Don't remove reverse deps until node is known to be changed. This helps avoid mutating the deps of nodes that are still going to be deps after evaluation is finished.
--
MOS_MIGRATED_REVID=103659429
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index 547549e..41b94ad 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -73,9 +73,10 @@
/**
* The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes
- * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link DirtyState#REBUILDING},
- * depending on whether the caller specified that the node was itself changed or not. A non-null
- * {@code dirtyState} indicates that the node {@link #isDirty} in some way.
+ * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or
+ * {@link DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node
+ * was itself changed or not. A non-null {@code dirtyState} indicates that the node
+ * {@link #isDirty} in some way.
*/
private DirtyState dirtyState = null;
@@ -118,41 +119,41 @@
// node will be removed by the time evaluation starts, so reverse deps to signal can just be
// reverse deps in the main ValueEntry object.
private Object reverseDepsToSignal = ImmutableList.of();
- private List<SkyKey> reverseDepsToRemove = null;
+ private Object reverseDepsDataToConsolidate = null;
private boolean reverseDepIsSingleObject = false;
private static final ReverseDepsUtil<BuildingState> REVERSE_DEPS_UTIL =
new ReverseDepsUtil<BuildingState>() {
- @Override
- void setReverseDepsObject(BuildingState container, Object object) {
- container.reverseDepsToSignal = object;
- }
+ @Override
+ void setReverseDepsObject(BuildingState container, Object object) {
+ container.reverseDepsToSignal = object;
+ }
- @Override
- void setSingleReverseDep(BuildingState container, boolean singleObject) {
- container.reverseDepIsSingleObject = singleObject;
- }
+ @Override
+ void setSingleReverseDep(BuildingState container, boolean singleObject) {
+ container.reverseDepIsSingleObject = singleObject;
+ }
- @Override
- void setReverseDepsToRemove(BuildingState container, List<SkyKey> object) {
- container.reverseDepsToRemove = object;
- }
+ @Override
+ void setDataToConsolidate(BuildingState container, Object dataToConsolidate) {
+ container.reverseDepsDataToConsolidate = dataToConsolidate;
+ }
- @Override
- Object getReverseDepsObject(BuildingState container) {
- return container.reverseDepsToSignal;
- }
+ @Override
+ Object getReverseDepsObject(BuildingState container) {
+ return container.reverseDepsToSignal;
+ }
- @Override
- boolean isSingleReverseDep(BuildingState container) {
- return container.reverseDepIsSingleObject;
- }
+ @Override
+ boolean isSingleReverseDep(BuildingState container) {
+ return container.reverseDepIsSingleObject;
+ }
- @Override
- List<SkyKey> getReverseDepsToRemove(BuildingState container) {
- return container.reverseDepsToRemove;
- }
- };
+ @Override
+ Object getDataToConsolidate(BuildingState container) {
+ return container.reverseDepsDataToConsolidate;
+ }
+ };
// Below are fields that are used for dirty nodes.
@@ -180,12 +181,10 @@
Preconditions.checkState(isChanged || !this.lastBuildDirectDeps.isEmpty(),
"%s is being marked dirty, not changed, but has no children that could have dirtied it",
this);
- dirtyState = isChanged ? DirtyState.REBUILDING
- : DirtyState.CHECK_DEPENDENCIES;
- if (dirtyState == DirtyState.CHECK_DEPENDENCIES) {
- // We need to iterate through the deps to see if they have changed. Initialize the iterator.
- dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
- }
+ dirtyState = isChanged ? DirtyState.NEEDS_REBUILDING : DirtyState.CHECK_DEPENDENCIES;
+ // We need to iterate through the deps to see if they have changed, or to remove them if one
+ // has. Initialize the iterator.
+ dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
}
static BuildingState newDirtyState(boolean isChanged,
@@ -197,7 +196,7 @@
Preconditions.checkState(isDirty(), this);
Preconditions.checkState(!isChanged(), this);
Preconditions.checkState(!evaluating, this);
- dirtyState = DirtyState.REBUILDING;
+ dirtyState = DirtyState.NEEDS_REBUILDING;
}
void forceChanged() {
@@ -234,11 +233,7 @@
* @see NodeEntry#isChanged()
*/
boolean isChanged() {
- return dirtyState == DirtyState.REBUILDING;
- }
-
- private boolean rebuilding() {
- return dirtyState == DirtyState.REBUILDING;
+ return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING;
}
/**
@@ -246,10 +241,14 @@
* actually like to check that the node has been evaluated, but that is not available in
* this context.
*/
- private void checkNotProcessing() {
+ private void checkFinishedBuildingWhenAboutToSetValue() {
Preconditions.checkState(evaluating, "not started building %s", this);
- Preconditions.checkState(!isDirty() || dirtyState == DirtyState.VERIFIED_CLEAN
- || rebuilding(), "not done building %s", this);
+ Preconditions.checkState(
+ !isDirty()
+ || dirtyState == DirtyState.VERIFIED_CLEAN
+ || dirtyState == DirtyState.REBUILDING,
+ "not done building %s",
+ this);
Preconditions.checkState(isReady(), "not done building %s", this);
}
@@ -269,7 +268,7 @@
* finished is equal to the number of known children.
*
* <p>If the node is dirty and checking its deps for changes, this also updates {@link
- * #dirtyState} as needed -- {@link DirtyState#REBUILDING} if the child has changed,
+ * #dirtyState} as needed -- {@link DirtyState#NEEDS_REBUILDING} if the child has changed,
* and {@link DirtyState#VERIFIED_CLEAN} if the child has not changed and this was the
* last child to be checked (as determined by {@link #dirtyDirectDepIterator}.hasNext() and
* isReady()).
@@ -278,15 +277,15 @@
*/
boolean signalDep(boolean childChanged) {
signaledDeps++;
- if (isDirty() && !rebuilding()) {
- // Synchronization isn't needed here because the only caller is ValueEntry, which does it
- // through the synchronized method signalDep(long).
+ if (isDirty() && !isChanged()) {
+ // Synchronization isn't needed here because the only caller is NodeEntry, which does it
+ // through the synchronized method signalDep(Version).
if (childChanged) {
- dirtyState = DirtyState.REBUILDING;
+ dirtyState = DirtyState.NEEDS_REBUILDING;
} else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
&& isReady()
&& !dirtyDirectDepIterator.hasNext()) {
- // No other dep already marked this as REBUILDING, no deps outstanding, and this was
+ // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
// the last block of deps to be checked.
dirtyState = DirtyState.VERIFIED_CLEAN;
}
@@ -300,7 +299,7 @@
* was built, in the same order. Should only be used by {@link NodeEntry#setValue}.
*/
boolean unchangedFromLastBuild(SkyValue newValue) {
- checkNotProcessing();
+ checkFinishedBuildingWhenAboutToSetValue();
return getLastBuildValue().equals(newValue) && lastBuildDirectDeps.equals(directDeps);
}
@@ -341,6 +340,22 @@
return nextDeps;
}
+ Collection<SkyKey> getAllRemainingDirtyDirectDeps() {
+ Preconditions.checkState(isDirty(), this);
+ ImmutableList.Builder<SkyKey> result = ImmutableList.builder();
+ while (dirtyDirectDepIterator.hasNext()) {
+ result.addAll(dirtyDirectDepIterator.next());
+ }
+ return result.build();
+ }
+
+ Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+ Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
+ Collection<SkyKey> result = getAllRemainingDirtyDirectDeps();
+ dirtyState = DirtyState.REBUILDING;
+ return result;
+ }
+
void addDirectDeps(GroupedListHelper<SkyKey> depsThisRun) {
directDeps.append(depsThisRun);
}
@@ -380,7 +395,7 @@
* @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey)
*/
void addReverseDepToSignal(SkyKey newReverseDep) {
- REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+ REVERSE_DEPS_UTIL.consolidateData(this);
REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep));
}
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 ad50bea..9e346eb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -27,7 +27,6 @@
import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingInvalidationState;
import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvalidationState;
import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
-import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
import com.google.devtools.build.skyframe.ParallelEvaluator.Receiver;
import java.io.PrintStream;
@@ -224,29 +223,8 @@
return;
}
for (Entry<SkyKey, SkyValue> entry : valuesToInject.entrySet()) {
- SkyKey key = entry.getKey();
- SkyValue value = entry.getValue();
- Preconditions.checkState(value != null, key);
- NodeEntry prevEntry = graph.createIfAbsent(key);
- if (prevEntry.isDirty()) {
- // 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.
- Preconditions.checkState(prevEntry.getTemporaryDirectDeps().isEmpty(), key);
-
- DependencyState newState = prevEntry.addReverseDepAndCheckIfDone(null);
- Preconditions.checkState(newState == DependencyState.NEEDS_SCHEDULING, key);
-
- // 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.setValue(value, version);
- // The evaluate method previously invalidated all keys in valuesToInject that survived the
- // pruneInjectedValues call. Now that this key's injected value is set, it is no longer dirty.
- dirtyKeyTracker.notDirty(key);
+ ParallelEvaluator.injectValue(
+ entry.getKey(), entry.getValue(), version, graph, dirtyKeyTracker);
}
// Start with a new map to avoid bloat since clear() does not downsize the map.
valuesToInject = new HashMap<>();
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index fa8e308..f3a6a81 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -18,11 +18,11 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
import java.util.Collection;
-import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
@@ -82,49 +82,49 @@
protected boolean reverseDepIsSingleObject = false;
/**
- * During the invalidation we keep the reverse deps to be removed in this list instead of directly
- * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N).
+ * When reverse deps are removed or checked for presence, we store them in this object instead of
+ * directly removing/checking them. That is because removals/checks in reverseDeps are O(N).
* Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
*
* <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
- * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done
- * more effectively than trying to remove each dirty reverse dependency individually (O(N) each
- * time).
+ * {@code consolidateData} first. While this operation is not free, it can be done
+ * more effectively than trying to remove/check each dirty reverse dependency individually (O(N)
+ * each time).
*/
- private List<SkyKey> reverseDepsToRemove = null;
+ private Object reverseDepsDataToConsolidate = null;
protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
new ReverseDepsUtil<InMemoryNodeEntry>() {
- @Override
- void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
- container.reverseDeps = object;
- }
+ @Override
+ void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
+ container.reverseDeps = object;
+ }
- @Override
- void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
- container.reverseDepIsSingleObject = singleObject;
- }
+ @Override
+ void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
+ container.reverseDepIsSingleObject = singleObject;
+ }
- @Override
- void setReverseDepsToRemove(InMemoryNodeEntry container, List<SkyKey> object) {
- container.reverseDepsToRemove = object;
- }
+ @Override
+ void setDataToConsolidate(InMemoryNodeEntry container, Object dataToConsolidate) {
+ container.reverseDepsDataToConsolidate = dataToConsolidate;
+ }
- @Override
- Object getReverseDepsObject(InMemoryNodeEntry container) {
- return container.reverseDeps;
- }
+ @Override
+ Object getReverseDepsObject(InMemoryNodeEntry container) {
+ return container.reverseDeps;
+ }
- @Override
- boolean isSingleReverseDep(InMemoryNodeEntry container) {
- return container.reverseDepIsSingleObject;
- }
+ @Override
+ boolean isSingleReverseDep(InMemoryNodeEntry container) {
+ return container.reverseDepIsSingleObject;
+ }
- @Override
- List<SkyKey> getReverseDepsToRemove(InMemoryNodeEntry container) {
- return container.reverseDepsToRemove;
- }
- };
+ @Override
+ Object getDataToConsolidate(InMemoryNodeEntry container) {
+ return container.reverseDepsDataToConsolidate;
+ }
+ };
/**
* The transient state of this entry, after it has been created but before it is done. It allows
@@ -202,7 +202,7 @@
private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
// Get reverse deps that need to be signaled.
ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
- REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+ REVERSE_DEPS_UTIL.consolidateData(this);
REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
this.directDeps = buildingState.getFinishedDirectDeps().compress();
@@ -247,7 +247,7 @@
public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
if (reverseDep != null) {
if (keepEdges()) {
- REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+ REVERSE_DEPS_UTIL.consolidateData(this);
REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
}
if (isDone()) {
@@ -263,7 +263,20 @@
return DependencyState.DONE;
}
return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING
- : DependencyState.ADDED_DEP;
+ : DependencyState.ALREADY_EVALUATING;
+ }
+
+ @Override
+ public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+ Preconditions.checkNotNull(reverseDep, this);
+ Preconditions.checkState(keepEdges(), "%s %s", reverseDep, this);
+ if (!isDone()) {
+ REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+ buildingState.addReverseDepToSignal(reverseDep);
+ } else {
+ REVERSE_DEPS_UTIL.checkReverseDep(this, reverseDep);
+ }
+ return addReverseDepAndCheckIfDone(null);
}
@Override
@@ -271,19 +284,23 @@
if (!keepEdges()) {
return;
}
- if (REVERSE_DEPS_UTIL.reverseDepsIsEmpty(this)) {
- // If an entry has no existing reverse deps, all its reverse deps are to signal, and vice
- // versa.
- buildingState.removeReverseDepToSignal(reverseDep);
- } else {
- REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
- }
+ REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
}
@Override
- public synchronized Collection<SkyKey> getReverseDeps() {
+ public synchronized void removeInProgressReverseDep(SkyKey reverseDep) {
+ buildingState.removeReverseDepToSignal(reverseDep);
+ }
+
+ @Override
+ public synchronized Iterable<SkyKey> getReverseDeps() {
assertKeepEdges();
- return REVERSE_DEPS_UTIL.getReverseDeps(this);
+ Iterable<SkyKey> reverseDeps = REVERSE_DEPS_UTIL.getReverseDeps(this);
+ if (isDone()) {
+ return reverseDeps;
+ } else {
+ return Iterables.concat(reverseDeps, buildingState.getReverseDepsToSignal());
+ }
}
@Override
@@ -313,15 +330,13 @@
}
@Override
- @Nullable
- public synchronized Iterable<SkyKey> markDirty(boolean isChanged) {
+ public synchronized boolean markDirty(boolean isChanged) {
assertKeepEdges();
if (isDone()) {
- GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps);
- buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value);
+ buildingState =
+ BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
value = null;
- directDeps = null;
- return lastDirectDeps.toSet();
+ return true;
}
// The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
// thread may have lost the race, but it is the caller's responsibility not to try to mark
@@ -330,13 +345,12 @@
Preconditions.checkState(isChanged != isChanged(),
"Cannot mark node dirty twice or changed twice: %s", this);
Preconditions.checkState(value == null, "Value should have been reset already %s", this);
- Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this);
if (isChanged) {
// If the changed marker lost the race, we just need to mark changed in this method -- all
// other work was done by the dirty marker.
buildingState.markChanged();
}
- return null;
+ return false;
}
@Override
@@ -371,10 +385,27 @@
/** @see BuildingState#getNextDirtyDirectDeps() */
@Override
public synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
+ Preconditions.checkState(isReady(), this);
return buildingState.getNextDirtyDirectDeps();
}
@Override
+ public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+ Preconditions.checkState(!isDone(), this);
+ if (!isDirty()) {
+ return getTemporaryDirectDeps();
+ } else {
+ return Iterables.concat(
+ getTemporaryDirectDeps(), buildingState.getAllRemainingDirtyDirectDeps());
+ }
+ }
+
+ @Override
+ public synchronized Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps() {
+ return buildingState.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+ }
+
+ @Override
public synchronized Set<SkyKey> getTemporaryDirectDeps() {
Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
return buildingState.getDirectDepsForBuild();
@@ -403,13 +434,15 @@
}
@Override
- public String toString() {
+ public synchronized String toString() {
return MoreObjects.toStringHelper(this)
+ .add("identity", System.identityHashCode(this))
.add("value", value)
.add("version", version)
.add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
.add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
- .add("buildingState", buildingState).toString();
+ .add("buildingState", buildingState)
+ .toString();
}
/**
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 791155a..659f8f6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -239,17 +239,39 @@
for (SkyKey reverseDep : entry.getReverseDeps()) {
visit(reverseDep, InvalidationType.DELETED, !MUST_EXIST);
}
+
+ // Unregister this node as an rdep from its direct deps, since reverse dep edges
+ // cannot point to non-existent nodes. To know whether the child has this node as an
+ // "in-progress" rdep to be signaled, or just as a known rdep, we look at the deps
+ // that this node declared during its last (presumably interrupted) evaluation. If a
+ // dep is in this set, then it was notified to signal this node, and so the rdep
+ // will be an in-progress rdep, if the dep itself isn't done. Otherwise it will be a
+ // normal rdep. That information is used to remove this node as an rdep from the
+ // correct list of rdeps in the child -- because of our compact storage of rdeps,
+ // checking which list contains this parent could be expensive.
+ Set<SkyKey> signalingDeps =
+ entry.isDone() ? ImmutableSet.<SkyKey>of() : entry.getTemporaryDirectDeps();
Iterable<SkyKey> directDeps =
- entry.isDone() ? entry.getDirectDeps() : entry.getTemporaryDirectDeps();
- // Unregister this node from direct deps, since reverse dep edges cannot point to
- // non-existent nodes.
- for (SkyKey directDep : directDeps) {
- NodeEntry dep = graph.get(directDep);
+ entry.isDone()
+ ? entry.getDirectDeps()
+ : entry.getAllDirectDepsForIncompleteNode();
+ Map<SkyKey, NodeEntry> depMap = graph.getBatch(directDeps);
+ for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) {
+ NodeEntry dep = directDepEntry.getValue();
if (dep != null) {
- dep.removeReverseDep(key);
+ if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
+ dep.removeReverseDep(key);
+ } else {
+ // This step is not strictly necessary, since all in-progress nodes are
+ // deleted during graph cleaning, which happens in a single
+ // DeletingNodeVisitor visitation, aka the one right now. We leave this here
+ // in case the logic changes.
+ dep.removeInProgressReverseDep(key);
+ }
}
}
}
+
// Allow custom key-specific logic to update dirtiness status.
informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DELETED);
// Actually remove the node.
@@ -343,40 +365,20 @@
return;
}
- // This entry remains in the graph in this dirty state until it is re-evaluated.
- Iterable<SkyKey> deps = entry.markDirty(isChanged);
// It is not safe to interrupt the logic from this point until the end of the method.
// Any exception thrown should be unrecoverable.
- if (deps == null) {
+ // This entry remains in the graph in this dirty state until it is re-evaluated.
+ if (!entry.markDirty(isChanged)) {
// Another thread has already dirtied this node. Don't do anything in this thread.
pendingVisitations.remove(invalidationPair);
return;
}
- // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps
- // should only be marked dirty (because only a dependency of theirs has changed).
+ // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps should
+ // only be marked dirty (because only a dependency of theirs has changed).
for (SkyKey reverseDep : entry.getReverseDeps()) {
visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST);
}
- // Remove this node as a reverse dep from its children, since we have reset it and
- // it no longer lists its children as direct deps.
- Map<SkyKey, ? extends ThinNodeEntry> children = graph.getBatch(deps);
- if (children.size() != Iterables.size(deps)) {
- Set<SkyKey> depsSet = ImmutableSet.copyOf(deps);
- throw new IllegalStateException(
- "Mismatch in getBatch: "
- + key
- + ", "
- + entry
- + "\n"
- + Sets.difference(depsSet, children.keySet())
- + "\n"
- + Sets.difference(children.keySet(), depsSet));
- }
- for (ThinNodeEntry child : children.values()) {
- child.removeReverseDep(key);
- }
-
informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY);
dirtyKeyTracker.dirty(key);
// Remove the node from the set as the last operation.
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
index 56f8997..9f45ad4 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -29,15 +29,17 @@
*/
public interface NodeEntry extends ThinNodeEntry {
/**
- * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}.
+ * Return code for {@link #addReverseDepAndCheckIfDone} and
+ * {@link #checkIfDoneForDirtyReverseDep}.
*/
enum DependencyState {
/** The node is done. */
DONE,
/**
- * The node was just created and needs to be scheduled for its first evaluation pass. The
- * evaluator is responsible for signaling the reverse dependency node.
+ * The node has not started evaluating, and needs to be scheduled for its first evaluation pass.
+ * The caller getting this return value is responsible for scheduling its evaluation and
+ * signaling the reverse dependency node when this node is done.
*/
NEEDS_SCHEDULING,
@@ -45,7 +47,7 @@
* The node was already created, but isn't done yet. The evaluator is responsible for
* signaling the reverse dependency node.
*/
- ADDED_DEP;
+ ALREADY_EVALUATING;
}
/**
@@ -63,9 +65,11 @@
*/
VERIFIED_CLEAN,
/**
- * A rebuilding is required or in progress, because either the node itself changed or one of
- * its dependencies did.
+ * A rebuilding is required, because either the node itself changed or one of its dependencies
+ * did.
*/
+ NEEDS_REBUILDING,
+ /** A rebuilding is in progress. */
REBUILDING
}
@@ -149,7 +153,17 @@
* if the node needs to be scheduled.
*/
@ThreadSafe
- DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep);
+ DependencyState addReverseDepAndCheckIfDone(@Nullable SkyKey reverseDep);
+
+ /**
+ * Similar to {@link #addReverseDepAndCheckIfDone}, except that {@param reverseDep} must already
+ * be a reverse dep of this entry. Should be used when reverseDep has been marked dirty and is
+ * checking its dependencies for changes. The caller must treat the return value just as they
+ * would the return value of {@link #addReverseDepAndCheckIfDone} by scheduling this node for
+ * evaluation if needed.
+ */
+ @ThreadSafe
+ DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep);
/**
* Tell this node that one of its dependencies is now done. Callers must check the return value,
@@ -169,7 +183,7 @@
* {@link #getVersion()}, then this entry records that one of its children has changed since it
* was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the
* child was last evaluated at {@code childVersion}. Thus, the next call to
- * {@link #getDirtyState()} will return {@link DirtyState#REBUILDING}.
+ * {@link #getDirtyState()} will return {@link DirtyState#NEEDS_REBUILDING}.
*/
@ThreadSafe
boolean signalDep(Version childVersion);
@@ -230,6 +244,37 @@
Collection<SkyKey> getNextDirtyDirectDeps();
/**
+ * Returns all deps of a node that has not yet finished evaluating. In other words, if a node has
+ * a reverse dep on this node, its key will be in the returned set here. If this node was freshly
+ * created, this is just any elements that were added using {@link #addTemporaryDirectDeps} (so it
+ * is the same as {@link #getTemporaryDirectDeps}). If this node is marked dirty, this includes
+ * all the elements that would have been returned by successive calls to
+ * {@link #getNextDirtyDirectDeps}.
+ *
+ * <p>This method should only be called when this node is about to be deleted after an aborted
+ * evaluation. After such an evaluation, any nodes that did not finish evaluating are deleted, as
+ * are any nodes that depend on them, which are necessarily also not done. If this node is to be
+ * deleted because of this, we must delete it as a reverse dep from other nodes. This method
+ * returns that list of other nodes. This method may not be called on done nodes, since they do
+ * not need to be deleted after aborted evaluations.
+ *
+ * <p>This method must not be called twice: the next thing done to this node after this method is
+ * called should be the removal of the node from the graph.
+ */
+ Iterable<SkyKey> getAllDirectDepsForIncompleteNode();
+
+ /**
+ * Notifies a node that it is about to be rebuilt. This method can only be called if the node
+ * {@link DirtyState#NEEDS_REBUILDING}. It returns the remaining deps of the node that had not
+ * yet been checked: all the keys that would be returned by successive calls to
+ * {@link #getNextDirtyDirectDeps}. It is the caller's responsibility to (uninterruptibly) remove
+ * the reverse deps those deps have on this node in order to keep the graph consistent. After this
+ * call, this node no longer has a dep on the nodes whose keys were returned by this call and
+ * is ready to be rebuilt (it will be in {@link DirtyState#REBUILDING}).
+ */
+ Collection<SkyKey> markRebuildingAndGetAllRemainingDirtyDirectDeps();
+
+ /**
* Returns the set of direct dependencies. This may only be called while the node is being
* evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
*/
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 12cc1dd..a2df93a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -40,6 +40,7 @@
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.Scheduler.SchedulerException;
import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
@@ -582,6 +583,32 @@
}
/**
+ * If the entry is dirty and not already rebuilding, puts it in a state that it can rebuild, and
+ * removes it as a reverse dep from any dirty direct deps it had yet to check.
+ */
+ private void maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(SkyKey key, NodeEntry entry) {
+ if (entry.isDirty() && entry.getDirtyState() != DirtyState.REBUILDING) {
+ Collection<SkyKey> depsToRemove = entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
+ Map<SkyKey, NodeEntry> depsToClearFrom = graph.getBatch(depsToRemove);
+ Preconditions.checkState(
+ depsToRemove.size() == depsToClearFrom.size(),
+ "%s %s: %s %s",
+ key,
+ entry,
+ depsToRemove,
+ depsToClearFrom);
+ for (NodeEntry depEntry : depsToClearFrom.values()) {
+ depEntry.removeReverseDep(key);
+ }
+ }
+ }
+
+ private enum DirtyOutcome {
+ ALREADY_PROCESSED,
+ NEEDS_EVALUATION
+ }
+
+ /**
* An action that evaluates a value.
*/
private class Evaluate implements Runnable {
@@ -594,20 +621,24 @@
this.skyKey = skyKey;
}
- private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child) {
+ private void enqueueChild(SkyKey skyKey, NodeEntry entry, SkyKey child, boolean dirtyParent) {
Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
NodeEntry depEntry = graph.createIfAbsent(child);
- switch (depEntry.addReverseDepAndCheckIfDone(skyKey)) {
- case DONE :
+ DependencyState dependencyState =
+ dirtyParent
+ ? depEntry.checkIfDoneForDirtyReverseDep(skyKey)
+ : depEntry.addReverseDepAndCheckIfDone(skyKey);
+ switch (dependencyState) {
+ case DONE:
if (entry.signalDep(depEntry.getVersion())) {
// This can only happen if there are no more children to be added.
visitor.enqueueEvaluation(skyKey);
}
break;
- case ADDED_DEP :
+ case ALREADY_EVALUATING:
break;
- case NEEDS_SCHEDULING :
+ case NEEDS_SCHEDULING:
visitor.enqueueEvaluation(child);
break;
}
@@ -623,97 +654,116 @@
&& !graph.get(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<SkyKey> 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(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<SkyKey, NodeEntry> entriesToCheck = graph.getBatch(directDepsToCheck);
+ for (Map.Entry<SkyKey, NodeEntry> 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<SkyKey, NodeEntry> 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.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
+ for (SkyKey directDep : directDepsToCheck) {
+ enqueueChild(skyKey, state, directDep, /*dirtyParent=*/ 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<SkyKey> 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, reverseDeps, state.getVersion());
+ return DirtyOutcome.ALREADY_PROCESSED;
+ case NEEDS_REBUILDING:
+ maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(skyKey, 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(skyKey), skyKey);
Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
-
- if (state.isDirty()) {
- 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.
- Collection<SkyKey> 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();
- break; // Fall through to re-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.
- for (Map.Entry<SkyKey, NodeEntry> entry :
- graph.getBatch(directDepsToCheck).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.
- if (!visitor.preventNewEvaluations()) {
- // An error was already thrown in the evaluator. Don't do anything here.
- return;
- }
- SkyKey errorKey = entry.getKey();
- NodeEntry errorEntry = entry.getValue();
- state.addTemporaryDirectDeps(
- GroupedListHelper.create(ImmutableList.of(errorKey)));
- DependencyState errorState = entry.getValue().addReverseDepAndCheckIfDone(skyKey);
- Preconditions.checkState(errorState == DependencyState.DONE, "%s %s %s %s",
- skyKey, state, errorKey, errorEntry);
- 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.addTemporaryDirectDeps(GroupedListHelper.create(directDepsToCheck));
- for (SkyKey directDep : directDepsToCheck) {
- enqueueChild(skyKey, state, directDep);
- }
- return;
- 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<SkyKey> 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;
- }
- throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
- }
- signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion());
- return;
- case REBUILDING:
- // Nothing to be done if we are already rebuilding.
- }
+ if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
+ return;
}
// TODO(bazel-team): Once deps are requested in a deterministic order within a group, or the
@@ -850,7 +900,7 @@
}
for (SkyKey newDirectDep : newDirectDeps) {
- enqueueChild(skyKey, state, newDirectDep);
+ enqueueChild(skyKey, state, newDirectDep, /*dirtyParent=*/ false);
}
// It is critical that there is no code below this point.
}
@@ -904,13 +954,13 @@
}
/**
- * If child is not done, removes key from child's reverse deps. Returns whether child should be
- * removed from key's entry's direct deps.
+ * 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 key, SkyKey child) {
+ private boolean removeIncompleteChild(SkyKey inProgressParent, SkyKey child) {
NodeEntry childEntry = graph.get(child);
if (!isDoneForBuild(childEntry)) {
- childEntry.removeReverseDep(key);
+ childEntry.removeInProgressReverseDep(inProgressParent);
return true;
}
return false;
@@ -1021,18 +1071,13 @@
// 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 = graph.createIfAbsent(ErrorTransienceValue.key());
- DependencyState triState = errorTransienceEntry.addReverseDepAndCheckIfDone(null);
- Preconditions.checkState(triState != DependencyState.ADDED_DEP,
- "%s %s", errorTransienceEntry, triState);
- if (triState != DependencyState.DONE) {
- errorTransienceEntry.setValue(new ErrorTransienceValue(), graphVersion);
- // The error transience entry is always invalidated by the RecordingDifferencer.
- // Now that the entry's value is set, it is no longer dirty.
- dirtyKeyTracker.notDirty(ErrorTransienceValue.key());
-
- Preconditions.checkState(
- errorTransienceEntry.addReverseDepAndCheckIfDone(null) != DependencyState.ADDED_DEP,
- errorTransienceEntry);
+ if (!errorTransienceEntry.isDone()) {
+ injectValue(
+ ErrorTransienceValue.key(),
+ new ErrorTransienceValue(),
+ graphVersion,
+ graph,
+ dirtyKeyTracker);
}
for (SkyKey skyKey : skyKeys) {
NodeEntry entry = graph.createIfAbsent(skyKey);
@@ -1044,7 +1089,7 @@
case DONE:
informProgressReceiverThatValueIsDone(skyKey);
break;
- case ADDED_DEP:
+ case ALREADY_EVALUATING:
break;
default:
throw new IllegalStateException(entry + " for " + skyKey + " in unknown state");
@@ -1135,7 +1180,7 @@
Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>();
boolean externalInterrupt = false;
while (true) {
- NodeEntry errorEntry = graph.get(errorKey);
+ NodeEntry errorEntry = Preconditions.checkNotNull(graph.get(errorKey), errorKey);
Iterable<SkyKey> reverseDeps = errorEntry.isDone()
? errorEntry.getReverseDeps()
: errorEntry.getInProgressReverseDeps();
@@ -1178,15 +1223,27 @@
bubbleParent, bubbleParentEntry, parentVersion, graphVersion);
continue;
}
- // Arbitrarily pick the first in-flight parent.
- Preconditions.checkState(visitor.isInflight(bubbleParent),
- "errorKey: %s, errorEntry: %s, bubbleParent: %s, bubbleParentEntry: %s", errorKey,
- errorEntry, bubbleParent, bubbleParentEntry);
- parent = bubbleParent;
- parentEntry = bubbleParentEntry;
+ if (visitor.isInflight(bubbleParent)
+ && bubbleParentEntry.getTemporaryDirectDeps().contains(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(parent, "%s %s", errorKey, bubbleErrorInfo);
errorKey = parent;
SkyFunction factory = skyFunctions.get(parent.functionName());
if (parentEntry.isDirty()) {
@@ -1195,9 +1252,11 @@
// 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 REBUILDING, since state is now REBUILDING.
+ // Fall through to NEEDS_REBUILDING, since state is now NEEDS_REBUILDING.
+ case NEEDS_REBUILDING:
+ maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(parent, parentEntry);
+ // Fall through to REBUILDING.
case REBUILDING:
- // Nothing to be done.
break;
default:
throw new AssertionError(parent + " not in valid dirty state: " + parentEntry);
@@ -1392,6 +1451,7 @@
} else if (!entry.isReady()) {
removeIncompleteChildrenForCycle(key, entry, entry.getTemporaryDirectDeps());
}
+ maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
Set<SkyKey> directDeps = entry.getTemporaryDirectDeps();
// Find out which children have errors. Similar logic to that in Evaluate#run().
List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(directDeps);
@@ -1425,6 +1485,7 @@
// 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();
+ maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
}
if (keepGoing) {
// Any children of this node that we haven't already visited are not worth visiting,
@@ -1560,6 +1621,7 @@
// that the entry can conceivably be ready if its cycleChild already found a different cycle
// and was built.
entry.signalDep();
+ maybeMarkRebuildingAndRemoveRemainingDirtyDirectDeps(key, entry);
}
Preconditions.checkState(entry.isReady(), "%s %s %s", key, cycleChild, entry);
Iterator<SkyKey> it = toVisit.iterator();
@@ -1645,4 +1707,39 @@
private boolean isDoneForBuild(@Nullable NodeEntry entry) {
return entry != null && entry.isDone();
}
+
+ static void injectValue(
+ SkyKey key,
+ SkyValue value,
+ Version version,
+ EvaluableGraph graph,
+ DirtyKeyTracker dirtyKeyTracker) {
+ Preconditions.checkNotNull(value, key);
+ NodeEntry prevEntry = graph.createIfAbsent(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);
+ // Put the node into a "rebuilding" state and verify that there were no dirty deps remaining.
+ Preconditions.checkState(
+ prevEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps().isEmpty(),
+ "%s %s",
+ key,
+ prevEntry);
+ }
+ prevEntry.setValue(value, version);
+ // Now that this key's injected value is set, it is no longer dirty.
+ dirtyKeyTracker.notDirty(key);
+ }
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
index 807aa8c..ed8d724 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -21,10 +21,14 @@
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
+import java.util.ArrayList;
import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
import java.util.Set;
+import javax.annotation.Nullable;
+
/**
* A utility class that allows us to keep the reverse dependencies as an array list instead of a
* set. This is more memory-efficient. At the same time it allows us to group the removals and
@@ -46,13 +50,126 @@
abstract void setSingleReverseDep(T container, boolean singleObject);
- abstract void setReverseDepsToRemove(T container, List<SkyKey> object);
+ abstract void setDataToConsolidate(T container, Object dataToConsolidate);
abstract Object getReverseDepsObject(T container);
abstract boolean isSingleReverseDep(T container);
- abstract List<SkyKey> getReverseDepsToRemove(T container);
+ abstract Object getDataToConsolidate(T container);
+
+ private enum DataState {
+ NULL,
+ CHECK_ONLY,
+ BOTH
+ }
+
+ private static class RDepsToCheckAndRemove {
+ // reverseDepstoCheck may be null, but not toRemove, because we store a bare list if
+ // we have only toCheck.
+ @Nullable List<SkyKey> toCheck;
+ List<SkyKey> toRemove;
+
+ RDepsToCheckAndRemove(List<SkyKey> toCheck, List<SkyKey> toRemove) {
+ this.toCheck = toCheck;
+ this.toRemove = Preconditions.checkNotNull(toRemove);
+ }
+
+ static RDepsToCheckAndRemove justRemove(List<SkyKey> toRemove) {
+ return new RDepsToCheckAndRemove(null, toRemove);
+ }
+
+ static RDepsToCheckAndRemove replaceRemove(
+ RDepsToCheckAndRemove original, List<SkyKey> toRemove) {
+ return new RDepsToCheckAndRemove(original.toCheck, toRemove);
+ }
+
+ static RDepsToCheckAndRemove replaceCheck(
+ RDepsToCheckAndRemove original, List<SkyKey> toCheck) {
+ return new RDepsToCheckAndRemove(toCheck, original.toRemove);
+ }
+ }
+
+ private static DataState getDataState(Object reverseDepsToCheckAndRemove) {
+ if (reverseDepsToCheckAndRemove == null) {
+ return DataState.NULL;
+ } else if (reverseDepsToCheckAndRemove instanceof List) {
+ return DataState.CHECK_ONLY;
+ } else {
+ Preconditions.checkState(
+ reverseDepsToCheckAndRemove instanceof RDepsToCheckAndRemove,
+ reverseDepsToCheckAndRemove);
+ return DataState.BOTH;
+ }
+ }
+
+ private void setReverseDepsToRemove(T container, List<SkyKey> toRemove) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ reverseDepsToCheckAndRemove = RDepsToCheckAndRemove.justRemove(toRemove);
+ break;
+ case CHECK_ONLY:
+ reverseDepsToCheckAndRemove =
+ new RDepsToCheckAndRemove(((List<SkyKey>) reverseDepsToCheckAndRemove), toRemove);
+ break;
+ case BOTH:
+ reverseDepsToCheckAndRemove =
+ RDepsToCheckAndRemove.replaceRemove(
+ (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toRemove);
+ break;
+ default:
+ throw new IllegalStateException(container + ", " + toRemove);
+ }
+ setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+ }
+
+ private void setReverseDepsToCheck(T container, List<SkyKey> toCheck) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ case CHECK_ONLY:
+ reverseDepsToCheckAndRemove = toCheck;
+ break;
+ case BOTH:
+ reverseDepsToCheckAndRemove =
+ RDepsToCheckAndRemove.replaceCheck(
+ (RDepsToCheckAndRemove) reverseDepsToCheckAndRemove, toCheck);
+ break;
+ default:
+ throw new IllegalStateException(container + ", " + toCheck);
+ }
+ setDataToConsolidate(container, reverseDepsToCheckAndRemove);
+ }
+
+ @Nullable
+ private List<SkyKey> getReverseDepsToRemove(T container) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ case CHECK_ONLY:
+ return null;
+ case BOTH:
+ return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toRemove;
+ default:
+ throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+ }
+ }
+
+ @Nullable
+ private List<SkyKey> getReverseDepsToCheck(T container) {
+ Object reverseDepsToCheckAndRemove = getDataToConsolidate(container);
+ switch (getDataState(reverseDepsToCheckAndRemove)) {
+ case NULL:
+ return null;
+ case CHECK_ONLY:
+ return (List<SkyKey>) reverseDepsToCheckAndRemove;
+ case BOTH:
+ return ((RDepsToCheckAndRemove) reverseDepsToCheckAndRemove).toCheck;
+ default:
+ throw new IllegalStateException(reverseDepsToCheckAndRemove.toString());
+ }
+ }
/**
* We check that the reverse dependency is not already present. We only do that if reverseDeps is
@@ -60,15 +177,22 @@
*/
void maybeCheckReverseDepNotPresent(T container, SkyKey reverseDep) {
if (isSingleReverseDep(container)) {
- Preconditions.checkState(!getReverseDepsObject(container).equals(reverseDep),
- "Reverse dep %s already present", reverseDep);
+ Preconditions.checkState(
+ !getReverseDepsObject(container).equals(reverseDep),
+ "Reverse dep %s already present in %s",
+ reverseDep,
+ container);
return;
}
@SuppressWarnings("unchecked")
List<SkyKey> asList = (List<SkyKey>) getReverseDepsObject(container);
if (asList.size() < MAYBE_CHECK_THRESHOLD) {
- Preconditions.checkState(!asList.contains(reverseDep), "Reverse dep %s already present"
- + " in %s", reverseDep, asList);
+ Preconditions.checkState(
+ !asList.contains(reverseDep),
+ "Reverse dep %s already present in %s for %s",
+ reverseDep,
+ asList,
+ container);
}
}
@@ -106,9 +230,29 @@
}
}
- boolean reverseDepsIsEmpty(T container) {
- return !isSingleReverseDep(container)
- && ((List<SkyKey>) getReverseDepsObject(container)).isEmpty();
+ void checkReverseDep(T container, SkyKey reverseDep) {
+ Object reverseDepsObject = getReverseDepsObject(container);
+ if (isSingleReverseDep(container)) {
+ Preconditions.checkState(
+ reverseDepsObject.equals(reverseDep),
+ "%s %s %s",
+ reverseDep,
+ reverseDepsObject,
+ container);
+ return;
+ }
+ List<SkyKey> asList = (List<SkyKey>) reverseDepsObject;
+ if (asList.size() < MAYBE_CHECK_THRESHOLD) {
+ Preconditions.checkState(
+ asList.contains(reverseDep), "%s not in %s for %s", reverseDep, asList, container);
+ } else {
+ List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+ if (reverseDepsToCheck == null) {
+ reverseDepsToCheck = new ArrayList<>();
+ setReverseDepsToCheck(container, reverseDepsToCheck);
+ }
+ reverseDepsToCheck.add(reverseDep);
+ }
}
/**
@@ -122,7 +266,7 @@
"toRemove: %s container: %s",
reverseDep,
container);
- overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
+ overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
return;
}
@SuppressWarnings("unchecked")
@@ -138,7 +282,7 @@
}
ImmutableSet<SkyKey> getReverseDeps(T container) {
- consolidateReverseDepsRemovals(container);
+ consolidateData(container);
// TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
// wrt. thread-safety. The parents of a node get modified when any of the parents is deleted,
@@ -155,19 +299,38 @@
}
}
- void consolidateReverseDepsRemovals(T container) {
- List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+ void consolidateData(T container) {
Object reverseDeps = getReverseDepsObject(container);
- if (reverseDepsToRemove == null) {
+ List<SkyKey> reverseDepsToRemove = getReverseDepsToRemove(container);
+ List<SkyKey> reverseDepsToCheck = getReverseDepsToCheck(container);
+ if (reverseDepsToRemove == null && reverseDepsToCheck == null) {
return;
}
- Preconditions.checkState(!isSingleReverseDep(container),
- "We do not use reverseDepsToRemove for single lists: %s", container);
- // Should not happen, as we only create reverseDepsToRemove in case we have at least one
- // reverse dep to remove.
- Preconditions.checkState((!((List<?>) reverseDeps).isEmpty()),
- "Could not remove %s elements from %s.\nReverse deps to remove: %s. %s",
- reverseDepsToRemove.size(), reverseDeps, reverseDepsToRemove, container);
+ Preconditions.checkState(
+ !isSingleReverseDep(container),
+ "We do not delay removals/checks for single lists: %s %s %s",
+ container,
+ reverseDepsToRemove,
+ reverseDepsToCheck);
+ @SuppressWarnings("unchecked")
+ List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ // Should not happen, as we only create reverseDepsToRemove/Check in case we have at least one
+ // reverse dep to remove/check.
+ Preconditions.checkState(
+ !reverseDepsAsList.isEmpty(),
+ "Could not do delayed removal/check for %s elements from %s.\n"
+ + "Reverse deps to check: %s. Container: %s",
+ reverseDepsToRemove,
+ reverseDeps,
+ reverseDepsToCheck,
+ container);
+ if (reverseDepsToRemove == null) {
+ Set<SkyKey> reverseDepsAsSet = new HashSet<>(reverseDepsAsList);
+ Preconditions.checkState(
+ reverseDepsAsSet.containsAll(reverseDepsToCheck), "%s %s", reverseDepsToCheck, container);
+ setDataToConsolidate(container, null);
+ return;
+ }
Set<SkyKey> toRemove = Sets.newHashSet(reverseDepsToRemove);
int expectedRemovals = toRemove.size();
@@ -175,12 +338,13 @@
"A reverse dependency tried to remove itself twice: %s. %s", reverseDepsToRemove,
container);
- @SuppressWarnings("unchecked")
- List<SkyKey> reverseDepsAsList = (List<SkyKey>) reverseDeps;
+ Set<SkyKey> toCheck =
+ reverseDepsToCheck == null ? new HashSet<SkyKey>() : new HashSet<>(reverseDepsToCheck);
List<SkyKey> newReverseDeps = Lists
.newArrayListWithExpectedSize(Math.max(0, reverseDepsAsList.size() - expectedRemovals));
for (SkyKey reverseDep : reverseDepsAsList) {
+ toCheck.remove(reverseDep);
if (!toRemove.contains(reverseDep)) {
newReverseDeps.add(reverseDep);
}
@@ -188,6 +352,7 @@
Preconditions.checkState(newReverseDeps.size() == reverseDepsAsList.size() - expectedRemovals,
"Could not remove some elements from %s.\nReverse deps to remove: %s. %s", reverseDeps,
toRemove, container);
+ Preconditions.checkState(toCheck.isEmpty(), "%s %s", toCheck, container);
if (newReverseDeps.isEmpty()) {
overwriteReverseDepsList(container, ImmutableList.<SkyKey>of());
@@ -196,14 +361,14 @@
} else {
overwriteReverseDepsList(container, newReverseDeps);
}
- setReverseDepsToRemove(container, null);
+ setDataToConsolidate(container, null);
}
String toString(T container) {
return MoreObjects.toStringHelper("ReverseDeps")
.add("reverseDeps", getReverseDepsObject(container))
.add("singleReverseDep", isSingleReverseDep(container))
- .add("reverseDepsToRemove", getReverseDepsToRemove(container))
+ .add("dataToConsolidate", getDataToConsolidate(container))
.toString();
}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
index 661b521..8cd16f0 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -49,6 +49,15 @@
void removeReverseDep(SkyKey reverseDep);
/**
+ * Removes a reverse dependency.
+ *
+ * <p>May only be called if this entry is not done (i.e. {@link #isDone} is false) and
+ * {@param reverseDep} is present in {@link #getReverseDeps}
+ */
+ @ThreadSafe
+ void removeInProgressReverseDep(SkyKey reverseDep);
+
+ /**
* Returns a copy of the set of reverse dependencies. Note that this introduces a potential
* check-then-act race; {@link #removeReverseDep} may fail for a key that is returned here.
*/
@@ -80,11 +89,11 @@
* the caller will only ever want to call {@code markDirty()} a second time if a transition from a
* dirty-unchanged state to a dirty-changed state is required.
*
- * @return The direct deps of this entry, or null if the entry has already been marked
- * dirty. In the latter case, the caller should abort its handling of this node, since another
- * thread is already dealing with it.
+ * @return true if the node was previously clean, and false if it was already dirty. If it was
+ * already dirty, the caller should abort its handling of this node, since another thread is
+ * already dealing with it.
*/
@Nullable
@ThreadSafe
- Iterable<SkyKey> markDirty(boolean isChanged);
+ boolean markDirty(boolean isChanged);
}
