fix and test for simple cycle

andimarek · andimarek · commit 7c6d687c2471 · 2018-03-17T21:14:04.000+11:00
diff --git a/src/main/java/graphql/util/Traverser.java b/src/main/java/graphql/util/Traverser.java
@@ -164,6 +164,7 @@ public <U> Object traverse(Collection<? extends T> roots, TraverserVisitor<? sup
             } else {
                 TraversalControl traversalControl = visitor.enter(currentContext);
                 assertNotNull(traversalControl, "result of enter must not be null");
+                this.traverserState.addVisited((T) currentContext.thisNode());
                 switch (traversalControl) {
                     case QUIT:
                         break traverseLoop;
diff --git a/src/main/java/graphql/util/TraverserState.java b/src/main/java/graphql/util/TraverserState.java
@@ -89,6 +89,10 @@ public void clear() {
         visited.clear();
     }
 
+    public void addVisited(T visited) {
+        this.visited.add(visited);
+    }
+
     public TraverserContext<T> newContext(T o, TraverserContext<T> parent) {
         return newContext(o, parent, new ConcurrentHashMap<>());
     }
diff --git a/src/main/java/graphql/util/TraverserVisitor.java b/src/main/java/graphql/util/TraverserVisitor.java
@@ -14,9 +14,6 @@ public interface TraverserVisitor<T> {
      *
      * @param context traverser context
      *
-     * @return either a value to pass to next Visitor's method during traversal
-     * or a marker to control the traversal
-     *
      * @see TraverserContext
      */
     TraversalControl enter(TraverserContext<T> context);
@@ -26,9 +23,6 @@ public interface TraverserVisitor<T> {
      *
      * @param context traverser context
      *
-     * @return either a value to pass to next Visitor's method during traversal
-     * or a marker to control the traversal
-     *
      * @see TraverserContext
      */
     TraversalControl leave(TraverserContext<T> context);
@@ -40,13 +34,10 @@ public interface TraverserVisitor<T> {
      *
      * @param context traverser context
      *
-     * @return either a value to pass to next Visitor's method during traversal
-     * or a marker to control the traversal
-     *
      * @see TraverserContext
      */
-    default TraversalControl backRef(TraverserContext<T> context) {
-        return null;
+    default void backRef(TraverserContext<T> context) {
+
     }
 
 }
diff --git a/src/test/groovy/graphql/util/TraverserTest.groovy b/src/test/groovy/graphql/util/TraverserTest.groovy
@@ -102,7 +102,6 @@ class TraverserTest extends Specification {
         given:
         def initialData = new ArrayList()
         def leaveCount = 0
-
         def visitor = [
                 enter: { TraverserContext context ->
                     context.getInitialData().add(context.thisNode().number)
@@ -169,6 +168,26 @@ class TraverserTest extends Specification {
 
         then:
         initialData == [0, 1, 2, 3]
+    }
+
+    static class Node {
+        int number
+        List<Node> children
+    }
+
+    def "simple cycle"() {
+        given:
+        def cycleRoot = new Node(number: 0, children: [])
+        cycleRoot.children.add(cycleRoot)
+
+        def visitor = Mock(TraverserVisitor)
+        when:
+        Traverser.depthFirst({ n -> n.children }).traverse(cycleRoot, visitor)
+
+        then:
+        1 * visitor.enter(_) >> TraversalControl.CONTINUE
+        1 * visitor.leave(_) >> TraversalControl.CONTINUE
+        1 * visitor.backRef({ TraverserContext context -> context.thisNode() == cycleRoot })
 
     }
 

Original file line number	Diff line number	Diff line change
`@@ -89,6 +89,10 @@ public void clear() {`
`89`	`89`	`visited.clear();`
`90`	`90`	`}`
`91`	`91`
	`92`	`+ public void addVisited(T visited) {`
	`93`	`+ this.visited.add(visited);`
	`94`	`+ }`
	`95`	`+`
`92`	`96`	`public TraverserContext<T> newContext(T o, TraverserContext<T> parent) {`
`93`	`97`	`return newContext(o, parent, new ConcurrentHashMap<>());`
`94`	`98`	`}`
Original file line number	Diff line number	Diff line change
`@@ -14,9 +14,6 @@ public interface TraverserVisitor<T> {`
`14`	`14`	`*`
`15`	`15`	`* @param context traverser context`
`16`	`16`	`*`
`17`		`- * @return either a value to pass to next Visitor's method during traversal`
`18`		`- * or a marker to control the traversal`
`19`		`- *`
`20`	`17`	`* @see TraverserContext`
`21`	`18`	`*/`
`22`	`19`	`TraversalControl enter(TraverserContext<T> context);`
`@@ -26,9 +23,6 @@ public interface TraverserVisitor<T> {`
`26`	`23`	`*`
`27`	`24`	`* @param context traverser context`
`28`	`25`	`*`
`29`		`- * @return either a value to pass to next Visitor's method during traversal`
`30`		`- * or a marker to control the traversal`
`31`		`- *`
`32`	`26`	`* @see TraverserContext`
`33`	`27`	`*/`
`34`	`28`	`TraversalControl leave(TraverserContext<T> context);`
`@@ -40,13 +34,10 @@ public interface TraverserVisitor<T> {`
`40`	`34`	`*`
`41`	`35`	`* @param context traverser context`
`42`	`36`	`*`
`43`		`- * @return either a value to pass to next Visitor's method during traversal`
`44`		`- * or a marker to control the traversal`
`45`		`- *`
`46`	`37`	`* @see TraverserContext`
`47`	`38`	`*/`
`48`		`- default TraversalControl backRef(TraverserContext<T> context) {`
`49`		`- return null;`
	`39`	`+ default void backRef(TraverserContext<T> context) {`
	`40`	`+`
`50`	`41`	`}`
`51`	`42`
`52`	`43`	`}`