// Copyright 2014 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.annotations.VisibleForTesting; import com.google.common.base.Function; import com.google.common.base.Predicate; import com.google.common.base.Predicates; import com.google.common.base.Supplier; import com.google.common.base.Suppliers; import com.google.common.base.Throwables; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; import com.google.common.collect.Maps; import com.google.common.collect.Sets; import com.google.devtools.build.lib.collect.nestedset.NestedSet; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor; import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor; import com.google.devtools.build.lib.concurrent.ErrorClassifier; import com.google.devtools.build.lib.concurrent.ErrorHandler; import com.google.devtools.build.lib.concurrent.ForkJoinQuiescingExecutor; import com.google.devtools.build.lib.concurrent.QuiescingExecutor; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible; import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.events.EventHandler; import com.google.devtools.build.lib.events.StoredEventHandler; import com.google.devtools.build.lib.profiler.AutoProfiler; import com.google.devtools.build.lib.profiler.Profiler; import com.google.devtools.build.lib.profiler.ProfilerTask; import com.google.devtools.build.lib.util.BlazeClock; import com.google.devtools.build.lib.util.GroupedList; import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper; import com.google.devtools.build.lib.util.Preconditions; import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState; 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; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Set; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicBoolean; import java.util.logging.Logger; import javax.annotation.Nullable; /** * Evaluates a set of given functions ({@code SkyFunction}s) with arguments ({@code SkyKey}s). * Cycles are not allowed and are detected during the traversal. * *

This class implements multi-threaded evaluation. This is a fairly complex process that has * strong consistency requirements between the {@link ProcessableGraph}, the nodes in the graph of * type {@link NodeEntry}, the work queue, and the set of in-flight nodes. * *

The basic invariants are: * *

A node can be in one of three states: ready, waiting, and done. A node is ready if and only * if all of its dependencies have been signaled. A node is done if it has a value. It is waiting * if not all of its dependencies have been signaled. * *

A node must be in the work queue if and only if it is ready. It is an error for a node to be * in the work queue twice at the same time. * *

A node is considered in-flight if it has been created, and is not done yet. In case of an * interrupt, the work queue is discarded, and the in-flight set is used to remove partially * computed values. * *

Each evaluation of the graph takes place at a "version," which is currently given by a * non-negative {@code long}. The version can also be thought of as an "mtime." Each node in the * graph has a version, which is the last version at which its value changed. This version data is * used to avoid unnecessary re-evaluation of values. If a node is re-evaluated and found to have * the same data as before, its version (mtime) remains the same. If all of a node's children's * have the same version as before, its re-evaluation can be skipped. * *

