Ensure that parallels in ForkScanner follow the same reverse-order it…

…eration, per JENKINS-38309
jenkinsci · Sep 18, 2016 · dcd2152 · dcd2152
1 parent 8ca82ae
commit dcd2152
Show file tree

Hide file tree

Showing 3 changed files with 46 additions and 18 deletions.
diff --git a/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/ForkScanner.java b/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/ForkScanner.java
@@ -50,10 +50,11 @@
  * Scanner that will scan down all forks when we hit parallel blocks before continuing, but generally runs in linear order
  * <p>Think of it as the opposite of {@link DepthFirstScanner}.
  *
- * <p>This is a fairly efficient way to visit all FlowNodes, and provides three useful guarantees:
+ * <p>This is a fairly efficient way to visit all FlowNodes, and provides four useful guarantees:
  * <ul>
- *   <li>Every FlowNode is visited, and visited EXACTLY ONCE (not true for LinearScanner)</li>
+ *   <li>Every FlowNode is visited, and visited EXACTLY ONCE (not true for LinearScanner, which misses some)</li>
  *   <li>All parallel branches are visited before we move past the parallel block (not true for DepthFirstScanner)</li>
+ *   <li>For parallels, we visit branches in reverse order (in fitting with end to start general flow)</li>
  *   <li>For EVERY block, the BlockEndNode is visited before the BlockStartNode (not true for DepthFirstScanner, with parallels)</li>
  * </ul>
  *
@@ -436,7 +437,7 @@ FlowNode hitParallelEnd(BlockEndNode endNode, List<FlowNode> parents, Collection
         ArrayDeque<FlowNode> branches = new ArrayDeque<FlowNode>();
         for (FlowNode f : parents) {
             if (!blackList.contains(f)) {
-                branches.add(f);
+                branches.addFirst(f);
             }
         }
 

diff --git a/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/FlowScannerTest.java b/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/FlowScannerTest.java
@@ -364,13 +364,19 @@ public void testParallelScan() throws Exception {
         // We're going to test the ForkScanner in more depth since this is its natural use
         scanner = new ForkScanner();
         scanner.setup(heads);
-        assertNodeOrder("ForkedScanner", scanner, 15, 14, 13, 9, 8, 6, 12, 11, 10, 7, 4, 3, 2);
+        assertNodeOrder("ForkedScanner", scanner, 15, 14, 13,
+                    12, 11, 10, 7,// One parallel
+                    9, 8, 6, // other parallel
+                4, 3, 2); // end bit
         scanner.setup(heads, Collections.singleton(exec.getNode("9")));
         assertNodeOrder("ForkedScanner", scanner, 15, 14, 13, 12, 11, 10, 7, 4, 3, 2);
 
         // Test forkscanner midflow
         scanner.setup(exec.getNode("14"));
-        assertNodeOrder("ForkedScanner", scanner, 14, 13, 9, 8, 6, 12, 11, 10, 7, 4, 3, 2);
+        assertNodeOrder("ForkedScanner", scanner, 14, 13,
+                    12, 11, 10, 7, // Last parallel
+                    9, 8, 6, // First parallel
+                4, 3, 2); // end bit
 
         // Test forkscanner inside a parallel
 

diff --git a/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/ForkScannerTest.java b/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/ForkScannerTest.java
@@ -206,21 +206,42 @@ public void testForkedScanner() throws Exception {
         Assert.assertEquals(1, start.unvisited.size());
         Assert.assertEquals(exec.getNode("4"), start.forkStart);
 
-        Assert.assertEquals(exec.getNode("9"), scanner.next());
+        /** Flow structure (ID - type)
+         2 - FlowStartNode (BlockStartNode)
+         3 - Echostep
+         4 - ParallelStep (StepStartNode) (start branches)
+         6 - ParallelStep (StepStartNode) (start branch 1), ParallelLabelAction with branchname=1
+         7 - ParallelStep (StepStartNode) (start branch 2), ParallelLabelAction with branchname=2
+         8 - EchoStep, (branch 1) parent=6
+         9 - StepEndNode, (end branch 1) startId=6, parentId=8
+         10 - EchoStep, (branch 2) parentId=7
+         11 - EchoStep, (branch 2) parentId = 10
+         12 - StepEndNode (end branch 2)  startId=7  parentId=11,
+         13 - StepEndNode (close branches), parentIds = 9,12, startId=4
+         14 - EchoStep
+         15 - FlowEndNode (BlockEndNode)
+         */
+
+        Assert.assertEquals(exec.getNode("12"), scanner.next()); //12
         Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_END, scanner.getCurrentType());
         Assert.assertEquals(ForkScanner.NodeType.NORMAL, scanner.getNextType());
-        Assert.assertEquals(exec.getNode("8"), scanner.next());
+        Assert.assertEquals(exec.getNode("11"), scanner.next());
+        Assert.assertEquals(ForkScanner.NodeType.NORMAL, scanner.getCurrentType());
+        Assert.assertEquals(exec.getNode("10"), scanner.next());
         Assert.assertEquals(ForkScanner.NodeType.NORMAL, scanner.getCurrentType());
         Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_START, scanner.getNextType());
-        Assert.assertEquals(exec.getNode("6"), scanner.next());
+        Assert.assertEquals(exec.getNode("7"), scanner.next());
         Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_START, scanner.getCurrentType());
+
+        // Next branch, branch 1 (since we visit in reverse)
         Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_END, scanner.getNextType());
-        FlowNode f = scanner.next();
+        Assert.assertEquals(exec.getNode("9"), scanner.next());
         Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_END, scanner.getCurrentType());
-        Assert.assertEquals(ForkScanner.NodeType.NORMAL, scanner.getNextType());
-        Assert.assertEquals(exec.getNode("12"), f);
-
-        // Now we test the least common ancestor bits
+        Assert.assertEquals(exec.getNode("8"), scanner.next());
+        Assert.assertEquals(ForkScanner.NodeType.NORMAL, scanner.getCurrentType());
+        Assert.assertEquals(exec.getNode("6"), scanner.next());
+        Assert.assertEquals(ForkScanner.NodeType.PARALLEL_BRANCH_START, scanner.getCurrentType());
+        Assert.assertEquals(ForkScanner.NodeType.PARALLEL_START, scanner.getNextType());
     }
 
     /** Reference the flow graphs in {@link #SIMPLE_PARALLEL_RUN} and {@link #NESTED_PARALLEL_RUN} */
@@ -445,12 +466,12 @@ public boolean apply(TestVisitor.CallEntry input) {
         //Tests for parallel handling
         // Start to end, in reverse order
 
-        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_END, 4, 9).assertEquals(parallelCalls.get(1));
-        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_START, 4, 6).assertEquals(parallelCalls.get(2));
-        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_END, 4, 12).assertEquals(parallelCalls.get(3));
+        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_END, 4, 12).assertEquals(parallelCalls.get(1));
+        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_START, 4, 7).assertEquals(parallelCalls.get(2));
+        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_END, 4, 9).assertEquals(parallelCalls.get(3));
 
-        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_START, 4, 7).assertEquals(parallelCalls.get(4));
-        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_START, 4, 7).assertEquals(parallelCalls.get(5));
+        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_BRANCH_START, 4, 6).assertEquals(parallelCalls.get(4));
+        new TestVisitor.CallEntry(TestVisitor.CallType.PARALLEL_START, 4, 6).assertEquals(parallelCalls.get(5));
 
     }