Merge pull request #16 from jenkinsci/make-depthfirstscanner-obey-ord…

…ering-JENKINS-38458 Make DepthFirstScanner obey first-last parallel branch ordering [JENKINS-38458]
jenkinsci · Sep 23, 2016 · bcd2e30 · bcd2e30
2 parents 85d91e8 + f5a98a8
commit bcd2e30
Show file tree

Hide file tree

Showing 3 changed files with 60 additions and 18 deletions.
diff --git a/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/DepthFirstScanner.java b/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/DepthFirstScanner.java
@@ -24,23 +24,34 @@
 
 package org.jenkinsci.plugins.workflow.graphanalysis;
 
+import com.google.common.base.Predicate;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Lists;
 import org.jenkinsci.plugins.workflow.graph.BlockStartNode;
 import org.jenkinsci.plugins.workflow.graph.FlowNode;
 
 import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
 import javax.annotation.concurrent.NotThreadSafe;
+import java.lang.reflect.Array;
 import java.util.ArrayDeque;
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
+import java.util.ListIterator;
 
 /** Does a simple and somewhat efficient depth-first search of all FlowNodes in the DAG.
  *
  *  <p>Iteration order: depth-first search, revisiting parallel branches once done.
- *  With parallel branches, the first branch is explored, then remaining branches are explored in reverse order.
  *
  * <p> The behavior is analogous to {@link org.jenkinsci.plugins.workflow.graph.FlowGraphWalker} but faster.
+ *  With parallel branches, the first branch is explored, then remaining branches are explored in order.
+ *  This keeps ordering compatibility with {@link org.jenkinsci.plugins.workflow.graph.FlowGraphWalker} - it can be a drop-in replacement.
+ *
  *  @author Sam Van Oort
  */
 @NotThreadSafe
