Stop converting temporary direct deps to a set. In almost all cases, this conversion is unnecessary and wasteful. In the remaining cases, the set conversion can be explicit.

--
MOS_MIGRATED_REVID=122294939

7 files changed, 81 insertions, 44 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
index 393b05dc5a..7f0db7839c 100644
--- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
+++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -122,6 +122,23 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
     return elements.isEmpty();
   }
 
+  /**
+   * Returns true if this list contains {@code needle}. Takes time proportional to list size. Call
+   * {@link #toSet} instead and use the result if doing multiple contains checks.
+   */
+  public boolean expensiveContains(T needle) {
+    for (Object obj : elements) {
+      if (obj instanceof List) {
+        if (((List) obj).contains(needle)) {
+          return true;
+        }
+      } else if (obj.equals(needle)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   private static final Object EMPTY_LIST = new Object();
 
   public Object compress() {
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index 9b4a9720a3..95a7ca8ae5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -388,8 +388,8 @@ public class BuildingState {
    *
    * @see NodeEntry#getTemporaryDirectDeps()
    */
-  Set<SkyKey> getDirectDepsForBuild() {
-    return directDeps.toSet();
+  GroupedList<SkyKey> getDirectDepsForBuild() {
+    return directDeps;
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index 52b2ffba2a..4215f0e495 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 
 import java.util.Collection;
@@ -120,7 +121,7 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
-  public Set<SkyKey> getTemporaryDirectDeps() {
+  public GroupedList<SkyKey> getTemporaryDirectDeps() {
     return getDelegate().getTemporaryDirectDeps();
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 7b885b8ebd..56bcd05024 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -415,10 +415,11 @@ public class InMemoryNodeEntry implements NodeEntry {
   public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
     Preconditions.checkState(!isDone(), this);
     if (!isDirty()) {
-      return getTemporaryDirectDeps();
+      return Iterables.concat(getTemporaryDirectDeps());
     } else {
       return Iterables.concat(
-          getTemporaryDirectDeps(), buildingState.getAllRemainingDirtyDirectDeps());
+          Iterables.concat(getTemporaryDirectDeps()),
+          buildingState.getAllRemainingDirtyDirectDeps());
     }
   }
 
@@ -428,7 +429,7 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
-  public synchronized Set<SkyKey> getTemporaryDirectDeps() {
+  public synchronized GroupedList<SkyKey> getTemporaryDirectDeps() {
     Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
     return buildingState.getDirectDepsForBuild();
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 06ff375fae..cdda90ea9f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -297,7 +297,9 @@ public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGr
                   // child -- because of our compact storage of rdeps, checking which list
                   // contains this parent could be expensive.
                   Set<SkyKey> signalingDeps =
-                      entry.isDone() ? ImmutableSet.<SkyKey>of() : entry.getTemporaryDirectDeps();
+                      entry.isDone()
+                          ? ImmutableSet.<SkyKey>of()
+                          : entry.getTemporaryDirectDeps().toSet();
                   Iterable<SkyKey> directDeps =
                       entry.isDone()
                           ? entry.getDirectDeps()
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
index d9f5c87676..924771a232 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 
 import java.util.Collection;
@@ -284,11 +285,11 @@ public interface NodeEntry extends ThinNodeEntry {
   Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps();
 
   /**
-   * Returns the set of direct dependencies. This may only be called while the node is being
-   * evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
+   * Returns the {@link GroupedList} of direct dependencies. This may only be called while the node
+   * is being evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
    */
   @ThreadSafe
-  Set<SkyKey> getTemporaryDirectDeps();
+  GroupedList<SkyKey> getTemporaryDirectDeps();
 
   @ThreadSafe
   boolean noDepsLastBuild();
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 51c393a8b6..74ba24c999 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -39,6 +39,7 @@ import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.util.BlazeClock;
+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.EvaluationProgressReceiver.EvaluationState;
@@ -268,25 +269,36 @@ public final class ParallelEvaluator implements Evaluator {
           }
         };
 
-    private SkyFunctionEnvironment(SkyKey skyKey, Set<SkyKey> directDeps, ValueVisitor visitor) {
+    private SkyFunctionEnvironment(
+        SkyKey skyKey, GroupedList<SkyKey> directDeps, ValueVisitor visitor) {
       this(skyKey, directDeps, null, visitor);
     }
 
-    private SkyFunctionEnvironment(SkyKey skyKey, Set<SkyKey> directDeps,
-        @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo, ValueVisitor visitor) {
+    private SkyFunctionEnvironment(
+        SkyKey skyKey,
+        GroupedList<SkyKey> directDeps,
+        @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
+        ValueVisitor visitor) {
       this.skyKey = skyKey;
       this.directDeps = Collections.unmodifiableMap(
           batchPrefetch(directDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey));
       this.bubbleErrorInfo = bubbleErrorInfo;
       this.visitor = visitor;
+      Preconditions.checkState(
+          !this.directDeps.containsKey(ErrorTransienceValue.KEY),
+          "%s cannot have a dep on ErrorTransienceValue during building",
+          skyKey);
     }
 
     private Map<SkyKey, NodeEntry> batchPrefetch(
-        Set<SkyKey> keys, boolean assertDone, SkyKey keyForDebugging) {
-      Map<SkyKey, NodeEntry> batchMap = graph.getBatch(keys);
-      if (batchMap.size() != keys.size()) {
-        throw new IllegalStateException("Missing keys for " + keyForDebugging + ": "
-            + Sets.difference(keys, batchMap.keySet()));
+        GroupedList<SkyKey> keys, boolean assertDone, SkyKey keyForDebugging) {
+      Map<SkyKey, NodeEntry> batchMap = graph.getBatch(Iterables.concat(keys));
+      if (batchMap.size() != keys.numElements()) {
+        throw new IllegalStateException(
+            "Missing keys for "
+                + keyForDebugging
+                + ": "
+                + Sets.difference(keys.toSet(), batchMap.keySet()));
       }
       if (assertDone) {
         for (Map.Entry<SkyKey, NodeEntry> entry : batchMap.entrySet()) {
@@ -311,14 +323,16 @@ public final class ParallelEvaluator implements Evaluator {
       }
       if (storedEventFilter.storeEvents()) {
         // Only do the work of processing children if we're going to store events.
-        Set<SkyKey> depKeys = graph.get(skyKey).getTemporaryDirectDeps();
-        Map<SkyKey, SkyValue> deps = getValuesMaybeFromError(depKeys, bubbleErrorInfo);
-        if (!missingChildren && depKeys.size() != deps.size()) {
+        GroupedList<SkyKey> depKeys = graph.get(skyKey).getTemporaryDirectDeps();
+        Map<SkyKey, SkyValue> deps =
+            getValuesMaybeFromError(
+                Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements());
+        if (!missingChildren && depKeys.numElements() != deps.size()) {
           throw new IllegalStateException(
               "Missing keys for "
                   + skyKey
                   + ": "
-                  + Sets.difference(depKeys, deps.keySet())
+                  + Sets.difference(depKeys.toSet(), deps.keySet())
                   + ", "
                   + graph.get(skyKey));
         }
@@ -388,9 +402,11 @@ public final class ParallelEvaluator implements Evaluator {
     }
 
     private Map<SkyKey, SkyValue> getValuesMaybeFromError(
-        Set<SkyKey> keys, @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo) {
+        Iterable<SkyKey> keys,
+        @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
+        int keySize) {
       ImmutableMap.Builder<SkyKey, SkyValue> builder = ImmutableMap.builder();
-      ArrayList<SkyKey> missingKeys = new ArrayList<>(keys.size());
+      ArrayList<SkyKey> missingKeys = new ArrayList<>(keySize);
       for (SkyKey key : keys) {
         NodeEntry entry = directDeps.get(key);
         if (entry != null) {
@@ -417,7 +433,8 @@ public final class ParallelEvaluator implements Evaluator {
           !depKeys.contains(ErrorTransienceValue.KEY),
           "Error transience key cannot be in requested deps of %s",
           skyKey);
-      Map<SkyKey, SkyValue> values = getValuesMaybeFromError(depKeys, bubbleErrorInfo);
+      Map<SkyKey, SkyValue> values =
+          getValuesMaybeFromError(depKeys, bubbleErrorInfo, depKeys.size());
       for (Map.Entry<SkyKey, SkyValue> depEntry : values.entrySet()) {
         SkyKey depKey = depEntry.getKey();
         SkyValue depValue = depEntry.getValue();
@@ -933,16 +950,9 @@ public final class ParallelEvaluator implements Evaluator {
         return;
       }
 
-      // TODO(bazel-team): Once deps are requested in a deterministic order within a group, or the
-      // framework is resilient to rearranging group order, change this so that
-      // SkyFunctionEnvironment "follows along" as the node builder runs, iterating through the
-      // direct deps that were requested on a previous run. This would allow us to avoid the
-      // conversion of the direct deps into a set.
-      Set<SkyKey> directDeps = state.getTemporaryDirectDeps();
-      Preconditions.checkState(!directDeps.contains(ErrorTransienceValue.KEY),
-          "%s cannot have a dep on ErrorTransienceValue during building: %s", skyKey, state);
       // Get the corresponding SkyFunction and call it on this value.
-      SkyFunctionEnvironment env = new SkyFunctionEnvironment(skyKey, directDeps, visitor);
+      SkyFunctionEnvironment env =
+          new SkyFunctionEnvironment(skyKey, state.getTemporaryDirectDeps(), visitor);
       SkyFunctionName functionName = skyKey.functionName();
       SkyFunction factory = skyFunctions.get(functionName);
       Preconditions.checkState(factory != null,
@@ -1038,8 +1048,8 @@ public final class ParallelEvaluator implements Evaluator {
         NodeEntry childErrorEntry = Preconditions.checkNotNull(graph.get(childErrorKey),
             "skyKey: %s, state: %s childErrorKey: %s", skyKey, state, childErrorKey);
         Preconditions.checkState(
-            !state.getTemporaryDirectDeps().contains(childErrorKey),
-            "Done error was already know: %s %s %s %s",
+            !state.getTemporaryDirectDeps().expensiveContains(childErrorKey),
+            "Done error was already known: %s %s %s %s",
             skyKey,
             state,
             childErrorKey,
@@ -1448,7 +1458,7 @@ public final class ParallelEvaluator implements Evaluator {
           continue;
         }
         if (visitor.isInflight(bubbleParent)
-            && bubbleParentEntry.getTemporaryDirectDeps().contains(errorKey)) {
+            && bubbleParentEntry.getTemporaryDirectDeps().expensiveContains(errorKey)) {
           // Only bubble up to parent if it's part of this build. If this node was dirtied and
           // re-evaluated, but in a build without this parent, we may try to bubble up to that
           // parent. Don't -- it's not part of the build.
@@ -1488,7 +1498,7 @@ public final class ParallelEvaluator implements Evaluator {
         }
       }
       SkyFunctionEnvironment env =
-          new SkyFunctionEnvironment(parent, ImmutableSet.<SkyKey>of(), bubbleErrorInfo, visitor);
+          new SkyFunctionEnvironment(parent, new GroupedList<SkyKey>(), bubbleErrorInfo, visitor);
       externalInterrupt = externalInterrupt || Thread.currentThread().isInterrupted();
       try {
         // This build is only to check if the parent node can give us a better error. We don't
@@ -1701,12 +1711,13 @@ public final class ParallelEvaluator implements Evaluator {
           // error.
           Preconditions.checkState(entry.isReady(), "%s not ready. ValueEntry: %s", key, entry);
         } else if (!entry.isReady()) {
-          removeIncompleteChildrenForCycle(key, entry, entry.getTemporaryDirectDeps());
+          removeIncompleteChildrenForCycle(
+              key, entry, Iterables.concat(entry.getTemporaryDirectDeps()));
         }
         maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
-        Set<SkyKey> directDeps = entry.getTemporaryDirectDeps();
+        GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps();
         // Find out which children have errors. Similar logic to that in Evaluate#run().
-        List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(directDeps);
+        List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(Iterables.concat(directDeps));
         Preconditions.checkState(!errorDeps.isEmpty(),
             "Value %s was not successfully evaluated, but had no child errors. ValueEntry: %s", key,
             entry);
@@ -1758,7 +1769,9 @@ public final class ParallelEvaluator implements Evaluator {
           // Construct error info for this node. Get errors from children, which are all done
           // except possibly for the cycleChild.
           List<ErrorInfo> allErrors =
-              getChildrenErrors(entry.getTemporaryDirectDeps(), /*unfinishedChild=*/cycleChild);
+              getChildrenErrors(
+                  Iterables.concat(entry.getTemporaryDirectDeps()), /*unfinishedChild=*/
+                  cycleChild);
           CycleInfo cycleInfo = new CycleInfo(cycle);
           // Add in this cycle.
           allErrors.add(ErrorInfo.fromCycle(cycleInfo));
@@ -1775,7 +1788,7 @@ public final class ParallelEvaluator implements Evaluator {
       }
 
       // This node is not yet known to be in a cycle. So process its children.
-      Iterable<SkyKey> children = entry.getTemporaryDirectDeps();
+      Iterable<SkyKey> children = Iterables.concat(entry.getTemporaryDirectDeps());
       if (Iterables.isEmpty(children)) {
         continue;
       }
@@ -1864,7 +1877,9 @@ public final class ParallelEvaluator implements Evaluator {
    */
   private void removeDescendantsOfCycleValue(SkyKey key, NodeEntry entry,
       @Nullable SkyKey cycleChild, Iterable<SkyKey> toVisit, int cycleLength) {
-    Set<SkyKey> unvisitedDeps = new HashSet<>(entry.getTemporaryDirectDeps());
+    GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps();
+    Set<SkyKey> unvisitedDeps = Sets.newHashSetWithExpectedSize(directDeps.numElements());
+    Iterables.addAll(unvisitedDeps, Iterables.concat(directDeps));
     unvisitedDeps.remove(cycleChild);
     // Remove any children from this node that are not part of the cycle we just found. They are
     // irrelevant to the node as it stands, and if they are deleted from the graph because they are