Stop storing a set in GroupedListHelper to deduplicate SkyKey dep requests. Instead, deduplicate when the helper is actually added to a GroupedList.
--
MOS_MIGRATED_REVID=136145321
diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
index 7f0db78..a6f9fbe 100644
--- a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
+++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -18,7 +18,6 @@
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.collect.CompactHashSet;
-
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
@@ -56,15 +55,48 @@
this.elements = new ArrayList<>(elements);
}
- /** Appends the list constructed in helper to this list. */
- public void append(GroupedListHelper<T> helper) {
+ /**
+ * Appends the list constructed in {@code helper} to this list. Returns the elements of {@code
+ * helper}, uniquified.
+ */
+ @SuppressWarnings("unchecked") // Cast to T and List<T>.
+ public Set<T> append(GroupedListHelper<T> helper) {
Preconditions.checkState(helper.currentGroup == null, "%s %s", this, helper);
// Do a check to make sure we don't have lists here. Note that if helper.elements is empty,
// Iterables.getFirst will return null, and null is not instanceof List.
Preconditions.checkState(!(Iterables.getFirst(helper.elements, null) instanceof List),
"Cannot make grouped list of lists: %s", helper);
- elements.addAll(helper.groupedList);
- size += helper.size();
+ Set<T> uniquifier = CompactHashSet.createWithExpectedSize(helper.groupedList.size());
+ for (Object item : helper.groupedList) {
+ if (item instanceof List) {
+ // Optimize for the case that elements in this list are unique.
+ ImmutableList.Builder<T> dedupedList = null;
+ List<T> list = (List<T>) item;
+ for (int i = 0; i < list.size(); i++) {
+ T elt = list.get(i);
+ if (!uniquifier.add(elt)) {
+ if (dedupedList == null) {
+ dedupedList = ImmutableList.builder();
+ dedupedList.addAll(list.subList(0, i));
+ }
+ } else if (dedupedList != null) {
+ dedupedList.add(elt);
+ }
+ }
+ if (dedupedList == null) {
+ elements.add(list);
+ } else {
+ List<T> filteredList = dedupedList.build();
+ if (!filteredList.isEmpty()) {
+ elements.add(filteredList);
+ }
+ }
+ } else if (uniquifier.add((T) item)) {
+ elements.add(item);
+ }
+ }
+ size += uniquifier.size();
+ return uniquifier;
}
public void appendGroup(Collection<T> group) {
@@ -343,25 +375,28 @@
/**
* Builder-like object for GroupedLists. An already-existing grouped list is appended to by
* constructing a helper, mutating it, and then appending that helper to the grouped list.
+ *
+ * <p>Duplicate elements may be encountered while iterating through this object.
*/
public static class GroupedListHelper<E> implements Iterable<E> {
// Non-final only for removal.
private List<Object> groupedList;
private List<E> currentGroup = null;
- private final CompactHashSet<E> elements;
+ private final List<E> elements;
public GroupedListHelper() {
// Optimize for short lists.
groupedList = new ArrayList<>(1);
- elements = CompactHashSet.create();
+ elements = new ArrayList<>(1);
}
/** Create with a copy of the contents of {@param elements} as the initial group. */
- private GroupedListHelper(Collection<E> elements) {
+ private GroupedListHelper(E element) {
// Optimize for short lists.
groupedList = new ArrayList<>(1);
- addItem(elements, groupedList);
- this.elements = CompactHashSet.create(elements);
+ groupedList.add(element);
+ this.elements = new ArrayList<>(1);
+ this.elements.add(element);
}
/**
@@ -369,7 +404,7 @@
* goes in a group of its own.
*/
public void add(E elt) {
- Preconditions.checkState(elements.add(Preconditions.checkNotNull(elt)), "%s %s", elt, this);
+ elements.add(Preconditions.checkNotNull(elt, "%s %s", elt, this));
if (currentGroup == null) {
groupedList.add(elt);
} else {
@@ -384,9 +419,7 @@
*/
public void remove(Set<E> toRemove) {
groupedList = GroupedList.remove(groupedList, toRemove);
- int oldSize = size();
elements.removeAll(toRemove);
- Preconditions.checkState(oldSize == size() + toRemove.size(), "%s %s", toRemove, this);
}
/**
@@ -406,31 +439,22 @@
currentGroup = null;
}
- /** Returns true if elt is present in the list. */
+ /**
+ * Returns true if elt is present in the list. Takes time proportional to the list size, so
+ * should not be called routinely.
+ */
public boolean contains(E elt) {
return elements.contains(elt);
}
- private int size() {
- return elements.size();
- }
-
- /** Returns true if list is empty. */
- public boolean isEmpty() {
- return elements.isEmpty();
- }
-
@Override
public Iterator<E> iterator() {
return elements.iterator();
}
- /** Create a GroupedListHelper from a collection of elements, all put in the same group.*/
- public static <F> GroupedListHelper<F> create(Collection<F> elements) {
- GroupedListHelper<F> helper = new GroupedListHelper<>(elements);
- Preconditions.checkState(helper.elements.size() == elements.size(),
- "%s %s", helper, elements);
- return helper;
+ /** Create a GroupedListHelper from a single element. */
+ public static <F> GroupedListHelper<F> create(F element) {
+ return new GroupedListHelper<>(element);
}
@Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index 47a9e61..2152fb3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -141,8 +141,8 @@
}
@Override
- public void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
- getDelegate().addTemporaryDirectDeps(helper);
+ public Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
+ return getDelegate().addTemporaryDirectDeps(helper);
}
@Override
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 82d6922..4c8ebce 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -473,9 +473,9 @@
}
@Override
- public synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
+ public synchronized Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this);
- getTemporaryDirectDeps().append(helper);
+ return getTemporaryDirectDeps().append(helper);
}
@Override
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 ee75ac3..b86d471 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -351,8 +351,12 @@
@ThreadSafe
void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps);
+ /**
+ * Adds the temporary direct deps given in {@code helper} and returns the set of unique deps
+ * added.
+ */
@ThreadSafe
- void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
+ Set<SkyKey> addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
/**
* Add a group of direct deps to the node. May only be called with a {@link Collection} returned
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 ee3ac72..727b839 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -279,7 +279,7 @@
// 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)));
+ state.addTemporaryDirectDeps(GroupedListHelper.create(errorKey));
errorEntry.checkIfDoneForDirtyReverseDep(skyKey);
// Perform the necessary bookkeeping for any deps that are not being used.
for (Entry<SkyKey, ? extends NodeEntry> depEntry : entriesToCheck.entrySet()) {
@@ -344,138 +344,143 @@
@Override
public void run() {
try {
- NodeEntry state = Preconditions.checkNotNull(
- graph.get(null, Reason.EVALUATION, skyKey),
- skyKey);
- Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
- if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
- return;
- }
+ NodeEntry state =
+ Preconditions.checkNotNull(graph.get(null, Reason.EVALUATION, skyKey), skyKey);
+ Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
+ if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
+ return;
+ }
- Set<SkyKey> oldDeps = state.getAllRemainingDirtyDirectDeps();
- SkyFunctionEnvironment env =
- new SkyFunctionEnvironment(
- skyKey, state.getTemporaryDirectDeps(), oldDeps, evaluatorContext);
- SkyFunctionName functionName = skyKey.functionName();
- SkyFunction factory =
- Preconditions.checkNotNull(
- evaluatorContext.getSkyFunctions().get(functionName),
- "Unable to find SkyFunction '%s' for node with key %s, %s",
- functionName,
- skyKey,
- state);
+ Set<SkyKey> oldDeps = state.getAllRemainingDirtyDirectDeps();
+ SkyFunctionEnvironment env =
+ new SkyFunctionEnvironment(
+ skyKey, state.getTemporaryDirectDeps(), oldDeps, evaluatorContext);
+ SkyFunctionName functionName = skyKey.functionName();
+ SkyFunction factory =
+ Preconditions.checkNotNull(
+ evaluatorContext.getSkyFunctions().get(functionName),
+ "Unable to find SkyFunction '%s' for node with key %s, %s",
+ functionName,
+ skyKey,
+ state);
- SkyValue value = null;
- long startTime = BlazeClock.instance().nanoTime();
- try {
- value = factory.compute(skyKey, env);
- } catch (final SkyFunctionException builderException) {
- ReifiedSkyFunctionException reifiedBuilderException =
- new ReifiedSkyFunctionException(builderException, skyKey);
- // In keep-going mode, we do not let SkyFunctions throw errors with missing deps -- we will
- // restart them when their deps are done, so we can have a definitive error and definitive
- // graph structure, thus avoiding non-determinism. It's completely reasonable for
- // SkyFunctions to throw eagerly because they do not know if they are in keep-going mode.
- // Propagated transitive errors are treated the same as missing deps.
- if ((!evaluatorContext.keepGoing() || !env.valuesMissing())
- && reifiedBuilderException.getRootCauseSkyKey().equals(skyKey)) {
- boolean shouldFailFast =
- !evaluatorContext.keepGoing() || builderException.isCatastrophic();
- if (shouldFailFast) {
+ SkyValue value = null;
+ long startTime = BlazeClock.instance().nanoTime();
+ try {
+ value = factory.compute(skyKey, env);
+ } catch (final SkyFunctionException builderException) {
+ ReifiedSkyFunctionException reifiedBuilderException =
+ new ReifiedSkyFunctionException(builderException, skyKey);
+ // In keep-going mode, we do not let SkyFunctions throw errors with missing deps -- we
+ // will restart them when their deps are done, so we can have a definitive error and
+ // definitive graph structure, thus avoiding non-determinism. It's completely reasonable
+ // for SkyFunctions to throw eagerly because they do not know if they are in keep-going
+ // mode.
+ // Propagated transitive errors are treated the same as missing deps.
+ if ((!evaluatorContext.keepGoing() || !env.valuesMissing())
+ && reifiedBuilderException.getRootCauseSkyKey().equals(skyKey)) {
+ boolean shouldFailFast =
+ !evaluatorContext.keepGoing() || builderException.isCatastrophic();
+ if (shouldFailFast) {
// After we commit this error to the graph but before the doMutatingEvaluation call
// completes with the error there is a race-like opportunity for the error to be used,
// either by an in-flight computation or by a future computation.
if (!evaluatorContext.getVisitor().preventNewEvaluations()) {
- // This is not the first error encountered, so we ignore it so that we can terminate
- // with the first error.
+ // This is not the first error encountered, so we ignore it so that we can terminate
+ // with the first error.
+ return;
+ }
+ }
+
+ Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
+ evaluatorContext.getBatchValues(
+ skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps());
+ boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
+ for (NodeEntry depEntry :
+ Iterables.concat(env.getDirectDepsValues(), newlyRequestedDeps.values())) {
+ if (!isDoneForBuild(depEntry)) {
+ continue;
+ }
+ ErrorInfo depError = depEntry.getErrorInfo();
+ if (depError != null) {
+ isTransitivelyTransient |= depError.isTransient();
+ }
+ }
+ ErrorInfo errorInfo =
+ ErrorInfo.fromException(reifiedBuilderException, isTransitivelyTransient);
+ registerNewlyDiscoveredDepsForDoneEntry(
+ skyKey, state, newlyRequestedDeps, oldDeps, env);
+ env.setError(
+ state, errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
+ env.commit(
+ state,
+ evaluatorContext.keepGoing()
+ ? EnqueueParentBehavior.ENQUEUE
+ : EnqueueParentBehavior.SIGNAL);
+ if (!shouldFailFast) {
return;
}
+ throw SchedulerException.ofError(errorInfo, skyKey);
}
-
- Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
- evaluatorContext.getBatchValues(
- skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps());
- boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
- for (NodeEntry depEntry :
- Iterables.concat(env.getDirectDepsValues(), newlyRequestedDeps.values())) {
- if (!isDoneForBuild(depEntry)) {
- continue;
- }
- ErrorInfo depError = depEntry.getErrorInfo();
- if (depError != null) {
- isTransitivelyTransient |= depError.isTransient();
- }
- }
- ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException,
- isTransitivelyTransient);
- registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env);
- env.setError(
- state,
- errorInfo,
- /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
- env.commit(
- state,
- evaluatorContext.keepGoing()
- ? EnqueueParentBehavior.ENQUEUE
- : EnqueueParentBehavior.SIGNAL);
- if (!shouldFailFast) {
- return;
- }
- throw SchedulerException.ofError(errorInfo, skyKey);
- }
- } catch (RuntimeException re) {
- // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output
- // some context together with the exception.
- String msg = prepareCrashMessage(skyKey, state.getInProgressReverseDeps());
- RuntimeException ex = new RuntimeException(msg, re);
+ } catch (RuntimeException re) {
+ // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output
+ // some context together with the exception.
+ String msg = prepareCrashMessage(skyKey, state.getInProgressReverseDeps());
+ RuntimeException ex = new RuntimeException(msg, re);
evaluatorContext.getVisitor().noteCrash(ex);
- throw ex;
- } finally {
- env.doneBuilding();
- long elapsedTimeNanos = BlazeClock.instance().nanoTime() - startTime;
- if (elapsedTimeNanos > 0) {
- evaluatorContext.getProgressReceiver().computed(skyKey, elapsedTimeNanos);
- Profiler.instance().logSimpleTaskDuration(startTime, elapsedTimeNanos,
- ProfilerTask.SKYFUNCTION, skyKey);
+ throw ex;
+ } finally {
+ env.doneBuilding();
+ long elapsedTimeNanos = BlazeClock.instance().nanoTime() - startTime;
+ if (elapsedTimeNanos > 0) {
+ evaluatorContext.getProgressReceiver().computed(skyKey, elapsedTimeNanos);
+ Profiler.instance()
+ .logSimpleTaskDuration(
+ startTime, elapsedTimeNanos, ProfilerTask.SKYFUNCTION, skyKey);
+ }
}
- }
- GroupedListHelper<SkyKey> newDirectDeps = env.getNewlyRequestedDeps();
+ GroupedListHelper<SkyKey> newDirectDeps = env.getNewlyRequestedDeps();
- if (value != null) {
- Preconditions.checkState(!env.valuesMissing(), "Evaluation of %s returned non-null value "
- + "but requested dependencies that weren't computed yet (one of %s), ValueEntry: %s",
- skyKey, newDirectDeps, state);
- env.setValue(value);
- registerNewlyDiscoveredDepsForDoneEntry(
- skyKey,
- state,
- graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps()),
- oldDeps,
- env);
+ if (value != null) {
+ Preconditions.checkState(
+ !env.valuesMissing(),
+ "Evaluation of %s returned non-null value but requested dependencies that weren't "
+ + "computed yet (one of %s), NodeEntry: %s",
+ skyKey,
+ newDirectDeps,
+ state);
+ env.setValue(value);
+ registerNewlyDiscoveredDepsForDoneEntry(
+ skyKey,
+ state,
+ graph.getBatch(skyKey, Reason.RDEP_ADDITION, env.getNewlyRequestedDeps()),
+ oldDeps,
+ env);
env.commit(state, EnqueueParentBehavior.ENQUEUE);
- return;
- }
+ return;
+ }
- if (env.getDepErrorKey() != null) {
- Preconditions.checkState(
- !evaluatorContext.keepGoing(), "%s %s %s", skyKey, state, env.getDepErrorKey());
- // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first
- // need to add the edge between the current node and the child error it requested so that
- // error bubbling can occur. Note that this edge will subsequently be removed during graph
- // cleaning (since the current node will never be committed to the graph).
- SkyKey childErrorKey = env.getDepErrorKey();
- NodeEntry childErrorEntry = Preconditions.checkNotNull(
- graph.get(skyKey, Reason.OTHER, childErrorKey),
- "skyKey: %s, state: %s childErrorKey: %s",
- skyKey,
- state,
- childErrorKey);
+ if (env.getDepErrorKey() != null) {
+ Preconditions.checkState(
+ !evaluatorContext.keepGoing(), "%s %s %s", skyKey, state, env.getDepErrorKey());
+ // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first
+ // need to add the edge between the current node and the child error it requested so that
+ // error bubbling can occur. Note that this edge will subsequently be removed during graph
+ // cleaning (since the current node will never be committed to the graph).
+ SkyKey childErrorKey = env.getDepErrorKey();
+ NodeEntry childErrorEntry =
+ Preconditions.checkNotNull(
+ graph.get(skyKey, Reason.OTHER, childErrorKey),
+ "skyKey: %s, state: %s childErrorKey: %s",
+ skyKey,
+ state,
+ childErrorKey);
if (newDirectDeps.contains(childErrorKey)) {
// Add this dep if it was just requested. In certain rare race conditions (see
// MemoizingEvaluatorTest.cachedErrorCausesRestart) this dep may have already been
// requested.
- state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(childErrorKey)));
+ state.addTemporaryDirectDeps(GroupedListHelper.create(childErrorKey));
DependencyState childErrorState;
if (oldDeps.contains(childErrorKey)) {
childErrorState = childErrorEntry.checkIfDoneForDirtyReverseDep(skyKey);
@@ -489,62 +494,62 @@
state,
childErrorKey,
childErrorEntry);
- }
- ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo());
+ }
+ ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo());
evaluatorContext.getVisitor().preventNewEvaluations();
- throw SchedulerException.ofError(childErrorInfo, childErrorKey);
- }
+ throw SchedulerException.ofError(childErrorInfo, childErrorKey);
+ }
- // TODO(bazel-team): This code is not safe to interrupt, because we would lose the state in
- // newDirectDeps.
+ // TODO(bazel-team): This code is not safe to interrupt, because we would lose the state in
+ // newDirectDeps.
- // TODO(bazel-team): An ill-behaved SkyFunction can throw us into an infinite loop where we
- // add more dependencies on every run. [skyframe-core]
+ // TODO(bazel-team): An ill-behaved SkyFunction can throw us into an infinite loop where we
+ // add more dependencies on every run. [skyframe-core]
- // Add all new keys to the set of known deps.
- state.addTemporaryDirectDeps(newDirectDeps);
+ // Add all new keys to the set of known deps.
+ Set<SkyKey> uniqueNewDeps = state.addTemporaryDirectDeps(newDirectDeps);
- // If there were no newly requested dependencies, at least one of them was in error or there
- // is a bug in the SkyFunction implementation. The environment has collected its errors, so we
- // just order it to be built.
- if (newDirectDeps.isEmpty()) {
- // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
- Preconditions.checkState(
- !env.getChildErrorInfos().isEmpty(),
- "Evaluation of SkyKey failed and no dependencies were requested: %s %s",
- skyKey,
- state);
- Preconditions.checkState(
- evaluatorContext.keepGoing(),
- "nokeep_going evaluation should have failed on first child error: %s %s %s",
- skyKey,
- state,
- env.getChildErrorInfos());
+ // If there were no newly requested dependencies, at least one of them was in error or there
+ // is a bug in the SkyFunction implementation. The environment has collected its errors, so
+ // we just order it to be built.
+ if (uniqueNewDeps.isEmpty()) {
+ // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
+ Preconditions.checkState(
+ !env.getChildErrorInfos().isEmpty(),
+ "Evaluation of SkyKey failed and no dependencies were requested: %s %s",
+ skyKey,
+ state);
+ Preconditions.checkState(
+ evaluatorContext.keepGoing(),
+ "nokeep_going evaluation should have failed on first child error: %s %s %s",
+ skyKey,
+ state,
+ env.getChildErrorInfos());
// If the child error was catastrophic, committing this parent to the graph is not
// necessary, but since we don't do error bubbling in catastrophes, it doesn't violate any
// invariants either.
env.commit(state, EnqueueParentBehavior.ENQUEUE);
- return;
- }
+ return;
+ }
- for (Entry<SkyKey, ? extends NodeEntry> e :
- graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) {
- SkyKey newDirectDep = e.getKey();
- NodeEntry newDirectDepEntry = e.getValue();
- enqueueChild(
- skyKey,
- state,
- newDirectDep,
- newDirectDepEntry,
- /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
- }
+ for (Entry<SkyKey, ? extends NodeEntry> e :
+ graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, uniqueNewDeps).entrySet()) {
+ SkyKey newDirectDep = e.getKey();
+ NodeEntry newDirectDepEntry = e.getValue();
+ enqueueChild(
+ skyKey,
+ state,
+ newDirectDep,
+ newDirectDepEntry,
+ /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
+ }
+ // It is critical that there is no code below this point in the try block.
} catch (InterruptedException ie) {
// InterruptedException cannot be thrown by Runnable.run, so we must wrap it.
// Interrupts can be caught by both the Evaluator and the AbstractQueueVisitor.
// The former will unwrap the IE and propagate it as is; the latter will throw a new IE.
throw SchedulerException.ofInterruption(ie, skyKey);
}
- // It is critical that there is no code below this point.
}
private String prepareCrashMessage(SkyKey skyKey, Iterable<SkyKey> reverseDeps) {
@@ -594,8 +599,8 @@
}
}
env.getNewlyRequestedDeps().remove(unfinishedDeps);
- entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps());
- for (SkyKey newDep : env.getNewlyRequestedDeps()) {
+ Set<SkyKey> uniqueNewDeps = entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps());
+ for (SkyKey newDep : uniqueNewDeps) {
// Note that this depEntry can't be null. If env.newlyRequestedDeps contained a key with a
// null entry, then it would have been added to unfinishedDeps and then removed from
// env.newlyRequestedDeps just above this loop.
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index 8c3126f..8e1d3cf 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -191,7 +191,7 @@
+ skyKey
+ ". Present values: "
+ deps
- + "requested from: "
+ + " requested from: "
+ depKeys
+ ", "
+ entry);
@@ -262,8 +262,7 @@
}
Preconditions.checkState(
triState == DependencyState.DONE, "%s %s %s", skyKey, triState, errorInfo);
- state.addTemporaryDirectDeps(
- GroupedListHelper.create(ImmutableList.of(ErrorTransienceValue.KEY)));
+ state.addTemporaryDirectDeps(GroupedListHelper.create(ErrorTransienceValue.KEY));
state.signalDep();
}
@@ -467,10 +466,7 @@
}
private void addDep(SkyKey key) {
- if (!newlyRequestedDeps.contains(key)) {
- // dep may have been requested already this evaluation. If not, add it.
- newlyRequestedDeps.add(key);
- }
+ newlyRequestedDeps.add(key);
}
/**
diff --git a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
index b416719..6ffba0e 100644
--- a/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/util/GroupedListTest.java
@@ -23,16 +23,14 @@
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Set;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
@RunWith(JUnit4.class)
public class GroupedListTest {
@@ -162,6 +160,22 @@
}
@Test
+ public void sizeWithDuplicatesInAndOutOfGroups() {
+ GroupedList<String> groupedList = new GroupedList<>();
+ GroupedListHelper<String> helper = new GroupedListHelper<>();
+ helper.add("1");
+ helper.startGroup();
+ helper.add("1");
+ helper.add("2");
+ helper.add("3");
+ helper.endGroup();
+ helper.add("3");
+ groupedList.append(helper);
+ assertThat(groupedList.numElements()).isEqualTo(3);
+ assertThat(groupedList.listSize()).isEqualTo(2);
+ }
+
+ @Test
public void removeMakesEmpty() {
GroupedList<String> groupedList = new GroupedList<>();
assertTrue(groupedList.isEmpty());
@@ -226,7 +240,13 @@
private static Object createAndCompress(Collection<String> list) {
GroupedList<String> result = new GroupedList<>();
- result.append(GroupedListHelper.create(list));
+ GroupedListHelper<String> helper = new GroupedListHelper<>();
+ helper.startGroup();
+ for (String item : list) {
+ helper.add(item);
+ }
+ helper.endGroup();
+ result.append(helper);
return result.compress();
}
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 9c19360..8b8fb81 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -709,7 +709,14 @@
.addReverseDepAndCheckIfDone(null)
.isEqualTo(DependencyState.NEEDS_SCHEDULING);
for (Set<SkyKey> depGroup : groupedDirectDeps) {
- entry.addTemporaryDirectDeps(GroupedListHelper.create(depGroup));
+ GroupedListHelper<SkyKey> helper = new GroupedListHelper<>();
+ helper.startGroup();
+ for (SkyKey item : depGroup) {
+ helper.add(item);
+ }
+ helper.endGroup();
+
+ entry.addTemporaryDirectDeps(helper);
for (int i = 0; i < depGroup.size(); i++) {
entry.signalDep();
}