This class is not intended for direct use, and is only exposed as public for use in * evaluation implementations outside of this package. */ public final class ParallelEvaluator implements Evaluator { private static final Logger LOG = Logger.getLogger(ParallelEvaluator.class.getName()); private static final boolean PREFETCH_OLD_DEPS = Boolean.parseBoolean( System.getProperty("skyframe.ParallelEvaluator.PrefetchOldDeps", "true")); /** Filters out events which should not be stored. */ public interface EventFilter extends Predicate { /** * Returns true if any events should be stored. Otherwise, optimizations may be made to avoid * doing unnecessary work. */ boolean storeEvents(); } private final ProcessableGraph graph; private final Version graphVersion; private static class SkyValueSupplier implements Supplier { private final NodeEntry state; public SkyValueSupplier(NodeEntry state) { this.state = state; } @Override public SkyValue get() { return state.getValue(); } } /** An general interface for {@link ParallelEvaluator} to receive objects of type {@code T}. */ public interface Receiver { // TODO(dmarting): should we just make it a common object for all Bazel codebase? /** * Consumes the given object. */ void accept(T object); } private final ImmutableMap skyFunctions; private final EventHandler reporter; private final NestedSetVisitor replayingNestedSetEventVisitor; private final boolean keepGoing; private final boolean storeErrorsAlongsideValues; private final int threadCount; @Nullable private final ForkJoinPool forkJoinPool; @Nullable private final EvaluationProgressReceiver progressReceiver; private final DirtyKeyTracker dirtyKeyTracker; private final Receiver> inflightKeysReceiver; private final EventFilter storedEventFilter; private final ErrorHandler errorHandler; public ParallelEvaluator( ProcessableGraph graph, Version graphVersion, ImmutableMap skyFunctions, final EventHandler reporter, EmittedEventState emittedEventState, EventFilter storedEventFilter, boolean keepGoing, int threadCount, @Nullable EvaluationProgressReceiver progressReceiver, DirtyKeyTracker dirtyKeyTracker, Receiver> inflightKeysReceiver) { this.graph = graph; this.skyFunctions = skyFunctions; this.graphVersion = graphVersion; this.inflightKeysReceiver = inflightKeysReceiver; this.reporter = Preconditions.checkNotNull(reporter); this.keepGoing = keepGoing; this.storeErrorsAlongsideValues = true; this.threadCount = threadCount; this.progressReceiver = progressReceiver; this.dirtyKeyTracker = Preconditions.checkNotNull(dirtyKeyTracker); this.replayingNestedSetEventVisitor = new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState); this.storedEventFilter = storedEventFilter; this.forkJoinPool = null; this.errorHandler = ErrorHandler.NullHandler.INSTANCE; } public ParallelEvaluator( ProcessableGraph graph, Version graphVersion, ImmutableMap skyFunctions, final EventHandler reporter, EmittedEventState emittedEventState, EventFilter storedEventFilter, boolean keepGoing, boolean storeErrorsAlongsideValues, @Nullable EvaluationProgressReceiver progressReceiver, DirtyKeyTracker dirtyKeyTracker, Receiver> inflightKeysReceiver, ForkJoinPool forkJoinPool, ErrorHandler errorHandler) { this.graph = graph; this.skyFunctions = skyFunctions; this.graphVersion = graphVersion; this.inflightKeysReceiver = inflightKeysReceiver; this.reporter = Preconditions.checkNotNull(reporter); this.keepGoing = keepGoing; this.storeErrorsAlongsideValues = storeErrorsAlongsideValues; Preconditions.checkState(storeErrorsAlongsideValues || keepGoing); this.threadCount = 0; this.progressReceiver = progressReceiver; this.dirtyKeyTracker = Preconditions.checkNotNull(dirtyKeyTracker); this.replayingNestedSetEventVisitor = new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState); this.storedEventFilter = storedEventFilter; this.forkJoinPool = Preconditions.checkNotNull(forkJoinPool); this.errorHandler = errorHandler; } private Map getBatchValues( SkyKey parent, Reason reason, Iterable keys) { return graph.getBatch(parent, reason, keys); } /** Receives the events from the NestedSet and delegates to the reporter. */ private static class NestedSetEventReceiver implements NestedSetVisitor.Receiver { private final EventHandler reporter; public NestedSetEventReceiver(EventHandler reporter) { this.reporter = reporter; } @Override public void accept(TaggedEvents events) { String tag = events.getTag(); for (Event e : events.getEvents()) { reporter.handle(e.withTag(tag)); } } } /** * A suitable {@link SkyFunction.Environment} implementation. */ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment { private boolean building = true; private SkyKey depErrorKey = null; private final SkyKey skyKey; /** * The deps requested during the previous build of this node. Used for two reasons: (1) They are * fetched eagerly before the node is built, to potentially prime the graph and speed up * requests for them during evaluation. (2) When the node finishes building, any deps from the * previous build that are not deps from this build must have this node removed from them as a * reverse dep. Thus, it is important that all nodes in this set have the property that they * have this node as a reverse dep from the last build, but that this node has not added them as * a reverse dep on this build. That set is normally {@link * NodeEntry#getAllRemainingDirtyDirectDeps()}, but in certain corner cases, like cycles, * further filtering may be needed. */ private final Set oldDeps; private SkyValue value = null; private ErrorInfo errorInfo = null; private final Map bubbleErrorInfo; /** The values previously declared as dependencies. */ private final Map directDeps; /** * The grouped list of values requested during this build as dependencies. On a subsequent * build, if this value is dirty, all deps in the same dependency group can be checked in * parallel for changes. In other words, if dep1 and dep2 are in the same group, then dep1 will * be checked in parallel with dep2. See {@link #getValues} for more. */ private final GroupedListHelper newlyRequestedDeps = new GroupedListHelper<>(); /** * The value visitor managing the thread pool. Used to enqueue parents when this value is * finished, and, during testing, to block until an exception is thrown if a value builder * requests that. */ private final ValueVisitor visitor; /** The set of errors encountered while fetching children. */ private final Collection childErrorInfos = new LinkedHashSet<>(); private final StoredEventHandler eventHandler = new StoredEventHandler() { @Override @SuppressWarnings("UnsynchronizedOverridesSynchronized") // only delegates to thread-safe. public void handle(Event e) { checkActive(); if (storedEventFilter.apply(e)) { super.handle(e); } else { reporter.handle(e); } } }; private SkyFunctionEnvironment( SkyKey skyKey, GroupedList directDeps, Set oldDeps, ValueVisitor visitor) { this(skyKey, directDeps, null, oldDeps, visitor); } private SkyFunctionEnvironment( SkyKey skyKey, GroupedList directDeps, @Nullable Map bubbleErrorInfo, Set oldDeps, ValueVisitor visitor) { this.skyKey = skyKey; this.oldDeps = oldDeps; this.directDeps = Collections.unmodifiableMap(batchPrefetch( skyKey, directDeps, oldDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey)); this.bubbleErrorInfo = bubbleErrorInfo; this.visitor = visitor; Preconditions.checkState( !this.directDeps.containsKey(ErrorTransienceValue.KEY), "%s cannot have a dep on ErrorTransienceValue during building", skyKey); } private Map batchPrefetch( SkyKey requestor, GroupedList depKeys, Set oldDeps, boolean assertDone, SkyKey keyForDebugging) { Iterable depKeysAsIterable = Iterables.concat(depKeys); Iterable keysToPrefetch = depKeysAsIterable; if (PREFETCH_OLD_DEPS) { ImmutableSet.Builder keysToPrefetchBuilder = ImmutableSet.builder(); keysToPrefetchBuilder.addAll(depKeysAsIterable).addAll(oldDeps); keysToPrefetch = keysToPrefetchBuilder.build(); } Map batchMap = getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch); if (PREFETCH_OLD_DEPS) { batchMap = ImmutableMap.copyOf( Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable)))); } if (batchMap.size() != depKeys.numElements()) { throw new IllegalStateException( "Missing keys for " + keyForDebugging + ": " + Sets.difference(depKeys.toSet(), batchMap.keySet())); } if (assertDone) { for (Map.Entry entry : batchMap.entrySet()) { Preconditions.checkState( entry.getValue().isDone(), "%s had not done %s", keyForDebugging, entry); } } return batchMap; } private void checkActive() { Preconditions.checkState(building, skyKey); } private NestedSet buildEvents(NodeEntry entry, boolean missingChildren) { // Aggregate the nested set of events from the direct deps, also adding the events from // building this value. NestedSetBuilder eventBuilder = NestedSetBuilder.stableOrder(); ImmutableList events = eventHandler.getEvents(); if (!events.isEmpty()) { eventBuilder.add(new TaggedEvents(getTagFromKey(), events)); } if (storedEventFilter.storeEvents()) { // Only do the work of processing children if we're going to store events. GroupedList depKeys = entry.getTemporaryDirectDeps(); Map deps = getValuesMaybeFromError( null, Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements()); if (!missingChildren && depKeys.numElements() != deps.size()) { throw new IllegalStateException( "Missing keys for " + skyKey + ": " + Sets.difference(depKeys.toSet(), deps.keySet()) + ", " + entry); } for (SkyValue value : deps.values()) { if (value == NULL_MARKER) { Preconditions.checkState(missingChildren, "Missing dep in %s for %s", depKeys, skyKey); } else { eventBuilder.addTransitive(ValueWithMetadata.getEvents(value)); } } } return eventBuilder.build(); } /** * If this node has an error, that is, if errorInfo is non-null, do nothing. Otherwise, set * errorInfo to the union of the child errors that were recorded earlier by getValueOrException, * if there are any. * *

Child errors are remembered, if there are any and yet the parent recovered without * error, so that subsequent noKeepGoing evaluations can stop as soon as they encounter a * node whose (transitive) children had experienced an error, even if that (transitive) * parent node had been able to recover from it during a keepGoing build. This behavior can be * suppressed by setting {@link #storeErrorsAlongsideValues} to false, which will cause nodes * with values to have no stored error info. This may be useful if this graph will only ever be * used for keepGoing builds, since in that case storing errors from recovered nodes is * pointless. */ private void finalizeErrorInfo() { if (errorInfo == null && (storeErrorsAlongsideValues || value == null) && !childErrorInfos.isEmpty()) { errorInfo = ErrorInfo.fromChildErrors(skyKey, childErrorInfos); } } private void setValue(SkyValue newValue) { Preconditions.checkState(errorInfo == null && bubbleErrorInfo == null, "%s %s %s %s", skyKey, newValue, errorInfo, bubbleErrorInfo); Preconditions.checkState(value == null, "%s %s %s", skyKey, value, newValue); value = newValue; } /** * Set this node to be in error. The node's value must not have already been set. However, all * dependencies of this node must 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(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(skyKey, Reason.RDEP_ADDITION, ErrorTransienceValue.KEY); DependencyState triState; if (oldDeps.contains(ErrorTransienceValue.KEY)) { triState = errorTransienceNode.checkIfDoneForDirtyReverseDep(skyKey); } else { triState = errorTransienceNode.addReverseDepAndCheckIfDone(skyKey); } Preconditions.checkState(triState == DependencyState.DONE, "%s %s %s", skyKey, triState, errorInfo); state.addTemporaryDirectDeps( GroupedListHelper.create(ImmutableList.of(ErrorTransienceValue.KEY))); state.signalDep(); } this.errorInfo = Preconditions.checkNotNull(errorInfo, skyKey); } private Map getValuesMaybeFromError( @Nullable SkyKey requestor, Iterable keys, @Nullable Map bubbleErrorInfo, int keySize) { ImmutableMap.Builder builder = ImmutableMap.builder(); ArrayList missingKeys = new ArrayList<>(keySize); for (SkyKey key : keys) { NodeEntry entry = directDeps.get(key); if (entry != null) { SkyValue value = maybeGetValueFromError(key, entry, bubbleErrorInfo); if (value != NULL_MARKER) { builder.put(key, value); } } else { missingKeys.add(key); } } Map missingEntries = getBatchValues(requestor, Reason.DEP_REQUESTED, missingKeys); for (SkyKey key : missingKeys) { builder.put(key, maybeGetValueFromError(key, missingEntries.get(key), bubbleErrorInfo)); } return builder.build(); } @Override protected Map getValueOrUntypedExceptions( Set depKeys) { checkActive(); Preconditions.checkState( !depKeys.contains(ErrorTransienceValue.KEY), "Error transience key cannot be in requested deps of %s", skyKey); Map values = getValuesMaybeFromError(skyKey, depKeys, bubbleErrorInfo, depKeys.size()); for (Map.Entry depEntry : values.entrySet()) { SkyKey depKey = depEntry.getKey(); SkyValue depValue = depEntry.getValue(); if (depValue == NULL_MARKER) { if (directDeps.containsKey(depKey)) { throw new IllegalStateException( "Undone key " + depKey + " was already in deps of " + skyKey + "( dep: " + graph.get(skyKey, Reason.OTHER, depKey) + ", parent: " + graph.get(null, Reason.OTHER, skyKey)); } valuesMissing = true; addDep(depKey); continue; } ErrorInfo errorInfo = ValueWithMetadata.getMaybeErrorInfo(depEntry.getValue()); if (errorInfo != null) { childErrorInfos.add(errorInfo); if (bubbleErrorInfo != null) { // Set interrupted status, to try to prevent the calling SkyFunction from doing anything // fancy after this. SkyFunctions executed during error bubbling are supposed to // (quickly) rethrow errors or return a value/null (but there's currently no way to // enforce this). Thread.currentThread().interrupt(); } if ((!keepGoing && bubbleErrorInfo == null) || errorInfo.getException() == null) { valuesMissing = true; // We arbitrarily record the first child error if we are about to abort. if (!keepGoing && depErrorKey == null) { depErrorKey = depKey; } } } if (!directDeps.containsKey(depKey)) { if (bubbleErrorInfo == null) { addDep(depKey); } replayingNestedSetEventVisitor.visit(ValueWithMetadata.getEvents(depValue)); } } return Maps.transformValues( values, new Function() { @Override public ValueOrUntypedException apply(SkyValue maybeWrappedValue) { if (maybeWrappedValue == NULL_MARKER) { return ValueOrExceptionUtils.ofNull(); } SkyValue justValue = ValueWithMetadata.justValue(maybeWrappedValue); ErrorInfo errorInfo = ValueWithMetadata.getMaybeErrorInfo(maybeWrappedValue); if (justValue != null && (keepGoing || errorInfo == null)) { // If the dep did compute a value, it is given to the caller if we are in // keepGoing mode or if we are in noKeepGoingMode and there were no errors computing // it. return ValueOrExceptionUtils.ofValueUntyped(justValue); } // There was an error building the value, which we will either report by throwing an // exception or insulate the caller from by returning null. Preconditions.checkNotNull(errorInfo, "%s %s", skyKey, maybeWrappedValue); Exception exception = errorInfo.getException(); if (!keepGoing && exception != null && bubbleErrorInfo == null) { // Child errors should not be propagated in noKeepGoing mode (except during error // bubbling). Instead we should fail fast. return ValueOrExceptionUtils.ofNull(); } if (exception != null) { // Give builder a chance to handle this exception. return ValueOrExceptionUtils.ofExn(exception); } // In a cycle. Preconditions.checkState( !Iterables.isEmpty(errorInfo.getCycleInfo()), "%s %s %s", skyKey, errorInfo, maybeWrappedValue); return ValueOrExceptionUtils.ofNull(); } }); } @Override public Map> getValuesOrThrow( Iterable depKeys, Class exceptionClass1, Class exceptionClass2, Class exceptionClass3, Class exceptionClass4, Class exceptionClass5) { newlyRequestedDeps.startGroup(); Map> result = super.getValuesOrThrow( depKeys, exceptionClass1, exceptionClass2, exceptionClass3, exceptionClass4, exceptionClass5); newlyRequestedDeps.endGroup(); return result; } private void addDep(SkyKey key) { if (!newlyRequestedDeps.contains(key)) { // dep may have been requested already this evaluation. If not, add it. newlyRequestedDeps.add(key); } } /** * If {@code !keepGoing} and there is at least one dep in error, returns a dep in error. * Otherwise returns {@code null}. */ @Nullable private SkyKey getDepErrorKey() { return depErrorKey; } @Override public EventHandler getListener() { checkActive(); return eventHandler; } private void doneBuilding() { building = false; } /** * Apply the change to the graph (mostly) atomically and signal all nodes that are waiting for * this node to complete. Adding nodes and signaling is not atomic, but may need to be changed * for interruptibility. * *

Parents are only enqueued if {@code enqueueParents} holds. Parents should be enqueued * unless (1) this node is being built after the main evaluation has aborted, or (2) this node * is being built with --nokeep_going, and so we are about to shut down the main evaluation * anyway. * *

The node entry is informed if the node's value and error are definitive via the flag * {@code completeValue}. */ void commit(NodeEntry primaryEntry, boolean enqueueParents) { // Construct the definitive error info, if there is one. finalizeErrorInfo(); // We have the following implications: // errorInfo == null => value != null => enqueueParents. // All these implications are strict: // (1) errorInfo != null && value != null happens for values with recoverable errors. // (2) value == null && enqueueParents happens for values that are found to have errors // during a --keep_going build. NestedSet events = buildEvents(primaryEntry, /*missingChildren=*/false); Version valueVersion; SkyValue valueWithMetadata; if (value == null) { Preconditions.checkNotNull(errorInfo, "%s %s", skyKey, primaryEntry); valueWithMetadata = ValueWithMetadata.error(errorInfo, events); } else { // We must be enqueueing parents if we have a value. Preconditions.checkState(enqueueParents, "%s %s", skyKey, primaryEntry); valueWithMetadata = ValueWithMetadata.normal(value, errorInfo, events); } if (!oldDeps.isEmpty()) { // Remove the rdep on this entry for each of its old deps that is no longer a direct dep. Set depsToRemove = Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet()); Collection oldDepEntries = graph.getBatch( skyKey, Reason.RDEP_REMOVAL, depsToRemove).values(); for (NodeEntry oldDepEntry : oldDepEntries) { oldDepEntry.removeReverseDep(skyKey); } } // If this entry is dirty, setValue may not actually change it, if it determines that // the data being written now is the same as the data already present in the entry. // We could consider using max(childVersions) here instead of graphVersion. When full // versioning is implemented, this would allow evaluation at a version between // max(childVersions) and graphVersion to re-use this result. Set reverseDeps = primaryEntry.setValue(valueWithMetadata, graphVersion); // Note that if this update didn't actually change the value entry, this version may not // be the graph version. valueVersion = primaryEntry.getVersion(); Preconditions.checkState(valueVersion.atMost(graphVersion), "%s should be at most %s in the version partial ordering", valueVersion, graphVersion); if (progressReceiver != null) { // Tell the receiver that this value was built. If valueVersion.equals(graphVersion), it // was evaluated this run, and so was changed. Otherwise, it is less than graphVersion, // by the Preconditions check above, and was not actually changed this run -- when it was // written above, its version stayed below this update's version, so its value remains the // same as before. // We use a SkyValueSupplier here because it keeps a reference to the entry, allowing for // the receiver to be confident that the entry is readily accessible in memory. progressReceiver.evaluated(skyKey, new SkyValueSupplier(primaryEntry), valueVersion.equals(graphVersion) ? EvaluationState.BUILT : EvaluationState.CLEAN); } signalValuesAndEnqueueIfReady( enqueueParents ? visitor : null, skyKey, reverseDeps, valueVersion); visitor.notifyDone(skyKey); replayingNestedSetEventVisitor.visit(events); } @Nullable private String getTagFromKey() { return skyFunctions.get(skyKey.functionName()).extractTag(skyKey); } /** * Gets the latch that is counted down when an exception is thrown in {@code * AbstractQueueVisitor}. For use in tests to check if an exception actually was thrown. Calling * {@code AbstractQueueVisitor#awaitExceptionForTestingOnly} can throw a spurious {@link * InterruptedException} because {@link CountDownLatch#await} checks the interrupted bit before * returning, even if the latch is already at 0. See bug "testTwoErrors is flaky". */ CountDownLatch getExceptionLatchForTesting() { return visitor.getExceptionLatchForTestingOnly(); } @Override public boolean inErrorBubblingForTesting() { return bubbleErrorInfo != null; } } private static final ErrorClassifier VALUE_VISITOR_ERROR_CLASSIFIER = new ErrorClassifier() { @Override protected ErrorClassification classifyException(Exception e) { if (e instanceof SchedulerException) { return ErrorClassification.CRITICAL; } if (e instanceof RuntimeException) { // We treat non-SchedulerException RuntimeExceptions as more severe than // SchedulerExceptions so that AbstractQueueVisitor will propagate instances of the // former. They indicate actual Blaze bugs, rather than normal Skyframe evaluation // control flow. return ErrorClassification.CRITICAL_AND_LOG; } return ErrorClassification.NOT_CRITICAL; } }; private class ValueVisitor { private final QuiescingExecutor quiescingExecutor; private final AtomicBoolean preventNewEvaluations = new AtomicBoolean(false); private final Set inflightNodes = Sets.newConcurrentHashSet(); private final Set crashes = Sets.newConcurrentHashSet(); private ValueVisitor(ForkJoinPool forkJoinPool) { quiescingExecutor = new ForkJoinQuiescingExecutor(forkJoinPool, VALUE_VISITOR_ERROR_CLASSIFIER, errorHandler); } private ValueVisitor(int threadCount) { quiescingExecutor = new AbstractQueueVisitor( /*concurrent*/ true, threadCount, /*keepAliveTime=*/ 1, TimeUnit.SECONDS, /*failFastOnException*/ true, "skyframe-evaluator", VALUE_VISITOR_ERROR_CLASSIFIER, errorHandler); } private void waitForCompletion() throws InterruptedException { quiescingExecutor.awaitQuiescence(/*interruptWorkers=*/ true); } private void enqueueEvaluation(SkyKey key) { // We unconditionally add the key to the set of in-flight nodes because even if evaluation is // never scheduled we still want to remove the previously created NodeEntry from the graph. // Otherwise we would leave the graph in a weird state (wasteful garbage in the best case and // inconsistent in the worst case). boolean newlyEnqueued = inflightNodes.add(key); // All nodes enqueued for evaluation will be either verified clean, re-evaluated, or cleaned // up after being in-flight when an error happens in nokeep_going mode or in the event of an // interrupt. In any of these cases, they won't be dirty anymore. if (newlyEnqueued) { dirtyKeyTracker.notDirty(key); } if (preventNewEvaluations.get()) { return; } if (newlyEnqueued && progressReceiver != null) { progressReceiver.enqueueing(key); } quiescingExecutor.execute(new Evaluate(this, key)); } /** * Stop any new evaluations from being enqueued. Returns whether this was the first thread to * request a halt. If true, this thread should proceed to throw an exception. If false, another * thread already requested a halt and will throw an exception, and so this thread can simply * end. */ private boolean preventNewEvaluations() { return preventNewEvaluations.compareAndSet(false, true); } private void noteCrash(RuntimeException e) { crashes.add(e); } private Collection getCrashes() { return crashes; } private void notifyDone(SkyKey key) { inflightNodes.remove(key); } private boolean isInflight(SkyKey key) { return inflightNodes.contains(key); } @VisibleForTesting private CountDownLatch getExceptionLatchForTestingOnly() { return quiescingExecutor.getExceptionLatchForTestingOnly(); } } /** * If the entry is dirty and not already rebuilding, puts it in a state so that it can rebuild. */ private static void maybeMarkRebuilding(NodeEntry entry) { if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) { entry.markRebuilding(); } } private enum DirtyOutcome { ALREADY_PROCESSED, NEEDS_EVALUATION } /** * An action that evaluates a value. */ private class Evaluate implements Runnable { private final ValueVisitor visitor; /** The name of the value to be evaluated. */ private final SkyKey skyKey; private Evaluate(ValueVisitor visitor, SkyKey skyKey) { this.visitor = visitor; this.skyKey = skyKey; } private void enqueueChild( SkyKey skyKey, NodeEntry entry, SkyKey child, NodeEntry childEntry, boolean depAlreadyExists) { Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry); DependencyState dependencyState = depAlreadyExists ? childEntry.checkIfDoneForDirtyReverseDep(skyKey) : childEntry.addReverseDepAndCheckIfDone(skyKey); switch (dependencyState) { case DONE: if (entry.signalDep(childEntry.getVersion())) { // This can only happen if there are no more children to be added. visitor.enqueueEvaluation(skyKey); } break; case ALREADY_EVALUATING: break; case NEEDS_SCHEDULING: visitor.enqueueEvaluation(child); break; } } /** * Returns true if this depGroup consists of the error transience value and the error transience * value is newer than the entry, meaning that the entry must be re-evaluated. */ private boolean invalidatedByErrorTransience(Collection depGroup, NodeEntry entry) { return depGroup.size() == 1 && depGroup.contains(ErrorTransienceValue.KEY) && !graph.get( null, Reason.OTHER, ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion()); } private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) { if (!state.isDirty()) { return DirtyOutcome.NEEDS_EVALUATION; } switch (state.getDirtyState()) { case CHECK_DEPENDENCIES: // Evaluating a dirty node for the first time, and checking its children to see if any // of them have changed. Note that there must be dirty children for this to happen. // Check the children group by group -- we don't want to evaluate a value that is no // longer needed because an earlier dependency changed. For example, //foo:foo depends // on target //bar:bar and is built. Then foo/BUILD is modified to remove the dependence // on bar, and bar/BUILD is deleted. Reloading //bar:bar would incorrectly throw an // exception. To avoid this, we must reload foo/BUILD first, at which point we will // discover that it has changed, and re-evaluate target //foo:foo from scratch. // On the other hand, when an action requests all of its inputs, we can safely check all // of them in parallel on a subsequent build. So we allow checking an entire group in // parallel here, if the node builder requested a group last build. // Note: every dep returned here must either have this node re-registered for it (using // checkIfDoneForDirtyReverseDep) and be registered as a direct dep of this node, or have // its reverse dep on this node removed. Failing to do either one of these would result in // a graph inconsistency, where the child had a reverse dep on this node, but this node // had no kind of dependency on the child. Collection directDepsToCheck = state.getNextDirtyDirectDeps(); if (invalidatedByErrorTransience(directDepsToCheck, state)) { // If this dep is the ErrorTransienceValue and the ErrorTransienceValue has been // updated then we need to force a rebuild. We would like to just signal the entry as // 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( skyKey, Reason.RDEP_REMOVAL, ErrorTransienceValue.KEY).removeReverseDep(skyKey); return DirtyOutcome.NEEDS_EVALUATION; } if (!keepGoing) { // This check ensures that we maintain the invariant that if a node with an error is // reached during a no-keep-going build, none of its currently building parents // finishes building. If the child isn't done building yet, it will detect on its own // that it has an error (see the VERIFIED_CLEAN case below). On the other hand, if it // is done, then it is the parent's responsibility to notice that, which we do here. // We check the deps for errors so that we don't continue building this node if it has // a child error. Map entriesToCheck = graph.getBatch(skyKey, Reason.OTHER, directDepsToCheck); for (Map.Entry entry : entriesToCheck.entrySet()) { if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) { // If any child has an error, we arbitrarily add a dep on the first one (needed // for error bubbling) and throw an exception coming from it. SkyKey errorKey = entry.getKey(); NodeEntry errorEntry = entry.getValue(); state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(errorKey))); errorEntry.checkIfDoneForDirtyReverseDep(skyKey); // Perform the necessary bookkeeping for any deps that are not being used. for (Map.Entry depEntry : entriesToCheck.entrySet()) { if (!depEntry.getKey().equals(errorKey)) { depEntry.getValue().removeReverseDep(skyKey); } } if (!visitor.preventNewEvaluations()) { // An error was already thrown in the evaluator. Don't do anything here. return DirtyOutcome.ALREADY_PROCESSED; } throw SchedulerException.ofError(errorEntry.getErrorInfo(), entry.getKey()); } } } // It is safe to add these deps back to the node -- even if one of them has changed, the // contract of pruning is that the node will request these deps again when it rebuilds. // We must add these deps before enqueuing them, so that the node knows that it depends // on them. If one of these deps is the error transience node, the check we did above // in #invalidatedByErrorTransience means that the error transience node is not newer // than this node, so we are going to mark it clean (since the error transience node is // always the last dep). state.addTemporaryDirectDepsGroupToDirtyEntry(directDepsToCheck); // 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 e : graph.createIfAbsentBatch( skyKey, Reason.ENQUEUING_CHILD, directDepsToCheck).entrySet()) { SkyKey directDep = e.getKey(); NodeEntry directDepEntry = e.getValue(); enqueueChild(skyKey, state, directDep, directDepEntry, /*depAlreadyExists=*/ true); } return DirtyOutcome.ALREADY_PROCESSED; case VERIFIED_CLEAN: // No child has a changed value. This node can be marked done and its parents signaled // without any re-evaluation. visitor.notifyDone(skyKey); Set reverseDeps = state.markClean(); if (progressReceiver != null) { // Tell the receiver that the value was not actually changed this run. progressReceiver.evaluated(skyKey, new SkyValueSupplier(state), EvaluationState.CLEAN); } if (!keepGoing && state.getErrorInfo() != null) { if (!visitor.preventNewEvaluations()) { return DirtyOutcome.ALREADY_PROCESSED; } throw SchedulerException.ofError(state.getErrorInfo(), skyKey); } signalValuesAndEnqueueIfReady(visitor, skyKey, reverseDeps, state.getVersion()); return DirtyOutcome.ALREADY_PROCESSED; case NEEDS_REBUILDING: maybeMarkRebuilding(state); // Fall through to REBUILDING case. case REBUILDING: return DirtyOutcome.NEEDS_EVALUATION; default: throw new IllegalStateException("key: " + skyKey + ", entry: " + state); } } @Override public void run() { 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; } Set oldDeps = state.getAllRemainingDirtyDirectDeps(); SkyFunctionEnvironment env = new SkyFunctionEnvironment(skyKey, state.getTemporaryDirectDeps(), oldDeps, visitor); SkyFunctionName functionName = skyKey.functionName(); SkyFunction factory = skyFunctions.get(functionName); Preconditions.checkState(factory != null, "Unable to find SkyFunction '%s' for node with key %s, %s", functionName, skyKey, state); SkyValue value = null; long startTime = BlazeClock.instance().nanoTime(); try { value = factory.compute(skyKey, env); } catch (final SkyFunctionException builderException) { ReifiedSkyFunctionException reifiedBuilderException = new ReifiedSkyFunctionException(builderException, skyKey); // In keep-going mode, we do not let SkyFunctions throw errors with missing deps -- we will // restart them when their deps are done, so we can have a definitive error and definitive // graph structure, thus avoiding non-determinism. It's completely reasonable for // SkyFunctions to throw eagerly because they do not know if they are in keep-going mode. // Propagated transitive errors are treated the same as missing deps. if ((!keepGoing || !env.valuesMissing()) && reifiedBuilderException.getRootCauseSkyKey().equals(skyKey)) { boolean shouldFailFast = !keepGoing || builderException.isCatastrophic(); if (shouldFailFast) { // After we commit this error to the graph but before the eval call completes with the // error there is a race-like opportunity for the error to be used, either by an // in-flight computation or by a future computation. if (!visitor.preventNewEvaluations()) { // This is not the first error encountered, so we ignore it so that we can terminate // with the first error. return; } } Map newlyRequestedDeps = getBatchValues(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps); boolean isTransitivelyTransient = reifiedBuilderException.isTransient(); for (NodeEntry depEntry : Iterables.concat(env.directDeps.values(), newlyRequestedDeps.values())) { if (!isDoneForBuild(depEntry)) { continue; } ErrorInfo depError = depEntry.getErrorInfo(); if (depError != null) { isTransitivelyTransient |= depError.isTransient(); } } ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException, isTransitivelyTransient); registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env); env.setError( state, errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient()); env.commit(state, /*enqueueParents=*/keepGoing); if (!shouldFailFast) { return; } throw SchedulerException.ofError(errorInfo, skyKey); } } catch (InterruptedException ie) { // InterruptedException cannot be thrown by Runnable.run, so we must wrap it. // Interrupts can be caught by both the Evaluator and the AbstractQueueVisitor. // The former will unwrap the IE and propagate it as is; the latter will throw a new IE. throw SchedulerException.ofInterruption(ie, skyKey); } catch (RuntimeException re) { // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output // some context together with the exception. String msg = prepareCrashMessage(skyKey, state.getInProgressReverseDeps()); RuntimeException ex = new RuntimeException(msg, re); visitor.noteCrash(ex); throw ex; } finally { env.doneBuilding(); long elapsedTimeNanos = BlazeClock.instance().nanoTime() - startTime; if (elapsedTimeNanos > 0) { if (progressReceiver != null) { progressReceiver.computed(skyKey, elapsedTimeNanos); } Profiler.instance().logSimpleTaskDuration(startTime, elapsedTimeNanos, ProfilerTask.SKYFUNCTION, skyKey); } } GroupedListHelper newDirectDeps = env.newlyRequestedDeps; if (value != null) { Preconditions.checkState(!env.valuesMissing(), "Evaluation of %s returned non-null value " + "but requested dependencies that weren't computed yet (one of %s), ValueEntry: %s", skyKey, newDirectDeps, state); env.setValue(value); registerNewlyDiscoveredDepsForDoneEntry( skyKey, state, graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps), oldDeps, env); env.commit(state, /*enqueueParents=*/true); return; } if (env.getDepErrorKey() != null) { Preconditions.checkState(!keepGoing, "%s %s %s", skyKey, state, env.getDepErrorKey()); // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first // need to add the edge between the current node and the child error it requested so that // 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(skyKey, Reason.OTHER, childErrorKey), "skyKey: %s, state: %s childErrorKey: %s", skyKey, state, childErrorKey); if (newDirectDeps.contains(childErrorKey)) { // Add this dep if it was just requested. In certain rare race conditions (see // MemoizingEvaluatorTest.cachedErrorCausesRestart) this dep may have already been // requested. state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(childErrorKey))); DependencyState childErrorState; if (oldDeps.contains(childErrorKey)) { childErrorState = childErrorEntry.checkIfDoneForDirtyReverseDep(skyKey); } else { childErrorState = childErrorEntry.addReverseDepAndCheckIfDone(skyKey); } Preconditions.checkState( childErrorState == DependencyState.DONE, "skyKey: %s, state: %s childErrorKey: %s", skyKey, state, childErrorKey, childErrorEntry); } ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo()); visitor.preventNewEvaluations(); throw SchedulerException.ofError(childErrorInfo, childErrorKey); } // TODO(bazel-team): This code is not safe to interrupt, because we would lose the state in // newDirectDeps. // TODO(bazel-team): An ill-behaved SkyFunction can throw us into an infinite loop where we // add more dependencies on every run. [skyframe-core] // Add all new keys to the set of known deps. state.addTemporaryDirectDeps(newDirectDeps); // If there were no newly requested dependencies, at least one of them was in error or there // is a bug in the SkyFunction implementation. The environment has collected its errors, so we // just order it to be built. if (newDirectDeps.isEmpty()) { // TODO(bazel-team): This means a bug in the SkyFunction. What to do? Preconditions.checkState(!env.childErrorInfos.isEmpty(), "Evaluation of SkyKey failed and no dependencies were requested: %s %s", skyKey, state); Preconditions.checkState( keepGoing, "nokeep_going evaluation should have failed on first child error: %s %s %s", skyKey, state, env.childErrorInfos); // 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(state, /*enqueueParents=*/ true); return; } for (Map.Entry e : graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) { SkyKey newDirectDep = e.getKey(); NodeEntry newDirectDepEntry = e.getValue(); enqueueChild( skyKey, state, newDirectDep, newDirectDepEntry, /*depAlreadyExists=*/ oldDeps.contains(newDirectDep)); } // It is critical that there is no code below this point. } private String prepareCrashMessage(SkyKey skyKey, Iterable reverseDeps) { StringBuilder reverseDepDump = new StringBuilder(); for (SkyKey key : reverseDeps) { if (reverseDepDump.length() > MAX_REVERSEDEP_DUMP_LENGTH) { reverseDepDump.append(", ..."); break; } if (reverseDepDump.length() > 0) { reverseDepDump.append(", "); } reverseDepDump.append("'"); reverseDepDump.append(key.toString()); reverseDepDump.append("'"); } return String.format( "Unrecoverable error while evaluating node '%s' (requested by nodes %s)", skyKey, reverseDepDump); } private static final int MAX_REVERSEDEP_DUMP_LENGTH = 1000; } /** * Signals all parents that this node is finished. If visitor is not null, also enqueues any * parents that are ready. If visitor is null, indicating that we are building this node after * the main build aborted, then skip any parents that are already done (that can happen with * cycles). */ private void signalValuesAndEnqueueIfReady( @Nullable ValueVisitor visitor, SkyKey skyKey, Iterable 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 batch = graph.getBatch(skyKey, Reason.SIGNAL_DEP, keys); if (visitor != null) { for (SkyKey key : keys) { NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key); if (entry.signalDep(version)) { visitor.enqueueEvaluation(key); } } } else { for (SkyKey key : keys) { NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key); if (!entry.isDone()) { // In cycles, we can have parents that are already done. entry.signalDep(version); } } } } /** * 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 removeIncompleteChildForCycle(SkyKey inProgressParent, SkyKey child) { NodeEntry childEntry = graph.get(inProgressParent, Reason.CYCLE_CHECKING, child); if (!isDoneForBuild(childEntry)) { childEntry.removeInProgressReverseDep(inProgressParent); return true; } return false; } /** * Add any additional deps that were registered during the run of a builder that finished by * creating a node or throwing an error. Builders may throw errors even if all their deps were not * provided -- we trust that a SkyFunction may be know it should throw an error even if not all of * its requested deps are done. However, that means we're assuming the SkyFunction would throw * that same error if all of its requested deps were done. Unfortunately, there is no way to * enforce that condition. */ private static void registerNewlyDiscoveredDepsForDoneEntry( SkyKey skyKey, NodeEntry entry, Map newlyRequestedDepMap, Set oldDeps, SkyFunctionEnvironment env) { Set unfinishedDeps = new HashSet<>(); for (SkyKey dep : env.newlyRequestedDeps) { if (!isDoneForBuild(newlyRequestedDepMap.get(dep))) { unfinishedDeps.add(dep); } } env.newlyRequestedDeps.remove(unfinishedDeps); entry.addTemporaryDirectDeps(env.newlyRequestedDeps); for (SkyKey newDep : env.newlyRequestedDeps) { // Note that this depEntry can't be null. If env.newlyRequestedDeps contained a key with a // null entry, then it would have been added to unfinishedDeps and then removed from // env.newlyRequestedDeps just above this loop. NodeEntry depEntry = Preconditions.checkNotNull(newlyRequestedDepMap.get(newDep), newDep); DependencyState triState = oldDeps.contains(newDep) ? depEntry.checkIfDoneForDirtyReverseDep(skyKey) : depEntry.addReverseDepAndCheckIfDone(skyKey); Preconditions.checkState(DependencyState.DONE == triState, "new dep %s was not already done for %s. ValueEntry: %s. DepValueEntry: %s", newDep, skyKey, entry, depEntry); entry.signalDep(); } Preconditions.checkState(entry.isReady(), "%s %s %s", skyKey, entry, env.newlyRequestedDeps); } private void informProgressReceiverThatValueIsDone(SkyKey key, NodeEntry entry) { if (progressReceiver != null) { Preconditions.checkState(entry.isDone(), entry); SkyValue value = entry.getValue(); Version valueVersion = entry.getVersion(); Preconditions.checkState(valueVersion.atMost(graphVersion), "%s should be at most %s in the version partial ordering", valueVersion, graphVersion); // For most nodes we do not inform the progress receiver if they were already done when we // retrieve them, but top-level nodes are presumably of more interest. // If valueVersion is not equal to graphVersion, it must be less than it (by the // Preconditions check above), and so the node is clean. progressReceiver.evaluated(key, Suppliers.ofInstance(value), valueVersion.equals(graphVersion) ? EvaluationState.BUILT : EvaluationState.CLEAN); } } @Override @ThreadCompatible public EvaluationResult eval(Iterable skyKeys) throws InterruptedException { ImmutableSet skyKeySet = ImmutableSet.copyOf(skyKeys); // 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; Map batch = getBatchValues(null, Reason.PRE_OR_POST_EVALUATION, skyKeySet); for (SkyKey key : skyKeySet) { if (!isDoneForBuild(batch.get(key))) { allAreDone = false; break; } } if (allAreDone) { for (SkyKey skyKey : skyKeySet) { informProgressReceiverThatValueIsDone(skyKey, batch.get(skyKey)); } // Note that the 'catastrophe' parameter doesn't really matter here (it's only used for // sanity checking). return constructResult(null, skyKeySet, null, /*catastrophe=*/false); } if (!keepGoing) { Set cachedErrorKeys = new HashSet<>(); for (SkyKey skyKey : skyKeySet) { NodeEntry entry = graph.get(null, Reason.PRE_OR_POST_EVALUATION, skyKey); if (entry == null) { continue; } if (entry.isDone() && entry.getErrorInfo() != null) { informProgressReceiverThatValueIsDone(skyKey, entry); cachedErrorKeys.add(skyKey); } } // Errors, even cached ones, should halt evaluations not in keepGoing mode. if (!cachedErrorKeys.isEmpty()) { // Note that the 'catastrophe' parameter doesn't really matter here (it's only used for // sanity checking). return constructResult(null, cachedErrorKeys, null, /*catastrophe=*/false); } } // We delay this check until we know that some kind of evaluation is necessary, since !keepGoing // and !keepsEdges are incompatible only in the case of a failed evaluation -- there is no // need to be overly harsh to callers who are just trying to retrieve a cached result. Preconditions.checkState( keepGoing || !(graph instanceof InMemoryGraphImpl) || ((InMemoryGraphImpl) graph).keepsEdges(), "nokeep_going evaluations are not allowed if graph edges are not kept: %s", skyKeys); Profiler.instance().startTask(ProfilerTask.SKYFRAME_EVAL, skyKeySet); try { ValueVisitor valueVisitor = forkJoinPool == null ? new ValueVisitor(threadCount) : new ValueVisitor(forkJoinPool); return eval(skyKeySet, valueVisitor); } finally { Profiler.instance().completeTask(ProfilerTask.SKYFRAME_EVAL); } } @ThreadCompatible private EvaluationResult eval(ImmutableSet skyKeys, ValueVisitor visitor) throws InterruptedException { // We unconditionally add the ErrorTransienceValue here, to ensure that it will be created, and // 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( null, Reason.PRE_OR_POST_EVALUATION, ImmutableList.of(ErrorTransienceValue.KEY)).values()); if (!errorTransienceEntry.isDone()) { injectValues( ImmutableMap.of(ErrorTransienceValue.KEY, (SkyValue) ErrorTransienceValue.INSTANCE), graphVersion, graph, dirtyKeyTracker); } for (Map.Entry e : graph.createIfAbsentBatch(null, Reason.PRE_OR_POST_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. switch (entry.addReverseDepAndCheckIfDone(null)) { case NEEDS_SCHEDULING: visitor.enqueueEvaluation(skyKey); break; case DONE: informProgressReceiverThatValueIsDone(skyKey, entry); break; case ALREADY_EVALUATING: break; default: throw new IllegalStateException(entry + " for " + skyKey + " in unknown state"); } } try { return waitForCompletionAndConstructResult(visitor, skyKeys); } finally { inflightKeysReceiver.accept(visitor.inflightNodes); } } private EvaluationResult waitForCompletionAndConstructResult( ValueVisitor visitor, Iterable skyKeys) throws InterruptedException { Map bubbleErrorInfo = null; boolean catastrophe = false; try { visitor.waitForCompletion(); } catch (final SchedulerException e) { if (!visitor.getCrashes().isEmpty()) { reporter.handle(Event.error("Crashes detected: " + visitor.getCrashes())); throw Iterables.getFirst(visitor.getCrashes(), null); } Throwables.propagateIfPossible(e.getCause(), InterruptedException.class); if (Thread.interrupted()) { // As per the contract of AbstractQueueVisitor#work, if an unchecked exception is thrown and // the build is interrupted, the thrown exception is what will be rethrown. Since the user // presumably wanted to interrupt the build, we ignore the thrown SchedulerException (which // doesn't indicate a programming bug) and throw an InterruptedException. throw new InterruptedException(); } SkyKey errorKey = Preconditions.checkNotNull(e.getFailedValue(), e); // ErrorInfo could only be null if SchedulerException wrapped an InterruptedException, but // that should have been propagated. ErrorInfo errorInfo = Preconditions.checkNotNull(e.getErrorInfo(), errorKey); if (!keepGoing) { bubbleErrorInfo = bubbleErrorUp(errorInfo, errorKey, skyKeys, visitor); } else { Preconditions.checkState( errorInfo.isCatastrophic(), "Scheduler exception only thrown for catastrophe in keep_going evaluation: %s", e); catastrophe = true; // Bubbling the error up requires that graph edges are present for done nodes. This is not // always the case in a keepGoing evaluation, since it is assumed that done nodes do not // need to be traversed. In this case, we hope the caller is tolerant of a possibly empty // result, and return prematurely. bubbleErrorInfo = ImmutableMap.of( errorKey, ValueWithMetadata.wrapWithMetadata( graph.get(null, Reason.ERROR_BUBBLING, errorKey).getValueMaybeWithMetadata())); } } Preconditions.checkState(visitor.getCrashes().isEmpty(), visitor.getCrashes()); // Successful evaluation, either because keepGoing or because we actually did succeed. // TODO(bazel-team): Maybe report root causes during the build for lower latency. return constructResult(visitor, skyKeys, bubbleErrorInfo, catastrophe); } /** * Walk up graph to find a top-level node (without parents) that wanted this failure. Store * the failed nodes along the way in a map, with ErrorInfos that are appropriate for that layer. * Example: * foo bar * \ / * unrequested baz * \ | * failed-node * User requests foo, bar. When failed-node fails, we look at its parents. unrequested is not * in-flight, so we replace failed-node by baz and repeat. We look at baz's parents. foo is * in-flight, so we replace baz by foo. Since foo is a top-level node and doesn't have parents, * we then break, since we know a top-level node, foo, that depended on the failed node. * * There's the potential for a weird "track jump" here in the case: * foo * / \ * fail1 fail2 * If fail1 and fail2 fail simultaneously, fail2 may start propagating up in the loop below. * However, foo requests fail1 first, and then throws an exception based on that. This is not * incorrect, but may be unexpected. * *

Returns a map of errors that have been constructed during the bubbling up, so that the * appropriate error can be returned to the caller, even though that error was not written to the * graph. If a cycle is detected during the bubbling, this method aborts and returns null so that * the normal cycle detection can handle the cycle. * *

Note that we are not propagating error to the first top-level node but to the highest one, * because during this process we can add useful information about error from other nodes. */ private Map bubbleErrorUp(final ErrorInfo leafFailure, SkyKey errorKey, Iterable skyKeys, ValueVisitor visitor) { Set rootValues = ImmutableSet.copyOf(skyKeys); ErrorInfo error = leafFailure; Map bubbleErrorInfo = new HashMap<>(); boolean externalInterrupt = false; while (true) { NodeEntry errorEntry = Preconditions.checkNotNull( graph.get(null, Reason.ERROR_BUBBLING, errorKey), errorKey); Iterable reverseDeps = errorEntry.isDone() ? errorEntry.getReverseDeps() : errorEntry.getInProgressReverseDeps(); // We should break from loop only when node doesn't have any parents. if (Iterables.isEmpty(reverseDeps)) { Preconditions.checkState(rootValues.contains(errorKey), "Current key %s has to be a top-level key: %s", errorKey, rootValues); break; } SkyKey parent = null; NodeEntry parentEntry = null; for (SkyKey bubbleParent : reverseDeps) { if (bubbleErrorInfo.containsKey(bubbleParent)) { // 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(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 // since any error message produced won't be meaningful to this evaluate call. // The child error must also be cached from a previous build. Preconditions.checkState(errorEntry.isDone(), "%s %s", errorEntry, bubbleParentEntry); Version parentVersion = bubbleParentEntry.getVersion(); Version childVersion = errorEntry.getVersion(); Preconditions.checkState(childVersion.atMost(graphVersion) && !childVersion.equals(graphVersion), "child entry is not older than the current graph version, but had a done parent. " + "child: %s childEntry: %s, childVersion: %s" + "bubbleParent: %s bubbleParentEntry: %s, parentVersion: %s, graphVersion: %s", errorKey, errorEntry, childVersion, bubbleParent, bubbleParentEntry, parentVersion, graphVersion); Preconditions.checkState(parentVersion.atMost(graphVersion) && !parentVersion.equals(graphVersion), "parent entry is not older than the current graph version. " + "child: %s childEntry: %s, childVersion: %s" + "bubbleParent: %s bubbleParentEntry: %s, parentVersion: %s, graphVersion: %s", errorKey, errorEntry, childVersion, bubbleParent, bubbleParentEntry, parentVersion, graphVersion); continue; } if (visitor.isInflight(bubbleParent) && bubbleParentEntry.getTemporaryDirectDeps().expensiveContains(errorKey)) { // Only bubble up to parent if it's part of this build. If this node was dirtied and // re-evaluated, but in a build without this parent, we may try to bubble up to that // parent. Don't -- it's not part of the build. // Similarly, the parent may not yet have requested this dep in its dirtiness-checking // process. Don't bubble up to it in that case either. parent = bubbleParent; parentEntry = bubbleParentEntry; break; } } if (parent == null) { Preconditions.checkState( rootValues.contains(errorKey), "Current key %s has to be a top-level key: %s, %s", errorKey, rootValues, errorEntry); break; } Preconditions.checkNotNull(parentEntry, "%s %s", errorKey, parent); errorKey = parent; SkyFunction factory = skyFunctions.get(parent.functionName()); if (parentEntry.isDirty()) { switch (parentEntry.getDirtyState()) { case CHECK_DEPENDENCIES: // If this value's child was bubbled up to, it did not signal this value, and so we must // manually make it ready to build. parentEntry.signalDep(); // Fall through to NEEDS_REBUILDING, since state is now NEEDS_REBUILDING. case NEEDS_REBUILDING: maybeMarkRebuilding(parentEntry); // Fall through to REBUILDING. case REBUILDING: break; default: throw new AssertionError(parent + " not in valid dirty state: " + parentEntry); } } SkyFunctionEnvironment env = new SkyFunctionEnvironment( parent, new GroupedList(), bubbleErrorInfo, ImmutableSet.of(), visitor); externalInterrupt = externalInterrupt || Thread.currentThread().isInterrupted(); try { // This build is only to check if the parent node can give us a better error. We don't // care about a return value. factory.compute(parent, env); } catch (InterruptedException interruptedException) { // Do nothing. // This throw happens if the builder requested the failed node, and then checked the // interrupted state later -- getValueOrThrow sets the interrupted bit after the failed // value is requested, to prevent the builder from doing too much work. } catch (SkyFunctionException builderException) { // Clear interrupted status. We're not listening to interrupts here. Thread.interrupted(); ReifiedSkyFunctionException reifiedBuilderException = new ReifiedSkyFunctionException(builderException, parent); if (reifiedBuilderException.getRootCauseSkyKey().equals(parent)) { error = ErrorInfo.fromException(reifiedBuilderException, /*isTransitivelyTransient=*/ false); bubbleErrorInfo.put(errorKey, ValueWithMetadata.error(ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)), env.buildEvents(parentEntry, /*missingChildren=*/true))); continue; } } finally { // Clear interrupted status. We're not listening to interrupts here. Thread.interrupted(); } // 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(parentEntry, /*missingChildren=*/true))); } // Reset the interrupt bit if there was an interrupt from outside this evaluator interrupt. // Note that there are internal interrupts set in the node builder environment if an error // bubbling node calls getValueOrThrow() on a node in error. if (externalInterrupt) { Thread.currentThread().interrupt(); } return bubbleErrorInfo; } /** * Constructs an {@link EvaluationResult} from the {@link #graph}. Looks for cycles if there * are unfinished nodes but no error was already found through bubbling up * (as indicated by {@code bubbleErrorInfo} being null). * *

{@code visitor} may be null, but only in the case where all graph entries corresponding to * {@code skyKeys} are known to be in the DONE state ({@code entry.isDone()} returns true). */ private EvaluationResult constructResult( @Nullable ValueVisitor visitor, Iterable skyKeys, @Nullable Map bubbleErrorInfo, boolean catastrophe) { Preconditions.checkState( catastrophe == (keepGoing && bubbleErrorInfo != null), "Catastrophe not consistent with keepGoing mode and bubbleErrorInfo: %s %s %s %s", skyKeys, catastrophe, keepGoing, bubbleErrorInfo); EvaluationResult.Builder result = EvaluationResult.builder(); List cycleRoots = new ArrayList<>(); for (SkyKey skyKey : skyKeys) { SkyValue unwrappedValue = maybeGetValueFromError( skyKey, graph.get(null, Reason.PRE_OR_POST_EVALUATION, skyKey), bubbleErrorInfo); ValueWithMetadata valueWithMetadata = unwrappedValue == NULL_MARKER ? null : ValueWithMetadata.wrapWithMetadata(unwrappedValue); // Cycle checking: if there is a cycle, evaluation cannot progress, therefore, // the final values will not be in DONE state when the work runs out. if (valueWithMetadata == null) { // Don't look for cycles if the build failed for a known reason. if (bubbleErrorInfo == null) { cycleRoots.add(skyKey); } continue; } SkyValue value = valueWithMetadata.getValue(); // TODO(bazel-team): Verify that message replay is fast and works in failure // modes [skyframe-core] // Note that replaying events here is only necessary on null builds, because otherwise we // would have already printed the transitive messages after building these values. replayingNestedSetEventVisitor.visit(valueWithMetadata.getTransitiveEvents()); ErrorInfo errorInfo = valueWithMetadata.getErrorInfo(); Preconditions.checkState(value != null || errorInfo != null, skyKey); if (!keepGoing && errorInfo != null) { // value will be null here unless the value was already built on a prior keepGoing build. result.addError(skyKey, errorInfo); continue; } if (value == null) { // Note that we must be in the keepGoing case. Only make this value an error if it doesn't // have a value. The error shouldn't matter to the caller since the value succeeded after a // fashion. result.addError(skyKey, errorInfo); } else { result.addResult(skyKey, value); } } if (!cycleRoots.isEmpty()) { Preconditions.checkState(visitor != null, skyKeys); checkForCycles(cycleRoots, result, visitor, keepGoing); } if (catastrophe) { // We may not have a top-level node completed. Inform the caller of the catastrophic exception // that shut down the evaluation so that it has some context. ErrorInfo errorInfo = Preconditions.checkNotNull( Iterables.getOnlyElement(bubbleErrorInfo.values()).getErrorInfo(), "bubbleErrorInfo should have contained element with errorInfo: %s", bubbleErrorInfo); Preconditions.checkState( errorInfo.isCatastrophic(), "bubbleErrorInfo should have contained element with catastrophe: %s", bubbleErrorInfo); result.setCatastrophe(errorInfo.getException()); } EvaluationResult builtResult = result.build(); Preconditions.checkState( bubbleErrorInfo == null || builtResult.hasError(), "If an error bubbled up, some top-level node must be in error: %s %s %s", bubbleErrorInfo, skyKeys, builtResult); return builtResult; } private void checkForCycles( Iterable badRoots, EvaluationResult.Builder result, final ValueVisitor visitor, boolean keepGoing) { try (AutoProfiler p = AutoProfiler.logged("Checking for Skyframe cycles", LOG, 10)) { for (SkyKey root : badRoots) { ErrorInfo errorInfo = checkForCycles(root, visitor, keepGoing); if (errorInfo == null) { // This node just wasn't finished when evaluation aborted -- there were no cycles below // it. Preconditions.checkState(!keepGoing, "", root, badRoots); continue; } Preconditions.checkState(!Iterables.isEmpty(errorInfo.getCycleInfo()), "%s was not evaluated, but was not part of a cycle", root); result.addError(root, errorInfo); if (!keepGoing) { return; } } } } /** * Marker value that we push onto a stack before we push a node's children on. When the marker * value is popped, we know that all the children are finished. We would use null instead, but * ArrayDeque does not permit null elements. */ private static final SkyKey CHILDREN_FINISHED = SkyKey.create(SkyFunctionName.create("MARKER"), "MARKER"); /** The max number of cycles we will report to the user for a given root, to avoid OOMing. */ private static final int MAX_CYCLES = 20; /** * The algorithm for this cycle detector is as follows. We visit the graph depth-first, keeping * track of the path we are currently on. We skip any DONE nodes (they are transitively * error-free). If we come to a node already on the path, we immediately construct a cycle. If * we are in the noKeepGoing case, we return ErrorInfo with that cycle to the caller. Otherwise, * we continue. Once all of a node's children are done, we construct an error value for it, based * on those children. Finally, when the original root's node is constructed, we return its * ErrorInfo. */ private ErrorInfo checkForCycles(SkyKey root, ValueVisitor visitor, boolean keepGoing) { // The number of cycles found. Do not keep on searching for more cycles after this many were // found. int cyclesFound = 0; // The path through the graph currently being visited. List graphPath = new ArrayList<>(); // Set of nodes on the path, to avoid expensive searches through the path for cycles. Set pathSet = new HashSet<>(); // Maintain a stack explicitly instead of recursion to avoid stack overflows // on extreme graphs (with long dependency chains). Deque toVisit = new ArrayDeque<>(); toVisit.push(root); // The procedure for this check is as follows: we visit a node, push it onto the graph stack, // push a marker value onto the toVisit stack, and then push all of its children onto the // toVisit stack. Thus, when the marker node comes to the top of the toVisit stack, we have // visited the downward transitive closure of the value. At that point, all of its children must // be finished, and so we can build the definitive error info for the node, popping it off the // graph stack. while (!toVisit.isEmpty()) { SkyKey key = toVisit.pop(); NodeEntry entry; if (key == CHILDREN_FINISHED) { // 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(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()) { continue; } if (!keepGoing) { // in the --nokeep_going mode, we would have already returned if we'd found a cycle below // this node. The fact that we haven't means that there were no cycles below this node // -- it just hadn't finished evaluating. So skip it. continue; } Set removedDeps = ImmutableSet.of(); if (cyclesFound < MAX_CYCLES) { // Value must be ready, because all of its children have finished, so we can build its // error. Preconditions.checkState(entry.isReady(), "%s not ready. ValueEntry: %s", key, entry); } else if (!entry.isReady()) { removedDeps = removeIncompleteChildrenForCycle( key, entry, Iterables.concat(entry.getTemporaryDirectDeps())); } maybeMarkRebuilding(entry); GroupedList directDeps = entry.getTemporaryDirectDeps(); // Find out which children have errors. Similar logic to that in Evaluate#run(). List 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); SkyFunctionEnvironment env = new SkyFunctionEnvironment( key, directDeps, Sets.difference(entry.getAllRemainingDirtyDirectDeps(), removedDeps), visitor); env.setError( entry, ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false); env.commit(entry, /*enqueueParents=*/false); } else { entry = graph.get(null, Reason.CYCLE_CHECKING, key); } Preconditions.checkNotNull(entry, key); // Nothing to be done for this node if it already has an entry. if (entry.isDone()) { continue; } if (cyclesFound == MAX_CYCLES) { // Do not keep on searching for cycles indefinitely, to avoid excessive runtime/OOMs. continue; } if (pathSet.contains(key)) { int cycleStart = graphPath.indexOf(key); // Found a cycle! cyclesFound++; Iterable cycle = graphPath.subList(cycleStart, graphPath.size()); LOG.info("Found cycle : " + cycle + " from " + graphPath); // Put this node into a consistent state for building if it is dirty. if (entry.isDirty() && entry.getDirtyState() == NodeEntry.DirtyState.CHECK_DEPENDENCIES) { // In the check deps state, entry has exactly one child not done yet. Note that this node // must be part of the path to the cycle we have found (since done nodes cannot be in // cycles, and this is the only missing one). Thus, it will not be removed below in // removeDescendantsOfCycleValue, so it is safe here to signal that it is done. entry.signalDep(); maybeMarkRebuilding(entry); } if (keepGoing) { // Any children of this node that we haven't already visited are not worth visiting, // since this node is about to be done. Thus, the only child worth visiting is the one in // this cycle, the cycleChild (which may == key if this cycle is a self-edge). SkyKey cycleChild = selectCycleChild(key, graphPath, cycleStart); Set removedDeps = removeDescendantsOfCycleValue( key, entry, cycleChild, toVisit, graphPath.size() - cycleStart); ValueWithMetadata dummyValue = ValueWithMetadata.wrapWithMetadata(new SkyValue() {}); SkyFunctionEnvironment env = new SkyFunctionEnvironment( key, entry.getTemporaryDirectDeps(), ImmutableMap.of(cycleChild, dummyValue), Sets.difference(entry.getAllRemainingDirtyDirectDeps(), removedDeps), visitor); // Construct error info for this node. Get errors from children, which are all done // except possibly for the cycleChild. List allErrors = getChildrenErrorsForCycleChecking( Iterables.concat(entry.getTemporaryDirectDeps()), /*unfinishedChild=*/ cycleChild); CycleInfo cycleInfo = new CycleInfo(cycle); // Add in this cycle. allErrors.add(ErrorInfo.fromCycle(cycleInfo)); 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 // path) and return. Preconditions.checkState(graphPath.get(0).equals(root), "%s not reached from %s. ValueEntry: %s", key, root, entry); return ErrorInfo.fromCycle(new CycleInfo(graphPath.subList(0, cycleStart), cycle)); } } // This node is not yet known to be in a cycle. So process its children. Iterable children = Iterables.concat(entry.getTemporaryDirectDeps()); if (Iterables.isEmpty(children)) { continue; } // Prefetch all children, in case our graph performs better with a primed cache. No need to // recurse into done nodes. The fields of done nodes aren't necessary, since we'll filter them // out. // TODO(janakr): If graph implementations start using these hints for not-done nodes, we may // have to change this. Map childrenNodes = graph.getBatch(key, Reason.EXISTENCE_CHECKING, children); Preconditions.checkState(childrenNodes.size() == Iterables.size(children), childrenNodes); children = Maps.filterValues(childrenNodes, new Predicate() { @Override public boolean apply(NodeEntry nodeEntry) { return !nodeEntry.isDone(); } }).keySet(); // This marker flag will tell us when all this node's children have been processed. toVisit.push(CHILDREN_FINISHED); // This node is now part of the path through the graph. graphPath.add(key); pathSet.add(key); for (SkyKey nextValue : children) { toVisit.push(nextValue); } } return keepGoing ? getAndCheckDoneForCycle(root).getErrorInfo() : null; } /** * Returns the child of this node that is in the cycle that was just found. If the cycle is a * self-edge, returns the node itself. */ private static SkyKey selectCycleChild(SkyKey key, List graphPath, int cycleStart) { return cycleStart + 1 == graphPath.size() ? key : graphPath.get(cycleStart + 1); } /** * Get all the errors of child nodes. There must be at least one cycle amongst them. * * @param children child nodes to query for errors. * @return List of ErrorInfos from all children that had errors. */ private List getChildrenErrorsForCycle(SkyKey parent, Iterable children) { List allErrors = new ArrayList<>(); boolean foundCycle = false; for (NodeEntry childNode : getAndCheckDoneBatchForCycle(parent, children).values()) { ErrorInfo errorInfo = childNode.getErrorInfo(); if (errorInfo != null) { foundCycle |= !Iterables.isEmpty(errorInfo.getCycleInfo()); allErrors.add(errorInfo); } } Preconditions.checkState(foundCycle, "", children, allErrors); return allErrors; } /** * Get all the errors of child nodes. * * @param children child nodes to query for errors. * @param unfinishedChild child which is allowed to not be done. * @return List of ErrorInfos from all children that had errors. */ private List getChildrenErrorsForCycleChecking( Iterable children, SkyKey unfinishedChild) { List allErrors = new ArrayList<>(); Set> childEntries = getBatchValues(null, Reason.CYCLE_CHECKING, children).entrySet(); for (Entry childMapEntry : childEntries) { SkyKey childKey = childMapEntry.getKey(); NodeEntry childNodeEntry = childMapEntry.getValue(); ErrorInfo errorInfo = getErrorMaybe(childKey, childNodeEntry, /*allowUnfinished=*/childKey.equals(unfinishedChild)); if (errorInfo != null) { allErrors.add(errorInfo); } } return allErrors; } @Nullable private ErrorInfo getErrorMaybe(SkyKey key, NodeEntry childNodeEntry, boolean allowUnfinished) { Preconditions.checkNotNull(childNodeEntry, key); if (!allowUnfinished) { return checkDone(key, childNodeEntry).getErrorInfo(); } return childNodeEntry.isDone() ? childNodeEntry.getErrorInfo() : null; } /** * Removes direct children of key from toVisit and from the entry itself, and makes the entry * ready if necessary. We must do this because it would not make sense to try to build the * children after building the entry. It would violate the invariant that a parent can only be * built after its children are built; See bug "Precondition error while evaluating a Skyframe * graph with a cycle". * * @param key SkyKey of node in a cycle. * @param entry NodeEntry of node in a cycle. * @param cycleChild direct child of key in the cycle, or key itself if the cycle is a self-edge. * @param toVisit list of remaining nodes to visit by the cycle-checker. * @param cycleLength the length of the cycle found. */ private Set removeDescendantsOfCycleValue( SkyKey key, NodeEntry entry, @Nullable SkyKey cycleChild, Iterable toVisit, int cycleLength) { GroupedList directDeps = entry.getTemporaryDirectDeps(); Set unvisitedDeps = Sets.newHashSetWithExpectedSize(directDeps.numElements()); Iterables.addAll(unvisitedDeps, Iterables.concat(directDeps)); unvisitedDeps.remove(cycleChild); // Remove any children from this node that are not part of the cycle we just found. They are // irrelevant to the node as it stands, and if they are deleted from the graph because they are // not built by the end of cycle-checking, we would have dangling references. Set removedDeps = removeIncompleteChildrenForCycle(key, entry, unvisitedDeps); if (!entry.isReady()) { // The entry has at most one undone dep now, its cycleChild. Signal to make entry ready. Note // that the entry can conceivably be ready if its cycleChild already found a different cycle // and was built. entry.signalDep(); } maybeMarkRebuilding(entry); Preconditions.checkState(entry.isReady(), "%s %s %s", key, cycleChild, entry); Iterator it = toVisit.iterator(); while (it.hasNext()) { SkyKey descendant = it.next(); if (descendant == CHILDREN_FINISHED) { // Marker value, delineating the end of a group of children that were enqueued. cycleLength--; if (cycleLength == 0) { // We have seen #cycleLength-1 marker values, and have arrived at the one for this value, // so we are done. return removedDeps; } continue; // Don't remove marker values. } if (cycleLength == 1) { // Remove the direct children remaining to visit of the cycle node. Preconditions.checkState(unvisitedDeps.contains(descendant), "%s %s %s %s %s", key, descendant, cycleChild, unvisitedDeps, entry); it.remove(); } } throw new IllegalStateException("There were not " + cycleLength + " groups of children in " + toVisit + " when trying to remove children of " + key + " other than " + cycleChild); } private Set removeIncompleteChildrenForCycle( SkyKey key, NodeEntry entry, Iterable children) { Set unfinishedDeps = new HashSet<>(); for (SkyKey child : children) { if (removeIncompleteChildForCycle(key, child)) { unfinishedDeps.add(child); } } entry.removeUnfinishedDeps(unfinishedDeps); return unfinishedDeps; } private static NodeEntry checkDone(SkyKey key, NodeEntry entry) { Preconditions.checkNotNull(entry, key); Preconditions.checkState(entry.isDone(), "%s %s", key, entry); return entry; } private NodeEntry getAndCheckDoneForCycle(SkyKey key) { return checkDone(key, graph.get(null, Reason.CYCLE_CHECKING, key)); } private Map getAndCheckDoneBatchForCycle( SkyKey parent, Iterable keys) { Map nodes = getBatchValues(parent, Reason.CYCLE_CHECKING, keys); for (Map.Entry nodeEntryMapEntry : nodes.entrySet()) { checkDone(nodeEntryMapEntry.getKey(), nodeEntryMapEntry.getValue()); } return nodes; } private static final SkyValue NULL_MARKER = new SkyValue() {}; private static SkyValue maybeGetValueFromError( SkyKey key, @Nullable NodeEntry entry, @Nullable Map bubbleErrorInfo) { SkyValue value = bubbleErrorInfo == null ? null : bubbleErrorInfo.get(key); if (value != null) { Preconditions.checkNotNull( entry, "Value cannot have error before evaluation started: %s %s", key, value); return value; } return isDoneForBuild(entry) ? entry.getValueMaybeWithMetadata() : NULL_MARKER; } /** * Return true if the entry does not need to be re-evaluated this build. The entry will need to be * re-evaluated if it is not done, but also if it was not completely evaluated last build and this * build is keepGoing. */ private static boolean isDoneForBuild(@Nullable NodeEntry entry) { return entry != null && entry.isDone(); } static void injectValues( Map injectionMap, Version version, EvaluableGraph graph, DirtyKeyTracker dirtyKeyTracker) { Map prevNodeEntries = graph.createIfAbsentBatch(null, Reason.OTHER, injectionMap.keySet()); for (Map.Entry injectionEntry : injectionMap.entrySet()) { SkyKey key = injectionEntry.getKey(); SkyValue value = injectionEntry.getValue(); NodeEntry prevEntry = prevNodeEntries.get(key); DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null); Preconditions.checkState( newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry); if (prevEntry.isDirty()) { Preconditions.checkState( newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry); // There was an existing entry for this key in the graph. // Get the node in the state where it is able to accept a value. // Check that the previous node has no dependencies. Overwriting a value with deps with an // injected value (which is by definition deps-free) needs a little additional bookkeeping // (removing reverse deps from the dependencies), but more importantly it's something that // we want to avoid, because it indicates confusion of input values and derived values. Preconditions.checkState( prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry); prevEntry.markRebuilding(); } prevEntry.setValue(value, version); // Now that this key's injected value is set, it is no longer dirty. dirtyKeyTracker.notDirty(key); } } }