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);
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
index 2c4e861..b8c46b6 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
@@ -13,6 +13,7 @@
// limitations under the License.
package com.google.devtools.build.skyframe;
+import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.devtools.build.lib.util.GroupedList;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
@@ -69,7 +70,7 @@
@Override
public synchronized Collection<SkyKey> getReverseDeps() {
TreeSet<SkyKey> result = new TreeSet<>(ALPHABETICAL_SKYKEY_COMPARATOR);
- result.addAll(super.getReverseDeps());
+ Iterables.addAll(result, super.getReverseDeps());
return result;
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 623e088..5b5790f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -126,6 +126,10 @@
throw new UnsupportedOperationException("Sublcasses must override");
}
+ protected boolean reverseDepsPresent() {
+ throw new UnsupportedOperationException("Subclasses must override");
+ }
+
// Convenience method for eval-ing a single value.
protected SkyValue eval(boolean keepGoing, SkyKey key) throws InterruptedException {
SkyKey[] keys = { key };
@@ -349,10 +353,20 @@
assertTrue(isInvalidated(skyKey("ab")));
assertTrue(isInvalidated(skyKey("abc")));
- // The reverse deps to ab and ab_c should have been removed.
- assertThat(graph.get(skyKey("a")).getReverseDeps()).isEmpty();
- assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactly(skyKey("bc"));
- assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactly(skyKey("bc"));
+ // The reverse deps to ab and ab_c should have been removed if reverse deps are cleared.
+ Set<SkyKey> reverseDeps = new HashSet<>();
+ if (reverseDepsPresent()) {
+ reverseDeps.add(skyKey("ab"));
+ }
+ assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+ reverseDeps.add(skyKey("bc"));
+ assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+ reverseDeps.clear();
+ if (reverseDepsPresent()) {
+ reverseDeps.add(skyKey("ab_c"));
+ }
+ reverseDeps.add(skyKey("bc"));
+ assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
}
@Test
@@ -612,6 +626,11 @@
return InvalidationType.DELETED;
}
+ @Override
+ protected boolean reverseDepsPresent() {
+ return false;
+ }
+
@Test
public void dirtyKeyTrackerWorksWithDeletingInvalidator() throws Exception {
setupInvalidatableGraph();
@@ -628,7 +647,7 @@
Iterable<SkyKey> diff = ImmutableList.of(skyKey("a"));
Preconditions.checkNotNull(EagerInvalidator.createDeletingVisitorIfNeeded(graph, diff,
receiver, state, true, dirtyKeyTracker)).run();
- assertThat(dirtyKeyTracker.getDirtyKeys()).containsExactly(skyKey("ab"));
+ assertThat(dirtyKeyTracker.getDirtyKeys()).isEmpty();
}
}
@@ -670,6 +689,11 @@
return InvalidationType.CHANGED;
}
+ @Override
+ protected boolean reverseDepsPresent() {
+ return true;
+ }
+
@Test
public void dirtyKeyTrackerWorksWithDirtyingInvalidator() throws Exception {
setupInvalidatableGraph();
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
index cf28aa8..9ad0159 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -43,6 +43,7 @@
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
/** Base class for concurrency sanity tests on {@link EvaluableGraph} implementations. */
public abstract class GraphConcurrencyTest {
@@ -85,58 +86,59 @@
final NodeEntry entry = graph.createIfAbsent(key);
// These numbers are arbitrary.
int numThreads = 50;
- int numKeys = 100;
+ int numKeys = numThreads;
// One chunk will be used to add and remove rdeps before setting the node value. The second
// chunk of work will have the node value set and the last chunk will be to add and remove
// rdeps after the value has been set.
final int chunkSize = 40;
- final int numIterations = chunkSize * 3;
+ final int numIterations = chunkSize * 2;
// This latch is used to signal that the runnables have been submitted to the executor.
- final CountDownLatch countDownLatch1 = new CountDownLatch(1);
+ final CountDownLatch waitForStart = new CountDownLatch(1);
// This latch is used to signal to the main thread that we have begun the second chunk
// for sufficiently many keys. The minimum of numThreads and numKeys is used to prevent
// thread starvation from causing a delay here.
- final CountDownLatch countDownLatch2 = new CountDownLatch(Math.min(numThreads, numKeys));
+ final CountDownLatch waitForAddedRdep = new CountDownLatch(numThreads);
// This latch is used to guarantee that we set the node's value before we enter the third
// chunk for any key.
- final CountDownLatch countDownLatch3 = new CountDownLatch(1);
+ final CountDownLatch waitForSetValue = new CountDownLatch(1);
ExecutorService pool = Executors.newFixedThreadPool(numThreads);
// Add single rdep before transition to done.
assertEquals(DependencyState.NEEDS_SCHEDULING, entry.addReverseDepAndCheckIfDone(key("rdep")));
for (int i = 0; i < numKeys; i++) {
final int j = i;
- Runnable r = new Runnable() {
- @Override
- public void run() {
- try {
- countDownLatch1.await();
- // Add and remove the rdep a bunch of times to test interleaving.
- for (int k = 1; k <= numIterations; k++) {
- if (k == chunkSize) {
- countDownLatch2.countDown();
+ Runnable r =
+ new Runnable() {
+ @Override
+ public void run() {
+ try {
+ // Add and remove the rdep a bunch of times to test interleaving.
+ waitForStart.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+ for (int k = 1; k < chunkSize; k++) {
+ assertThat(entry.addReverseDepAndCheckIfDone(key("rdep" + j)))
+ .isNotEqualTo(DependencyState.DONE);
+ entry.removeInProgressReverseDep(key("rdep" + j));
+ assertThat(entry.getInProgressReverseDeps()).doesNotContain(key("rdep" + j));
+ }
+ assertThat(entry.addReverseDepAndCheckIfDone(key("rdep" + j)))
+ .isNotEqualTo(DependencyState.DONE);
+ waitForAddedRdep.countDown();
+ waitForSetValue.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+ } catch (InterruptedException e) {
+ fail("Test failed: " + e.toString());
}
- entry.addReverseDepAndCheckIfDone(key("rdep" + j));
- entry.removeReverseDep(key("rdep" + j));
- if (k == chunkSize * 2) {
- countDownLatch3.await();
+ for (int k = chunkSize; k <= numIterations; k++) {
+ entry.removeReverseDep(key("rdep" + j));
+ entry.addReverseDepAndCheckIfDone(key("rdep" + j));
+ entry.getReverseDeps();
}
}
- entry.addReverseDepAndCheckIfDone(key("rdep" + j));
- } catch (InterruptedException e) {
- fail("Test failed: " + e.toString());
- }
- }
- };
+ };
pool.execute(wrapper.wrap(r));
}
- countDownLatch1.countDown();
- try {
- countDownLatch2.await();
- } catch (InterruptedException e) {
- fail("Test failed: " + e.toString());
- }
+ waitForStart.countDown();
+ waitForAddedRdep.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
entry.setValue(new StringValue("foo1"), startingVersion);
- countDownLatch3.countDown();
+ waitForSetValue.countDown();
entry.removeReverseDep(key("rdep"));
wrapper.waitForTasksAndMaybeThrow();
assertFalse(ExecutorUtil.interruptibleShutdown(pool));
@@ -148,6 +150,7 @@
// Mark the node as dirty again and check that the reverse deps have been preserved.
sameEntry.markDirty(true);
startEvaluation(sameEntry);
+ sameEntry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
sameEntry.setValue(new StringValue("foo2"), startingVersion.next());
assertEquals(new StringValue("foo2"), graph.get(key).getValue());
assertEquals(numKeys, Iterables.size(graph.get(key).getReverseDeps()));
@@ -253,6 +256,7 @@
entry.markDirty(true);
// Make some changes, like adding a dep and rdep.
entry.addReverseDepAndCheckIfDone(key("rdep"));
+ entry.markRebuildingAndGetAllRemainingDirtyDirectDeps();
addTemporaryDirectDep(entry, key("dep"));
entry.signalDep();
// Move node from dirty back to done.
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 1976766..b598bf8 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -98,8 +98,8 @@
SkyKey mother = key("mother");
SkyKey father = key("father");
assertEquals(DependencyState.NEEDS_SCHEDULING, entry.addReverseDepAndCheckIfDone(mother));
- assertEquals(DependencyState.ADDED_DEP, entry.addReverseDepAndCheckIfDone(null));
- assertEquals(DependencyState.ADDED_DEP, entry.addReverseDepAndCheckIfDone(father));
+ assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(null));
+ assertEquals(DependencyState.ALREADY_EVALUATING, entry.addReverseDepAndCheckIfDone(father));
assertThat(setValue(entry, new SkyValue() {},
/*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father);
assertThat(entry.getReverseDeps()).containsExactly(mother, father);
@@ -197,6 +197,7 @@
entry.signalDep();
assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
assertTrue(entry.isReady());
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
/*graphVersion=*/1L)).containsExactly(parent);
}
@@ -218,9 +219,10 @@
assertTrue(entry.isReady());
SkyKey parent = key("parent");
entry.addReverseDepAndCheckIfDone(parent);
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
assertTrue(entry.isReady());
assertThat(entry.getTemporaryDirectDeps()).isEmpty();
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).containsExactly(dep);
assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
/*graphVersion=*/1L)).containsExactly(parent);
assertEquals(new IntVersion(1L), entry.getVersion());
@@ -409,8 +411,9 @@
assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
addTemporaryDirectDep(entry, dep);
entry.signalDep(new IntVersion(1L));
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
assertTrue(entry.isDone());
assertEquals(new IntVersion(0L), entry.getVersion());
@@ -438,11 +441,12 @@
assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
addTemporaryDirectDep(entry, dep);
entry.signalDep(new IntVersion(1L));
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
key("cause"));
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
setValue(entry, new IntegerValue(5), new ErrorInfo(exception),
/*graphVersion=*/1L);
assertTrue(entry.isDone());
@@ -467,8 +471,9 @@
assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
addTemporaryDirectDep(entry, dep);
entry.signalDep(new IntVersion(1L));
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
setValue(entry, /*value=*/null, errorInfo, /*graphVersion=*/1L);
assertTrue(entry.isDone());
assertEquals(new IntVersion(0L), entry.getVersion());
@@ -542,8 +547,9 @@
assertThat(entry.getNextDirtyDirectDeps()).containsExactly(dep).inOrder();
addTemporaryDirectDep(entry, dep);
assertTrue(entry.signalDep(new IntVersion(1L)));
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
assertThat(entry.getTemporaryDirectDeps()).containsExactly(dep);
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
addTemporaryDirectDep(entry, key("dep2"));
assertTrue(entry.signalDep(new IntVersion(1L)));
setValue(entry, new IntegerValue(5), /*errorInfo=*/null, /*graphVersion=*/1L);
@@ -586,7 +592,8 @@
entry.markDirty(/*isChanged=*/true);
SkyKey newParent = key("new parent");
entry.addReverseDepAndCheckIfDone(newParent);
- assertEquals(NodeEntry.DirtyState.REBUILDING, entry.getDirtyState());
+ assertEquals(NodeEntry.DirtyState.NEEDS_REBUILDING, entry.getDirtyState());
+ assertThat(entry.markRebuildingAndGetAllRemainingDirtyDirectDeps()).isEmpty();
assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
/*graphVersion=*/1L)).containsExactly(newParent);
}
@@ -612,6 +619,8 @@
SkyKey newChild = key("newchild");
addTemporaryDirectDep(clone2, newChild);
clone2.signalDep();
+ assertThat(clone2.markRebuildingAndGetAllRemainingDirtyDirectDeps())
+ .containsExactly(originalChild);
clone2.setValue(updatedValue, version.next());
assertThat(entry.getVersion()).isEqualTo(version);
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index ffb5bf8..348f5c0 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -840,6 +840,43 @@
assertThat(cycleInfo.getPathToCycle()).containsExactly(cycleKey2).inOrder();
}
+ @Test
+ public void cycleAndSelfEdgeWithDirtyValueInSameGroup() throws Exception {
+ setGraphForTesting(new DeterministicInMemoryGraph());
+ final SkyKey cycleKey1 = GraphTester.toSkyKey("zcycleKey1");
+ final SkyKey cycleKey2 = GraphTester.toSkyKey("acycleKey2");
+ tester.getOrCreate(cycleKey2).addDependency(cycleKey2).setComputedValue(CONCATENATE);
+ tester
+ .getOrCreate(cycleKey1)
+ .setBuilder(
+ new SkyFunction() {
+ @Nullable
+ @Override
+ public SkyValue compute(SkyKey skyKey, Environment env)
+ throws SkyFunctionException, InterruptedException {
+ Map<SkyKey, SkyValue> result =
+ env.getValues(ImmutableList.of(cycleKey1, cycleKey2));
+ Preconditions.checkState(env.valuesMissing(), result);
+ return null;
+ }
+
+ @Nullable
+ @Override
+ public String extractTag(SkyKey skyKey) {
+ return null;
+ }
+ });
+ // Evaluate twice to make sure nothing strange happens with invalidation the second time.
+ for (int i = 0; i < 2; i++) {
+ EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ true, cycleKey1);
+ assertEquals(null, result.get(cycleKey1));
+ ErrorInfo errorInfo = result.getError(cycleKey1);
+ CycleInfo cycleInfo = Iterables.getOnlyElement(errorInfo.getCycleInfo());
+ assertThat(cycleInfo.getCycle()).containsExactly(cycleKey1).inOrder();
+ assertThat(cycleInfo.getPathToCycle()).isEmpty();
+ }
+ }
+
/** Regression test: "crash in cycle checker with dirty values". */
@Test
public void cycleWithDirtyValue() throws Exception {
@@ -1587,6 +1624,70 @@
}
@Test
+ public void removeReverseDepFromRebuildingNode() throws Exception {
+ SkyKey topKey = GraphTester.skyKey("top");
+ final SkyKey midKey = GraphTester.skyKey("mid");
+ final SkyKey changedKey = GraphTester.skyKey("changed");
+ tester.getOrCreate(changedKey).setConstantValue(new StringValue("first"));
+ // When top depends on mid,
+ tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
+ // And mid depends on changed,
+ tester.getOrCreate(midKey).addDependency(changedKey).setComputedValue(CONCATENATE);
+ final CountDownLatch changedKeyStarted = new CountDownLatch(1);
+ final CountDownLatch changedKeyCanFinish = new CountDownLatch(1);
+ final AtomicBoolean controlTiming = new AtomicBoolean(false);
+ setGraphForTesting(
+ new NotifyingInMemoryGraph(
+ new Listener() {
+ @Override
+ public void accept(SkyKey key, EventType type, Order order, Object context) {
+ if (!controlTiming.get()) {
+ return;
+ }
+ if (key.equals(midKey)
+ && type == EventType.CHECK_IF_DONE
+ && order == Order.BEFORE) {
+ TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
+ changedKeyStarted, "changed key didn't start");
+ } else if (key.equals(changedKey)
+ && type == EventType.REMOVE_REVERSE_DEP
+ && order == Order.AFTER
+ && midKey.equals(context)) {
+ changedKeyCanFinish.countDown();
+ }
+ }
+ }));
+ // Then top builds as expected.
+ assertThat(tester.evalAndGet(/*keepGoing=*/ false, topKey)).isEqualTo(new StringValue("first"));
+ // When changed is modified,
+ tester
+ .getOrCreate(changedKey, /*markAsModified=*/ true)
+ .setConstantValue(null)
+ .setBuilder(
+ // And changed is not allowed to finish building until it is released,
+ new ChainedFunction(
+ changedKeyStarted,
+ changedKeyCanFinish,
+ null,
+ false,
+ new StringValue("second"),
+ ImmutableList.<SkyKey>of()));
+ // And mid is independently marked as modified,
+ tester.getOrCreate(midKey, /*markAsModified=*/ true);
+ tester.invalidate();
+ SkyKey newTopKey = GraphTester.skyKey("newTop");
+ // And changed will start rebuilding independently of midKey, because it's requested directly by
+ // newTop
+ tester.getOrCreate(newTopKey).addDependency(changedKey).setComputedValue(CONCATENATE);
+ // And we control the timing using the graph listener above to make sure that:
+ // (1) before we do anything with mid, changed has already started, and
+ // (2) changed key can't finish until mid tries to remove its reverse dep from changed,
+ controlTiming.set(true);
+ // Then this evaluation completes without crashing.
+ tester.eval(/*keepGoing=*/ false, newTopKey, topKey);
+ }
+
+ @Test
public void dirtyThenDeleted() throws Exception {
initializeTester();
SkyKey topKey = GraphTester.skyKey("top");
@@ -1616,15 +1717,24 @@
// leaf4 should not built in the second build.
final SkyKey leaf4 = GraphTester.toSkyKey("leaf4");
final AtomicBoolean shouldNotBuildLeaf4 = new AtomicBoolean(false);
- setGraphForTesting(new NotifyingInMemoryGraph(new Listener() {
- @Override
- public void accept(SkyKey key, EventType type, Order order, Object context) {
- if (shouldNotBuildLeaf4.get() && key.equals(leaf4)) {
- throw new IllegalStateException("leaf4 should not have been considered this build: "
- + type + ", " + order + ", " + context);
- }
- }
- }));
+ setGraphForTesting(
+ new NotifyingInMemoryGraph(
+ new Listener() {
+ @Override
+ public void accept(SkyKey key, EventType type, Order order, Object context) {
+ if (shouldNotBuildLeaf4.get()
+ && key.equals(leaf4)
+ && type != EventType.REMOVE_REVERSE_DEP) {
+ throw new IllegalStateException(
+ "leaf4 should not have been considered this build: "
+ + type
+ + ", "
+ + order
+ + ", "
+ + context);
+ }
+ }
+ }));
tester.set(leaf4, new StringValue("leaf4"));
// Create leaf0, leaf1 and leaf2 values with values "leaf2", "leaf3", "leaf4" respectively.
@@ -2548,10 +2658,10 @@
tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
tester.getOrCreate(midKey).addDependency(badKey).setComputedValue(CONCATENATE);
tester.getOrCreate(badKey).setHasError(true);
- EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/false, topKey, midKey);
+ EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ false, topKey, midKey);
assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
// Do it again with keepGoing. We should also see an error for the top key this time.
- result = tester.eval(/*keepGoing=*/true, topKey, midKey);
+ result = tester.eval(/*keepGoing=*/ true, topKey, midKey);
assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
assertThat(result.getError(topKey).getRootCauses()).containsExactly(badKey);
}
@@ -2566,13 +2676,13 @@
.addErrorDependency(errorKey, new StringValue("recovered"))
.setComputedValue(CONCATENATE);
// When the error value throws, the propagation will cause an interrupted exception in parent.
- EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, parentKey);
+ EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/ false, parentKey);
assertThat(result.keyNames()).isEmpty();
Map.Entry<SkyKey, ErrorInfo> error = Iterables.getOnlyElement(result.errorMap().entrySet());
assertEquals(parentKey, error.getKey());
assertThat(error.getValue().getRootCauses()).containsExactly(errorKey);
assertFalse(Thread.interrupted());
- result = tester.eval(/*keepGoing=*/true, parentKey);
+ result = tester.eval(/*keepGoing=*/ true, parentKey);
assertThat(result.errorMap()).isEmpty();
assertEquals("recovered", result.get(parentKey).getValue());
}
@@ -2624,10 +2734,10 @@
tester.getOrCreate(topKey).addDependency(midKey).setComputedValue(CONCATENATE);
tester.getOrCreate(midKey).addDependency(badKey).setComputedValue(CONCATENATE);
tester.getOrCreate(badKey).setHasError(true);
- EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/false, topKey, midKey);
+ EvaluationResult<SkyValue> result = tester.eval(/*keepGoing=*/ false, topKey, midKey);
assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
waitForSecondCall.set(true);
- result = tester.eval(/*keepGoing=*/true, topKey, midKey);
+ result = tester.eval(/*keepGoing=*/ true, topKey, midKey);
assertNotNull(firstThread.get());
assertEquals(0, otherThreadWinning.getCount());
assertThat(result.getError(midKey).getRootCauses()).containsExactly(badKey);
@@ -2645,12 +2755,12 @@
.addErrorDependency(errorKey, new StringValue("recovered"))
.setComputedValue(CONCATENATE)
.addDependency("after");
- EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, parentKey);
+ EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/ false, parentKey);
assertThat(result.keyNames()).isEmpty();
Map.Entry<SkyKey, ErrorInfo> error = Iterables.getOnlyElement(result.errorMap().entrySet());
assertEquals(parentKey, error.getKey());
assertThat(error.getValue().getRootCauses()).containsExactly(errorKey);
- result = tester.eval(/*keepGoing=*/true, parentKey);
+ result = tester.eval(/*keepGoing=*/ true, parentKey);
assertThat(result.errorMap()).isEmpty();
assertEquals("recoveredafter", result.get(parentKey).getValue());
}
@@ -2741,7 +2851,7 @@
// When the graph is evaluated in noKeepGoing mode,
EvaluationResult<StringValue> result =
- tester.eval(/*keepGoing=*/false, errorKey, otherErrorKey);
+ tester.eval(/*keepGoing=*/ false, errorKey, otherErrorKey);
// Then the result reports that an error occurred because of errorKey,
assertTrue(result.hasError());
@@ -3398,6 +3508,68 @@
}
}
+ @Test
+ public void cleanReverseDepFromDirtyNodeNotInBuild() throws Exception {
+ final SkyKey topKey = GraphTester.skyKey("top");
+ SkyKey inactiveKey = GraphTester.skyKey("inactive");
+ final Thread mainThread = Thread.currentThread();
+ final AtomicBoolean shouldInterrupt = new AtomicBoolean(false);
+ NotifyingInMemoryGraph graph =
+ new NotifyingInMemoryGraph(
+ new Listener() {
+ @Override
+ public void accept(SkyKey key, EventType type, Order order, Object context) {
+ if (shouldInterrupt.get()
+ && key.equals(topKey)
+ && type == EventType.IS_READY
+ && order == Order.BEFORE) {
+ mainThread.interrupt();
+ shouldInterrupt.set(false);
+ try {
+ // Make sure threadpool propagates interrupt.
+ Thread.sleep(TestUtils.WAIT_TIMEOUT_MILLISECONDS);
+ } catch (InterruptedException e) {
+ Thread.currentThread().interrupt();
+ }
+ }
+ }
+ });
+ setGraphForTesting(graph);
+ // When top depends on inactive,
+ tester.getOrCreate(topKey).addDependency(inactiveKey).setComputedValue(COPY);
+ StringValue val = new StringValue("inactive");
+ // And inactive is constant,
+ tester.set(inactiveKey, val);
+ // Then top evaluates normally.
+ assertThat(tester.evalAndGet(/*keepGoing=*/ true, topKey)).isEqualTo(val);
+ // When evaluation will be interrupted as soon as top starts evaluating,
+ shouldInterrupt.set(true);
+ // And inactive is dirty,
+ tester.getOrCreate(inactiveKey, /*markAsModified=*/ true);
+ // And so is top,
+ tester.getOrCreate(topKey, /*markAsModified=*/ true);
+ tester.invalidate();
+ try {
+ // Then evaluation is interrupted,
+ tester.eval(/*keepGoing=*/ false, topKey);
+ fail();
+ } catch (InterruptedException e) {
+ // Expected.
+ }
+ // But inactive is still present,
+ assertThat(graph.get(inactiveKey)).isNotNull();
+ // And still dirty,
+ assertThat(graph.get(inactiveKey).isDirty()).isTrue();
+ // And re-evaluates successfully,
+ assertThat(tester.evalAndGet(/*keepGoing=*/ true, inactiveKey)).isEqualTo(val);
+ // But top is gone from the graph,
+ assertThat(graph.get(topKey)).isNull();
+ // And we can successfully invalidate and re-evaluate inactive again.
+ tester.getOrCreate(inactiveKey, /*markAsModified=*/ true);
+ tester.invalidate();
+ assertThat(tester.evalAndGet(/*keepGoing=*/ true, inactiveKey)).isEqualTo(val);
+ }
+
/**
* A graph tester that is specific to the memoizing evaluator, with some convenience methods.
*/
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
index 53f6ebf..bbed5ba 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
@@ -89,13 +89,17 @@
public enum EventType {
CREATE_IF_ABSENT,
ADD_REVERSE_DEP,
+ REMOVE_REVERSE_DEP,
SIGNAL,
SET_VALUE,
MARK_DIRTY,
MARK_CLEAN,
IS_CHANGED,
GET_VALUE_WITH_METADATA,
- IS_DIRTY
+ IS_DIRTY,
+ IS_READY,
+ CHECK_IF_DONE,
+ GET_ALL_DIRECT_DEPS_FOR_INCOMPLETE_NODE
}
public enum Order {
@@ -121,6 +125,13 @@
}
@Override
+ public synchronized void removeReverseDep(SkyKey reverseDep) {
+ graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.BEFORE, reverseDep);
+ super.removeReverseDep(reverseDep);
+ graphListener.accept(myKey, EventType.REMOVE_REVERSE_DEP, Order.AFTER, reverseDep);
+ }
+
+ @Override
public boolean signalDep(Version childVersion) {
graphListener.accept(myKey, EventType.SIGNAL, Order.BEFORE, childVersion);
boolean result = super.signalDep(childVersion);
@@ -137,9 +148,9 @@
}
@Override
- public Iterable<SkyKey> markDirty(boolean isChanged) {
+ public boolean markDirty(boolean isChanged) {
graphListener.accept(myKey, EventType.MARK_DIRTY, Order.BEFORE, isChanged);
- Iterable<SkyKey> result = super.markDirty(isChanged);
+ boolean result = super.markDirty(isChanged);
graphListener.accept(myKey, EventType.MARK_DIRTY, Order.AFTER, isChanged);
return result;
}
@@ -165,9 +176,28 @@
}
@Override
+ public synchronized boolean isReady() {
+ graphListener.accept(myKey, EventType.IS_READY, Order.BEFORE, this);
+ return super.isReady();
+ }
+
+ @Override
public SkyValue getValueMaybeWithMetadata() {
graphListener.accept(myKey, EventType.GET_VALUE_WITH_METADATA, Order.BEFORE, this);
return super.getValueMaybeWithMetadata();
}
+
+ @Override
+ public synchronized DependencyState checkIfDoneForDirtyReverseDep(SkyKey reverseDep) {
+ graphListener.accept(myKey, EventType.CHECK_IF_DONE, Order.BEFORE, reverseDep);
+ return super.checkIfDoneForDirtyReverseDep(reverseDep);
+ }
+
+ @Override
+ public synchronized Iterable<SkyKey> getAllDirectDepsForIncompleteNode() {
+ graphListener.accept(
+ myKey, EventType.GET_ALL_DIRECT_DEPS_FOR_INCOMPLETE_NODE, Order.BEFORE, this);
+ return super.getAllDirectDepsForIncompleteNode();
+ }
}
}
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
index efcbbec..526666f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilTest.java
@@ -48,43 +48,49 @@
this.numElements = numElements;
}
- private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL = new ReverseDepsUtil<Example>() {
- @Override
- void setReverseDepsObject(Example container, Object object) {
- container.reverseDeps = object;
- }
+ private static final ReverseDepsUtil<Example> REVERSE_DEPS_UTIL =
+ new ReverseDepsUtil<Example>() {
+ @Override
+ void setReverseDepsObject(Example container, Object object) {
+ container.reverseDeps = object;
+ }
- @Override
- void setSingleReverseDep(Example container, boolean singleObject) {
- container.single = singleObject;
- }
+ @Override
+ void setSingleReverseDep(Example container, boolean singleObject) {
+ container.single = singleObject;
+ }
- @Override
- void setReverseDepsToRemove(Example container, List<SkyKey> object) {
- container.reverseDepsToRemove = object;
- }
+ @Override
+ void setDataToConsolidate(Example container, Object dataToConsolidate) {
+ container.dataToConsolidate = dataToConsolidate;
+ }
- @Override
- Object getReverseDepsObject(Example container) {
- return container.reverseDeps;
- }
+ @Override
+ Object getReverseDepsObject(Example container) {
+ return container.reverseDeps;
+ }
- @Override
- boolean isSingleReverseDep(Example container) {
- return container.single;
- }
+ @Override
+ boolean isSingleReverseDep(Example container) {
+ return container.single;
+ }
- @Override
- List<SkyKey> getReverseDepsToRemove(Example container) {
- return container.reverseDepsToRemove;
- }
- };
+ @Override
+ Object getDataToConsolidate(Example container) {
+ return container.dataToConsolidate;
+ }
+ };
private class Example {
Object reverseDeps = ImmutableList.of();
boolean single;
- List<SkyKey> reverseDepsToRemove;
+ Object dataToConsolidate;
+
+ @Override
+ public String toString() {
+ return "Example: " + reverseDeps + ", " + single + ", " + dataToConsolidate;
+ }
}
@Test
@@ -101,7 +107,7 @@
REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
}
assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
- assertThat(example.reverseDepsToRemove).isNull();
+ assertThat(example.dataToConsolidate).isNull();
}
}
@@ -120,7 +126,7 @@
REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
}
assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
- assertThat(example.reverseDepsToRemove).isNull();
+ assertThat(example.dataToConsolidate).isNull();
}
}
