Store SkyValues for new deps from the graph intra-environment

This ensures that if a SkyFunction read a value (or its absence) for a
dep during its evaluation, subsequent requests for that dep's value (or
its absence) provide the same result.

This does not yet necessarily apply to the process of collecting events
and posts from a node's deps, which will be considered in a future
refactoring.

This CL adds SkyFunctionEnvironment#removeUndoneNewlyRequestedDeps
because the prior strategy for removing undone deps for done parents, by
re-requesting the dep's node from the graph and checking its doneness,
could lead to deps being dropped from parents if those deps transitioned
from done to dirty as the parent completes.

Minor cleanup to the bubbleErrorInfo field, which is nullable, and now
documented.

(Note that done->dirty node transitions during evaluation are planned,
but not yet possible.)

RELNOTES: None.
PiperOrigin-RevId: 202577098

2 files changed, 131 insertions, 66 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index abca3b25c4..8267fa27e1 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -36,7 +36,6 @@ import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
 import java.time.Duration;
 import java.util.Collection;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
@@ -675,16 +674,7 @@ public abstract class AbstractParallelEvaluator {
 
     // We don't expect any unfinished deps in a keep-going build.
     if (!keepGoing) {
-      Map<SkyKey, ? extends NodeEntry> newlyRequestedDepMap =
-          graph.getBatch(skyKey, Reason.DONE_CHECKING, env.getNewlyRequestedDeps());
-      Set<SkyKey> unfinishedDeps = new HashSet<>();
-      while (it.hasNext()) {
-        SkyKey dep = it.next();
-        if (!isDoneForBuild(newlyRequestedDepMap.get(dep))) {
-          unfinishedDeps.add(dep);
-        }
-      }
-      env.getNewlyRequestedDeps().remove(unfinishedDeps);
+      env.removeUndoneNewlyRequestedDeps();
     }
 
     Set<SkyKey> uniqueNewDeps = entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps());
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 333b0e41de..828c0795bb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -13,8 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import static com.google.devtools.build.skyframe.AbstractParallelEvaluator.isDoneForBuild;
-
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
@@ -38,6 +36,7 @@ import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
@@ -70,7 +69,16 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
 
   private SkyValue value = null;
   private ErrorInfo errorInfo = null;
-  private final Map<SkyKey, ValueWithMetadata> bubbleErrorInfo;
+
+  /**
+   * This is not {@code null} only during cycle detection and error bubbling. The nullness of this
+   * field is used to detect whether evaluation is in one of those special states.
+   *
+   * <p>When this is not {@code null}, values in this map should be used (while getting
+   * dependencies' values, events, or posts) over values from the graph for keys present in this
+   * map.
+   */
+  @Nullable private final Map<SkyKey, ValueWithMetadata> bubbleErrorInfo;
 
   /**
    * The values previously declared as dependencies.
@@ -79,7 +87,25 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
    * NodeEntry#getValueMaybeWithMetadata}. In the latter case, they should be processed using the
    * static methods of {@link ValueWithMetadata}.
    */
-  private final Map<SkyKey, SkyValue> directDeps;
+  private final Map<SkyKey, SkyValue> previouslyRequestedDepsValues;
+
+  /**
+   * The values newly requested from the graph.
+   *
+   * <p>Values in this map are either {@link #NULL_MARKER} or were retrieved via {@link
+   * NodeEntry#getValueMaybeWithMetadata}. In the latter case, they should be processed using the
+   * static methods of {@link ValueWithMetadata}.
+   */
+  private final Map<SkyKey, SkyValue> newlyRequestedDepsValues = new HashMap<>();
+
+  /**
+   * Keys of dependencies registered via {@link #registerDependencies}.
+   *
+   * <p>The {@link #registerDependencies} method is hacky. Deps registered through it will not have
+   * entries in {@link #newlyRequestedDepsValues}, but they are expected to be done. This set tracks
+   * those keys so that they aren't removed when {@link #removeUndoneNewlyRequestedDeps} is called.
+   */
+  private final Set<SkyKey> newlyRegisteredDeps = new HashSet<>();
 
   /**
    * The grouped list of values requested during this build as dependencies. On a subsequent build,
@@ -138,11 +164,11 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     this.skyKey = skyKey;
     this.oldDeps = oldDeps;
     this.evaluatorContext = evaluatorContext;
-    this.directDeps =
+    this.previouslyRequestedDepsValues =
         batchPrefetch(skyKey, directDeps, oldDeps, /*assertDone=*/ bubbleErrorInfo == null, skyKey);
     this.bubbleErrorInfo = bubbleErrorInfo;
     Preconditions.checkState(
-        !this.directDeps.containsKey(ErrorTransienceValue.KEY),
+        !this.previouslyRequestedDepsValues.containsKey(ErrorTransienceValue.KEY),
         "%s cannot have a dep on ErrorTransienceValue during building",
         skyKey);
   }
