spot  2.16.3
acc.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) by the Spot authors, see the AUTHORS file for details.
3 //
4 // This file is part of Spot, a model checking library.
5 //
6 // Spot is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // Spot is distributed in the hope that it will be useful, but WITHOUT
12 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 // License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 
19 #pragma once
20 
21 #include <functional>
22 #include <limits>
23 #include <sstream>
24 #include <stdexcept>
25 #include <vector>
26 #include <iostream>
27 #include <algorithm>
28 #include <numeric>
29 #include <bddx.h>
30 #include <tuple>
31 #include <spot/misc/_config.h>
32 #include <spot/misc/bitset.hh>
33 #include <spot/misc/trival.hh>
34 
35 namespace spot
36 {
37  namespace internal
38  {
39  class mark_container;
40  }
41 
44 
53  class SPOT_API acc_cond
54  {
55 #ifndef SWIG
56  private:
57  [[noreturn]] static void report_too_many_sets();
58 #endif
59  public:
60 
75  struct mark_t
76  {
77  private:
78  // configure guarantees that SPOT_MAX_ACCSETS % (8*sizeof(unsigned)) == 0
79  typedef bitset<SPOT_MAX_ACCSETS / (8*sizeof(unsigned))> _value_t;
80  _value_t id;
81 
82  mark_t(_value_t id) noexcept
83  : id(id)
84  {
85  }
86 
87  public:
89  mark_t() = default;
90 
91 #ifndef SWIG
93  template<class iterator>
94  mark_t(const iterator& begin, const iterator& end)
95  : mark_t(_value_t::zero())
96  {
97  for (iterator i = begin; i != end; ++i)
98  if (SPOT_LIKELY(*i < SPOT_MAX_ACCSETS))
99  set(*i);
100  else
101  report_too_many_sets();
102  }
103 
105  mark_t(std::initializer_list<unsigned> vals)
106  : mark_t(vals.begin(), vals.end())
107  {
108  }
109 #endif
110 
116  constexpr static unsigned max_accsets()
117  {
118  return SPOT_MAX_ACCSETS;
119  }
120 
126  static mark_t all()
127  {
128  return mark_t(_value_t::mone());
129  }
130 
132  size_t hash() const noexcept
133  {
134  std::hash<decltype(id)> h;
135  return h(id);
136  }
137 
139  bool operator==(mark_t o) const
140  {
141  return id == o.id;
142  }
143 
145  bool operator!=(mark_t o) const
146  {
147  return id != o.id;
148  }
149 
151  bool operator<(mark_t o) const
152  {
153  return id < o.id;
154  }
155 
157  bool operator<=(mark_t o) const
158  {
159  return id <= o.id;
160  }
161 
163  bool operator>(mark_t o) const
164  {
165  return id > o.id;
166  }
167 
169  bool operator>=(mark_t o) const
170  {
171  return id >= o.id;
172  }
173 
175  explicit operator bool() const
176  {
177  return !!id;
178  }
179 
181  bool has(unsigned u) const
182  {
183  return !!this->operator&(mark_t({0}) << u);
184  }
185 
187  void set(unsigned u)
188  {
189  id.set(u);
190  }
191 
198  void set_checked(unsigned u)
199  {
200  if (SPOT_UNLIKELY(u >= max_accsets()))
201  report_too_many_sets();
202  id.set(u);
203  }
204 
206  void clear(unsigned u)
207  {
208  id.clear(u);
209  }
210 
213  {
214  id &= r.id;
215  return *this;
216  }
217 
220  {
221  id |= r.id;
222  return *this;
223  }
224 
227  {
228  id &= ~r.id;
229  return *this;
230  }
231 
234  {
235  id ^= r.id;
236  return *this;
237  }
238 
241  {
242  return id & r.id;
243  }
244 
247  {
248  return id | r.id;
249  }
250 
253  {
254  return id & ~r.id;
255  }
256 
259  {
260  return ~id;
261  }
262 
265  {
266  return id ^ r.id;
267  }
268 
269 #if SPOT_DEBUG || defined(SWIGPYTHON)
270 # define SPOT_WRAP_OP(ins) \
271  try \
272  { \
273  ins; \
274  } \
275  catch (const std::runtime_error& e) \
276  { \
277  report_too_many_sets(); \
278  }
279 #else
280 # define SPOT_WRAP_OP(ins) ins;
281 #endif
283  mark_t operator<<(unsigned i) const
284  {
285  SPOT_WRAP_OP(return id << i);
286  }
287 
289  mark_t& operator<<=(unsigned i)
290  {
291  SPOT_WRAP_OP(id <<= i; return *this);
292  }
293 
295  mark_t operator>>(unsigned i) const
296  {
297  SPOT_WRAP_OP(return id >> i);
298  }
299 
301  mark_t& operator>>=(unsigned i)
302  {
303  SPOT_WRAP_OP(id >>= i; return *this);
304  }
305 #undef SPOT_WRAP_OP
306 
311  mark_t strip(mark_t y) const
312  {
313  // strip every bit of id that is marked in y
314  // 100101110100.strip(
315  // 001011001000)
316  // == 10 1 11 100
317  // == 10111100
318 
319  auto xv = id; // 100101110100
320  auto yv = y.id; // 001011001000
321 
322  while (yv && xv)
323  {
324  // Mask for everything after the last 1 in y
325  auto rm = (~yv) & (yv - 1); // 000000000111
326  // Mask for everything before the last 1 in y
327  auto lm = ~(yv ^ (yv - 1)); // 111111110000
328  xv = ((xv & lm) >> 1) | (xv & rm);
329  yv = (yv & lm) >> 1;
330  }
331  return xv;
332  }
333 
336  bool subset(mark_t m) const
337  {
338  return !((*this) - m);
339  }
340 
343  bool proper_subset(mark_t m) const
344  {
345  return *this != m && this->subset(m);
346  }
347 
349  unsigned count() const
350  {
351  return id.count();
352  }
353 
358  unsigned max_set() const
359  {
360  if (id)
361  return id.highest()+1;
362  else
363  return 0;
364  }
365 
370  unsigned min_set() const
371  {
372  if (id)
373  return id.lowest()+1;
374  else
375  return 0;
376  }
377 
382  mark_t lowest() const
383  {
384  return id & -id;
385  }
386 
388  bool is_singleton() const
389  {
390 #if __GNUC__
391  /* With GCC and Clang, count() is implemented using popcount. */
392  return count() == 1;
393 #else
394  return id && !(id & (id - 1));
395 #endif
396  }
397 
399  bool has_many() const
400  {
401 #if __GNUC__
402  /* With GCC and Clang, count() is implemented using popcount. */
403  return count() > 1;
404 #else
405  return !!(id & (id - 1));
406 #endif
407  }
408 
412  mark_t& remove_some(unsigned n)
413  {
414  while (n--)
415  id &= id - 1;
416  return *this;
417  }
418 
420  template<class iterator>
421  void fill(iterator here) const;
422 
424  spot::internal::mark_container sets() const;
425 
427  std::string as_string() const;
428  };
429 
431  enum class acc_op : unsigned
432  { Inf, Fin, InfNeg, FinNeg, And, Or };
433 
441  union acc_word
442  {
444  struct {
452  unsigned size:24;
453  } sub;
454  };
455 
468  struct SPOT_API acc_code: public std::vector<acc_word>
469  {
471  acc_code
473 
475  bool operator==(const acc_code& other) const
476  {
477  // We have two ways to represent t, unfortunately.
478  if (is_t() && other.is_t())
479  return true;
480  unsigned pos = size();
481  if (other.size() != pos)
482  return false;
483  while (pos > 0)
484  {
485  auto op = (*this)[pos - 1].sub.op;
486  auto sz = (*this)[pos - 1].sub.size;
487  if (other[pos - 1].sub.op != op ||
488  other[pos - 1].sub.size != sz)
489  return false;
490  switch (op)
491  {
492  case acc_cond::acc_op::And:
493  case acc_cond::acc_op::Or:
494  --pos;
495  break;
496  case acc_cond::acc_op::Inf:
497  case acc_cond::acc_op::InfNeg:
498  case acc_cond::acc_op::Fin:
499  case acc_cond::acc_op::FinNeg:
500  pos -= 2;
501  if (other[pos].mark != (*this)[pos].mark)
502  return false;
503  break;
504  }
505  }
506  return true;
507  };
508 
510  bool operator<(const acc_code& other) const
511  {
512  // We have two ways to represent t, unfortunately.
513  if (is_t() && other.is_t())
514  return false;
515  unsigned pos = size();
516  auto osize = other.size();
517  if (pos < osize)
518  return true;
519  if (pos > osize)
520  return false;
521  while (pos > 0)
522  {
523  auto op = (*this)[pos - 1].sub.op;
524  auto oop = other[pos - 1].sub.op;
525  if (op < oop)
526  return true;
527  if (op > oop)
528  return false;
529  auto sz = (*this)[pos - 1].sub.size;
530  auto osz = other[pos - 1].sub.size;
531  if (sz < osz)
532  return true;
533  if (sz > osz)
534  return false;
535  switch (op)
536  {
537  case acc_cond::acc_op::And:
538  case acc_cond::acc_op::Or:
539  --pos;
540  break;
541  case acc_cond::acc_op::Inf:
542  case acc_cond::acc_op::InfNeg:
543  case acc_cond::acc_op::Fin:
544  case acc_cond::acc_op::FinNeg:
545  {
546  pos -= 2;
547  auto m = (*this)[pos].mark;
548  auto om = other[pos].mark;
549  if (m < om)
550  return true;
551  if (m > om)
552  return false;
553  break;
554  }
555  }
556  }
557  return false;
558  }
559 
561  bool operator>(const acc_code& other) const
562  {
563  return other < *this;
564  }
565 
567  bool operator<=(const acc_code& other) const
568  {
569  return !(other < *this);
570  }
571 
573  bool operator>=(const acc_code& other) const
574  {
575  return !(*this < other);
576  }
577 
579  bool operator!=(const acc_code& other) const
580  {
581  return !(*this == other);
582  }
583 
588  bool is_t() const
589  {
590  // We store "t" as an empty condition, or as Inf({}).
591  unsigned s = size();
592  return s == 0 || ((*this)[s - 1].sub.op == acc_op::Inf
593  && !((*this)[s - 2].mark));
594  }
595 
602  bool is_f() const
603  {
604  // We store "f" as Fin({}).
605  unsigned s = size();
606  return s > 1
607  && (*this)[s - 1].sub.op == acc_op::Fin && !((*this)[s - 2].mark);
608  }
609 
610  private:
615  static constexpr size_t max_acc_formula_size_ = (1U << 24) - 1;
616 
617 #ifndef SWIG
619  [[noreturn]] static void report_too_large_acceptance_formula_()
620  {
621  throw std::runtime_error("acceptance formula is too large");
622  }
623 #endif
624 
625  public:
632  static acc_code f()
633  {
634  acc_code res;
635  res.resize(2);
636  res[0].mark = {};
637  res[1].sub.op = acc_op::Fin;
638  res[1].sub.size = 1;
639  return res;
640  }
641 
646  static acc_code t()
647  {
648  return {};
649  }
650 
658  static acc_code fin(mark_t m)
659  {
660  acc_code res;
661  res.resize(2);
662  res[0].mark = m;
663  res[1].sub.op = acc_op::Fin;
664  res[1].sub.size = 1;
665  return res;
666  }
667 
668  static acc_code fin(std::initializer_list<unsigned> vals)
669  {
670  return fin(mark_t(vals));
671  }
673 
691  {
692  acc_code res;
693  res.resize(2);
694  res[0].mark = m;
695  res[1].sub.op = acc_op::FinNeg;
696  res[1].sub.size = 1;
697  return res;
698  }
699 
700  static acc_code fin_neg(std::initializer_list<unsigned> vals)
701  {
702  return fin_neg(mark_t(vals));
703  }
705 
714  static acc_code inf(mark_t m)
715  {
716  acc_code res;
717  res.resize(2);
718  res[0].mark = m;
719  res[1].sub.op = acc_op::Inf;
720  res[1].sub.size = 1;
721  return res;
722  }
723 
724  static acc_code inf(std::initializer_list<unsigned> vals)
725  {
726  return inf(mark_t(vals));
727  }
729 
747  {
748  acc_code res;
749  res.resize(2);
750  res[0].mark = m;
751  res[1].sub.op = acc_op::InfNeg;
752  res[1].sub.size = 1;
753  return res;
754  }
755 
756  static acc_code inf_neg(std::initializer_list<unsigned> vals)
757  {
758  return inf_neg(mark_t(vals));
759  }
761 
765  static acc_code buchi()
766  {
767  return inf({0});
768  }
769 
773  static acc_code cobuchi()
774  {
775  return fin({0});
776  }
777 
783  static acc_code generalized_buchi(unsigned n)
784  {
785  if (n == 0)
786  return inf({});
787  acc_cond::mark_t m = mark_t::all();
788  m >>= mark_t::max_accsets() - n;
789  return inf(m);
790  }
791 
797  static acc_code generalized_co_buchi(unsigned n)
798  {
799  if (n == 0)
800  return fin({});
801  acc_cond::mark_t m = mark_t::all();
802  m >>= mark_t::max_accsets() - n;
803  return fin(m);
804  }
805 
810  static acc_code rabin(unsigned n)
811  {
812  acc_cond::acc_code res = f();
813  while (n > 0)
814  {
815  res |= inf({2*n - 1}) & fin({2*n - 2});
816  --n;
817  }
818  return res;
819  }
820 
825  static acc_code streett(unsigned n)
826  {
827  acc_cond::acc_code res = t();
828  while (n > 0)
829  {
830  res &= inf({2*n - 1}) | fin({2*n - 2});
831  --n;
832  }
833  return res;
834  }
835 
848  template<class Iterator>
849  static acc_code generalized_rabin(Iterator begin, Iterator end)
850  {
851  acc_cond::acc_code res = f();
852  unsigned n = 0;
853  for (Iterator i = begin; i != end; ++i)
854  {
855  unsigned f = n++;
856  acc_cond::mark_t m = {};
857  for (unsigned ni = *i; ni > 0; --ni)
858  m.set(n++);
859  auto pair = inf(m) & fin({f});
860  std::swap(pair, res);
861  res |= std::move(pair);
862  }
863  return res;
864  }
865 
873  static acc_code parity(bool is_max, bool is_odd, unsigned sets);
874  static acc_code parity_max(bool is_odd, unsigned sets)
875  {
876  return parity(true, is_odd, sets);
877  }
878  static acc_code parity_max_odd(unsigned sets)
879  {
880  return parity_max(true, sets);
881  }
882  static acc_code parity_max_even(unsigned sets)
883  {
884  return parity_max(false, sets);
885  }
886  static acc_code parity_min(bool is_odd, unsigned sets)
887  {
888  return parity(false, is_odd, sets);
889  }
890  static acc_code parity_min_odd(unsigned sets)
891  {
892  return parity_min(true, sets);
893  }
894  static acc_code parity_min_even(unsigned sets)
895  {
896  return parity_min(false, sets);
897  }
899 
916  static acc_code random(unsigned n, double reuse = 0.0);
917 
920  {
921  if (is_t() || r.is_f())
922  {
923  *this = r;
924  return *this;
925  }
926  if (is_f() || r.is_t())
927  return *this;
928  unsigned s = size() - 1;
929  unsigned rs = r.size() - 1;
930  // We want to group all Inf(x) operators:
931  // Inf(a) & Inf(b) = Inf(a & b)
932  if (((*this)[s].sub.op == acc_op::Inf
933  && r[rs].sub.op == acc_op::Inf)
934  || ((*this)[s].sub.op == acc_op::InfNeg
935  && r[rs].sub.op == acc_op::InfNeg))
936  {
937  (*this)[s - 1].mark |= r[rs - 1].mark;
938  return *this;
939  }
940 
941  // In the more complex scenarios, left and right may both
942  // be conjunctions, and Inf(x) might be a member of each
943  // side. Find it if it exists.
944  // left_inf points to the left Inf mark if any.
945  // right_inf points to the right Inf mark if any.
946  acc_word* left_inf = nullptr;
947  if ((*this)[s].sub.op == acc_op::And)
948  {
949  auto start = &(*this)[s] - (*this)[s].sub.size;
950  auto pos = &(*this)[s] - 1;
951  pop_back();
952  while (pos > start)
953  {
954  if (pos->sub.op == acc_op::Inf)
955  {
956  left_inf = pos - 1;
957  break;
958  }
959  pos -= pos->sub.size + 1;
960  }
961  }
962  else if ((*this)[s].sub.op == acc_op::Inf)
963  {
964  left_inf = &(*this)[s - 1];
965  }
966 
967  const acc_word* right_inf = nullptr;
968  auto right_end = &r.back();
969  if (right_end->sub.op == acc_op::And)
970  {
971  auto start = &r[0];
972  auto pos = --right_end;
973  while (pos > start)
974  {
975  if (pos->sub.op == acc_op::Inf)
976  {
977  right_inf = pos - 1;
978  break;
979  }
980  pos -= pos->sub.size + 1;
981  }
982  }
983  else if (right_end->sub.op == acc_op::Inf)
984  {
985  right_inf = right_end - 1;
986  }
987 
988  acc_cond::mark_t carry = {};
989  if (left_inf && right_inf)
990  {
991  carry = left_inf->mark;
992  auto pos = left_inf - &(*this)[0];
993  erase(begin() + pos, begin() + pos + 2);
994  }
995  auto sz = size();
996  insert(end(), &r[0], right_end + 1);
997  if (carry)
998  (*this)[sz + (right_inf - &r[0])].mark |= carry;
999 
1000  acc_word w = {};
1001  w.sub.op = acc_op::And;
1002  auto new_size = size();
1003  if (SPOT_UNLIKELY(new_size > max_acc_formula_size_))
1004  report_too_large_acceptance_formula_();
1005  w.sub.size = new_size;
1006  emplace_back(w);
1007  return *this;
1008  }
1009 
1011  acc_code operator&(const acc_code& r) const
1012  {
1013  acc_code res = *this;
1014  res &= r;
1015  return res;
1016  }
1017 
1018 #ifndef SWIG
1021  {
1022  acc_code res = *this;
1023  res &= r;
1024  return res;
1025  }
1026 #endif // SWIG
1027 
1030  {
1031  if (is_t() || r.is_f())
1032  return *this;
1033  if (is_f() || r.is_t())
1034  {
1035  *this = r;
1036  return *this;
1037  }
1038  unsigned s = size() - 1;
1039  unsigned rs = r.size() - 1;
1040  // Fin(a) | Fin(b) = Fin(a | b)
1041  if (((*this)[s].sub.op == acc_op::Fin
1042  && r[rs].sub.op == acc_op::Fin)
1043  || ((*this)[s].sub.op == acc_op::FinNeg
1044  && r[rs].sub.op == acc_op::FinNeg))
1045  {
1046  (*this)[s - 1].mark |= r[rs - 1].mark;
1047  return *this;
1048  }
1049 
1050  // In the more complex scenarios, left and right may both
1051  // be disjunctions, and Fin(x) might be a member of each
1052  // side. Find it if it exists.
1053  // left_inf points to the left Inf mark if any.
1054  // right_inf points to the right Inf mark if any.
1055  acc_word* left_fin = nullptr;
1056  if ((*this)[s].sub.op == acc_op::Or)
1057  {
1058  auto start = &(*this)[s] - (*this)[s].sub.size;
1059  auto pos = &(*this)[s] - 1;
1060  pop_back();
1061  while (pos > start)
1062  {
1063  if (pos->sub.op == acc_op::Fin)
1064  {
1065  left_fin = pos - 1;
1066  break;
1067  }
1068  pos -= pos->sub.size + 1;
1069  }
1070  }
1071  else if ((*this)[s].sub.op == acc_op::Fin)
1072  {
1073  left_fin = &(*this)[s - 1];
1074  }
1075 
1076  const acc_word* right_fin = nullptr;
1077  auto right_end = &r.back();
1078  if (right_end->sub.op == acc_op::Or)
1079  {
1080  auto start = &r[0];
1081  auto pos = --right_end;
1082  while (pos > start)
1083  {
1084  if (pos->sub.op == acc_op::Fin)
1085  {
1086  right_fin = pos - 1;
1087  break;
1088  }
1089  pos -= pos->sub.size + 1;
1090  }
1091  }
1092  else if (right_end->sub.op == acc_op::Fin)
1093  {
1094  right_fin = right_end - 1;
1095  }
1096 
1097  acc_cond::mark_t carry = {};
1098  if (left_fin && right_fin)
1099  {
1100  carry = left_fin->mark;
1101  auto pos = (left_fin - &(*this)[0]);
1102  this->erase(begin() + pos, begin() + pos + 2);
1103  }
1104  auto sz = size();
1105  insert(end(), &r[0], right_end + 1);
1106  if (carry)
1107  (*this)[sz + (right_fin - &r[0])].mark |= carry;
1108  acc_word w = {};
1109  w.sub.op = acc_op::Or;
1110  auto new_size = size();
1111  if (SPOT_UNLIKELY(new_size > max_acc_formula_size_))
1112  report_too_large_acceptance_formula_();
1113  w.sub.size = new_size;
1114  emplace_back(w);
1115  return *this;
1116  }
1117 
1118 #ifndef SWIG
1121  {
1122  acc_code res = *this;
1123  res |= r;
1124  return res;
1125  }
1126 #endif // SWIG
1127 
1129  acc_code operator|(const acc_code& r) const
1130  {
1131  acc_code res = *this;
1132  res |= r;
1133  return res;
1134  }
1135 
1141  acc_code& operator<<=(unsigned sets)
1142  {
1143  if (SPOT_UNLIKELY(sets >= mark_t::max_accsets()))
1144  report_too_many_sets();
1145  if (empty())
1146  return *this;
1147  unsigned pos = size();
1148  do
1149  {
1150  switch ((*this)[pos - 1].sub.op)
1151  {
1152  case acc_cond::acc_op::And:
1153  case acc_cond::acc_op::Or:
1154  --pos;
1155  break;
1156  case acc_cond::acc_op::Inf:
1157  case acc_cond::acc_op::InfNeg:
1158  case acc_cond::acc_op::Fin:
1159  case acc_cond::acc_op::FinNeg:
1160  pos -= 2;
1161  (*this)[pos].mark <<= sets;
1162  break;
1163  }
1164  }
1165  while (pos > 0);
1166  return *this;
1167  }
1168 
1172  acc_code operator<<(unsigned sets) const
1173  {
1174  acc_code res = *this;
1175  res <<= sets;
1176  return res;
1177  }
1178 
1185  bool is_dnf() const;
1186 
1193  bool is_cnf() const;
1194 
1205  acc_code to_dnf() const;
1206 
1213  acc_code to_cnf() const;
1214 
1219  bdd to_bdd(const bdd* map) const;
1220 
1229  std::vector<acc_code> top_disjuncts() const;
1230 
1239  std::vector<acc_code> top_conjuncts() const;
1240 
1252 
1266  mark_t fin_unit() const;
1267 
1280  mark_t mafins() const;
1281 
1293  mark_t inf_unit() const;
1294 
1299  int fin_one() const;
1300 
1321  std::pair<int, acc_code> fin_one_extract() const;
1322 
1341  std::tuple<int, acc_cond::acc_code, acc_cond::acc_code>
1343  std::tuple<int, acc_cond::acc_code, acc_cond::acc_code>
1346 
1362  std::vector<std::pair<acc_cond::mark_t, acc_cond::acc_code>>
1363  mafins_split() const;
1364 
1377  std::vector<std::vector<int>>
1378  missing(mark_t inf, bool accepting) const;
1379 
1382  bool accepting(mark_t inf) const;
1383 
1390  bool inf_satisfiable(mark_t inf) const;
1391 
1403  trival maybe_accepting(mark_t infinitely_often,
1404  mark_t always_present) const;
1405 
1419  trival weakly_accepting(mark_t infinitely_often,
1420  mark_t always_present) const;
1421 
1432  std::vector<unsigned> symmetries() const;
1433 
1447  acc_code remove(acc_cond::mark_t rem, bool missing) const;
1448 
1453  acc_code strip(acc_cond::mark_t rem, bool missing) const;
1456 
1463 
1466 
1478  std::vector<std::pair<acc_cond::mark_t, acc_cond::mark_t>>
1480 
1488 
1490  std::pair<acc_cond::mark_t, acc_cond::mark_t> used_inf_fin_sets() const;
1491 
1496  std::ostream&
1497  to_html(std::ostream& os,
1498  std::function<void(std::ostream&, int)>
1499  set_printer = nullptr) const;
1500 
1505  std::ostream&
1506  to_text(std::ostream& os,
1507  std::function<void(std::ostream&, int)>
1508  set_printer = nullptr) const;
1509 
1514  std::ostream&
1515  to_latex(std::ostream& os,
1516  std::function<void(std::ostream&, int)>
1517  set_printer = nullptr) const;
1518 
1541  acc_code(const char* input);
1542 
1547  {
1548  }
1549 
1551  acc_code(const acc_word* other)
1552  : std::vector<acc_word>(other - other->sub.size, other + 1)
1553  {
1554  }
1555 
1556  };
1557 
1565  acc_cond(unsigned n_sets = 0, const acc_code& code = {})
1566  : num_(0U), all_({}), code_(code)
1567  {
1568  add_sets(n_sets);
1569  uses_fin_acceptance_ = check_fin_acceptance();
1570  }
1571 
1576  acc_cond(const acc_code& code)
1577  : num_(0U), all_({}), code_(code)
1578  {
1579  add_sets(code.used_sets().max_set());
1580  uses_fin_acceptance_ = check_fin_acceptance();
1581  }
1582 
1584  acc_cond(const acc_cond& o)
1585  : num_(o.num_), all_(o.all_), code_(o.code_),
1586  uses_fin_acceptance_(o.uses_fin_acceptance_)
1587  {
1588  }
1589 
1592  {
1593  num_ = o.num_;
1594  all_ = o.all_;
1595  code_ = o.code_;
1596  uses_fin_acceptance_ = o.uses_fin_acceptance_;
1597  return *this;
1598  }
1599 
1600  ~acc_cond()
1601  {
1602  }
1603 
1607  void set_acceptance(const acc_code& code)
1608  {
1609  code_ = code;
1610  uses_fin_acceptance_ = check_fin_acceptance();
1611  }
1612 
1614  const acc_code& get_acceptance() const
1615  {
1616  return code_;
1617  }
1618 
1621  {
1622  return code_;
1623  }
1624 
1626  bool operator==(const acc_cond& other) const
1627  {
1628  if (other.num_sets() != num_)
1629  return false;
1630  const acc_code& ocode = other.get_acceptance();
1631  // We have two ways to represent t, unfortunately.
1632  return (ocode == code_ || (ocode.is_t() && code_.is_t()));
1633  }
1634 
1636  bool operator!=(const acc_cond& other) const
1637  {
1638  return !(*this == other);
1639  }
1640 
1642  bool uses_fin_acceptance() const
1643  {
1644  return uses_fin_acceptance_;
1645  }
1646 
1648  bool is_t() const
1649  {
1650  return code_.is_t();
1651  }
1652 
1657  bool is_all() const
1658  {
1659  return num_ == 0 && is_t();
1660  }
1661 
1663  bool is_f() const
1664  {
1665  return code_.is_f();
1666  }
1667 
1672  bool is_none() const
1673  {
1674  return num_ == 0 && is_f();
1675  }
1676 
1681  bool is_buchi() const
1682  {
1683  unsigned s = code_.size();
1684  return num_ == 1 &&
1685  s == 2 && code_[1].sub.op == acc_op::Inf && code_[0].mark == all_sets();
1686  }
1687 
1692  bool is_co_buchi() const
1693  {
1694  return num_ == 1 && is_generalized_co_buchi();
1695  }
1696 
1700  {
1701  set_acceptance(inf(all_sets()));
1702  }
1703 
1707  {
1708  set_acceptance(fin(all_sets()));
1709  }
1710 
1716  {
1717  unsigned s = code_.size();
1718  return (s == 0 && num_ == 0) || (s == 2 && code_[1].sub.op == acc_op::Inf
1719  && code_[0].mark == all_sets());
1720  }
1721 
1727  {
1728  unsigned s = code_.size();
1729  return (s == 2 &&
1730  code_[1].sub.op == acc_op::Fin && code_[0].mark == all_sets());
1731  }
1732 
1744  int is_rabin() const;
1745 
1757  int is_streett() const;
1758 
1768  struct SPOT_API rs_pair
1769  {
1770 #ifndef SWIG
1771  rs_pair() = default;
1773  rs_pair(const rs_pair&) = default;
1775  rs_pair& operator=(const rs_pair&) = default;
1776 #endif
1777 
1780  fin(fin),
1781  inf(inf)
1782  {}
1785 
1787  bool operator==(rs_pair o) const
1788  {
1789  return fin == o.fin && inf == o.inf;
1790  }
1792  bool operator!=(rs_pair o) const
1793  {
1794  return fin != o.fin || inf != o.inf;
1795  }
1797  bool operator<(rs_pair o) const
1798  {
1799  return fin < o.fin || (!(o.fin < fin) && inf < o.inf);
1800  }
1802  bool operator<=(rs_pair o) const
1803  {
1804  return !(o < *this);
1805  }
1807  bool operator>(rs_pair o) const
1808  {
1809  return o < *this;
1810  }
1812  bool operator>=(rs_pair o) const
1813  {
1814  return !(*this < o);
1815  }
1816  };
1827  bool is_streett_like(std::vector<rs_pair>& pairs) const;
1828 
1839  bool is_rabin_like(std::vector<rs_pair>& pairs) const;
1840 
1850  bool is_generalized_rabin(std::vector<unsigned>& pairs) const;
1851 
1864  bool is_generalized_streett(std::vector<unsigned>& pairs) const;
1865 
1875  bool is_parity(bool& max, bool& odd, bool equiv = false) const;
1876 
1877 
1880  bool is_parity() const
1881  {
1882  bool max;
1883  bool odd;
1884  return is_parity(max, odd);
1885  }
1886 
1895  {
1896  return acc_cond(num_, code_.unit_propagation());
1897  }
1898 
1903  std::pair<bool, acc_cond::mark_t> unsat_mark() const
1904  {
1905  return sat_unsat_mark(false);
1906  }
1911  std::pair<bool, acc_cond::mark_t> sat_mark() const
1912  {
1913  return sat_unsat_mark(true);
1914  }
1915 
1916  protected:
1918  bool check_fin_acceptance() const;
1920  std::pair<bool, acc_cond::mark_t> sat_unsat_mark(bool) const;
1921 
1922  public:
1931  static acc_code inf(mark_t mark)
1932  {
1933  return acc_code::inf(mark);
1934  }
1935 
1936  static acc_code inf(std::initializer_list<unsigned> vals)
1937  {
1938  return inf(mark_t(vals.begin(), vals.end()));
1939  }
1941 
1958  static acc_code inf_neg(mark_t mark)
1959  {
1960  return acc_code::inf_neg(mark);
1961  }
1962 
1963  static acc_code inf_neg(std::initializer_list<unsigned> vals)
1964  {
1965  return inf_neg(mark_t(vals.begin(), vals.end()));
1966  }
1968 
1976  static acc_code fin(mark_t mark)
1977  {
1978  return acc_code::fin(mark);
1979  }
1980 
1981  static acc_code fin(std::initializer_list<unsigned> vals)
1982  {
1983  return fin(mark_t(vals.begin(), vals.end()));
1984  }
1986 
2003  static acc_code fin_neg(mark_t mark)
2004  {
2005  return acc_code::fin_neg(mark);
2006  }
2007 
2008  static acc_code fin_neg(std::initializer_list<unsigned> vals)
2009  {
2010  return fin_neg(mark_t(vals.begin(), vals.end()));
2011  }
2013 
2018  unsigned add_sets(unsigned num)
2019  {
2020  if (num == 0)
2021  return -1U;
2022  unsigned j = num_;
2023  num += j;
2024  if (num > mark_t::max_accsets())
2025  report_too_many_sets();
2026  // Make sure we do not update if we raised an exception.
2027  num_ = num;
2028  all_ = all_sets_();
2029  return j;
2030  }
2031 
2036  unsigned add_set()
2037  {
2038  return add_sets(1);
2039  }
2040 
2042  mark_t mark(unsigned u) const
2043  {
2044  SPOT_ASSERT(u < num_sets());
2045  return mark_t({u});
2046  }
2047 
2052  mark_t comp(const mark_t& l) const
2053  {
2054  return all_ ^ l;
2055  }
2056 
2059  {
2060  return all_;
2061  }
2062 
2065  bool accepting(mark_t inf) const
2066  {
2067  return code_.accepting(inf);
2068  }
2069 
2075  bool inf_satisfiable(mark_t inf) const
2076  {
2077  return code_.inf_satisfiable(inf);
2078  }
2079 
2086  {
2087  return {num_sets(), code_.keep_one_inf_per_branch()};
2088  }
2089 
2101  trival maybe_accepting(mark_t infinitely_often, mark_t always_present) const
2102  {
2103  return code_.maybe_accepting(infinitely_often, always_present);
2104  }
2105 
2119  trival
2120  weakly_accepting(mark_t infinitely_often, mark_t always_present) const
2121  {
2122  return code_.weakly_accepting(infinitely_often, always_present);
2123  }
2124 
2139 
2141  unsigned num_sets() const
2142  {
2143  return num_;
2144  }
2145 
2153  template<class iterator>
2154  mark_t useless(iterator begin, iterator end) const
2155  {
2156  mark_t u = {}; // The set of useless sets
2157  for (unsigned x = 0; x < num_; ++x)
2158  {
2159  // Skip sets that are already known to be useless.
2160  if (u.has(x))
2161  continue;
2162  auto all = comp(u | mark_t({x}));
2163  // Iterate over all mark_t, and keep track of
2164  // set numbers that always appear with x.
2165  for (iterator y = begin; y != end; ++y)
2166  {
2167  const mark_t& v = *y;
2168  if (v.has(x))
2169  {
2170  all &= v;
2171  if (!all)
2172  break;
2173  }
2174  }
2175  u |= all;
2176  }
2177  return u;
2178  }
2179 
2193  acc_cond remove(mark_t rem, bool missing) const
2194  {
2195  return {num_sets(), code_.remove(rem, missing)};
2196  }
2197 
2202  acc_cond strip(mark_t rem, bool missing) const
2203  {
2204  return
2205  { num_sets() - (all_sets() & rem).count(), code_.strip(rem, missing) };
2206  }
2207 
2210  {
2211  return {num_sets(), code_.force_inf(m)};
2212  }
2213 
2217  {
2218  return {num_sets(), code_.remove(all_sets() - rem, true)};
2219  }
2220 
2232  std::string name(const char* fmt = "alo") const;
2233 
2248  {
2249  return code_.fin_unit();
2250  }
2251 
2264  mark_t mafins() const
2265  {
2266  return code_.mafins();
2267  }
2268 
2273  std::vector<std::pair<mark_t, acc_cond>> mafins_split() const
2274  {
2275  auto v = code_.mafins_split();
2276  std::vector<std::pair<mark_t, acc_cond>> result;
2277  result.reserve(v.size());
2278  for (auto& [m, c] : v)
2279  result.emplace_back(m, acc_cond(num_, c));
2280  return result;
2281  }
2282 
2295  {
2296  return code_.inf_unit();
2297  }
2298 
2303  int fin_one() const
2304  {
2305  return code_.fin_one();
2306  }
2307 
2328  std::pair<int, acc_cond> fin_one_extract() const
2329  {
2330  auto [f, c] = code_.fin_one_extract();
2331  return {f, {num_sets(), std::move(c)}};
2332  }
2333 
2352  std::tuple<int, acc_cond, acc_cond>
2354  {
2355  auto [f, l, r] = code_.fin_unit_one_split();
2356  return {f, {num_sets(), std::move(l)}, {num_sets(), std::move(r)}};
2357  }
2358  std::tuple<int, acc_cond, acc_cond>
2360  {
2361  auto [f, l, r] = code_.fin_unit_one_split_improved();
2362  return {f, {num_sets(), std::move(l)}, {num_sets(), std::move(r)}};
2363  }
2365 
2374  std::vector<acc_cond> top_disjuncts() const;
2375 
2384  std::vector<acc_cond> top_conjuncts() const;
2385 
2386  protected:
2389  {
2390  return mark_t::all() >> (spot::acc_cond::mark_t::max_accsets() - num_);
2391  }
2392 
2393  unsigned num_;
2397  bool uses_fin_acceptance_ = false;
2398 
2399  };
2400 
2403  struct rs_pairs_view {
2405  typedef std::vector<acc_cond::rs_pair> rs_pairs;
2406 
2408  explicit rs_pairs_view(const rs_pairs& p, const acc_cond::mark_t& m)
2409  : pairs_(p), view_marks_(m) {}
2410 
2412  explicit rs_pairs_view(const rs_pairs& p)
2413  : rs_pairs_view(p, acc_cond::mark_t::all()) {}
2414 
2417  {
2418  return do_view([&](const acc_cond::rs_pair& p)
2419  {
2420  return visible(p.inf) ? p.inf : acc_cond::mark_t({});
2421  });
2422  }
2423 
2426  {
2427  return do_view([&](const acc_cond::rs_pair& p)
2428  {
2429  return visible(p.fin) ? p.fin : acc_cond::mark_t({});
2430  });
2431  }
2432 
2435  {
2436  return do_view([&](const acc_cond::rs_pair& p)
2437  {
2438  return !visible(p.inf) && visible(p.fin) ? p.fin
2439  : acc_cond::mark_t({});
2440  });
2441  }
2442 
2445  {
2446  return do_view([&](const acc_cond::rs_pair& p)
2447  {
2448  return !visible(p.fin) && visible(p.inf) ? p.inf
2449  : acc_cond::mark_t({});
2450  });
2451  }
2452 
2456  acc_cond::mark_t paired_with_fin(unsigned mark) const
2457  {
2458  acc_cond::mark_t res = {};
2459  for (const auto& p: pairs_)
2460  if (p.fin.has(mark) && visible(p.fin) && visible(p.inf))
2461  res |= p.inf;
2462  return res;
2463  }
2464 
2466  const rs_pairs& pairs() const
2467  {
2468  return pairs_;
2469  }
2470 
2471  private:
2472  template<typename filter>
2473  acc_cond::mark_t do_view(const filter& filt) const
2474  {
2475  acc_cond::mark_t res = {};
2476  for (const auto& p: pairs_)
2477  res |= filt(p);
2478  return res;
2479  }
2480 
2481  bool visible(const acc_cond::mark_t& v) const
2482  {
2483  return !!(view_marks_ & v);
2484  }
2485 
2486  const rs_pairs& pairs_;
2487  acc_cond::mark_t view_marks_;
2488  };
2489 
2490 
2491  SPOT_API
2492  std::ostream& operator<<(std::ostream& os, const acc_cond& acc);
2493 
2494  // The next two operators used to be declared as friend inside the
2495  // acc_cond::mark_t and acc_cond::acc_code, but Swig 4.2.1
2496  // introduced a bug with friend operators. See
2497  // https://github.com/swig/swig/issues/2845
2498 
2499  SPOT_API
2500  std::ostream& operator<<(std::ostream& os, acc_cond::mark_t m);
2501 
2503  SPOT_API
2504  std::ostream& operator<<(std::ostream& os,
2505  const acc_cond::acc_code& code);
2506 
2508 
2509  namespace internal
2510  {
2511  class SPOT_API mark_iterator
2512  {
2513  public:
2514  typedef unsigned value_type;
2515  typedef const value_type& reference;
2516  typedef const value_type* pointer;
2517  typedef std::ptrdiff_t difference_type;
2518  typedef std::forward_iterator_tag iterator_category;
2519 
2520  mark_iterator() noexcept
2521  : m_({})
2522  {
2523  }
2524 
2525  mark_iterator(acc_cond::mark_t m) noexcept
2526  : m_(m)
2527  {
2528  }
2529 
2530  bool operator==(mark_iterator m) const
2531  {
2532  return m_ == m.m_;
2533  }
2534 
2535  bool operator!=(mark_iterator m) const
2536  {
2537  return m_ != m.m_;
2538  }
2539 
2540  value_type operator*() const
2541  {
2542  SPOT_ASSERT(m_);
2543  return m_.min_set() - 1;
2544  }
2545 
2546  mark_iterator& operator++()
2547  {
2548  m_.clear(this->operator*());
2549  return *this;
2550  }
2551 
2552  mark_iterator operator++(int)
2553  {
2554  mark_iterator it = *this;
2555  ++(*this);
2556  return it;
2557  }
2558  private:
2559  acc_cond::mark_t m_;
2560  };
2561 
2562  class SPOT_API mark_container
2563  {
2564  public:
2565  mark_container(spot::acc_cond::mark_t m) noexcept
2566  : m_(m)
2567  {
2568  }
2569 
2570  mark_iterator begin() const
2571  {
2572  return {m_};
2573  }
2574  mark_iterator end() const
2575  {
2576  return {};
2577  }
2578  private:
2580  };
2581  }
2582 
2583  inline spot::internal::mark_container acc_cond::mark_t::sets() const
2584  {
2585  return {*this};
2586  }
2587 
2588  template<class iterator>
2589  void acc_cond::mark_t::fill(iterator here) const
2590  {
2591  for (unsigned s : sets())
2592  *here++ = s;
2593  }
2594 }
2595 
2596 namespace std
2597 {
2600  template<>
2601  struct hash<spot::acc_cond::mark_t>
2602  {
2604  size_t operator()(spot::acc_cond::mark_t m) const noexcept
2605  {
2606  return m.hash();
2607  }
2608  };
2609 }
An acceptance condition.
Definition: acc.hh:54
bool inf_satisfiable(mark_t inf) const
Assuming that we will visit at least all sets in inf, is there any chance that we will satisfy the co...
Definition: acc.hh:2075
mark_t all_sets() const
Construct a mark_t with all declared sets.
Definition: acc.hh:2058
static acc_code fin_neg(mark_t mark)
Construct a generalized co-Büchi acceptance for complemented sets.
Definition: acc.hh:2003
mark_t mafins() const
Find a Fin(i) that is mandatory.
Definition: acc.hh:2264
static acc_code inf_neg(mark_t mark)
Construct a generalized Büchi acceptance for complemented sets.
Definition: acc.hh:1958
std::pair< bool, acc_cond::mark_t > sat_unsat_mark(bool) const
Shared implementation for sat_mark() and unsat_mark().
acc_cond unit_propagation()
Remove superfluous Fin and Inf by unit propagation.
Definition: acc.hh:1894
void set_generalized_co_buchi()
Change the acceptance condition to generalized-co-Büchi, over all declared sets.
Definition: acc.hh:1706
std::pair< bool, acc_cond::mark_t > unsat_mark() const
Return an unsatisfying mark if one exists.
Definition: acc.hh:1903
const acc_code & get_acceptance() const
Retrieve the acceptance formula.
Definition: acc.hh:1614
bool operator==(const acc_cond &other) const
Equality: same number of sets and equivalent formula.
Definition: acc.hh:1626
static acc_code fin(mark_t mark)
Construct a generalized co-Büchi acceptance.
Definition: acc.hh:1976
bool is_co_buchi() const
Whether the acceptance condition is "co-Büchi".
Definition: acc.hh:1692
bool accepting(mark_t inf) const
Check whether visiting exactly all sets inf infinitely often satisfies the acceptance condition.
Definition: acc.hh:2065
static acc_code inf(mark_t mark)
Construct a generalized Büchi acceptance.
Definition: acc.hh:1931
unsigned num_
Number of declared acceptance sets.
Definition: acc.hh:2393
bool is_generalized_buchi() const
Whether the acceptance condition is "generalized-Büchi".
Definition: acc.hh:1715
static acc_code fin_neg(std::initializer_list< unsigned > vals)
Construct a generalized co-Büchi acceptance for complemented sets.
Definition: acc.hh:2008
static acc_code inf(std::initializer_list< unsigned > vals)
Construct a generalized Büchi acceptance.
Definition: acc.hh:1936
unsigned add_set()
Add a single set to the acceptance condition.
Definition: acc.hh:2036
bool check_fin_acceptance() const
Recompute whether the formula uses Fin acceptance.
bool is_parity(bool &max, bool &odd, bool equiv=false) const
Check if the acceptance condition matches one of the four type of parity acceptance defined in the HO...
mark_t mark(unsigned u) const
Build a mark_t with a single set.
Definition: acc.hh:2042
void set_generalized_buchi()
Change the acceptance condition to generalized-Büchi, over all declared sets.
Definition: acc.hh:1699
acc_cond force_inf(mark_t m) const
For all x in m, replaces Fin(x) by false.
Definition: acc.hh:2209
acc_cond remove(mark_t rem, bool missing) const
Remove all the acceptance sets in rem.
Definition: acc.hh:2193
std::tuple< int, acc_cond, acc_cond > fin_unit_one_split() const
Split an acceptance condition, trying to select one unit-Fin.
Definition: acc.hh:2353
acc_cond(unsigned n_sets=0, const acc_code &code={})
Build an acceptance condition.
Definition: acc.hh:1565
unsigned add_sets(unsigned num)
Add more sets to the acceptance condition.
Definition: acc.hh:2018
bool is_parity() const
Check if the acceptance condition matches one of the four type of parity acceptance defined in the HO...
Definition: acc.hh:1880
bool is_t() const
Whether the acceptance formula is "t" (true)
Definition: acc.hh:1648
trival weakly_accepting(mark_t infinitely_often, mark_t always_present) const
Check if cycles in a SCC are all accepting, all rejecting, or mixed.
Definition: acc.hh:2120
bool is_generalized_rabin(std::vector< unsigned > &pairs) const
Is the acceptance condition generalized-Rabin?
acc_op
Operators for acceptance formulas.
Definition: acc.hh:432
mark_t comp(const mark_t &l) const
Complement a mark_t.
Definition: acc.hh:2052
acc_cond keep_one_inf_per_branch() const
Rewrite an acceptance condition by keeping at most one Inf(x) on each disjunctive branch.
Definition: acc.hh:2085
std::tuple< int, acc_cond, acc_cond > fin_unit_one_split_improved() const
Split an acceptance condition, trying to select one unit-Fin.
Definition: acc.hh:2359
std::vector< acc_cond > top_conjuncts() const
Return the top-level conjuncts.
std::pair< int, acc_cond > fin_one_extract() const
Return one acceptance set i that appears as Fin(i) in the condition, and all disjuncts containing it ...
Definition: acc.hh:2328
static acc_code fin(std::initializer_list< unsigned > vals)
Construct a generalized co-Büchi acceptance.
Definition: acc.hh:1981
bool is_generalized_co_buchi() const
Whether the acceptance condition is "generalized-co-Büchi".
Definition: acc.hh:1726
std::vector< std::pair< mark_t, acc_cond > > mafins_split() const
Split an acceptance condition into disjuncts according to mandatory fins.
Definition: acc.hh:2273
acc_cond restrict_to(mark_t rem) const
Restrict an acceptance condition to a subset of set numbers that are occurring at some point.
Definition: acc.hh:2216
trival maybe_accepting(mark_t infinitely_often, mark_t always_present) const
Check potential acceptance of an SCC.
Definition: acc.hh:2101
std::string name(const char *fmt="alo") const
Return the name of this acceptance condition, in the specified format.
bool is_none() const
Whether the acceptance condition is "none".
Definition: acc.hh:1672
void set_acceptance(const acc_code &code)
Change the acceptance formula.
Definition: acc.hh:1607
int is_rabin() const
Check if the acceptance condition matches the Rabin acceptance of the HOA format.
bool uses_fin_acceptance_
Whether the formula contains any Fin term.
Definition: acc.hh:2397
bool is_rabin_like(std::vector< rs_pair > &pairs) const
Test whether an acceptance condition is Rabin-like and returns each Rabin pair in an std::vector<rs_p...
mark_t accepting_sets(mark_t inf) const
Return an accepting subset of inf.
bool is_all() const
Whether the acceptance condition is "all".
Definition: acc.hh:1657
acc_cond strip(mark_t rem, bool missing) const
Remove acceptance sets, and shift set numbers.
Definition: acc.hh:2202
int fin_one() const
Return one acceptance set i that appear as Fin(i) in the condition.
Definition: acc.hh:2303
mark_t all_sets_() const
Returns a mark with one bit set per declared acceptance set.
Definition: acc.hh:2388
mark_t useless(iterator begin, iterator end) const
Compute useless acceptance sets given a list of mark_t that occur in an SCC.
Definition: acc.hh:2154
int is_streett() const
Check if the acceptance condition matches the Streett acceptance of the HOA format.
mark_t fin_unit() const
Find a Fin(i) that is a unit clause.
Definition: acc.hh:2247
acc_code & get_acceptance()
Retrieve the acceptance formula.
Definition: acc.hh:1620
mark_t all_
Precomputed all_sets_() value.
Definition: acc.hh:2394
bool is_generalized_streett(std::vector< unsigned > &pairs) const
Is the acceptance condition generalized-Streett?
acc_cond(const acc_code &code)
Build an acceptance condition.
Definition: acc.hh:1576
acc_cond(const acc_cond &o)
Copy an acceptance condition.
Definition: acc.hh:1584
std::pair< bool, acc_cond::mark_t > sat_mark() const
Return a satisfying mark if one exists.
Definition: acc.hh:1911
acc_code code_
Definition: acc.hh:2395
acc_cond & operator=(const acc_cond &o)
Copy an acceptance condition.
Definition: acc.hh:1591
bool operator!=(const acc_cond &other) const
Inequality comparison.
Definition: acc.hh:1636
static acc_code inf_neg(std::initializer_list< unsigned > vals)
Construct a generalized Büchi acceptance for complemented sets.
Definition: acc.hh:1963
bool is_streett_like(std::vector< rs_pair > &pairs) const
Test whether an acceptance condition is Streett-like and returns each Streett pair in an std::vector<...
bool is_buchi() const
Whether the acceptance condition is "Büchi".
Definition: acc.hh:1681
mark_t inf_unit() const
Find a Inf(i) that is a unit clause.
Definition: acc.hh:2294
bool uses_fin_acceptance() const
Whether the acceptance condition uses Fin terms.
Definition: acc.hh:1642
bool is_f() const
Whether the acceptance formula is "f" (false)
Definition: acc.hh:1663
unsigned num_sets() const
The number of sets used in the acceptance condition.
Definition: acc.hh:2141
std::vector< acc_cond > top_disjuncts() const
Return the top-level disjuncts.
A fixed-size bitset backed by N unsigned words.
Definition: bitset.hh:40
A class implementing Kleene's three-valued logic.
Definition: trival.hh:33
op
Operator types.
Definition: formula.hh:85
@ Or
(omega-Rational) Or
@ U
until
@ And
(omega-Rational) And
scc_info_options operator&(scc_info_options left, scc_info_options right)
Bitwise AND of two scc_info_options values.
Definition: sccinfo.hh:427
Definition: automata.hh:26
std::ostream & operator<<(std::ostream &os, const mc_algorithm &ma)
Print an mc_algorithm value to a stream.
Definition: mc.hh:74
constexpr bool operator==(trival a, trival b)
Equality comparison of two trival values.
Definition: trival.hh:134
constexpr bool operator!=(trival a, trival b)
Inequality comparison of two trival values.
Definition: trival.hh:140
An acceptance formula.
Definition: acc.hh:469
std::vector< std::pair< acc_cond::mark_t, acc_cond::mark_t > > useless_colors_patterns() const
Find patterns of useless colors.
std::tuple< int, acc_cond::acc_code, acc_cond::acc_code > fin_unit_one_split() const
Split an acceptance condition, trying to select one unit-Fin.
static acc_code parity_max(bool is_odd, unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:874
bool operator!=(const acc_code &other) const
Inequality comparison of acceptance formulas.
Definition: acc.hh:579
mark_t mafins() const
Find a Fin(i) that is mandatory.
static acc_code inf(mark_t m)
Construct a generalized Büchi acceptance.
Definition: acc.hh:714
acc_code to_cnf() const
Convert the acceptance formula into disjunctive normal form.
acc_code operator&(acc_code &&r) const
Conjunct the current condition with r.
Definition: acc.hh:1020
acc_code force_inf(mark_t m) const
For all x in m, replaces Fin(x) by false.
std::ostream & to_html(std::ostream &os, std::function< void(std::ostream &, int)> set_printer=nullptr) const
Print the acceptance formula as HTML.
static acc_code inf_neg(std::initializer_list< unsigned > vals)
Construct a generalized Büchi acceptance for complemented sets.
Definition: acc.hh:756
std::vector< std::pair< acc_cond::mark_t, acc_cond::acc_code > > mafins_split() const
Split an acceptance conditions into disjuncts according to mandatory fins.
std::vector< acc_code > top_disjuncts() const
Return the top-level disjuncts.
std::tuple< int, acc_cond::acc_code, acc_cond::acc_code > fin_unit_one_split_improved() const
Split an acceptance condition, trying to select one unit-Fin.
trival maybe_accepting(mark_t infinitely_often, mark_t always_present) const
Check potential acceptance of an SCC.
acc_code operator|(const acc_code &r) const
Disjunct the current condition with r.
Definition: acc.hh:1129
std::vector< std::vector< int > > missing(mark_t inf, bool accepting) const
Help closing accepting or rejecting cycle.
acc_code operator|(acc_code &&r) const
Disjunct the current condition with r.
Definition: acc.hh:1120
static acc_code fin(std::initializer_list< unsigned > vals)
Construct a generalized co-Büchi acceptance.
Definition: acc.hh:668
bool is_dnf() const
Whether the acceptance formula is in disjunctive normal form.
acc_code operator&(const acc_code &r) const
Conjunct the current condition with r.
Definition: acc.hh:1011
static acc_code inf(std::initializer_list< unsigned > vals)
Construct a generalized Büchi acceptance.
Definition: acc.hh:724
static acc_code parity_min_even(unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:894
static acc_code parity(bool is_max, bool is_odd, unsigned sets)
Build a parity acceptance condition.
std::pair< acc_cond::mark_t, acc_cond::mark_t > used_inf_fin_sets() const
Return the sets used as Inf or Fin in the acceptance condition.
mark_t used_once_sets() const
Return the sets that appears only once in the acceptance.
bool is_f() const
Is this the "false" acceptance condition?
Definition: acc.hh:602
std::ostream & to_text(std::ostream &os, std::function< void(std::ostream &, int)> set_printer=nullptr) const
Print the acceptance formula as text.
static acc_code generalized_buchi(unsigned n)
Build a generalized-Büchi acceptance condition with n sets.
Definition: acc.hh:783
bool operator>(const acc_code &other) const
Greater-than comparison of acceptance formulas.
Definition: acc.hh:561
static acc_code parity_min_odd(unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:890
acc_code(const acc_word *other)
Copy a part of another acceptance formula.
Definition: acc.hh:1551
mark_t fin_unit() const
Find a Fin(i) that is a unit clause.
trival weakly_accepting(mark_t infinitely_often, mark_t always_present) const
Check if cycles in a SCC are all accepting, all rejecting, or mixed.
static acc_code parity_max_even(unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:882
static acc_code f()
Construct the "false" acceptance condition.
Definition: acc.hh:632
bool accepting(mark_t inf) const
Check whether visiting exactly all sets inf infinitely often satisfies the acceptance condition.
static acc_code parity_max_odd(unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:878
bool is_t() const
Is this the "true" acceptance condition?
Definition: acc.hh:588
acc_code operator<<(unsigned sets) const
Apply a left shift to all mark_t that appear in the condition.
Definition: acc.hh:1172
static acc_code random(unsigned n, double reuse=0.0)
Build a random acceptance condition.
static acc_code rabin(unsigned n)
Build a Rabin condition with n pairs.
Definition: acc.hh:810
acc_code()
Build an empty acceptance formula.
Definition: acc.hh:1546
acc_code keep_one_inf_per_branch() const
Rewrite an acceptance condition by keeping at most one Inf(x) on each disjunctive branch.
bool operator==(const acc_code &other) const
Equality comparison of acceptance formulas.
Definition: acc.hh:475
static acc_code cobuchi()
Build a co-Büchi acceptance condition.
Definition: acc.hh:773
acc_code complement() const
Complement an acceptance formula.
static acc_code inf_neg(mark_t m)
Construct a generalized Büchi acceptance for complemented sets.
Definition: acc.hh:746
bdd to_bdd(const bdd *map) const
Convert the acceptance formula into a BDD.
int fin_one() const
Return one acceptance set i that appears as Fin(i) in the condition.
bool operator<=(const acc_code &other) const
Less-or-equal comparison of acceptance formulas.
Definition: acc.hh:567
acc_cond::mark_t used_sets() const
Return the set of sets appearing in the condition.
bool operator>=(const acc_code &other) const
Greater-or-equal comparison of acceptance formulas.
Definition: acc.hh:573
acc_code strip(acc_cond::mark_t rem, bool missing) const
Remove acceptance sets, and shift set numbers.
acc_code(const char *input)
Construct an acc_code from a string.
static acc_code fin_neg(std::initializer_list< unsigned > vals)
Construct a generalized co-Büchi acceptance for complemented sets.
Definition: acc.hh:700
acc_code & operator<<=(unsigned sets)
Apply a left shift to all mark_t that appear in the condition.
Definition: acc.hh:1141
mark_t inf_unit() const
Find a Inf(i) that is a unit clause.
static acc_code streett(unsigned n)
Build a Streett condition with n pairs.
Definition: acc.hh:825
acc_code unit_propagation()
Apply unit propagation to simplify the formula.
std::vector< acc_code > top_conjuncts() const
Return the top-level conjuncts.
static acc_code t()
Construct the "true" acceptance condition.
Definition: acc.hh:646
static acc_code fin_neg(mark_t m)
Construct a generalized co-Büchi acceptance for complemented sets.
Definition: acc.hh:690
bool operator<(const acc_code &other) const
Lexicographic less-than comparison on acceptance formulas.
Definition: acc.hh:510
static acc_code parity_min(bool is_odd, unsigned sets)
Build a parity acceptance condition.
Definition: acc.hh:886
std::pair< int, acc_code > fin_one_extract() const
Return one acceptance set i that appears as Fin(i) in the condition, and all disjuncts containing it ...
static acc_code fin(mark_t m)
Construct a generalized co-Büchi acceptance.
Definition: acc.hh:658
bool inf_satisfiable(mark_t inf) const
Assuming that we will visit infinitely often at least all sets in inf, is there any chance that we wi...
bool is_cnf() const
Whether the acceptance formula is in conjunctive normal form.
static acc_code buchi()
Build a Büchi acceptance condition.
Definition: acc.hh:765
static acc_code generalized_co_buchi(unsigned n)
Build a generalized-co-Büchi acceptance condition with n sets.
Definition: acc.hh:797
std::vector< unsigned > symmetries() const
compute the symmetry class of the acceptance sets.
acc_code remove(acc_cond::mark_t rem, bool missing) const
Remove all the acceptance sets in rem.
acc_code to_dnf() const
Convert the acceptance formula into disjunctive normal form.
static acc_code generalized_rabin(Iterator begin, Iterator end)
Build a generalized Rabin condition.
Definition: acc.hh:849
acc_code & operator|=(const acc_code &r)
Disjunct the current condition in place with r.
Definition: acc.hh:1029
acc_code & operator&=(const acc_code &r)
Conjunct the current condition in place with r.
Definition: acc.hh:919
std::ostream & to_latex(std::ostream &os, std::function< void(std::ostream &, int)> set_printer=nullptr) const
Print the acceptance formula as LaTeX.
An acceptance mark.
Definition: acc.hh:76
std::string as_string() const
Returns a string representation of this mark.
mark_t operator~() const
Bitwise complement.
Definition: acc.hh:258
bool is_singleton() const
Whether the mark contains only one bit set.
Definition: acc.hh:388
mark_t lowest() const
A mark_t where all bits have been removed except the lowest one.
Definition: acc.hh:382
unsigned max_set() const
The number of the highest set used plus one.
Definition: acc.hh:358
mark_t & remove_some(unsigned n)
Remove n bits that were set.
Definition: acc.hh:412
constexpr static unsigned max_accsets()
The maximum number of acceptance sets supported by this implementation.
Definition: acc.hh:116
size_t hash() const noexcept
Returns a hash value for this mark.
Definition: acc.hh:132
bool operator<=(mark_t o) const
Less-or-equal comparison.
Definition: acc.hh:157
static mark_t all()
A mark_t with all bits set to one.
Definition: acc.hh:126
spot::internal::mark_container sets() const
Returns some iterable object that contains the used sets.
Definition: acc.hh:2583
bool proper_subset(mark_t m) const
Whether the set of bits represented by *this is a proper subset of those represented by m.
Definition: acc.hh:343
mark_t & operator-=(mark_t r)
Difference-assignment (removes bits set in r).
Definition: acc.hh:226
mark_t strip(mark_t y) const
Remove bits indexed by y and compact the remaining bits.
Definition: acc.hh:311
mark_t(const iterator &begin, const iterator &end)
Create a mark_t from a range of set numbers.
Definition: acc.hh:94
void set_checked(unsigned u)
Add acceptance set u to this mark, but report an error if u is not a valid set number.
Definition: acc.hh:198
mark_t & operator<<=(unsigned i)
Left-shift-assignment.
Definition: acc.hh:289
unsigned count() const
Number of bits set.
Definition: acc.hh:349
mark_t operator>>(unsigned i) const
Right-shift all acceptance set indices by i.
Definition: acc.hh:295
mark_t & operator>>=(unsigned i)
Right-shift-assignment.
Definition: acc.hh:301
mark_t & operator|=(mark_t r)
Union-assignment.
Definition: acc.hh:219
mark_t operator^(mark_t r) const
Symmetric difference.
Definition: acc.hh:264
mark_t operator-(mark_t r) const
Difference (bits in this mark but not in r).
Definition: acc.hh:252
mark_t()=default
Initialize an empty mark_t.
mark_t(std::initializer_list< unsigned > vals)
Create a mark_t from a list of set numbers.
Definition: acc.hh:105
bool operator!=(mark_t o) const
Inequality comparison.
Definition: acc.hh:145
mark_t operator<<(unsigned i) const
Left-shift all acceptance set indices by i.
Definition: acc.hh:283
bool operator>=(mark_t o) const
Greater-or-equal comparison.
Definition: acc.hh:169
bool has_many() const
Whether the mark contains at least two bits set.
Definition: acc.hh:399
mark_t & operator^=(mark_t r)
Symmetric-difference-assignment.
Definition: acc.hh:233
void clear(unsigned u)
Remove acceptance set u from this mark.
Definition: acc.hh:206
mark_t & operator&=(mark_t r)
Intersection-assignment.
Definition: acc.hh:212
unsigned min_set() const
The number of the lowest set used plus one.
Definition: acc.hh:370
mark_t operator&(mark_t r) const
Intersection.
Definition: acc.hh:240
bool has(unsigned u) const
Returns true iff acceptance set u is in this mark.
Definition: acc.hh:181
bool operator<(mark_t o) const
Less-than comparison.
Definition: acc.hh:151
bool operator>(mark_t o) const
Greater-than comparison.
Definition: acc.hh:163
mark_t operator|(mark_t r) const
Union.
Definition: acc.hh:246
bool operator==(mark_t o) const
Equality comparison.
Definition: acc.hh:139
bool subset(mark_t m) const
Whether the set of bits represented by *this is a subset of those represented by m.
Definition: acc.hh:336
void fill(iterator here) const
Fill a container with the indices of the bits that are set.
Definition: acc.hh:2589
void set(unsigned u)
Add acceptance set u to this mark.
Definition: acc.hh:187
Rabin/streett pairs used by is_rabin_like and is_streett_like.
Definition: acc.hh:1769
rs_pair(acc_cond::mark_t fin, acc_cond::mark_t inf) noexcept
Construct a pair with Fin mark fin and Inf mark inf.
Definition: acc.hh:1779
rs_pair(const rs_pair &)=default
Copy constructor.
bool operator<=(rs_pair o) const
Less-or-equal comparison.
Definition: acc.hh:1802
rs_pair & operator=(const rs_pair &)=default
Copy-assignment operator.
acc_cond::mark_t fin
The Fin acceptance mark of this pair.
Definition: acc.hh:1783
bool operator>=(rs_pair o) const
Greater-or-equal comparison.
Definition: acc.hh:1812
bool operator>(rs_pair o) const
Greater-than comparison.
Definition: acc.hh:1807
bool operator<(rs_pair o) const
Less-than comparison (lexicographic on fin then inf).
Definition: acc.hh:1797
bool operator==(rs_pair o) const
Equality comparison.
Definition: acc.hh:1787
bool operator!=(rs_pair o) const
Inequality comparison.
Definition: acc.hh:1792
acc_cond::mark_t inf
The Inf acceptance mark of this pair.
Definition: acc.hh:1784
A view over Rabin-Streett pairs restricted to a subset of acceptance marks.
Definition: acc.hh:2403
std::vector< acc_cond::rs_pair > rs_pairs
Type alias for a vector of Rabin-Streett pairs.
Definition: acc.hh:2405
acc_cond::mark_t fins() const
Returns the union of all visible Fin marks across all pairs.
Definition: acc.hh:2425
rs_pairs_view(const rs_pairs &p, const acc_cond::mark_t &m)
Create a view of pairs p restricted to marks visible in m.
Definition: acc.hh:2408
rs_pairs_view(const rs_pairs &p)
Create an unrestricted view of all pairs in p.
Definition: acc.hh:2412
acc_cond::mark_t paired_with_fin(unsigned mark) const
Returns all Inf marks paired with a Fin containing mark.
Definition: acc.hh:2456
acc_cond::mark_t fins_alone() const
Returns Fin marks from pairs whose Inf part is not visible.
Definition: acc.hh:2434
acc_cond::mark_t infs_alone() const
Returns Inf marks from pairs whose Fin part is not visible.
Definition: acc.hh:2444
const rs_pairs & pairs() const
Returns a reference to the underlying vector of pairs.
Definition: acc.hh:2466
acc_cond::mark_t infs() const
Returns the union of all visible Inf marks across all pairs.
Definition: acc.hh:2416
size_t operator()(spot::acc_cond::mark_t m) const noexcept
Returns the hash of acceptance mark m.
Definition: acc.hh:2604
A "node" in an acceptance formulas.
Definition: acc.hh:442
mark_t mark
A set of acceptance marks.
Definition: acc.hh:443
acc_op op
Operator (6 possible values, stored in 8 bits)
Definition: acc.hh:446
unsigned size
Size of the subtree.
Definition: acc.hh:452
struct spot::acc_cond::acc_word::@5 sub
An operator node with its subtree size.

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.1