diff options
16 files changed, 305 insertions, 170 deletions
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java index 7a584ecd1f..b6c582559e 100644 --- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java @@ -18,7 +18,7 @@ import com.google.common.base.Predicates; import com.google.common.collect.ImmutableList; import com.google.common.collect.Maps; import com.google.devtools.build.lib.util.Preconditions; - +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import java.util.EnumSet; import java.util.HashMap; import java.util.Map; @@ -39,7 +39,8 @@ public class DelegatingWalkableGraph implements WalkableGraph { private NodeEntry getEntry(SkyKey key) { NodeEntry entry = Preconditions.checkNotNull( - graph.getBatchWithFieldHints(ImmutableList.of(key), NodeEntryField.VALUE_ONLY).get(key), + graph.getBatchWithFieldHints( + null, Reason.OTHER, ImmutableList.of(key), NodeEntryField.VALUE_ONLY).get(key), key); Preconditions.checkState(entry.isDone(), "%s %s", key, entry); return entry; @@ -48,7 +49,8 @@ public class DelegatingWalkableGraph implements WalkableGraph { @Override public boolean exists(SkyKey key) { NodeEntry entry = - graph.getBatchWithFieldHints(ImmutableList.of(key), NodeEntryField.NO_FIELDS).get(key); + graph.getBatchWithFieldHints( + null, Reason.OTHER, ImmutableList.of(key), NodeEntryField.NO_FIELDS).get(key); return entry != null && entry.isDone(); } @@ -71,7 +73,8 @@ public class DelegatingWalkableGraph implements WalkableGraph { public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) { return Maps.filterValues( Maps.transformValues( - graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY), GET_SKY_VALUE_FUNCTION), + graph.getBatchWithFieldHints(null, Reason.OTHER, keys, NodeEntryField.VALUE_ONLY), + GET_SKY_VALUE_FUNCTION), Predicates.notNull()); } @@ -79,7 +82,7 @@ public class DelegatingWalkableGraph implements WalkableGraph { public Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys) { Map<SkyKey, Exception> result = new HashMap<>(); Map<SkyKey, NodeEntry> graphResult = - graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY); + graph.getBatchWithFieldHints(null, Reason.OTHER, keys, NodeEntryField.VALUE_ONLY); for (SkyKey key : keys) { NodeEntry nodeEntry = graphResult.get(key); if (nodeEntry == null || !nodeEntry.isDone()) { @@ -103,8 +106,8 @@ public class DelegatingWalkableGraph implements WalkableGraph { @Override public Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys) { - Map<SkyKey, NodeEntry> entries = - graph.getBatchWithFieldHints(keys, EnumSet.of(NodeEntryField.DIRECT_DEPS)); + Map<SkyKey, NodeEntry> entries = graph.getBatchWithFieldHints( + null, Reason.OTHER, keys, EnumSet.of(NodeEntryField.DIRECT_DEPS)); Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size()); for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) { Preconditions.checkState(entry.getValue().isDone(), entry); @@ -115,8 +118,8 @@ public class DelegatingWalkableGraph implements WalkableGraph { @Override public Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) { - Map<SkyKey, NodeEntry> entries = - graph.getBatchWithFieldHints(keys, EnumSet.of(NodeEntryField.REVERSE_DEPS)); + Map<SkyKey, NodeEntry> entries = graph.getBatchWithFieldHints( + null, Reason.OTHER, keys, EnumSet.of(NodeEntryField.REVERSE_DEPS)); Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size()); for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) { Preconditions.checkState(entry.getValue().isDone(), entry); diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java index a9c067d6fd..0db7daddf9 100644 --- a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java @@ -14,8 +14,8 @@ package com.google.devtools.build.skyframe; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; - import java.util.Map; +import javax.annotation.Nullable; /** * Interface between a single version of the graph and the evaluator. Supports mutation of that @@ -27,6 +27,11 @@ interface EvaluableGraph extends QueryableGraph, DeletableGraph { * Like {@link QueryableGraph#getBatchWithFieldHints}, except it creates a new node for each key * not already present in the graph. Thus, the returned map will have an entry for each key in * {@code keys}. + * + * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are + * being requested. + * @param reason the reason the nodes are being requested. */ - Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys); + Map<SkyKey, NodeEntry> createIfAbsentBatch( + @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys); } diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java index 6f25093e41..9eee52e581 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java @@ -18,7 +18,7 @@ import java.util.Map; /** {@link ProcessableGraph} that exposes the contents of the entire graph. */ interface InMemoryGraph extends ProcessableGraph, InvalidatableGraph { @Override - Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys); + Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys); /** * Returns a read-only live view of the nodes in the graph. All node are included. Dirty values diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java index ef6e24b1a6..e068c3f4ad 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java @@ -19,11 +19,11 @@ import com.google.common.base.Predicates; import com.google.common.collect.ImmutableMap; import com.google.common.collect.MapMaker; import com.google.common.collect.Maps; - import java.util.Collections; import java.util.EnumSet; import java.util.Map; import java.util.concurrent.ConcurrentMap; +import javax.annotation.Nullable; /** * An in-memory graph implementation. All operations are thread-safe with ConcurrentMap semantics. @@ -51,15 +51,15 @@ public class InMemoryGraphImpl implements InMemoryGraph { } @Override - public NodeEntry get(SkyKey skyKey) { + public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey skyKey) { return nodeMap.get(skyKey); } @Override - public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) { + public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) { ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder(); for (SkyKey key : keys) { - NodeEntry entry = get(key); + NodeEntry entry = get(null, Reason.OTHER, key); if (entry != null) { builder.put(key, entry); } @@ -69,8 +69,8 @@ public class InMemoryGraphImpl implements InMemoryGraph { @Override public Map<SkyKey, NodeEntry> getBatchWithFieldHints( - Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) { - return getBatch(keys); + SkyKey requestor, Reason reason, Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) { + return getBatchForInvalidation(keys); } protected NodeEntry createIfAbsent(SkyKey key) { @@ -80,7 +80,8 @@ public class InMemoryGraphImpl implements InMemoryGraph { } @Override - public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) { + public Map<SkyKey, NodeEntry> createIfAbsentBatch( + @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) { ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder(); for (SkyKey key : keys) { builder.put(key, createIfAbsent(key)); diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java index 5d853b7aff..38604ed50d 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java @@ -29,7 +29,7 @@ import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvali import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState; import com.google.devtools.build.skyframe.ParallelEvaluator.EventFilter; import com.google.devtools.build.skyframe.ParallelEvaluator.Receiver; - +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import java.io.PrintStream; import java.util.Collection; import java.util.HashMap; @@ -129,7 +129,7 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { Sets.filter(dirtyKeyTracker.getDirtyKeys(), new Predicate<SkyKey>() { @Override public boolean apply(SkyKey skyKey) { - NodeEntry entry = graph.get(skyKey); + NodeEntry entry = graph.get(null, Reason.OTHER, skyKey); Preconditions.checkNotNull(entry, skyKey); Preconditions.checkState(entry.isDirty(), skyKey); return entry.getVersion().atMost(threshold); @@ -207,7 +207,7 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { Entry<SkyKey, SkyValue> entry = it.next(); SkyKey key = entry.getKey(); SkyValue newValue = entry.getValue(); - NodeEntry prevEntry = graph.get(key); + NodeEntry prevEntry = graph.get(null, Reason.OTHER, key); if (prevEntry != null && prevEntry.isDone()) { Iterable<SkyKey> directDeps = prevEntry.getDirectDeps(); Preconditions.checkState(Iterables.isEmpty(directDeps), @@ -280,7 +280,7 @@ public final class InMemoryMemoizingEvaluator implements MemoizingEvaluator { @Nullable @Override public NodeEntry getExistingEntryForTesting(SkyKey key) { - return graph.get(key); + return graph.get(null, Reason.OTHER, key); } @Override diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java index 243740705a..8abdae6263 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java @@ -30,5 +30,5 @@ public interface InvalidatableGraph { * {@code keys}, {@code m.get(k).equals(e)} iff {@code get(k) == e} and {@code e != null}, and * {@code !m.containsKey(k)} iff {@code get(k) == null}. */ - Map<SkyKey, ? extends ThinNodeEntry> getBatch(Iterable<SkyKey> keys); + Map<SkyKey, ? extends ThinNodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys); } diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java index 1fe90d193e..c8dd68a0fe 100644 --- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java +++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java @@ -269,7 +269,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends InvalidatableGraph> for (SkyKey key : unvisitedKeys) { pendingVisitations.add(Pair.of(key, InvalidationType.DELETED)); } - final Map<SkyKey, NodeEntry> entries = graph.getBatch(unvisitedKeys); + final Map<SkyKey, NodeEntry> entries = graph.getBatchForInvalidation(unvisitedKeys); for (final SkyKey key : unvisitedKeys) { executor.execute( new Runnable() { @@ -305,7 +305,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends InvalidatableGraph> entry.isDone() ? entry.getDirectDeps() : entry.getAllDirectDepsForIncompleteNode(); - Map<SkyKey, NodeEntry> depMap = graph.getBatch(directDeps); + Map<SkyKey, NodeEntry> depMap = graph.getBatchForInvalidation(directDeps); for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) { NodeEntry dep = directDepEntry.getValue(); if (dep != null) { @@ -432,7 +432,7 @@ public abstract class InvalidatingNodeVisitor<TGraph extends InvalidatableGraph> pendingVisitations.add(Pair.of(key, invalidationType)); } } - final Map<SkyKey, ? extends ThinNodeEntry> entries = graph.getBatch(keysToGet); + final Map<SkyKey, ? extends ThinNodeEntry> entries = graph.getBatchForInvalidation(keysToGet); if (enqueueingKeyForExistenceCheck != null && entries.size() != keysToGet.size()) { Set<SkyKey> missingKeys = Sets.difference(ImmutableSet.copyOf(keysToGet), entries.keySet()); throw new IllegalStateException( 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 8cd502dd45..61c93cb757 100644 --- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java +++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java @@ -49,6 +49,7 @@ import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationS import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState; import com.google.devtools.build.skyframe.NodeEntry.DependencyState; import com.google.devtools.build.skyframe.NodeEntry.DirtyState; +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException; import java.util.ArrayDeque; @@ -222,8 +223,11 @@ public final class ParallelEvaluator implements Evaluator { this.errorHandler = errorHandler; } - private Map<SkyKey, NodeEntry> getBatchValues(Iterable<SkyKey> keys) { - return graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY); + private Map<SkyKey, NodeEntry> getBatchValues( + SkyKey parent, + Reason reason, + Iterable<SkyKey> keys) { + return graph.getBatchWithFieldHints(parent, reason, keys, NodeEntryField.VALUE_ONLY); } /** Receives the events from the NestedSet and delegates to the reporter. */ @@ -312,8 +316,8 @@ public final class ParallelEvaluator implements Evaluator { ValueVisitor visitor) { this.skyKey = skyKey; this.oldDeps = oldDeps; - this.directDeps = Collections.unmodifiableMap( - batchPrefetch(directDeps, oldDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey)); + this.directDeps = Collections.unmodifiableMap(batchPrefetch( + skyKey, directDeps, oldDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey)); this.bubbleErrorInfo = bubbleErrorInfo; this.visitor = visitor; Preconditions.checkState( @@ -323,7 +327,7 @@ public final class ParallelEvaluator implements Evaluator { } private Map<SkyKey, NodeEntry> batchPrefetch( - GroupedList<SkyKey> depKeys, Set<SkyKey> oldDeps, boolean assertDone, + SkyKey requestor, GroupedList<SkyKey> depKeys, Set<SkyKey> oldDeps, boolean assertDone, SkyKey keyForDebugging) { Iterable<SkyKey> depKeysAsIterable = Iterables.concat(depKeys); Iterable<SkyKey> keysToPrefetch = depKeysAsIterable; @@ -332,7 +336,7 @@ public final class ParallelEvaluator implements Evaluator { keysToPrefetchBuilder.addAll(depKeysAsIterable).addAll(oldDeps); keysToPrefetch = keysToPrefetchBuilder.build(); } - Map<SkyKey, NodeEntry> batchMap = getBatchValues(keysToPrefetch); + Map<SkyKey, NodeEntry> batchMap = getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch); if (PREFETCH_OLD_DEPS) { batchMap = ImmutableMap.copyOf( Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable)))); @@ -357,7 +361,7 @@ public final class ParallelEvaluator implements Evaluator { Preconditions.checkState(building, skyKey); } - private NestedSet<TaggedEvents> buildEvents(boolean missingChildren) { + private NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean missingChildren) { // Aggregate the nested set of events from the direct deps, also adding the events from // building this value. NestedSetBuilder<TaggedEvents> eventBuilder = NestedSetBuilder.stableOrder(); @@ -367,10 +371,10 @@ public final class ParallelEvaluator implements Evaluator { } if (storedEventFilter.storeEvents()) { // Only do the work of processing children if we're going to store events. - GroupedList<SkyKey> depKeys = graph.get(skyKey).getTemporaryDirectDeps(); + GroupedList<SkyKey> depKeys = entry.getTemporaryDirectDeps(); Map<SkyKey, SkyValue> deps = getValuesMaybeFromError( - Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements()); + null, Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements()); if (!missingChildren && depKeys.numElements() != deps.size()) { throw new IllegalStateException( "Missing keys for " @@ -378,7 +382,7 @@ public final class ParallelEvaluator implements Evaluator { + ": " + Sets.difference(depKeys.toSet(), deps.keySet()) + ", " - + graph.get(skyKey)); + + entry); } for (SkyValue value : deps.values()) { if (value == NULL_MARKER) { @@ -425,13 +429,14 @@ public final class ParallelEvaluator implements Evaluator { * dependencies of this node <i>must</i> already have been registered, since this method may * register a dependence on the error transience node, which should always be the last dep. */ - private void setError(ErrorInfo errorInfo, boolean isDirectlyTransient) { + private void setError(NodeEntry state, ErrorInfo errorInfo, boolean isDirectlyTransient) { Preconditions.checkState(value == null, "%s %s %s", skyKey, value, errorInfo); Preconditions.checkState(this.errorInfo == null, "%s %s %s", skyKey, this.errorInfo, errorInfo); if (isDirectlyTransient) { - NodeEntry errorTransienceNode = graph.get(ErrorTransienceValue.KEY); + NodeEntry errorTransienceNode = + graph.get(skyKey, Reason.RDEP_ADDITION, ErrorTransienceValue.KEY); DependencyState triState; if (oldDeps.contains(ErrorTransienceValue.KEY)) { triState = errorTransienceNode.checkIfDoneForDirtyReverseDep(skyKey); @@ -440,8 +445,6 @@ public final class ParallelEvaluator implements Evaluator { } Preconditions.checkState(triState == DependencyState.DONE, "%s %s %s", skyKey, triState, errorInfo); - - final NodeEntry state = graph.get(skyKey); state.addTemporaryDirectDeps( GroupedListHelper.create(ImmutableList.of(ErrorTransienceValue.KEY))); state.signalDep(); @@ -451,6 +454,7 @@ public final class ParallelEvaluator implements Evaluator { } private Map<SkyKey, SkyValue> getValuesMaybeFromError( + @Nullable SkyKey requestor, Iterable<SkyKey> keys, @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo, int keySize) { @@ -467,7 +471,8 @@ public final class ParallelEvaluator implements Evaluator { missingKeys.add(key); } } - Map<SkyKey, NodeEntry> missingEntries = getBatchValues(missingKeys); + Map<SkyKey, NodeEntry> missingEntries = + getBatchValues(requestor, Reason.DEP_REQUESTED, missingKeys); for (SkyKey key : missingKeys) { builder.put(key, maybeGetValueFromError(key, missingEntries.get(key), bubbleErrorInfo)); } @@ -483,7 +488,7 @@ public final class ParallelEvaluator implements Evaluator { "Error transience key cannot be in requested deps of %s", skyKey); Map<SkyKey, SkyValue> values = - getValuesMaybeFromError(depKeys, bubbleErrorInfo, depKeys.size()); + getValuesMaybeFromError(skyKey, depKeys, bubbleErrorInfo, depKeys.size()); for (Map.Entry<SkyKey, SkyValue> depEntry : values.entrySet()) { SkyKey depKey = depEntry.getKey(); SkyValue depValue = depEntry.getValue(); @@ -495,9 +500,9 @@ public final class ParallelEvaluator implements Evaluator { + " was already in deps of " + skyKey + "( dep: " - + graph.get(depKey) + + graph.get(skyKey, Reason.OTHER, depKey) + ", parent: " - + graph.get(skyKey)); + + graph.get(null, Reason.OTHER, skyKey)); } valuesMissing = true; addDep(depKey); @@ -636,8 +641,7 @@ public final class ParallelEvaluator implements Evaluator { * <p>The node entry is informed if the node's value and error are definitive via the flag * {@code completeValue}. */ - void commit(boolean enqueueParents) { - NodeEntry primaryEntry = Preconditions.checkNotNull(graph.get(skyKey), skyKey); + void commit(NodeEntry primaryEntry, boolean enqueueParents) { // Construct the definitive error info, if there is one. finalizeErrorInfo(); @@ -648,7 +652,7 @@ public final class ParallelEvaluator implements Evaluator { // (2) value == null && enqueueParents happens for values that are found to have errors // during a --keep_going build. - NestedSet<TaggedEvents> events = buildEvents(/*missingChildren=*/false); + NestedSet<TaggedEvents> events = buildEvents(primaryEntry, /*missingChildren=*/false); Version valueVersion; SkyValue valueWithMetadata; if (value == null) { @@ -663,11 +667,12 @@ public final class ParallelEvaluator implements Evaluator { // Remove the rdep on this entry for each of its old deps that is no longer a direct dep. Set<SkyKey> depsToRemove = Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet()); - for (NodeEntry oldDepEntry : - graph - .getBatchWithFieldHints( - depsToRemove, EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)) - .values()) { + Collection<NodeEntry> oldDepEntries = graph.getBatchWithFieldHints( + skyKey, + Reason.RDEP_REMOVAL, + depsToRemove, + EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)).values(); + for (NodeEntry oldDepEntry : oldDepEntries) { oldDepEntry.removeReverseDep(skyKey); } } @@ -694,7 +699,11 @@ public final class ParallelEvaluator implements Evaluator { progressReceiver.evaluated(skyKey, new SkyValueSupplier(primaryEntry), valueVersion.equals(graphVersion) ? EvaluationState.BUILT : EvaluationState.CLEAN); } - signalValuesAndEnqueueIfReady(enqueueParents ? visitor : null, reverseDeps, valueVersion); + signalValuesAndEnqueueIfReady( + enqueueParents ? visitor : null, + skyKey, + reverseDeps, + valueVersion); visitor.notifyDone(skyKey); replayingNestedSetEventVisitor.visit(events); @@ -878,7 +887,8 @@ public final class ParallelEvaluator implements Evaluator { private boolean invalidatedByErrorTransience(Collection<SkyKey> depGroup, NodeEntry entry) { return depGroup.size() == 1 && depGroup.contains(ErrorTransienceValue.KEY) - && !graph.get(ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion()); + && !graph.get( + null, Reason.OTHER, ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion()); } private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) { @@ -912,7 +922,8 @@ public final class ParallelEvaluator implements Evaluator { // usual, but we can't, because then the ErrorTransienceValue would remain as a dep, // which would be incorrect if, for instance, the value re-evaluated to a non-error. state.forceRebuild(); - graph.get(ErrorTransienceValue.KEY).removeReverseDep(skyKey); + graph.get( + skyKey, Reason.RDEP_REMOVAL, ErrorTransienceValue.KEY).removeReverseDep(skyKey); return DirtyOutcome.NEEDS_EVALUATION; } if (!keepGoing) { @@ -925,6 +936,8 @@ public final class ParallelEvaluator implements Evaluator { // a child error. Map<SkyKey, NodeEntry> entriesToCheck = graph.getBatchWithFieldHints( + skyKey, + Reason.EVALUATION, directDepsToCheck, EnumSet.of(NodeEntryField.VALUE, NodeEntryField.INDIVIDUAL_REVERSE_DEPS)); for (Map.Entry<SkyKey, NodeEntry> entry : entriesToCheck.entrySet()) { @@ -960,8 +973,8 @@ public final class ParallelEvaluator implements Evaluator { // TODO(bazel-team): If this signals the current node, consider falling through to the // VERIFIED_CLEAN case below directly, without scheduling a new Evaluate(). - for (Map.Entry<SkyKey, NodeEntry> e - : graph.createIfAbsentBatch(directDepsToCheck).entrySet()) { + for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch( + skyKey, Reason.ENQUEUING_CHILD, directDepsToCheck).entrySet()) { SkyKey directDep = e.getKey(); NodeEntry directDepEntry = e.getValue(); enqueueChild(skyKey, state, directDep, directDepEntry, /*depAlreadyExists=*/ true); @@ -982,7 +995,7 @@ public final class ParallelEvaluator implements Evaluator { } throw SchedulerException.ofError(state.getErrorInfo(), skyKey); } - signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion()); + signalValuesAndEnqueueIfReady(visitor, skyKey, reverseDeps, state.getVersion()); return DirtyOutcome.ALREADY_PROCESSED; case NEEDS_REBUILDING: maybeMarkRebuilding(state); @@ -996,7 +1009,9 @@ public final class ParallelEvaluator implements Evaluator { @Override public void run() { - NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey); + 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; @@ -1036,7 +1051,8 @@ public final class ParallelEvaluator implements Evaluator { } } - Map<SkyKey, NodeEntry> newlyRequestedDeps = getBatchValues(env.newlyRequestedDeps); + Map<SkyKey, NodeEntry> newlyRequestedDeps = + getBatchValues(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps); boolean isTransitivelyTransient = reifiedBuilderException.isTransient(); for (NodeEntry depEntry : Iterables.concat(env.directDeps.values(), newlyRequestedDeps.values())) { @@ -1051,8 +1067,11 @@ public final class ParallelEvaluator implements Evaluator { ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException, isTransitivelyTransient); registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env); - env.setError(errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient()); - env.commit(/*enqueueParents=*/keepGoing); + env.setError( + state, + errorInfo, + /*isDirectlyTransient=*/ reifiedBuilderException.isTransient()); + env.commit(state, /*enqueueParents=*/keepGoing); if (!shouldFailFast) { return; } @@ -1093,10 +1112,13 @@ public final class ParallelEvaluator implements Evaluator { skyKey, state, graph.getBatchWithFieldHints( - env.newlyRequestedDeps, EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)), + skyKey, + Reason.RDEP_ADDITION, + env.newlyRequestedDeps, + EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)), oldDeps, env); - env.commit(/*enqueueParents=*/true); + env.commit(state, /*enqueueParents=*/true); return; } @@ -1107,8 +1129,12 @@ public final class ParallelEvaluator implements Evaluator { // 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(childErrorKey), - "skyKey: %s, state: %s childErrorKey: %s", skyKey, state, childErrorKey); + NodeEntry childErrorEntry = Preconditions.checkNotNull( + graph.get(skyKey, Reason.OTHER, childErrorKey), + "skyKey: %s, state: %s childErrorKey: %s", + skyKey, + state, + childErrorKey); Preconditions.checkState( !state.getTemporaryDirectDeps().expensiveContains(childErrorKey), "Done error was already known: %s %s %s %s", @@ -1162,11 +1188,12 @@ public final class ParallelEvaluator implements Evaluator { // 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(/*enqueueParents=*/ true); + env.commit(state, /*enqueueParents=*/ true); return; } - for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(newDirectDeps).entrySet()) { + for (Map.Entry<SkyKey, NodeEntry> e + : graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) { SkyKey newDirectDep = e.getKey(); NodeEntry newDirectDepEntry = e.getValue(); enqueueChild( @@ -1209,11 +1236,12 @@ public final class ParallelEvaluator implements Evaluator { * cycles). */ private void signalValuesAndEnqueueIfReady( - @Nullable ValueVisitor visitor, Iterable<SkyKey> keys, Version version) { + @Nullable ValueVisitor visitor, SkyKey skyKey, Iterable<SkyKey> keys, Version version) { // No fields of the entry are needed here, since we're just enqueuing for evaluation, but more // importantly, these hints are not respected for not-done nodes. If they are, we may need to // alter this hint. - Map<SkyKey, NodeEntry> batch = graph.getBatchWithFieldHints(keys, NodeEntryField.NO_FIELDS); + Map<SkyKey, NodeEntry> batch = + graph.getBatchWithFieldHints(skyKey, Reason.SIGNAL_DEP, keys, NodeEntryField.NO_FIELDS); if (visitor != null) { for (SkyKey key : keys) { NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key); @@ -1236,8 +1264,8 @@ public final class ParallelEvaluator implements Evaluator { * If child is not done, removes {@param inProgressParent} from {@param child}'s reverse deps. * Returns whether child should be removed from inProgressParent's entry's direct deps. */ - private boolean removeIncompleteChild(SkyKey inProgressParent, SkyKey child) { - NodeEntry childEntry = graph.get(child); + private boolean removeIncompleteChildForCycle(SkyKey inProgressParent, SkyKey child) { + NodeEntry childEntry = graph.get(inProgressParent, Reason.CYCLE_CHECKING, child); if (!isDoneForBuild(childEntry)) { childEntry.removeInProgressReverseDep(inProgressParent); return true; @@ -1311,7 +1339,7 @@ public final class ParallelEvaluator implements Evaluator { // 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; - Map<SkyKey, NodeEntry> batch = getBatchValues(skyKeySet); + Map<SkyKey, NodeEntry> batch = getBatchValues(null, Reason.EVALUATION, skyKeySet); for (SkyKey key : skyKeySet) { if (!isDoneForBuild(batch.get(key))) { allAreDone = false; @@ -1330,7 +1358,7 @@ public final class ParallelEvaluator implements Evaluator { if (!keepGoing) { Set<SkyKey> cachedErrorKeys = new HashSet<>(); for (SkyKey skyKey : skyKeySet) { - NodeEntry entry = graph.get(skyKey); + NodeEntry entry = graph.get(null, Reason.EVALUATION, skyKey); if (entry == null) { continue; } @@ -1375,7 +1403,8 @@ public final class ParallelEvaluator implements Evaluator { // in the graph, by the time that it is needed. Creating it on demand in a parallel context sets // up a race condition, because there is no way to atomically create a node and set its value. NodeEntry errorTransienceEntry = Iterables.getOnlyElement( - graph.createIfAbsentBatch(ImmutableList.of(ErrorTransienceValue.KEY)).values()); + graph.createIfAbsentBatch( + null, Reason.EVALUATION, ImmutableList.of(ErrorTransienceValue.KEY)).values()); if (!errorTransienceEntry.isDone()) { injectValues( ImmutableMap.of(ErrorTransienceValue.KEY, (SkyValue) ErrorTransienceValue.INSTANCE), @@ -1383,7 +1412,8 @@ public final class ParallelEvaluator implements Evaluator { graph, dirtyKeyTracker); } - for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(skyKeys).entrySet()) { + for (Map.Entry<SkyKey, NodeEntry> e + : graph.createIfAbsentBatch(null, Reason.EVALUATION, skyKeys).entrySet()) { SkyKey skyKey = e.getKey(); NodeEntry entry = e.getValue(); // This must be equivalent to the code in enqueueChild above, in order to be thread-safe. @@ -1447,7 +1477,7 @@ public final class ParallelEvaluator implements Evaluator { ImmutableMap.of( errorKey, ValueWithMetadata.wrapWithMetadata( - graph.get(errorKey).getValueMaybeWithMetadata())); + graph.get(null, Reason.ERROR_BUBBLING, errorKey).getValueMaybeWithMetadata())); } } Preconditions.checkState(visitor.getCrashes().isEmpty(), visitor.getCrashes()); @@ -1494,7 +1524,9 @@ public final class ParallelEvaluator implements Evaluator { Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>(); boolean externalInterrupt = false; while (true) { - NodeEntry errorEntry = Preconditions.checkNotNull(graph.get(errorKey), errorKey); + NodeEntry errorEntry = Preconditions.checkNotNull( + graph.get(null, Reason.ERROR_BUBBLING, errorKey), + errorKey); Iterable<SkyKey> reverseDeps = errorEntry.isDone() ? errorEntry.getReverseDeps() : errorEntry.getInProgressReverseDeps(); @@ -1511,8 +1543,11 @@ public final class ParallelEvaluator implements Evaluator { // We are in a cycle. Don't try to bubble anything up -- cycle detection will kick in. return null; } - NodeEntry bubbleParentEntry = Preconditions.checkNotNull(graph.get(bubbleParent), - "parent %s of %s not in graph", bubbleParent, errorKey); + NodeEntry bubbleParentEntry = Preconditions.checkNotNull( + graph.get(errorKey, Reason.ERROR_BUBBLING, bubbleParent), + "parent %s of %s not in graph", + bubbleParent, + errorKey); // Might be the parent that requested the error. if (bubbleParentEntry.isDone()) { // This parent is cached from a previous evaluate call. We shouldn't bubble up to it @@ -1604,7 +1639,7 @@ public final class ParallelEvaluator implements Evaluator { /*isTransitivelyTransient=*/ false); bubbleErrorInfo.put(errorKey, ValueWithMetadata.error(ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)), - env.buildEvents(/*missingChildren=*/true))); + env.buildEvents(parentEntry, /*missingChildren=*/true))); continue; } } finally { @@ -1614,7 +1649,7 @@ public final class ParallelEvaluator implements Evaluator { // Builder didn't throw an exception, so just propagate this one up. bubbleErrorInfo.put(errorKey, ValueWithMetadata.error(ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)), - env.buildEvents(/*missingChildren=*/true))); + env.buildEvents(parentEntry, /*missingChildren=*/true))); } // Reset the interrupt bit if there was an interrupt from outside this evaluator interrupt. @@ -1649,7 +1684,10 @@ public final class ParallelEvaluator implements Evaluator { EvaluationResult.Builder<T> result = EvaluationResult.builder(); List<SkyKey> cycleRoots = new ArrayList<>(); for (SkyKey skyKey : skyKeys) { - SkyValue unwrappedValue = maybeGetValueFromError(skyKey, graph.get(skyKey), bubbleErrorInfo); + SkyValue unwrappedValue = maybeGetValueFromError( + skyKey, + graph.get(null, Reason.EVALUATION, skyKey), + bubbleErrorInfo); ValueWithMetadata valueWithMetadata = unwrappedValue == NULL_MARKER ? null : ValueWithMetadata.wrapWithMetadata(unwrappedValue); // Cycle checking: if there is a cycle, evaluation cannot progress, therefore, @@ -1782,7 +1820,7 @@ public final class ParallelEvaluator implements Evaluator { // A marker node means we are done with all children of a node. Since all nodes have // errors, we must have found errors in the children when that happens. key = graphPath.remove(graphPath.size() - 1); - entry = Preconditions.checkNotNull(graph.get(key), key); + entry = Preconditions.checkNotNull(graph.get(null, Reason.CYCLE_CHECKING, key), key); pathSet.remove(key); // Skip this node if it was first/last node of a cycle, and so has already been processed. if (entry.isDone()) { @@ -1807,7 +1845,7 @@ public final class ParallelEvaluator implements Evaluator { maybeMarkRebuilding(entry); GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps(); // Find out which children have errors. Similar logic to that in Evaluate#run(). - List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(Iterables.concat(directDeps)); + List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(key, Iterables.concat(directDeps)); Preconditions.checkState(!errorDeps.isEmpty(), "Value %s was not successfully evaluated, but had no child errors. ValueEntry: %s", key, entry); @@ -1817,10 +1855,11 @@ public final class ParallelEvaluator implements Evaluator { directDeps, Sets.difference(entry.getAllRemainingDirtyDirectDeps(), removedDeps), visitor); - env.setError(ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false); - env.commit(/*enqueueParents=*/false); + env.setError( + entry, ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false); + env.commit(entry, /*enqueueParents=*/false); } else { - entry = graph.get(key); + entry = graph.get(null, Reason.CYCLE_CHECKING, key); } Preconditions.checkNotNull(entry, key); @@ -1870,14 +1909,14 @@ public final class ParallelEvaluator implements Evaluator { // Construct error info for this node. Get errors from children, which are all done // except possibly for the cycleChild. List<ErrorInfo> allErrors = - getChildrenErrors( + getChildrenErrorsForCycleChecking( Iterables.concat(entry.getTemporaryDirectDeps()), /*unfinishedChild=*/ cycleChild); CycleInfo cycleInfo = new CycleInfo(cycle); // Add in this cycle. allErrors.add(ErrorInfo.fromCycle(cycleInfo)); - env.setError(ErrorInfo.fromChildErrors(key, allErrors), /*isTransient=*/false); - env.commit(/*enqueueParents=*/false); + env.setError(entry, ErrorInfo.fromChildErrors(key, allErrors), /*isTransient=*/false); + env.commit(entry, /*enqueueParents=*/false); continue; } else { // We need to return right away in the noKeepGoing case, so construct the cycle (with the @@ -1898,8 +1937,8 @@ public final class ParallelEvaluator implements Evaluator { // out. // TODO(janakr): If graph implementations start using these hints for not-done nodes, we may // have to change this. - Map<SkyKey, NodeEntry> childrenNodes = - graph.getBatchWithFieldHints(children, NodeEntryField.NO_FIELDS); + Map<SkyKey, NodeEntry> childrenNodes = graph.getBatchWithFieldHints( + key, Reason.CYCLE_CHECKING, children, NodeEntryField.NO_FIELDS); Preconditions.checkState(childrenNodes.size() == Iterables.size(children), childrenNodes); children = Maps.filterValues(childrenNodes, new Predicate<NodeEntry>() { @Override @@ -1917,7 +1956,7 @@ public final class ParallelEvaluator implements Evaluator { toVisit.push(nextValue); } } - return keepGoing ? getAndCheckDone(root).getErrorInfo() : null; + return keepGoing ? getAndCheckDoneForCycle(root).getErrorInfo() : null; } /** @@ -1934,10 +1973,10 @@ public final class ParallelEvaluator implements Evaluator { * @param children child nodes to query for errors. * @return List of ErrorInfos from all children that had errors. */ - private List<ErrorInfo> getChildrenErrorsForCycle(Iterable<SkyKey> children) { + private List<ErrorInfo> getChildrenErrorsForCycle(SkyKey parent, Iterable<SkyKey> children) { List<ErrorInfo> allErrors = new ArrayList<>(); boolean foundCycle = false; - for (NodeEntry childNode : getAndCheckDoneBatch(children).values()) { + for (NodeEntry childNode : getAndCheckDoneBatchForCycle(parent, children).values()) { ErrorInfo errorInfo = childNode.getErrorInfo(); if (errorInfo != null) { foundCycle |= !Iterables.isEmpty(errorInfo.getCycleInfo()); @@ -1955,9 +1994,12 @@ public final class ParallelEvaluator implements Evaluator { * @param unfinishedChild child which is allowed to not be done. * @return List of ErrorInfos from all children that had errors. */ - private List<ErrorInfo> getChildrenErrors(Iterable<SkyKey> children, SkyKey unfinishedChild) { + private List<ErrorInfo> getChildrenErrorsForCycleChecking( + Iterable<SkyKey> children, SkyKey unfinishedChild) { List<ErrorInfo> allErrors = new ArrayList<>(); - for (Entry<SkyKey, NodeEntry> childMapEntry : getBatchValues(children).entrySet()) { + Set<Entry<SkyKey, NodeEntry>> childEntries = + getBatchValues(null, Reason.CYCLE_CHECKING, children).entrySet(); + for (Entry<SkyKey, NodeEntry> childMapEntry : childEntries) { SkyKey childKey = childMapEntry.getKey(); NodeEntry childNodeEntry = childMapEntry.getValue(); ErrorInfo errorInfo = getErrorMaybe(childKey, childNodeEntry, @@ -2041,7 +2083,7 @@ public final class ParallelEvaluator implements Evaluator { SkyKey key, NodeEntry entry, Iterable<SkyKey> children) { Set<SkyKey> unfinishedDeps = new HashSet<>(); for (SkyKey child : children) { - if (removeIncompleteChild(key, child)) { + if (removeIncompleteChildForCycle(key, child)) { unfinishedDeps.add(child); } } @@ -2049,18 +2091,19 @@ public final class ParallelEvaluator implements Evaluator { return unfinishedDeps; } - private NodeEntry getAndCheckDone(SkyKey key) { - return checkDone(key, graph.get(key)); - } - private static NodeEntry checkDone(SkyKey key, NodeEntry entry) { Preconditions.checkNotNull(entry, key); Preconditions.checkState(entry.isDone(), "%s %s", key, entry); return entry; } - private Map<SkyKey, NodeEntry> getAndCheckDoneBatch(Iterable<SkyKey> keys) { - Map<SkyKey, NodeEntry> nodes = getBatchValues(keys); + private NodeEntry getAndCheckDoneForCycle(SkyKey key) { + return checkDone(key, graph.get(null, Reason.CYCLE_CHECKING, key)); + } + + private Map<SkyKey, NodeEntry> getAndCheckDoneBatchForCycle( + SkyKey parent, Iterable<SkyKey> keys) { + Map<SkyKey, NodeEntry> nodes = getBatchValues(parent, Reason.CYCLE_CHECKING, keys); for (Map.Entry<SkyKey, NodeEntry> nodeEntryMapEntry : nodes.entrySet()) { checkDone(nodeEntryMapEntry.getKey(), nodeEntryMapEntry.getValue()); } @@ -2096,7 +2139,8 @@ public final class ParallelEvaluator implements Evaluator { Version version, EvaluableGraph graph, DirtyKeyTracker dirtyKeyTracker) { - Map<SkyKey, NodeEntry> prevNodeEntries = graph.createIfAbsentBatch(injectionMap.keySet()); + Map<SkyKey, NodeEntry> prevNodeEntries = + graph.createIfAbsentBatch(null, Reason.OTHER, injectionMap.keySet()); for (Map.Entry<SkyKey, SkyValue> injectionEntry : injectionMap.entrySet()) { SkyKey key = injectionEntry.getKey(); SkyValue value = injectionEntry.getValue(); diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java index 27038021fe..75ce05c970 100644 --- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java +++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java @@ -23,9 +23,15 @@ import javax.annotation.Nullable; /** A graph that exposes its entries and structure, for use by classes that must traverse it. */ @ThreadSafe public interface QueryableGraph { - /** Returns the node with the given name, or {@code null} if the node does not exist. */ + /** + * Returns the node with the given {@code key}, or {@code null} if the node does not exist. + * + * @param requestor if non-{@code null}, the node on behalf of which {@code key} is being + * requested. + * @param reason the reason the node is being requested. + */ @Nullable - NodeEntry get(SkyKey key); + NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key); /** * Fetches all the given nodes. Returns a map {@code m} such that, for all {@code k} in {@code @@ -34,7 +40,65 @@ public interface QueryableGraph { * QueryableGraph implementation that allows it to possibly construct certain fields of the * returned node entries more lazily. Hints may only be applied to nodes in a certain state, like * done nodes. + * + * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are + * being requested. + * @param reason the reason the nodes are being requested. */ Map<SkyKey, NodeEntry> getBatchWithFieldHints( - Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields); + @Nullable SkyKey requestor, + Reason reason, + Iterable<SkyKey> keys, + EnumSet<NodeEntryField> fields); + + /** + * The reason that a node is being looked up in the Skyframe graph. + * + * <p>Alternate graph implementations may wish to make use of this information. + */ + enum Reason { + /** + * The node is being looked up as part of the prefetch step before evaluation of a SkyFunction. + */ + PREFETCH, + + /** + * The node is being fetched because it is about to be evaluated or it has already been + * evaluated, but *not* because it was just requested during evaluation of a SkyFunction (see + * DEP_REQUESTED). + */ + EVALUATION, + + /** The node is being looked up because it was requested during evaluation of a SkyFunction. */ + DEP_REQUESTED, + + /** The node is being looked up during the invalidation phase of Skyframe evaluation. */ + INVALIDATION, + + /** The node is being looked up during the cycle checking phase of Skyframe evaluation. */ + CYCLE_CHECKING, + + /** The node is being looked up so that an rdep can be added to it. */ + RDEP_ADDITION, + + /** The node is being looked up so that an rdep can be removed from it. */ + RDEP_REMOVAL, + + /** The node is being looked up so it can be enqueued for evaluation or change pruning. */ + ENQUEUING_CHILD, + + /** + * The node is being looked up so that it can be signaled that a dependency is now complete. + */ + SIGNAL_DEP, + + /** + * The node is being looking up as part of the error bubbling phase of fail-fast Skyframe + * evaluation. + */ + ERROR_BUBBLING, + + /** Some other reason than one of the above. */ + OTHER, + } } diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java index ed38be387e..6aaadcd80a 100644 --- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java +++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java @@ -19,7 +19,7 @@ import com.google.common.collect.Maps; import com.google.common.collect.Sets; import com.google.devtools.build.lib.events.EventHandler; import com.google.devtools.build.lib.util.Preconditions; - +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import java.util.HashMap; import java.util.Map; import java.util.Set; @@ -70,8 +70,8 @@ public class QueryableGraphBackedSkyFunctionEnvironment extends AbstractSkyFunct @Override protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(Set<SkyKey> depKeys) { - Map<SkyKey, NodeEntry> resultMap = - queryableGraph.getBatchWithFieldHints(depKeys, NodeEntryField.VALUE_ONLY); + Map<SkyKey, NodeEntry> resultMap = queryableGraph.getBatchWithFieldHints( + null, Reason.DEP_REQUESTED, depKeys, NodeEntryField.VALUE_ONLY); Map<SkyKey, NodeEntry> resultWithMissingKeys = new HashMap<>(resultMap); for (SkyKey missingDep : Sets.difference(depKeys, resultMap.keySet())) { resultWithMissingKeys.put(missingDep, null); diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java index 50bd380ed7..fe7c76fc91 100644 --- a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java +++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java @@ -14,7 +14,6 @@ package com.google.devtools.build.skyframe; import com.google.common.collect.Iterables; - import java.util.Collection; import java.util.Comparator; import java.util.EnumSet; @@ -91,8 +90,8 @@ public class DeterministicHelper extends NotifyingHelper { } @Override - public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) { - return makeDeterministic(super.getBatch(keys)); + public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) { + return makeDeterministic(super.getBatchForInvalidation(keys)); } } @@ -111,14 +110,18 @@ public class DeterministicHelper extends NotifyingHelper { } @Override - public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) { - return makeDeterministic(super.createIfAbsentBatch(keys)); + public Map<SkyKey, NodeEntry> createIfAbsentBatch( + @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) { + return makeDeterministic(super.createIfAbsentBatch(requestor, reason, keys)); } @Override public Map<SkyKey, NodeEntry> getBatchWithFieldHints( - Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) { - return makeDeterministic(super.getBatchWithFieldHints(keys, fields)); + @Nullable SkyKey requestor, + Reason reason, + Iterable<SkyKey> keys, + EnumSet<NodeEntryField> fields) { + return makeDeterministic(super.getBatchWithFieldHints(requestor, reason, keys, fields)); } } diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java index bb61d0f202..0cbc91ce32 100644 --- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java +++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java @@ -27,8 +27,8 @@ class DeterministicInMemoryGraph extends DeterministicHelper.DeterministicProces } @Override - public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) { - return getBatchWithFieldHints(keys, NodeEntryField.ALL_FIELDS); + public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) { + return getBatchWithFieldHints(null, Reason.INVALIDATION, keys, NodeEntryField.ALL_FIELDS); } @Override diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java index dbc418f79f..fb3058c103 100644 --- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java @@ -39,7 +39,7 @@ import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvali import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingNodeVisitor; import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState; import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationType; - +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import org.junit.After; import org.junit.Before; import org.junit.Test; @@ -93,7 +93,7 @@ public class EagerInvalidatorTest { boolean gcExpected() { throw new UnsupportedOperationException(); } private boolean isInvalidated(SkyKey key) { - NodeEntry entry = graph.get(key); + NodeEntry entry = graph.get(null, Reason.OTHER, key); if (gcExpected()) { return entry == null; } else { @@ -102,7 +102,7 @@ public class EagerInvalidatorTest { } private void assertChanged(SkyKey key) { - NodeEntry entry = graph.get(key); + NodeEntry entry = graph.get(null, Reason.OTHER, key); if (gcExpected()) { assertNull(entry); } else { @@ -111,7 +111,7 @@ public class EagerInvalidatorTest { } private void assertDirtyAndNotChanged(SkyKey key) { - NodeEntry entry = graph.get(key); + NodeEntry entry = graph.get(null, Reason.OTHER, key); if (gcExpected()) { assertNull(entry); } else { @@ -344,10 +344,12 @@ public class EagerInvalidatorTest { .setComputedValue(CONCATENATE); eval(false, skyKey("ab_c"), skyKey("bc")); - assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactly(skyKey("ab")); - assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc")); - assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactly(skyKey("ab_c"), - skyKey("bc")); + assertThat(graph.get(null, Reason.OTHER, skyKey("a")) + .getReverseDeps()).containsExactly(skyKey("ab")); + assertThat(graph.get(null, Reason.OTHER, skyKey("b")) + .getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc")); + assertThat(graph.get(null, Reason.OTHER, skyKey("c")) + .getReverseDeps()).containsExactly(skyKey("ab_c"), skyKey("bc")); invalidateWithoutError(null, skyKey("ab")); eval(false); @@ -361,15 +363,18 @@ public class EagerInvalidatorTest { if (reverseDepsPresent()) { reverseDeps.add(skyKey("ab")); } - assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("a")) + .getReverseDeps()).containsExactlyElementsIn(reverseDeps); reverseDeps.add(skyKey("bc")); - assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("b")) + .getReverseDeps()).containsExactlyElementsIn(reverseDeps); reverseDeps.clear(); if (reverseDepsPresent()) { reverseDeps.add(skyKey("ab_c")); } reverseDeps.add(skyKey("bc")); - assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactlyElementsIn(reverseDeps); + assertThat(graph.get(null, Reason.OTHER, skyKey("c")) + .getReverseDeps()).containsExactlyElementsIn(reverseDeps); } @Test @@ -438,7 +443,7 @@ public class EagerInvalidatorTest { assertFalse(state.isEmpty()); final Set<SkyKey> invalidated = Sets.newConcurrentHashSet(); assertFalse(isInvalidated(parent)); - assertNotNull(graph.get(parent).getValue()); + assertNotNull(graph.get(null, Reason.OTHER, parent).getValue()); receiver = new EvaluationProgressReceiver() { @Override public void invalidated(SkyKey skyKey, InvalidationState state) { diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java index 73e42ea4d7..df6f99ca22 100644 --- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java +++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java @@ -30,7 +30,7 @@ import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import com.google.devtools.build.lib.util.Preconditions; import com.google.devtools.build.skyframe.GraphTester.StringValue; import com.google.devtools.build.skyframe.NodeEntry.DependencyState; - +import com.google.devtools.build.skyframe.QueryableGraph.Reason; import org.junit.Before; import org.junit.Test; @@ -77,7 +77,7 @@ public abstract class GraphConcurrencyTest { @Test public void createIfAbsentBatchSanity() { - graph.createIfAbsentBatch(ImmutableList.of(key("cat"), key("dog"))); + graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key("cat"), key("dog"))); } @Test @@ -91,11 +91,11 @@ public abstract class GraphConcurrencyTest { new Runnable() { @Override public void run() { - graph.get(key); + graph.get(null, Reason.OTHER, key); } })); t.start(); - assertThat(graph.createIfAbsentBatch(ImmutableList.of(key))).isNotEmpty(); + assertThat(graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key))).isNotEmpty(); graph.remove(key); } } @@ -111,7 +111,7 @@ public abstract class GraphConcurrencyTest { public void run() { TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions( startThreads, "threads not started"); - graph.createIfAbsentBatch(ImmutableList.of(key)); + graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key)); } }; Runnable noCreateRunnable = @@ -120,7 +120,7 @@ public abstract class GraphConcurrencyTest { public void run() { TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions( startThreads, "threads not started"); - graph.get(key); + graph.get(null, Reason.OTHER, key); } }; List<Thread> threads = new ArrayList<>(2 * numThreads); @@ -144,7 +144,7 @@ public abstract class GraphConcurrencyTest { public void testAddRemoveRdeps() throws Exception { SkyKey key = key("foo"); final NodeEntry entry = Iterables.getOnlyElement( - graph.createIfAbsentBatch(ImmutableList.of(key)).values()); + graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key)).values()); // These numbers are arbitrary. int numThreads = 50; int numKeys = numThreads; @@ -169,7 +169,7 @@ public abstract class GraphConcurrencyTest { for (int i = 0; i < numKeys; i++) { rdepKeys.add(key("rdep" + i)); } - graph.createIfAbsentBatch(rdepKeys); + graph.createIfAbsentBatch(null, Reason.OTHER, rdepKeys); for (int i = 0; i < numKeys; i++) { final int j = i; Runnable r = @@ -200,18 +200,18 @@ public abstract class GraphConcurrencyTest { waitForSetValue.countDown(); wrapper.waitForTasksAndMaybeThrow(); assertFalse(ExecutorUtil.interruptibleShutdown(pool)); - assertEquals(new StringValue("foo1"), graph.get(key).getValue()); - assertEquals(numKeys + 1, Iterables.size(graph.get(key).getReverseDeps())); + assertEquals(new StringValue("foo1"), graph.get(null, Reason.OTHER, key).getValue()); + assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps())); graph = getGraph(getNextVersion(startingVersion)); - NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(key)); + NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(null, Reason.OTHER, key)); // Mark the node as dirty again and check that the reverse deps have been preserved. sameEntry.markDirty(true); startEvaluation(sameEntry); sameEntry.markRebuilding(); sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion)); - assertEquals(new StringValue("foo2"), graph.get(key).getValue()); - assertEquals(numKeys + 1, Iterables.size(graph.get(key).getReverseDeps())); + assertEquals(new StringValue("foo2"), graph.get(null, Reason.OTHER, key).getValue()); + assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps())); } // Tests adding inflight nodes with a given key while an existing node with the same key @@ -236,12 +236,13 @@ public abstract class GraphConcurrencyTest { new Runnable() { public void run() { for (SkyKey key : keys) { - NodeEntry entry = graph.get(key); + NodeEntry entry = graph.get(null, Reason.OTHER, key); if (entry == null) { nodeCreated.add(key); } } - Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(keys); + Map<SkyKey, NodeEntry> entries = + graph.createIfAbsentBatch(null, Reason.OTHER, keys); for (Integer keyNum : ImmutableList.of(keyNum1, keyNum2)) { SkyKey key = key("foo" + keyNum); NodeEntry entry = entries.get(key); @@ -255,7 +256,7 @@ public abstract class GraphConcurrencyTest { } } // This shouldn't cause any problems from the other threads. - graph.createIfAbsentBatch(keys); + graph.createIfAbsentBatch(null, Reason.OTHER, keys); } }; pool.execute(wrapper.wrap(r)); @@ -269,8 +270,9 @@ public abstract class GraphConcurrencyTest { SkyKey key = key("foo" + i); assertTrue(nodeCreated.contains(key)); assertTrue(valuesSet.contains(key)); - assertThat(graph.get(key).getValue()).isEqualTo(new StringValue("bar" + i)); - assertThat(graph.get(key).getVersion()).isEqualTo(startingVersion); + assertThat(graph.get(null, Reason.OTHER, key).getValue()) + .isEqualTo(new StringValue("bar" + i)); + assertThat(graph.get(null, Reason.OTHER, key).getVersion()).isEqualTo(startingVersion); } } @@ -289,16 +291,16 @@ public abstract class GraphConcurrencyTest { for (int i = 0; i < numKeys; i++) { keys.add(key("foo" + i)); } - Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(keys); + Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(null, Reason.OTHER, keys); for (int i = 0; i < numKeys; i++) { NodeEntry entry = entries.get(key("foo" + i)); startEvaluation(entry); entry.setValue(new StringValue("bar"), startingVersion); } - assertNotNull(graph.get(key("foo" + 0))); + assertNotNull(graph.get(null, Reason.OTHER, key("foo" + 0))); graph = getGraph(getNextVersion(startingVersion)); - assertNotNull(graph.get(key("foo" + 0))); + assertNotNull(graph.get(null, Reason.OTHER, key("foo" + 0))); ExecutorService pool1 = Executors.newFixedThreadPool(numThreads); ExecutorService pool2 = Executors.newFixedThreadPool(numThreads); ExecutorService pool3 = Executors.newFixedThreadPool(numThreads); @@ -323,7 +325,7 @@ public abstract class GraphConcurrencyTest { } catch (InterruptedException e) { throw new AssertionError(e); } - NodeEntry entry = graph.get(key("foo" + keyNum)); + NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + keyNum)); entry.markDirty(true); // Make some changes, like adding a dep and rdep. entry.addReverseDepAndCheckIfDone(key("rdep")); @@ -345,7 +347,7 @@ public abstract class GraphConcurrencyTest { } catch (InterruptedException e) { throw new AssertionError(e); } - NodeEntry entry = graph.get(key("foo" + keyNum)); + NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + keyNum)); assertNotNull(entry); // Requests for the value are made at the same time that the version increments from // the base. Check that there is no problem in requesting the version and that the @@ -379,7 +381,7 @@ public abstract class GraphConcurrencyTest { throw new AssertionError(e); } Map<SkyKey, NodeEntry> batchMap = - graph.getBatchWithFieldHints(batch, NodeEntryField.NO_FIELDS); + graph.getBatchWithFieldHints(null, Reason.OTHER, batch, NodeEntryField.NO_FIELDS); getBatchCountDownLatch.countDown(); assertThat(batchMap).hasSize(batch.size()); for (NodeEntry entry : batchMap.values()) { @@ -398,7 +400,7 @@ public abstract class GraphConcurrencyTest { assertFalse(ExecutorUtil.interruptibleShutdown(pool2)); assertFalse(ExecutorUtil.interruptibleShutdown(pool3)); for (int i = 0; i < numKeys; i++) { - NodeEntry entry = graph.get(key("foo" + i)); + NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + i)); assertThat(entry.getValue()).isEqualTo(new StringValue("bar" + i)); assertThat(entry.getVersion()).isEqualTo(getNextVersion(startingVersion)); for (SkyKey key : entry.getReverseDeps()) { diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java index 711e9e7b2d..af0049b52b 100644 --- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java +++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java @@ -19,7 +19,6 @@ import com.google.common.collect.Maps; import com.google.common.collect.Maps.EntryTransformer; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.util.GroupedList; - import java.util.EnumSet; import java.util.Map; import java.util.Set; @@ -89,8 +88,10 @@ public class NotifyingHelper { } @Override - public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) { - return Maps.transformEntries(delegate.getBatch(keys), notifyingHelper.wrapEntry); + public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) { + return Maps.transformEntries( + delegate.getBatchForInvalidation(keys), + notifyingHelper.wrapEntry); } } @@ -114,24 +115,31 @@ public class NotifyingHelper { } @Override - public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) { + public Map<SkyKey, NodeEntry> createIfAbsentBatch( + @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) { for (SkyKey key : keys) { notifyingHelper.graphListener.accept(key, EventType.CREATE_IF_ABSENT, Order.BEFORE, null); } - return Maps.transformEntries(delegate.createIfAbsentBatch(keys), notifyingHelper.wrapEntry); + return Maps.transformEntries( + delegate.createIfAbsentBatch(requestor, reason, keys), + notifyingHelper.wrapEntry); } @Override public Map<SkyKey, NodeEntry> getBatchWithFieldHints( - Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) { + @Nullable SkyKey requestor, + Reason reason, + Iterable<SkyKey> keys, + EnumSet<NodeEntryField> fields) { return Maps.transformEntries( - delegate.getBatchWithFieldHints(keys, fields), notifyingHelper.wrapEntry); + delegate.getBatchWithFieldHints(requestor, reason, keys, fields), + notifyingHelper.wrapEntry); } @Nullable @Override - public NodeEntry get(SkyKey key) { - return notifyingHelper.wrapEntry(key, delegate.get(key)); + public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key) { + return notifyingHelper.wrapEntry(key, delegate.get(requestor, reason, key)); } } diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java index 1689440b79..d6d3ab04c7 100644 --- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java +++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java @@ -23,8 +23,8 @@ class NotifyingInMemoryGraph extends NotifyingHelper.NotifyingProcessableGraph } @Override - public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) { - return getBatchWithFieldHints(keys, NodeEntryField.ALL_FIELDS); + public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) { + return getBatchWithFieldHints(null, Reason.INVALIDATION, keys, NodeEntryField.ALL_FIELDS); } @Override |