@@ -63,30 +74,41 @@ protected void reset() {
 
     @Override
     protected void setHeads(@Nonnull Collection<FlowNode> heads) {
-        Iterator<FlowNode> it = heads.iterator();
-        if (it.hasNext()) {
-            FlowNode f = it.next();
-            myCurrent = f;
-            myNext = f;
+        if (heads.isEmpty()) {
+            return;
         }
-        while (it.hasNext()) {
-            queue.add(it.next());
+        ArrayList<FlowNode>  nodes = new ArrayList<FlowNode>(heads);
+        for(int i=nodes.size()-1; i >= 0; i--) {
+            queue.push(nodes.get(i));
         }
+        myCurrent = queue.pop();
+        myNext = myCurrent;
+    }
+
+    // Can be overridden with a more specific test
+    protected boolean possibleParallelStart(FlowNode f) {
+        return f instanceof BlockStartNode;
+    }
+
+    protected boolean testCandidate(FlowNode f, Collection<FlowNode> blackList) {
+        return !blackList.contains(f) && !((possibleParallelStart(f)) && visited.contains(f));
     }
 
     @Override
-    protected FlowNode next(@Nonnull FlowNode current, @Nonnull Collection<FlowNode> blackList) {
+    protected FlowNode next(@Nonnull FlowNode current, @Nonnull final Collection<FlowNode> blackList) {
         FlowNode output = null;
 
         // Walk through parents of current node
         List<FlowNode> parents = current.getParents();  // Can't be null
-        for (FlowNode f : parents) {
-            // Only ParallelStep nodes may be visited multiple times... but we can't just filter those
-            // because that's in workflow-cps plugin which depends on this one.
-            if (!blackList.contains(f) && !(f instanceof BlockStartNode && visited.contains(f))) {
-                if (output == null ) {
-                    output = f;  // Do direct assignment rather than needless push/pop
-                } else {
+        if (parents.size() == 1) {  // Common case, make it more efficient
+            FlowNode f = parents.get(0);
+            if (testCandidate(f, blackList)) {
+                output = f;
+            }
+        } else if (parents.size() > 1) { // Add the branches in reverse order
+            for(int i=parents.size()-1; i>=0; i--) {
+                FlowNode f = parents.get(i);
+                if (testCandidate(f, blackList)) {
                     queue.push(f);
                 }
             }

diff --git a/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/package-info.java b/src/main/java/org/jenkinsci/plugins/workflow/graphanalysis/package-info.java
@@ -6,6 +6,13 @@
  * visiting all nodes via internal iteration.
  *
  * <p> Static methods and a few implementations are also provided in {@link org.jenkinsci.plugins.workflow.graphanalysis.FlowScanningUtils}.
+ * <p><em>How To Pick A FlowScanner For Iteration</em></p>
+ * <ol>
+ *     <li><em>Want fast iteration, don't care about visiting every node or parallels?</em> {@link org.jenkinsci.plugins.workflow.graphanalysis.LinearScanner}</li>
+ *     <li><em>Visit every node as fast as possible?</em> {@link org.jenkinsci.plugins.workflow.graphanalysis.DepthFirstScanner}</li>
+ *     <li><em>Visit every block in a predictable order, from end to start?</em> {@link org.jenkinsci.plugins.workflow.graphanalysis.ForkScanner}</li>
+ *     <li><em>Fastest way to find preceding sibling or enclosing nodes?</em> {@link org.jenkinsci.plugins.workflow.graphanalysis.LinearBlockHoppingScanner}</li>
+ * </ol>
  */
 
 package org.jenkinsci.plugins.workflow.graphanalysis;
diff --git a/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/FlowScannerTest.java b/src/test/java/org/jenkinsci/plugins/workflow/graphanalysis/FlowScannerTest.java
@@ -26,8 +26,10 @@
 
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
+import com.google.common.collect.Iterators;
 import org.jenkinsci.plugins.workflow.cps.CpsFlowDefinition;
 import org.jenkinsci.plugins.workflow.flow.FlowExecution;
+import org.jenkinsci.plugins.workflow.graph.FlowGraphWalker;
 import org.jenkinsci.plugins.workflow.graph.FlowNode;
 import org.jenkinsci.plugins.workflow.job.WorkflowJob;
 import org.jenkinsci.plugins.workflow.job.WorkflowRun;
@@ -354,7 +356,16 @@ public void testParallelScan() throws Exception {
         // Depth first scanner and with blacklist
         scanner = new DepthFirstScanner();
         scanner.setup(heads);
-        assertNodeOrder("Depth first", scanner, 15, 14, 13, 9, 8, 6, 4, 3, 2, 12, 11, 10, 7);
+
+        // Compatibility test for ordering
+        assertNodeOrder("FlowGraphWalker", new FlowGraphWalker(exec), 15, 14, 13,
+                9, 8, 6, // Branch 1
+                4, 3, 2, // Before parallel
+                12, 11, 10, 7); // Branch 2
+        assertNodeOrder("Depth first", new FlowGraphWalker(exec), 15, 14, 13,
+                9, 8, 6, // Branch 1
+                4, 3, 2, // Before parallel
+                12, 11, 10, 7); // Branch 2
         scanner.setup(heads, Collections.singleton(exec.getNode("9")));
         assertNodeOrder("Linear", scanner, 15, 14, 13, 12, 11, 10, 7, 4, 3, 2);
 
@@ -379,7 +390,6 @@ public void testParallelScan() throws Exception {
                 4, 3, 2); // end bit
 
         // Test forkscanner inside a parallel
-
         List<FlowNode> startingPoints = Arrays.asList(exec.getNode("9"), exec.getNode("12"));
         scanner.setup(startingPoints);
         assertNodeOrder("ForkedScanner", scanner, 9, 8, 6, 12, 11, 10, 7, 4, 3, 2);
@@ -457,6 +467,9 @@ public void testNestedParallelScan() throws Exception {
         Collection<FlowNode> matches = scanner.filteredNodes(heads, null, MATCH_ECHO_STEP);
         Assert.assertEquals(7, matches.size());
 
+        scanner.setup(heads);
+        Assert.assertTrue("FlowGraphWalker differs from DepthFirstScanner", Iterators.elementsEqual(new FlowGraphWalker(exec).iterator(), scanner.iterator()));
+
 
         // We're going to test the ForkScanner in more depth since this is its natural use
         scanner = new ForkScanner();