Reuse previously stored SkyValues during event/post collection

If a SkyFunction read a value (or its absence) from the graph during its
evaluation, that value will be used to compute the event and post
metadata for that evaluation.

This CL modifies the assertion strategy for this code. Previously,
registered deps which were not done would have gone undetected, and
their events/posts skipped.

This CL also makes a few minor changes that make SkyFunctionEnvironment
more consistent:
 - Deps not already in previouslyRequestedDepsValues are added to
 newlyRequestedDeps regardless of whether evaluation was in
 error bubbling or whether the dep was done.
 - Previously requested deps of an inflight node are prefetched (by
 passing them to SkyFunctionEnvironment's ctor) during error bubbling in
 the same way as they are during normal eval or cycle checking.
 - Minor signature and documentation adjustments.

RELNOTES: None.
PiperOrigin-RevId: 202672709

2 files changed, 81 insertions, 59 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
index 20bf5d5879..a82d1158df 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -23,7 +23,6 @@ import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
-import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationSuccessState;
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState;
@@ -478,7 +477,7 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
       SkyFunctionEnvironment env =
           new SkyFunctionEnvironment(
               parent,
-              new GroupedList<SkyKey>(),
+              parentEntry.getTemporaryDirectDeps(),
               bubbleErrorInfo,
               ImmutableSet.<SkyKey>of(),
               evaluatorContext);
@@ -504,8 +503,8 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
               errorKey,
               ValueWithMetadata.error(
                   ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)),
-                  env.buildEvents(parentEntry, /*missingChildren=*/ true),
-                  env.buildPosts(parentEntry)));
+                  env.buildEvents(parentEntry, /*expectDoneDeps=*/ false),
+                  env.buildPosts(parentEntry, /*expectDoneDeps=*/ false)));
           continue;
         }
       } finally {
@@ -517,8 +516,8 @@ public abstract class AbstractExceptionalParallelEvaluator<E extends Exception>
           errorKey,
           ValueWithMetadata.error(
               ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)),
-              env.buildEvents(parentEntry, /*missingChildren=*/ true),
-              env.buildPosts(parentEntry)));
+              env.buildEvents(parentEntry, /*expectDoneDeps=*/ false),
+              env.buildPosts(parentEntry, /*expectDoneDeps=*/ false)));
     }
 
     // Reset the interrupt bit if there was an interrupt from outside this evaluator interrupt.
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 828c0795bb..6d7918f768 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -225,38 +225,28 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     Preconditions.checkState(building, skyKey);
   }
 
-  NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean missingChildren)
+  NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean expectDoneDeps)
       throws InterruptedException {
     if (!evaluatorContext.getStoredEventFilter().storeEventsAndPosts()) {
       return NestedSetBuilder.emptySet(Order.STABLE_ORDER);
     }
-    // Aggregate the nested set of events from the direct deps, also adding the events from
-    // building this value.
     NestedSetBuilder<TaggedEvents> eventBuilder = NestedSetBuilder.stableOrder();
     ImmutableList<Event> events = eventHandler.getEvents();
     if (!events.isEmpty()) {
       eventBuilder.add(new TaggedEvents(getTagFromKey(), events));
     }
+
     GroupedList<SkyKey> depKeys = entry.getTemporaryDirectDeps();
-    Collection<SkyValue> deps = getDepValuesForDoneNodeMaybeFromError(depKeys);
-    if (!missingChildren && depKeys.numElements() != deps.size()) {
-      throw new IllegalStateException(
-          "Missing keys for "
-              + skyKey
-              + ". Present values: "
-              + deps
-              + " requested from: "
-              + depKeys
-              + ", "
-              + entry);
-    }
+    Collection<SkyValue> deps =
+        getDepValuesForDoneNodeFromErrorOrDepsOrGraph(depKeys, expectDoneDeps);
     for (SkyValue value : deps) {
       eventBuilder.addTransitive(ValueWithMetadata.getEvents(value));
     }
     return eventBuilder.build();
   }
 
