Uploaded image for project: 'TinkerPop'
  1. TinkerPop
  2. TINKERPOP-1400

SubgraphStrategy introduces infinite recursion if filter has Vertex/Edge steps.

Details

    • Bug
    • Status: Closed
    • Major
    • Resolution: Fixed
    • 3.2.1
    • 3.2.2
    • process
    • None

    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

          Activity

            githubbot ASF GitHub Bot added a comment -

            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 <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.


            githubbot ASF GitHub Bot added a comment - 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 <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.
            githubbot ASF GitHub Bot added a comment -

            Github user analytically commented on a diff in the pull request:

            https://github.com/apache/tinkerpop/pull/374#discussion_r73747869

            — Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java —
            @@ -156,20 +182,36 @@ private static void transferLabels(final Step from, final Step to) {
            private Builder() {
            }

            • public Builder vertexCriterion(final Traversal<Vertex, ?> predicate) {
            • vertexCriterion = predicate;
              + public Builder vertices(final Traversal<Vertex, ?> vertexPredicate) {
              + this.vertexCriterion = vertexPredicate;
                • End diff –

            Best rename the local vertexCriterion to vertexPredicate too no?

            githubbot ASF GitHub Bot added a comment - Github user analytically commented on a diff in the pull request: https://github.com/apache/tinkerpop/pull/374#discussion_r73747869 — Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java — @@ -156,20 +182,36 @@ private static void transferLabels(final Step from, final Step to) { private Builder() { } public Builder vertexCriterion(final Traversal<Vertex, ?> predicate) { vertexCriterion = predicate; + public Builder vertices(final Traversal<Vertex, ?> vertexPredicate) { + this.vertexCriterion = vertexPredicate; End diff – Best rename the local vertexCriterion to vertexPredicate too no?
            githubbot ASF GitHub Bot added a comment -

            Github user twilmes commented on the issue:

            https://github.com/apache/tinkerpop/pull/374

            VOTE: +1

            githubbot ASF GitHub Bot added a comment - Github user twilmes commented on the issue: https://github.com/apache/tinkerpop/pull/374 VOTE: +1
            githubbot ASF GitHub Bot added a comment -

            Github user spmallette commented on the issue:

            https://github.com/apache/tinkerpop/pull/374

            All tests pass with `docker/build.sh -t -n -i`

            VOTE +1

            githubbot ASF GitHub Bot added a comment - Github user spmallette commented on the issue: https://github.com/apache/tinkerpop/pull/374 All tests pass with `docker/build.sh -t -n -i` VOTE +1
            githubbot ASF GitHub Bot added a comment -

            Github user asfgit closed the pull request at:

            https://github.com/apache/tinkerpop/pull/374

            githubbot ASF GitHub Bot added a comment - Github user asfgit closed the pull request at: https://github.com/apache/tinkerpop/pull/374

            People

              okram Marko A. Rodriguez
              okram Marko A. Rodriguez
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: