23 #include <spot/twa/acc.hh>
24 #include <spot/mc/unionfind.hh>
25 #include <spot/mc/intersect.hh>
26 #include <spot/mc/mc.hh>
27 #include <spot/misc/timer.hh>
28 #include <spot/twacube/twacube.hh>
29 #include <spot/twacube/fwd.hh>
38 template<
typename State,
typename SuccIterator,
39 typename StateHash,
typename StateEqual>
48 struct product_state_equal
51 operator()(
const product_state lhs,
52 const product_state rhs)
const
55 return (lhs.st_prop == rhs.st_prop) &&
56 equal(lhs.st_kripke, rhs.st_kripke);
60 struct product_state_hash
63 operator()(
const product_state that)
const noexcept
68 return wang32_hash(that.st_prop) ^ hasher(that.st_kripke);
74 using shared_map = int;
75 using shared_struct = int;
77 static shared_struct* make_shared_structure(shared_map m,
unsigned i)
87 std::atomic<bool>& stop)
88 : sys_(sys), twa_(
twa), tid_(tid), stop_(stop),
92 State, SuccIterator>::value,
93 "error: does not match the kripkecube requirements");
101 sys_.recycle(todo.back().it_kripke, tid_);
109 product_state initial = {sys_.initial(tid_), twa_->get_initial()};
110 if (SPOT_LIKELY(push_state(initial, dfs_number+1, {})))
112 todo.push_back({initial, sys_.succ(initial.st_kripke, tid_),
113 twa_->succ(initial.st_prop)});
116 if (todo.back().it_prop->done())
119 forward_iterators(sys_, twa_, todo.back().it_kripke,
120 todo.back().it_prop,
true, 0);
121 map[initial] = ++dfs_number;
123 while (!todo.empty() && !stop_.load(std::memory_order_relaxed))
127 if (todo.back().it_kripke->done())
129 bool is_init = todo.size() == 1;
130 auto newtop = is_init? todo.back().st: todo[todo.size() -2].st;
131 if (SPOT_LIKELY(pop_state(todo.back().st,
137 sys_.recycle(todo.back().it_kripke, tid_);
140 if (SPOT_UNLIKELY(found_))
152 todo.back().it_kripke->state(),
153 twa_->trans_storage(todo.back().it_prop, tid_).dst
155 auto acc = twa_->trans_data(todo.back().it_prop, tid_).acc_;
156 forward_iterators(sys_, twa_, todo.back().it_kripke,
157 todo.back().it_prop,
false, 0);
158 auto it = map.find(dst);
161 if (SPOT_LIKELY(push_state(dst, dfs_number+1, acc)))
163 map[dst] = ++dfs_number;
164 todo.push_back({dst, sys_.succ(dst.st_kripke, tid_),
165 twa_->succ(dst.st_prop)});
166 forward_iterators(sys_, twa_, todo.back().it_kripke,
167 todo.back().it_prop,
true, 0);
170 else if (SPOT_UNLIKELY(update(todo.back().st,
172 dst, map[dst], acc)))
185 tm_.start(
"DFS thread " + std::to_string(tid_));
191 roots_.push_back({dfsnum, cond, {}});
202 bool pop_state(product_state,
unsigned top_dfsnum,
bool,
203 product_state,
unsigned)
205 if (top_dfsnum == roots_.back().dfsnum)
209 uf_.markdead(top_dfsnum);
211 dfs_ = todo.size() > dfs_ ? todo.size() : dfs_;
218 product_state,
unsigned dst_dfsnum,
221 if (uf_.isdead(dst_dfsnum))
224 while (!uf_.sameset(dst_dfsnum, roots_.back().dfsnum))
226 auto& el = roots_.back();
228 uf_.unite(dst_dfsnum, el.dfsnum);
229 cond |= el.acc | el.ingoing;
231 roots_.back().acc |= cond;
232 found_ = acc_.accepting(roots_.back().acc);
233 if (SPOT_UNLIKELY(found_))
240 bool tst_val =
false;
242 bool exchanged = stop_.compare_exchange_strong(tst_val, new_val);
245 tm_.stop(
"DFS thread " + std::to_string(tid_));
253 unsigned int states()
258 unsigned int transitions()
265 return tm_.timer(
"DFS thread " + std::to_string(tid_)).walltime();
270 return "renault_lpar13";
286 std::string res =
"Prefix:\n";
290 res +=
" " + std::to_string(s.st.st_prop) +
291 +
"*" + sys_.to_string(s.st.st_kripke) +
"\n";
298 const product_state* prod_st;
299 ctrx_element* parent_st;
300 SuccIterator* it_kripke;
301 std::shared_ptr<trans_index> it_prop;
303 std::queue<ctrx_element*> bfs;
305 acc_cond::mark_t acc = {};
307 bfs.push(
new ctrx_element({&todo.back().st,
nullptr,
308 sys_.succ(todo.back().st.st_kripke, tid_),
309 twa_->succ(todo.back().st.st_prop)}));
313 auto* front = bfs.front();
316 while (!front->it_kripke->done())
318 while (!front->it_prop->done())
320 if (twa_->get_cubeset().intersect
321 (twa_->trans_data(front->it_prop, tid_).cube_,
322 front->it_kripke->condition()))
324 const product_state dst = {
325 front->it_kripke->state(),
326 twa_->trans_storage(front->it_prop).dst
330 auto it = map.find(dst);
331 if (it == map.end() ||
332 !uf_.sameset(it->second,
333 map[todo.back().st]))
335 front->it_prop->next();
342 auto mark = twa_->trans_data(front->it_prop,
346 ctrx_element* current = front;
347 while (current !=
nullptr)
351 std::to_string(current->prod_st->st_prop) +
353 sys_. to_string(current->prod_st->st_kripke) +
355 current = current->parent_st;
361 auto* e = bfs.front();
362 sys_.recycle(e->it_kripke, tid_);
366 sys_.recycle(front->it_kripke, tid_);
371 if (twa_->acc().accepting(acc))
376 const product_state* q = &(it->first);
377 ctrx_element* root =
new ctrx_element({
379 sys_.succ(q->st_kripke, tid_),
380 twa_->succ(q->st_prop)
387 const product_state* q = &(it->first);
388 ctrx_element* root =
new ctrx_element({
390 sys_.succ(q->st_kripke, tid_),
391 twa_->succ(q->st_prop)
395 front->it_prop->next();
397 front->it_prop->reset();
398 front->it_kripke->next();
400 sys_.recycle(front->it_kripke, tid_);
413 SuccIterator* it_kripke;
414 std::shared_ptr<trans_index> it_prop;
417 struct root_element {
419 acc_cond::mark_t ingoing;
420 acc_cond::mark_t acc;
423 typedef std::unordered_map<
const product_state, int,
425 product_state_equal> visited_map;
427 kripkecube<State, SuccIterator>& sys_;
429 std::vector<todo_element> todo;
431 unsigned int dfs_number = 0;
432 unsigned int trans_ = 0;
434 std::atomic<bool>& stop_;
436 std::vector<root_element> roots_;
442 bool finisher_ =
false;
This class allows to ensure (at compile time) if a given parameter is of type kripkecube....
Definition: kripke.hh:72
This class is a template representation of a Kripke structure. It is composed of two template paramet...
Definition: kripke.hh:41
This class implements the sequential emptiness check as presented in "Three SCC-based Emptiness Check...
Definition: lpar13.hh:41
bool update(product_state, unsigned, product_state, unsigned dst_dfsnum, acc_cond::mark_t cond)
This method is called for every closing, back, or forward edge. Return true if a counterexample has b...
Definition: lpar13.hh:217
bool pop_state(product_state, unsigned top_dfsnum, bool, product_state, unsigned)
This method is called to notify the emptiness checks that a state will be popped. If the method retur...
Definition: lpar13.hh:202
A map of timer, where each timer has a name.
Definition: timer.hh:229
A Transition-based ω-Automaton.
Definition: twa.hh:623
const acc_cond & acc() const
The acceptance condition of the automaton.
Definition: twa.hh:816
size_t wang32_hash(size_t key)
Thomas Wang's 32 bit hash function.
Definition: hashfunc.hh:41
Definition: automata.hh:27
mc_rvalue
Definition: mc.hh:44
@ NOT_EMPTY
The product is not empty.
@ EMPTY
The product is empty.
An acceptance mark.
Definition: acc.hh:85