Merge lp:~tapaal-ltl/verifypn/resumable-suc-generator into lp:~tapaal-ltl/verifypn/ltl_model_checker
- resumable-suc-generator
- Merge into ltl_model_checker
Proposed by
Simon Virenfeldt
Status: | Merged |
---|---|
Merged at revision: | 232 |
Proposed branch: | lp:~tapaal-ltl/verifypn/resumable-suc-generator |
Merge into: | lp:~tapaal-ltl/verifypn/ltl_model_checker |
Diff against target: |
1016 lines (+357/-197) 15 files modified
CMakeLists.txt (+2/-2) include/LTL/BuchiSuccessorGenerator.h (+2/-2) include/LTL/LTL_algorithm/ModelChecker.h (+2/-0) include/LTL/LTL_algorithm/NestedDepthFirstSearch.h (+9/-3) include/LTL/LTL_algorithm/TarjanModelChecker.h (+26/-22) include/LTL/ProductSuccessorGenerator.h (+68/-5) include/LTL/Structures/ProductState.h (+2/-0) include/PetriEngine/PQL/Expressions.h (+2/-2) include/PetriEngine/SuccessorGenerator.h (+5/-1) src/LTL/LTL_algorithm/LTLToBuchi.cpp (+17/-31) src/LTL/LTL_algorithm/NestedDepthFirstSearch.cpp (+57/-51) src/LTL/LTL_algorithm/ProductSuccessorGenerator.cpp (+42/-9) src/LTL/LTL_algorithm/TarjanModelChecker.cpp (+118/-64) src/LTLMain.cpp (+4/-4) src/PetriEngine/SuccessorGenerator.cpp (+1/-1) |
To merge this branch: | bzr merge lp:~tapaal-ltl/verifypn/resumable-suc-generator |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Simon Virenfeldt | Approve | ||
Review via email: mp+393497@code.launchpad.net |
Commit message
Merge branch resumable_
Description of the change
To post a comment you must log in.
- 262. By Simon Virenfeldt
-
Removed some commented code lines
- 263. By Simon Virenfeldt
-
Merge remote
Revision history for this message
Simon Virenfeldt (simwir) : | # |
review:
Approve
Preview Diff
[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1 | === modified file 'CMakeLists.txt' | |||
2 | --- CMakeLists.txt 2020-10-19 11:13:27 +0000 | |||
3 | +++ CMakeLists.txt 2020-11-09 13:59:57 +0000 | |||
4 | @@ -29,7 +29,7 @@ | |||
5 | 29 | endif() | 29 | endif() |
6 | 30 | 30 | ||
7 | 31 | if (CMAKE_BUILD_TYPE MATCHES Debug) | 31 | if (CMAKE_BUILD_TYPE MATCHES Debug) |
9 | 32 | #add_compile_definitions(PRINTF_DEBUG) | 32 | add_compile_definitions(PRINTF_DEBUG) |
10 | 33 | endif() | 33 | endif() |
11 | 34 | 34 | ||
12 | 35 | if (VERIFYPN_Static) | 35 | if (VERIFYPN_Static) |
13 | @@ -59,7 +59,7 @@ | |||
14 | 59 | endif () | 59 | endif () |
15 | 60 | 60 | ||
16 | 61 | set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -Wall -pedantic-errors -O3 -DNDEBUG") | 61 | set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -Wall -pedantic-errors -O3 -DNDEBUG") |
18 | 62 | set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -O0 -fno-omit-frame-pointer -fsanitize=address ") | 62 | set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -O0 -fno-omit-frame-pointer") |
19 | 63 | set(CMAKE_EXE_LINKER_FLAGS_RELEASE "${CMAKE_EXE_LINKER_FLAGS_RELEASE} -O3 -DNDEBUG") | 63 | set(CMAKE_EXE_LINKER_FLAGS_RELEASE "${CMAKE_EXE_LINKER_FLAGS_RELEASE} -O3 -DNDEBUG") |
20 | 64 | if (VERIFYPN_Static AND NOT APPLE) | 64 | if (VERIFYPN_Static AND NOT APPLE) |
21 | 65 | set(CMAKE_EXE_LINKER_FLAGS_RELEASE "${CMAKE_EXE_LINKER_FLAGS_RELEASE} -static") | 65 | set(CMAKE_EXE_LINKER_FLAGS_RELEASE "${CMAKE_EXE_LINKER_FLAGS_RELEASE} -static") |
22 | 66 | 66 | ||
23 | === modified file 'include/LTL/BuchiSuccessorGenerator.h' | |||
24 | --- include/LTL/BuchiSuccessorGenerator.h 2020-10-05 10:15:17 +0000 | |||
25 | +++ include/LTL/BuchiSuccessorGenerator.h 2020-11-09 13:59:57 +0000 | |||
26 | @@ -18,7 +18,7 @@ | |||
27 | 18 | namespace LTL { | 18 | namespace LTL { |
28 | 19 | class BuchiSuccessorGenerator { | 19 | class BuchiSuccessorGenerator { |
29 | 20 | public: | 20 | public: |
31 | 21 | BuchiSuccessorGenerator(Structures::BuchiAutomaton automaton) | 21 | explicit BuchiSuccessorGenerator(Structures::BuchiAutomaton automaton) |
32 | 22 | : aut(std::move(automaton)) { | 22 | : aut(std::move(automaton)) { |
33 | 23 | } | 23 | } |
34 | 24 | 24 | ||
35 | @@ -31,7 +31,7 @@ | |||
36 | 31 | bool next(size_t &state, bdd &cond) { | 31 | bool next(size_t &state, bdd &cond) { |
37 | 32 | if (!succ->done()) { | 32 | if (!succ->done()) { |
38 | 33 | state = aut.buchi->state_number(succ->dst()); | 33 | state = aut.buchi->state_number(succ->dst()); |
40 | 34 | #ifdef PRINTF_DEBUG | 34 | #ifdef _PRINTF_DEBUG |
41 | 35 | std::cerr << "buchi state " << state << std::endl; | 35 | std::cerr << "buchi state " << state << std::endl; |
42 | 36 | #endif | 36 | #endif |
43 | 37 | cond = succ->cond(); | 37 | cond = succ->cond(); |
44 | 38 | 38 | ||
45 | === modified file 'include/LTL/LTL_algorithm/ModelChecker.h' | |||
46 | --- include/LTL/LTL_algorithm/ModelChecker.h 2020-10-16 11:34:00 +0000 | |||
47 | +++ include/LTL/LTL_algorithm/ModelChecker.h 2020-11-09 13:59:57 +0000 | |||
48 | @@ -20,6 +20,8 @@ | |||
49 | 20 | std::unique_ptr<ProductSuccessorGenerator> successorGenerator; | 20 | std::unique_ptr<ProductSuccessorGenerator> successorGenerator; |
50 | 21 | const PetriEngine::PetriNet &net; | 21 | const PetriEngine::PetriNet &net; |
51 | 22 | PetriEngine::PQL::Condition_ptr formula; | 22 | PetriEngine::PQL::Condition_ptr formula; |
52 | 23 | |||
53 | 24 | size_t _discovered = 0; | ||
54 | 23 | }; | 25 | }; |
55 | 24 | } | 26 | } |
56 | 25 | 27 | ||
57 | 26 | 28 | ||
58 | === modified file 'include/LTL/LTL_algorithm/NestedDepthFirstSearch.h' | |||
59 | --- include/LTL/LTL_algorithm/NestedDepthFirstSearch.h 2020-10-05 10:15:17 +0000 | |||
60 | +++ include/LTL/LTL_algorithm/NestedDepthFirstSearch.h 2020-11-09 13:59:57 +0000 | |||
61 | @@ -12,6 +12,7 @@ | |||
62 | 12 | #include "LTL/Structures/ProductStateFactory.h" | 12 | #include "LTL/Structures/ProductStateFactory.h" |
63 | 13 | 13 | ||
64 | 14 | #include <ptrie/ptrie_stable.h> | 14 | #include <ptrie/ptrie_stable.h> |
65 | 15 | #include <unordered_set> | ||
66 | 15 | 16 | ||
67 | 16 | using namespace PetriEngine; | 17 | using namespace PetriEngine; |
68 | 17 | 18 | ||
69 | @@ -20,7 +21,7 @@ | |||
70 | 20 | public: | 21 | public: |
71 | 21 | NestedDepthFirstSearch(const PetriNet &net, PetriEngine::PQL::Condition_ptr ptr) | 22 | NestedDepthFirstSearch(const PetriNet &net, PetriEngine::PQL::Condition_ptr ptr) |
72 | 22 | : ModelChecker(net, ptr), factory{net, successorGenerator->initial_buchi_state()}, | 23 | : ModelChecker(net, ptr), factory{net, successorGenerator->initial_buchi_state()}, |
74 | 23 | mark1(net, 0, (int)net.numberOfPlaces() + 1), mark2(net, 0, (int)net.numberOfPlaces() + 1) {} | 24 | states(net, 0, (int)net.numberOfPlaces() + 1) {} |
75 | 24 | 25 | ||
76 | 25 | bool isSatisfied() override; | 26 | bool isSatisfied() override; |
77 | 26 | 27 | ||
78 | @@ -28,9 +29,14 @@ | |||
79 | 28 | using State = LTL::Structures::ProductState; | 29 | using State = LTL::Structures::ProductState; |
80 | 29 | 30 | ||
81 | 30 | Structures::ProductStateFactory factory; | 31 | Structures::ProductStateFactory factory; |
84 | 31 | PetriEngine::Structures::StateSet mark1; | 32 | PetriEngine::Structures::StateSet states; |
85 | 32 | PetriEngine::Structures::StateSet mark2; | 33 | std::set<size_t> mark1; |
86 | 34 | std::set<size_t> mark2; | ||
87 | 33 | 35 | ||
88 | 36 | struct StackEntry { | ||
89 | 37 | size_t id; | ||
90 | 38 | successor_info sucinfo; | ||
91 | 39 | }; | ||
92 | 34 | 40 | ||
93 | 35 | State *seed; | 41 | State *seed; |
94 | 36 | bool violation = false; | 42 | bool violation = false; |
95 | 37 | 43 | ||
96 | === modified file 'include/LTL/LTL_algorithm/TarjanModelChecker.h' | |||
97 | --- include/LTL/LTL_algorithm/TarjanModelChecker.h 2020-10-19 12:35:11 +0000 | |||
98 | +++ include/LTL/LTL_algorithm/TarjanModelChecker.h 2020-11-09 13:59:57 +0000 | |||
99 | @@ -18,10 +18,11 @@ | |||
100 | 18 | 18 | ||
101 | 19 | namespace LTL { | 19 | namespace LTL { |
102 | 20 | 20 | ||
103 | 21 | template <bool SaveTrace> | ||
104 | 21 | class TarjanModelChecker : public ModelChecker { | 22 | class TarjanModelChecker : public ModelChecker { |
105 | 22 | public: | 23 | public: |
106 | 23 | TarjanModelChecker(const PetriEngine::PetriNet &net, const Condition_ptr &cond) | 24 | TarjanModelChecker(const PetriEngine::PetriNet &net, const Condition_ptr &cond) |
108 | 24 | : ModelChecker(net, cond), successorGenerator(net, cond), factory(net, successorGenerator.initial_buchi_state()), | 25 | : ModelChecker(net, cond), factory(net, successorGenerator->initial_buchi_state()), |
109 | 25 | seen(net, 0, (int) net.numberOfPlaces() + 1) { | 26 | seen(net, 0, (int) net.numberOfPlaces() + 1) { |
110 | 26 | chash.fill(std::numeric_limits<idx_t>::max()); | 27 | chash.fill(std::numeric_limits<idx_t>::max()); |
111 | 27 | } | 28 | } |
112 | @@ -31,45 +32,46 @@ | |||
113 | 31 | private: | 32 | private: |
114 | 32 | using State = LTL::Structures::ProductState; | 33 | using State = LTL::Structures::ProductState; |
115 | 33 | using idx_t = size_t; | 34 | using idx_t = size_t; |
116 | 35 | static constexpr idx_t HashSz = 4096; | ||
117 | 34 | 36 | ||
118 | 35 | LTL::ProductSuccessorGenerator successorGenerator; | ||
119 | 36 | LTL::Structures::ProductStateFactory factory; | 37 | LTL::Structures::ProductStateFactory factory; |
120 | 37 | 38 | ||
121 | 38 | PetriEngine::Structures::StateSet seen; | 39 | PetriEngine::Structures::StateSet seen; |
122 | 39 | std::unordered_set<idx_t> store; | 40 | std::unordered_set<idx_t> store; |
123 | 40 | //PetriEngine::Structures::StateSet store; | ||
124 | 41 | 41 | ||
125 | 42 | static constexpr idx_t HashSz = 4096; | ||
126 | 43 | std::array<idx_t, HashSz> chash; | 42 | std::array<idx_t, HashSz> chash; |
127 | 44 | inline idx_t hash_search(idx_t stateid) { | ||
128 | 45 | idx_t idx = chash[hash(stateid)]; | ||
129 | 46 | while (idx != stateid && idx != std::numeric_limits<idx_t>::max()) { | ||
130 | 47 | idx = cstack[idx].next; | ||
131 | 48 | } | ||
132 | 49 | return idx; | ||
133 | 50 | } | ||
134 | 51 | 43 | ||
136 | 52 | inline idx_t hash(idx_t id) { | 44 | static inline idx_t hash(idx_t id) { |
137 | 53 | return id % HashSz; | 45 | return id % HashSz; |
138 | 54 | } | 46 | } |
139 | 55 | 47 | ||
141 | 56 | struct CStack { | 48 | struct PlainCEntry { |
142 | 57 | size_t lowlink; | 49 | size_t lowlink; |
143 | 58 | size_t stateid; | 50 | size_t stateid; |
144 | 59 | size_t next = std::numeric_limits<idx_t>::max(); | 51 | size_t next = std::numeric_limits<idx_t>::max(); |
145 | 60 | 52 | ||
150 | 61 | CStack(size_t lowlink, size_t stateid, size_t next) : lowlink(lowlink), stateid(stateid), next(next) {} | 53 | PlainCEntry(size_t lowlink, size_t stateid, size_t next) : lowlink(lowlink), stateid(stateid), next(next) {} |
151 | 62 | }; | 54 | }; |
152 | 63 | 55 | ||
153 | 64 | struct DStack { | 56 | struct TracableCEntry : PlainCEntry { |
154 | 57 | idx_t lowsource = std::numeric_limits<size_t>::max(); | ||
155 | 58 | uint32_t sourcetrans; | ||
156 | 59 | |||
157 | 60 | TracableCEntry(size_t lowlink, size_t stateid, size_t next) : PlainCEntry(lowlink, stateid, next) {} | ||
158 | 61 | }; | ||
159 | 62 | |||
160 | 63 | using CEntry = std::conditional_t<SaveTrace, | ||
161 | 64 | TracableCEntry, | ||
162 | 65 | PlainCEntry>; | ||
163 | 66 | |||
164 | 67 | struct DEntry { | ||
165 | 65 | size_t pos; | 68 | size_t pos; |
168 | 66 | uint32_t nexttrans = -1; | 69 | successor_info sucinfo; |
167 | 67 | std::optional<std::vector<size_t>> neighbors; | ||
169 | 68 | }; | 70 | }; |
170 | 69 | 71 | ||
171 | 70 | 72 | ||
174 | 71 | std::vector<CStack> cstack; | 73 | std::vector<CEntry> cstack; |
175 | 72 | std::stack<DStack> dstack; | 74 | std::stack<DEntry> dstack; |
176 | 73 | std::stack<idx_t> astack; | 75 | std::stack<idx_t> astack; |
177 | 74 | bool violation = false; | 76 | bool violation = false; |
178 | 75 | 77 | ||
179 | @@ -79,8 +81,10 @@ | |||
180 | 79 | 81 | ||
181 | 80 | void update(idx_t to); | 82 | void update(idx_t to); |
182 | 81 | 83 | ||
184 | 82 | bool nexttrans(State &state, DStack &delem); | 84 | bool nexttrans(State &state, State& parent, DEntry &delem); |
185 | 83 | }; | 85 | }; |
186 | 86 | extern template class TarjanModelChecker<true>; | ||
187 | 87 | extern template class TarjanModelChecker<false>; | ||
188 | 84 | } | 88 | } |
189 | 85 | 89 | ||
190 | 86 | #endif //VERIFYPN_TARJANMODELCHECKER_H | 90 | #endif //VERIFYPN_TARJANMODELCHECKER_H |
191 | 87 | 91 | ||
192 | === modified file 'include/LTL/ProductSuccessorGenerator.h' | |||
193 | --- include/LTL/ProductSuccessorGenerator.h 2020-10-16 11:20:30 +0000 | |||
194 | +++ include/LTL/ProductSuccessorGenerator.h 2020-11-09 13:59:57 +0000 | |||
195 | @@ -11,13 +11,63 @@ | |||
196 | 11 | #include "LTL/BuchiSuccessorGenerator.h" | 11 | #include "LTL/BuchiSuccessorGenerator.h" |
197 | 12 | #include "LTL/LTLToBuchi.h" | 12 | #include "LTL/LTLToBuchi.h" |
198 | 13 | 13 | ||
199 | 14 | |||
200 | 14 | namespace LTL { | 15 | namespace LTL { |
201 | 16 | /** | ||
202 | 17 | * type holding sufficient information to resume successor generation for a state from a given point. | ||
203 | 18 | */ | ||
204 | 19 | struct successor_info { | ||
205 | 20 | uint32_t pcounter; | ||
206 | 21 | uint32_t tcounter; | ||
207 | 22 | size_t buchi_state; | ||
208 | 23 | size_t last_state; | ||
209 | 24 | |||
210 | 25 | friend bool operator==(const successor_info &lhs, const successor_info &rhs) { | ||
211 | 26 | return lhs.pcounter == rhs.pcounter && | ||
212 | 27 | lhs.tcounter == rhs.tcounter && | ||
213 | 28 | lhs.buchi_state == rhs.buchi_state && | ||
214 | 29 | lhs.last_state == rhs.last_state; | ||
215 | 30 | } | ||
216 | 31 | |||
217 | 32 | friend bool operator!=(const successor_info &lhs, const successor_info &rhs) { | ||
218 | 33 | return !(rhs == lhs); | ||
219 | 34 | } | ||
220 | 35 | |||
221 | 36 | inline bool has_pcounter() const { | ||
222 | 37 | return pcounter != NoPCounter; | ||
223 | 38 | } | ||
224 | 39 | |||
225 | 40 | inline bool has_tcounter() const { | ||
226 | 41 | return tcounter != NoTCounter; | ||
227 | 42 | } | ||
228 | 43 | |||
229 | 44 | inline bool has_buchistate() const { | ||
230 | 45 | return buchi_state != NoBuchiState; | ||
231 | 46 | } | ||
232 | 47 | |||
233 | 48 | inline bool has_prev_state() const { | ||
234 | 49 | return last_state != NoLastState; | ||
235 | 50 | } | ||
236 | 51 | |||
237 | 52 | static constexpr auto NoPCounter = 0; | ||
238 | 53 | static constexpr auto NoTCounter = std::numeric_limits<uint32_t>::max(); | ||
239 | 54 | static constexpr auto NoBuchiState = std::numeric_limits<size_t>::max(); | ||
240 | 55 | static constexpr auto NoLastState = std::numeric_limits<size_t>::max(); | ||
241 | 56 | }; | ||
242 | 57 | |||
243 | 58 | constexpr successor_info initial_suc_info{ | ||
244 | 59 | successor_info::NoPCounter, | ||
245 | 60 | successor_info::NoTCounter, | ||
246 | 61 | successor_info::NoBuchiState, | ||
247 | 62 | successor_info::NoLastState | ||
248 | 63 | }; | ||
249 | 64 | |||
250 | 15 | class ProductSuccessorGenerator : public PetriEngine::SuccessorGenerator { | 65 | class ProductSuccessorGenerator : public PetriEngine::SuccessorGenerator { |
251 | 16 | public: | 66 | public: |
252 | 67 | |||
253 | 17 | ProductSuccessorGenerator(const PetriEngine::PetriNet &net, | 68 | ProductSuccessorGenerator(const PetriEngine::PetriNet &net, |
257 | 18 | const PetriEngine::PQL::Condition_ptr& cond) | 69 | const PetriEngine::PQL::Condition_ptr &cond) |
258 | 19 | : PetriEngine::SuccessorGenerator(net), buchi(makeBuchiAutomaton(cond)) | 70 | : PetriEngine::SuccessorGenerator(net), buchi(makeBuchiAutomaton(cond)) {} |
256 | 20 | {} | ||
259 | 21 | 71 | ||
260 | 22 | [[nodiscard]] size_t initial_buchi_state() const { return buchi.initial_state_number(); }; | 72 | [[nodiscard]] size_t initial_buchi_state() const { return buchi.initial_state_number(); }; |
261 | 23 | 73 | ||
262 | @@ -43,8 +93,21 @@ | |||
263 | 43 | } | 93 | } |
264 | 44 | } | 94 | } |
265 | 45 | 95 | ||
268 | 46 | protected: | 96 | /** |
269 | 47 | bool next(LTL::Structures::ProductState &write, uint32_t &tindex); | 97 | * prepare a state for successor generation, starting from specific point in iteration |
270 | 98 | * @param state the source state to generate successors from | ||
271 | 99 | * @param sucinfo the point in the iteration to start from, as returned by `next`. | ||
272 | 100 | */ | ||
273 | 101 | void prepare(const LTL::Structures::ProductState *state, const successor_info &sucinfo); | ||
274 | 102 | |||
275 | 103 | /** | ||
276 | 104 | * compute the next successor from the last state that was sent to `prepare`. | ||
277 | 105 | * @param[out] state the state to write | ||
278 | 106 | * @param[out] sucinfo checkpoint information from which iteration can later be resumed. | ||
279 | 107 | * @return `true` if a successor was successfully generated, `false` otherwise. | ||
280 | 108 | * @warning do not use the same State for both prepare and next, this will cause wildly incorrect behaviour! | ||
281 | 109 | */ | ||
282 | 110 | bool next(Structures::ProductState &state, successor_info &sucinfo); | ||
283 | 48 | 111 | ||
284 | 49 | private: | 112 | private: |
285 | 50 | BuchiSuccessorGenerator buchi; | 113 | BuchiSuccessorGenerator buchi; |
286 | 51 | 114 | ||
287 | === modified file 'include/LTL/Structures/ProductState.h' | |||
288 | --- include/LTL/Structures/ProductState.h 2020-10-16 11:20:30 +0000 | |||
289 | +++ include/LTL/Structures/ProductState.h 2020-11-09 13:59:57 +0000 | |||
290 | @@ -48,6 +48,8 @@ | |||
291 | 48 | getBuchiState() == rhs.getBuchiState();*/ | 48 | getBuchiState() == rhs.getBuchiState();*/ |
292 | 49 | } | 49 | } |
293 | 50 | 50 | ||
294 | 51 | size_t size() const { return buchi_state_idx + 1; } | ||
295 | 52 | |||
296 | 51 | bool operator!=(const ProductState &rhs) const { | 53 | bool operator!=(const ProductState &rhs) const { |
297 | 52 | return !(rhs == *this); | 54 | return !(rhs == *this); |
298 | 53 | } | 55 | } |
299 | 54 | 56 | ||
300 | === modified file 'include/PetriEngine/PQL/Expressions.h' | |||
301 | --- include/PetriEngine/PQL/Expressions.h 2020-09-23 12:26:04 +0000 | |||
302 | +++ include/PetriEngine/PQL/Expressions.h 2020-11-09 13:59:57 +0000 | |||
303 | @@ -533,7 +533,7 @@ | |||
304 | 533 | // TODO implement | 533 | // TODO implement |
305 | 534 | assert(false); std::cerr << "TODO implement" << std::endl; exit(0); | 534 | assert(false); std::cerr << "TODO implement" << std::endl; exit(0); |
306 | 535 | } | 535 | } |
308 | 536 | bool containsNext() const override { return true; } | 536 | bool containsNext() const override { return _cond->containsNext(); } |
309 | 537 | virtual bool isLoopSensitive() const override { return true; } | 537 | virtual bool isLoopSensitive() const override { return true; } |
310 | 538 | void visit(Visitor&) const override; | 538 | void visit(Visitor&) const override; |
311 | 539 | private: | 539 | private: |
312 | @@ -569,7 +569,7 @@ | |||
313 | 569 | // TODO implement | 569 | // TODO implement |
314 | 570 | assert(false); std::cerr << "TODO implement" << std::endl; exit(0); | 570 | assert(false); std::cerr << "TODO implement" << std::endl; exit(0); |
315 | 571 | } | 571 | } |
317 | 572 | bool containsNext() const override { return true; } | 572 | bool containsNext() const override { return _cond->containsNext(); } |
318 | 573 | virtual bool isLoopSensitive() const override { return true; } | 573 | virtual bool isLoopSensitive() const override { return true; } |
319 | 574 | void visit(Visitor&) const override; | 574 | void visit(Visitor&) const override; |
320 | 575 | private: | 575 | private: |
321 | 576 | 576 | ||
322 | === modified file 'include/PetriEngine/SuccessorGenerator.h' | |||
323 | --- include/PetriEngine/SuccessorGenerator.h 2020-10-16 11:20:30 +0000 | |||
324 | +++ include/PetriEngine/SuccessorGenerator.h 2020-11-09 13:59:57 +0000 | |||
325 | @@ -60,16 +60,20 @@ | |||
326 | 60 | */ | 60 | */ |
327 | 61 | void producePostset(Structures::State& write, uint32_t t); | 61 | void producePostset(Structures::State& write, uint32_t t); |
328 | 62 | 62 | ||
329 | 63 | size_t last_transition() const { return _suc_tcounter == std::numeric_limits<uint32_t>::max() ? std::numeric_limits<uint32_t>::max() : _suc_tcounter - 1; } | ||
330 | 64 | |||
331 | 63 | protected: | 65 | protected: |
332 | 64 | const PetriNet& _net; | 66 | const PetriNet& _net; |
333 | 65 | 67 | ||
334 | 66 | bool next(Structures::State &write, uint32_t &tindex); | 68 | bool next(Structures::State &write, uint32_t &tindex); |
335 | 67 | 69 | ||
336 | 68 | const Structures::State* _parent; | 70 | const Structures::State* _parent; |
338 | 69 | private: | 71 | |
339 | 70 | uint32_t _suc_pcounter; | 72 | uint32_t _suc_pcounter; |
340 | 71 | uint32_t _suc_tcounter; | 73 | uint32_t _suc_tcounter; |
341 | 72 | 74 | ||
342 | 75 | private: | ||
343 | 76 | |||
344 | 73 | friend class ReducingSuccessorGenerator; | 77 | friend class ReducingSuccessorGenerator; |
345 | 74 | 78 | ||
346 | 75 | }; | 79 | }; |
347 | 76 | 80 | ||
348 | === modified file 'src/LTL/LTL_algorithm/LTLToBuchi.cpp' | |||
349 | --- src/LTL/LTL_algorithm/LTLToBuchi.cpp 2020-10-16 11:20:30 +0000 | |||
350 | +++ src/LTL/LTL_algorithm/LTLToBuchi.cpp 2020-11-09 13:59:57 +0000 | |||
351 | @@ -29,8 +29,6 @@ | |||
352 | 29 | 29 | ||
353 | 30 | void _accept(const PetriEngine::PQL::OrCondition *element) override; | 30 | void _accept(const PetriEngine::PQL::OrCondition *element) override; |
354 | 31 | 31 | ||
355 | 32 | //void _accept(const PetriEngine::PQL::CompareConjunction *element) override; | ||
356 | 33 | |||
357 | 34 | void _accept(const PetriEngine::PQL::LessThanCondition *element) override; | 32 | void _accept(const PetriEngine::PQL::LessThanCondition *element) override; |
358 | 35 | 33 | ||
359 | 36 | void _accept(const PetriEngine::PQL::LessThanOrEqualCondition *element) override; | 34 | void _accept(const PetriEngine::PQL::LessThanOrEqualCondition *element) override; |
360 | @@ -63,7 +61,7 @@ | |||
361 | 63 | 61 | ||
362 | 64 | public: | 62 | public: |
363 | 65 | 63 | ||
365 | 66 | FormulaToSpotSyntax(std::ostream &os = std::cout) | 64 | explicit FormulaToSpotSyntax(std::ostream &os = std::cout) |
366 | 67 | : PetriEngine::PQL::QueryPrinter(os) {} | 65 | : PetriEngine::PQL::QueryPrinter(os) {} |
367 | 68 | 66 | ||
368 | 69 | auto begin() const { | 67 | auto begin() const { |
369 | @@ -147,88 +145,76 @@ | |||
370 | 147 | 145 | ||
371 | 148 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::LiteralExpr *element) { | 146 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::LiteralExpr *element) { |
372 | 149 | assert(false); | 147 | assert(false); |
374 | 150 | std::cerr << "LiteralExpr should not be visited by Spot serialiezr" << std::endl; | 148 | std::cerr << "LiteralExpr should not be visited by Spot serializer" << std::endl; |
375 | 151 | exit(1); | 149 | exit(1); |
376 | 152 | //make_atomic_prop(element->shared_from_this()); | 150 | //make_atomic_prop(element->shared_from_this()); |
377 | 153 | } | 151 | } |
378 | 154 | 152 | ||
379 | 155 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::PlusExpr *element) { | 153 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::PlusExpr *element) { |
380 | 156 | assert(false); | 154 | assert(false); |
382 | 157 | std::cerr << "PlusExpr should not be visited by Spot serialiezr" << std::endl; | 155 | std::cerr << "PlusExpr should not be visited by Spot serializer" << std::endl; |
383 | 158 | exit(1); | 156 | exit(1); |
384 | 159 | //make_atomic_prop(element->shared_from_this()); | 157 | //make_atomic_prop(element->shared_from_this()); |
385 | 160 | } | 158 | } |
386 | 161 | 159 | ||
387 | 162 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::MultiplyExpr *element) { | 160 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::MultiplyExpr *element) { |
388 | 163 | assert(false); | 161 | assert(false); |
390 | 164 | std::cerr << "MultiplyExpr should not be visited by Spot serialiezr" << std::endl; | 162 | std::cerr << "MultiplyExpr should not be visited by Spot serializer" << std::endl; |
391 | 165 | exit(1); | 163 | exit(1); |
392 | 166 | //make_atomic_prop(element->shared_from_this()); | 164 | //make_atomic_prop(element->shared_from_this()); |
393 | 167 | } | 165 | } |
394 | 168 | 166 | ||
395 | 169 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::MinusExpr *element) { | 167 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::MinusExpr *element) { |
396 | 170 | assert(false); | 168 | assert(false); |
398 | 171 | std::cerr << "MinusExpr should not be visited by Spot serialiezr" << std::endl; | 169 | std::cerr << "MinusExpr should not be visited by Spot serializer" << std::endl; |
399 | 172 | exit(1); | 170 | exit(1); |
400 | 173 | //make_atomic_prop(element->shared_from_this()); | 171 | //make_atomic_prop(element->shared_from_this()); |
401 | 174 | } | 172 | } |
402 | 175 | 173 | ||
403 | 176 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::SubtractExpr *element) { | 174 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::SubtractExpr *element) { |
404 | 177 | assert(false); | 175 | assert(false); |
406 | 178 | std::cerr << "LiteralExpr should not be visited by Spot serialiezr" << std::endl; | 176 | std::cerr << "LiteralExpr should not be visited by Spot serializer" << std::endl; |
407 | 179 | exit(1); | 177 | exit(1); |
408 | 180 | //make_atomic_prop(element->shared_from_this()); | 178 | //make_atomic_prop(element->shared_from_this()); |
409 | 181 | } | 179 | } |
410 | 182 | 180 | ||
411 | 183 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::IdentifierExpr *element) { | 181 | void FormulaToSpotSyntax::_accept(const PetriEngine::PQL::IdentifierExpr *element) { |
412 | 184 | assert(false); | 182 | assert(false); |
414 | 185 | std::cerr << "IdentifierExpr should not be visited by Spot serialiezr" << std::endl; | 183 | std::cerr << "IdentifierExpr should not be visited by Spot serializer" << std::endl; |
415 | 186 | exit(1); | 184 | exit(1); |
416 | 187 | //make_atomic_prop(element->shared_from_this()); | 185 | //make_atomic_prop(element->shared_from_this()); |
417 | 188 | } | 186 | } |
418 | 189 | 187 | ||
419 | 190 | |||
420 | 191 | std::string toSpotFormat(const QueryItem &query) { | ||
421 | 192 | std::stringstream ss; | ||
422 | 193 | toSpotFormat(query, ss); | ||
423 | 194 | return ss.str(); | ||
424 | 195 | } | ||
425 | 196 | |||
426 | 197 | void toSpotFormat(const QueryItem &query, std::ostream &os) { | ||
427 | 198 | FormulaToSpotSyntax spotConverter{os}; | ||
428 | 199 | // FIXME nasty hack for top-level query, should be fixed elsewhere (e.g. asLTL) | ||
429 | 200 | auto top_quant = dynamic_cast<SimpleQuantifierCondition *>(query.query.get()); | ||
430 | 201 | (*top_quant)[0]->visit(spotConverter); | ||
431 | 202 | } | ||
432 | 203 | |||
433 | 204 | BuchiSuccessorGenerator makeBuchiAutomaton(const Condition_ptr &query) { | 188 | BuchiSuccessorGenerator makeBuchiAutomaton(const Condition_ptr &query) { |
434 | 205 | std::stringstream ss; | 189 | std::stringstream ss; |
435 | 206 | FormulaToSpotSyntax spotConverter{ss}; | 190 | FormulaToSpotSyntax spotConverter{ss}; |
436 | 207 | query->visit(spotConverter); | 191 | query->visit(spotConverter); |
437 | 208 | |||
438 | 209 | const std::string spotFormula = "!(" + ss.str() + ")"; | 192 | const std::string spotFormula = "!(" + ss.str() + ")"; |
439 | 210 | #ifdef PRINTF_DEBUG | 193 | #ifdef PRINTF_DEBUG |
440 | 211 | std::cerr << "ORIG FORMULA: \n " << ss.str() << std::endl; | 194 | std::cerr << "ORIG FORMULA: \n " << ss.str() << std::endl; |
441 | 212 | std::cerr << "SPOT FORMULA: \n " << spotFormula << std::endl; | 195 | std::cerr << "SPOT FORMULA: \n " << spotFormula << std::endl; |
442 | 213 | #endif | 196 | #endif |
443 | 214 | spot::formula formula = spot::parse_formula(spotFormula); | 197 | spot::formula formula = spot::parse_formula(spotFormula); |
448 | 215 | spot::bdd_dict_ptr bdd = spot::make_bdd_dict(); | 198 | spot::translator translator; |
449 | 216 | auto translator = spot::translator(bdd); | 199 | translator.set_type(spot::postprocessor::BA); |
450 | 217 | translator.set_pref(spot::postprocessor::Complete | 200 | translator.set_pref(spot::postprocessor::Complete); |
447 | 218 | | spot::postprocessor::SBAcc); | ||
451 | 219 | spot::twa_graph_ptr automaton = translator.run(formula); | 201 | spot::twa_graph_ptr automaton = translator.run(formula); |
452 | 220 | #ifdef PRINTF_DEBUG | 202 | #ifdef PRINTF_DEBUG |
453 | 221 | automaton->get_graph().dump_storage(std::cerr); | 203 | automaton->get_graph().dump_storage(std::cerr); |
454 | 222 | spot::print_dot(std::cerr, automaton); | 204 | spot::print_dot(std::cerr, automaton); |
455 | 223 | bdd->dump(std::cerr); | ||
456 | 224 | #endif | 205 | #endif |
457 | 225 | std::unordered_map<int, AtomicProposition> ap_map; | 206 | std::unordered_map<int, AtomicProposition> ap_map; |
458 | 207 | // bind PQL expressions to the atomic proposition IDs used by spot. | ||
459 | 208 | // the resulting map can be indexed using variables mentioned on edges of the created Büchi automaton. | ||
460 | 226 | for (const auto &apinfo : spotConverter) { | 209 | for (const auto &apinfo : spotConverter) { |
461 | 227 | int varnum = automaton->register_ap(apinfo.text); | 210 | int varnum = automaton->register_ap(apinfo.text); |
462 | 228 | ap_map[varnum] = apinfo; | 211 | ap_map[varnum] = apinfo; |
463 | 229 | } | 212 | } |
464 | 213 | #ifdef PRINTF_DEBUG | ||
465 | 214 | automaton->get_dict()->dump(std::cerr); | ||
466 | 215 | #endif | ||
467 | 230 | 216 | ||
469 | 231 | return BuchiSuccessorGenerator{Structures::BuchiAutomaton{automaton, ap_map}}; | 217 | return BuchiSuccessorGenerator{Structures::BuchiAutomaton{std::move(automaton), std::move(ap_map)}}; |
470 | 232 | } | 218 | } |
471 | 233 | 219 | ||
472 | 234 | } | ||
473 | 235 | \ No newline at end of file | 220 | \ No newline at end of file |
474 | 221 | } | ||
475 | 236 | 222 | ||
476 | === modified file 'src/LTL/LTL_algorithm/NestedDepthFirstSearch.cpp' | |||
477 | --- src/LTL/LTL_algorithm/NestedDepthFirstSearch.cpp 2020-10-19 12:35:11 +0000 | |||
478 | +++ src/LTL/LTL_algorithm/NestedDepthFirstSearch.cpp 2020-11-09 13:59:57 +0000 | |||
479 | @@ -20,100 +20,106 @@ | |||
480 | 20 | 20 | ||
481 | 21 | bool NestedDepthFirstSearch::isSatisfied() { | 21 | bool NestedDepthFirstSearch::isSatisfied() { |
482 | 22 | dfs(); | 22 | dfs(); |
483 | 23 | #ifdef _PRINTF_DEBUG | ||
484 | 24 | std::cout << "discovered " << _discovered << " states." << std::endl; | ||
485 | 25 | std::cout << "mark1 size: " << mark1.size() << "\tmark2 size: " << mark2.size() << std::endl; | ||
486 | 26 | #endif | ||
487 | 23 | return !violation; | 27 | return !violation; |
488 | 24 | } | 28 | } |
489 | 25 | 29 | ||
490 | 26 | void NestedDepthFirstSearch::dfs() { | 30 | void NestedDepthFirstSearch::dfs() { |
491 | 27 | std::stack<size_t> call_stack; | 31 | std::stack<size_t> call_stack; |
495 | 28 | 32 | std::stack<StackEntry> todo; | |
493 | 29 | PetriEngine::Structures::StateSet states{net,0, (int)net.numberOfPlaces() + 1}; | ||
494 | 30 | PetriEngine::Structures::DFSQueue todo{&states}; | ||
496 | 31 | 33 | ||
497 | 32 | State working = factory.newState(); | 34 | State working = factory.newState(); |
498 | 33 | PQL::DistanceContext ctx{&net, working.marking()}; | ||
499 | 34 | State curState = factory.newState(); | 35 | State curState = factory.newState(); |
500 | 36 | |||
501 | 35 | { | 37 | { |
502 | 36 | std::vector<State> initial_states; | 38 | std::vector<State> initial_states; |
503 | 37 | successorGenerator->makeInitialState(initial_states); | 39 | successorGenerator->makeInitialState(initial_states); |
504 | 38 | for (auto &state : initial_states) { | 40 | for (auto &state : initial_states) { |
505 | 39 | auto res = states.add(state); | 41 | auto res = states.add(state); |
506 | 40 | assert(res.first); | 42 | assert(res.first); |
508 | 41 | todo.push(res.second, ctx, formula); | 43 | todo.push(StackEntry{res.second, initial_suc_info}); |
509 | 44 | _discovered++; | ||
510 | 42 | } | 45 | } |
511 | 43 | } | 46 | } |
512 | 44 | 47 | ||
516 | 45 | while (todo.top(curState)) { | 48 | while (!todo.empty()) { |
517 | 46 | 49 | auto &top = todo.top(); | |
518 | 47 | if (!call_stack.empty() && states.lookup(curState).second == call_stack.top()) { | 50 | states.decode(curState, top.id); |
519 | 51 | successorGenerator->prepare(&curState, top.sucinfo); | ||
520 | 52 | if (top.sucinfo.has_prev_state()) { | ||
521 | 53 | states.decode(working, top.sucinfo.last_state); | ||
522 | 54 | } | ||
523 | 55 | if (!successorGenerator->next(working, top.sucinfo)) { | ||
524 | 56 | // no successor | ||
525 | 57 | todo.pop(); | ||
526 | 48 | if (successorGenerator->isAccepting(curState)) { | 58 | if (successorGenerator->isAccepting(curState)) { |
527 | 49 | seed = &curState; | 59 | seed = &curState; |
528 | 50 | ndfs(curState); | 60 | ndfs(curState); |
531 | 51 | if (violation) | 61 | if (violation) return; |
530 | 52 | return; | ||
532 | 53 | } | 62 | } |
533 | 54 | todo.pop(curState); | ||
534 | 55 | call_stack.pop(); | ||
535 | 56 | } else { | 63 | } else { |
552 | 57 | call_stack.push(states.add(curState).second); | 64 | #ifdef PRINTF_DEBUG |
553 | 58 | if (!mark1.add(curState).first) { | 65 | dump_state(working); |
554 | 59 | continue; | 66 | #endif |
555 | 60 | } | 67 | auto[_, stateid] = states.add(working); |
556 | 61 | successorGenerator->prepare(&curState); | 68 | auto[it, is_new] = mark1.insert(stateid); |
557 | 62 | #ifdef PRINTF_DEBUG | 69 | top.sucinfo.last_state = stateid; |
558 | 63 | std::cerr << "curState:\n"; | 70 | if (is_new) { |
559 | 64 | dump_state(curState); | 71 | _discovered++; |
560 | 65 | #endif | 72 | todo.push(StackEntry{stateid, initial_suc_info}); |
545 | 66 | while (successorGenerator->next(working)) { | ||
546 | 67 | #ifdef PRINTF_DEBUG | ||
547 | 68 | std::cerr << "working:\n"; | ||
548 | 69 | dump_state(working); | ||
549 | 70 | #endif | ||
550 | 71 | auto r = states.add(working); | ||
551 | 72 | todo.push(r.second, ctx, formula); | ||
561 | 73 | } | 73 | } |
562 | 74 | } | 74 | } |
563 | 75 | } | 75 | } |
564 | 76 | } | 76 | } |
565 | 77 | 77 | ||
566 | 78 | 78 | ||
570 | 79 | void NestedDepthFirstSearch::ndfs(State& state) { | 79 | void NestedDepthFirstSearch::ndfs(State &state) { |
571 | 80 | PetriEngine::Structures::StateSet states{net, 0, (int)net.numberOfPlaces() + 1}; | 80 | #ifdef PRINTF_DEBUG |
572 | 81 | PetriEngine::Structures::DFSQueue todo{&states}; | 81 | std::cerr << "ENTERING NDFS" << std::endl; |
573 | 82 | #endif | ||
574 | 83 | std::stack<StackEntry> todo; | ||
575 | 82 | 84 | ||
576 | 83 | State working = factory.newState(); | 85 | State working = factory.newState(); |
577 | 84 | State curState = factory.newState(); | 86 | State curState = factory.newState(); |
578 | 85 | 87 | ||
586 | 86 | PQL::DistanceContext ctx{&net, state.marking()}; | 88 | todo.push(StackEntry{states.add(state).second, initial_suc_info}); |
587 | 87 | 89 | ||
588 | 88 | todo.push(states.add(state).second, ctx, formula); | 90 | while (!todo.empty()) { |
589 | 89 | 91 | auto &top = todo.top(); | |
590 | 90 | while (todo.pop(curState)) { | 92 | states.decode(curState, top.id); |
591 | 91 | if (!mark2.add(curState).first) { | 93 | successorGenerator->prepare(&curState, top.sucinfo); |
592 | 92 | continue; | 94 | if (top.sucinfo.has_prev_state()) { |
593 | 95 | states.decode(working, top.sucinfo.last_state); | ||
594 | 93 | } | 96 | } |
604 | 94 | 97 | if (!successorGenerator->next(working, top.sucinfo)) { | |
605 | 95 | successorGenerator->prepare(&curState); | 98 | todo.pop(); |
606 | 96 | #ifdef PRINTF_DEBUG | 99 | } else { |
607 | 97 | std::cerr << "curState:\n"; | 100 | #ifdef PRINTF_DEBUG |
599 | 98 | dump_state(curState); | ||
600 | 99 | #endif | ||
601 | 100 | while (successorGenerator->next(working)) { | ||
602 | 101 | #ifdef PRINTF_DEBUG | ||
603 | 102 | std::cerr << "working:\n"; | ||
608 | 103 | dump_state(working); | 101 | dump_state(working); |
609 | 104 | #endif | 102 | #endif |
610 | 105 | if (working == *seed) { | 103 | if (working == *seed) { |
612 | 106 | #ifdef PRINTF_DEBUG | 104 | #ifdef _PRINTF_DEBUG |
613 | 107 | std::cerr << "seed:\n "; dump_state(*seed); | 105 | std::cerr << "seed:\n "; dump_state(*seed); |
614 | 108 | std::cerr << "working:\n "; dump_state(working); | 106 | std::cerr << "working:\n "; dump_state(working); |
615 | 109 | #endif | 107 | #endif |
616 | 110 | violation = true; | 108 | violation = true; |
617 | 111 | return; | 109 | return; |
618 | 112 | } | 110 | } |
621 | 113 | auto r = states.add(working); | 111 | auto[_, stateid] = states.add(working); |
622 | 114 | todo.push(r.second, ctx, formula); | 112 | auto[it, is_new] = mark2.insert(stateid); |
623 | 113 | top.sucinfo.last_state = stateid; | ||
624 | 114 | if (is_new) { | ||
625 | 115 | _discovered++; | ||
626 | 116 | todo.push(StackEntry{stateid, initial_suc_info}); | ||
627 | 117 | } | ||
628 | 118 | |||
629 | 115 | } | 119 | } |
630 | 116 | } | 120 | } |
632 | 117 | 121 | #ifdef PRINTF_DEBUG | |
633 | 122 | std::cerr << "LEAVING NDFS" << std::endl; | ||
634 | 123 | #endif | ||
635 | 118 | } | 124 | } |
636 | 119 | } | 125 | } |
637 | 120 | \ No newline at end of file | 126 | \ No newline at end of file |
638 | 121 | 127 | ||
639 | === modified file 'src/LTL/LTL_algorithm/ProductSuccessorGenerator.cpp' | |||
640 | --- src/LTL/LTL_algorithm/ProductSuccessorGenerator.cpp 2020-10-16 11:20:30 +0000 | |||
641 | +++ src/LTL/LTL_algorithm/ProductSuccessorGenerator.cpp 2020-11-09 13:59:57 +0000 | |||
642 | @@ -29,6 +29,27 @@ | |||
643 | 29 | fresh_marking = true; | 29 | fresh_marking = true; |
644 | 30 | } | 30 | } |
645 | 31 | 31 | ||
646 | 32 | void ProductSuccessorGenerator::prepare(const LTL::Structures::ProductState *state, const successor_info &sucinfo) { | ||
647 | 33 | SuccessorGenerator::prepare(state); | ||
648 | 34 | buchi.prepare(state->getBuchiState()); | ||
649 | 35 | buchi_parent = state->getBuchiState(); | ||
650 | 36 | fresh_marking = sucinfo.pcounter == 0 && sucinfo.tcounter == std::numeric_limits<uint32_t>::max(); | ||
651 | 37 | _suc_pcounter = sucinfo.pcounter; | ||
652 | 38 | _suc_tcounter = sucinfo.tcounter; | ||
653 | 39 | if (!fresh_marking) { | ||
654 | 40 | assert(sucinfo.buchi_state != std::numeric_limits<size_t>::max()); | ||
655 | 41 | // spool Büchi successors until last state found. | ||
656 | 42 | // TODO is there perhaps a good way to avoid this, perhaps using raw edge vector? | ||
657 | 43 | // Caveat: it seems like there usually are not that many successors, so this is probably cheap regardless | ||
658 | 44 | size_t tmp; | ||
659 | 45 | while (buchi.next(tmp, cond)) { | ||
660 | 46 | if (tmp == sucinfo.buchi_state) { | ||
661 | 47 | break; | ||
662 | 48 | } | ||
663 | 49 | } | ||
664 | 50 | } | ||
665 | 51 | } | ||
666 | 52 | |||
667 | 32 | bool ProductSuccessorGenerator::next(LTL::Structures::ProductState &state) { | 53 | bool ProductSuccessorGenerator::next(LTL::Structures::ProductState &state) { |
668 | 33 | if (fresh_marking) { | 54 | if (fresh_marking) { |
669 | 34 | fresh_marking = false; | 55 | fresh_marking = false; |
670 | @@ -75,14 +96,16 @@ | |||
671 | 75 | 96 | ||
672 | 76 | bool ProductSuccessorGenerator::guard_valid(const PetriEngine::Structures::State &state, bdd bdd) { | 97 | bool ProductSuccessorGenerator::guard_valid(const PetriEngine::Structures::State &state, bdd bdd) { |
673 | 77 | EvaluationContext ctx{state.marking(), &_net}; | 98 | EvaluationContext ctx{state.marking(), &_net}; |
675 | 78 | while (!(bdd == bddtrue || bdd == bddfalse)) { | 99 | // IDs 0 and 1 are false and true atoms, respectively |
676 | 100 | while (bdd.id() > 1/*!(bdd == bddtrue || bdd == bddfalse)*/) { | ||
677 | 101 | // find variable to test, and test it | ||
678 | 79 | size_t var = bdd_var(bdd); | 102 | size_t var = bdd_var(bdd); |
679 | 80 | Condition::Result res = buchi.getExpression(var)->evaluate(ctx); | 103 | Condition::Result res = buchi.getExpression(var)->evaluate(ctx); |
680 | 81 | switch (res) { | 104 | switch (res) { |
681 | 82 | case Condition::RUNKNOWN: | 105 | case Condition::RUNKNOWN: |
682 | 83 | std::cerr << "Unexpected unknown answer from evaluating query!\n"; | 106 | std::cerr << "Unexpected unknown answer from evaluating query!\n"; |
683 | 84 | assert(false); | 107 | assert(false); |
685 | 85 | exit(0); | 108 | exit(1); |
686 | 86 | break; | 109 | break; |
687 | 87 | case Condition::RFALSE: | 110 | case Condition::RFALSE: |
688 | 88 | bdd = bdd_low(bdd); | 111 | bdd = bdd_low(bdd); |
689 | @@ -95,23 +118,33 @@ | |||
690 | 95 | return bdd == bddtrue; | 118 | return bdd == bddtrue; |
691 | 96 | } | 119 | } |
692 | 97 | 120 | ||
694 | 98 | bool ProductSuccessorGenerator::next(Structures::ProductState &state, uint32_t &tindex) { | 121 | bool ProductSuccessorGenerator::next(Structures::ProductState &state, successor_info &sucinfo) { |
695 | 122 | auto update_sucinfo = [&]() { | ||
696 | 123 | sucinfo.pcounter = _suc_pcounter; | ||
697 | 124 | sucinfo.tcounter = _suc_tcounter; | ||
698 | 125 | sucinfo.buchi_state = state.getBuchiState(); | ||
699 | 126 | }; | ||
700 | 127 | |||
701 | 99 | if (fresh_marking) { | 128 | if (fresh_marking) { |
702 | 100 | fresh_marking = false; | 129 | fresh_marking = false; |
705 | 101 | if (!SuccessorGenerator::next(state, tindex)) { | 130 | if (!SuccessorGenerator::next(state)) { |
706 | 102 | // This is a fresh marking, so if there is no more successors for the state the state is deadlocked. | 131 | // This is a fresh marking, so if there are no more successors for the state the state is deadlocked. |
707 | 103 | // The semantics for deadlock is to just loop the marking so return true without changing the value of state. | 132 | // The semantics for deadlock is to just loop the marking so return true without changing the value of state. |
709 | 104 | // This assumes SuccessorGenerator::next only modifies &state if there is a successor. | 133 | std::copy(_parent->marking(), _parent->marking() + state.buchi_state_idx + 1, state.marking()); |
710 | 105 | } | 134 | } |
711 | 106 | } | 135 | } |
712 | 107 | if (next_buchi_succ(state)) { | 136 | if (next_buchi_succ(state)) { |
713 | 137 | update_sucinfo(); | ||
714 | 108 | return true; | 138 | return true; |
715 | 109 | } | 139 | } |
718 | 110 | // No valid transition in Büchi automaton for current marking; | 140 | // No valid transition in Büchi automaton for current marking; |
719 | 111 | // Try next marking(s) and see if we find a successor. | 141 | // Try next marking(s) and see if we find a successor. |
720 | 112 | else { | 142 | else { |
722 | 113 | while (SuccessorGenerator::next(state, tindex)) { | 143 | while (SuccessorGenerator::next(state)) { |
723 | 144 | // reset buchi successors | ||
724 | 145 | buchi.prepare(buchi_parent); | ||
725 | 114 | if (next_buchi_succ(state)) { | 146 | if (next_buchi_succ(state)) { |
726 | 147 | update_sucinfo(); | ||
727 | 115 | return true; | 148 | return true; |
728 | 116 | } | 149 | } |
729 | 117 | } | 150 | } |
730 | 118 | 151 | ||
731 | === modified file 'src/LTL/LTL_algorithm/TarjanModelChecker.cpp' | |||
732 | --- src/LTL/LTL_algorithm/TarjanModelChecker.cpp 2020-10-19 12:35:11 +0000 | |||
733 | +++ src/LTL/LTL_algorithm/TarjanModelChecker.cpp 2020-11-09 13:59:57 +0000 | |||
734 | @@ -7,72 +7,123 @@ | |||
735 | 7 | 7 | ||
736 | 8 | #include "LTL/LTL_algorithm/TarjanModelChecker.h" | 8 | #include "LTL/LTL_algorithm/TarjanModelChecker.h" |
737 | 9 | 9 | ||
738 | 10 | #undef PRINTF_DEBUG | ||
739 | 10 | namespace LTL { | 11 | namespace LTL { |
740 | 11 | 12 | ||
746 | 12 | 13 | inline void _dump_state(const LTL::Structures::ProductState &state) { | |
742 | 13 | #ifdef PRINTF_DEBUG | ||
743 | 14 | |||
744 | 15 | inline void _dump_state(const LTL::Structures::ProductState &state, int nplaces = -1) { | ||
745 | 16 | if (nplaces == -1) nplaces = state.buchi_state_idx; | ||
747 | 17 | std::cerr << "marking: "; | 14 | std::cerr << "marking: "; |
748 | 18 | std::cerr << state.marking()[0]; | 15 | std::cerr << state.marking()[0]; |
750 | 19 | for (int i = 1; i <= nplaces; ++i) { | 16 | for (int i = 1; i < state.size(); ++i) { |
751 | 20 | std::cerr << ", " << state.marking()[i]; | 17 | std::cerr << ", " << state.marking()[i]; |
752 | 21 | } | 18 | } |
753 | 22 | std::cerr << std::endl; | 19 | std::cerr << std::endl; |
754 | 23 | } | 20 | } |
755 | 24 | 21 | ||
764 | 25 | #endif | 22 | template<bool SaveTrace> |
765 | 26 | 23 | bool TarjanModelChecker<SaveTrace>::isSatisfied() { | |
766 | 27 | bool LTL::TarjanModelChecker::isSatisfied() { | 24 | std::vector<State> initial_states; |
767 | 28 | { | 25 | successorGenerator->makeInitialState(initial_states); |
768 | 29 | std::vector<State> initial_states; | 26 | State working = factory.newState(); |
769 | 30 | successorGenerator.makeInitialState(initial_states); | 27 | State parent = factory.newState(); |
770 | 31 | for (auto &state : initial_states) { | 28 | for (auto &state : initial_states) { |
771 | 32 | seen.add(state); | 29 | auto res = seen.add(state); |
772 | 30 | if (res.first) { | ||
773 | 33 | push(state); | 31 | push(state); |
774 | 34 | } | 32 | } |
798 | 35 | } | 33 | while (!dstack.empty() && !violation) { |
799 | 36 | State working = factory.newState(); | 34 | DEntry &dtop = dstack.top(); |
800 | 37 | while (!dstack.empty() && !violation) { | 35 | if (!nexttrans(working, parent, dtop)) { |
801 | 38 | DStack &dtop = dstack.top(); | 36 | pop(); |
802 | 39 | if (!nexttrans(working, dtop)) { | 37 | continue; |
803 | 40 | pop(); | 38 | } |
804 | 41 | continue; | 39 | idx_t stateid = seen.add(working).second; |
805 | 42 | } | 40 | dtop.sucinfo.last_state = stateid; |
806 | 43 | // get ID of transition taken (nexttrans = lasttrans + 1) | 41 | |
807 | 44 | idx_t stateid = (*dtop.neighbors)[dtop.nexttrans - 1]; | 42 | // lookup successor in 'hash' table |
808 | 45 | 43 | auto p = chash[hash(stateid)]; | |
809 | 46 | // lookup successor in 'hash' table | 44 | while (p != std::numeric_limits<idx_t>::max() && cstack[p].stateid != stateid) { |
810 | 47 | auto p = chash[hash(stateid)]; | 45 | p = cstack[p].next; |
811 | 48 | while (p != std::numeric_limits<idx_t>::max() && cstack[p].stateid != stateid) { | 46 | } |
812 | 49 | p = cstack[p].next; | 47 | if (p != std::numeric_limits<idx_t>::max()) { |
813 | 50 | } | 48 | // we found the successor, i.e. there's a loop! |
814 | 51 | if (p != std::numeric_limits<idx_t>::max()) { | 49 | // now update lowlinks and check whether the loop contains an accepting state |
815 | 52 | // we found the successor! update lowlinks etc | 50 | update(p); |
816 | 53 | update(p); | 51 | continue; |
817 | 54 | continue; | 52 | } |
818 | 55 | } | 53 | if (store.find(stateid) == std::end(store)) { |
819 | 56 | if (store.find(stateid) == std::end(store)) { | 54 | push(working); |
820 | 57 | push(working); | 55 | } |
821 | 56 | } | ||
822 | 57 | if constexpr (SaveTrace) { | ||
823 | 58 | if (violation) { | ||
824 | 59 | State next = factory.newState(); | ||
825 | 60 | std::cerr << "Printing trace: " << std::endl; | ||
826 | 61 | std::vector<DEntry> rev; | ||
827 | 62 | auto sz = dstack.size(); | ||
828 | 63 | // dump stack to vector to allow iteration | ||
829 | 64 | for (int i = 0; i < sz; ++i) { | ||
830 | 65 | rev.push_back(dstack.top()); | ||
831 | 66 | dstack.pop(); | ||
832 | 67 | } | ||
833 | 68 | idx_t pos = 0; | ||
834 | 69 | // print dstack in-order. rev[0] is dstack.top(), so loop vector in reverse | ||
835 | 70 | for (int i = rev.size() - 1; i >= 0; --i) { | ||
836 | 71 | pos = rev[i].pos; | ||
837 | 72 | seen.decode(parent, cstack[pos].stateid); | ||
838 | 73 | _dump_state(parent); | ||
839 | 74 | cstack[pos].lowlink = std::numeric_limits<idx_t>::max(); | ||
840 | 75 | if (i > 0) { | ||
841 | 76 | // print transition to next state | ||
842 | 77 | seen.decode(next, cstack[rev[i - 1].pos].stateid); | ||
843 | 78 | successorGenerator->prepare(&parent); | ||
844 | 79 | while (successorGenerator->next(working)) { | ||
845 | 80 | if (working == next) { | ||
846 | 81 | std::cerr << net.transitionNames()[successorGenerator->last_transition()] | ||
847 | 82 | << std::endl; | ||
848 | 83 | break; | ||
849 | 84 | } | ||
850 | 85 | } | ||
851 | 86 | } | ||
852 | 87 | } | ||
853 | 88 | |||
854 | 89 | // follow lowsource until back in dstack | ||
855 | 90 | pos = cstack[pos].lowsource; | ||
856 | 91 | if (cstack[pos].lowlink != std::numeric_limits<idx_t>::max()) { | ||
857 | 92 | std::cerr << "Printing looping part\n"; | ||
858 | 93 | } | ||
859 | 94 | while (cstack[pos].lowlink != std::numeric_limits<idx_t>::max()) { | ||
860 | 95 | seen.decode(parent, cstack[pos].stateid); | ||
861 | 96 | _dump_state(parent); | ||
862 | 97 | pos = cstack[pos].lowsource; | ||
863 | 98 | } | ||
864 | 99 | } | ||
865 | 58 | } | 100 | } |
866 | 59 | } | 101 | } |
867 | 60 | return !violation; | 102 | return !violation; |
868 | 61 | } | 103 | } |
869 | 62 | 104 | ||
871 | 63 | void TarjanModelChecker::push(State &state) { | 105 | /** |
872 | 106 | * Push a state to the various stacks. | ||
873 | 107 | * @param state | ||
874 | 108 | */ | ||
875 | 109 | template<bool SaveTrace> | ||
876 | 110 | void TarjanModelChecker<SaveTrace>::push(State &state) { | ||
877 | 64 | const auto res = seen.add(state); | 111 | const auto res = seen.add(state); |
878 | 65 | const auto ctop = static_cast<idx_t>(cstack.size()); | 112 | const auto ctop = static_cast<idx_t>(cstack.size()); |
879 | 66 | const auto h = hash(res.second); | 113 | const auto h = hash(res.second); |
880 | 67 | cstack.emplace_back(ctop, res.second, chash[h]); | 114 | cstack.emplace_back(ctop, res.second, chash[h]); |
881 | 115 | if constexpr (SaveTrace) { | ||
882 | 116 | cstack.back().lowsource = ctop; | ||
883 | 117 | } | ||
884 | 68 | chash[h] = ctop; | 118 | chash[h] = ctop; |
887 | 69 | dstack.push({ctop}); | 119 | dstack.push(DEntry{ctop, initial_suc_info}); |
888 | 70 | if (successorGenerator.isAccepting(state)) { | 120 | if (successorGenerator->isAccepting(state)) { |
889 | 71 | astack.push(ctop); | 121 | astack.push(ctop); |
890 | 72 | } | 122 | } |
891 | 73 | } | 123 | } |
892 | 74 | 124 | ||
894 | 75 | void TarjanModelChecker::pop() { | 125 | template<bool SaveTrace> |
895 | 126 | void TarjanModelChecker<SaveTrace>::pop() { | ||
896 | 76 | const size_t p = dstack.top().pos; | 127 | const size_t p = dstack.top().pos; |
897 | 77 | dstack.pop(); | 128 | dstack.pop(); |
898 | 78 | if (cstack[p].lowlink == p) { | 129 | if (cstack[p].lowlink == p) { |
899 | @@ -91,42 +142,45 @@ | |||
900 | 91 | } | 142 | } |
901 | 92 | } | 143 | } |
902 | 93 | 144 | ||
904 | 94 | void TarjanModelChecker::update(idx_t to) { | 145 | template<bool SaveTrace> |
905 | 146 | void TarjanModelChecker<SaveTrace>::update(idx_t to) { | ||
906 | 95 | const auto from = dstack.top().pos; | 147 | const auto from = dstack.top().pos; |
907 | 96 | if (cstack[to].lowlink <= cstack[from].lowlink) { | 148 | if (cstack[to].lowlink <= cstack[from].lowlink) { |
908 | 149 | // we have found a loop into earlier seen component cstack[to].lowlink. | ||
909 | 150 | // if this earlier component was found before an accepting state, | ||
910 | 151 | // we have found an accepting loop and thus a violation. | ||
911 | 97 | violation = (!astack.empty() && to <= astack.top()); | 152 | violation = (!astack.empty() && to <= astack.top()); |
912 | 98 | cstack[from].lowlink = cstack[to].lowlink; | 153 | cstack[from].lowlink = cstack[to].lowlink; |
913 | 154 | if constexpr (SaveTrace) { | ||
914 | 155 | cstack[from].lowsource = to; | ||
915 | 156 | } | ||
916 | 99 | } | 157 | } |
917 | 100 | } | 158 | } |
918 | 101 | 159 | ||
929 | 102 | bool TarjanModelChecker::nexttrans(State &state, TarjanModelChecker::DStack &delem) { | 160 | template<bool SaveTrace> |
930 | 103 | if (!delem.neighbors) { | 161 | bool TarjanModelChecker<SaveTrace>::nexttrans(State &state, State &parent, TarjanModelChecker::DEntry &delem) { |
931 | 104 | delem.neighbors = std::vector<idx_t>(); | 162 | seen.decode(parent, cstack[delem.pos].stateid); |
922 | 105 | delem.nexttrans = 0; | ||
923 | 106 | State src = factory.newState(); | ||
924 | 107 | State dst = factory.newState(); | ||
925 | 108 | seen.decode(src, cstack[delem.pos].stateid); | ||
926 | 109 | successorGenerator.prepare(&src); | ||
927 | 110 | while (successorGenerator.next(dst)) { | ||
928 | 111 | auto res = seen.add(dst); | ||
932 | 112 | #ifdef PRINTF_DEBUG | 163 | #ifdef PRINTF_DEBUG |
935 | 113 | std::cerr << "adding state\n"; | 164 | std::cerr << "loaded parent\n "; |
936 | 114 | _dump_state(dst); | 165 | _dump_state(parent); |
937 | 115 | #endif | 166 | #endif |
940 | 116 | delem.neighbors->push_back(res.second); | 167 | successorGenerator->prepare(&parent, delem.sucinfo); |
941 | 117 | } | 168 | if (delem.sucinfo.has_prev_state()) { |
942 | 169 | seen.decode(state, delem.sucinfo.last_state); | ||
943 | 118 | } | 170 | } |
948 | 119 | if (delem.nexttrans == delem.neighbors->size()) { | 171 | auto res = successorGenerator->next(state, delem.sucinfo); |
945 | 120 | return false; | ||
946 | 121 | } else { | ||
947 | 122 | seen.decode(state, (*delem.neighbors)[delem.nexttrans]); | ||
949 | 123 | #ifdef PRINTF_DEBUG | 172 | #ifdef PRINTF_DEBUG |
951 | 124 | std::cerr << "loaded state\n"; | 173 | if (res) { |
952 | 174 | std::cerr << "going to state\n"; | ||
953 | 125 | _dump_state(state); | 175 | _dump_state(state); |
954 | 176 | } | ||
955 | 126 | #endif | 177 | #endif |
959 | 127 | delem.nexttrans++; | 178 | return res; |
957 | 128 | return true; | ||
958 | 129 | } | ||
960 | 130 | } | 179 | } |
961 | 131 | 180 | ||
962 | 181 | template | ||
963 | 182 | class TarjanModelChecker<true>; | ||
964 | 183 | |||
965 | 184 | template | ||
966 | 185 | class TarjanModelChecker<false>; | ||
967 | 132 | } | 186 | } |
968 | 133 | \ No newline at end of file | 187 | \ No newline at end of file |
969 | 134 | 188 | ||
970 | === modified file 'src/LTLMain.cpp' | |||
971 | --- src/LTLMain.cpp 2020-10-16 11:40:41 +0000 | |||
972 | +++ src/LTLMain.cpp 2020-11-09 13:59:57 +0000 | |||
973 | @@ -32,10 +32,8 @@ | |||
974 | 32 | 32 | ||
975 | 33 | #include "CTL/CTLEngine.h" | 33 | #include "CTL/CTLEngine.h" |
976 | 34 | #include "PetriEngine/PQL/Expressions.h" | 34 | #include "PetriEngine/PQL/Expressions.h" |
977 | 35 | #include "LTL/LTLToBuchi.h" | ||
978 | 36 | #include "LTL/LTLValidator.h" | 35 | #include "LTL/LTLValidator.h" |
979 | 37 | #include "LTL/LTL_algorithm/NestedDepthFirstSearch.h" | 36 | #include "LTL/LTL_algorithm/NestedDepthFirstSearch.h" |
980 | 38 | #include "LTL/LTL_algorithm/ProductPrinter.h" | ||
981 | 39 | #include "LTL/LTL_algorithm/TarjanModelChecker.h" | 37 | #include "LTL/LTL_algorithm/TarjanModelChecker.h" |
982 | 40 | #include "LTL/LTL.h" | 38 | #include "LTL/LTL.h" |
983 | 41 | 39 | ||
984 | @@ -43,7 +41,6 @@ | |||
985 | 43 | using namespace PetriEngine::PQL; | 41 | using namespace PetriEngine::PQL; |
986 | 44 | using namespace PetriEngine::Reachability; | 42 | using namespace PetriEngine::Reachability; |
987 | 45 | 43 | ||
988 | 46 | |||
989 | 47 | std::vector<std::string> explode(std::string const & s) | 44 | std::vector<std::string> explode(std::string const & s) |
990 | 48 | { | 45 | { |
991 | 49 | std::vector<std::string> result; | 46 | std::vector<std::string> result; |
992 | @@ -502,7 +499,10 @@ | |||
993 | 502 | modelChecker = std::make_unique<LTL::NestedDepthFirstSearch>(*net, negated_formula); | 499 | modelChecker = std::make_unique<LTL::NestedDepthFirstSearch>(*net, negated_formula); |
994 | 503 | break; | 500 | break; |
995 | 504 | case LTL::Algorithm::Tarjan: | 501 | case LTL::Algorithm::Tarjan: |
997 | 505 | modelChecker = std::make_unique<LTL::TarjanModelChecker>(*net, negated_formula); | 502 | if (options.trace) |
998 | 503 | modelChecker = std::make_unique<LTL::TarjanModelChecker<true>>(*net, negated_formula); | ||
999 | 504 | else | ||
1000 | 505 | modelChecker = std::make_unique<LTL::TarjanModelChecker<false>>(*net, negated_formula); | ||
1001 | 506 | break; | 506 | break; |
1002 | 507 | } | 507 | } |
1003 | 508 | 508 | ||
1004 | 509 | 509 | ||
1005 | === modified file 'src/PetriEngine/SuccessorGenerator.cpp' | |||
1006 | --- src/PetriEngine/SuccessorGenerator.cpp 2020-10-16 13:38:03 +0000 | |||
1007 | +++ src/PetriEngine/SuccessorGenerator.cpp 2020-11-09 13:59:57 +0000 | |||
1008 | @@ -97,7 +97,7 @@ | |||
1009 | 97 | for (; _suc_tcounter != last; ++_suc_tcounter) { | 97 | for (; _suc_tcounter != last; ++_suc_tcounter) { |
1010 | 98 | 98 | ||
1011 | 99 | if (!checkPreset(_suc_tcounter)) continue; | 99 | if (!checkPreset(_suc_tcounter)) continue; |
1013 | 100 | #ifdef PRINTF_DEBUG | 100 | #ifdef _PRINTF_DEBUG |
1014 | 101 | std::cerr << "trace: " << _net.transitionNames()[_suc_tcounter] << std::endl; | 101 | std::cerr << "trace: " << _net.transitionNames()[_suc_tcounter] << std::endl; |
1015 | 102 | #endif | 102 | #endif |
1016 | 103 | memcpy(write.marking(), (*_parent).marking(), _net._nplaces * sizeof (MarkVal)); | 103 | memcpy(write.marking(), (*_parent).marking(), _net._nplaces * sizeof (MarkVal)); |