Fix bug where an was-inflight-and-is-about-to-be-done NodeEntry has incomplete deps that need to be removed, and

these deps are currently duplicated in the NodeEntry's newly requested deps
GroupedList.

Also add a fast-path to GroupedListHelper#remove(List<Object> elements, Set<E> toRemove) for the incredibly common case where toRemove is empty. This saves a wasteful O(elements.size()) scan over elements. This method is unconditionally called each time a SkyFunction restart causes us to add new direct deps (with elements=<the new direct deps> and toRemove=<unfinished direct deps>); in the case where there are a ton of new direct deps, this scan entails wasted cpu and gc churn. The bug only occurs in uncommon case that there are deps to remove.

The bug has existed since GroupedList was first introduced into the codebase.

In Skyframe-land, this is only observable in nokeep_going mode because in keep_going mode "we
do not let SkyFunctions throw errors with missing deps" (quote from
comment in AbstractParallelEvaluator).

A Bazel-on-Skyframe-land example how this bug could occur in practice is PackageFunction's Skyframe hybrid globbing. If an io error is encountered during legacy globbing, the PackageFunction eagerly throws a SkyFunctionException but it has already requested the Skyframe GlobValue deps.

RELNOTES: None
PiperOrigin-RevId: 182403943

1 files changed, 11 insertions, 1 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 475e38518b..11bef3fcc2 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
@@ -343,6 +343,9 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
    * GroupedListHelper.
    */
   private static <E> List<Object> remove(List<Object> elements, Set<E> toRemove) {
+    if (toRemove.isEmpty()) {
+      return elements;
+    }
     int removedCount = 0;
     // elements.size is an upper bound of the needed size. Since normally removal happens just
     // before the list is finished and compressed, optimizing this size isn't a concern.
@@ -369,8 +372,15 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
         }
       }
     }
+    // removedCount can be larger if elements had duplicates and the duplicate was also in toRemove.
     Preconditions.checkState(
-        removedCount == toRemove.size(), "%s %s %s", elements, toRemove, newElements);
+        removedCount >= toRemove.size(),
+        "removedCount=%s, toRemove.size()=%s, elements=%s toRemove=%s newElements=%s",
+        removedCount,
+        toRemove.size(),
+        elements,
+        toRemove,
+        newElements);
     return newElements;
   }