Merge lp:~verifypn-maintainers/verifypn/sumoXMLparsing into lp:~verifypn-maintainers/verifypn/trunk
- sumoXMLparsing
- Merge into trunk
Proposed by
Jiri Srba
Status: | Merged |
---|---|
Approved by: | Jiri Srba |
Approved revision: | 96 |
Merged at revision: | 51 |
Proposed branch: | lp:~verifypn-maintainers/verifypn/sumoXMLparsing |
Merge into: | lp:~verifypn-maintainers/verifypn/trunk |
Diff against target: |
1220 lines (+857/-80) 9 files modified
PetriEngine/PQL/PQLQueryTokens.l (+0/-1) PetriParse/PNMLParser.cpp (+28/-6) PetriParse/PNMLParser.h (+7/-0) PetriParse/QueryXMLParser.cpp (+455/-0) PetriParse/QueryXMLParser.h (+68/-0) README.mkd (+1/-0) Scripts/BenchKit_head.sh (+106/-0) Scripts/run.sh (+20/-0) VerifyPN.cpp (+172/-73) |
To merge this branch: | bzr merge lp:~verifypn-maintainers/verifypn/sumoXMLparsing |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Jiri Srba | Approve | ||
Jonas Finnemann Jensen | Approve | ||
Review via email: mp+218201@code.launchpad.net |
Commit message
Adds a new flag -x query_number for parsing XML queries (model checking contest).
Description of the change
Adds a new flag -x query_number for parsing XML queries (model checking contest).
To post a comment you must log in.
Revision history for this message
Jonas Finnemann Jensen (jopsen) wrote : | # |
Revision history for this message
Jiri Srba (srba) wrote : | # |
Regarding A) the code now prints errors to stderr using fprintf.
Regarding B) the code is now clean of exception throws
Licence headers were added.
review:
Needs Resubmitting
Revision history for this message
Jonas Finnemann Jensen (jopsen) wrote : | # |
This looks good to me. Getting rid of exceptions makes me quite happy :)
Test cases would have been nice, but the current test setup is too hacked to cover -x at the moment...
review:
Approve
Revision history for this message
Jiri Srba (srba) : | # |
review:
Approve
Preview Diff
[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1 | === modified file 'PetriEngine/PQL/PQLQueryTokens.l' |
2 | --- PetriEngine/PQL/PQLQueryTokens.l 2014-03-23 05:21:56 +0000 |
3 | +++ PetriEngine/PQL/PQLQueryTokens.l 2014-05-13 20:18:53 +0000 |
4 | @@ -14,7 +14,6 @@ |
5 | |
6 | digit [0-9] |
7 | letter [a-zA-Z_] |
8 | - |
9 | %% |
10 | |
11 | [ \t\n\r] ; |
12 | |
13 | === modified file 'PetriParse/PNMLParser.cpp' |
14 | --- PetriParse/PNMLParser.cpp 2014-03-22 19:59:08 +0000 |
15 | +++ PetriParse/PNMLParser.cpp 2014-05-13 20:18:53 +0000 |
16 | @@ -21,6 +21,7 @@ |
17 | #include <string> |
18 | #include <stdio.h> |
19 | #include <stdlib.h> |
20 | +#include <iostream> |
21 | |
22 | using namespace PetriEngine; |
23 | using namespace XMLSP; |
24 | @@ -33,6 +34,7 @@ |
25 | arcs.clear(); |
26 | transitions.clear(); |
27 | inhibarcs.clear(); |
28 | + transitionEnabledness.clear(); |
29 | |
30 | //Set the builder |
31 | this->builder = builder; |
32 | @@ -41,6 +43,11 @@ |
33 | DOMElement* root = DOMElement::loadXML(xml); |
34 | parseElement(root); |
35 | |
36 | + // initialize transitionEnabledness |
37 | + for(TransitionIter it = transitions.begin(); it != transitions.end(); it++){ |
38 | + transitionEnabledness[it->id]="(true"; |
39 | + } |
40 | + |
41 | //Create inhibitor arcs |
42 | for(InhibitorArcIter inhb = inhibarcs.begin(); inhb != inhibarcs.end(); inhb++){ |
43 | //Check that source id exists |
44 | @@ -68,6 +75,10 @@ |
45 | char weight[sizeof(int) * 8 + 1]; |
46 | sprintf(weight, "%i", inhb->weight); |
47 | |
48 | + //cout << "INHIB ARC: " << source.id << " to " << target.id << " weight " << weight << endl; |
49 | + string cond = " and \"" + source.id + "\" < " + weight; |
50 | + transitionEnabledness[it->id]+=cond; |
51 | + |
52 | if(it->cond.empty()){ |
53 | it->cond = source.id + " < " + string(weight); |
54 | }else{ |
55 | @@ -103,6 +114,14 @@ |
56 | |
57 | if(source.isPlace && !target.isPlace){ |
58 | builder->addInputArc(source.id, target.id, it->weight); |
59 | + |
60 | + // cout << "ARC: " << source.id << " to " << target.id << " weight " << it->weight << endl; |
61 | + char weight[sizeof(int) * 8 + 1]; |
62 | + sprintf(weight, "%i", it->weight); |
63 | + |
64 | + string cond = " and \"" + source.id + "\" >= " + weight; |
65 | + transitionEnabledness[target.id]+=cond; |
66 | + |
67 | }else if(!source.isPlace && target.isPlace){ |
68 | builder->addOutputArc(source.id, target.id, it->weight); |
69 | }else{ |
70 | @@ -113,6 +132,11 @@ |
71 | } |
72 | } |
73 | |
74 | + // finalize transitionEnabledness |
75 | + for(TransitionIter it = transitions.begin(); it != transitions.end(); it++){ |
76 | + transitionEnabledness[it->id]+=")"; |
77 | + } |
78 | + |
79 | //Release DOM tree |
80 | delete root; |
81 | |
82 | @@ -257,7 +281,6 @@ |
83 | weight = atoi(text.c_str()); |
84 | } |
85 | } |
86 | - |
87 | Arc arc; |
88 | arc.source = source; |
89 | arc.target = target; |
90 | @@ -300,14 +323,13 @@ |
91 | builder->addVariable(name, initialValue, range); |
92 | } |
93 | |
94 | - |
95 | -void PNMLParser::parseValue(DOMElement* element, string& text){ |
96 | +void PNMLParser::parseValue(DOMElement* element, string& text) { |
97 | DOMElements elements = element->getChilds(); |
98 | DOMElements::iterator it; |
99 | - for(it = elements.begin(); it != elements.end(); it++){ |
100 | - if((*it)->getElementName() == "value" || (*it)->getElementName() == "text") |
101 | + for (it = elements.begin(); it != elements.end(); it++) { |
102 | + if ((*it)->getElementName() == "value" || (*it)->getElementName() == "text") { |
103 | text = (*it)->getCData(); |
104 | - else |
105 | + } else |
106 | parseValue(*it, text); |
107 | } |
108 | } |
109 | |
110 | === modified file 'PetriParse/PNMLParser.h' |
111 | --- PetriParse/PNMLParser.h 2014-03-22 19:59:08 +0000 |
112 | +++ PetriParse/PNMLParser.h 2014-05-13 20:18:53 +0000 |
113 | @@ -48,6 +48,7 @@ |
114 | bool isPlace; |
115 | }; |
116 | typedef std::map<std::string, NodeName> NodeNameMap; |
117 | + |
118 | public: |
119 | |
120 | struct Query{ |
121 | @@ -61,6 +62,7 @@ |
122 | }; |
123 | typedef std::vector<InhibitorArc> InhibitorArcList; |
124 | typedef InhibitorArcList::iterator InhibitorArcIter; |
125 | + typedef std::map<std::string, std::string> TransitionEnablednessMap; |
126 | |
127 | PNMLParser(){ |
128 | builder = NULL; |
129 | @@ -75,6 +77,10 @@ |
130 | InhibitorArcList getInhibitorArcs(){ |
131 | return inhibarcs; |
132 | } |
133 | + |
134 | + TransitionEnablednessMap getTransitionEnabledness() { |
135 | + return transitionEnabledness; |
136 | + } |
137 | |
138 | private: |
139 | void parseElement(XMLSP::DOMElement* element); |
140 | @@ -93,6 +99,7 @@ |
141 | TransitionList transitions; |
142 | InhibitorArcList inhibarcs; |
143 | std::vector<Query> queries; |
144 | + TransitionEnablednessMap transitionEnabledness; // encodes the enabledness condition for each transition |
145 | }; |
146 | |
147 | #endif // PNMLPARSER_H |
148 | |
149 | === added file 'PetriParse/QueryXMLParser.cpp' |
150 | --- PetriParse/QueryXMLParser.cpp 1970-01-01 00:00:00 +0000 |
151 | +++ PetriParse/QueryXMLParser.cpp 2014-05-13 20:18:53 +0000 |
152 | @@ -0,0 +1,455 @@ |
153 | +/* VerifyPN - TAPAAL Petri Net Engine |
154 | + * Copyright (C) 2014 Jiri Srba <srba.jiri@gmail.com> |
155 | + * |
156 | + * This program is free software: you can redistribute it and/or modify |
157 | + * it under the terms of the GNU General Public License as published by |
158 | + * the Free Software Foundation, either version 3 of the License, or |
159 | + * (at your option) any later version. |
160 | + * |
161 | + * This program is distributed in the hope that it will be useful, |
162 | + * but WITHOUT ANY WARRANTY; without even the implied warranty of |
163 | + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
164 | + * GNU General Public License for more details. |
165 | + * |
166 | + * You should have received a copy of the GNU General Public License |
167 | + * along with this program. If not, see <http://www.gnu.org/licenses/>. |
168 | + */ |
169 | + |
170 | +#include "QueryXMLParser.h" |
171 | + |
172 | +#include <string> |
173 | +#include <stdio.h> |
174 | +#include <stdlib.h> |
175 | +#include <iostream> |
176 | +#include <sstream> |
177 | +#include <algorithm> |
178 | + |
179 | +using namespace XMLSP; |
180 | +using namespace std; |
181 | + |
182 | +QueryXMLParser::QueryXMLParser(const PNMLParser::TransitionEnablednessMap &transitionEnabledness) { |
183 | + _transitionEnabledness = transitionEnabledness; |
184 | +}; |
185 | + |
186 | +// QueryXMLParser::~QueryXMLParser() { }; |
187 | + |
188 | + |
189 | +bool QueryXMLParser::parse(const std::string& xml){ |
190 | + //Parse the xml |
191 | + DOMElement* root = DOMElement::loadXML(xml); |
192 | + bool parsingOK; |
193 | + if (root) { |
194 | + parsingOK = parsePropertySet(root); |
195 | + } else { |
196 | + parsingOK=false; |
197 | + } |
198 | + |
199 | + //Release DOM tree |
200 | + delete root; |
201 | + return parsingOK; |
202 | +} |
203 | + |
204 | + |
205 | +bool QueryXMLParser::parsePropertySet(DOMElement* element){ |
206 | + if (element->getElementName()!="property-set") { |
207 | + fprintf(stderr,"ERROR missing property-set\n"); |
208 | + return false; // missing property-set element |
209 | + } |
210 | + DOMElements elements = element->getChilds(); |
211 | + DOMElements::iterator it; |
212 | + for(it = elements.begin(); it != elements.end(); it++){ |
213 | + if (!parseProperty(*it)) { |
214 | + return false; |
215 | + }; |
216 | + } |
217 | + return true; |
218 | +} |
219 | + |
220 | +bool QueryXMLParser::parseProperty(DOMElement* element){ |
221 | + if (element->getElementName()!="property") { |
222 | + fprintf(stderr,"ERROR missing property\n"); |
223 | + return false; // unexpected element (only property is allowed) |
224 | + } |
225 | + string id; |
226 | + string queryText; |
227 | + bool negateResult=false; |
228 | + bool isPlaceBound=false; |
229 | + string placeNameForBound; |
230 | + bool tagsOK=true; |
231 | + |
232 | + DOMElements elements = element->getChilds(); |
233 | + DOMElements::iterator it; |
234 | + DOMElements::iterator formulaPtr; |
235 | + for(it = elements.begin(); it != elements.end(); it++){ |
236 | + if ((*it)->getElementName()=="id") { |
237 | + id = (*it)->getCData(); |
238 | + } else if ((*it)->getElementName()=="formula") { |
239 | + formulaPtr=it; |
240 | + } else if ((*it)->getElementName()=="tags") { |
241 | + tagsOK=parseTags(*it); |
242 | + } |
243 | + } |
244 | + |
245 | + if (id=="") { |
246 | + fprintf(stderr,"ERROR a query with empty id\n"); |
247 | + return false; |
248 | + } |
249 | + |
250 | + QueryItem queryItem; |
251 | + queryItem.id=id; |
252 | + if (tagsOK && parseFormula(*formulaPtr, queryText, negateResult, isPlaceBound, placeNameForBound)) { |
253 | + queryItem.queryText=queryText; |
254 | + queryItem.negateResult=negateResult; |
255 | + queryItem.isPlaceBound=isPlaceBound; |
256 | + queryItem.placeNameForBound=placeNameForBound; |
257 | + queryItem.parsingResult=QueryItem::PARSING_OK; |
258 | + } else { |
259 | + queryItem.queryText=""; |
260 | + queryItem.negateResult=false; |
261 | + queryItem.isPlaceBound=false; |
262 | + queryItem.placeNameForBound=""; |
263 | + queryItem.parsingResult=QueryItem::UNSUPPORTED_QUERY; |
264 | + } |
265 | + queries.push_back(queryItem); |
266 | + return true; |
267 | +} |
268 | + |
269 | +bool QueryXMLParser::parseTags(DOMElement* element){ |
270 | + // we can accept only reachability query |
271 | + DOMElements elements = element->getChilds(); |
272 | + DOMElements::iterator it; |
273 | + for(it = elements.begin(); it != elements.end(); it++){ |
274 | + if ((*it)->getElementName()=="is-reachability" && (*it)->getCData()!="true") { |
275 | + return false; |
276 | + } |
277 | + } |
278 | + return true; |
279 | +} |
280 | + |
281 | +bool QueryXMLParser::parseFormula(DOMElement* element, string &queryText, bool &negateResult, bool &isPlaceBound, string &placeNameForBound){ |
282 | + /* |
283 | + Describe here how to parse |
284 | + * INV phi = AG phi = not EF not phi |
285 | + * IMPOS phi = AG not phi = not EF phi |
286 | + * POS phi = EF phi |
287 | + * NEG INV phi = not AG phi = EF not phi |
288 | + * NEG IMPOS phi = not AG not phi = EF phi |
289 | + * NEG POS phi = not EF phi |
290 | + */ |
291 | + DOMElements elements = element->getChilds(); |
292 | + if (elements.size() != 1) { |
293 | + return false; |
294 | + } |
295 | + DOMElements::iterator booleanFormula = elements.begin(); |
296 | + string elementName = (*booleanFormula)->getElementName(); |
297 | + if (elementName=="invariant") { |
298 | + queryText="EF not("; |
299 | + negateResult=true; |
300 | + } else if (elementName=="impossibility") { |
301 | + queryText="EF ( "; |
302 | + negateResult=true; |
303 | + } else if (elementName=="possibility") { |
304 | + queryText="EF ( "; |
305 | + negateResult=false; |
306 | + } else if (elementName=="negation") { |
307 | + DOMElements children = (*elements.begin())->getChilds(); |
308 | + if (children.size() !=1) { |
309 | + return false; |
310 | + } |
311 | + booleanFormula = children.begin(); |
312 | + string negElementName = (*booleanFormula)->getElementName(); |
313 | + if (negElementName=="invariant") { |
314 | + queryText="EF not( "; |
315 | + negateResult=false; |
316 | + } else if (negElementName=="impossibility") { |
317 | + queryText="EF ( "; |
318 | + negateResult=false; |
319 | + } else if (negElementName=="possibility") { |
320 | + queryText="EF ( "; |
321 | + negateResult=true; |
322 | + } else { |
323 | + return false; |
324 | + } |
325 | + } else if (elementName == "place-bound") { |
326 | + queryText = "EF "; |
327 | + DOMElements children = (*booleanFormula)->getChilds(); |
328 | + if (children.size() != 1) { |
329 | + return false; // we support only place-bound for one place |
330 | + } |
331 | + if (children[0]->getElementName() != "place") { |
332 | + return false; |
333 | + } |
334 | + placeNameForBound = parsePlace(children[0]); |
335 | + if (placeNameForBound=="") { |
336 | + return false; // invalid place name |
337 | + } |
338 | + queryText += "\""+placeNameForBound+"\""+" < 0"; |
339 | + negateResult = false; |
340 | + isPlaceBound = true; |
341 | + return true; |
342 | + } else { |
343 | + return false; |
344 | + } |
345 | + DOMElements nextElements = (*booleanFormula)->getChilds(); |
346 | + if (nextElements.size() !=1 || !parseBooleanFormula(nextElements[0] , queryText)) { |
347 | + return false; |
348 | + } |
349 | + queryText+=" )"; |
350 | + isPlaceBound=false; |
351 | + placeNameForBound = ""; |
352 | + return true; |
353 | +} |
354 | + |
355 | +bool QueryXMLParser::parseBooleanFormula(DOMElement* element, string &queryText){ |
356 | + string elementName = element->getElementName(); |
357 | + if (elementName == "deadlock") { |
358 | + queryText+="deadlock"; |
359 | + return true; |
360 | + } else if (elementName == "true") { |
361 | + queryText+="true"; |
362 | + return true; |
363 | + } else if (elementName == "false") { |
364 | + queryText+="false"; |
365 | + return true; |
366 | + } else if (elementName == "negation") { |
367 | + DOMElements children = element->getChilds(); |
368 | + queryText+="not("; |
369 | + if (children.size()==1 && parseBooleanFormula(children[0], queryText)) { |
370 | + queryText+=")"; |
371 | + } else { |
372 | + return false; |
373 | + } |
374 | + return true; |
375 | + } else if (elementName == "conjunction") { |
376 | + DOMElements children = element->getChilds(); |
377 | + if (children.size()<2) { |
378 | + return false; |
379 | + } |
380 | + if (!(parseBooleanFormula((children[0]), queryText))) { |
381 | + return false; |
382 | + } |
383 | + DOMElements::iterator it; |
384 | + for(it = (children.begin())+1; it != children.end(); it++) { |
385 | + queryText+=" and "; |
386 | + if (!(parseBooleanFormula(*it, queryText))) { |
387 | + return false; |
388 | + } |
389 | + } |
390 | + return true; |
391 | + } else if (elementName == "disjunction") { |
392 | + DOMElements children = element->getChilds(); |
393 | + if (children.size()<2) { |
394 | + return false; |
395 | + } |
396 | + if (!(parseBooleanFormula(*children.begin(), queryText))) { |
397 | + return false; |
398 | + } |
399 | + DOMElements::iterator it; |
400 | + for(it = children.begin()+1; it != children.end(); it++) { |
401 | + queryText+=" or "; |
402 | + if (!(parseBooleanFormula(*it, queryText))) { |
403 | + return false; |
404 | + } |
405 | + } |
406 | + return true; |
407 | + } else if (elementName == "exclusive-disjunction") { |
408 | + DOMElements children = element->getChilds(); |
409 | + if (children.size()!=2) { // we support only two subformulae here |
410 | + return false; |
411 | + } |
412 | + string subformula1; |
413 | + string subformula2; |
414 | + if (!(parseBooleanFormula(*(children.begin()), subformula1))) { |
415 | + return false; |
416 | + } |
417 | + if (!(parseBooleanFormula(*(children.begin()+1), subformula2))) { |
418 | + return false; |
419 | + } |
420 | + queryText+= "(("+subformula1+" and not("+subformula2+")) or (not("+subformula1+") and "+subformula2+"))"; |
421 | + return true; |
422 | + } else if (elementName == "implication") { |
423 | + DOMElements children = element->getChilds(); |
424 | + if (children.size()!=2) { // implication has only two subformulae |
425 | + return false; |
426 | + } |
427 | + string subformula1; |
428 | + string subformula2; |
429 | + if (!(parseBooleanFormula(*(children.begin()), subformula1))) { |
430 | + return false; |
431 | + } |
432 | + if (!(parseBooleanFormula(*(children.begin()+1), subformula2))) { |
433 | + return false; |
434 | + } |
435 | + queryText+= "not("+subformula1+") or ( "+subformula2+" )"; |
436 | + return true; |
437 | + } else if (elementName == "equivalence") { |
438 | + DOMElements children = element->getChilds(); |
439 | + if (children.size()!=2) { // we support only two subformulae here |
440 | + return false; |
441 | + } |
442 | + string subformula1; |
443 | + string subformula2; |
444 | + if (!(parseBooleanFormula(*(children.begin()), subformula1))) { |
445 | + return false; |
446 | + } |
447 | + if (!(parseBooleanFormula(*(children.begin()+1), subformula2))) { |
448 | + return false; |
449 | + } |
450 | + queryText+= "(("+subformula1+" and "+subformula2+") or (not("+subformula1+") and not("+subformula2+")))"; |
451 | + return true; |
452 | + } else if ( elementName == "integer-eq" || |
453 | + elementName == "integer-ne" || |
454 | + elementName == "integer-lt" || |
455 | + elementName == "integer-le" || |
456 | + elementName == "integer-gt" || |
457 | + elementName == "integer-ge") { |
458 | + DOMElements children = element->getChilds(); |
459 | + if (children.size()!=2) { // exactly two integer subformulae are required |
460 | + return false; |
461 | + } |
462 | + string subformula1; |
463 | + string subformula2; |
464 | + if (!(parseIntegerExpression(children[0], subformula1))) { |
465 | + return false; |
466 | + } |
467 | + if (!(parseIntegerExpression(children[1], subformula2))) { |
468 | + return false; |
469 | + } |
470 | + string mathoperator; |
471 | + if ( elementName == "integer-eq") mathoperator=" == "; |
472 | + else if ( elementName == "integer-ne") mathoperator=" != "; |
473 | + else if ( elementName == "integer-lt") mathoperator=" < "; |
474 | + else if ( elementName == "integer-le") mathoperator=" <= "; |
475 | + else if ( elementName == "integer-gt") mathoperator=" > "; |
476 | + else if ( elementName == "integer-ge") mathoperator=" >= "; |
477 | + |
478 | + queryText+="("+subformula1+mathoperator+subformula2+")"; |
479 | + return true; |
480 | + } else if (elementName == "is-fireable") { |
481 | + DOMElements children = element->getChilds(); |
482 | + if (children.size() == 0) { |
483 | + return false; |
484 | + } |
485 | + if (children.size() > 1) { |
486 | + queryText += "("; |
487 | + } |
488 | + for (int i = 0; i < children.size(); i++) { |
489 | + if (children[i]->getElementName() != "transition") { |
490 | + return false; |
491 | + } |
492 | + if (i > 0) { |
493 | + queryText += " or "; |
494 | + } |
495 | + string transitionName = children[i]->getCData(); |
496 | + if(_transitionEnabledness.find(transitionName) == _transitionEnabledness.end()){ |
497 | + fprintf(stderr, |
498 | + "XML Query Parsing error: Transition id=\"%s\" was not found!\n", |
499 | + transitionName.c_str()); |
500 | + return false; |
501 | + } |
502 | + queryText += _transitionEnabledness[transitionName]; |
503 | + } |
504 | + if (children.size() > 1) { |
505 | + queryText += ")"; |
506 | + } |
507 | + return true; |
508 | + } |
509 | + return false; |
510 | +} |
511 | + |
512 | +bool QueryXMLParser::parseIntegerExpression(DOMElement* element, string &queryText){ |
513 | + string elementName = element->getElementName(); |
514 | + if (elementName == "integer-constant") { |
515 | + int i; |
516 | + if(sscanf((element->getCData()).c_str(), "%d", &i) == EOF ) { |
517 | + return false; // expected integer at this place |
518 | + } |
519 | + stringstream ss;//create a stringstream |
520 | + ss << i;//add number to the stream |
521 | + queryText+=ss.str(); |
522 | + return true; |
523 | + } else if (elementName == "tokens-count") { |
524 | + DOMElements children = element->getChilds(); |
525 | + if (children.size()==0) { |
526 | + return false; |
527 | + } |
528 | + if (children.size()>1) { |
529 | + queryText+="("; |
530 | + } |
531 | + for (int i = 0; i < children.size(); i++) { |
532 | + if (children[i]->getElementName() != "place") { |
533 | + return false; |
534 | + } |
535 | + if (i > 0) { |
536 | + queryText += " + "; |
537 | + } |
538 | + string placeName = parsePlace(children[i]); |
539 | + if (placeName == "") { |
540 | + return false; // invalid place name |
541 | + } |
542 | + queryText+="\""+placeName+"\""; |
543 | + } |
544 | + if (children.size()>1) { |
545 | + queryText+=")"; |
546 | + } |
547 | + return true; |
548 | + } else if ( elementName == "integer-sum" || |
549 | + elementName == "integer-product" ) { |
550 | + DOMElements children = element->getChilds(); |
551 | + if (children.size() < 2) { // at least two integer subexpression are required |
552 | + return false; |
553 | + } |
554 | + string mathoperator; |
555 | + if ( elementName == "integer-sum") mathoperator = " + "; |
556 | + else if (elementName == "integer-product") mathoperator = " * "; |
557 | + queryText+="("; |
558 | + for (int i = 0; i < children.size(); i++) { |
559 | + if (i > 0) { |
560 | + queryText+= mathoperator; |
561 | + } |
562 | + if (!parseIntegerExpression(children[i], queryText)) { |
563 | + return false; |
564 | + } |
565 | + } |
566 | + queryText+=")"; |
567 | + return true; |
568 | + } else if (elementName == "integer-difference" ) { |
569 | + DOMElements children = element->getChilds(); |
570 | + if (children.size() != 2) { // at least two integer subexpression are required |
571 | + return false; |
572 | + } |
573 | + queryText+="("; |
574 | + if (!parseIntegerExpression(children[0], queryText)) { |
575 | + return false; |
576 | + } |
577 | + queryText+=" - "; |
578 | + if (!parseIntegerExpression(children[1], queryText)) { |
579 | + return false; |
580 | + } |
581 | + queryText+=")"; |
582 | + return true; |
583 | + } |
584 | + return false; |
585 | +} |
586 | + |
587 | +string QueryXMLParser::parsePlace(XMLSP::DOMElement* element) { |
588 | + if (element->getElementName() != "place") { |
589 | + return ""; // missing place tag |
590 | + } |
591 | + string placeName = element->getCData(); |
592 | + placeName.erase(std::remove_if(placeName.begin(), placeName.end(), ::isspace), placeName.end()); |
593 | + return placeName; |
594 | +} |
595 | + |
596 | + |
597 | +void QueryXMLParser::printQueries() { |
598 | + QueryXMLParser::QueriesIterator it; |
599 | + for(it = queries.begin(); it != queries.end(); it++){ |
600 | + cout << it->id << ": " << (it->isPlaceBound ? "\tplace-bound " : ""); |
601 | + if (it->parsingResult == QueryItem::UNSUPPORTED_QUERY) { |
602 | + cout << "\t---------- unsupported query ----------" << endl; |
603 | + } else { |
604 | + cout << "\t" << (it->negateResult ? "not " : "") << it->queryText << endl; |
605 | + } |
606 | + } |
607 | +} |
608 | |
609 | === added file 'PetriParse/QueryXMLParser.h' |
610 | --- PetriParse/QueryXMLParser.h 1970-01-01 00:00:00 +0000 |
611 | +++ PetriParse/QueryXMLParser.h 2014-05-13 20:18:53 +0000 |
612 | @@ -0,0 +1,68 @@ |
613 | +/* VerifyPN - TAPAAL Petri Net Engine |
614 | + * Copyright (C) 2014 Jiri Srba <srba.jiri@gmail.com> |
615 | + * |
616 | + * This program is free software: you can redistribute it and/or modify |
617 | + * it under the terms of the GNU General Public License as published by |
618 | + * the Free Software Foundation, either version 3 of the License, or |
619 | + * (at your option) any later version. |
620 | + * |
621 | + * This program is distributed in the hope that it will be useful, |
622 | + * but WITHOUT ANY WARRANTY; without even the implied warranty of |
623 | + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
624 | + * GNU General Public License for more details. |
625 | + * |
626 | + * You should have received a copy of the GNU General Public License |
627 | + * along with this program. If not, see <http://www.gnu.org/licenses/>. |
628 | + */ |
629 | + |
630 | +#ifndef QUERYXMLPARSER_H |
631 | +#define QUERYXMLPARSER_H |
632 | + |
633 | +#include "xmlsp/xmlsp_dom.h" |
634 | +#include "PNMLParser.h" |
635 | + |
636 | +#include <map> |
637 | +#include <string> |
638 | +#include <string.h> |
639 | +#include <vector> |
640 | +#include <sstream> |
641 | + |
642 | +using namespace std; |
643 | + |
644 | +class QueryXMLParser { |
645 | +public: |
646 | + QueryXMLParser(const PNMLParser::TransitionEnablednessMap &transitionEnabledness); |
647 | + // ~QueryXMLParser(); |
648 | + |
649 | + struct QueryItem { |
650 | + string id; // query name |
651 | + string queryText; // only EF queries will be here |
652 | + bool negateResult; // true if the final result should be negated |
653 | + bool isPlaceBound; // true if the query is a place-bound one (returns integer) |
654 | + string placeNameForBound; |
655 | + enum { |
656 | + PARSING_OK, |
657 | + UNSUPPORTED_QUERY, |
658 | + } parsingResult; |
659 | + }; |
660 | + |
661 | + typedef vector<QueryItem> Queries; |
662 | + typedef Queries::iterator QueriesIterator; |
663 | + Queries queries; |
664 | + |
665 | + bool parse(const string& xml); |
666 | + void printQueries(); |
667 | + |
668 | +private: |
669 | + bool parsePropertySet(XMLSP::DOMElement* element); |
670 | + bool parseProperty(XMLSP::DOMElement* element); |
671 | + bool parseTags(XMLSP::DOMElement* element); |
672 | + bool parseFormula(XMLSP::DOMElement* element, string &queryText, bool &negateResult, bool &isPlaceBound, string &placeNameForBound); |
673 | + bool parseBooleanFormula(XMLSP::DOMElement* element, string &queryText); |
674 | + bool parseIntegerExpression(XMLSP::DOMElement* element, string &queryText); |
675 | + string parsePlace(XMLSP::DOMElement* element); |
676 | + PNMLParser::TransitionEnablednessMap _transitionEnabledness; |
677 | +}; |
678 | + |
679 | +#endif /* QUERYXMLPARSER_H */ |
680 | + |
681 | |
682 | === modified file 'README.mkd' |
683 | --- README.mkd 2013-10-21 09:24:49 +0000 |
684 | +++ README.mkd 2014-05-13 20:18:53 +0000 |
685 | @@ -55,3 +55,4 @@ |
686 | * Jonas Finnemann Jensen |
687 | * Thomas Søndersø Nielsen |
688 | * Lars Kærlund Østergaard |
689 | + * Jiri Srba |
690 | |
691 | === added directory 'Scripts' |
692 | === added file 'Scripts/BenchKit_head.sh' |
693 | --- Scripts/BenchKit_head.sh 1970-01-01 00:00:00 +0000 |
694 | +++ Scripts/BenchKit_head.sh 2014-05-13 20:18:53 +0000 |
695 | @@ -0,0 +1,106 @@ |
696 | +#!/bin/bash |
697 | + |
698 | +# This is the initialization script for the participation of TAPAAL |
699 | +# untimed engine verifypn in the Petri net competition 2014. |
700 | + |
701 | +# BK_EXAMINATION: it is a string that identifies your "examination" |
702 | + |
703 | +export PATH="$PATH:/home/mcc/BenchKit/bin/" |
704 | +VERIFYPN=$HOME/BenchKit/bin/verifypn |
705 | +#VERIFYPN=/Users/srba/dev/sumoXMLparsing/verifypn-osx64 |
706 | +TIMEOUT=10 |
707 | + |
708 | +if [ ! -f iscolored ]; then |
709 | + echo "File 'iscolored' not found!" |
710 | +else |
711 | + if [ "TRUE" = `cat iscolored` ]; then |
712 | + echo "TAPAAL does not support colored nets." |
713 | + echo "DO_NOT_COMPETE" |
714 | + exit 0 |
715 | + fi |
716 | +fi |
717 | + |
718 | +if [ ! -f model.pnml ]; then |
719 | + echo "File 'model.pnml' not found!" |
720 | + exit 1 |
721 | +fi |
722 | + |
723 | +function verify { |
724 | + if [ ! -f $2 ]; then |
725 | + echo "File '$2' not found!" |
726 | + exit 1 |
727 | + fi |
728 | + local NUMBER=`cat $2 | grep "<property>" | wc -l` |
729 | + for (( QUERY=1; QUERY<=$NUMBER; QUERY++ )) |
730 | + do |
731 | + echo |
732 | + echo "verifypn" $1 "-x" $QUERY "model.pnml" $2 |
733 | + if [ $TIMEOUT = 0 ]; then |
734 | + $VERIFYPN $1 "-x" $QUERY "model.pnml" $2 |
735 | + else |
736 | + timeout $TIMEOUT $VERIFYPN $1 "-x" $QUERY "model.pnml" $2 |
737 | + RETVAL=$? |
738 | + if [ $RETVAL = 124 ] || [ $RETVAL = 125 ] || [ $RETVAL = 126 ] || [ $RETVAL = 127 ] || [ $RETVAL = 137 ] ; then |
739 | + echo -ne "CANNOT_COMPUTE\n" |
740 | + fi |
741 | + fi |
742 | + done |
743 | +} |
744 | + |
745 | + |
746 | +case "$BK_EXAMINATION" in |
747 | + |
748 | + StateSpace) |
749 | + echo |
750 | + echo "*****************************************" |
751 | + echo "* TAPAAL performing StateSpace search *" |
752 | + echo "*****************************************" |
753 | + $VERIFYPN -n -d -e model.pnml |
754 | + ;; |
755 | + |
756 | + ReachabilityComputeBounds) |
757 | + echo |
758 | + echo "***********************************************" |
759 | + echo "* TAPAAL verifying ReachabilityComputeBounds *" |
760 | + echo "***********************************************" |
761 | + verify "-n -r 1" "ReachabilityComputeBounds.xml" |
762 | + ;; |
763 | + |
764 | + ReachabilityDeadlock) |
765 | + echo |
766 | + echo "**********************************************" |
767 | + echo "* TAPAAL checking for ReachabilityDeadlock *" |
768 | + echo "**********************************************" |
769 | + TIMEOUT=0 |
770 | + verify "-n -r 1" "ReachabilityDeadlock.xml" |
771 | + ;; |
772 | + |
773 | + ReachabilityCardinality) |
774 | + echo |
775 | + echo "**********************************************" |
776 | + echo "* TAPAAL verifying ReachabilityCardinality *" |
777 | + echo "**********************************************" |
778 | + verify "-n -r 1" "ReachabilityCardinality.xml" |
779 | + ;; |
780 | + |
781 | + ReachabilityFireability) |
782 | + echo |
783 | + echo "**********************************************" |
784 | + echo "* TAPAAL verifying ReachabilityFireability *" |
785 | + echo "**********************************************" |
786 | + verify "-n -r 1" "ReachabilityFireability.xml" |
787 | + ;; |
788 | + |
789 | + ReachabilityFireabilitySimple) |
790 | + echo |
791 | + echo "****************************************************" |
792 | + echo "* TAPAAL verifying ReachabilityFireabilitySimple *" |
793 | + echo "****************************************************" |
794 | + verify "-n -r 1" "ReachabilityFireabilitySimple.xml" |
795 | + ;; |
796 | + |
797 | + *) |
798 | + echo "DO_NOT_COMPETE" |
799 | + exit 0 |
800 | + ;; |
801 | +esac |
802 | |
803 | === added file 'Scripts/run.sh' |
804 | --- Scripts/run.sh 1970-01-01 00:00:00 +0000 |
805 | +++ Scripts/run.sh 2014-05-13 20:18:53 +0000 |
806 | @@ -0,0 +1,20 @@ |
807 | +for D in $(find INPUTS -mindepth 1 -maxdepth 1 -type d) ; do |
808 | + echo; |
809 | + echo "####################################################################"; |
810 | + echo $D ; |
811 | + cp BenchKit_head.sh $D ; |
812 | + cd $D ; |
813 | + export BK_EXAMINATION=StateSpace ; |
814 | + ./BenchKit_head.sh |
815 | + export BK_EXAMINATION=ReachabilityComputeBounds ; |
816 | + ./BenchKit_head.sh |
817 | + export BK_EXAMINATION=ReachabilityDeadlock ; |
818 | + ./BenchKit_head.sh |
819 | + export BK_EXAMINATION=ReachabilityCardinality ; |
820 | + ./BenchKit_head.sh |
821 | + export BK_EXAMINATION=ReachabilityFireability ; |
822 | + ./BenchKit_head.sh |
823 | + export BK_EXAMINATION=ReachabilityFireabilitySimple ; |
824 | + ./BenchKit_head.sh |
825 | + cd ../.. |
826 | +done |
827 | |
828 | === modified file 'VerifyPN.cpp' |
829 | --- VerifyPN.cpp 2014-03-18 07:13:31 +0000 |
830 | +++ VerifyPN.cpp 2014-05-13 20:18:53 +0000 |
831 | @@ -1,8 +1,8 @@ |
832 | /* PeTe - Petri Engine exTremE |
833 | - * Copyright (C) 2011 Jonas Finnemann Jensen <jopsen@gmail.com>, |
834 | - * Thomas Søndersø Nielsen <primogens@gmail.com>, |
835 | - * Lars Kærlund Østergaard <larsko@gmail.com>, |
836 | - * Jiri Srba <srba.jiri@gmail.com> |
837 | + * Copyright (C) 2011-2014 Jonas Finnemann Jensen <jopsen@gmail.com>, |
838 | + * Thomas Søndersø Nielsen <primogens@gmail.com>, |
839 | + * Lars Kærlund Østergaard <larsko@gmail.com>, |
840 | + * Jiri Srba <srba.jiri@gmail.com> |
841 | * |
842 | * This program is free software: you can redistribute it and/or modify |
843 | * it under the terms of the GNU General Public License as published by |
844 | @@ -39,6 +39,7 @@ |
845 | #include <PetriEngine/Reachability/BreadthFirstReachabilitySearch.h> |
846 | |
847 | #include "PetriEngine/Reducer.h" |
848 | +#include "PetriParse/QueryXMLParser.h" |
849 | |
850 | |
851 | using namespace std; |
852 | @@ -74,8 +75,13 @@ |
853 | char* modelfile = NULL; |
854 | char* queryfile = NULL; |
855 | bool disableoverapprox = false; |
856 | - int enablereduction = 0; // 0 ... disabled (default), 1 ... aggresive, 2 ... k-boundedness preserving |
857 | + int enablereduction = 0; // 0 ... disabled (default), 1 ... aggresive, 2 ... k-boundedness preserving |
858 | + int xmlquery = -1; // if value is nonnegative then input query file is in xml format and we verify query |
859 | + // number xmlquery |
860 | + bool statespaceexploration = false; |
861 | + bool printstatistics = true; |
862 | |
863 | + |
864 | //----------------------- Parse Arguments -----------------------// |
865 | |
866 | // Parse command line arguments |
867 | @@ -111,27 +117,40 @@ |
868 | fprintf(stderr, "Argument Error: Unrecognized search strategy \"%s\"\n", s); |
869 | return ErrorCode; |
870 | } |
871 | - }else if(strcmp(argv[i], "-m") == 0 || strcmp(argv[i], "--memory-limit") == 0){ |
872 | - if (i==argc-1) { |
873 | - fprintf(stderr, "Missing number after \"%s\"\n\n", argv[i]); |
874 | - return ErrorCode; |
875 | - } |
876 | - if(sscanf(argv[++i], "%d", &memorylimit) != 1 || memorylimit < 0){ |
877 | + } else if (strcmp(argv[i], "-m") == 0 || strcmp(argv[i], "--memory-limit") == 0) { |
878 | + if (i == argc - 1) { |
879 | + fprintf(stderr, "Missing number after \"%s\"\n\n", argv[i]); |
880 | + return ErrorCode; |
881 | + } |
882 | + if (sscanf(argv[++i], "%d", &memorylimit) != 1 || memorylimit < 0) { |
883 | fprintf(stderr, "Argument Error: Invalid memory limit \"%s\"\n", argv[i]); |
884 | return ErrorCode; |
885 | } |
886 | - }else if(strcmp(argv[i], "-d") == 0 || strcmp(argv[i], "--disable-overapprox") == 0){ |
887 | + } else if (strcmp(argv[i], "-d") == 0 || strcmp(argv[i], "--disable-overapprox") == 0) { |
888 | disableoverapprox = true; |
889 | - }else if(strcmp(argv[i], "-r") == 0 || strcmp(argv[i], "--reduction") == 0){ |
890 | - if (i==argc-1) { |
891 | - fprintf(stderr, "Missing number after \"%s\"\n\n", argv[i]); |
892 | - return ErrorCode; |
893 | - } |
894 | - if(sscanf(argv[++i], "%d", &enablereduction) != 1 || enablereduction < 0 || enablereduction > 2){ |
895 | - fprintf(stderr, "Argument Error: Invalid reduction argument \"%s\"\n", argv[i]); |
896 | + } else if (strcmp(argv[i], "-e") == 0 || strcmp(argv[i], "--state-space-exploration") == 0) { |
897 | + statespaceexploration = true; |
898 | + } else if (strcmp(argv[i], "-n") == 0 || strcmp(argv[i], "--no-statistics") == 0) { |
899 | + printstatistics = false; |
900 | + } else if (strcmp(argv[i], "-x") == 0 || strcmp(argv[i], "--xml-queries") == 0) { |
901 | + if (i == argc - 1) { |
902 | + fprintf(stderr, "Missing number after \"%s\"\n\n", argv[i]); |
903 | return ErrorCode; |
904 | } |
905 | - }else if(strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "--help") == 0){ |
906 | + if (sscanf(argv[++i], "%d", &xmlquery) != 1 || xmlquery <= 0) { |
907 | + fprintf(stderr, "Argument Error: Query index to verify \"%s\"\n", argv[i]); |
908 | + return ErrorCode; |
909 | + } |
910 | + }else if (strcmp(argv[i], "-r") == 0 || strcmp(argv[i], "--reduction") == 0) { |
911 | + if (i == argc - 1) { |
912 | + fprintf(stderr, "Missing number after \"%s\"\n\n", argv[i]); |
913 | + return ErrorCode; |
914 | + } |
915 | + if (sscanf(argv[++i], "%d", &enablereduction) != 1 || enablereduction < 0 || enablereduction > 2) { |
916 | + fprintf(stderr, "Argument Error: Invalid reduction argument \"%s\"\n", argv[i]); |
917 | + return ErrorCode; |
918 | + } |
919 | + } else if (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "--help") == 0){ |
920 | printf( "Usage: verifypn [options] model-file query-file\n" |
921 | "A tool for answering reachability of place cardinality queries (including deadlock)\n" |
922 | "for weighted P/T Petri nets extended with inhibitor arcs.\n" |
923 | @@ -144,14 +163,17 @@ |
924 | " - BFS Breadth first search\n" |
925 | " - DFS Depth first search\n" |
926 | " - RDFS Random depth first search\n" |
927 | - " - OverApprox Linear Over Approx.\n" |
928 | + " - OverApprox Linear Over Approx\n" |
929 | " -m, --memory-limit <megabyte> Memory limit for the state space search in MB,\n" |
930 | " 0 for unlimited (default)\n" |
931 | + " -e, --state-space-exploration State-space exploration only (query-file is irrelevant)\n" |
932 | + " -x, --xml-query <query index> Parse XML query file and verify query of a given index\n" |
933 | " -d, --disable-over-approximation Disable linear over approximation\n" |
934 | - " -r, --reduction Enable structural net reduction:\n" |
935 | - " - 0 disabled (default)\n" |
936 | - " - 1 aggressive reduction\n" |
937 | - " - 2 reduction preserving k-boundedness\n" |
938 | + " -r, --reduction Enable structural net reduction:\n" |
939 | + " - 0 disabled (default)\n" |
940 | + " - 1 aggressive reduction\n" |
941 | + " - 2 reduction preserving k-boundedness\n" |
942 | + " -n, --no-statistics Do not display any statistics (default is to display it)\n" |
943 | " -h, --help Display this help message\n" |
944 | " -v, --version Display version information\n" |
945 | "\n" |
946 | @@ -169,7 +191,7 @@ |
947 | printf("VerifyPN (untimed verification engine for TAPAAL) %s\n", VERSION); |
948 | printf("Copyright (C) 2011-2014 Jonas Finnemann Jensen <jopsen@gmail.com>,\n"); |
949 | printf(" Thomas Søndersø Nielsen <primogens@gmail.com>,\n"); |
950 | - printf(" Lars Kærlund Østergaard <larsko@gmail.com>\n"); |
951 | + printf(" Lars Kærlund Østergaard <larsko@gmail.com>,\n"); |
952 | printf(" Jiri Srba <srba.jiri@gmail.com>\n"); |
953 | printf("GNU GPLv3 or later <http://gnu.org/licenses/gpl.html>\n"); |
954 | return 0; |
955 | @@ -182,6 +204,15 @@ |
956 | return ErrorCode; |
957 | } |
958 | } |
959 | + if (statespaceexploration) { |
960 | + // for state-space exploration some options are mandatory |
961 | + disableoverapprox = true; |
962 | + enablereduction = 0; |
963 | + kbound = 0; |
964 | + outputtrace = false; |
965 | + searchstrategy = BFS; |
966 | + } |
967 | + |
968 | |
969 | //----------------------- Validate Arguments -----------------------// |
970 | |
971 | @@ -192,7 +223,7 @@ |
972 | } |
973 | |
974 | //Check for query file |
975 | - if(!modelfile){ |
976 | + if(!modelfile && !statespaceexploration){ |
977 | fprintf(stderr, "Argument Error: No query-file provided\n"); |
978 | return ErrorCode; |
979 | } |
980 | @@ -204,14 +235,15 @@ |
981 | MarkVal* m0 = NULL; |
982 | VarVal* v0 = NULL; |
983 | |
984 | - // List of inhibitor arcs |
985 | - PNMLParser::InhibitorArcList inhibarcs; |
986 | - |
987 | + // List of inhibitor arcs and transition enabledness |
988 | + PNMLParser::InhibitorArcList inhibarcs; |
989 | + PNMLParser::TransitionEnablednessMap transitionEnabledness; |
990 | { |
991 | //Load the model |
992 | ifstream mfile(modelfile, ifstream::in); |
993 | if(!mfile){ |
994 | fprintf(stderr, "Error: Model file \"%s\" couldn't be opened\n", modelfile); |
995 | + fprintf(stdout, "CANNOT_COMPUTE\n"); |
996 | return ErrorCode; |
997 | } |
998 | |
999 | @@ -225,8 +257,9 @@ |
1000 | parser.parse(buffer.str(), &builder); |
1001 | parser.makePetriNet(); |
1002 | |
1003 | - inhibarcs = parser.getInhibitorArcs(); // Remember inhibitor arcs |
1004 | - |
1005 | + inhibarcs = parser.getInhibitorArcs(); // Remember inhibitor arcs |
1006 | + transitionEnabledness = parser.getTransitionEnabledness(); // Remember conditions for transitions |
1007 | + |
1008 | //Build the petri net |
1009 | net = builder.makePetriNet(); |
1010 | m0 = builder.makeInitialMarking(); |
1011 | @@ -235,50 +268,84 @@ |
1012 | // Close the file |
1013 | mfile.close(); |
1014 | } |
1015 | - |
1016 | + |
1017 | //----------------------- Parse Query -----------------------// |
1018 | |
1019 | //Condition to check |
1020 | Condition* query = NULL; |
1021 | bool isInvariant = false; |
1022 | - |
1023 | + QueryXMLParser XMLparser(transitionEnabledness); // parser for XML queries |
1024 | //Read query file, begin scope to release memory |
1025 | { |
1026 | - //Open query file |
1027 | - ifstream qfile(queryfile, ifstream::in); |
1028 | - if(!qfile){ |
1029 | - fprintf(stderr, "Error: Query file \"%s\" couldn't be opened\n", queryfile); |
1030 | - return ErrorCode; |
1031 | - } |
1032 | - |
1033 | - //Read everything |
1034 | - stringstream buffer; |
1035 | - buffer << qfile.rdbuf(); |
1036 | - string querystr = buffer.str(); |
1037 | - |
1038 | - //Validate query type |
1039 | - if(querystr.substr(0, 2) != "EF" && querystr.substr(0, 2) != "AG"){ |
1040 | - fprintf(stderr, "Error: Query type \"%s\" not supported, only (EF and AG is supported)\n", querystr.substr(0, 2).c_str()); |
1041 | - return ErrorCode; |
1042 | - } |
1043 | - |
1044 | - //Check if is invariant |
1045 | - isInvariant = querystr.substr(0, 2) == "AG"; |
1046 | - |
1047 | - //Warp in not if isInvariant |
1048 | - string querystring = querystr.substr(2); |
1049 | - if(isInvariant) |
1050 | - querystring = "not ( " + querystring + " )"; |
1051 | - |
1052 | + string querystring; // excluding EF and AG |
1053 | + if (!statespaceexploration) { |
1054 | + //Open query file |
1055 | + ifstream qfile(queryfile, ifstream::in); |
1056 | + if (!qfile) { |
1057 | + fprintf(stderr, "Error: Query file \"%s\" couldn't be opened\n", queryfile); |
1058 | + fprintf(stdout, "CANNOT_COMPUTE\n"); |
1059 | + return ErrorCode; |
1060 | + } |
1061 | + |
1062 | + //Read everything |
1063 | + stringstream buffer; |
1064 | + buffer << qfile.rdbuf(); |
1065 | + string querystr = buffer.str(); // including EF and AG |
1066 | + //Parse XML the queries and querystr let be the index of xmlquery |
1067 | + if (xmlquery > 0) { |
1068 | + if (!XMLparser.parse(querystr)) { |
1069 | + fprintf(stderr, "Error: Failed parsing XML query file\n"); |
1070 | + fprintf(stdout, "DO_NOT_COMPETE\n"); |
1071 | + return ErrorCode; |
1072 | + } |
1073 | + // XMLparser.printQueries(); |
1074 | + if (XMLparser.queries.size() < xmlquery) { |
1075 | + fprintf(stderr, "Error: Wrong index of query in the XML query file\n"); |
1076 | + fprintf(stdout, "CANNOT_COMPUTE\n"); |
1077 | + return ErrorCode; |
1078 | + } |
1079 | + if (XMLparser.queries[xmlquery - 1].parsingResult == QueryXMLParser::QueryItem::UNSUPPORTED_QUERY) { |
1080 | + fprintf(stdout, "The selected query in the XML query file is not supported\n"); |
1081 | + fprintf(stdout, "FORMULA %s CANNOT_COMPUTE\n", XMLparser.queries[xmlquery-1].id.c_str()); |
1082 | + return ErrorCode; |
1083 | + } |
1084 | + // fprintf(stdout, "Index of the selected query: %d\n\n", xmlquery); |
1085 | + querystr = XMLparser.queries[xmlquery - 1].queryText; |
1086 | + querystring = querystr.substr(2); |
1087 | + isInvariant = XMLparser.queries[xmlquery - 1].negateResult; |
1088 | + |
1089 | + if (xmlquery>0) { |
1090 | + fprintf(stdout, "FORMULA %s ", XMLparser.queries[xmlquery-1].id.c_str()); |
1091 | + fflush(stdout); |
1092 | + } |
1093 | + |
1094 | + } else { // standard textual query |
1095 | + //Validate query type |
1096 | + if (querystr.substr(0, 2) != "EF" && querystr.substr(0, 2) != "AG") { |
1097 | + fprintf(stderr, "Error: Query type \"%s\" not supported, only (EF and AG is supported)\n", querystr.substr(0, 2).c_str()); |
1098 | + return ErrorCode; |
1099 | + } |
1100 | + //Check if is invariant |
1101 | + isInvariant = querystr.substr(0, 2) == "AG"; |
1102 | + |
1103 | + //Warp in not if isInvariant |
1104 | + querystring = querystr.substr(2); |
1105 | + if (isInvariant) |
1106 | + querystring = "not ( " + querystring + " )"; |
1107 | + } |
1108 | + //Close query file |
1109 | + qfile.close(); |
1110 | + } else { // state-space exploration |
1111 | + querystring = "false"; |
1112 | + isInvariant = false; |
1113 | + } |
1114 | + |
1115 | //Parse query |
1116 | query = ParseQuery(querystring); |
1117 | if(!query){ |
1118 | - fprintf(stderr, "Error: Failed to parse query \"%s\"\n", querystr.substr(2).c_str()); |
1119 | + fprintf(stderr, "Error: Failed to parse query \"%s\"\n", querystring.c_str()); //querystr.substr(2).c_str()); |
1120 | return ErrorCode; |
1121 | } |
1122 | - |
1123 | - //Close query file |
1124 | - qfile.close(); |
1125 | } |
1126 | |
1127 | //----------------------- Context Analysis -----------------------// |
1128 | @@ -298,8 +365,9 @@ |
1129 | } |
1130 | } |
1131 | |
1132 | - //--------------------- Apply Net Reduction ---------------// |
1133 | - |
1134 | + |
1135 | + //--------------------- Apply Net Reduction ---------------// |
1136 | + |
1137 | Reducer reducer = Reducer(net); // reduced is needed also in trace generation (hence the extended scope) |
1138 | if (enablereduction == 1 or enablereduction == 2) { |
1139 | // Compute how many times each place appears in the query |
1140 | @@ -355,12 +423,12 @@ |
1141 | ReachabilityResult result = strategy->reachable(*net, m0, v0, query); |
1142 | |
1143 | //----------------------- Output Trace -----------------------// |
1144 | - const std::vector<unsigned int>& trace = (enablereduction==0 ? result.trace() : reducer.NonreducedTrace(net,result.trace())); |
1145 | - const std::vector<std::string>& tnames = net->transitionNames(); |
1146 | + const std::vector<std::string>& tnames = net->transitionNames(); |
1147 | const std::vector<std::string>& pnames = net->placeNames(); |
1148 | - |
1149 | + |
1150 | //Print result to stderr |
1151 | if(outputtrace && result.result() == ReachabilityResult::Satisfied){ |
1152 | + const std::vector<unsigned int>& trace = (enablereduction==0 ? result.trace() : reducer.NonreducedTrace(net,result.trace())); |
1153 | fprintf(stderr, "Trace:\n<trace>\n"); |
1154 | for(size_t i = 0; i < trace.size(); i++){ |
1155 | fprintf(stderr, "\t<transition id=\"%s\">\n", tnames[trace[i]].c_str()); |
1156 | @@ -378,6 +446,7 @@ |
1157 | |
1158 | //----------------------- Output Statistics -----------------------// |
1159 | |
1160 | + if (printstatistics) { |
1161 | //Print statistics |
1162 | fprintf(stdout, "STATS:\n"); |
1163 | fprintf(stdout, "\tdiscovered states: %lli\n", result.discoveredStates()); |
1164 | @@ -412,11 +481,22 @@ |
1165 | } |
1166 | } |
1167 | fprintf(stdout,"\n\n"); |
1168 | + } |
1169 | |
1170 | //----------------------- Output Result -----------------------// |
1171 | |
1172 | ReturnValues retval = ErrorCode; |
1173 | |
1174 | + if (statespaceexploration) { |
1175 | + retval = UnknownCode; |
1176 | + unsigned int placeBound = 0; |
1177 | + for(size_t p = 0; p < result.maxPlaceBound().size(); p++) { |
1178 | + placeBound = std::max<unsigned int>(placeBound,result.maxPlaceBound()[p]); |
1179 | + } |
1180 | + fprintf(stdout,"STATE_SPACE %lli -1 %d %d TECHNIQUES EXPLICIT\n", result.exploredStates(), result.maxTokens(), placeBound); |
1181 | + return retval; |
1182 | + } |
1183 | + |
1184 | //Find result code |
1185 | if(result.result() == ReachabilityResult::Unknown) |
1186 | retval = UnknownCode; |
1187 | @@ -428,10 +508,29 @@ |
1188 | //Print result |
1189 | if(retval == UnknownCode) |
1190 | fprintf(stdout, "Unable to decide if query is satisfied.\n"); |
1191 | - else if(retval == SuccessCode) |
1192 | - fprintf(stdout, "Query is satisfied.\n"); |
1193 | - else if(retval == FailedCode) |
1194 | - fprintf(stdout, "Query is NOT satisfied.\n"); |
1195 | + else if(retval == SuccessCode) { |
1196 | + if (xmlquery>0) { |
1197 | + fprintf(stdout, "TRUE TECHNIQUES EXPLICIT STRUCTURAL_REDUCTION\n"); |
1198 | + } |
1199 | + fprintf(stdout, "Query is satisfied.\n"); |
1200 | + } else if(retval == FailedCode) { |
1201 | + if (xmlquery>0 && XMLparser.queries[xmlquery-1].isPlaceBound) { |
1202 | + // find index of the place for reporting place bound |
1203 | + for(size_t p = 0; p < result.maxPlaceBound().size(); p++) { |
1204 | + if (pnames[p]==XMLparser.queries[xmlquery-1].placeNameForBound) { |
1205 | + fprintf(stdout, "%d TECHNIQUES EXPLICIT STRUCTURAL_REDUCTION\n", result.maxPlaceBound()[p]); |
1206 | + fprintf(stdout, "Maximum number of tokens in place %s: %d\n",XMLparser.queries[xmlquery-1].placeNameForBound.c_str(),result.maxPlaceBound()[p]); |
1207 | + retval = UnknownCode; |
1208 | + break; |
1209 | + } |
1210 | + } |
1211 | + } else { |
1212 | + if (xmlquery>0) { |
1213 | + fprintf(stdout, "FALSE TECHNIQUES EXPLICIT STRUCTURAL_REDUCTION\n"); |
1214 | + } |
1215 | + fprintf(stdout, "Query is NOT satisfied.\n"); |
1216 | + } |
1217 | + } |
1218 | |
1219 | return retval; |
1220 | } |
This looks good...
Things like transitionEnabl edness and InhibitorArcList makes me very sad. We should have a Petri Net structure that carries this kind of information.
Anyways, that is not the state of the current codebase, and given what we have this is good.
The overhead of encoding a condition string for each transition is negligible anyways.
It is just a source for bugs and other pains, but it'll probably work fine :)
Comments for PetriParse/ QueryXMLParser. cpp:
A)
stdout is consistently used for logging errors. I would strongly advice using stderr for communicating errors.
Personally, I prefer to use fprintf(stderr, "...", ...); but cerr works too. C++ streams are not the best for
formatting output, things get so obscure and for large datasets (not the case here) performance is an issue.
Hence, I try to stay away from cout/cerr as a rule of thumb.
B)
Exceptions is a feature in C++ that is rarely used. At least I've rarely seen people use it, and many projects outright forbid it: Gecko, LLVM, Google C++ guidelines...
Compiling with exceptions causes RTTI Run-Time Type Information to be encoded and prevents certain compiler optimizations.
Unless coding some sort of big enterprise project where correctness and stability is more important than speed, I wouldn't use exceptions. Both because they are complicated and because they have overhead.
Comments for PetriParse/ QueryXMLParser. (h|cpp) :
Please, add license header for consistency, I believe this would be appropriate:
/* VerifyPN - TAPAAL Petri Net Engine www.gnu. org/licenses/>.
* Copyright (C) 2014 Jiri Srba <email address hidden>
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://
*/
Assuming you're okay with licensing it under GPLv3.
It's just nice to clear up any confusion.