@@ -289,9 +315,23 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     this.errorInfo = Preconditions.checkNotNull(errorInfo, skyKey);
   }
 
-  private Map<SkyKey, SkyValue> getValuesMaybeFromError(Iterable<? extends SkyKey> keys)
-      throws InterruptedException {
-    // Use a HashMap, not an ImmutableMap.Builder, because we have not yet deduplicated these keys
+  /**
+   * Returns a map of {@code keys} to values or {@link #NULL_MARKER}s, populating the map's contents
+   * by looking in order at:
+   *
+   * <ol>
+   *   <li>{@link #bubbleErrorInfo}
+   *   <li>{@link #previouslyRequestedDepsValues}
+   *   <li>{@link #newlyRequestedDepsValues}
+   *   <li>{@link #evaluatorContext}'s graph accessing methods
+   * </ol>
+   *
+   * <p>Any key whose {@link NodeEntry}--or absence thereof--had to be read from the graph will also
+   * be entered into {@link #newlyRequestedDepsValues} with its value or a {@link #NULL_MARKER}.
+   */
+  private Map<SkyKey, SkyValue> maybeGetValuesFromErrorOrDepsOrGraph(
+      Iterable<? extends SkyKey> keys) throws InterruptedException {
+    // Uses a HashMap, not an ImmutableMap.Builder, because we have not yet deduplicated these keys
     // and ImmutableMap.Builder does not tolerate duplicates.  The map will be thrown away
     // shortly in any case.
     Map<SkyKey, SkyValue> result = new HashMap<>();
@@ -311,26 +351,31 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     Map<SkyKey, ? extends NodeEntry> missingEntries =
         evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys);
     for (SkyKey key : missingKeys) {
-      result.put(key, getValueOrNullMarker(missingEntries.get(key)));
+      SkyValue valueOrNullMarker = getValueOrNullMarker(missingEntries.get(key));
+      result.put(key, valueOrNullMarker);
+      newlyRequestedDepsValues.put(key, valueOrNullMarker);
     }
     return result;
   }
 
   /**
    * Returns just the values of the deps in {@code depKeys}, looking at {@code bubbleErrorInfo},
-   * {@link #directDeps}, and the backing {@link #evaluatorContext#graph} in that order. Any deps
-   * that are not yet done will not have their values present in the returned collection.
+   * {@link #previouslyRequestedDepsValues}, and the backing {@link #evaluatorContext#graph} in that
+   * order. Any deps that are not yet done will not have their values present in the returned
+   * collection.
    */
   private Collection<SkyValue> getDepValuesForDoneNodeMaybeFromError(GroupedList<SkyKey> depKeys)
       throws InterruptedException {
     int keySize = depKeys.numElements();
     List<SkyValue> result = new ArrayList<>(keySize);
     // depKeys consists of all known deps of this entry. That should include all the keys in
-    // directDeps, and any keys in bubbleErrorInfo. We expect to have to retrieve the keys that
-    // are not in either one.
+    // previouslyRequestedDepsValues, and any keys in bubbleErrorInfo. We expect to have to retrieve
+    // the keys that are not in either one.
     int expectedMissingKeySize =
         Math.max(
-            keySize - directDeps.size() - (bubbleErrorInfo == null ? 0 : bubbleErrorInfo.size()),
+            keySize
+                - previouslyRequestedDepsValues.size()
+                - (bubbleErrorInfo == null ? 0 : bubbleErrorInfo.size()),
             0);
     ArrayList<SkyKey> missingKeys = new ArrayList<>(expectedMissingKeySize);
     for (SkyKey key : depKeys.getAllElementsAsIterable()) {
@@ -348,6 +393,18 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     return result;
   }
 
+  /**
+   * Returns a value or a {@link #NULL_MARKER} associated with {@code key} by looking in order at:
+   *
+   * <ol>
+   *   <li>{@code bubbleErrorInfo}
+   *   <li>{@link #previouslyRequestedDepsValues}
+   *   <li>{@link #newlyRequestedDepsValues}
+   * </ol>
+   *
+   * <p>Returns {@code null} if no entries for {@code key} were found in any of those three maps.
+   * (Note that none of the maps can have {@code null} as a value.)
+   */
   @Nullable
   private SkyValue maybeGetValueFromErrorOrDeps(SkyKey key) {
     if (bubbleErrorInfo != null) {
@@ -356,12 +413,27 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         return bubbleErrorInfoValue;
       }
     }
-    return directDeps.get(key);
+    SkyValue directDepsValue = previouslyRequestedDepsValues.get(key);
+    if (directDepsValue != null) {
+      return directDepsValue;
+    }
+    SkyValue newlyRequestedDepsValue = newlyRequestedDepsValues.get(key);
+    if (newlyRequestedDepsValue != null) {
+      return newlyRequestedDepsValue;
+    }
+    return null;
   }
 
   private static SkyValue getValueOrNullMarker(@Nullable NodeEntry nodeEntry)
       throws InterruptedException {
-    return isDoneForBuild(nodeEntry) ? nodeEntry.getValueMaybeWithMetadata() : NULL_MARKER;
+    if (nodeEntry == null) {
+      return NULL_MARKER;
+    }
+    SkyValue valueMaybeWithMetadata = nodeEntry.getValueMaybeWithMetadata();
+    if (valueMaybeWithMetadata == null) {
+      return NULL_MARKER;
+    }
+    return valueMaybeWithMetadata;
   }
 
   @Override
