[
https://issues.apache.org/jira/browse/TINKERPOP-1400?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15409927#comment-15409927
]
ASF GitHub Bot commented on TINKERPOP-1400:
-------------------------------------------
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.
* Note: given the differences in strategy application code, this can not
easily go into the `tp31`-line without a rewrite. Thus, this is headed to
`master/`.
CHANGELOG
```
* Fixed a severe bug in `SubgraphStrategy`.
* Deprecated `SubgraphStrategy.Builder.vertexCriterion()/edgeCriterion()`
in favor of `vertices()/edges()`.
```
VOTE +1.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/apache/tinkerpop TINKERPOP-1400
Alternatively 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 <[email protected]>
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.
----
> SubgraphStrategy introduces infinite recursion if filter has Vertex/Edge
> steps.
> -------------------------------------------------------------------------------
>
> Key: TINKERPOP-1400
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1400
> Project: TinkerPop
> Issue Type: Bug
> Components: process
> Affects Versions: 3.2.1
> Reporter: Marko A. Rodriguez
> Assignee: Marko A. Rodriguez
>
> James from the mailing list reported:
> {code}
> 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>
> {code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
