Minor improvement to cycle detection algorithm: Do not recurse into done nodes, where there is no work to do anyway.

This triggered some non-determinism that we explicitly workaround in the unit tests.

Also add a comment about a potential but unrelated optimization.

--
MOS_MIGRATED_REVID=125355303

1 files changed, 9 insertions, 4 deletions

diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 08b0f26c6b..93c8f2b552 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -978,6 +978,7 @@ public class MemoizingEvaluatorTest {
   /** @see ParallelEvaluatorTest#cycleAboveIndependentCycle() */
   @Test
   public void cycleAboveIndependentCycle() throws Exception {
+    makeGraphDeterministic();
     SkyKey aKey = GraphTester.toSkyKey("a");
     final SkyKey bKey = GraphTester.toSkyKey("b");
     SkyKey cKey = GraphTester.toSkyKey("c");
@@ -1037,8 +1038,11 @@ public class MemoizingEvaluatorTest {
   @Test
   public void cycleAndSelfEdgeWithDirtyValue() throws Exception {
     initializeTester();
-    SkyKey cycleKey1 = GraphTester.toSkyKey("cycleKey1");
-    SkyKey cycleKey2 = GraphTester.toSkyKey("cycleKey2");
+    // The cycle detection algorithm non-deterministically traverses into children nodes, so
+    // use explicit determinism.
+    makeGraphDeterministic();
+    SkyKey cycleKey1 = GraphTester.toSkyKey("ZcycleKey1");
+    SkyKey cycleKey2 = GraphTester.toSkyKey("AcycleKey2");
     tester.getOrCreate(cycleKey1).addDependency(cycleKey2).addDependency(cycleKey1)
     .setComputedValue(CONCATENATE);
     tester.getOrCreate(cycleKey2).addDependency(cycleKey1).setComputedValue(COPY);
@@ -1065,8 +1069,9 @@ public class MemoizingEvaluatorTest {
 
   @Test
   public void cycleAndSelfEdgeWithDirtyValueInSameGroup() throws Exception {
-    final SkyKey cycleKey1 = GraphTester.toSkyKey("cycleKey1");
-    final SkyKey cycleKey2 = GraphTester.toSkyKey("cycleKey2");
+    makeGraphDeterministic();
+    final SkyKey cycleKey1 = GraphTester.toSkyKey("ZcycleKey1");
+    final SkyKey cycleKey2 = GraphTester.toSkyKey("AcycleKey2");
     tester.getOrCreate(cycleKey2).addDependency(cycleKey2).setComputedValue(CONCATENATE);
     tester
         .getOrCreate(cycleKey1)