-  NestedSet<Postable> buildPosts(NodeEntry entry) throws InterruptedException {
+  NestedSet<Postable> buildPosts(NodeEntry entry, boolean expectDoneDeps)
+      throws InterruptedException {
     if (!evaluatorContext.getStoredEventFilter().storeEventsAndPosts()) {
       return NestedSetBuilder.emptySet(Order.STABLE_ORDER);
     }
@@ -264,7 +254,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     postBuilder.addAll(eventHandler.getPosts());
 
     GroupedList<SkyKey> depKeys = entry.getTemporaryDirectDeps();
-    Collection<SkyValue> deps = getDepValuesForDoneNodeMaybeFromError(depKeys);
+    Collection<SkyValue> deps =
+        getDepValuesForDoneNodeFromErrorOrDepsOrGraph(depKeys, expectDoneDeps);
     for (SkyValue value : deps) {
       postBuilder.addTransitive(ValueWithMetadata.getPosts(value));
     }
@@ -329,8 +320,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
    * <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 {
+  private Map<SkyKey, SkyValue> getValuesFromErrorOrDepsOrGraph(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.
@@ -348,6 +339,9 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
         result.put(key, value);
       }
     }
+    if (missingKeys.isEmpty()) {
+      return result;
+    }
     Map<SkyKey, ? extends NodeEntry> missingEntries =
         evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys);
     for (SkyKey key : missingKeys) {
@@ -359,36 +353,64 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
   }
 
   /**
-   * Returns just the values of the deps in {@code depKeys}, looking at {@code bubbleErrorInfo},
-   * {@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.
+   * Returns the values of done deps in {@code depKeys}, 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}.
+   *
+   * <p>This asserts that only keys in {@link #newlyRegisteredDeps} require reading from the graph,
+   * because this node is done, and so all other deps must have been previously or newly requested.
+   *
+   * <p>If {@code assertDone}, this asserts that all deps in {@code depKeys} are done.
    */
-  private Collection<SkyValue> getDepValuesForDoneNodeMaybeFromError(GroupedList<SkyKey> depKeys)
-      throws InterruptedException {
+  private Collection<SkyValue> getDepValuesForDoneNodeFromErrorOrDepsOrGraph(
+      GroupedList<SkyKey> depKeys, boolean assertDone) 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
-    // 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
-                - previouslyRequestedDepsValues.size()
-                - (bubbleErrorInfo == null ? 0 : bubbleErrorInfo.size()),
-            0);
-    ArrayList<SkyKey> missingKeys = new ArrayList<>(expectedMissingKeySize);
+    // depKeys may contain keys in newlyRegisteredDeps whose values have not yet been retrieved from
+    // the graph during this environment's lifetime.
+    int expectedMissingKeys = newlyRegisteredDeps.size();
+    ArrayList<SkyKey> missingKeys =
+        expectedMissingKeys > 0 ? new ArrayList<>(expectedMissingKeys) : null;
+
     for (SkyKey key : depKeys.getAllElementsAsIterable()) {
       SkyValue value = maybeGetValueFromErrorOrDeps(key);
       if (value == null) {
+        if (key == ErrorTransienceValue.KEY) {
+          continue;
+        }
+        Preconditions.checkState(
+            newlyRegisteredDeps.contains(key),
+            "Dep was not previously or newly requested, nor registered, nor error transient: %s",
+            key);
         missingKeys.add(key);
+      } else if (value == NULL_MARKER) {
+        Preconditions.checkState(!assertDone, "%s had not done %s", skyKey, key);
       } else {
         result.add(value);
       }
     }
-    for (NodeEntry entry :
-        evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys).values()) {
-      result.add(getValueOrNullMarker(entry));
+    if (missingKeys == null || missingKeys.isEmpty()) {
+      return result;
+    }
+    Map<SkyKey, ? extends NodeEntry> missingEntries =
+        evaluatorContext.getBatchValues(skyKey, Reason.DEP_REQUESTED, missingKeys);
+    for (SkyKey key : missingKeys) {
+      SkyValue valueOrNullMarker = getValueOrNullMarker(missingEntries.get(key));
+      newlyRequestedDepsValues.put(key, valueOrNullMarker);
+      if (valueOrNullMarker == NULL_MARKER) {
+        // TODO(mschaller): handle registered deps that transitioned from done to dirty during eval
+        Preconditions.checkState(!assertDone, "%s had not done: %s", skyKey, key);
+        continue;
+      }
+      result.add(valueOrNullMarker);
     }
     return result;
   }
@@ -441,24 +463,27 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       Iterable<? extends SkyKey> depKeys) throws InterruptedException {
     checkActive();
     newlyRequestedDeps.startGroup();
-    Map<SkyKey, SkyValue> values = maybeGetValuesFromErrorOrDepsOrGraph(depKeys);
+    Map<SkyKey, SkyValue> values = getValuesFromErrorOrDepsOrGraph(depKeys);
     for (Map.Entry<SkyKey, SkyValue> depEntry : values.entrySet()) {
       SkyKey depKey = depEntry.getKey();
       SkyValue depValue = depEntry.getValue();
+
       if (depValue == NULL_MARKER) {
+        valuesMissing = true;
         if (previouslyRequestedDepsValues.containsKey(depKey)) {
-          throw new IllegalStateException(
-              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)));
+          Preconditions.checkState(
+              bubbleErrorInfo != null,
+              "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));
+        } else {
+          newlyRequestedDeps.add(depKey);
         }
-        valuesMissing = true;
-        newlyRequestedDeps.add(depKey);
         continue;
       }
+
       ErrorInfo errorInfo = ValueWithMetadata.getMaybeErrorInfo(depValue);
       if (errorInfo != null) {
         childErrorInfos.add(errorInfo);
@@ -480,9 +505,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
       }
 
       if (!previouslyRequestedDepsValues.containsKey(depKey)) {
-        if (bubbleErrorInfo == null) {
-          newlyRequestedDeps.add(depKey);
-        }
+        newlyRequestedDeps.add(depKey);
         evaluatorContext
             .getReplayingNestedSetPostableVisitor()
             .visit(ValueWithMetadata.getPosts(depValue));
@@ -635,8 +658,8 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment {
     // (2) value == null && enqueueParents happens for values that are found to have errors
     // during a --keep_going build.
 
-    NestedSet<Postable> posts = buildPosts(primaryEntry);
-    NestedSet<TaggedEvents> events = buildEvents(primaryEntry, /*missingChildren=*/ false);
+    NestedSet<Postable> posts = buildPosts(primaryEntry, /*expectDoneDeps=*/ true);
+    NestedSet<TaggedEvents> events = buildEvents(primaryEntry, /*expectDoneDeps=*/ true);
 
     Version valueVersion;
     SkyValue valueWithMetadata;