Stop storing a set in GroupedListHelper to deduplicate SkyKey dep requests. Instead, deduplicate when the helper is actually added to a GroupedList.

--
MOS_MIGRATED_REVID=136145321

8 files changed, 258 insertions, 202 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 7f0db7839c..a6f9fbe683 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
@@ -18,7 +18,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.collect.CompactHashSet;
-
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
@@ -56,15 +55,48 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
     this.elements = new ArrayList<>(elements);
   }
 
-  /** Appends the list constructed in helper to this list. */
-  public void append(GroupedListHelper<T> helper) {
+  /**
+   * Appends the list constructed in {@code helper} to this list. Returns the elements of {@code
+   * helper}, uniquified.
+   */
+  @SuppressWarnings("unchecked") // Cast to T and List<T>.
+  public Set<T> append(GroupedListHelper<T> helper) {
     Preconditions.checkState(helper.currentGroup == null, "%s %s", this, helper);
     // Do a check to make sure we don't have lists here. Note that if helper.elements is empty,
     // Iterables.getFirst will return null, and null is not instanceof List.
     Preconditions.checkState(!(Iterables.getFirst(helper.elements, null) instanceof List),
         "Cannot make grouped list of lists: %s", helper);
-    elements.addAll(helper.groupedList);
-    size += helper.size();
+    Set<T> uniquifier = CompactHashSet.createWithExpectedSize(helper.groupedList.size());
+    for (Object item : helper.groupedList) {
+      if (item instanceof List) {
+        // Optimize for the case that elements in this list are unique.
+        ImmutableList.Builder<T> dedupedList = null;
+        List<T> list = (List<T>) item;
+        for (int i = 0; i < list.size(); i++) {
+          T elt = list.get(i);
+          if (!uniquifier.add(elt)) {
+            if (dedupedList == null) {
+              dedupedList = ImmutableList.builder();
+              dedupedList.addAll(list.subList(0, i));
+            }
+          } else if (dedupedList != null) {
+            dedupedList.add(elt);
+          }
+        }
+        if (dedupedList == null) {
+          elements.add(list);
+        } else {
+          List<T> filteredList = dedupedList.build();
+          if (!filteredList.isEmpty()) {
+            elements.add(filteredList);
+          }
+        }
+      } else if (uniquifier.add((T) item)) {
+        elements.add(item);
+      }
+    }
+    size += uniquifier.size();
+    return uniquifier;
   }
 
   public void appendGroup(Collection<T> group) {
@@ -343,25 +375,28 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
   /**
    * Builder-like object for GroupedLists. An already-existing grouped list is appended to by
    * constructing a helper, mutating it, and then appending that helper to the grouped list.
+   *
+   * <p>Duplicate elements may be encountered while iterating through this object.
    */
   public static class GroupedListHelper<E> implements Iterable<E> {
     // Non-final only for removal.
     private List<Object> groupedList;
     private List<E> currentGroup = null;
-    private final CompactHashSet<E> elements;
+    private final List<E> elements;
 
     public GroupedListHelper() {
       // Optimize for short lists.
       groupedList = new ArrayList<>(1);
-      elements = CompactHashSet.create();
+      elements = new ArrayList<>(1);
     }
 
     /** Create with a copy of the contents of {@param elements} as the initial group. */
-    private GroupedListHelper(Collection<E> elements) {
+    private GroupedListHelper(E element) {
       // Optimize for short lists.
       groupedList = new ArrayList<>(1);
-      addItem(elements, groupedList);
-      this.elements = CompactHashSet.create(elements);
+      groupedList.add(element);
+      this.elements = new ArrayList<>(1);
+      this.elements.add(element);
     }
 
     /**
@@ -369,7 +404,7 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
      * goes in a group of its own.
      */
     public void add(E elt) {
-      Preconditions.checkState(elements.add(Preconditions.checkNotNull(elt)), "%s %s", elt, this);
+      elements.add(Preconditions.checkNotNull(elt, "%s %s", elt, this));
       if (currentGroup == null) {
         groupedList.add(elt);
       } else {
@@ -384,9 +419,7 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
      */
     public void remove(Set<E> toRemove) {
       groupedList = GroupedList.remove(groupedList, toRemove);
-      int oldSize = size();
       elements.removeAll(toRemove);
-      Preconditions.checkState(oldSize == size() + toRemove.size(), "%s %s", toRemove, this);
     }
 
     /**
@@ -406,31 +439,22 @@ public class GroupedList<T> implements Iterable<Collection<T>> {
       currentGroup = null;
     }
 
-    /** Returns true if elt is present in the list. */
+    /**
+     * Returns true if elt is present in the list. Takes time proportional to the list size, so
+     * should not be called routinely.
+     */
     public boolean contains(E elt) {
       return elements.contains(elt);
     }
 
-    private int size() {
-      return elements.size();
-    }
-
-    /** Returns true if list is empty. */
-    public boolean isEmpty() {
-      return elements.isEmpty();
-    }
-
     @Override
     public Iterator<E> iterator() {
       return elements.iterator();
     }
 
-    /** Create a GroupedListHelper from a collection of elements, all put in the same group.*/
-    public static <F> GroupedListHelper<F> create(Collection<F> elements) {
-      GroupedListHelper<F> helper = new GroupedListHelper<>(elements);
-      Preconditions.checkState(helper.elements.size() == elements.size(),
-          "%s %s", helper, elements);
-      return helper;
+    /** Create a GroupedListHelper from a single element. */
+    public static <F> GroupedListHelper<F> create(F element) {
+      return new GroupedListHelper<>(element);
     }
 
     @Override
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 47a9e616dd..2152fb34b0 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -141,8 +141,8 @@ public abstract class DelegatingNodeEntry implements NodeEntry {
   }
 
   @Override
-  public void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
-    getDelegate().addTemporaryDirectDeps(helper);
+  public Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
+    return getDelegate().addTemporaryDirectDeps(helper);
   }
 
   @Override
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 82d692201d..4c8ebce871 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -473,9 +473,9 @@ public class InMemoryNodeEntry implements NodeEntry {
   }
 
   @Override
-  public synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
+  public synchronized Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
     Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this);
-    getTemporaryDirectDeps().append(helper);
+    return getTemporaryDirectDeps().append(helper);
   }
 
   @Override
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 ee75ac3cf1..b86d4712a4 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -351,8 +351,12 @@ public interface NodeEntry extends ThinNodeEntry {
   @ThreadSafe
   void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps);
 
+  /**
+   * Adds the temporary direct deps given in {@code helper} and returns the set of unique deps
+   * added.
+   */
   @ThreadSafe
-  void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
+  Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
 
   /**
    * Add a group of direct deps to the node. May only be called with a {@link Collection} returned
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 ee3ac7290b..727b8395e9 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -279,7 +279,7 @@ public final class ParallelEvaluator implements Evaluator {
                 // for error bubbling) and throw an exception coming from it.
                 SkyKey errorKey = entry.getKey();
                 NodeEntry errorEntry = entry.getValue();
-                state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(errorKey)));
+                state.addTemporaryDirectDeps(GroupedListHelper.create(errorKey));
                 errorEntry.checkIfDoneForDirtyReverseDep(skyKey);
                 // Perform the necessary bookkeeping for any deps that are not being used.
                 for (Entry<SkyKey, ? extends NodeEntry> depEntry : entriesToCheck.entrySet()) {
@@ -344,138 +344,143 @@ public final class ParallelEvaluator implements Evaluator {
     @Override
     public void run() {
       try {
-      NodeEntry state = Preconditions.checkNotNull(
-          graph.get(null, Reason.EVALUATION, skyKey),
-          skyKey);
-      Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
-      if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
-        return;
-      }
+        NodeEntry state =
+            Preconditions.checkNotNull(graph.get(null, Reason.EVALUATION, skyKey), skyKey);
+        Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
+        if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
+          return;
+        }
 
-      Set<SkyKey> oldDeps = state.getAllRemainingDirtyDirectDeps();
-      SkyFunctionEnvironment env =
-          new SkyFunctionEnvironment(
-              skyKey, state.getTemporaryDirectDeps(), oldDeps, evaluatorContext);
-      SkyFunctionName functionName = skyKey.functionName();
-      SkyFunction factory =
-          Preconditions.checkNotNull(
-              evaluatorContext.getSkyFunctions().get(functionName),
-              "Unable to find SkyFunction '%s' for node with key %s, %s",
-              functionName,
-              skyKey,
-              state);
+        Set<SkyKey> oldDeps = state.getAllRemainingDirtyDirectDeps();
+        SkyFunctionEnvironment env =
+            new SkyFunctionEnvironment(
+                skyKey, state.getTemporaryDirectDeps(), oldDeps, evaluatorContext);
+        SkyFunctionName functionName = skyKey.functionName();
+        SkyFunction factory =
+            Preconditions.checkNotNull(
+                evaluatorContext.getSkyFunctions().get(functionName),
+                "Unable to find SkyFunction '%s' for node with key %s, %s",
+                functionName,
+                skyKey,
+                state);
 
-      SkyValue value = null;
-      long startTime = BlazeClock.instance().nanoTime();
-      try {
-        value = factory.compute(skyKey, env);
-      } catch (final SkyFunctionException builderException) {
-        ReifiedSkyFunctionException reifiedBuilderException =
-            new ReifiedSkyFunctionException(builderException, skyKey);
-        // In keep-going mode, we do not let SkyFunctions throw errors with missing deps -- we will
-        // restart them when their deps are done, so we can have a definitive error and definitive
-        // graph structure, thus avoiding non-determinism. It's completely reasonable for
-        // SkyFunctions to throw eagerly because they do not know if they are in keep-going mode.
-        // Propagated transitive errors are treated the same as missing deps.
-        if ((!evaluatorContext.keepGoing() || !env.valuesMissing())
-            && reifiedBuilderException.getRootCauseSkyKey().equals(skyKey)) {
-          boolean shouldFailFast =
-              !evaluatorContext.keepGoing() || builderException.isCatastrophic();
-          if (shouldFailFast) {
+        SkyValue value = null;
+        long startTime = BlazeClock.instance().nanoTime();
+        try {
+          value = factory.compute(skyKey, env);
+        } catch (final SkyFunctionException builderException) {
+          ReifiedSkyFunctionException reifiedBuilderException =
+              new ReifiedSkyFunctionException(builderException, skyKey);
+          // In keep-going mode, we do not let SkyFunctions throw errors with missing deps -- we
+          // will restart them when their deps are done, so we can have a definitive error and
+          // definitive graph structure, thus avoiding non-determinism. It's completely reasonable
+          // for SkyFunctions to throw eagerly because they do not know if they are in keep-going
+          // mode.
+          // Propagated transitive errors are treated the same as missing deps.
+          if ((!evaluatorContext.keepGoing() || !env.valuesMissing())
+              && reifiedBuilderException.getRootCauseSkyKey().equals(skyKey)) {
+            boolean shouldFailFast =
+                !evaluatorContext.keepGoing() || builderException.isCatastrophic();
+            if (shouldFailFast) {
               // After we commit this error to the graph but before the doMutatingEvaluation call
               // completes with the error there is a race-like opportunity for the error to be used,
               // either by an in-flight computation or by a future computation.
               if (!evaluatorContext.getVisitor().preventNewEvaluations()) {
-              // This is not the first error encountered, so we ignore it so that we can terminate
-              // with the first error.
-              return;
+                // This is not the first error encountered, so we ignore it so that we can terminate
+                // with the first error.
+                return;
+              }
             }
-          }
 
-          Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
-              evaluatorContext.getBatchValues(
-                  skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps());
-          boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
-          for (NodeEntry depEntry :
-              Iterables.concat(env.getDirectDepsValues(), newlyRequestedDeps.values())) {
-            if (!isDoneForBuild(depEntry)) {
-              continue;
+            Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
+                evaluatorContext.getBatchValues(
+                    skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps());
+            boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
+            for (NodeEntry depEntry :
+                Iterables.concat(env.getDirectDepsValues(), newlyRequestedDeps.values())) {
+              if (!isDoneForBuild(depEntry)) {
+                continue;
+              }
+              ErrorInfo depError = depEntry.getErrorInfo();
+              if (depError != null) {
+                isTransitivelyTransient |= depError.isTransient();
+              }
             }
-            ErrorInfo depError = depEntry.getErrorInfo();
-            if (depError != null) {
-              isTransitivelyTransient |= depError.isTransient();
+            ErrorInfo errorInfo =
+                ErrorInfo.fromException(reifiedBuilderException, isTransitivelyTransient);
+            registerNewlyDiscoveredDepsForDoneEntry(
+                skyKey, state, newlyRequestedDeps, oldDeps, env);
+            env.setError(
+                state, errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
+            env.commit(
+                state,
+                evaluatorContext.keepGoing()
+                    ? EnqueueParentBehavior.ENQUEUE
+                    : EnqueueParentBehavior.SIGNAL);
+            if (!shouldFailFast) {
+              return;
             }
+            throw SchedulerException.ofError(errorInfo, skyKey);
           }
-          ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException,
-              isTransitivelyTransient);
-          registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env);
-          env.setError(
-              state,
-              errorInfo,
-              /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
-          env.commit(
-              state,
-               evaluatorContext.keepGoing()
-                   ? EnqueueParentBehavior.ENQUEUE
-                   : EnqueueParentBehavior.SIGNAL);
-          if (!shouldFailFast) {
-            return;
-          }
-          throw SchedulerException.ofError(errorInfo, skyKey);
-        }
-      } catch (RuntimeException re) {
-        // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output
-        // some context together with the exception.
-        String msg = prepareCrashMessage(skyKey, state.getInProgressReverseDeps());
-        RuntimeException ex = new RuntimeException(msg, re);
+        } catch (RuntimeException re) {
+          // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output
+          // some context together with the exception.
+          String msg = prepareCrashMessage(skyKey, state.getInProgressReverseDeps());
+          RuntimeException ex = new RuntimeException(msg, re);
           evaluatorContext.getVisitor().noteCrash(ex);
-        throw ex;
-      } finally {
-        env.doneBuilding();
-        long elapsedTimeNanos =  BlazeClock.instance().nanoTime() - startTime;
-        if (elapsedTimeNanos > 0)  {
-          evaluatorContext.getProgressReceiver().computed(skyKey, elapsedTimeNanos);
-          Profiler.instance().logSimpleTaskDuration(startTime, elapsedTimeNanos,
-              ProfilerTask.SKYFUNCTION, skyKey);
+          throw ex;
+        } finally {
+          env.doneBuilding();
+          long elapsedTimeNanos = BlazeClock.instance().nanoTime() - startTime;
+          if (elapsedTimeNanos > 0) {
+            evaluatorContext.getProgressReceiver().computed(skyKey, elapsedTimeNanos);
+            Profiler.instance()
+                .logSimpleTaskDuration(
+                    startTime, elapsedTimeNanos, ProfilerTask.SKYFUNCTION, skyKey);
+          }
         }
-      }
 
-      GroupedListHelper<SkyKey> newDirectDeps = env.getNewlyRequestedDeps();
+        GroupedListHelper<SkyKey> newDirectDeps = env.getNewlyRequestedDeps();
 
-      if (value != null) {
-        Preconditions.checkState(!env.valuesMissing(), "Evaluation of %s returned non-null value "
-            + "but requested dependencies that weren't computed yet (one of %s), ValueEntry: %s",
-            skyKey, newDirectDeps, state);
-        env.setValue(value);
-        registerNewlyDiscoveredDepsForDoneEntry(
-            skyKey,
-            state,
-            graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps()),
-            oldDeps,
-            env);
+        if (value != null) {
+          Preconditions.checkState(
+              !env.valuesMissing(),
+              "Evaluation of %s returned non-null value but requested dependencies that weren't "
+                  + "computed yet (one of %s), NodeEntry: %s",
+              skyKey,
+              newDirectDeps,
+              state);
+          env.setValue(value);
+          registerNewlyDiscoveredDepsForDoneEntry(
+              skyKey,
+              state,
+              graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps()),
+              oldDeps,
+              env);
           env.commit(state, EnqueueParentBehavior.ENQUEUE);
-        return;
-      }
+          return;
+        }
 
-      if (env.getDepErrorKey() != null) {
-        Preconditions.checkState(
-            !evaluatorContext.keepGoing(), "%s %s %s", skyKey, state, env.getDepErrorKey());
-        // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first
-        // need to add the edge between the current node and the child error it requested so that
-        // error bubbling can occur. Note that this edge will subsequently be removed during graph
-        // cleaning (since the current node will never be committed to the graph).
-        SkyKey childErrorKey = env.getDepErrorKey();
-        NodeEntry childErrorEntry = Preconditions.checkNotNull(
-            graph.get(skyKey, Reason.OTHER, childErrorKey),
-            "skyKey: %s, state: %s childErrorKey: %s",
-            skyKey,
-            state,
-            childErrorKey);
+        if (env.getDepErrorKey() != null) {
+          Preconditions.checkState(
+              !evaluatorContext.keepGoing(), "%s %s %s", skyKey, state, env.getDepErrorKey());
+          // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first
+          // need to add the edge between the current node and the child error it requested so that
+          // error bubbling can occur. Note that this edge will subsequently be removed during graph
+          // cleaning (since the current node will never be committed to the graph).
+          SkyKey childErrorKey = env.getDepErrorKey();
+          NodeEntry childErrorEntry =
+              Preconditions.checkNotNull(
+                  graph.get(skyKey, Reason.OTHER, childErrorKey),
+                  "skyKey: %s, state: %s childErrorKey: %s",
+                  skyKey,
+                  state,
+                  childErrorKey);
           if (newDirectDeps.contains(childErrorKey)) {
             // Add this dep if it was just requested. In certain rare race conditions (see
             // MemoizingEvaluatorTest.cachedErrorCausesRestart) this dep may have already been
             // requested.
-            state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(childErrorKey)));
+            state.addTemporaryDirectDeps(GroupedListHelper.create(childErrorKey));
             DependencyState childErrorState;
             if (oldDeps.contains(childErrorKey)) {
               childErrorState = childErrorEntry.checkIfDoneForDirtyReverseDep(skyKey);
@@ -489,62 +494,62 @@ public final class ParallelEvaluator implements Evaluator {
                 state,
                 childErrorKey,
                 childErrorEntry);
-        }
-        ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo());
+          }
+          ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo());
           evaluatorContext.getVisitor().preventNewEvaluations();
-        throw SchedulerException.ofError(childErrorInfo, childErrorKey);
-      }
+          throw SchedulerException.ofError(childErrorInfo, childErrorKey);
+        }
 
-      // TODO(bazel-team): This code is not safe to interrupt, because we would lose the state in
-      // newDirectDeps.
+        // TODO(bazel-team): This code is not safe to interrupt, because we would lose the state in
+        // newDirectDeps.
 
-      // TODO(bazel-team): An ill-behaved SkyFunction can throw us into an infinite loop where we
-      // add more dependencies on every run. [skyframe-core]
+        // TODO(bazel-team): An ill-behaved SkyFunction can throw us into an infinite loop where we
+        // add more dependencies on every run. [skyframe-core]
 
-      // Add all new keys to the set of known deps.
-      state.addTemporaryDirectDeps(newDirectDeps);
+        // Add all new keys to the set of known deps.
+        Set<SkyKey> uniqueNewDeps = state.addTemporaryDirectDeps(newDirectDeps);
 
-      // If there were no newly requested dependencies, at least one of them was in error or there
-      // is a bug in the SkyFunction implementation. The environment has collected its errors, so we
-      // just order it to be built.
-      if (newDirectDeps.isEmpty()) {
-        // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
-        Preconditions.checkState(
-            !env.getChildErrorInfos().isEmpty(),
-            "Evaluation of SkyKey failed and no dependencies were requested: %s %s",
-            skyKey,
-            state);
-        Preconditions.checkState(
-            evaluatorContext.keepGoing(),
-            "nokeep_going evaluation should have failed on first child error: %s %s %s",
-            skyKey,
-            state,
-            env.getChildErrorInfos());
+        // If there were no newly requested dependencies, at least one of them was in error or there
+        // is a bug in the SkyFunction implementation. The environment has collected its errors, so
+        // we just order it to be built.
+        if (uniqueNewDeps.isEmpty()) {
+          // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
+          Preconditions.checkState(
+              !env.getChildErrorInfos().isEmpty(),
+              "Evaluation of SkyKey failed and no dependencies were requested: %s %s",
+              skyKey,
+              state);
+          Preconditions.checkState(
+              evaluatorContext.keepGoing(),
+              "nokeep_going evaluation should have failed on first child error: %s %s %s",
+              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, EnqueueParentBehavior.ENQUEUE);
-        return;
-      }
+          return;
+        }
 
-      for (Entry<SkyKey, ? extends NodeEntry> e :
-          graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) {
-        SkyKey newDirectDep = e.getKey();
-        NodeEntry newDirectDepEntry = e.getValue();
-        enqueueChild(
-            skyKey,
-            state,
-            newDirectDep,
-            newDirectDepEntry,
-            /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
-      }
+        for (Entry<SkyKey, ? extends NodeEntry> e :
+            graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, uniqueNewDeps).entrySet()) {
+          SkyKey newDirectDep = e.getKey();
+          NodeEntry newDirectDepEntry = e.getValue();
+          enqueueChild(
+              skyKey,
+              state,
+              newDirectDep,
+              newDirectDepEntry,
+              /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
+        }
+        // It is critical that there is no code below this point in the try block.
       } catch (InterruptedException ie) {
         // InterruptedException cannot be thrown by Runnable.run, so we must wrap it.
         // Interrupts can be caught by both the Evaluator and the AbstractQueueVisitor.
         // The former will unwrap the IE and propagate it as is; the latter will throw a new IE.
         throw SchedulerException.ofInterruption(ie, skyKey);
       }
-      // It is critical that there is no code below this point.
     }
 
     private String prepareCrashMessage(SkyKey skyKey, Iterable<SkyKey> reverseDeps) {
@@ -594,8 +599,8 @@ public final class ParallelEvaluator implements Evaluator {
       }
     }
     env.getNewlyRequestedDeps().remove(unfinishedDeps);
-    entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps());
-    for (SkyKey newDep : env.getNewlyRequestedDeps()) {
+    Set<SkyKey> uniqueNewDeps = entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps());
+    for (SkyKey newDep : uniqueNewDeps) {
       // Note that this depEntry can't be null. If env.newlyRequestedDeps contained a key with a
       // null entry, then it would have been added to unfinishedDeps and then removed from
       // env.newlyRequestedDeps just above this loop.
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 8c3126f38b..8e1d3cfb81 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -191,7 +191,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
                 + skyKey
                 + ". Present values: "
                 + deps
-                + "requested from: "
+                + " requested from: "
                 + depKeys
                 + ", "
                 + entry);
@@ -262,8 +262,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       }
       Preconditions.checkState(
           triState == DependencyState.DONE, "%s %s %s", skyKey, triState, errorInfo);
-      state.addTemporaryDirectDeps(
-          GroupedListHelper.create(ImmutableList.of(ErrorTransienceValue.KEY)));
+      state.addTemporaryDirectDeps(GroupedListHelper.create(ErrorTransienceValue.KEY));
       state.signalDep();
     }
 
@@ -467,10 +466,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
   }
 
   private void addDep(SkyKey key) {
-    if (!newlyRequestedDeps.contains(key)) {
-      // dep may have been requested already this evaluation. If not, add it.
-      newlyRequestedDeps.add(key);
-    }
+    newlyRequestedDeps.add(key);
   }
 
   /**
diff --git a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
index b416719f69..6ffba0ef34 100644
--- a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
@@ -23,16 +23,14 @@ import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.Set;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
 
 @RunWith(JUnit4.class)
 public class GroupedListTest {
@@ -162,6 +160,22 @@ public class GroupedListTest {
   }
 
   @Test
+  public void sizeWithDuplicatesInAndOutOfGroups() {
+    GroupedList<String> groupedList = new GroupedList<>();
+    GroupedListHelper<String> helper = new GroupedListHelper<>();
+    helper.add("1");
+    helper.startGroup();
+    helper.add("1");
+    helper.add("2");
+    helper.add("3");
+    helper.endGroup();
+    helper.add("3");
+    groupedList.append(helper);
+    assertThat(groupedList.numElements()).isEqualTo(3);
+    assertThat(groupedList.listSize()).isEqualTo(2);
+  }
+
+  @Test
   public void removeMakesEmpty() {
     GroupedList<String> groupedList = new GroupedList<>();
     assertTrue(groupedList.isEmpty());
@@ -226,7 +240,13 @@ public class GroupedListTest {
 
   private static Object createAndCompress(Collection<String> list) {
     GroupedList<String> result = new GroupedList<>();
-    result.append(GroupedListHelper.create(list));
+    GroupedListHelper<String> helper = new GroupedListHelper<>();
+    helper.startGroup();
+    for (String item : list) {
+      helper.add(item);
+    }
+    helper.endGroup();
+    result.append(helper);
     return result.compress();
   }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 9c19360762..8b8fb81c8c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -709,7 +709,14 @@ public class InMemoryNodeEntryTest {
         .addReverseDepAndCheckIfDone(null)
         .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     for (Set<SkyKey> depGroup : groupedDirectDeps) {
-      entry.addTemporaryDirectDeps(GroupedListHelper.create(depGroup));
+      GroupedListHelper<SkyKey> helper = new GroupedListHelper<>();
+      helper.startGroup();
+      for (SkyKey item : depGroup) {
+        helper.add(item);
+      }
+      helper.endGroup();
+
+      entry.addTemporaryDirectDeps(helper);
       for (int i = 0; i < depGroup.size(); i++) {
         entry.signalDep();
       }