Description
James from the mailing list reported:
gremlin> graph = TinkerFactory.createModern() ==>tinkergraph[vertices:6 edges:6] gremlin> g = graph.traversal() ==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard] gremlin> s = SubgraphStrategy.build().vertexCriterion(hasId(1)).create() ==>SubgraphStrategy gremlin> g.V().filter(hasId(1)) ==>v[1] gremlin> g.withStrategies(s).V() ==>v[1] works as expected. But if I change the predicate traversal to something slightly more complex, e.g. in('knows').hasId(1) things start to go haywire. The single step predicates works as expected in 3.1.1-incubating, 3.1.3 and 3.2.1. In 3.1.1-incubating the multi-step predicate subgraph strategy seems to end up generating the same traversal as using filter(...) but fails to execute: $ sh apache-gremlin-console-3.1.1-incubating/bin/gremlin.sh \,,,/ (o o) -----oOOo-(3)-oOOo----- plugin activated: tinkerpop.server plugin activated: tinkerpop.utilities plugin activated: tinkerpop.tinkergraph gremlin> graph = TinkerFactory.createModern() ==>tinkergraph[vertices:6 edges:6] gremlin> g = graph.traversal() ==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard] gremlin> s = SubgraphStrategy.build().vertexCriterion(__.in('knows').hasId(1)).create() ==>SubgraphStrategy gremlin> g1 = GraphTraversalSource.build().with(s).create(graph) ==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard] gremlin> g.V().filter(__.in('knows').hasId(1)).explain() ==>Traversal Explanation =========================================================================================================================================== Original Traversal [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] ConnectiveStrategy [D] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] IdentityRemovalStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] IncidentToAdjacentStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] AdjacentToIncidentStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] FilterRankingStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] MatchPredicateStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] RangeByIsCountStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] TinkerGraphStepStrategy [P] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] EngineDependentStrategy [F] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] ProfileStrategy [F] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] StandardVerificationStrategy [V] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] ComputerVerificationStrategy [V] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] Final Traversal [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] gremlin> g.V().filter(__.in('knows').hasId(1)) ==>v[2] ==>v[4] gremlin> g1.V().explain() ==>Traversal Explanation =========================================================================================================================================== Original Traversal [GraphStep([],vertex)] ConnectiveStrategy [D] [GraphStep([],vertex)] SubgraphStrategy [D] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] IdentityRemovalStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] IncidentToAdjacentStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] AdjacentToIncidentStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] FilterRankingStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] MatchPredicateStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] RangeByIsCountStrategy [O] [GraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] TinkerGraphStepStrategy [P] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] EngineDependentStrategy [F] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] ProfileStrategy [F] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] StandardVerificationStrategy [V] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] ComputerVerificationStrategy [V] [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] Final Traversal [TinkerGraphStep([],vertex), TraversalFilterStep([VertexStep(IN,[knows],vertex), HasStep([~id.eq(1)])])] gremlin> g1.V() java.lang.StackOverflowError Display stack trace? [yN] y java.lang.StackOverflowError at org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep.clone(TraversalFilterStep.java:57) at org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep.clone(TraversalFilterStep.java:35) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.clone(DefaultTraversal.java:213) at org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal.clone(DefaultGraphTraversal.java:50) at org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal.clone(DefaultGraphTraversal.java:28) at org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep.clone(ConnectiveStep.java:67) at org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep.clone(ConnectiveStep.java:36) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.clone(DefaultTraversal.java:213) at org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal.clone(DefaultGraphTraversal.java:50) at org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.DefaultGraphTraversal.clone(DefaultGraphTraversal.java:28) at org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy.lambda$apply$264(SubgraphStrategy.java:115) at java.util.stream.ForEachOps$ForEachOp$OfRef.accept(ForEachOps.java:184) at java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:175) at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1374) at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481) at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471) at java.util.stream.ForEachOps$ForEachOp.evaluateSequential(ForEachOps.java:151) at java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateSequential(ForEachOps.java:174) at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:418) at org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy.apply(SubgraphStrategy.java:102) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies.applyStrategies(DefaultTraversalStrategies.java:77) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.applyStrategies(DefaultTraversal.java:83) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.applyStrategies(DefaultTraversal.java:97) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.applyStrategies(DefaultTraversal.java:97) at org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal.applyStrategies(DefaultTraversal.java:97) [... about 1000 more repetitions of the applyStrategies(DefaultTraversal.java:97) line deleted ...] gremlin>
Attachments
Issue Links
- links to
GitHub user okram opened a pull request:
https://github.com/apache/tinkerpop/pull/374
TINKERPOP-1400: SubgraphStrategy introduces infinite recursion if filter has Vertex/Edge steps.https://issues.apache.org/jira/browse/TINKERPOP-1400
There was a severe bug in SubgraphStrategy where the traversal filters that were added for sub-graphing were being recursively applied yielded a StackOverflow. We did not have complex enough tests in SubgraphStrategyProcessTest to illicit the bug. The fix is clever using Step label markers to know if a traversal whose is having their strategy applied is a vertex/edge subgraph filter. Its clever.
CHANGELOG
```
```
VOTE +1.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/apache/tinkerpop
TINKERPOP-1400Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/374.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #374
commit 9d6a4957468a65d15180ddc31f5020255ad14f20
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-08-05T19:16:58Z
Fixed a severe bug in SubgraphStrategy where infinite recurssion occurs if the strategy is not smart about how child traverals with Vertex/EdgeSteps are analyzed. Also Deprecated vertexCriteria() method with vertices() likewise for edgeCritera() in SubGraphStrategy.Builder to be consistent with GraphFilter style (same concept). In fact, moving forward, SubGraphStrategy could take a GraphFilter.