@@ -369,27 +441,25 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       Iterable<? extends SkyKey> depKeys) throws InterruptedException {
     checkActive();
     newlyRequestedDeps.startGroup();
-    Map<SkyKey, SkyValue> values = getValuesMaybeFromError(depKeys);
+    Map<SkyKey, SkyValue> values = maybeGetValuesFromErrorOrDepsOrGraph(depKeys);
     for (Map.Entry<SkyKey, SkyValue> depEntry : values.entrySet()) {
       SkyKey depKey = depEntry.getKey();
       SkyValue depValue = depEntry.getValue();
       if (depValue == NULL_MARKER) {
-        if (directDeps.containsKey(depKey)) {
+        if (previouslyRequestedDepsValues.containsKey(depKey)) {
           throw new IllegalStateException(
-              "Undone key "
-                  + depKey
-                  + " was already in deps of "
-                  + skyKey
-                  + "( dep: "
-                  + evaluatorContext.getGraph().get(skyKey, Reason.OTHER, depKey)
-                  + ", parent: "
-                  + evaluatorContext.getGraph().get(null, Reason.OTHER, skyKey));
+              String.format(
+                  "Undone key %s was already in deps of %s( dep: %s, parent: %s )",
+                  depKey,
+                  skyKey,
+                  evaluatorContext.getGraph().get(skyKey, Reason.OTHER, depKey),
+                  evaluatorContext.getGraph().get(null, Reason.OTHER, skyKey)));
         }
         valuesMissing = true;
-        addDep(depKey);
+        newlyRequestedDeps.add(depKey);
         continue;
       }
-      ErrorInfo errorInfo = ValueWithMetadata.getMaybeErrorInfo(depEntry.getValue());
+      ErrorInfo errorInfo = ValueWithMetadata.getMaybeErrorInfo(depValue);
       if (errorInfo != null) {
         childErrorInfos.add(errorInfo);
         if (bubbleErrorInfo != null) {
@@ -409,9 +479,9 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         }
       }
 
-      if (!directDeps.containsKey(depKey)) {
+      if (!previouslyRequestedDepsValues.containsKey(depKey)) {
         if (bubbleErrorInfo == null) {
-          addDep(depKey);
+          newlyRequestedDeps.add(depKey);
         }
         evaluatorContext
             .getReplayingNestedSetPostableVisitor()
@@ -465,10 +535,6 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         });
   }
 
-  private void addDep(SkyKey key) {
-    newlyRequestedDeps.add(key);
-  }
-
   /**
    * If {@code !keepGoing} and there is at least one dep in error, returns a dep in error. Otherwise
    * returns {@code null}.
@@ -492,12 +558,29 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     return newlyRequestedDeps;
   }
 
+  void removeUndoneNewlyRequestedDeps() {
+    HashSet<SkyKey> undoneDeps = new HashSet<>();
+    for (SkyKey newlyRequestedDep : newlyRequestedDeps) {
+      if (newlyRegisteredDeps.contains(newlyRequestedDep)) {
+        continue;
+      }
+      SkyValue newlyRequestedDepValue =
+          Preconditions.checkNotNull(
+              newlyRequestedDepsValues.get(newlyRequestedDep), newlyRequestedDep);
+      if (newlyRequestedDepValue == NULL_MARKER) {
+        // The dep was normally requested, and was not done.
+        undoneDeps.add(newlyRequestedDep);
+      }
+    }
+    newlyRequestedDeps.remove(undoneDeps);
+  }
+
   boolean isAnyDirectDepErrorTransitivelyTransient() {
     Preconditions.checkState(
         bubbleErrorInfo == null,
         "Checking dep error transitive transience during error bubbling for: %s",
         skyKey);
-    for (SkyValue skyValue : directDeps.values()) {
+    for (SkyValue skyValue : previouslyRequestedDepsValues.values()) {
       ErrorInfo maybeErrorInfo = ValueWithMetadata.getMaybeErrorInfo(skyValue);
       if (maybeErrorInfo != null && maybeErrorInfo.isTransitivelyTransient()) {
         return true;
@@ -506,23 +589,14 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     return false;
   }
 
-  boolean isAnyNewlyRequestedDepErrorTransitivelyTransient() throws InterruptedException {
-    // TODO(mschaller): consider collecting SkyValues of newly requested deps as they're requested
-    // which would allow this code to avoid graph queries for nodes already queried.
-    //
-    // This will also be necessary for correct behavior in the presence of node re-dirtying.
-      Preconditions.checkState(
-          bubbleErrorInfo == null,
-          "Checking dep error transitive transience during error bubbling for: %s",
-          skyKey);
-    Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
-        evaluatorContext.getBatchValues(skyKey, Reason.DONE_CHECKING, getNewlyRequestedDeps());
-    for (NodeEntry depEntry : newlyRequestedDeps.values()) {
-      if (!isDoneForBuild(depEntry)) {
-        continue;
-      }
-      ErrorInfo depError = depEntry.getErrorInfo();
-      if (depError != null && depError.isTransitivelyTransient()) {
+  boolean isAnyNewlyRequestedDepErrorTransitivelyTransient() {
+    Preconditions.checkState(
+        bubbleErrorInfo == null,
+        "Checking dep error transitive transience during error bubbling for: %s",
+        skyKey);
+    for (SkyValue skyValue : newlyRequestedDepsValues.values()) {
+      ErrorInfo maybeErrorInfo = ValueWithMetadata.getMaybeErrorInfo(skyValue);
+      if (maybeErrorInfo != null && maybeErrorInfo.isTransitivelyTransient()) {
         return true;
       }
     }
@@ -652,8 +726,9 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
   public void registerDependencies(Iterable<SkyKey> keys) {
     newlyRequestedDeps.startGroup();
     for (SkyKey key : keys) {
-      if (!directDeps.containsKey(key)) {
-        addDep(key);
+      if (!previouslyRequestedDepsValues.containsKey(key)) {
+        newlyRequestedDeps.add(key);
+        newlyRegisteredDeps.add(key);
       }
     }
     newlyRequestedDeps.endGroup();