Merge lp:~peter-gjoel/verifydtapn/PTrieWorkflow into lp:verifydtapn
- PTrieWorkflow
- Merge into trunk
Status: | Merged |
---|---|
Approved by: | Jiri Srba |
Approved revision: | 364 |
Merged at revision: | 333 |
Proposed branch: | lp:~peter-gjoel/verifydtapn/PTrieWorkflow |
Merge into: | lp:verifydtapn |
Prerequisite: | lp:~peter-gjoel/verifydtapn/WorkflowRefactor |
Diff against target: |
1810 lines (+1104/-120) 15 files modified
makefile.linux64 (+2/-2) src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.cpp (+190/-0) src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.h (+57/-0) src/DiscreteVerification/DataStructures/MarkingEncoder.h (+31/-9) src/DiscreteVerification/DataStructures/NonStrictMarking.hpp (+12/-0) src/DiscreteVerification/DataStructures/WorkflowPWList.cpp (+130/-10) src/DiscreteVerification/DataStructures/WorkflowPWList.hpp (+23/-0) src/DiscreteVerification/DataStructures/binarywrapper.h (+168/-56) src/DiscreteVerification/DataStructures/ptrie.h (+158/-12) src/DiscreteVerification/DataStructures/visitor.h (+30/-0) src/DiscreteVerification/DiscreteVerification.cpp (+44/-23) src/DiscreteVerification/VerificationTypes/WorkflowSoundness.cpp (+109/-4) src/DiscreteVerification/VerificationTypes/WorkflowSoundness.hpp (+18/-0) src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.cpp (+112/-4) src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.hpp (+20/-0) |
To merge this branch: | bzr merge lp:~peter-gjoel/verifydtapn/PTrieWorkflow |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Jiri Srba | Approve | ||
Jakob Taankvist | Pending | ||
Mathias Grund Sørensen | Pending | ||
Review via email: mp+262676@code.launchpad.net |
Commit message
Description of the change
Implementation of ptries for workflow verification.
- 358. By Peter Gjøl Jensen
-
merged with trunk
Peter Gjøl Jensen (peter-gjoel) wrote : | # |
Fixed.
Jiri Srba (srba) wrote : | # |
Thanks. I am still getting some warnings:
In file included from src/DiscreteVer
src/DiscreteVer
is uninitialized when used within its own initialization [-Wuninitialized]
src/DiscreteVer
instantiation of member function
'
requested here
In file included from src/DiscreteVer
src/DiscreteVer
private field 'last' is not used [-Wunused-
2 warnings generated.
- 359. By Peter Gjøl Jensen
-
fixed warnings
- 360. By Peter Gjøl Jensen
-
fixed covered marking visitor
- 361. By Peter Gjøl Jensen
-
readded limit on cover-check
- 362. By Peter Gjøl Jensen
-
fixed problem with ptries and unbounded markings
- 363. By Peter Gjøl Jensen
-
merged with trunk
- 364. By Peter Gjøl Jensen
-
changed comparison function for ptries, simplifying code and giving a speedup on VERY large markings
Peter Gjøl Jensen (peter-gjoel) wrote : | # |
Minor re-factoring, improving on code-quality and possibly giving speedup on very large markings (several hundreds of tokens).
Jiri Srba (srba) wrote : | # |
Extensively tested and it works flawlessly on all my examples.
Preview Diff
1 | === modified file 'makefile.linux64' |
2 | --- makefile.linux64 2015-06-17 10:05:28 +0000 |
3 | +++ makefile.linux64 2015-08-20 13:27:24 +0000 |
4 | @@ -8,9 +8,9 @@ |
5 | CUT = cut |
6 | |
7 | # Compiler and linker flags |
8 | -CFLAGS = -fpermissive -DBOOST_DISABLE_THREADS -DNDEBUG -DDISABLE_ASSERTX -static -O3 -Wall -mtune=core2 |
9 | +CFLAGS = -DBOOST_DISABLE_THREADS -DNDEBUG -DDISABLE_ASSERTX -static -O3 -Wall -mtune=core2 |
10 | |
11 | -LDFLAGS = -fpermissive -DBOOST_DISABLE_THREADS -DNDEBUG -DDISABLE_ASSERTX -static -O3 -Wall -mtune=core2 |
12 | +LDFLAGS = -DBOOST_DISABLE_THREADS -DNDEBUG -DDISABLE_ASSERTX -static -O3 -Wall -mtune=core2 |
13 | |
14 | # Input files |
15 | SOURCES = $(shell find * -name "*.cpp") |
16 | |
17 | === added file 'src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.cpp' |
18 | --- src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.cpp 1970-01-01 00:00:00 +0000 |
19 | +++ src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.cpp 2015-08-20 13:27:24 +0000 |
20 | @@ -0,0 +1,190 @@ |
21 | +/* |
22 | + * File: CoveredMarkingVisitor.cpp |
23 | + * Author: Peter G. Jensen |
24 | + * |
25 | + * Created on 18 June 2015, 14:23 |
26 | + */ |
27 | + |
28 | +#include "CoveredMarkingVisitor.h" |
29 | + |
30 | + |
31 | +using namespace ptrie; |
32 | +namespace VerifyTAPN { |
33 | +namespace DiscreteVerification { |
34 | + |
35 | + CoveredMarkingVisitor::CoveredMarkingVisitor( |
36 | + MarkingEncoder<MetaData*, NonStrictMarking>& enc) |
37 | + : encoder(enc), scratchpad(0) |
38 | + { |
39 | + |
40 | + } |
41 | + |
42 | + |
43 | + CoveredMarkingVisitor::~CoveredMarkingVisitor() |
44 | + { |
45 | + scratchpad.release(); |
46 | + } |
47 | + |
48 | + void CoveredMarkingVisitor::set_target(NonStrictMarking* m, ptriepointer_t<MetaData*> me) |
49 | + { |
50 | + target = m; |
51 | + _found=false; |
52 | + _targetencoding = me; |
53 | + |
54 | + if(encoder.scratchpad.size() > scratchpad.size()) |
55 | + { |
56 | + scratchpad.release(); |
57 | + scratchpad = encoder.scratchpad.clone(); |
58 | + } |
59 | + } |
60 | + |
61 | + bool CoveredMarkingVisitor::set(int index, bool value) |
62 | + { |
63 | + if(_found) return true; // end |
64 | + scratchpad.set(index, value); |
65 | + // If we have enough bits to constitute a single token (with placement) |
66 | + if((index + 1) % encoder.offsetBitSize == 0 && index > 0) |
67 | + { |
68 | + size_t begin = (index / encoder.offsetBitSize) * encoder.offsetBitSize; |
69 | + unsigned long long data = 0; |
70 | + uint count = 0; |
71 | + uint cbit = index; |
72 | + |
73 | + while (cbit >= begin + encoder.countBitSize) { |
74 | + data = data << 1; |
75 | + if(scratchpad.at(cbit)) |
76 | + { |
77 | + data |= 1; |
78 | + } |
79 | + --cbit; |
80 | + } |
81 | + |
82 | + while(cbit >= begin) |
83 | + { |
84 | + count = count << 1; |
85 | + if(scratchpad.at(cbit)) |
86 | + { |
87 | + count |= 1; |
88 | + } |
89 | + if(cbit == 0) break; |
90 | + cbit--; |
91 | + } |
92 | + |
93 | + if (count) { |
94 | + return !target_contains_token(data, count); |
95 | + } |
96 | + // should not really happen |
97 | + assert(false); |
98 | + return true; // skip if happens! |
99 | + } |
100 | + else |
101 | + { |
102 | + return false; // not enough info |
103 | + } |
104 | + } |
105 | + |
106 | + bool CoveredMarkingVisitor::set_remainder(int index, |
107 | + ptriepointer_t<MetaData*> pointer) |
108 | + { |
109 | + // special case, marking cannot cover itself |
110 | + if(pointer.index == _targetencoding.index) return false; |
111 | + if(_found) return true; // end |
112 | + |
113 | + encoding_t remainder = pointer.remainder(); |
114 | + uint offset = index - (index % 8); // offset matches on a byte |
115 | + uint begin = (index / encoder.offsetBitSize ) * encoder.offsetBitSize; // start from whole token |
116 | + // check inclusion |
117 | + |
118 | + bool bit; |
119 | + |
120 | + while(true) |
121 | + { |
122 | + uint cbit = begin; |
123 | + unsigned long long data = 0; |
124 | + uint count = 0; |
125 | + cbit += encoder.offsetBitSize - 1; |
126 | + // unpack place/age/count |
127 | + while (cbit >= begin + encoder.countBitSize) { |
128 | + data = data << 1; |
129 | + |
130 | + if(cbit < offset) bit = scratchpad.at(cbit); |
131 | + else bit = remainder.at(cbit - offset); |
132 | + |
133 | + if(bit) |
134 | + { |
135 | + data |= 1; |
136 | + } |
137 | + --cbit; |
138 | + } |
139 | + |
140 | + while(cbit >= begin) |
141 | + { |
142 | + count = count << 1; |
143 | + |
144 | + if(cbit < offset) bit = scratchpad.at(cbit); |
145 | + else bit = remainder.at(cbit - offset); |
146 | + |
147 | + if(bit) |
148 | + { |
149 | + count |= 1; |
150 | + } |
151 | + if(cbit == 0) break; |
152 | + cbit--; |
153 | + } |
154 | + begin += encoder.offsetBitSize; |
155 | + if (count) |
156 | + { |
157 | + if(!target_contains_token(data, count)) |
158 | + { |
159 | + return false; |
160 | + } |
161 | + } |
162 | + else |
163 | + { |
164 | + break; |
165 | + } |
166 | + } |
167 | + |
168 | + match = pointer; |
169 | + _found = true; |
170 | + return true; |
171 | + } |
172 | + |
173 | + bool CoveredMarkingVisitor::back(int index) |
174 | + { |
175 | + return false; |
176 | + } |
177 | + |
178 | + bool CoveredMarkingVisitor::target_contains_token(unsigned long long placeage, uint count) |
179 | + { |
180 | + if(count == 0) return true; |
181 | + |
182 | + int age = floor(placeage / encoder.numberOfPlaces); |
183 | + int place = (placeage % encoder.numberOfPlaces); |
184 | + int cnt = count; |
185 | + const TokenList& tokens = target->getTokenList(place); |
186 | + |
187 | + |
188 | + for( TokenList::const_iterator it = tokens.begin(); |
189 | + it != tokens.end(); ++it) |
190 | + { |
191 | + if(it->getAge() == age) |
192 | + { |
193 | + if(it->getCount() >= cnt) return true; // continue |
194 | + else return false; // skip branch |
195 | + } |
196 | + else if(it->getAge() > age) return false; // skip branch |
197 | + } |
198 | + |
199 | + return false; // skip branch |
200 | + } |
201 | + |
202 | + NonStrictMarking* CoveredMarkingVisitor::decode() |
203 | + { |
204 | + NonStrictMarking* m = encoder.decode(match); |
205 | + m->meta = match.get_meta(); |
206 | + return m; |
207 | + } |
208 | + |
209 | +} |
210 | +} |
211 | \ No newline at end of file |
212 | |
213 | === added file 'src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.h' |
214 | --- src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.h 1970-01-01 00:00:00 +0000 |
215 | +++ src/DiscreteVerification/DataStructures/CoveredMarkingVisitor.h 2015-08-20 13:27:24 +0000 |
216 | @@ -0,0 +1,57 @@ |
217 | +/* |
218 | + * File: CoveredMarkingVisitor.h |
219 | + * Author: Peter G. Jensen |
220 | + * |
221 | + * Created on 17 June 2015, 00:04 |
222 | + */ |
223 | + |
224 | +#ifndef COVEREDMARKINGVISITOR_H |
225 | +#define COVEREDMARKINGVISITOR_H |
226 | + |
227 | +#include "binarywrapper.h" |
228 | +#include <limits> |
229 | +#include <vector> |
230 | +#include "ptrie.h" |
231 | +#include "visitor.h" |
232 | +#include "MarkingEncoder.h" |
233 | +#include "NonStrictMarkingBase.hpp" |
234 | +#include "NonStrictMarking.hpp" |
235 | + |
236 | + |
237 | +using namespace ptrie; |
238 | +namespace VerifyTAPN { |
239 | +namespace DiscreteVerification { |
240 | + |
241 | + class CoveredMarkingVisitor |
242 | + : public visitor_t<MetaData*> |
243 | + { |
244 | + typedef binarywrapper_t<MetaData*> encoding_t; |
245 | + private: |
246 | + MarkingEncoder<MetaData*, NonStrictMarking>& encoder; |
247 | + NonStrictMarking* target; |
248 | + encoding_t scratchpad; |
249 | + ptriepointer_t<MetaData*> match; |
250 | + bool _found; |
251 | + ptriepointer_t<MetaData*> _targetencoding; |
252 | + |
253 | + private: |
254 | + bool target_contains_token(unsigned long long placeage, uint count); |
255 | + |
256 | + public: |
257 | + CoveredMarkingVisitor( |
258 | + MarkingEncoder<MetaData*, NonStrictMarking>& enc); |
259 | + ~CoveredMarkingVisitor(); |
260 | + virtual bool back(int index); |
261 | + virtual bool set(int index, bool value); |
262 | + virtual bool set_remainder(int index, |
263 | + ptriepointer_t<MetaData*> pointer); |
264 | + void set_target(NonStrictMarking* m, ptriepointer_t<MetaData*> me); |
265 | + NonStrictMarking* decode(); |
266 | + bool found(){return _found;} |
267 | + }; |
268 | + |
269 | +} |
270 | +} |
271 | + |
272 | +#endif /* BINARYMARKINGVISITOR_H */ |
273 | + |
274 | |
275 | === modified file 'src/DiscreteVerification/DataStructures/MarkingEncoder.h' |
276 | --- src/DiscreteVerification/DataStructures/MarkingEncoder.h 2015-06-22 21:03:26 +0000 |
277 | +++ src/DiscreteVerification/DataStructures/MarkingEncoder.h 2015-08-20 13:27:24 +0000 |
278 | @@ -20,9 +20,12 @@ |
279 | namespace VerifyTAPN { |
280 | namespace DiscreteVerification { |
281 | |
282 | + class CoveredMarkingVisitor; |
283 | + |
284 | template<typename T, typename M = NonStrictMarkingBase> |
285 | class MarkingEncoder |
286 | { |
287 | + friend class CoveredMarkingVisitor; |
288 | typedef binarywrapper_t<T> encoding_t; |
289 | |
290 | private: |
291 | @@ -32,10 +35,9 @@ |
292 | const uint countBitSize; |
293 | const uint placeAgeBitSize; |
294 | const uint offsetBitSize; |
295 | - uint markingBitSize; |
296 | + const uint markingBitSize; |
297 | TAPN::TimedArcPetriNet& tapn; |
298 | encoding_t scratchpad; |
299 | - void* raw; |
300 | public: |
301 | MarkingEncoder(TAPN::TimedArcPetriNet& tapn, int knumber, |
302 | int nplaces, int mage); |
303 | @@ -58,8 +60,7 @@ |
304 | markingBitSize(offsetBitSize * (knumber ? knumber : 1)), |
305 | tapn(tapn) |
306 | { |
307 | - scratchpad = encoding_t(markingBitSize); |
308 | - raw = (void*)scratchpad.raw(); |
309 | + scratchpad = encoding_t(0); |
310 | } |
311 | |
312 | template<typename T, typename M> |
313 | @@ -71,7 +72,10 @@ |
314 | template<typename T, typename M> |
315 | M* MarkingEncoder<T, M>::decode(const ptriepointer_t<T>& pointer) |
316 | { |
317 | - assert(scratchpad.raw() == raw); |
318 | + // we allready know here that the scratchpad is large enough, |
319 | + // it is monotonically increased when we encode, ie; no marking |
320 | + // taking up more bits are currently in the ptrie. |
321 | + |
322 | M* m = new M(); |
323 | assert(pointer.container->consistent()); |
324 | const encoding_t remainder = pointer.remainder(); |
325 | @@ -81,12 +85,13 @@ |
326 | |
327 | uint cbit = 0; |
328 | // foreach token |
329 | - uint data = 0; |
330 | - uint count = 0; |
331 | + |
332 | bool bit; |
333 | for (uint i = 0; i < maxNumberOfTokens; i++) { |
334 | uint offset = offsetBitSize * i; |
335 | cbit = offset + offsetBitSize - 1; |
336 | + unsigned long long data = 0; |
337 | + uint count = 0; |
338 | |
339 | while (cbit >= offset + countBitSize) { |
340 | data = data << 1; |
341 | @@ -137,8 +142,6 @@ |
342 | uint place = (data % this->numberOfPlaces); |
343 | Token t = Token(age, count); |
344 | m->addTokenInPlace(tapn.getPlace(place), t); |
345 | - data = 0; |
346 | - count = 0; |
347 | } |
348 | else |
349 | { |
350 | @@ -157,6 +160,25 @@ |
351 | template<typename T, typename M> |
352 | binarywrapper_t<T> MarkingEncoder<T, M>::encode(M* marking) |
353 | { |
354 | + // make sure we have space to encode marking |
355 | + size_t count = 0; |
356 | + for (vector<Place>::const_iterator pi = marking->getPlaceList().begin(); |
357 | + pi != marking->getPlaceList().end(); |
358 | + pi++) { |
359 | + count += pi->tokens.size(); |
360 | + } |
361 | + count *= offsetBitSize; |
362 | + count /= 8; |
363 | + count += 1; |
364 | + |
365 | + if(scratchpad.size() < count) |
366 | + { |
367 | + scratchpad.release(); |
368 | + scratchpad = encoding_t(count * 8); |
369 | + } |
370 | + |
371 | + |
372 | + |
373 | scratchpad.zero(); |
374 | int tc = 0; |
375 | uint bitcount = 0; |
376 | |
377 | === modified file 'src/DiscreteVerification/DataStructures/NonStrictMarking.hpp' |
378 | --- src/DiscreteVerification/DataStructures/NonStrictMarking.hpp 2015-06-22 21:03:26 +0000 |
379 | +++ src/DiscreteVerification/DataStructures/NonStrictMarking.hpp 2015-08-20 13:27:24 +0000 |
380 | @@ -48,6 +48,18 @@ |
381 | MetaDataWithTraceAndEncoding* parent; |
382 | }; |
383 | |
384 | + struct WorkflowSoundnessMetaDataWithEncoding : public MetaDataWithTraceAndEncoding { |
385 | + public: |
386 | + WorkflowSoundnessMetaDataWithEncoding() : MetaDataWithTraceAndEncoding(), parents() |
387 | + { totalDelay = INT_MAX;}; |
388 | + virtual ~WorkflowSoundnessMetaDataWithEncoding() |
389 | + { |
390 | + parents.clear(); |
391 | + } |
392 | + |
393 | + vector<MetaData*> parents; |
394 | + }; |
395 | + |
396 | class NonStrictMarking : public NonStrictMarkingBase{ |
397 | public: |
398 | NonStrictMarking():NonStrictMarkingBase(), meta(NULL){} |
399 | |
400 | === modified file 'src/DiscreteVerification/DataStructures/WorkflowPWList.cpp' |
401 | --- src/DiscreteVerification/DataStructures/WorkflowPWList.cpp 2015-06-22 22:10:16 +0000 |
402 | +++ src/DiscreteVerification/DataStructures/WorkflowPWList.cpp 2015-08-20 13:27:24 +0000 |
403 | @@ -88,7 +88,8 @@ |
404 | } |
405 | |
406 | bool isFirst = true; |
407 | - for (vector<NonStrictMarking*>::iterator iter = coveredMarkings.begin(); iter != coveredMarkings.end(); ++iter) { |
408 | + for (vector<NonStrictMarking*>::iterator iter = coveredMarkings.begin(); |
409 | + iter != coveredMarkings.end(); ++iter) { |
410 | if (isFirst) { |
411 | isFirst = false; |
412 | continue; |
413 | @@ -96,22 +97,15 @@ |
414 | NonStrictMarking* covered = lookup(*iter); |
415 | if (covered != NULL) { |
416 | // cleanup |
417 | - for (vector<NonStrictMarking*>::iterator del = coveredMarkings.begin(); |
418 | - del != coveredMarkings.end(); ++del) |
419 | + for (;iter != coveredMarkings.end(); ++iter) |
420 | { |
421 | - delete *del; |
422 | + delete *iter; |
423 | } |
424 | return covered; |
425 | } |
426 | delete *iter; |
427 | } |
428 | |
429 | - // Cleanup |
430 | - for (vector<NonStrictMarking*>::iterator del = coveredMarkings.begin(); |
431 | - del != coveredMarkings.end(); ++del) |
432 | - { |
433 | - delete *del; |
434 | - } |
435 | } |
436 | return NULL; |
437 | } |
438 | @@ -163,6 +157,132 @@ |
439 | } |
440 | |
441 | |
442 | + WorkflowPWListHybrid::WorkflowPWListHybrid( |
443 | + TAPN::TimedArcPetriNet& tapn, |
444 | + WaitingList<ptriepointer_t<MetaData*> >* w_l, |
445 | + int knumber, |
446 | + int nplaces, |
447 | + int mage) |
448 | + : PWListHybrid(tapn, w_l, knumber, nplaces, mage, false, true), |
449 | + visitor(encoder) |
450 | + { |
451 | + |
452 | + } |
453 | + |
454 | + WorkflowPWListHybrid::~WorkflowPWListHybrid() |
455 | + { |
456 | + ptriepointer_t<MetaData*> begin = passed.begin(); |
457 | + while(begin != passed.end()) |
458 | + { |
459 | + delete begin.get_meta(); |
460 | + ++ begin; |
461 | + } |
462 | + } |
463 | + |
464 | + NonStrictMarking* WorkflowPWListHybrid::getCoveredMarking |
465 | + (NonStrictMarking* marking, bool useLinearSweep) |
466 | + { |
467 | + visitor.set_target(marking, last_pointer); |
468 | + passed.visit(visitor); |
469 | + if(visitor.found()) |
470 | + { |
471 | + NonStrictMarking* m = visitor.decode(); |
472 | + return m; |
473 | + } |
474 | + else |
475 | + { |
476 | + return NULL; |
477 | + } |
478 | + } |
479 | + |
480 | + NonStrictMarking* WorkflowPWListHybrid::getUnpassed() |
481 | + { |
482 | + ptriepointer_t<MetaData*> it = passed.last(); |
483 | + for(; it != passed.rend(); --it) |
484 | + { |
485 | + if(!it.get_meta()->passed) |
486 | + { |
487 | + NonStrictMarking* m = encoder.decode(it); |
488 | + m->meta = it.get_meta(); |
489 | + return m; |
490 | + } |
491 | + } |
492 | + return NULL; |
493 | + } |
494 | + |
495 | + bool WorkflowPWListHybrid::add(NonStrictMarking* marking) |
496 | + { |
497 | + discoveredMarkings++; |
498 | + std::pair<bool, ptriepointer_t<MetaData*> > res = |
499 | + passed.insert(encoder.encode(marking)); |
500 | + |
501 | + if (!res.first) { |
502 | + return false; |
503 | + } |
504 | + else |
505 | + { |
506 | + MetaDataWithTraceAndEncoding* meta = |
507 | + new MetaDataWithTraceAndEncoding(); |
508 | + meta->generatedBy = marking->getGeneratedBy(); |
509 | + meta->ep = res.second; |
510 | + meta->parent = parent; |
511 | + meta->totalDelay = marking->calculateTotalDelay(); |
512 | + |
513 | + res.second.set_meta(meta); |
514 | + |
515 | + stored++; |
516 | + |
517 | + // using min first waiting-list, weight is allready in pointer |
518 | + waiting_list->add(NULL, res.second); |
519 | + return true; |
520 | + } |
521 | + } |
522 | + |
523 | + NonStrictMarking* WorkflowPWListHybrid::addToPassed |
524 | + (NonStrictMarking* marking, bool strong) |
525 | + { |
526 | + discoveredMarkings++; |
527 | + std::pair<bool, ptriepointer_t<MetaData*> > res = |
528 | + passed.insert(encoder.encode(marking)); |
529 | + |
530 | + |
531 | + |
532 | + if (!res.first) { |
533 | + NonStrictMarking* old = encoder.decode(res.second); |
534 | + |
535 | + MetaDataWithTraceAndEncoding* meta = |
536 | + (MetaDataWithTraceAndEncoding*)res.second.get_meta(); |
537 | + old->setGeneratedBy(meta->generatedBy); |
538 | + old->meta = meta; |
539 | + last_pointer = res.second; |
540 | + return old; |
541 | + } else { |
542 | + stored++; |
543 | + |
544 | + if(strong) marking->meta = new MetaDataWithTraceAndEncoding(); |
545 | + else marking->meta = new WorkflowSoundnessMetaDataWithEncoding(); |
546 | + |
547 | + MetaDataWithTraceAndEncoding* meta = |
548 | + (MetaDataWithTraceAndEncoding*) marking->meta; |
549 | + meta->ep = res.second; |
550 | + meta->parent = this->parent; |
551 | + meta->generatedBy = marking->getGeneratedBy(); |
552 | + meta->totalDelay = marking->meta->totalDelay; |
553 | + |
554 | + res.second.set_meta(meta); |
555 | + last_pointer = res.second; |
556 | + return NULL; |
557 | + } |
558 | + } |
559 | + |
560 | + void WorkflowPWListHybrid::addLastToWaiting() |
561 | + { |
562 | + // using min first waiting-list, weight is allready in pointer |
563 | + waiting_list->add(NULL, last_pointer); |
564 | + } |
565 | + |
566 | + |
567 | + |
568 | |
569 | } |
570 | } |
571 | |
572 | === modified file 'src/DiscreteVerification/DataStructures/WorkflowPWList.hpp' |
573 | --- src/DiscreteVerification/DataStructures/WorkflowPWList.hpp 2015-06-22 22:10:16 +0000 |
574 | +++ src/DiscreteVerification/DataStructures/WorkflowPWList.hpp 2015-08-20 13:27:24 +0000 |
575 | @@ -15,6 +15,7 @@ |
576 | #include "NonStrictMarking.hpp" |
577 | #include "WaitingList.hpp" |
578 | #include "PWList.hpp" |
579 | +#include "CoveredMarkingVisitor.h" |
580 | |
581 | namespace VerifyTAPN { |
582 | namespace DiscreteVerification { |
583 | @@ -51,6 +52,28 @@ |
584 | } |
585 | |
586 | }; |
587 | + |
588 | + class WorkflowPWListHybrid : public WorkflowPWListBasic, public PWListHybrid { |
589 | + private: |
590 | + CoveredMarkingVisitor visitor; |
591 | + ptriepointer_t<MetaData*> last_pointer; |
592 | + public: |
593 | + WorkflowPWListHybrid(TAPN::TimedArcPetriNet& tapn, |
594 | + WaitingList<ptriepointer_t<MetaData*> >* w_l, |
595 | + int knumber, |
596 | + int nplaces, |
597 | + int mage); |
598 | + ~WorkflowPWListHybrid(); |
599 | + virtual NonStrictMarking* getCoveredMarking(NonStrictMarking* marking, bool useLinearSweep); |
600 | + virtual NonStrictMarking* getUnpassed(); |
601 | + virtual bool add(NonStrictMarking* marking); |
602 | + virtual NonStrictMarking* addToPassed(NonStrictMarking* marking, bool strong); |
603 | + virtual void addLastToWaiting(); |
604 | + virtual void setParent(NonStrictMarking* marking, NonStrictMarking*) |
605 | + { |
606 | + ((MetaDataWithTraceAndEncoding*)marking->meta)->parent = parent; |
607 | + } |
608 | + }; |
609 | |
610 | } /* namespace DiscreteVerification */ |
611 | } /* namespace VerifyTAPN */ |
612 | |
613 | === modified file 'src/DiscreteVerification/DataStructures/binarywrapper.h' |
614 | --- src/DiscreteVerification/DataStructures/binarywrapper.h 2015-06-17 09:03:12 +0000 |
615 | +++ src/DiscreteVerification/DataStructures/binarywrapper.h 2015-08-20 13:27:24 +0000 |
616 | @@ -9,6 +9,8 @@ |
617 | #include <stdio.h> |
618 | #include <iostream> |
619 | #include <string.h> |
620 | +#include <assert.h> |
621 | +#include <stdint.h> |
622 | |
623 | #ifndef BINARYWRAPPER_H |
624 | #define BINARYWRAPPER_H |
625 | @@ -17,44 +19,175 @@ |
626 | typedef unsigned int uint; |
627 | typedef unsigned char uchar; |
628 | |
629 | + /** |
630 | + * Wrapper for binary data. This provides easy access to individual bits, |
631 | + * heap allocation and comparison. Notice that one has to make sure to |
632 | + * explicitly call release() if one wishes to deallocate (possibly shared data). |
633 | + * |
634 | + */ |
635 | template<class T> |
636 | class binarywrapper_t |
637 | { |
638 | public: |
639 | // Constructors |
640 | + /** |
641 | + * Empty constructor, no data is allocated |
642 | + */ |
643 | + inline |
644 | binarywrapper_t(); |
645 | + |
646 | + /** |
647 | + Allocates a room for at least size bits |
648 | + */ |
649 | + inline |
650 | binarywrapper_t(uint size); |
651 | + |
652 | + /** |
653 | + * Constructor for copying over data from latest the offset'th bit. |
654 | + * Detects overflows. |
655 | + * @param other: wrapper to copy from |
656 | + * @param offset: maximal number of bits to skip. |
657 | + */ |
658 | + inline |
659 | binarywrapper_t(const binarywrapper_t& other, uint offset); |
660 | binarywrapper_t(const binarywrapper_t& other, uint size, uint offset, |
661 | uint encodingsize); |
662 | binarywrapper_t(uchar* raw, uint size, uint offset, uint encsize); |
663 | + |
664 | + /** |
665 | + * Assign (not copy) raw data to pointer. Set number of bytes to size |
666 | + * @param raw: some memory to point to |
667 | + * @param size: number of bytes. |
668 | + */ |
669 | + inline |
670 | binarywrapper_t(uchar* raw, uint size); |
671 | |
672 | - // Destructor |
673 | + /** |
674 | + * Empty destructor. Does NOT deallocate data - do this with explicit |
675 | + * call to release(). |
676 | + */ |
677 | + inline |
678 | ~binarywrapper_t(); |
679 | |
680 | - // Copy and clones |
681 | + /** |
682 | + * Makes a complete copy, including new heap-allocation |
683 | + * @return an exact copy, but in a different area of the heap. |
684 | + */ |
685 | + inline |
686 | binarywrapper_t clone() const; |
687 | + |
688 | + /** |
689 | + * Copy over data and meta-data from other, but insert only into target |
690 | + * after offset bits. |
691 | + * Notice that this can cause memory-corruption if there is not enough |
692 | + * room in target, or to many bits are skipped. |
693 | + * @param other: wrapper to copy from |
694 | + * @param offset: bits to skip |
695 | + */ |
696 | + inline |
697 | void copy(const binarywrapper_t& other, uint offset); |
698 | + |
699 | + /** |
700 | + * Copy over size bytes form raw data. Assumes that current wrapper has |
701 | + * enough room. |
702 | + * @param raw: source data |
703 | + * @param size: number of bytes to copy |
704 | + */ |
705 | + inline |
706 | void copy(const uchar* raw, uint size); |
707 | |
708 | // accessors |
709 | + /** |
710 | + * Get value of the place'th bit |
711 | + * @param place: bit index |
712 | + * @return |
713 | + */ |
714 | + inline |
715 | bool at(const uint place) const; |
716 | + |
717 | + /** |
718 | + * number of bytes allocated in heap |
719 | + * @return |
720 | + */ |
721 | + inline |
722 | uint size() const; |
723 | - uchar* raw() const; |
724 | + |
725 | + /** |
726 | + * Raw access to data |
727 | + * @return |
728 | + */ |
729 | + inline |
730 | + uchar*& raw(); |
731 | + |
732 | + /** |
733 | + * Raw access to data when in const setting |
734 | + * @return |
735 | + */ |
736 | + inline |
737 | + uchar* const_raw() const; |
738 | + |
739 | + /** |
740 | + * pretty print of content |
741 | + */ |
742 | + inline |
743 | void print() const; |
744 | + |
745 | + /** |
746 | + * finds the overhead (unused number of bits) when allocating for size |
747 | + * bits. |
748 | + * @param size: number of bits |
749 | + * @return |
750 | + */ |
751 | + inline |
752 | static size_t overhead(uint size); |
753 | |
754 | // modifiers |
755 | + /** |
756 | + * Change value of place'th bit |
757 | + * @param place: index of bit to change |
758 | + * @param value: desired value |
759 | + */ |
760 | + inline |
761 | void set(const uint place, const bool value) const; |
762 | + |
763 | + /** |
764 | + * Sets all memory on heap to 0 |
765 | + */ |
766 | + inline |
767 | void zero() const; |
768 | - void release() const; |
769 | + |
770 | + /** |
771 | + * Deallocates memory stored on heap |
772 | + */ |
773 | + inline |
774 | + void release(); |
775 | + |
776 | void set_meta(T data); |
777 | T get_meta() const; |
778 | + |
779 | + /** |
780 | + * Nice access to single bits |
781 | + * @param i: index to access |
782 | + * @return |
783 | + */ |
784 | + inline |
785 | uchar operator[](int i); |
786 | + |
787 | + /** |
788 | + * Removes a number of bytes from end of heap-allocated data if any is |
789 | + * allocated nothing happens if not. Bound-checks. |
790 | + * @param number of bytes to remove. |
791 | + */ |
792 | + inline |
793 | void pop_front(unsigned short); |
794 | |
795 | - inline int cmp(const binarywrapper_t &other) |
796 | + /** |
797 | + * Compares two wrappers. Assumes that smaller number of bytes also means |
798 | + * a smaller wrapper. Otherwise compares byte by byte. |
799 | + * @param other: wrapper to compare to |
800 | + * @return -1 if other is smaller, 0 if same, 1 if other is larger |
801 | + */ |
802 | + inline int cmp(const binarywrapper_t &other) const |
803 | { |
804 | if(_nbytes != other._nbytes) |
805 | { |
806 | @@ -62,63 +195,33 @@ |
807 | else return 1; |
808 | } |
809 | |
810 | - for(int i = _nbytes - 1; i >= 0; i--) |
811 | - { |
812 | - if(_blob[i] < other._blob[i]) |
813 | - return -1; |
814 | - else if (_blob[i] > other._blob[i]) |
815 | - return 1; |
816 | - } |
817 | + return memcmp(_blob, other.const_raw(), other._nbytes ); |
818 | + } |
819 | |
820 | - return 0; |
821 | - } |
822 | - |
823 | - // Operators |
824 | + /** |
825 | + * Compares wrappers bytes by bytes. If sizes do not match, they are not |
826 | + * equal. If sizes match, compares byte by byte. |
827 | + * @param enc1 |
828 | + * @param enc2 |
829 | + * @return true if a match, false otherwise |
830 | + */ |
831 | inline friend bool operator==( const binarywrapper_t &enc1, |
832 | const binarywrapper_t &enc2) { |
833 | - if(enc1._nbytes != enc2._nbytes) |
834 | - return false; |
835 | - |
836 | - for(size_t i = 0; i < enc1._nbytes; i++) |
837 | - if(enc1._blob[i] != enc2._blob[i]) |
838 | - return false; |
839 | - |
840 | - return true; |
841 | - } |
842 | - |
843 | - /* inline friend bool operator <=( const binarywrapper &enc1, |
844 | - const binarywrapper &enc2) |
845 | - { |
846 | - if(enc1.numberOfBytes != enc2.numberOfBytes) |
847 | - return enc1.numberOfBytes < enc2.numberOfBytes; |
848 | - |
849 | - for(size_t i = 0; i < enc1.numberOfBytes; i++) |
850 | - if(enc1.blob[i] < enc2.blob[i]) |
851 | - return true; |
852 | - else if (enc1.blob[i] > enc2.blob[i]) |
853 | - return false; |
854 | - |
855 | - return true; |
856 | - }*/ |
857 | - |
858 | - inline friend bool operator<( const binarywrapper_t &enc1, |
859 | - const binarywrapper_t &enc2) { |
860 | - if(enc1._nbytes != enc2._nbytes) |
861 | - return enc1._nbytes < enc2._nbytes; |
862 | - |
863 | - for(size_t i = 0; i < enc1._nbytes; i++) |
864 | - if(enc1._blob[i] < enc2._blob[i]) |
865 | - return true; |
866 | - else if (enc1._blob[i] > enc2._blob[i]) |
867 | - return false; |
868 | - |
869 | - return false; |
870 | + return enc1.cmp(enc2) == 0; |
871 | } |
872 | |
873 | private: |
874 | + |
875 | + // blob of heap-allocated data |
876 | uchar* _blob; |
877 | - unsigned short _nbytes; |
878 | + |
879 | + // number of bytes allocated on heap |
880 | + unsigned short _nbytes; |
881 | + |
882 | + // meta data to carry |
883 | T _meta; |
884 | + |
885 | + // masks for single-bit access |
886 | const static uchar _masks[8]; |
887 | }; |
888 | |
889 | @@ -273,7 +376,13 @@ |
890 | } |
891 | |
892 | template<class T> |
893 | - uchar* binarywrapper_t<T>::raw() const |
894 | + uchar*& binarywrapper_t<T>::raw() |
895 | + { |
896 | + return _blob; |
897 | + } |
898 | + |
899 | + template<class T> |
900 | + uchar* binarywrapper_t<T>::const_raw() const |
901 | { |
902 | return _blob; |
903 | } |
904 | @@ -292,6 +401,8 @@ |
905 | { |
906 | if(_nbytes == 0) return; // Special case, nothing to do! |
907 | unsigned short int nbytes; |
908 | + |
909 | + // make sure we do not remove to much, but as much as we can. |
910 | if(topop >= _nbytes) |
911 | { |
912 | topop = _nbytes; |
913 | @@ -340,9 +451,10 @@ |
914 | } |
915 | |
916 | template<class T> |
917 | - void binarywrapper_t<T>::release() const |
918 | + void binarywrapper_t<T>::release() |
919 | { |
920 | delete[] _blob; |
921 | + _blob = NULL; |
922 | } |
923 | |
924 | template<class T> |
925 | |
926 | === modified file 'src/DiscreteVerification/DataStructures/ptrie.h' |
927 | --- src/DiscreteVerification/DataStructures/ptrie.h 2015-06-22 21:03:26 +0000 |
928 | +++ src/DiscreteVerification/DataStructures/ptrie.h 2015-08-20 13:27:24 +0000 |
929 | @@ -1,5 +1,5 @@ |
930 | /* |
931 | - * File: PTrie.h |
932 | + * File: ptrie.h |
933 | * Author: Peter G. Jensen |
934 | * |
935 | * Created on 10 June 2015, 18:44 |
936 | @@ -9,10 +9,12 @@ |
937 | #define PTRIE_H |
938 | |
939 | #include "binarywrapper.h" |
940 | +#include "visitor.h" |
941 | #include <assert.h> |
942 | #include <limits> |
943 | #include <vector> |
944 | #include <stdint.h> |
945 | +#include <stack> |
946 | |
947 | namespace ptrie |
948 | { |
949 | @@ -35,7 +37,15 @@ |
950 | void set_meta(T); |
951 | uint write_partial_encoding(encoding_t&) const; |
952 | encoding_t& remainder() const; |
953 | + |
954 | ptriepointer_t() : container(NULL), index(0) {}; |
955 | + |
956 | + ptriepointer_t<T>& operator=(const ptriepointer_t<T>&); |
957 | + ptriepointer_t<T>& operator++(); |
958 | + ptriepointer_t<T>& operator--(); |
959 | + bool operator==(const ptriepointer_t<T>& other); |
960 | + bool operator!=(const ptriepointer_t<T>& other); |
961 | + |
962 | }; |
963 | |
964 | template<typename T> |
965 | @@ -45,6 +55,55 @@ |
966 | } |
967 | |
968 | template<typename T> |
969 | + |
970 | + ptriepointer_t<T>& ptriepointer_t<T>::operator= |
971 | + (const ptriepointer_t<T>& other) |
972 | + { |
973 | + container = other.container; |
974 | + index = other.index; |
975 | + return *this; |
976 | + } |
977 | + |
978 | + template<typename T> |
979 | + ptriepointer_t<T>& ptriepointer_t<T>::operator++() |
980 | + { |
981 | + ++index; |
982 | + assert(index <= container->_next_free_entry); |
983 | + return *this; |
984 | + } |
985 | + |
986 | + template<typename T> |
987 | + ptriepointer_t<T>& ptriepointer_t<T>::operator--() |
988 | + { |
989 | + --index; |
990 | + return *this; |
991 | + } |
992 | + |
993 | + template<typename T> |
994 | + bool ptriepointer_t<T>::operator==(const ptriepointer_t<T>& other) |
995 | + { |
996 | + return other.container == container && other.index == index; |
997 | + } |
998 | + |
999 | + template<typename T> |
1000 | + bool ptriepointer_t<T>::operator!=(const ptriepointer_t<T>& other) |
1001 | + { |
1002 | + return !(*this == other); |
1003 | + } |
1004 | + |
1005 | + /* |
1006 | + template<typename T> |
1007 | + void swap(ptriepointer<T>& lhs, ptriepointer<T>& rhs) |
1008 | + { |
1009 | + ptrie<T>* container = lhs.container; |
1010 | + uint index = lhs.index; |
1011 | + lhs.container = rhs.container; |
1012 | + lhs.index = rhs.index; |
1013 | + rhs.index = index; |
1014 | + rhs.container = container; |
1015 | + }*/ |
1016 | + |
1017 | + template<typename T> |
1018 | T ptriepointer_t<T>::get_meta() const |
1019 | { |
1020 | return container->get_entry(index)->_data.get_meta(); |
1021 | @@ -72,7 +131,7 @@ |
1022 | class ptrie_t { |
1023 | typedef binarywrapper_t<T> encoding_t; |
1024 | friend class ptriepointer_t<T>; |
1025 | - public: |
1026 | + private: |
1027 | |
1028 | // nodes in the tree |
1029 | struct node_t |
1030 | @@ -123,6 +182,12 @@ |
1031 | std::pair<bool, ptriepointer_t<T> > find(const encoding_t& encoding); |
1032 | bool consistent() const; |
1033 | uint size() const { return _next_free_entry; } |
1034 | + ptriepointer_t<T> begin(); |
1035 | + ptriepointer_t<T> end(); |
1036 | + ptriepointer_t<T> last(); |
1037 | + ptriepointer_t<T> rend(); |
1038 | + |
1039 | + void visit(visitor_t<T>&); |
1040 | }; |
1041 | |
1042 | template<typename T> |
1043 | @@ -173,6 +238,30 @@ |
1044 | } |
1045 | |
1046 | template<typename T> |
1047 | + ptriepointer_t<T> ptrie_t<T>::begin() |
1048 | + { |
1049 | + return ptriepointer_t<T>(this, 0); |
1050 | + } |
1051 | + |
1052 | + template<typename T> |
1053 | + ptriepointer_t<T> ptrie_t<T>::end() |
1054 | + { |
1055 | + return ptriepointer_t<T>(this, _next_free_entry); |
1056 | + } |
1057 | + |
1058 | + template<typename T> |
1059 | + ptriepointer_t<T> ptrie_t<T>::last() |
1060 | + { |
1061 | + return ptriepointer_t<T>(this, _next_free_entry-1); |
1062 | + } |
1063 | + |
1064 | + template<typename T> |
1065 | + ptriepointer_t<T> ptrie_t<T>::rend() |
1066 | + { |
1067 | + return ptriepointer_t<T>(this, std::numeric_limits<uint>::max()); |
1068 | + } |
1069 | + |
1070 | + template<typename T> |
1071 | typename ptrie_t<T>::node_t* |
1072 | ptrie_t<T>::get_node(uint index) const |
1073 | { |
1074 | @@ -218,6 +307,8 @@ |
1075 | bool ptrie_t<T>::consistent() const |
1076 | { |
1077 | return true; |
1078 | + assert(_next_free_node >= _nodevector.size()); |
1079 | + assert(_next_free_entry >= _entryvector.size()); |
1080 | for(size_t i = 0; i < _next_free_node; ++i) |
1081 | { |
1082 | node_t* node = get_node(i); |
1083 | @@ -269,6 +360,61 @@ |
1084 | } |
1085 | |
1086 | template<typename T> |
1087 | + void ptrie_t<T>::visit(visitor_t<T>& visitor) |
1088 | + { |
1089 | + std::stack<std::pair<uint, uint> > waiting; |
1090 | + waiting.push(std::pair<int, uint>(-1, 0)); |
1091 | + |
1092 | + bool stop = false; |
1093 | + do{ |
1094 | + int distance = waiting.top().first; |
1095 | + uint n_index = waiting.top().second; |
1096 | + waiting.pop(); |
1097 | + |
1098 | + if(distance > -1) |
1099 | + { |
1100 | + visitor.back(distance); |
1101 | + visitor.set(distance, true); // only high on stack |
1102 | + } |
1103 | + |
1104 | + node_t* node = get_node(n_index); |
1105 | + bool skip = false; |
1106 | + do |
1107 | + { |
1108 | + |
1109 | + if(node->_highpos != 0) |
1110 | + { |
1111 | + waiting.push(std::pair<uint, uint>(distance + 1, node->_highpos)); |
1112 | + } |
1113 | + |
1114 | + if(node->_lowpos == 0) break; |
1115 | + else |
1116 | + { |
1117 | + ++distance; |
1118 | + node = get_node(node->_lowpos); |
1119 | + skip = visitor.set(distance, false); |
1120 | + } |
1121 | + |
1122 | + } while(!skip); |
1123 | + |
1124 | + distance += 1; |
1125 | + |
1126 | + uint bucketsize = 0; |
1127 | + if(!skip) |
1128 | + { |
1129 | + if(node->_highcount > 0) bucketsize += node->_highcount; |
1130 | + if(node->_lowcount > 0) bucketsize += node->_lowcount; |
1131 | + |
1132 | + for(uint i = 0; i < bucketsize && !stop; ++i) |
1133 | + { |
1134 | + stop = visitor.set_remainder(distance, |
1135 | + ptriepointer_t<T>(this, node->_entries[i])); |
1136 | + } |
1137 | + } |
1138 | + } while(!waiting.empty() && !stop); |
1139 | + } |
1140 | + |
1141 | + template<typename T> |
1142 | bool ptrie_t<T>::best_match(const encoding_t& encoding, uint& tree_pos, |
1143 | uint& e_index, uint& enc_pos, uint& b_index, uint& bucketsize) |
1144 | { |
1145 | @@ -316,7 +462,7 @@ |
1146 | // start by creating an encoding that "points" to the "unmatched" |
1147 | // part of the encoding. Notice, this is a shallow copy, no actual |
1148 | // heap-allocation happens! |
1149 | - encoding_t s_enc = encoding_t( encoding.raw(), |
1150 | + encoding_t s_enc = encoding_t( encoding.const_raw(), |
1151 | (encsize - enc_pos), |
1152 | enc_pos, |
1153 | encsize); |
1154 | @@ -341,18 +487,18 @@ |
1155 | e_index = node->_entries[b_index]; |
1156 | break; |
1157 | } |
1158 | - else if(cmp == 1) |
1159 | + else if(cmp > 0) |
1160 | { |
1161 | low = b_index + 1; |
1162 | } |
1163 | - else //if cmp == -1 |
1164 | + else //if cmp < 0 |
1165 | { |
1166 | high = b_index - 1; |
1167 | } |
1168 | |
1169 | if(low > high) |
1170 | { |
1171 | - if(cmp == 1) |
1172 | + if(cmp > 0) |
1173 | b_index += 1; |
1174 | break; |
1175 | } |
1176 | @@ -367,13 +513,13 @@ |
1177 | /*int tmp;// refference debug code! |
1178 | for(tmp = 0; tmp < bucketsize; ++tmp) |
1179 | { |
1180 | - entry_t* ent = getEntry(node->entries[tmp]); |
1181 | - if(ent->data < s_enc) |
1182 | + entry_t* ent = get_entry(node->_entries[tmp]); |
1183 | + if(ent->_data.cmp(s_enc) < 0) |
1184 | { |
1185 | continue; |
1186 | } |
1187 | else |
1188 | - if(ent->data == s_enc) |
1189 | + if(ent->_data == s_enc) |
1190 | { |
1191 | assert(found); |
1192 | break; |
1193 | @@ -491,8 +637,8 @@ |
1194 | uint enc_pos; |
1195 | uint bucketsize; |
1196 | uint e_index; |
1197 | - |
1198 | - if(best_match(encoding, tree_pos, e_index, enc_pos, bucketsize)) |
1199 | + uint b_index; |
1200 | + if(best_match(encoding, tree_pos, e_index, enc_pos, b_index, bucketsize)) |
1201 | { |
1202 | return std::pair<bool, ptriepointer_t<T> >(true, |
1203 | ptriepointer_t<T>(this, e_index)); |
1204 | @@ -534,7 +680,7 @@ |
1205 | remainder_size, |
1206 | enc_pos, |
1207 | encsize); |
1208 | - assert(n_entry->_data.raw() != encoding.raw()); |
1209 | + //assert(n_entry->_data.const_raw() != encoding.const_raw()); |
1210 | |
1211 | n_entry->_nodeindex = tree_pos; |
1212 | |
1213 | |
1214 | === added file 'src/DiscreteVerification/DataStructures/visitor.h' |
1215 | --- src/DiscreteVerification/DataStructures/visitor.h 1970-01-01 00:00:00 +0000 |
1216 | +++ src/DiscreteVerification/DataStructures/visitor.h 2015-08-20 13:27:24 +0000 |
1217 | @@ -0,0 +1,30 @@ |
1218 | +/* |
1219 | + * File: visitor.h |
1220 | + * Author: Peter G. Jensen |
1221 | + * |
1222 | + * Created on 16 June 2015, 23:15 |
1223 | + */ |
1224 | + |
1225 | +#ifndef VISITOR_H |
1226 | +#define VISITOR_H |
1227 | + |
1228 | +#include <stdint.h> |
1229 | + |
1230 | +namespace ptrie |
1231 | +{ |
1232 | + template<typename T> |
1233 | + class ptriepointer_t; |
1234 | + |
1235 | + template<typename T> |
1236 | + class visitor_t |
1237 | + { |
1238 | + public: |
1239 | + virtual bool back(int index) = 0; |
1240 | + virtual bool set(int index, bool value) = 0; |
1241 | + virtual bool set_remainder(int index, ptriepointer_t<T> pointer) = 0; |
1242 | + }; |
1243 | +} |
1244 | + |
1245 | + |
1246 | +#endif /* VISITOR_H */ |
1247 | + |
1248 | |
1249 | === modified file 'src/DiscreteVerification/DiscreteVerification.cpp' |
1250 | --- src/DiscreteVerification/DiscreteVerification.cpp 2015-06-17 09:03:12 +0000 |
1251 | +++ src/DiscreteVerification/DiscreteVerification.cpp 2015-08-20 13:27:24 +0000 |
1252 | @@ -53,42 +53,63 @@ |
1253 | exit(1); |
1254 | } |
1255 | |
1256 | - if (options.getMemoryOptimization() != VerificationOptions::NO_MEMORY_OPTIMIZATION) { |
1257 | - cout << "Workflow analysis currently does not support any memory optimizations (i.e. no PTries)." << endl; |
1258 | - exit(1); |
1259 | - } |
1260 | - WaitingList<NonStrictMarking*>* strategy = getWaitingList<NonStrictMarking* > (query, options); |
1261 | if(options.getWorkflowMode() == VerificationOptions::WORKFLOW_SOUNDNESS){ |
1262 | - WorkflowSoundness* verifier = new WorkflowSoundness(tapn, *initialMarking, query, options, strategy); |
1263 | + WorkflowSoundness* verifier; |
1264 | + if(options.getMemoryOptimization() == VerificationOptions::NO_MEMORY_OPTIMIZATION) |
1265 | + { |
1266 | + verifier = new WorkflowSoundness(tapn, *initialMarking, query, options, |
1267 | + getWaitingList<NonStrictMarking* > (query, options)); |
1268 | + } |
1269 | + else |
1270 | + { |
1271 | + verifier = new WorkflowSoundnessPTrie(tapn, *initialMarking, query, options, |
1272 | + getWaitingList<ptriepointer_t<MetaData*> > (query, options)); |
1273 | + } |
1274 | |
1275 | - if(verifier->getModelType() == verifier->NOTTAWFN){ |
1276 | - std::cerr << "Model is not a TAWFN!" << std::endl; |
1277 | - return -1; |
1278 | - }else if(verifier->getModelType() == verifier->ETAWFN){ |
1279 | - std::cout << "Model is a ETAWFN" << std::endl << std::endl; |
1280 | - }else if(verifier->getModelType() == verifier->MTAWFN){ |
1281 | - std::cout << "Model is a MTAWFN" << std::endl << std::endl; |
1282 | - } |
1283 | - VerifyAndPrint( |
1284 | - tapn, |
1285 | - *verifier, |
1286 | - options, |
1287 | - query); |
1288 | - verifier->printExecutionTime(cout); |
1289 | - verifier->printMessages(cout); |
1290 | + if(verifier->getModelType() == verifier->NOTTAWFN){ |
1291 | + std::cerr << "Model is not a TAWFN!" << std::endl; |
1292 | + return -1; |
1293 | + }else if(verifier->getModelType() == verifier->ETAWFN){ |
1294 | + std::cout << "Model is a ETAWFN" << std::endl << std::endl; |
1295 | + }else if(verifier->getModelType() == verifier->MTAWFN){ |
1296 | + std::cout << "Model is a MTAWFN" << std::endl << std::endl; |
1297 | + } |
1298 | + VerifyAndPrint( |
1299 | + tapn, |
1300 | + *verifier, |
1301 | + options, |
1302 | + query); |
1303 | + verifier->printExecutionTime(cout); |
1304 | + verifier->printMessages(cout); |
1305 | +#ifdef CLEANUP |
1306 | + delete verifier; |
1307 | +#endif |
1308 | } |
1309 | else{ |
1310 | // Assumes correct structure of net! |
1311 | - WorkflowStrongSoundnessReachability* verifier = new WorkflowStrongSoundnessReachability(tapn, *initialMarking, query, options, strategy); |
1312 | + WorkflowStrongSoundnessReachability* verifier; |
1313 | + if(options.getMemoryOptimization() == VerificationOptions::NO_MEMORY_OPTIMIZATION) |
1314 | + { |
1315 | + verifier = new WorkflowStrongSoundnessReachability(tapn, *initialMarking, query, options, |
1316 | + getWaitingList<NonStrictMarking* > (query, options)); |
1317 | + } |
1318 | + else |
1319 | + { |
1320 | + verifier = new WorkflowStrongSoundnessPTrie(tapn, *initialMarking, query, options, |
1321 | + getWaitingList<ptriepointer_t<MetaData*> > (query, options)); |
1322 | + } |
1323 | VerifyAndPrint( |
1324 | tapn, |
1325 | *verifier, |
1326 | options, |
1327 | query); |
1328 | verifier->printExecutionTime(cout); |
1329 | +#ifdef CLEANUP |
1330 | + delete verifier; |
1331 | +#endif |
1332 | } |
1333 | |
1334 | - delete strategy; |
1335 | + |
1336 | return 0; |
1337 | } |
1338 | |
1339 | |
1340 | === modified file 'src/DiscreteVerification/VerificationTypes/WorkflowSoundness.cpp' |
1341 | --- src/DiscreteVerification/VerificationTypes/WorkflowSoundness.cpp 2015-06-22 22:10:16 +0000 |
1342 | +++ src/DiscreteVerification/VerificationTypes/WorkflowSoundness.cpp 2015-08-20 13:27:24 +0000 |
1343 | @@ -6,6 +6,7 @@ |
1344 | */ |
1345 | |
1346 | #include "WorkflowSoundness.hpp" |
1347 | +#include <limits> |
1348 | |
1349 | namespace VerifyTAPN { |
1350 | namespace DiscreteVerification { |
1351 | @@ -13,6 +14,7 @@ |
1352 | WorkflowSoundness::WorkflowSoundness(TAPN::TimedArcPetriNet& tapn, NonStrictMarking& initialMarking, AST::Query* query, VerificationOptions options, WaitingList<NonStrictMarking*>* waiting_list) |
1353 | : Workflow(tapn, initialMarking, query, options), passedStack(), minExec(INT_MAX), linearSweepTreshold(3), coveredMarking(NULL), modelType(calculateModelType()){ |
1354 | pwList = new WorkflowPWList(waiting_list); |
1355 | + |
1356 | } |
1357 | |
1358 | |
1359 | @@ -21,6 +23,17 @@ |
1360 | |
1361 | }; |
1362 | |
1363 | +WorkflowSoundnessPTrie::WorkflowSoundnessPTrie(TAPN::TimedArcPetriNet& tapn, NonStrictMarking& initialMarking, AST::Query* query, VerificationOptions options, WaitingList<ptriepointer_t<MetaData*> >* waiting_list) |
1364 | +: WorkflowSoundness(tapn, initialMarking, query, options) { |
1365 | + int kbound = modelType == MTAWFN ? (std::numeric_limits<int>::max() - 1) : options.getKBound(); |
1366 | + pwList = new WorkflowPWListHybrid( tapn, |
1367 | + waiting_list, |
1368 | + kbound, |
1369 | + tapn.getNumberOfPlaces(), |
1370 | + tapn.getMaxConstant()); |
1371 | + |
1372 | +} |
1373 | + |
1374 | |
1375 | bool WorkflowSoundness::verify(){ |
1376 | if(addToPW(&initialMarking, NULL)){ |
1377 | @@ -50,6 +63,7 @@ |
1378 | return false; |
1379 | } |
1380 | } |
1381 | + deleteMarking(next_marking); |
1382 | } |
1383 | |
1384 | // Phase 2 |
1385 | @@ -82,6 +96,25 @@ |
1386 | return passed; |
1387 | } |
1388 | |
1389 | +int WorkflowSoundnessPTrie::numberOfPassed() |
1390 | +{ |
1391 | + int passed = 0; |
1392 | + while(passedStack.size()){ |
1393 | + WorkflowSoundnessMetaDataWithEncoding* next = |
1394 | + static_cast<WorkflowSoundnessMetaDataWithEncoding*>(passedStack.top()); |
1395 | + |
1396 | + passedStack.pop(); |
1397 | + if(next->passed) continue; |
1398 | + next->passed = true; |
1399 | + ++passed; |
1400 | + for(vector<MetaData*>::iterator iter = next->parents.begin(); |
1401 | + iter != next->parents.end(); iter++){ |
1402 | + passedStack.push(*iter); |
1403 | + } |
1404 | + } |
1405 | + return passed; |
1406 | +} |
1407 | + |
1408 | |
1409 | bool WorkflowSoundness::addToPW(NonStrictMarking* marking, NonStrictMarking* parent){ |
1410 | marking->cut(placeStats); |
1411 | @@ -91,7 +124,9 @@ |
1412 | // Check K-bound |
1413 | pwList->setMaxNumTokensIfGreater(size); |
1414 | if(modelType == ETAWFN && size > options.getKBound()) { |
1415 | - lastMarking = marking; |
1416 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1417 | + lastMarking = marking; |
1418 | + setMetaParent(lastMarking); |
1419 | return true; // Terminate false |
1420 | } |
1421 | |
1422 | @@ -101,8 +136,6 @@ |
1423 | NonStrictMarking* old = pwList->addToPassed(marking, false); |
1424 | if(old == NULL){ |
1425 | isNew = true; |
1426 | - marking->meta = new WorkflowSoundnessMetaData(); |
1427 | - marking->setParent(parent); |
1428 | } else { |
1429 | delete marking; |
1430 | marking = old; |
1431 | @@ -130,11 +163,14 @@ |
1432 | marking->meta->totalDelay = min(marking->meta->totalDelay, parent->meta->totalDelay); // Transition |
1433 | // keep track of shortest trace |
1434 | if (marking->meta->totalDelay < minExec) { |
1435 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1436 | + |
1437 | minExec = marking->meta->totalDelay; |
1438 | lastMarking = marking; |
1439 | return false; |
1440 | } |
1441 | }else{ |
1442 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1443 | lastMarking = marking; |
1444 | return true; // Terminate false |
1445 | } |
1446 | @@ -143,15 +179,18 @@ |
1447 | if(isNew){ |
1448 | pwList->addLastToWaiting(); |
1449 | if(parent != NULL && marking->canDeadlock(tapn, 0)){ |
1450 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1451 | lastMarking = marking; |
1452 | return true; |
1453 | } |
1454 | if(modelType == MTAWFN && checkForCoveredMarking(marking)){ |
1455 | - lastMarking = marking; |
1456 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1457 | + lastMarking = marking; |
1458 | return true; // Terminate false |
1459 | } |
1460 | } |
1461 | } |
1462 | + deleteMarking(marking); |
1463 | return false; |
1464 | } |
1465 | |
1466 | @@ -162,6 +201,14 @@ |
1467 | |
1468 | } |
1469 | |
1470 | +void WorkflowSoundnessPTrie::addParentMeta(MetaData* meta, MetaData* parent) |
1471 | +{ |
1472 | + assert(meta != NULL); |
1473 | + assert(parent != NULL); |
1474 | + WorkflowSoundnessMetaDataWithEncoding* markingmeta = ((WorkflowSoundnessMetaDataWithEncoding*)meta); |
1475 | + markingmeta->parents.push_back(parent); |
1476 | + |
1477 | +} |
1478 | |
1479 | bool WorkflowSoundness::checkForCoveredMarking(NonStrictMarking* marking){ |
1480 | if(marking->size() <= options.getKBound()){ |
1481 | @@ -193,6 +240,64 @@ |
1482 | } |
1483 | |
1484 | |
1485 | +void WorkflowSoundnessPTrie::getTrace(NonStrictMarking* marking){ |
1486 | + |
1487 | + PWListHybrid* pwhlist = dynamic_cast<PWListHybrid*>(this->pwList); |
1488 | + |
1489 | + stack < NonStrictMarking*> printStack; |
1490 | + |
1491 | + if(marking != NULL){ |
1492 | + printStack.push(marking); |
1493 | + |
1494 | + MetaDataWithTraceAndEncoding* meta = |
1495 | + static_cast<MetaDataWithTraceAndEncoding*>(marking->meta); |
1496 | + if(meta) |
1497 | + { |
1498 | + marking->setGeneratedBy(meta->generatedBy); |
1499 | + |
1500 | + meta = meta->parent; |
1501 | + while(meta != NULL) |
1502 | + { |
1503 | + NonStrictMarking* next = pwhlist->decode(meta->ep); |
1504 | + printStack.push(next); |
1505 | + next->setGeneratedBy(meta->generatedBy); |
1506 | + printStack.top()->setParent(next); |
1507 | + meta = meta->parent; |
1508 | + } |
1509 | + } |
1510 | + printStack.top()->setGeneratedBy(NULL); |
1511 | + } |
1512 | + |
1513 | +#ifdef CLEANUP |
1514 | + stack < NonStrictMarking*> clearStack = printStack; |
1515 | +#endif |
1516 | + printXMLTrace(marking, printStack, query, tapn); |
1517 | +#ifdef CLEANUP |
1518 | + while(!clearStack.empty()) |
1519 | + { |
1520 | + if(clearStack.top() == lastMarking) break; // deleted elsewhere |
1521 | + delete clearStack.top(); |
1522 | + clearStack.pop(); |
1523 | + } |
1524 | +#endif |
1525 | +} |
1526 | + |
1527 | + |
1528 | +void WorkflowSoundnessPTrie::setMetaParent(NonStrictMarking* marking){ |
1529 | + PWListHybrid* pwhlist = dynamic_cast<PWListHybrid*>(this->pwList); |
1530 | + |
1531 | + if(marking->meta == NULL) |
1532 | + { |
1533 | + marking->meta = new MetaDataWithTraceAndEncoding(); |
1534 | + } |
1535 | + |
1536 | + MetaDataWithTraceAndEncoding* mte = |
1537 | + static_cast<MetaDataWithTraceAndEncoding*>(marking->meta); |
1538 | + mte->parent = pwhlist->parent; |
1539 | + mte->generatedBy = marking->getGeneratedBy(); |
1540 | +} |
1541 | + |
1542 | + |
1543 | |
1544 | WorkflowSoundness::ModelType WorkflowSoundness::calculateModelType() { |
1545 | bool isin, isout; |
1546 | |
1547 | === modified file 'src/DiscreteVerification/VerificationTypes/WorkflowSoundness.hpp' |
1548 | --- src/DiscreteVerification/VerificationTypes/WorkflowSoundness.hpp 2015-06-22 22:10:16 +0000 |
1549 | +++ src/DiscreteVerification/VerificationTypes/WorkflowSoundness.hpp 2015-08-20 13:27:24 +0000 |
1550 | @@ -26,6 +26,7 @@ |
1551 | #include "../DataStructures/WaitingList.hpp" |
1552 | #include "Workflow.hpp" |
1553 | |
1554 | +using namespace ptrie; |
1555 | namespace VerifyTAPN { |
1556 | namespace DiscreteVerification { |
1557 | |
1558 | @@ -71,6 +72,23 @@ |
1559 | |
1560 | }; |
1561 | |
1562 | + |
1563 | +class WorkflowSoundnessPTrie : public WorkflowSoundness |
1564 | +{ |
1565 | +public: |
1566 | + WorkflowSoundnessPTrie(TAPN::TimedArcPetriNet& tapn, NonStrictMarking& initialMarking, AST::Query* query, VerificationOptions options, WaitingList<ptriepointer_t<MetaData*> >* waiting_list); |
1567 | + |
1568 | + virtual void addParentMeta(MetaData* meta, MetaData* parent); |
1569 | + virtual int numberOfPassed(); |
1570 | + virtual void deleteMarking(NonStrictMarking* marking) |
1571 | + { |
1572 | + delete marking; |
1573 | + } |
1574 | + virtual void getTrace(NonStrictMarking* marking); |
1575 | +protected: |
1576 | + virtual void setMetaParent(NonStrictMarking*); |
1577 | +}; |
1578 | + |
1579 | } /* namespace DiscreteVerification */ |
1580 | } /* namespace VerifyTAPN */ |
1581 | #endif /* NONSTRICTSEARCH_HPP_ */ |
1582 | |
1583 | === modified file 'src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.cpp' |
1584 | --- src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.cpp 2015-06-22 22:10:16 +0000 |
1585 | +++ src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.cpp 2015-08-20 13:27:24 +0000 |
1586 | @@ -16,6 +16,10 @@ |
1587 | findInOut(); |
1588 | }; |
1589 | |
1590 | + WorkflowStrongSoundnessReachability::WorkflowStrongSoundnessReachability(TAPN::TimedArcPetriNet& tapn, NonStrictMarking& initialMarking, AST::Query* query, VerificationOptions options) |
1591 | + : Workflow(tapn, initialMarking, query, options), maxValue(-1), outPlace(NULL){ |
1592 | + findInOut(); |
1593 | + }; |
1594 | |
1595 | void WorkflowStrongSoundnessReachability::findInOut() |
1596 | { |
1597 | @@ -25,8 +29,27 @@ |
1598 | break; |
1599 | } |
1600 | } |
1601 | - }; |
1602 | - |
1603 | + } |
1604 | + |
1605 | + WorkflowStrongSoundnessPTrie::WorkflowStrongSoundnessPTrie( |
1606 | + TAPN::TimedArcPetriNet& tapn, |
1607 | + NonStrictMarking& initialMarking, |
1608 | + AST::Query* query, |
1609 | + VerificationOptions options, |
1610 | + WaitingList<ptriepointer_t<MetaData*> >* waiting_list) : |
1611 | + WorkflowStrongSoundnessReachability( |
1612 | + tapn, |
1613 | + initialMarking, |
1614 | + query, |
1615 | + options) |
1616 | + { |
1617 | + pwList = new WorkflowPWListHybrid( tapn, |
1618 | + waiting_list, |
1619 | + options.getKBound(), |
1620 | + tapn.getNumberOfPlaces(), |
1621 | + tapn.getMaxConstant()); |
1622 | + } |
1623 | + |
1624 | bool WorkflowStrongSoundnessReachability::verify() { |
1625 | |
1626 | if (outPlace == NULL) |
1627 | @@ -53,6 +76,7 @@ |
1628 | bool noDelay = false; |
1629 | Result res = successorGenerator.generateAndInsertSuccessors(*next_marking); |
1630 | if (res == ADDTOPW_RETURNED_TRUE) { |
1631 | + clearTrace(); |
1632 | return true; |
1633 | } else if (res == ADDTOPW_RETURNED_FALSE_URGENTENABLED) { |
1634 | noDelay = true; |
1635 | @@ -65,7 +89,7 @@ |
1636 | marking->setGeneratedBy(NULL); |
1637 | |
1638 | if (addToPW(marking, next_marking)) { |
1639 | - |
1640 | + clearTrace(); |
1641 | lastMarking = marking; |
1642 | return true; |
1643 | } |
1644 | @@ -77,6 +101,7 @@ |
1645 | // remove childless markings from stack |
1646 | while(!trace.empty() && trace.top()->getNumberOfChildren() <= 1){ |
1647 | trace.top()->meta->inTrace = false; |
1648 | + deleteMarking(trace.top()); |
1649 | trace.pop(); |
1650 | } |
1651 | if(trace.empty()){ |
1652 | @@ -108,6 +133,64 @@ |
1653 | printXMLTrace(lastMarking, printStack, query, tapn); |
1654 | } |
1655 | |
1656 | + void WorkflowStrongSoundnessPTrie::getTrace() { |
1657 | + |
1658 | + PWListHybrid* pwhlist = dynamic_cast<PWListHybrid*>(this->pwList); |
1659 | + |
1660 | + std::stack < NonStrictMarking*> printStack; |
1661 | + |
1662 | + NonStrictMarking* next = lastMarking; |
1663 | + if(next != NULL) |
1664 | + { |
1665 | + |
1666 | + printStack.push(next); |
1667 | + MetaDataWithTraceAndEncoding* meta = |
1668 | + static_cast<MetaDataWithTraceAndEncoding*>(next->meta); |
1669 | + |
1670 | + if(meta == NULL) |
1671 | + { |
1672 | + // We assume the parent was not deleted on return |
1673 | + NonStrictMarking* parent = (NonStrictMarking*)lastMarking->getParent(); |
1674 | + if(parent != NULL) meta = |
1675 | + static_cast<MetaDataWithTraceAndEncoding*>(parent->meta); |
1676 | + delete parent; |
1677 | + } |
1678 | + else |
1679 | + { |
1680 | + meta = meta->parent; |
1681 | + } |
1682 | + |
1683 | + while(meta != NULL) |
1684 | + { |
1685 | + next = pwhlist->decode(meta->ep); |
1686 | + next->setGeneratedBy(meta->generatedBy); |
1687 | + printStack.top()->setParent(next); |
1688 | + printStack.push(next); |
1689 | + meta = meta->parent; |
1690 | + } |
1691 | + } |
1692 | +#ifdef CLEANUP |
1693 | + std::stack < NonStrictMarking*> cleanup = printStack; |
1694 | +#endif |
1695 | + printXMLTrace(lastMarking, printStack, query, tapn); |
1696 | + |
1697 | +#ifdef CLEANUP |
1698 | + while(!cleanup.empty()) |
1699 | + { |
1700 | + if(cleanup.top() != lastMarking) // deleted elsewhere |
1701 | + { |
1702 | + delete cleanup.top(); |
1703 | + cleanup.pop(); |
1704 | + } |
1705 | + else |
1706 | + { |
1707 | + break; |
1708 | + } |
1709 | + } |
1710 | +#endif |
1711 | + } |
1712 | + |
1713 | + |
1714 | bool WorkflowStrongSoundnessReachability::addToPW(NonStrictMarking* marking, NonStrictMarking* parent) { |
1715 | marking->cut(placeStats); |
1716 | marking->setParent(parent); |
1717 | @@ -135,6 +218,7 @@ |
1718 | // make sure we can print trace |
1719 | marking->setNumberOfChildren(1); |
1720 | maxValue = totalDelay; |
1721 | + deleteMarking(old); |
1722 | return true; |
1723 | } else { |
1724 | // search again to find maxdelay |
1725 | @@ -145,12 +229,12 @@ |
1726 | // fall through on purpose |
1727 | } |
1728 | } else { |
1729 | + deleteMarking(old); |
1730 | delete marking; |
1731 | // already seen this maxage/marking combination |
1732 | return false; |
1733 | } |
1734 | } else { |
1735 | - marking->meta = new MetaData(); |
1736 | marking->meta->totalDelay = totalDelay; |
1737 | } |
1738 | |
1739 | @@ -166,10 +250,14 @@ |
1740 | // if terminal, update max_value and last marking of trace |
1741 | if(maxValue < marking->meta->totalDelay) { |
1742 | maxValue = marking->meta->totalDelay; |
1743 | + if(lastMarking != NULL) deleteMarking(lastMarking); |
1744 | lastMarking = marking; |
1745 | return false; |
1746 | } |
1747 | } |
1748 | + |
1749 | + deleteMarking(marking); |
1750 | + |
1751 | return false; |
1752 | } |
1753 | |
1754 | @@ -179,5 +267,25 @@ |
1755 | old->setParent(marking->getParent()); |
1756 | } |
1757 | |
1758 | + void WorkflowStrongSoundnessPTrie::swapData(NonStrictMarking* marking, NonStrictMarking* parent) |
1759 | + { |
1760 | + PWListHybrid* pwhlist = dynamic_cast<PWListHybrid*>(this->pwList); |
1761 | + MetaDataWithTraceAndEncoding* meta = |
1762 | + static_cast<MetaDataWithTraceAndEncoding*>(parent->meta); |
1763 | + |
1764 | + meta->generatedBy = marking->getGeneratedBy(); |
1765 | + meta->parent = pwhlist->parent; |
1766 | + } |
1767 | + |
1768 | + void WorkflowStrongSoundnessPTrie::clearTrace() |
1769 | + { |
1770 | + if(!trace.empty()) trace.pop(); // pop parent, used in getTrace |
1771 | + while(!trace.empty()) |
1772 | + { |
1773 | + delete trace.top(); |
1774 | + trace.pop(); |
1775 | + } |
1776 | + } |
1777 | + |
1778 | } /* namespace DiscreteVerification */ |
1779 | } /* namespace VerifyTAPN */ |
1780 | |
1781 | === modified file 'src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.hpp' |
1782 | --- src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.hpp 2015-06-22 22:10:16 +0000 |
1783 | +++ src/DiscreteVerification/VerificationTypes/WorkflowStrongSoundness.hpp 2015-08-20 13:27:24 +0000 |
1784 | @@ -53,6 +53,26 @@ |
1785 | int validChildren; |
1786 | }; |
1787 | |
1788 | +class WorkflowStrongSoundnessPTrie : public WorkflowStrongSoundnessReachability |
1789 | +{ |
1790 | +public: |
1791 | + WorkflowStrongSoundnessPTrie( |
1792 | + TAPN::TimedArcPetriNet& tapn, |
1793 | + NonStrictMarking& initialMarking, |
1794 | + AST::Query* query, |
1795 | + VerificationOptions options, |
1796 | + WaitingList<ptriepointer_t<MetaData*> >* waiting_list); |
1797 | + virtual void getTrace(); |
1798 | + virtual void deleteMarking(NonStrictMarking* marking) |
1799 | + { |
1800 | + delete marking; |
1801 | + } |
1802 | + |
1803 | +protected: |
1804 | + virtual void swapData(NonStrictMarking* marking, NonStrictMarking* old); |
1805 | + virtual void clearTrace(); |
1806 | +}; |
1807 | + |
1808 | } /* namespace DiscreteVerification */ |
1809 | } /* namespace VerifyTAPN */ |
1810 | #endif /* NONSTRICTSEARCH_HPP_ */ |
Please, merge trunk to this branch and resolve the numerous conflicts.