Don't GC dirty nodes that change pruning would verify clean (https://github.com/bazelbuild/bazel/pull/29965) ### Description The dirty-node garbage collector (`--version_window_for_dirty_node_gc`, run after every build via `BuildTool`) deletes dirty nodes that were not part of the build. A dirty node whose direct deps all turned out unchanged would be verified clean by change pruning the next time it is requested, but still ended up being deleted simply for not being part of the current evaluation. `AbstractInMemoryMemoizingEvaluator.deleteDirty` now keeps any dirty node that change pruning would verify clean if the new `--experimental_keep_change_prunable_nodes_during_gc` is enabled. ### Motivation This is motivated by https://github.com/bazelbuild/bazel/issues/29956, but doesn't quite fix it by itself (see https://github.com/bazelbuild/bazel/pull/29946#issuecomment-4797081830 and `deleteDirtyDeletesNodeNeedingRebuildToPrune`). It does help any change-prunable `SkyValue` (see the new integration test `test_unrelated_glob_change_pruned`). ### Build API Changes No ### Checklist - [x] I have added tests for the new use cases (if any). - [ ] I have updated the documentation (if applicable). RELNOTES[NEW]: With the new `--experimental_keep_change_prunable_nodes_during_gc` flag, Skyframe will keep computed nodes that aren't requested by the current evaluation but whose dependencies would be verified clean after change pruning. Closes #29965. PiperOrigin-RevId: 966612698 Change-Id: Ib809d5f50cd6647897a660a27bc5d531e30f2374
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java index 2ddd6c9..0ba603e 100644 --- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java +++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisOptions.java
@@ -110,6 +110,19 @@ public abstract long getVersionWindowForDirtyNodeGc(); @Option( + name = "experimental_keep_change_prunable_nodes_during_gc", + defaultValue = "false", + documentationCategory = OptionDocumentationCategory.UNDOCUMENTED, + metadataTags = OptionMetadataTag.EXPERIMENTAL, + effectTags = {OptionEffectTag.HOST_MACHINE_RESOURCE_OPTIMIZATIONS}, + help = + "If enabled, the dirty node garbage collection triggered by" + + " --version_window_for_dirty_node_gc keeps dirty nodes that change pruning would" + + " mark clean when they are next requested, at the cost of a scan over all dirty" + + " nodes at the end of the build.") + public abstract boolean getKeepChangePrunableNodesDuringGc(); + + @Option( name = "experimental_skyframe_cpu_heavy_skykeys_thread_pool_size", defaultValue = ResourceConverter.HOST_CPUS_KEYWORD, documentationCategory = OptionDocumentationCategory.UNDOCUMENTED,
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java b/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java index 9ad3568..46787c8 100644 --- a/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java +++ b/src/main/java/com/google/devtools/build/lib/buildtool/BuildTool.java
@@ -427,7 +427,9 @@ // Delete dirty nodes to ensure that they do not accumulate indefinitely. long versionWindow = request.getViewOptions().getVersionWindowForDirtyNodeGc(); if (versionWindow != -1) { - env.getSkyframeExecutor().deleteOldNodes(versionWindow); + env.getSkyframeExecutor() + .deleteOldNodes( + versionWindow, request.getViewOptions().getKeepChangePrunableNodesDuringGc()); } // The workspace status actions will not run with certain flags, or if an error occurs early // in the build. Ensure that build info is posted on every build.
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryProcessor.java b/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryProcessor.java index eae8e33..014510a 100644 --- a/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryProcessor.java +++ b/src/main/java/com/google/devtools/build/lib/buildtool/PostAnalysisQueryProcessor.java
@@ -89,7 +89,8 @@ // reproducible at the level of a single command. Either tolerate, or wipe the analysis graph // beforehand if this option is specified, or add another option to wipe if desired // (SkyframeExecutor#handleAnalysisInvalidatingChange should be sufficient). - env.getSkyframeExecutor().deleteOldNodes(/* versionWindowForDirtyGc= */ 0); + env.getSkyframeExecutor() + .deleteOldNodes(/* versionWindowForDirtyGc= */ 0, /* keepChangePrunableNodes= */ false); env.getSkyframeExecutor().applyInvalidation(env.getReporter()); if (!env.getSkyframeExecutor().tracksStateForIncrementality()) { throw new ExitException(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java index bae2e7f..70c1162 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -826,11 +826,11 @@ } @Override - public void deleteOldNodes(long versionWindowForDirtyGc) { + public void deleteOldNodes(long versionWindowForDirtyGc, boolean keepChangePrunableNodes) { // TODO(bazel-team): perhaps we should come up with a separate GC class dedicated to maintaining // value garbage. If we ever do so, this logic should be moved there. if (trackIncrementalState) { - memoizingEvaluator.deleteDirty(versionWindowForDirtyGc); + memoizingEvaluator.deleteDirty(versionWindowForDirtyGc, keepChangePrunableNodes); } }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java index e9879ab..4d7d693 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -3191,8 +3191,12 @@ * <p>Specifying a value N means, if the current version is V and a value was dirtied (and has * remained so) in version U, and U + N <= V, then the value will be marked for deletion and * purged in version V+1. + * + * <p>If {@code keepChangePrunableNodes} is true, dirty values that change pruning would mark + * clean when they are next requested are exempt from deletion. */ - public abstract void deleteOldNodes(long versionWindowForDirtyGc); + public abstract void deleteOldNodes( + long versionWindowForDirtyGc, boolean keepChangePrunableNodes); @Nullable public PackageProgressReceiver getPackageProgressReceiver() {
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryMemoizingEvaluator.java index 95fc8c4..2cdf4da 100644 --- a/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryMemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/AbstractInMemoryMemoizingEvaluator.java
@@ -21,6 +21,7 @@ import com.google.common.collect.HashMultimap; import com.google.common.collect.HashMultiset; import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; import com.google.common.collect.Multiset; import com.google.common.collect.Multisets; @@ -30,6 +31,7 @@ import com.google.devtools.build.lib.profiler.AutoProfiler; import com.google.devtools.build.lib.profiler.GoogleAutoProfilerUtils; 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.skyframe.Differencer.Diff; import com.google.devtools.build.skyframe.Differencer.DiffWithDelta.Delta; @@ -242,14 +244,34 @@ } @Override - public final void deleteDirty(long versionAgeLimit) { + public final void deleteDirty(long versionAgeLimit, boolean keepChangePrunableNodes) { checkArgument(versionAgeLimit >= 0, versionAgeLimit); Version threshold = IntVersion.of(lastGraphVersion.getVal() - versionAgeLimit); + var graph = getInMemoryGraph(); + + var dirtyKeys = progressReceiver.getUnenqueuedDirtyKeys(); + ImmutableSet<SkyKey> toKeep; + if (keepChangePrunableNodes) { + long profilerStartNanos = Profiler.instance().nanoTimeMaybe(); + toKeep = new ChangePrunableNodesFinder(graph, dirtyKeys).find(); + Profiler.instance() + .completeTask( + profilerStartNanos, + ProfilerTask.INFO, + "Resurrected %d out of %d dirty nodes during GC" + .formatted(toKeep.size(), dirtyKeys.size())); + } else { + toKeep = ImmutableSet.of(); + } + valuesToDelete.addAll( Sets.filter( - progressReceiver.getUnenqueuedDirtyKeys(), + dirtyKeys, skyKey -> { - NodeEntry entry = checkNotNull(getInMemoryGraph().getIfPresent(skyKey), skyKey); + if (toKeep.contains(skyKey)) { + return false; + } + NodeEntry entry = checkNotNull(graph.getIfPresent(skyKey), skyKey); checkState(entry.isDirty(), skyKey); return entry.getVersion().atMost(threshold); }));
diff --git a/src/main/java/com/google/devtools/build/skyframe/ChangePrunableNodesFinder.java b/src/main/java/com/google/devtools/build/skyframe/ChangePrunableNodesFinder.java new file mode 100644 index 0000000..2eb4ff9 --- /dev/null +++ b/src/main/java/com/google/devtools/build/skyframe/ChangePrunableNodesFinder.java
@@ -0,0 +1,152 @@ +// Copyright 2026 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.skyframe; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.devtools.build.lib.concurrent.ForkJoinQuiescingExecutor; +import com.google.devtools.build.lib.concurrent.NamedForkJoinPool; +import java.util.ArrayList; +import java.util.List; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentLinkedQueue; +import java.util.concurrent.atomic.AtomicInteger; + +/** + * Finds the dirty nodes that change pruning would verify clean if it ran, which it doesn't purely + * because these nodes weren't in scope for the current evaluation. + * + * <p>Operates in two phases: a parallel scan over all candidates that builds a DAG of dirty but + * unchanged deletion candidates and their dirty rdeps, followed by a traversal of the DAG that + * keeps all nodes whose dirty deps are also kept. The scan performs all graph accesses and its cost + * scales with the total number of candidates, so it runs on multiple threads; the traversal only + * visits the nodes that end up being kept. + */ +final class ChangePrunableNodesFinder { + private static final int SCAN_THREAD_COUNT = Runtime.getRuntime().availableProcessors(); + + private final InMemoryGraph graph; + private final ImmutableSet<SkyKey> candidates; + + // The DAG built by the scan phase: for each candidate with at least one dirty dep, the number + // of its dirty deps not yet known to be kept, together with the reverse edges. Candidates + // without dirty deps start out ready. Each entry in remainingDirtyDeps is written by a single + // scan thread, whereas dirtyRdeps values may receive edges from multiple threads. + private final ConcurrentHashMap<SkyKey, AtomicInteger> remainingDirtyDeps = + new ConcurrentHashMap<>(); + private final ConcurrentHashMap<SkyKey, ArrayList<SkyKey>> dirtyRdeps = new ConcurrentHashMap<>(); + private final ConcurrentLinkedQueue<SkyKey> ready = new ConcurrentLinkedQueue<>(); + + ChangePrunableNodesFinder(InMemoryGraph graph, ImmutableSet<SkyKey> candidates) { + this.graph = graph; + this.candidates = candidates; + } + + ImmutableSet<SkyKey> find() { + ImmutableList<SkyKey> candidateList = candidates.asList(); + if (candidateList.isEmpty()) { + return ImmutableSet.of(); + } + + var executor = + ForkJoinQuiescingExecutor.newBuilder() + .withOwnershipOf( + NamedForkJoinPool.newNamedPool("find-change-prunable-nodes", SCAN_THREAD_COUNT)) + .build(); + long listSize = candidateList.size(); + long numJobs = Math.min(SCAN_THREAD_COUNT, listSize); + for (long i = 0; i < numJobs; i++) { + int startIndex = (int) ((i * listSize) / numJobs); + int endIndex = (int) (((i + 1) * listSize) / numJobs); + ImmutableList<SkyKey> chunk = candidateList.subList(startIndex, endIndex); + executor.execute(() -> scanCandidates(chunk)); + } + try { + executor.awaitQuiescence(/* interruptWorkers= */ true); + } catch (InterruptedException e) { + // Keeping no nodes is always safe, it merely GCs more aggressively. + Thread.currentThread().interrupt(); + return ImmutableSet.of(); + } + + // Now visit the DAG, keeping all nodes whose dirty deps are also kept. + var toKeep = ImmutableSet.<SkyKey>builder(); + SkyKey readyKey; + while ((readyKey = ready.poll()) != null) { + toKeep.add(readyKey); + var rdeps = dirtyRdeps.get(readyKey); + if (rdeps == null) { + continue; + } + for (var rdep : rdeps) { + if (remainingDirtyDeps.get(rdep).decrementAndGet() == 0) { + // The last dirty dep of rdep is now known to be kept. + ready.add(rdep); + } + } + } + return toKeep.build(); + } + + private void scanCandidates(List<SkyKey> chunk) { + skipCandidate: + for (var skyKey : chunk) { + if (Thread.currentThread().isInterrupted()) { + // A partial scan only ever results in fewer nodes being kept, which is always safe. + return; + } + if (!(graph.getIfPresent(skyKey) instanceof IncrementalInMemoryNodeEntry entry)) { + continue; + } + Iterable<SkyKey> lastBuildDeps = entry.lastBuildDepsIfChangePrunable(); + if (lastBuildDeps == null) { + continue; + } + Version lastEvaluated = entry.lastEvaluatedVersion(); + var dirtyDeps = new ArrayList<SkyKey>(); + for (var dep : lastBuildDeps) { + NodeEntry depEntry = graph.getIfPresent(dep); + // A dep must be present and unchanged since this node was last evaluated to be + // potentially change-prunable. Undone deps that aren't unenqueued dirty deps will never + // be considered below and thus make an entry not change-prunable. + if (depEntry == null || !depEntry.getVersion().atMost(lastEvaluated)) { + continue skipCandidate; + } + if (depEntry.isDone()) { + continue; + } + if (!candidates.contains(dep)) { + continue skipCandidate; + } + dirtyDeps.add(dep); + } + if (dirtyDeps.isEmpty()) { + ready.add(skyKey); + } else { + remainingDirtyDeps.put(skyKey, new AtomicInteger(dirtyDeps.size())); + for (var dirtyDep : dirtyDeps) { + dirtyRdeps.compute( + dirtyDep, + (unusedKey, rdeps) -> { + if (rdeps == null) { + rdeps = new ArrayList<>(); + } + rdeps.add(skyKey); + return rdeps; + }); + } + } + } + } +}
diff --git a/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java index 7e478ba..db179aa 100644 --- a/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java +++ b/src/main/java/com/google/devtools/build/skyframe/IncrementalInMemoryNodeEntry.java
@@ -381,6 +381,32 @@ return version.lastChanged(); } + /** + * Returns this node's direct deps from the last evaluation if the node may be resurrected by + * change pruning; otherwise returns {@code null}. The node may be kept iff every returned dep is + * still present and was not changed more recently than {@link #lastEvaluatedVersion}. + */ + @Nullable + final Iterable<SkyKey> lastBuildDepsIfChangePrunable() { + var localDirtyBuildingState = dirtyBuildingState; + if (localDirtyBuildingState == null + || !localDirtyBuildingState.isIncremental() + || isChanged()) { + return null; + } + try { + return localDirtyBuildingState.getLastBuildDirectDeps().getAllElementsAsIterable(); + } catch (InterruptedException e) { + // An incremental dirty state returns its stored deps without blocking. + throw new IllegalStateException(e); + } + } + + /** Returns the version at which this node was last evaluated; see {@link NodeVersion}. */ + final Version lastEvaluatedVersion() { + return version.lastEvaluated(); + } + @Override public final synchronized ImmutableSet<SkyKey> getAllDirectDepsForIncompleteNode() throws InterruptedException {
diff --git a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java index 3053d4a..de34dd4 100644 --- a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
@@ -79,8 +79,12 @@ * be recomputed and the new values stored in the cache again. * * <p>To delete all dirty values, you can specify 0 for the limit. + * + * <p>If {@code keepChangePrunableNodes} is true, dirty values that change pruning would mark + * clean when they are next requested are exempt from deletion, regardless of how long they have + * been dirty. */ - void deleteDirty(long versionAgeLimit); + void deleteDirty(long versionAgeLimit, boolean keepChangePrunableNodes); /** * Returns the values in the graph.
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java index 136fb9f..9c6a336 100644 --- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -486,14 +486,14 @@ .containsExactly(skyKey("top"), skyKey("d1"), d2Key, ErrorTransienceValue.KEY); String[] noKeys = {}; - tester.evaluator.deleteDirty(2); + tester.evaluator.deleteDirty(2, /* keepChangePrunableNodes= */ false); tester.eval(true, noKeys); // The top node's value is dirty, but less than two generations old, so it wasn't deleted. assertThat(tester.evaluator.getValues().keySet()) .containsExactly(skyKey("top"), skyKey("d1"), d2Key, ErrorTransienceValue.KEY); - tester.evaluator.deleteDirty(2); + tester.evaluator.deleteDirty(2, /* keepChangePrunableNodes= */ false); tester.eval(true, noKeys); // The top node's value was dirty, and was two generations old, so it was deleted. @@ -510,7 +510,184 @@ assertThat(tester.evalAndGet(/*keepGoing=*/ false, topKey)).isEqualTo(new StringValue("value")); failBuildAndRemoveValue(leafKey); - tester.evaluator.deleteDirty(0); + tester.evaluator.deleteDirty(0, /* keepChangePrunableNodes= */ false); + } + + @Test + public void deleteDirtyKeepsChangePrunableNode() throws Exception { + // d -> b, c -> b, b -> a. Changing a so that b change-prunes and then evaluating only c leaves + // d + // dirty, even though change pruning would verify it clean (its only dep b is unchanged). + // Without + // rescue, the dirty-node GC deletes d and it must be recomputed the next time it is requested; + // with rescue, d survives and is verified clean. + SkyKey a = nonHermeticKey("a"); + SkyKey b = skyKey("b"); + SkyKey c = skyKey("c"); + SkyKey d = skyKey("d"); + StringValue fixedB = new StringValue("fixed-b"); + AtomicBoolean dEvaluated = new AtomicBoolean(false); + + tester.set(a, new StringValue("a1")); + // b depends on a but always returns the same value, so it change-prunes when a changes. + tester.getOrCreate(b).setBuilder((skyKey, env) -> env.getValue(a) == null ? null : fixedB); + tester.getOrCreate(c).addDependency(b).setComputedValue(COPY); + tester + .getOrCreate(d) + .setBuilder( + (skyKey, env) -> { + dEvaluated.set(true); + return env.getValue(b); + }); + + // The initial evaluation computes a, b, c and d. + tester.eval(/* keepGoing= */ false, c, d); + assertThat(tester.evaluator.getValues().keySet()).containsAtLeast(a, b, c, d); + + // Change a (b re-evaluates to the same value) and evaluate only c. b change-prunes, c is + // verified clean, and d is left dirty without being touched. + tester.set(a, new StringValue("a2")); + tester.invalidate(); + dEvaluated.set(false); + tester.eval(/* keepGoing= */ false, c); + assertThat(dEvaluated.get()).isFalse(); + assertThat(tester.getDirtyKeys()).contains(d); + + // Run dirty-node GC with the smallest possible version window. + String[] noKeys = {}; + tester.evaluator.deleteDirty(0, /* keepChangePrunableNodes= */ true); + tester.eval(/* keepGoing= */ false, noKeys); + + // d's only dep b change-pruned, so d is verifiable-clean and is kept rather than deleted. + assertThat(tester.evaluator.getValues().keySet()).contains(d); + // It is kept dirty (not eagerly recomputed), so it has no done value yet. + assertThat(tester.evaluator.getExistingValue(d)).isNull(); + + // Requesting d now verifies it clean via change pruning without recomputing it. + dEvaluated.set(false); + assertThat(tester.evalAndGet(/* keepGoing= */ false, d)).isEqualTo(fixedB); + assertThat(dEvaluated.get()).isFalse(); + } + + @Test + public void deleteDirtyDeletesChangePrunableNodeIfNotKeeping() throws Exception { + // Same setup as deleteDirtyKeepsChangePrunableNode, but without keepChangePrunableNodes, the + // dirty node d is deleted even though change pruning would verify it clean. + SkyKey a = nonHermeticKey("a"); + SkyKey b = skyKey("b"); + SkyKey c = skyKey("c"); + SkyKey d = skyKey("d"); + StringValue fixedB = new StringValue("fixed-b"); + + tester.set(a, new StringValue("a1")); + // b depends on a but always returns the same value, so it change-prunes when a changes. + tester.getOrCreate(b).setBuilder((skyKey, env) -> env.getValue(a) == null ? null : fixedB); + tester.getOrCreate(c).addDependency(b).setComputedValue(COPY); + tester.getOrCreate(d).addDependency(b).setComputedValue(COPY); + + tester.eval(/* keepGoing= */ false, c, d); + assertThat(tester.evaluator.getValues().keySet()).containsAtLeast(a, b, c, d); + + // Change a (b re-evaluates to the same value) and evaluate only c, leaving d dirty. + tester.set(a, new StringValue("a2")); + tester.invalidate(); + tester.eval(/* keepGoing= */ false, c); + assertThat(tester.getDirtyKeys()).contains(d); + + String[] noKeys = {}; + tester.evaluator.deleteDirty(0, /* keepChangePrunableNodes= */ false); + tester.eval(/* keepGoing= */ false, noKeys); + + assertThat(tester.evaluator.getValues().keySet()).doesNotContain(d); + } + + @Test + public void deleteDirtyKeepsChangePrunableChain() throws Exception { + // d -> bPrime -> b -> a, and c -> b. Changing a so that b change-prunes and evaluating only c + // leaves bPrime and d as unenqueued dirty orphans. bPrime is verifiable-clean because its dep b + // is done and unchanged; d is verifiable-clean only because bPrime is itself kept. + SkyKey a = nonHermeticKey("a"); + SkyKey b = skyKey("b"); + SkyKey bPrime = skyKey("bPrime"); + SkyKey c = skyKey("c"); + SkyKey d = skyKey("d"); + StringValue fixedB = new StringValue("fixed-b"); + AtomicBoolean dEvaluated = new AtomicBoolean(false); + + tester.set(a, new StringValue("a1")); + // b depends on a but always returns the same value, so it change-prunes when a changes. + tester.getOrCreate(b).setBuilder((skyKey, env) -> env.getValue(a) == null ? null : fixedB); + tester.getOrCreate(bPrime).addDependency(b).setComputedValue(COPY); + tester.getOrCreate(c).addDependency(b).setComputedValue(COPY); + tester + .getOrCreate(d) + .setBuilder( + (skyKey, env) -> { + dEvaluated.set(true); + return env.getValue(bPrime); + }); + + // The initial evaluation computes a, b, bPrime, c and d. + tester.eval(/* keepGoing= */ false, c, d); + assertThat(tester.evaluator.getValues().keySet()).containsAtLeast(a, b, bPrime, c, d); + + // Change a (b re-evaluates to the same value) and evaluate only c. b change-prunes; bPrime and + // d + // are left dirty without being touched. + tester.set(a, new StringValue("a2")); + tester.invalidate(); + dEvaluated.set(false); + tester.eval(/* keepGoing= */ false, c); + assertThat(dEvaluated.get()).isFalse(); + assertThat(tester.getDirtyKeys()).containsAtLeast(bPrime, d); + + // Run dirty-node GC with the smallest possible version window. + String[] noKeys = {}; + tester.evaluator.deleteDirty(0, /* keepChangePrunableNodes= */ true); + tester.eval(/* keepGoing= */ false, noKeys); + + // The whole chain is verifiable-clean, so both bPrime and (transitively) d are kept, not + // deleted. + assertThat(tester.evaluator.getValues().keySet()).containsAtLeast(bPrime, d); + + // Requesting d now verifies the chain clean without recomputing d. + dEvaluated.set(false); + assertThat(tester.evalAndGet(/* keepGoing= */ false, d)).isEqualTo(fixedB); + assertThat(dEvaluated.get()).isFalse(); + } + + @Test + public void deleteDirtyDeletesNodeNeedingRebuildToPrune() throws Exception { + // b -> a, d -> b, plus an unrelated direct consumer e -> a. Changing a and evaluating only e + // leaves b dirty (its dep a changed) and never recomputed, so b cannot be verified clean + // without + // a rebuild. The GC therefore deletes b and its rdep d even with rescue. + SkyKey a = nonHermeticKey("a"); + SkyKey b = skyKey("b"); + SkyKey d = skyKey("d"); + SkyKey e = skyKey("e"); + StringValue fixedB = new StringValue("fixed-b"); + + tester.set(a, new StringValue("a1")); + tester.getOrCreate(b).setBuilder((skyKey, env) -> env.getValue(a) == null ? null : fixedB); + tester.getOrCreate(d).addDependency(b).setComputedValue(COPY); + tester.getOrCreate(e).addDependency(a).setComputedValue(COPY); + + tester.eval(/* keepGoing= */ false, d, e); + assertThat(tester.evaluator.getValues().keySet()).containsAtLeast(a, b, d, e); + + // Change a and evaluate only e, which recomputes e but not b or d. + tester.set(a, new StringValue("a2")); + tester.invalidate(); + tester.eval(/* keepGoing= */ false, e); + assertThat(tester.getDirtyKeys()).containsAtLeast(b, d); + + String[] noKeys = {}; + tester.evaluator.deleteDirty(0, /* keepChangePrunableNodes= */ true); + tester.eval(/* keepGoing= */ false, noKeys); + + // b needs a rebuild to discover that it would prune, so it (and its rdep d) are still GC'd. + assertThat(tester.evaluator.getValues().keySet()).containsNoneOf(b, d); } @Test
diff --git a/src/test/shell/integration/loading_phase_test.sh b/src/test/shell/integration/loading_phase_test.sh index c828ec5..ae9369e 100755 --- a/src/test/shell/integration/loading_phase_test.sh +++ b/src/test/shell/integration/loading_phase_test.sh
@@ -260,6 +260,33 @@ assert_equals "3" $(wc -l "$TEST_log") } +function test_unrelated_glob_change_pruned() { + # Adding a file that the glob does not match changes the directory listing and thus dirties the + # shared glob, but the glob re-evaluates to the same matches and change-prunes. + local -r pkg="${FUNCNAME}" + mkdir -p "$pkg/data" || fail "could not create \"$pkg/data\"" + echo a > "$pkg/data/f0.txt" + echo b > "$pkg/data/f1.txt" + echo '[filegroup(name = "t%d" % i, srcs = glob(["data/*.txt"])) for i in range(21)]' \ + > "$pkg/BUILD" + + local -r gc_flag="--experimental_keep_change_prunable_nodes_during_gc" + bazel build "$gc_flag" "//$pkg:all" >& "$TEST_log" || fail "Expected initial build to succeed" + local before="$(bazel dump --skyframe=count 2>/dev/null \ + | awk '/^CONFIGURED_TARGET/{print $2}')" + + # Add a file not matched by the glob (dirties the directory listing; the glob change-prunes), + # build only one target (orphaning the other 20), then a no-op build to flush the dirty-node + # GC's deferred deletions. + echo unrelated > "$pkg/data/notes.md" + bazel build "$gc_flag" "//$pkg:t0" >& "$TEST_log" || fail "Expected build of t0 to succeed" + bazel build "$gc_flag" "//$pkg:t0" >& "$TEST_log" || fail "Expected flush build to succeed" + local after="$(bazel dump --skyframe=count 2>/dev/null \ + | awk '/^CONFIGURED_TARGET/{print $2}')" + + assert_equals "$before" "$after" +} + function test_glob_with_subpackage2() { local -r pkg="${FUNCNAME}" mkdir -p "$pkg" || fail "could not create \"$pkg\""