spot 2.16.3
Loading...
Searching...
No Matches
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
35namespace 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
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
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
442 {
444 struct {
452 unsigned size:24;
453 } sub;
454 };
455
468 struct SPOT_API acc_code: public std::vector<acc_word>
469 {
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
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
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
766 {
767 return inf({0});
768 }
769
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
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
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
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
1206
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
1267
1281
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>>
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
1404 mark_t always_present) const;
1405
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
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
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
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:
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
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
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
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
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
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
2596namespace 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
const acc_code & get_acceptance() const
Retrieve the acceptance formula.
Definition acc.hh:1614
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
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< 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
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...
std::vector< acc_cond > top_disjuncts() const
Return the top-level disjuncts.
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
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
acc_cond & operator=(const acc_cond &o)
Copy an acceptance condition.
Definition acc.hh:1591
acc_code & get_acceptance()
Retrieve the acceptance formula.
Definition acc.hh:1620
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::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
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
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
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?
std::pair< bool, acc_cond::mark_t > unsat_mark() const
Return an unsatisfying mark if one exists.
Definition acc.hh:1903
acc_cond(const acc_code &code)
Build an acceptance condition.
Definition acc.hh:1576
std::pair< bool, acc_cond::mark_t > sat_unsat_mark(bool) const
Shared implementation for sat_mark() and unsat_mark().
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
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
std::vector< acc_cond > top_conjuncts() const
Return the top-level conjuncts.
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
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
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
static acc_code parity_max(bool is_odd, unsigned sets)
Build a parity acceptance condition.
Definition acc.hh:874
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.
std::vector< std::vector< int > > missing(mark_t inf, bool accepting) const
Help closing accepting or rejecting cycle.
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.
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(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.
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::mark_t > > useless_colors_patterns() const
Find patterns of useless colors.
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< acc_code > top_conjuncts() const
Return the top-level conjuncts.
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.
std::vector< acc_code > top_disjuncts() const
Return the top-level disjuncts.
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.
mark_t used_once_sets() const
Return the sets that appears only once in the acceptance.
acc_code & operator<<=(unsigned sets)
Apply a left shift to all mark_t that appear in the condition.
Definition acc.hh:1141
bool is_f() const
Is this the "false" acceptance condition?
Definition acc.hh:602
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
std::ostream & to_latex(std::ostream &os, std::function< void(std::ostream &, int)> set_printer=nullptr) const
Print the acceptance formula as LaTeX.
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 ...
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
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.
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.
std::ostream & to_text(std::ostream &os, std::function< void(std::ostream &, int)> set_printer=nullptr) const
Print the acceptance formula as text.
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
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.
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
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.
acc_code & operator&=(const acc_code &r)
Conjunct the current condition in place with r.
Definition acc.hh:919
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.
static acc_code t()
Construct the "true" acceptance condition.
Definition acc.hh:646
std::vector< unsigned > symmetries() const
compute the symmetry class of the acceptance sets.
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
static acc_code fin(mark_t m)
Construct a generalized co-Büchi acceptance.
Definition acc.hh:658
acc_code & operator|=(const acc_code &r)
Disjunct the current condition in place with r.
Definition acc.hh:1029
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
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
An acceptance mark.
Definition acc.hh:76
std::string as_string() const
Returns a string representation of this mark.
static constexpr unsigned max_accsets()
The maximum number of acceptance sets supported by this implementation.
Definition acc.hh:116
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
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 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
mark_t & operator-=(mark_t r)
Difference-assignment (removes bits set in r).
Definition acc.hh:226
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
unsigned count() const
Number of bits set.
Definition acc.hh:349
mark_t & operator<<=(unsigned i)
Left-shift-assignment.
Definition acc.hh:289
mark_t operator>>(unsigned i) const
Right-shift all acceptance set indices by i.
Definition acc.hh:295
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
mark_t & operator^=(mark_t r)
Symmetric-difference-assignment.
Definition acc.hh:233
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
void clear(unsigned u)
Remove acceptance set u from this mark.
Definition acc.hh:206
mark_t & operator|=(mark_t r)
Union-assignment.
Definition acc.hh:219
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
mark_t & operator>>=(unsigned i)
Right-shift-assignment.
Definition acc.hh:301
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)
Intersection-assignment.
Definition acc.hh:212
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 & operator=(const rs_pair &)=default
Copy-assignment operator.
rs_pair(const rs_pair &)=default
Copy constructor.
bool operator<=(rs_pair o) const
Less-or-equal comparison.
Definition acc.hh:1802
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
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.8