[9.3.0] Report each top-level node to the progress receiver only once (https:… (#30918)

…//github.com/bazelbuild/bazel/pull/30734)

`ParallelEvaluator#doMutatingEvaluation` classifies the requested
top-level keys with `addReverseDepAndCheckIfDone` and schedules them in
the same loop. Scheduling starts concurrent evaluation, so a key the
loop has not reached yet can be built as a dependency of an already
scheduled one. When the loop does reach it, it observes `DONE` and hands
it to `informProgressReceiverThatValueIsDone`, which reports it to the
progress receiver a second time -- the first report having come from
`SkyFunctionEnvironment#commitAndGetParents` when the node was actually
built.

Whether a given key takes that path is a race between the main thread
and the evaluator threads, so the double report is intermittent.

This is not confined to tests.
`SkyframeBuildView.ActionLookupValueProgressReceiver#evaluated` counts
every call whose state is `SUCCESS_VERSION_CHANGED`, and the second
report qualifies: a node built by this evaluation has a value version
equal to the graph version, so `informProgressReceiverThatValueIsDone`
computes `changed = true`. The `configuredObjectCount` and
`configuredTargetCount` behind `AnalysisPhaseCompleteEvent` -- the "N
targets configured" line and the corresponding BEP metrics -- are
inflated by one for every top-level target that is also a dependency of
another top-level target and happens to be built first.

The fix records which keys were already done before anything is
scheduled, so the loop can tell "was done when this evaluation began"
from "became done while this loop was running". Only the former is
reported, which is what the notification exists for; the latter has
already been reported by `commitAndGetParents`.

Fixes over-reporting of configured target counts, and fixes a flaky
test.


`//src/test/java/com/google/devtools/build/lib/analysis/test:TrimTestConfigurationTest`
fails on unmodified master roughly two thirds of the time locally (9/15
at `e3c6211224`, 10/15 at `39055fdcc1`), always in
`flagOffDifferentTestOptions_ResultsInDifferentCTs`:

```
IllegalStateException: Number of newly evaluated action lookup values 41
  does not agree with number that changed in graph: 43
```

That test requests `//test:native_shared_dep` and
`//test:starlark_shared_dep` as top-level targets and they are also
dependencies of earlier top-level targets in the same request, which is
exactly the shape above. Instrumenting the receiver showed those two
keys, and only those two, reported twice, with the second report coming
from `informProgressReceiverThatValueIsDone` on the main thread. Across
runs, the number of second reports was 0 in every passing run and 2 in
every failing one.

With this change the test passes 20/20.

No

- [x] I have added tests for the new use cases (if any).
- [ ] I have updated the documentation (if applicable).

RELNOTES: None

Closes #30734.

PiperOrigin-RevId: 967655660
Change-Id: Ib5faaf98fe7f325ab0fbf8b12735456dbf361a90

<!--
Thank you for contributing to Bazel!
Please read the contribution guidelines: https://bazel.build/contribute
-->

### Description
<!--
Please provide a brief summary of the changes in this PR.
-->

### Motivation
<!--
Why is this change important? Does it fix a specific bug or add a new
feature?
If this PR fixes an existing issue, please link it here (e.g. "Fixes
#1234").
-->

### Build API Changes
<!--
Does this PR affect the Build API? (e.g. Starlark API, providers,
command-line flags, native rules)
If yes, please answer the following:
1. Has this been discussed in a design doc or issue? (Please link it)
2. Is the change backward compatible?
3. If it's a breaking change, what is the migration plan?
-->

No

### Checklist

- [ ] I have added tests for the new use cases (if any).
- [ ] I have updated the documentation (if applicable).

### Release Notes

<!--
If this is a new feature, please add 'RELNOTES[NEW]: <description>'
here.
If this is a breaking change, please add 'RELNOTES[INC]: <reason>' here.
If this change should be mentioned in release notes, please add
'RELNOTES: <reason>' here.
-->

RELNOTES: None

Commit
https://github.com/bazelbuild/bazel/commit/032b4bc20e1c58f66ee90cc0f94205b95346520f

Co-authored-by: Fabian Meumertzheim <fabian@meumertzhe.im>

src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java

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 50d6c51..b260039 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -38,6 +38,7 @@
 import java.io.IOException;
 import java.time.Duration;
 import java.util.ArrayList;
+import java.util.BitSet;
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
@@ -132,10 +133,11 @@
 
   @ThreadCompatible
   private <T extends SkyValue> EvaluationResult<T> doMutatingEvaluation(
-      ImmutableSet<SkyKey> skyKeys) throws InterruptedException {
+      ImmutableSet<SkyKey> skyKeys, BitSet doneBeforeEvaluation) throws InterruptedException {
     injectErrorTransienceValue();
     try {
       NodeBatch batch = graph.createIfAbsentBatch(null, Reason.PRE_OR_POST_EVALUATION, skyKeys);
+      int index = 0;
       for (SkyKey skyKey : skyKeys) {
         NodeEntry entry = batch.get(skyKey);
         // This must be equivalent to the code in AbstractParallelEvaluator.Evaluate#enqueueChild,
@@ -145,13 +147,19 @@
             evaluatorContext.getVisitor().enqueueEvaluation(skyKey, null);
             break;
           case DONE:
-            informProgressReceiverThatValueIsDone(skyKey, entry);
+            // Scheduling above starts concurrent evaluation, so a key that is a dependency of an
+            // earlier key may have become done while this loop was running. Avoid reporting it
+            // twice.
+            if (doneBeforeEvaluation.get(index)) {
+              informProgressReceiverThatValueIsDone(skyKey, entry);
+            }
             break;
           case ALREADY_EVALUATING:
             break;
           default:
             throw new IllegalStateException(entry + " for " + skyKey + " in unknown state");
         }
+        index++;
       }
     } catch (InterruptedException ie) {
       // When multiple keys are being evaluated, it's possible that a key may get queued before
@@ -634,19 +642,21 @@
       throws InterruptedException {
     ImmutableSet<SkyKey> skyKeySet = ImmutableSet.copyOf(skyKeys);
 
+    NodeBatch batch =
+        evaluatorContext.getGraph().getBatch(null, Reason.PRE_OR_POST_EVALUATION, skyKeySet);
+    BitSet doneBeforeEvaluation = new BitSet(skyKeySet.size());
+    int index = 0;
+    for (SkyKey skyKey : skyKeySet) {
+      if (isDoneForBuild(batch.get(skyKey))) {
+        doneBeforeEvaluation.set(index);
+      }
+      index++;
+    }
+
     // Optimization: if all required node values are already present in the cache, return them
     // directly without launching the heavy machinery, spawning threads, etc.
     // Inform progressReceiver that these nodes are done to be consistent with the main code path.
-    boolean allAreDone = true;
-    NodeBatch batch =
-        evaluatorContext.getGraph().getBatch(null, Reason.PRE_OR_POST_EVALUATION, skyKeySet);
-    for (SkyKey key : skyKeySet) {
-      if (!isDoneForBuild(batch.get(key))) {
-        allAreDone = false;
-        break;
-      }
-    }
-    if (allAreDone) {
+    if (doneBeforeEvaluation.cardinality() == skyKeySet.size()) {
       for (SkyKey skyKey : skyKeySet) {
         informProgressReceiverThatValueIsDone(skyKey, batch.get(skyKey));
       }
@@ -681,7 +691,7 @@
         () -> evaluatorContext.stateCache().invalidateAll());
     try (SilentCloseable c =
         Profiler.instance().profile(ProfilerTask.SKYFRAME_EVAL, "Parallel Evaluator evaluation")) {
-      return doMutatingEvaluation(skyKeySet);
+      return doMutatingEvaluation(skyKeySet, doneBeforeEvaluation);
     } finally {
       unnecessaryTemporaryStateDropperReceiver.onEvaluationFinished();
     }

src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java

diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index 4e3b2d6..226a907 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -4317,4 +4317,68 @@
     assertThat(result.hasError()).isTrue();
     assertThat(evaluatedValues).hasSize(2); // errorKey and midKey
   }
+
+  @Test
+  public void topLevelKeyBuiltAsDepOfAnotherTopLevelKey_reportedToProgressReceiverOnce()
+      throws InterruptedException {
+    SkyKey parentKey = skyKey("parent");
+    SkyKey childKey = skyKey("child");
+    tester.getOrCreate(childKey).setConstantValue(new StringValue("child"));
+    tester.getOrCreate(parentKey).addDependency(childKey).setComputedValue(CONCATENATE);
+
+    AtomicLongMap<SkyKey> evaluatedCounts = AtomicLongMap.create();
+    revalidationReceiver =
+        new DirtyAndInflightTrackingProgressReceiver(
+            new EvaluationProgressReceiver() {
+              @Override
+              public void evaluated(
+                  SkyKey skyKey,
+                  EvaluationState state,
+                  @Nullable SkyValue newValue,
+                  @Nullable ErrorInfo newError,
+                  @Nullable GroupedDeps directDeps) {
+                evaluatedCounts.incrementAndGet(skyKey);
+              }
+            });
+
+    graph = new InMemoryGraphImpl();
+
+    // The direct executor evaluates parentKey inline, so childKey is deterministically built by the
+    // time the loop reaches it. With a real thread pool this is a race.
+    EvaluationResult<StringValue> result =
+        makeDirectExecutorEvaluator().eval(ImmutableList.of(parentKey, childKey));
+
+    assertThat(result.hasError()).isFalse();
+    assertThat(evaluatedCounts.get(childKey)).isEqualTo(1);
+    assertThat(evaluatedCounts.get(parentKey)).isEqualTo(1);
+
+    // Nodes that were done before the evaluation began are still reported.
+    EvaluationResult<StringValue> secondResult =
+        makeDirectExecutorEvaluator().eval(ImmutableList.of(parentKey, childKey));
+
+    assertThat(secondResult.hasError()).isFalse();
+    assertThat(evaluatedCounts.get(childKey)).isEqualTo(2);
+    assertThat(evaluatedCounts.get(parentKey)).isEqualTo(2);
+  }
+
+  private ParallelEvaluator makeDirectExecutorEvaluator() {
+    return new ParallelEvaluator(
+        graph,
+        graphVersion,
+        Version.minimal(),
+        tester.getSkyFunctionMap(),
+        reportedEvents,
+        new EmittedEventState(),
+        EventFilter.FULL_STORAGE,
+        ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
+        revalidationReceiver,
+        GraphInconsistencyReceiver.THROWING,
+        AbstractQueueVisitor.createWithExecutorService(
+            MoreExecutors.newDirectExecutorService(),
+            AbstractQueueVisitor.ExceptionHandlingMode.KEEP_GOING,
+            ParallelEvaluatorErrorClassifier.instance()),
+        new SimpleCycleDetector(/* storeExactCycles= */ true),
+        UnnecessaryTemporaryStateDropperReceiver.NULL,
+        /* keepGoing= */ Predicates.alwaysFalse());
+  }
 }