From 2b8a3a45b22fd544230434f3e4ffd6f15334adc8 Mon Sep 17 00:00:00 2001 From: Janak Ramakrishnan Date: Fri, 14 Oct 2016 11:41:27 +0000 Subject: 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 --- .../devtools/build/lib/util/GroupedList.java | 82 ++++-- .../build/skyframe/DelegatingNodeEntry.java | 4 +- .../devtools/build/skyframe/InMemoryNodeEntry.java | 4 +- .../google/devtools/build/skyframe/NodeEntry.java | 6 +- .../devtools/build/skyframe/ParallelEvaluator.java | 313 +++++++++++---------- .../build/skyframe/SkyFunctionEnvironment.java | 10 +- .../devtools/build/lib/util/GroupedListTest.java | 32 ++- .../build/skyframe/InMemoryNodeEntryTest.java | 9 +- 8 files changed, 258 insertions(+), 202 deletions(-) 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 7f0db7839c..a6f9fbe683 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.ImmutableList; 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 @@ public class GroupedList implements Iterable> { this.elements = new ArrayList<>(elements); } - /** Appends the list constructed in helper to this list. */ - public void append(GroupedListHelper 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. + public Set append(GroupedListHelper 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 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 dedupedList = null; + List list = (List) 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 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 group) { @@ -343,25 +375,28 @@ public class GroupedList implements Iterable> { /** * 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. + * + *

Duplicate elements may be encountered while iterating through this object. */ public static class GroupedListHelper implements Iterable { // Non-final only for removal. private List groupedList; private List currentGroup = null; - private final CompactHashSet elements; + private final List 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 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 @@ public class GroupedList implements Iterable> { * 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 class GroupedList implements Iterable> { */ public void remove(Set 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 @@ public class GroupedList implements Iterable> { 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 iterator() { return elements.iterator(); } - /** Create a GroupedListHelper from a collection of elements, all put in the same group.*/ - public static GroupedListHelper create(Collection elements) { - GroupedListHelper 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 GroupedListHelper 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 47a9e616dd..2152fb34b0 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 @@ public abstract class DelegatingNodeEntry implements NodeEntry { } @Override - public void addTemporaryDirectDeps(GroupedListHelper helper) { - getDelegate().addTemporaryDirectDeps(helper); + public Set addTemporaryDirectDeps(GroupedListHelper 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 82d692201d..4c8ebce871 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 @@ public class InMemoryNodeEntry implements NodeEntry { } @Override - public synchronized void addTemporaryDirectDeps(GroupedListHelper helper) { + public synchronized Set addTemporaryDirectDeps(GroupedListHelper 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 ee75ac3cf1..b86d4712a4 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 @@ public interface NodeEntry extends ThinNodeEntry { @ThreadSafe void removeUnfinishedDeps(Set unfinishedDeps); + /** + * Adds the temporary direct deps given in {@code helper} and returns the set of unique deps + * added. + */ @ThreadSafe - void addTemporaryDirectDeps(GroupedListHelper helper); + Set addTemporaryDirectDeps(GroupedListHelper 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 ee3ac7290b..727b8395e9 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 @@ public final class ParallelEvaluator implements Evaluator { // 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 depEntry : entriesToCheck.entrySet()) { @@ -344,138 +344,143 @@ public final class ParallelEvaluator implements Evaluator { @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 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 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. - return; + // This is not the first error encountered, so we ignore it so that we can terminate + // with the first error. + return; + } } - } - Map 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; + Map 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 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); } - 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 newDirectDeps = env.getNewlyRequestedDeps(); + GroupedListHelper 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 @@ public final class ParallelEvaluator implements Evaluator { 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 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 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 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 reverseDeps) { @@ -594,8 +599,8 @@ public final class ParallelEvaluator implements Evaluator { } } env.getNewlyRequestedDeps().remove(unfinishedDeps); - entry.addTemporaryDirectDeps(env.getNewlyRequestedDeps()); - for (SkyKey newDep : env.getNewlyRequestedDeps()) { + Set 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 8c3126f38b..8e1d3cfb81 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 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment { + skyKey + ". Present values: " + deps - + "requested from: " + + " requested from: " + depKeys + ", " + entry); @@ -262,8 +262,7 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment { } 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 @@ class SkyFunctionEnvironment extends AbstractSkyFunctionEnvironment { } 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 b416719f69..6ffba0ef34 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.ImmutableSet; 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 { @@ -161,6 +159,22 @@ public class GroupedListTest { assertElementsEqualInGroups(groupedList, elements); } + @Test + public void sizeWithDuplicatesInAndOutOfGroups() { + GroupedList groupedList = new GroupedList<>(); + GroupedListHelper 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 groupedList = new GroupedList<>(); @@ -226,7 +240,13 @@ public class GroupedListTest { private static Object createAndCompress(Collection list) { GroupedList result = new GroupedList<>(); - result.append(GroupedListHelper.create(list)); + GroupedListHelper 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 9c19360762..8b8fb81c8c 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 @@ public class InMemoryNodeEntryTest { .addReverseDepAndCheckIfDone(null) .isEqualTo(DependencyState.NEEDS_SCHEDULING); for (Set depGroup : groupedDirectDeps) { - entry.addTemporaryDirectDeps(GroupedListHelper.create(depGroup)); + GroupedListHelper 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(); } -- cgit v1.2.3