Allow cycle detector to be injected into ParallelEvaluator, so that callers can use different cycle detection algorithms if they wish.

--
MOS_MIGRATED_REVID=131347160

6 files changed, 83 insertions, 30 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/CycleDetector.java b/src/main/java/com/google/devtools/build/skyframe/CycleDetector.java
new file mode 100644
index 0000000000..6cd1585498
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/CycleDetector.java
@@ -0,0 +1,27 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.skyframe;
+
+/**
+ * Detects cycles after a {@link ParallelEvaluator} evaluation that did not complete due to cycles.
+ *
+ * <p>Public only for the benefit of alternative graph implementations outside the skyframe package.
+ */
+public interface CycleDetector {
+  void checkForCycles(
+      Iterable<SkyKey> badRoots,
+      EvaluationResult.Builder<?> result,
+      ParallelEvaluatorContext evaluatorContext)
+      throws InterruptedException;
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
index 6d0dbfa6ff..dc394ed61c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntryVisitor.java
@@ -32,7 +32,7 @@ import java.util.concurrent.atomic.AtomicBoolean;
  * track of pending nodes.
  */
 class NodeEntryVisitor {
-  private static final ErrorClassifier NODE_ENTRY_VISITOR_ERROR_CLASSIFIER =
+  static final ErrorClassifier NODE_ENTRY_VISITOR_ERROR_CLASSIFIER =
       new ErrorClassifier() {
         @Override
         protected ErrorClassification classifyException(Exception e) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index b800207690..aee81ead3b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -33,6 +33,7 @@ import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationS
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
 import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
+import com.google.devtools.build.skyframe.ParallelEvaluatorContext.EnqueueParentBehavior;
 import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
 import java.util.ArrayList;
@@ -93,7 +94,7 @@ public final class ParallelEvaluator implements Evaluator {
   private final Receiver<Collection<SkyKey>> inflightKeysReceiver;
 
   private final ParallelEvaluatorContext evaluatorContext;
-  private final SimpleCycleDetector cycleDetector = new SimpleCycleDetector();
+  private final CycleDetector cycleDetector;
 
   public ParallelEvaluator(
       ProcessableGraph graph,
@@ -124,6 +125,7 @@ public final class ParallelEvaluator implements Evaluator {
             dirtyKeyTracker,
             createEvaluateRunnable(),
             threadCount);
+    cycleDetector = new SimpleCycleDetector();
   }
 
   public ParallelEvaluator(
@@ -138,9 +140,11 @@ public final class ParallelEvaluator implements Evaluator {
       @Nullable EvaluationProgressReceiver progressReceiver,
       DirtyKeyTracker dirtyKeyTracker,
       Receiver<Collection<SkyKey>> inflightKeysReceiver,
-      ForkJoinPool forkJoinPool) {
+      ForkJoinPool forkJoinPool,
+      CycleDetector cycleDetector) {
     this.graph = graph;
     this.inflightKeysReceiver = inflightKeysReceiver;
+    this.cycleDetector = cycleDetector;
     Preconditions.checkState(storeErrorsAlongsideValues || keepGoing);
     this.dirtyKeyTracker = Preconditions.checkNotNull(dirtyKeyTracker);
     evaluatorContext =
@@ -341,7 +345,7 @@ public final class ParallelEvaluator implements Evaluator {
             throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
           }
           evaluatorContext.signalValuesAndEnqueueIfReady(
-              skyKey, reverseDeps, state.getVersion(), /*enqueueParents=*/ true);
+              skyKey, reverseDeps, state.getVersion(), EnqueueParentBehavior.ENQUEUE);
           return DirtyOutcome.ALREADY_PROCESSED;
         case NEEDS_REBUILDING:
           maybeMarkRebuilding(state);
@@ -425,7 +429,11 @@ public final class ParallelEvaluator implements Evaluator {
               state,
               errorInfo,
               /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
-          env.commit(state, /*enqueueParents=*/ evaluatorContext.keepGoing());
+          env.commit(
+              state,
+               evaluatorContext.keepGoing()
+                   ? EnqueueParentBehavior.ENQUEUE
+                   : EnqueueParentBehavior.SIGNAL);
           if (!shouldFailFast) {
             return;
           }
@@ -463,7 +471,7 @@ public final class ParallelEvaluator implements Evaluator {
             graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps()),
             oldDeps,
             env);
-        env.commit(state, /*enqueueParents=*/true);
+          env.commit(state, EnqueueParentBehavior.ENQUEUE);
         return;
       }
 
@@ -530,10 +538,10 @@ public final class ParallelEvaluator implements Evaluator {
             skyKey,
             state,
             env.getChildErrorInfos());
-        // If the child error was catastrophic, committing this parent to the graph is not
-        // necessary, but since we don't do error bubbling in catastrophes, it doesn't violate any
-        // invariants either.
-        env.commit(state, /*enqueueParents=*/ true);
+          // If the child error was catastrophic, committing this parent to the graph is not
+          // necessary, but since we don't do error bubbling in catastrophes, it doesn't violate any
+          // invariants either.
+          env.commit(state, EnqueueParentBehavior.ENQUEUE);
         return;
       }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
index dbfd56760e..f364a71f4b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
@@ -36,6 +36,12 @@ import javax.annotation.Nullable;
  * <p>Also used during cycle detection.
  */
 class ParallelEvaluatorContext {
+  enum EnqueueParentBehavior {
+    ENQUEUE,
+    SIGNAL,
+    NO_ACTION
+  }
+
   private final QueryableGraph graph;
   private final Version graphVersion;
   private final ImmutableMap<SkyFunctionName, ? extends SkyFunction> skyFunctions;
@@ -133,27 +139,34 @@ class ParallelEvaluatorContext {
    * cycles).
    */
   void signalValuesAndEnqueueIfReady(
-      SkyKey skyKey, Iterable<SkyKey> keys, Version version, boolean enqueueParents)
+      SkyKey skyKey, Iterable<SkyKey> keys, Version version, EnqueueParentBehavior enqueueParents)
       throws InterruptedException {
     // No fields of the entry are needed here, since we're just enqueuing for evaluation, but more
     // importantly, these hints are not respected for not-done nodes. If they are, we may need to
     // alter this hint.
     Map<SkyKey, ? extends NodeEntry> batch = graph.getBatch(skyKey, Reason.SIGNAL_DEP, keys);
-    if (enqueueParents) {
-      for (SkyKey key : keys) {
-        NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
-        if (entry.signalDep(version)) {
-          getVisitor().enqueueEvaluation(key);
+    switch (enqueueParents) {
+      case ENQUEUE:
+        for (SkyKey key : keys) {
+          NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
+          if (entry.signalDep(version)) {
+            getVisitor().enqueueEvaluation(key);
+          }
         }
-      }
-    } else {
-      for (SkyKey key : keys) {
-        NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
-        if (!entry.isDone()) {
-          // In cycles, we can have parents that are already done.
-          entry.signalDep(version);
+        return;
+      case SIGNAL:
+        for (SkyKey key : keys) {
+          NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
+          if (!entry.isDone()) {
+            // In cycles, we can have parents that are already done.
+            entry.signalDep(version);
+          }
         }
-      }
+        return;
+      case NO_ACTION:
+        return;
+      default:
+        throw new IllegalStateException(enqueueParents + ", " + skyKey);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java b/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
index 6a736b2f4f..1c41fa56c8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
@@ -25,6 +25,7 @@ import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.ParallelEvaluatorContext.EnqueueParentBehavior;
 import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
@@ -41,10 +42,11 @@ import javax.annotation.Nullable;
  * Depth-first implementation of cycle detection after a {@link ParallelEvaluator} evaluation has
  * completed with at least one root unfinished.
  */
-class SimpleCycleDetector {
+class SimpleCycleDetector implements CycleDetector {
   private static final Logger logger = Logger.getLogger(SimpleCycleDetector.class.getName());
 
-  void checkForCycles(
+  @Override
+  public void checkForCycles(
       Iterable<SkyKey> badRoots,
       EvaluationResult.Builder<?> result,
       ParallelEvaluatorContext evaluatorContext)
@@ -161,7 +163,7 @@ class SimpleCycleDetector {
                 evaluatorContext);
         env.setError(
             entry, ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/ false);
-        env.commit(entry, /*enqueueParents=*/ false);
+        env.commit(entry, EnqueueParentBehavior.SIGNAL);
       } else {
         entry = evaluatorContext.getGraph().get(null, Reason.CYCLE_CHECKING, key);
       }
@@ -220,7 +222,7 @@ class SimpleCycleDetector {
           // Add in this cycle.
           allErrors.add(ErrorInfo.fromCycle(cycleInfo));
           env.setError(entry, ErrorInfo.fromChildErrors(key, allErrors), /*isTransient=*/ false);
-          env.commit(entry, /*enqueueParents=*/ false);
+          env.commit(entry, EnqueueParentBehavior.SIGNAL);
           continue;
         } else {
           // We need to return right away in the noKeepGoing case, so construct the cycle (with the
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index ec84b1b33e..a15522025b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -35,6 +35,7 @@ import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.ParallelEvaluatorContext.EnqueueParentBehavior;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
@@ -515,7 +516,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
    * <p>The node entry is informed if the node's value and error are definitive via the flag {@code
    * completeValue}.
    */
-  void commit(NodeEntry primaryEntry, boolean enqueueParents) throws InterruptedException {
+  void commit(NodeEntry primaryEntry, EnqueueParentBehavior enqueueParents)
+      throws InterruptedException {
     // Construct the definitive error info, if there is one.
     finalizeErrorInfo();
 
@@ -534,7 +536,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       valueWithMetadata = ValueWithMetadata.error(errorInfo, events);
     } else {
       // We must be enqueueing parents if we have a value.
-      Preconditions.checkState(enqueueParents, "%s %s", skyKey, primaryEntry);
+      Preconditions.checkState(
+          enqueueParents == EnqueueParentBehavior.ENQUEUE, "%s %s", skyKey, primaryEntry);
       valueWithMetadata = ValueWithMetadata.normal(value, errorInfo, events);
     }
     if (!oldDeps.isEmpty()) {