31 #include <spot/misc/_config.h>
32 #include <spot/misc/bitset.hh>
33 #include <spot/misc/trival.hh>
57 [[noreturn]]
static void report_too_many_sets();
93 template<
class iterator>
94 mark_t(
const iterator& begin,
const iterator& end)
97 for (iterator i = begin; i != end; ++i)
98 if (SPOT_LIKELY(*i < SPOT_MAX_ACCSETS))
101 report_too_many_sets();
105 mark_t(std::initializer_list<unsigned> vals)
106 :
mark_t(vals.begin(), vals.end())
118 return SPOT_MAX_ACCSETS;
128 return mark_t(_value_t::mone());
134 std::hash<decltype(
id)> h;
175 explicit operator bool()
const
181 bool has(
unsigned u)
const
200 if (SPOT_UNLIKELY(u >= max_accsets()))
201 report_too_many_sets();
269 #if SPOT_DEBUG || defined(SWIGPYTHON)
270 # define SPOT_WRAP_OP(ins) \
275 catch (const std::runtime_error& e) \
277 report_too_many_sets(); \
280 # define SPOT_WRAP_OP(ins) ins;
285 SPOT_WRAP_OP(
return id << i);
291 SPOT_WRAP_OP(
id <<= i;
return *
this);
297 SPOT_WRAP_OP(
return id >> i);
303 SPOT_WRAP_OP(
id >>= i;
return *
this);
325 auto rm = (~yv) & (yv - 1);
327 auto lm = ~(yv ^ (yv - 1));
328 xv = ((xv & lm) >> 1) | (xv & rm);
338 return !((*this) - m);
345 return *
this != m && this->subset(m);
361 return id.highest()+1;
373 return id.lowest()+1;
394 return id && !(
id & (
id - 1));
405 return !!(
id & (
id - 1));
420 template<
class iterator>
421 void fill(iterator here)
const;
424 spot::internal::mark_container sets()
const;
432 { Inf, Fin, InfNeg, FinNeg,
And,
Or };
468 struct SPOT_API
acc_code:
public std::vector<acc_word>
478 if (is_t() && other.
is_t())
480 unsigned pos = size();
481 if (other.size() != pos)
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)
492 case acc_cond::acc_op::And:
493 case acc_cond::acc_op::Or:
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:
501 if (other[pos].mark != (*
this)[pos].mark)
513 if (is_t() && other.
is_t())
515 unsigned pos = size();
516 auto osize = other.size();
523 auto op = (*this)[pos - 1].sub.op;
524 auto oop = other[pos - 1].sub.op;
529 auto sz = (*this)[pos - 1].sub.size;
530 auto osz = other[pos - 1].sub.size;
537 case acc_cond::acc_op::And:
538 case acc_cond::acc_op::Or:
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:
547 auto m = (*this)[pos].mark;
548 auto om = other[pos].mark;
563 return other < *
this;
569 return !(other < *
this);
575 return !(*
this < other);
581 return !(*
this == other);
592 return s == 0 || ((*this)[s - 1].sub.op == acc_op::Inf
593 && !((*this)[s - 2].mark));
607 && (*this)[s - 1].sub.op == acc_op::Fin && !((*this)[s - 2].mark);
615 static constexpr
size_t max_acc_formula_size_ = (1U << 24) - 1;
619 [[noreturn]]
static void report_too_large_acceptance_formula_()
621 throw std::runtime_error(
"acceptance formula is too large");
637 res[1].sub.op = acc_op::Fin;
663 res[1].sub.op = acc_op::Fin;
695 res[1].sub.op = acc_op::FinNeg;
702 return fin_neg(
mark_t(vals));
719 res[1].sub.op = acc_op::Inf;
751 res[1].sub.op = acc_op::InfNeg;
758 return inf_neg(
mark_t(vals));
788 m >>= mark_t::max_accsets() - n;
802 m >>= mark_t::max_accsets() - n;
815 res |= inf({2*n - 1}) & fin({2*n - 2});
830 res &= inf({2*n - 1}) | fin({2*n - 2});
848 template<
class Iterator>
853 for (Iterator i = begin; i != end; ++i)
857 for (
unsigned ni = *i; ni > 0; --ni)
859 auto pair = inf(m) & fin({f});
860 std::swap(pair, res);
861 res |= std::move(pair);
876 return parity(
true, is_odd, sets);
880 return parity_max(
true, sets);
884 return parity_max(
false, sets);
888 return parity(
false, is_odd, sets);
892 return parity_min(
true, sets);
896 return parity_min(
false, sets);
921 if (is_t() || r.
is_f())
926 if (is_f() || r.
is_t())
928 unsigned s = size() - 1;
929 unsigned rs = r.size() - 1;
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))
937 (*this)[s - 1].mark |= r[rs - 1].mark;
947 if ((*
this)[s].sub.op == acc_op::And)
949 auto start = &(*this)[s] - (*this)[s].
sub.
size;
950 auto pos = &(*this)[s] - 1;
954 if (pos->sub.op == acc_op::Inf)
962 else if ((*
this)[s].sub.op == acc_op::Inf)
964 left_inf = &(*this)[s - 1];
967 const acc_word* right_inf =
nullptr;
968 auto right_end = &r.back();
969 if (right_end->sub.op == acc_op::And)
972 auto pos = --right_end;
975 if (pos->sub.op == acc_op::Inf)
983 else if (right_end->sub.op == acc_op::Inf)
985 right_inf = right_end - 1;
989 if (left_inf && right_inf)
991 carry = left_inf->
mark;
992 auto pos = left_inf - &(*this)[0];
993 erase(begin() + pos, begin() + pos + 2);
996 insert(end(), &r[0], right_end + 1);
998 (*this)[sz + (right_inf - &r[0])].mark |= carry;
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;
1031 if (is_t() || r.
is_f())
1033 if (is_f() || r.
is_t())
1038 unsigned s = size() - 1;
1039 unsigned rs = r.size() - 1;
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))
1046 (*this)[s - 1].mark |= r[rs - 1].mark;
1056 if ((*
this)[s].sub.op == acc_op::Or)
1058 auto start = &(*this)[s] - (*this)[s].
sub.
size;
1059 auto pos = &(*this)[s] - 1;
1063 if (pos->sub.op == acc_op::Fin)
1071 else if ((*
this)[s].sub.op == acc_op::Fin)
1073 left_fin = &(*this)[s - 1];
1076 const acc_word* right_fin =
nullptr;
1077 auto right_end = &r.back();
1078 if (right_end->sub.op == acc_op::Or)
1081 auto pos = --right_end;
1084 if (pos->sub.op == acc_op::Fin)
1086 right_fin = pos - 1;
1092 else if (right_end->sub.op == acc_op::Fin)
1094 right_fin = right_end - 1;
1098 if (left_fin && right_fin)
1100 carry = left_fin->
mark;
1101 auto pos = (left_fin - &(*this)[0]);
1102 this->erase(begin() + pos, begin() + pos + 2);
1105 insert(end(), &r[0], right_end + 1);
1107 (*this)[sz + (right_fin - &r[0])].mark |= carry;
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;
1143 if (SPOT_UNLIKELY(sets >= mark_t::max_accsets()))
1144 report_too_many_sets();
1147 unsigned pos = size();
1150 switch ((*
this)[pos - 1].sub.op)
1152 case acc_cond::acc_op::And:
1153 case acc_cond::acc_op::Or:
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:
1161 (*this)[pos].mark <<= sets;
1341 std::tuple<int, acc_cond::acc_code, acc_cond::acc_code>
1343 std::tuple<int, acc_cond::acc_code, acc_cond::acc_code>
1362 std::vector<std::pair<acc_cond::mark_t, acc_cond::acc_code>>
1377 std::vector<std::vector<int>>
1404 mark_t always_present)
const;
1420 mark_t always_present)
const;
1478 std::vector<std::pair<acc_cond::mark_t, acc_cond::mark_t>>
1498 std::function<
void(std::ostream&,
int)>
1499 set_printer =
nullptr)
const;
1507 std::function<
void(std::ostream&,
int)>
1508 set_printer =
nullptr)
const;
1516 std::function<
void(std::ostream&,
int)>
1517 set_printer =
nullptr)
const;
1552 : std::vector<
acc_word>(other - other->sub.size, other + 1)
1566 : num_(0U), all_({}), code_(code)
1569 uses_fin_acceptance_ = check_fin_acceptance();
1577 : num_(0
U), all_({}), code_(code)
1579 add_sets(code.used_sets().max_set());
1580 uses_fin_acceptance_ = check_fin_acceptance();
1585 : num_(o.num_), all_(o.all_), code_(o.code_),
1586 uses_fin_acceptance_(o.uses_fin_acceptance_)
1610 uses_fin_acceptance_ = check_fin_acceptance();
1632 return (ocode == code_ || (ocode.
is_t() && code_.is_t()));
1638 return !(*
this == other);
1644 return uses_fin_acceptance_;
1650 return code_.is_t();
1659 return num_ == 0 && is_t();
1665 return code_.is_f();
1674 return num_ == 0 && is_f();
1683 unsigned s = code_.size();
1685 s == 2 && code_[1].sub.op == acc_op::Inf && code_[0].mark == all_sets();
1694 return num_ == 1 && is_generalized_co_buchi();
1701 set_acceptance(inf(all_sets()));
1708 set_acceptance(fin(all_sets()));
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());
1728 unsigned s = code_.size();
1730 code_[1].sub.op == acc_op::Fin && code_[0].mark == all_sets());
1789 return fin == o.
fin && inf == o.
inf;
1794 return fin != o.
fin || inf != o.
inf;
1799 return fin < o.
fin || (!(o.
fin < fin) && inf < o.
inf);
1804 return !(o < *
this);
1814 return !(*
this < o);
1875 bool is_parity(
bool& max,
bool& odd,
bool equiv =
false)
const;
1884 return is_parity(max, odd);
1896 return acc_cond(num_, code_.unit_propagation());
1905 return sat_unsat_mark(
false);
1913 return sat_unsat_mark(
true);
1933 return acc_code::inf(mark);
1938 return inf(
mark_t(vals.begin(), vals.end()));
1960 return acc_code::inf_neg(mark);
1965 return inf_neg(
mark_t(vals.begin(), vals.end()));
1978 return acc_code::fin(mark);
1983 return fin(
mark_t(vals.begin(), vals.end()));
2005 return acc_code::fin_neg(mark);
2010 return fin_neg(
mark_t(vals.begin(), vals.end()));
2024 if (num > mark_t::max_accsets())
2025 report_too_many_sets();
2044 SPOT_ASSERT(u < num_sets());
2067 return code_.accepting(inf);
2077 return code_.inf_satisfiable(inf);
2103 return code_.maybe_accepting(infinitely_often, always_present);
2122 return code_.weakly_accepting(infinitely_often, always_present);
2153 template<
class iterator>
2157 for (
unsigned x = 0; x < num_; ++x)
2162 auto all = comp(u |
mark_t({x}));
2165 for (iterator y = begin; y != end; ++y)
2195 return {num_sets(), code_.
remove(rem, missing)};
2205 { num_sets() - (all_sets() & rem).count(), code_.
strip(rem, missing) };
2211 return {num_sets(), code_.
force_inf(m)};
2218 return {num_sets(), code_.
remove(all_sets() - rem,
true)};
2232 std::string
name(
const char* fmt =
"alo")
const;
2249 return code_.fin_unit();
2266 return code_.mafins();
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));
2296 return code_.inf_unit();
2305 return code_.fin_one();
2330 auto [f, c] = code_.fin_one_extract();
2331 return {f, {num_sets(), std::move(c)}};
2352 std::tuple<int, acc_cond, acc_cond>
2355 auto [f, l, r] = code_.fin_unit_one_split();
2356 return {f, {num_sets(), std::move(l)}, {num_sets(), std::move(r)}};
2358 std::tuple<int, acc_cond, acc_cond>
2361 auto [f, l, r] = code_.fin_unit_one_split_improved();
2362 return {f, {num_sets(), std::move(l)}, {num_sets(), std::move(r)}};
2397 bool uses_fin_acceptance_ =
false;
2409 : pairs_(p), view_marks_(m) {}
2438 return !visible(p.
inf) && visible(p.
fin) ? p.
fin
2448 return !visible(p.
fin) && visible(p.
inf) ? p.
inf
2459 for (
const auto& p: pairs_)
2460 if (p.fin.has(mark) && visible(p.fin) && visible(p.inf))
2472 template<
typename filter>
2476 for (
const auto& p: pairs_)
2481 bool visible(
const acc_cond::mark_t& v)
const
2483 return !!(view_marks_ & v);
2487 acc_cond::mark_t view_marks_;
2511 class SPOT_API mark_iterator
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;
2520 mark_iterator() noexcept
2525 mark_iterator(acc_cond::mark_t m) noexcept
2540 value_type operator*()
const
2543 return m_.min_set() - 1;
2546 mark_iterator& operator++()
2548 m_.clear(this->
operator*());
2552 mark_iterator operator++(
int)
2554 mark_iterator it = *
this;
2559 acc_cond::mark_t m_;
2562 class SPOT_API mark_container
2570 mark_iterator begin()
const
2574 mark_iterator end()
const
2588 template<
class iterator>
2591 for (
unsigned s : sets())
2601 struct hash<
spot::acc_cond::mark_t>
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
@ 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.