bazel collect: simplify NestedSet depth limit check
This change causes NestedSet to record its depth in the graph.
Specifically, it records the height of the DAG of arrays,
after singleton inlining. It is exposed as NestedSet.getDepth.
To save space, we squirrel the value into the first slot of the children array.
According to the Usual Benchmark, the extra array element adds +0.65% RAM.
This compares to +1.3% for the naive solution of an additional 'int depth' field.
This allows the depth to be computed in constant time, without flattening,
so the Starlark depset constructor can reject too-deep sets eagerly instead
of deferring the check till flattening time, which resulted in the scattering
of unchecked NestedSetDepthExceptions throughout the code base,
including in such places as the Starlark interpreter's 'str' operator.
Java code that uses NestedSet is not subject to any depth limit or check,
but is free to add explicit checks at important boundaries, such as
rule construction, provider construction, and so on.
Even in the absence of such explicit checks, if an overly deep depset
is constructed by alternating Java and Starlark operations,
a Starlark operation will eventually fail even it was not the one
that crossed the threshold of the limit.
RELNOTES: The --debug_depset_flag has been removed as it is in effect always on at no cost.
PiperOrigin-RevId: 315741238
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/StarlarkRuleConfiguredTargetUtil.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/StarlarkRuleConfiguredTargetUtil.java
index 7fff89b..d71b44d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/StarlarkRuleConfiguredTargetUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/StarlarkRuleConfiguredTargetUtil.java
@@ -33,7 +33,6 @@
import com.google.devtools.build.lib.analysis.test.InstrumentedFilesInfo;
import com.google.devtools.build.lib.collect.nestedset.Depset;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet.NestedSetDepthException;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
@@ -652,23 +651,11 @@
private static void assertExecutableSymlinkPresent(
Runfiles runfiles, Artifact executable, Location loc) throws EvalException {
- try {
- // Extracting the map from Runfiles flattens a depset.
- // TODO(cparsons): Investigate: Avoiding this flattening may be an efficiency win.
- Map<PathFragment, Artifact> symlinks = runfiles.asMapWithoutRootSymlinks();
- if (!symlinks.containsValue(executable)) {
- throw new EvalException(loc, "main program " + executable + " not included in runfiles");
- }
- } catch (NestedSetDepthException exception) {
- throw new EvalException(
- loc,
- "depset exceeded maximum depth "
- + exception.getDepthLimit()
- + ". This was only discovered when attempting to flatten the runfiles depset "
- + "returned by the rule implementation function. the size of depsets is unknown "
- + "until flattening. "
- + "See https://github.com/bazelbuild/bazel/issues/9180 for details and possible "
- + "solutions.");
+ // Extracting the map from Runfiles flattens a depset.
+ // TODO(cparsons): Investigate: Avoiding this flattening may be an efficiency win.
+ Map<PathFragment, Artifact> symlinks = runfiles.asMapWithoutRootSymlinks();
+ if (!symlinks.containsValue(executable)) {
+ throw new EvalException(loc, "main program " + executable + " not included in runfiles");
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
index ba3a521..a26131c 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
@@ -15,7 +15,6 @@
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet.NestedSetDepthException;
import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
import com.google.devtools.build.lib.syntax.Dict;
@@ -29,6 +28,7 @@
import com.google.devtools.build.lib.syntax.StarlarkThread;
import com.google.devtools.build.lib.syntax.StarlarkValue;
import java.util.List;
+import java.util.concurrent.atomic.AtomicInteger;
import javax.annotation.Nullable;
import net.starlark.java.annot.StarlarkBuiltin;
import net.starlark.java.annot.StarlarkDocumentationCategory;
@@ -341,18 +341,7 @@
+ "on the depset and vice versa.",
useStarlarkThread = true)
public StarlarkList<Object> toListForStarlark(StarlarkThread thread) throws EvalException {
- try {
- return StarlarkList.copyOf(thread.mutability(), this.toList());
- } catch (NestedSetDepthException exception) {
- throw new EvalException(
- null,
- "depset exceeded maximum depth "
- + exception.getDepthLimit()
- + ". This was only discovered when attempting to flatten the depset for to_list(), "
- + "as the size of depsets is unknown until flattening. "
- + "See https://github.com/bazelbuild/bazel/issues/9180 for details and possible "
- + "solutions.");
- }
+ return StarlarkList.copyOf(thread.mutability(), this.toList());
}
/** Create a Depset from the given direct and transitive components. */
@@ -559,17 +548,13 @@
result = legacyDepsetConstructor(items, order, direct, transitive, semantics);
}
- if (semantics.debugDepsetDepth()) {
- // Flatten the underlying nested set. If the set exceeds the depth limit, then this will
- // throw a NestedSetDepthException.
- // This is an extremely inefficient check and should be only done in the
- // "--debug_depset_depth" mode.
- try {
- result.toList(); // may throw exception
- } catch (NestedSetDepthException ex) {
- throw Starlark.errorf("depset exceeded maximum depth %d", ex.getDepthLimit());
- }
+ // check depth limit
+ int depth = result.getSet().getDepth();
+ int limit = depthLimit.get();
+ if (depth > limit) {
+ throw Starlark.errorf("depset depth %d exceeds limit (%d)", depth, limit);
}
+
return result;
}
@@ -602,4 +587,17 @@
private static boolean isEmptyStarlarkList(Object o) {
return o instanceof Sequence && ((Sequence) o).isEmpty();
}
+
+ /**
+ * Sets the maximum depth for nested sets constructed by the Starlark {@code depset} function (as
+ * set by {@code --nested_set_depth_limit}).
+ *
+ * @return whether the new limit differs from the old
+ */
+ public static boolean setDepthLimit(int newLimit) {
+ int oldValue = depthLimit.getAndSet(newLimit);
+ return oldValue != newLimit;
+ }
+
+ private static final AtomicInteger depthLimit = new AtomicInteger(3500);
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index 217b5f8..550dc76 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -36,7 +36,6 @@
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
-import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Consumer;
import java.util.function.Predicate;
import javax.annotation.Nullable;
@@ -86,31 +85,36 @@
// The relative order of direct and transitive is determined by the Order.
// All empty sets have children==EMPTY_CHILDREN, not null.
//
+ // The first slot in an array is not a true element, but the Integer depth of the graph,
+ // which is one greater than that of the deepest successor. Thus arrays other than
+ // EMPTY_CHILDREN have length >= 3: the depth plus 2 or more successors.
+ //
// Please be careful to use the terms of the conceptual model in the API documentation,
// and the terms of the physical representation in internal comments. They are not the same.
+ // In graphical terms, the "direct" elements are the graph successors that are leaves,
+ // and the "transitive" elements are the graph successors that are non-leaves, and
+ // non-leaf nodes have an out-degree of at least 2.
//
- // TODO(adonovan): rename this field and related accessors to something less suggestive,
- // such as 'state' or 'repr' or 'node'. The public API no longer mentions "children".
+ // TODO(adonovan): rename this field and all accessors that use the same format to
+ // something less suggestive such as 'repr' or 'impl', and rename all uses of children
+ // meaning "logical graph successors" to 'successors'.
final Object children;
+ // memo is a bitfield, lazily populated by lockedExpand, that indicates whether the
+ // ith successor (a non-leaf) should be visited, or skipped because that subgraph would
+ // contribute nothing to the flattening as it contains only elements previously seen in
+ // the traversal. All NestedSets of depth < 3, that is, those whose successors are
+ // all leaves, share the empty NO_MEMO array.
@Nullable private byte[] memo;
- /**
- * The application depth limit of nested sets. Nested sets over this depth will throw {@link
- * NestedSetDepthException} on flattening of the depset.
- *
- * <p>This limit should be set by command line option processing in the Bazel server.
- */
- private static final AtomicInteger expansionDepthLimit = new AtomicInteger(3500);
-
- private static final byte[] LEAF_MEMO = {};
- @AutoCodec static final Object[] EMPTY_CHILDREN = {};
+ private static final byte[] NO_MEMO = {};
+ @AutoCodec static final Object[] EMPTY_CHILDREN = {0};
/** Construct an empty NestedSet. Should only be called by Order's class initializer. */
NestedSet(Order order) {
this.orderAndSize = order.ordinal();
this.children = EMPTY_CHILDREN;
- this.memo = LEAF_MEMO;
+ this.memo = NO_MEMO;
}
NestedSet(
@@ -145,9 +149,10 @@
// the same child, which is a problem for the fast path in toList().
Set<E> alreadyInserted = ImmutableSet.of();
// The candidate array of children.
- Object[] children = new Object[direct.size() + transitive.size()];
- int n = 0; // current position in children
+ Object[] children = new Object[1 + direct.size() + transitive.size()];
+ int n = 1; // current position in children array (skip depth slot)
boolean leaf = true; // until we find otherwise
+ int depth = 2;
for (int pass = 0; pass <= 1; ++pass) {
if ((pass == 0) == preorder && !direct.isEmpty()) {
@@ -170,9 +175,10 @@
Object c = subset.getChildrenInternal(interruptStrategy);
if (c instanceof Object[]) {
Object[] a = (Object[]) c;
- if (a.length < 2) {
+ if (a.length < 3) {
throw new AssertionError(a.length);
}
+ depth = Math.max(depth, 1 + depth(a));
children[n++] = a;
leaf = false;
} else {
@@ -190,27 +196,28 @@
}
}
+ // n == |successors| + 1
// If we ended up wrapping exactly one item or one other set, dereference it.
- if (n == 1) {
- this.children = children[0];
- } else if (n == 0) {
+ if (n == 2) {
+ this.children = children[1];
+ } else if (n == 1) {
this.children = EMPTY_CHILDREN;
- } else if (n < children.length) {
- this.children = Arrays.copyOf(children, n);
} else {
+ children[0] = depth;
+ if (n < children.length) {
+ children = Arrays.copyOf(children, n); // shrink to save space
+ }
this.children = children;
}
if (leaf) {
- this.memo = LEAF_MEMO;
+ this.memo = NO_MEMO;
}
}
+ // Precondition: EMPTY_CHILDREN is used as the canonical empty array.
private NestedSet(Order order, Object children, @Nullable byte[] memo) {
this.orderAndSize = order.ordinal();
- this.children =
- children instanceof Object[] && ((Object[]) children).length == 0
- ? EMPTY_CHILDREN
- : children;
+ this.children = children;
this.memo = memo;
}
@@ -230,7 +237,7 @@
boolean hasChildren =
children instanceof Object[]
&& (Arrays.stream((Object[]) children).anyMatch(child -> child instanceof Object[]));
- byte[] memo = hasChildren ? null : LEAF_MEMO;
+ byte[] memo = hasChildren ? null : NO_MEMO;
return new NestedSet<>(order, children, memo);
}
@@ -316,7 +323,9 @@
Predicate<Object> descend, Consumer<E> f, Object node) {
if (descend.test(node)) {
if (node instanceof Object[]) {
- for (Object child : (Object[]) node) {
+ Object[] children = (Object[]) node;
+ for (int i = 1; i < children.length; i++) { // skip depth
+ Object child = children[i];
forEachElementImpl(descend, f, child);
}
} else {
@@ -339,6 +348,22 @@
return isSingleton(children);
}
+ /**
+ * Returns the depth of the nested set graph. The empty set has depth zero. A leaf node with a
+ * single element has depth 1. A non-leaf node has a depth one greater than its deepest successor.
+ */
+ public int getDepth() {
+ return depth(getChildren());
+ }
+
+ private static int depth(Object children) {
+ return children == EMPTY_CHILDREN
+ ? 0 //
+ : children instanceof Object[]
+ ? (Integer) ((Object[]) children)[0] //
+ : 1;
+ }
+
private static boolean isSingleton(Object children) {
// Singleton sets are special cased in serialization, and make no calls to storage. Therefore,
// we know that any NestedSet with a ListenableFuture member is not a singleton.
@@ -516,8 +541,13 @@
*/
private ImmutableList<E> expand(Object[] children) {
// This value is only set in the constructor, so safe to test here with no lock.
- if (memo == LEAF_MEMO) {
- return ImmutableList.copyOf(new ArraySharingCollection<>(children));
+ if (memo == NO_MEMO) {
+ // The children array contains only leaf nodes. (It doesn't necessarily mean cardinality <=
+ // 1.)
+ // Use the array-sharing hack to return an (immutable) alias for the underlying data.
+ // ImutableList.subList (and reverse, if later called) use decorators, not copying.
+ ImmutableList<E> r = ImmutableList.copyOf(new ArraySharingCollection<>(children));
+ return r.subList(1, r.size()); // skip depth
}
CompactHashSet<E> members = lockedExpand(children);
if (members != null) {
@@ -554,27 +584,26 @@
/**
* If this is the first call for this object, fills {@code this.memo} and returns a set from
- * {@link #walk}. Otherwise returns null; the caller should use {@link #replay} instead.
+ * {@link #walk}. Otherwise returns null, in which case some other thread must have completely
+ * populated memo; the caller should use {@link #replay} instead.
*/
private synchronized CompactHashSet<E> lockedExpand(Object[] children) {
+ // Postcondition: memo is completely populated.
if (memo != null) {
return null;
}
CompactHashSet<E> members = CompactHashSet.createWithExpectedSize(128);
CompactHashSet<Object> sets = CompactHashSet.createWithExpectedSize(128);
sets.add(children);
- memo = new byte[Math.min((children.length + 7) / 8, 8)];
- int pos =
- walk(
- sets,
- members,
- children,
- /* pos= */ 0,
- /* currentDepth= */ 1,
- expansionDepthLimit.get());
- int bytes = (pos + 7) / 8;
+ int nsuccs = children.length - 1; // skip depth
+ // Allocate less memo than we might need, on the optimistic
+ // assumption that later bits are all zero (redundant successors)
+ // which need not be represented explictly.
+ memo = new byte[Math.min(ceildiv(nsuccs, 8), 8)];
+ int pos = walk(sets, members, children, /*pos=*/ 0);
+ int bytes = ceildiv(pos, 8);
if (bytes <= memo.length - 16) {
- memo = Arrays.copyOf(memo, bytes);
+ memo = Arrays.copyOf(memo, bytes); // shrink to save space
}
Preconditions.checkState(members.size() < (Integer.MAX_VALUE >> 2));
orderAndSize |= (members.size()) << 2;
@@ -589,16 +618,9 @@
* <p>Returns the final value of {@code pos}.
*/
private int walk(
- CompactHashSet<Object> sets,
- CompactHashSet<E> members,
- Object[] children,
- int pos,
- int currentDepth,
- int maxDepth) {
- if (currentDepth > maxDepth) {
- throw new NestedSetDepthException(maxDepth);
- }
- for (Object child : children) {
+ CompactHashSet<Object> sets, CompactHashSet<E> members, Object[] children, int pos) {
+ for (int i = 1; i < children.length; i++) { // skip depth
+ Object child = children[i];
if ((pos >> 3) >= memo.length) {
memo = Arrays.copyOf(memo, memo.length * 2);
}
@@ -606,7 +628,7 @@
if (sets.add(child)) {
int prepos = pos;
int presize = members.size();
- pos = walk(sets, members, (Object[]) child, pos + 1, currentDepth + 1, maxDepth);
+ pos = walk(sets, members, (Object[]) child, pos + 1);
if (presize < members.size()) {
memo[prepos >> 3] |= (byte) (1 << (prepos & 7));
} else {
@@ -634,7 +656,8 @@
*/
private static <E> int replay(
ImmutableList.Builder<E> output, Object[] children, byte[] memo, int pos) {
- for (Object child : children) {
+ for (int i = 1; i < children.length; i++) { // skip depth
+ Object child = children[i];
if ((memo[pos >> 3] & (1 << (pos & 7))) != 0) {
if (child instanceof Object[]) {
pos = replay(output, (Object[]) child, memo, pos + 1);
@@ -649,60 +672,67 @@
return pos;
}
- /**
- * Sets the application depth limit of nested sets. When flattening a {@link NestedSet} deeper
- * than this limit, a {@link NestedSetDepthException} will be thrown.
- *
- * <p>This limit should be set by command line option processing.
- *
- * @return true if the previous limit was different than this new limit
- */
- public static boolean setApplicationDepthLimit(int newLimit) {
- int oldValue = expansionDepthLimit.getAndSet(newLimit);
- return oldValue != newLimit;
- }
-
- /** An exception thrown when a nested set exceeds the application's depth limits. */
- public static final class NestedSetDepthException extends RuntimeException {
- private final int depthLimit;
-
- public NestedSetDepthException(int depthLimit) {
- this.depthLimit = depthLimit;
- }
-
- /** Returns the depth limit that was exceeded which resulted in this exception being thrown. */
- public int getDepthLimit() {
- return depthLimit;
- }
+ // ceildiv(x/y) returns ⌈x/y⌉.
+ private static int ceildiv(int x, int y) {
+ return (x + y - 1) / y;
}
/**
- * Returns a new NestedSet containing the same elements, but represented using a logical graph
- * with the specified maximum out-degree, which must be at least 2. The resulting set's iteration
- * order is undefined.
+ * Returns a new NestedSet containing the same elements, but represented using a graph node whose
+ * out-degree does not exceed {@code maxDegree}, which must be at least 2. The operation is
+ * shallow, not deeply recursive. The resulting set's iteration order is undefined.
*/
- public NestedSet<E> splitIfExceedsMaximumSize(int maximumSize) {
- Preconditions.checkArgument(maximumSize >= 2, "maximumSize must be at least 2");
+ // TODO(adonovan): move this hack into BuildEventStreamer. And rename 'size' to 'degree'.
+ public NestedSet<E> splitIfExceedsMaximumSize(int maxDegree) {
+ Preconditions.checkArgument(maxDegree >= 2, "maxDegree must be at least 2");
Object children = getChildren(); // may wait for a future
if (!(children instanceof Object[])) {
return this;
}
- Object[] arr = (Object[]) children;
- int size = arr.length;
- if (size <= maximumSize) {
+ Object[] succs = (Object[]) children;
+
+ int nsuccs = succs.length - 1; // skip depth
+ if (nsuccs <= maxDegree) {
return this;
}
- Object[][] pieces = new Object[((size + maximumSize - 1) / maximumSize)][];
- for (int i = 0; i < pieces.length; i++) {
- int max = Math.min((i + 1) * maximumSize, arr.length);
- pieces[i] = Arrays.copyOfRange(arr, i * maximumSize, max);
+
+ // Cut succs into n pieces each of at most maxDegree.
+ // The arrays succs, pieces, and pieces[i>1] all have an initial depth Integer.
+ int npieces = ceildiv(nsuccs, maxDegree);
+ Object[] pieces = new Object[1 + npieces];
+ pieces[0] = 1 + (int) succs[0]; // depth
+ for (int i = 0; i < npieces; i++) {
+ int piecelen = maxDegree;
+ if (nsuccs < (i + 1) * maxDegree) {
+ // short final piece
+ piecelen = nsuccs - i * maxDegree;
+
+ // very short (1-node) final piece? Inline it.
+ if (piecelen == 1) {
+ pieces[1 + i] = succs[1 + i * maxDegree];
+ break;
+ }
+ }
+
+ // Copy succs[...] into piece[1:], updating piece[0] with correct depth.
+ Object[] piece = new Object[1 + piecelen];
+ int depth = 1;
+ for (int j = 0; j < piecelen; j++) {
+ Object x = succs[1 + i * maxDegree + j];
+ piece[1 + j] = x;
+ if (x instanceof Object[]) {
+ depth = Math.max(depth, 1 + depth(x));
+ }
+ }
+ piece[0] = depth;
+ pieces[1 + i] = piece;
}
- // TODO(adonovan): why is this recursive call here? It looks like it is intended to propagate
- // the split down to each subgraph, but it clearly never did that, because it would have to be
- // applied to each element of pieces[i]. More surprising is that it does anything at all: pieces
- // has already been split. Yet a test breaks if it is removed. Investigate and simplify.
- return new NestedSet<E>(getOrder(), pieces, null).splitIfExceedsMaximumSize(maximumSize);
+ // Each piece is now smaller than maxDegree, but there may be many pieces.
+ // Recursively split pieces. (The recursion affects only the root; it
+ // does not traverse into successors.) In practice, maxDegree is large
+ // enough that the recursion rarely does any work.
+ return new NestedSet<E>(getOrder(), pieces, null).splitIfExceedsMaximumSize(maxDegree);
}
/** Returns the list of this node's successors that are themselves non-leaf nodes. */
@@ -731,7 +761,9 @@
return ImmutableList.of((E) children);
}
ImmutableList.Builder<E> res = ImmutableList.builder();
- for (Object c : (Object[]) children) {
+ Object[] succs = (Object[]) children;
+ for (int i = 1; i < succs.length; i++) { // skip depth
+ Object c = succs[i];
if (!(c instanceof Object[])) {
res.add((E) c);
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index 46eddd8..4e73229 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -79,8 +79,9 @@
if (children instanceof Object[]) {
if (!digestMap.readDigest(children, fingerprint)) {
Fingerprint childrenFingerprint = new Fingerprint();
- for (Object child : (Object[]) children) {
- addToFingerprint(mapFn, childrenFingerprint, digestMap, child);
+ Object[] succs = (Object[]) children;
+ for (int i = 1; i < succs.length; i++) { // skip depth
+ addToFingerprint(mapFn, childrenFingerprint, digestMap, succs[i]);
}
digestMap.insertAndReadDigest(children, childrenFingerprint, fingerprint);
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetOptionsModule.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetOptionsModule.java
index 5e99a5e..851d0f4 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetOptionsModule.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetOptionsModule.java
@@ -33,17 +33,15 @@
documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
effectTags = {OptionEffectTag.LOADING_AND_ANALYSIS},
help =
- "Limit on the depth of NestedSet, which is the internal data structure used to "
- + "implement `depset` in Starlark. If a depset is flattened during evaluation of "
- + "Starlark code or a NestedSet is flattened internally, and that data structure "
- + "has a depth exceeding this limit, then the Bazel invocation will fail.")
+ "The maximum depth of the graph internal to a depset (also known as NestedSet), above"
+ + " which the depset() constructor will fail.")
public int nestedSetDepthLimit;
}
@Override
public void beforeCommand(CommandEnvironment env) {
Options options = env.getOptions().getOptions(Options.class);
- boolean changed = NestedSet.setApplicationDepthLimit(options.nestedSetDepthLimit);
+ boolean changed = Depset.setDepthLimit(options.nestedSetDepthLimit);
if (changed) {
env.getSkyframeExecutor().resetEvaluator();
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
index 1a36ff9..6b9f152 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
@@ -30,7 +30,6 @@
*
* @param <E> the data type
*/
-// @ThreadSafety.ThreadSafe
public final class NestedSetVisitor<E> {
/**
@@ -77,8 +76,9 @@
private void visitRaw(Object node) {
if (visited.add(node)) {
if (node instanceof Object[]) {
- for (Object child : (Object[]) node) {
- visitRaw(child);
+ Object[] children = (Object[]) node;
+ for (int i = 1; i < children.length; i++) { // skip depth
+ visitRaw(children[i]);
}
} else {
callback.accept((E) node);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
index 1324ddd..2a9ce32 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
@@ -64,19 +64,6 @@
// <== Add new options here in alphabetic order ==>
@Option(
- name = "debug_depset_depth",
- defaultValue = "false",
- documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
- effectTags = {OptionEffectTag.BUILD_FILE_SEMANTICS},
- metadataTags = {},
- help =
- "Enables an expensive additional check that causes depset construction to fail fast if "
- + "the depset's depth would exceed the limit specified by "
- + "`--nested_set_depth_limit`. Ordinarily this failure occurs only when the depset "
- + "is flattened, which may be far from its point of creation.")
- public boolean debugDepsetDepth;
-
- @Option(
name = "experimental_action_args",
defaultValue = "true",
documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
@@ -654,7 +641,6 @@
StarlarkSemantics semantics =
StarlarkSemantics.builder()
// <== Add new options here in alphabetic order ==>
- .debugDepsetDepth(debugDepsetDepth)
.experimentalActionArgs(experimentalActionArgs)
.experimentalAllowIncrementalRepositoryUpdates(
experimentalAllowIncrementalRepositoryUpdates)
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Type.java b/src/main/java/com/google/devtools/build/lib/packages/Type.java
index da812e8..778019c 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Type.java
@@ -22,7 +22,6 @@
import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.collect.nestedset.Depset;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet.NestedSetDepthException;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
import com.google.devtools.build.lib.syntax.EvalException;
import com.google.devtools.build.lib.syntax.EvalUtils;
@@ -612,17 +611,7 @@
if (x instanceof Iterable) {
iterable = (Iterable<?>) x;
} else if (x instanceof Depset) {
- try {
- iterable = ((Depset) x).toList();
- } catch (NestedSetDepthException exception) {
- throw new ConversionException(
- "depset exceeded maximum depth "
- + exception.getDepthLimit()
- + ". This was only discovered when attempting to flatten the depset for"
- + " iteration, as the size of depsets is unknown until flattening. See"
- + " https://github.com/bazelbuild/bazel/issues/9180 for details and possible "
- + "solutions.");
- }
+ iterable = ((Depset) x).toList();
} else {
throw new ConversionException(this, x, what);
}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java b/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
index 5f90065..74c17e3 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
@@ -125,8 +125,8 @@
/**
* Given a set whose leaf successors are {@link Artifact} and {@link ExpandedArtifact}, returns a
- * weird Frankenstein object with each leaf successor replaced by ExpandedArtifact. Non-leaf
- * successors are unaltered.
+ * new NestedSet whose leaf successors are all ExpandedArtifact. Non-leaf successors are
+ * unaltered.
*/
static NestedSet<?> expandSet(CompletionContext ctx, NestedSet<?> artifacts) {
NestedSetBuilder<Object> res = new NestedSetBuilder<>(Order.STABLE_ORDER);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 556f3b3..c164679 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -291,20 +291,7 @@
+ "str(8) == \"8\"</pre>",
parameters = {@Param(name = "x", doc = "The object to convert.", noneable = true)})
public String str(Object x) throws EvalException {
- try {
- return Starlark.str(x);
- } catch (RuntimeException ex) {
- // TODO(adonovan): get rid of this somehow.
- if (ex.getClass().getSimpleName().equals("NestedSetDepthException")) {
- throw Starlark.errorf(
- "depset exceeded maximum depth"
- + ". This was only discovered when attempting to flatten the depset for str(), as "
- + "the size of depsets is unknown until flattening. "
- + "See https://github.com/bazelbuild/bazel/issues/9180 for details and possible "
- + "solutions.");
- }
- throw ex;
- }
+ return Starlark.str(x);
}
@StarlarkMethod(
@@ -734,19 +721,7 @@
String separator = "";
for (Object x : args) {
p.append(separator);
- try {
- p.debugPrint(x);
- } catch (RuntimeException ex) {
- // TODO(adonovan): get rid of this somehow.
- if (ex.getClass().getSimpleName().equals("NestedSetDepthException")) {
- throw Starlark.errorf(
- "depset exceeded maximum depth. This was only discovered when attempting to"
- + " flatten the depset for print(), as the size of depsets is unknown until"
- + " flattening. See https://github.com/bazelbuild/bazel/issues/9180 for details"
- + " and possible solutions.");
- }
- throw ex;
- }
+ p.debugPrint(x);
separator = sep;
}
// As part of the integration test "skylark_flag_test.sh", if the
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
index 70c6f43..f859597 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
@@ -194,8 +194,6 @@
AutoValue_StarlarkSemantics.class;
// <== Add new options here in alphabetic order ==>
- public abstract boolean debugDepsetDepth();
-
public abstract boolean experimentalActionArgs();
public abstract boolean experimentalAllowIncrementalRepositoryUpdates();
@@ -311,7 +309,6 @@
public static final StarlarkSemantics DEFAULT =
builder()
// <== Add new options here in alphabetic order ==>
- .debugDepsetDepth(false)
.experimentalActionArgs(true)
.experimentalAllowTagsPropagation(false)
.experimentalBuiltinsBzlPath("")
@@ -360,8 +357,6 @@
public abstract static class Builder {
// <== Add new options here in alphabetic order ==>
- public abstract Builder debugDepsetDepth(boolean value);
-
public abstract Builder experimentalActionArgs(boolean value);
public abstract Builder experimentalAllowIncrementalRepositoryUpdates(boolean value);
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
index 7990c1d..3f66420 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
@@ -431,19 +431,25 @@
}
@Test
- public void testDepthExceedsLimitDuringIteration() throws Exception {
- NestedSet.setApplicationDepthLimit(2000);
+ public void testConstructorDepthLimit() throws Exception {
ev.new Scenario()
.setUp(
"def create_depset(depth):",
" x = depset([0])",
" for i in range(1, depth):",
- " x = depset([i], transitive = [x])",
- " for element in x.to_list():",
- " str(x)",
- " return None")
- .testEval("create_depset(1000)", "None")
- .testIfErrorContains("depset exceeded maximum depth", "create_depset(3000)");
+ " x = depset([i], transitive = [x])")
+ .testEval("create_depset(3000)", "None") // succeeds
+ .testIfErrorContains("depset depth 3501 exceeds limit (3500)", "create_depset(4000)");
+
+ Depset.setDepthLimit(100);
+ ev.new Scenario()
+ .setUp(
+ "def create_depset(depth):",
+ " x = depset([0])",
+ " for i in range(1, depth):",
+ " x = depset([i], transitive = [x])")
+ .testEval("create_depset(99)", "None") // succeeds
+ .testIfErrorContains("depset depth 101 exceeds limit (100)", "create_depset(1000)");
}
@Test
@@ -508,37 +514,4 @@
+ "--incompatible_disable_depset_inputs=false",
"depset(items=[0,1])");
}
-
- @Test
- public void testDepsetDepthLimit() throws Exception {
- NestedSet.setApplicationDepthLimit(2000);
- ev.new Scenario()
- .setUp(
- "def create_depset(depth):",
- " x = depset([0])",
- " for i in range(1, depth):",
- " x = depset([i], transitive = [x])",
- " return x",
- "too_deep_depset = create_depset(3000)",
- "fine_depset = create_depset(900)")
- .testEval("fine_depset.to_list()[0]", "0")
- .testEval("str(fine_depset)[0:6]", "'depset'")
- .testIfErrorContains("depset exceeded maximum depth", "print(too_deep_depset)")
- .testIfErrorContains("depset exceeded maximum depth", "str(too_deep_depset)")
- .testIfErrorContains("depset exceeded maximum depth", "too_deep_depset.to_list()");
- }
-
- @Test
- public void testDepsetDebugDepth() throws Exception {
- NestedSet.setApplicationDepthLimit(2000);
- ev.new Scenario("--debug_depset_depth=true")
- .setUp(
- "def create_depset(depth):",
- " x = depset([0])",
- " for i in range(1, depth):",
- " x = depset([i], transitive = [x])",
- " return x")
- .testEval("str(create_depset(900))[0:6]", "'depset'")
- .testIfErrorContains("depset exceeded maximum depth", "create_depset(3000)");
- }
}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
index 83c2397..41f20ab 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
@@ -286,50 +286,51 @@
@Test
public void buildInterruptibly_propagatesInterrupt() {
- NestedSet<String> deserialzingNestedSet =
+ NestedSet<String> deserializingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
NestedSetBuilder<String> builder =
- NestedSetBuilder.<String>stableOrder().addTransitive(deserialzingNestedSet).add("a");
+ NestedSetBuilder.<String>stableOrder().addTransitive(deserializingNestedSet).add("a");
Thread.currentThread().interrupt();
assertThrows(InterruptedException.class, builder::buildInterruptibly);
}
@Test
public void getChildrenInterruptibly_propagatesInterrupt() {
- NestedSet<String> deserialzingNestedSet =
+ NestedSet<String> deserializingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
Thread.currentThread().interrupt();
- assertThrows(InterruptedException.class, deserialzingNestedSet::getChildrenInterruptibly);
+ assertThrows(InterruptedException.class, deserializingNestedSet::getChildrenInterruptibly);
}
@Test
public void toListWithTimeout_propagatesInterrupt() {
- NestedSet<String> deserialzingNestedSet =
+ NestedSet<String> deserializingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
Thread.currentThread().interrupt();
assertThrows(
InterruptedException.class,
- () -> deserialzingNestedSet.toListWithTimeout(Duration.ofDays(1)));
+ () -> deserializingNestedSet.toListWithTimeout(Duration.ofDays(1)));
}
@Test
public void toListWithTimeout_timesOut() {
- NestedSet<String> deserialzingNestedSet =
+ NestedSet<String> deserializingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
assertThrows(
- TimeoutException.class, () -> deserialzingNestedSet.toListWithTimeout(Duration.ofNanos(1)));
+ TimeoutException.class,
+ () -> deserializingNestedSet.toListWithTimeout(Duration.ofNanos(1)));
}
@Test
public void toListWithTimeout_waits() throws Exception {
SettableFuture<Object[]> future = SettableFuture.create();
- NestedSet<String> deserialzingNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, future);
+ NestedSet<String> deserializingNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, future);
Future<ImmutableList<String>> result =
Executors.newSingleThreadExecutor()
- .submit(() -> deserialzingNestedSet.toListWithTimeout(Duration.ofMinutes(1)));
+ .submit(() -> deserializingNestedSet.toListWithTimeout(Duration.ofMinutes(1)));
Thread.sleep(100);
assertThat(result.isDone()).isFalse();
- future.set(new Object[] {"a", "b"});
+ future.set(new Object[] {/*depth=*/ 2, "a", "b"});
assertThat(result.get()).containsExactly("a", "b");
}
@@ -360,4 +361,36 @@
future.set(new Object[] {"a", "b"});
assertThat(deserializingNestedSet.isReady()).isTrue();
}
+
+ @Test
+ public void getDepth() {
+ NestedSet<String> empty = nestedSetBuilder().build();
+ NestedSet<String> justA = nestedSetBuilder("a").build();
+ NestedSet<String> justB = nestedSetBuilder("b").build();
+ NestedSet<String> ab = nestedSetBuilder().addTransitive(justA).addTransitive(justB).build();
+
+ assertThat(empty.getDepth()).isEqualTo(0);
+ assertThat(nestedSetBuilder().addTransitive(empty).addTransitive(empty).build().getDepth())
+ .isEqualTo(0);
+ assertThat(justA.getDepth()).isEqualTo(1);
+ assertThat(justB.getDepth()).isEqualTo(1);
+ assertThat(nestedSetBuilder().addTransitive(empty).addTransitive(empty).build().getDepth())
+ .isEqualTo(0);
+ assertThat(nestedSetBuilder().addTransitive(empty).addTransitive(justA).build().getDepth())
+ .isEqualTo(1);
+ assertThat(nestedSetBuilder().addTransitive(justA).addTransitive(empty).build().getDepth())
+ .isEqualTo(1);
+ assertThat(nestedSetBuilder().addTransitive(justA).addTransitive(justA).build().getDepth())
+ .isEqualTo(1);
+ assertThat(nestedSetBuilder().addTransitive(justA).addTransitive(justB).build().getDepth())
+ .isEqualTo(2);
+ assertThat(
+ nestedSetBuilder("a", "b", "c")
+ .addTransitive(justA)
+ .addTransitive(justB)
+ .addTransitive(ab)
+ .build()
+ .getDepth())
+ .isEqualTo(3);
+ }
}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
index 5846eb8..29c5261 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
@@ -162,6 +162,10 @@
NestedSet<String> s = v.splitIfExceedsMaximumSize(2);
assertThat(s).isNotSameInstanceAs(v);
assertThat(collectCheckSize(s, 2)).containsExactly("a", "b", "c", "d", "e");
+
+ // Splitting may increment the graph depth, possibly more than once.
+ assertThat(v.getDepth()).isEqualTo(2);
+ assertThat(s.getDepth()).isEqualTo(4);
}
private static <T> List<T> collectCheckSize(NestedSet<T> set, int maxSize) {
diff --git a/src/test/java/com/google/devtools/build/lib/packages/StarlarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/StarlarkSemanticsConsistencyTest.java
index 212a2f6..6aa52d5 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/StarlarkSemanticsConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/StarlarkSemanticsConsistencyTest.java
@@ -119,7 +119,6 @@
private static StarlarkSemanticsOptions buildRandomOptions(Random rand) throws Exception {
return parseOptions(
// <== Add new options here in alphabetic order ==>
- "--debug_depset_depth=" + rand.nextBoolean(),
"--experimental_action_args=" + rand.nextBoolean(),
"--experimental_disable_external_package=" + rand.nextBoolean(),
"--experimental_sibling_repository_layout=" + rand.nextBoolean(),
@@ -173,7 +172,6 @@
private static StarlarkSemantics buildRandomSemantics(Random rand) {
return StarlarkSemantics.builder()
// <== Add new options here in alphabetic order ==>
- .debugDepsetDepth(rand.nextBoolean())
.experimentalActionArgs(rand.nextBoolean())
.experimentalDisableExternalPackage(rand.nextBoolean())
.experimentalSiblingRepositoryLayout(rand.nextBoolean())
diff --git a/src/test/shell/integration/starlark_flag_test.sh b/src/test/shell/integration/starlark_flag_test.sh
index 2ca12f1..aad02c8 100755
--- a/src/test/shell/integration/starlark_flag_test.sh
+++ b/src/test/shell/integration/starlark_flag_test.sh
@@ -244,11 +244,11 @@
bazel build //test:test --nested_set_depth_limit=500 &> $TEST_log \
&& fail "Build should have failed at depth limit 500"
- expect_log "depset exceeded maximum depth 500"
+ expect_log "depset depth 501 exceeds limit (500)"
bazel build //test:test --nested_set_depth_limit=100 &> $TEST_log \
&& fail "Build should have failed at depth limit 100"
- expect_log "depset exceeded maximum depth 100"
+ expect_log "depset depth 101 exceeds limit (100)"
bazel build //test:test --nested_set_depth_limit=3000 &> $TEST_log \
|| fail "Build should have succeeded at depth limit 3000"
