Bugzilla – Full Text Bug Listing
| Summary: | [serializer] infinite loop when syntactic transition involves loop | ||
|---|---|---|---|
| Product: | [Modeling] TMF | Reporter: | Moritz Eysholdt <moritz.eysholdt> |
| Component: | Xtext | Assignee: | Project Inbox <tmf.xtext-inbox> |
| Status: | CLOSED FIXED | QA Contact: | |
| Severity: | normal | ||
| Priority: | P3 | CC: | mkomor, sebastian.zarnekow |
| Version: | 2.3.0 | Flags: | moritz.eysholdt:
kepler+
|
| Target Milestone: | M7 | ||
| Hardware: | PC | ||
| OS: | Mac OS X - Carbon (unsup.) | ||
| Whiteboard: | |||
It turns out this is no real infinite loop, but a exponential high runtime complexity for scenarios like:
Greeting:
'Hello' foo=ID
("kw1" val1+=ID? |
"kw2" val2+=ID? |
"kw3" val3+=ID? |
"kw4" val4+=ID? |
"kw5" val5+=ID? |
"kw6" val6+=ID? |
"kw7" val7+=ID? |
"kw8" val8+=ID?)*
'!';
The state machine describing the syntactic transition from "start" to "stop" involves all keywords from this rule, since all assignments are optional. Furthermore, since the parser rule allows the keywords to be in any order, any keyword can be followed by any other keyword.
In this state-machine, PdaUtil.shortestStackpruningPathTo() does a breadth-first search, i.e. the algorithm tries all possibles paths at the same time, by extending each path by one step in every iteration, until one valid path has been found. In this state machine, the amount of paths multiplies by the amount of states in each step.
Proposed fix:
Don't execute the algorithm on the "full" state machine. Instead, create a derived state machine that does not include the edges which by definition can not be part of the shortest path. That are the edges that lead to optional elements or loops.
Sounds like a good use case for Dijkstra's algorithm for graphs where the cost function could be the minimum number of remaining steps, e.g.
Greeting:
'Hello' foo=ID
("kw1" val1+=ID? |
"kw2" val2+=ID? |
)*
'!';
ignoring the val1+=ID after consuming the kw1 would be more expensive than consuming it. Should be straight forward to apply for the given search problem.
It looks like this has been fixed in the meantime. I've added a test case in http://git.eclipse.org/c/tmf/org.eclipse.xtext.git/commit/?id=4df39d675f106570cb668d0c1f865526b40afce7 Requested via bug 522520. -M. |
I assume this can be reproduced with grammars such as Rule: name=ID ('foo'* bar=ID)*; The infinite loop results in an OutOfMemoryError in Thread [main] (Suspended) PdaUtil.traceToWithPruningStack(Pda<S,P>, Iterable<S>, Iterator<P>, Predicate<S>, Predicate<S>) line: 536 PdaUtil.shortestStackpruningPathTo(Pda<S,P>, S, Iterator<P>, Predicate<S>, Predicate<S>) line: 457 PdaUtil.shortestStackpruningPathTo(Pda<S,P>, Iterator<P>, Predicate<S>) line: 447 SyntacticSequencerPDAProvider$SynTransition(SyntacticSequencerPDAProvider$SynNavigable).shortestStackpruningPathTo(Iterator<RuleCall>, Predicate<ISynState>, boolean) line: 338 SyntacticSequencerPDAProvider$SynTransition(SyntacticSequencerPDAProvider$SynNavigable).getShortestStackpruningPathToAbsorber(RuleCallStack) line: 225 ClassmodelSyntacticSequencer(AbstractSyntacticSequencer).navigateToAbsorber(ISyntacticSequencerPDAProvider$ISynFollowerOwner, INode, INode, RuleCallStack) line: 411 ClassmodelSyntacticSequencer(AbstractSyntacticSequencer).navigateToAbsorber(AbstractElement, INode) line: 399 ClassmodelSyntacticSequencer(AbstractSyntacticSequencer).finish() line: 341 SequenceFeeder.finish() line: 369 BacktrackingSemanticSequencer.createSequence(EObject, EObject) line: 426