Roll back https://github.com/bazelbuild/bazel/commit/ed9d6390eb78303631c25b3d4776cb07eeded544 due to memory regression.
PiperOrigin-RevId: 315934735
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 d71b44d..7fff89b 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,6 +33,7 @@
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;
@@ -651,11 +652,23 @@
private static void assertExecutableSymlinkPresent(
Runfiles runfiles, Artifact executable, Location loc) throws EvalException {
- // 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");
+ 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.");
}
}
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 a26131c..ba3a521 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,6 +15,7 @@
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;
@@ -28,7 +29,6 @@
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,7 +341,18 @@
+ "on the depset and vice versa.",
useStarlarkThread = true)
public StarlarkList<Object> toListForStarlark(StarlarkThread thread) throws EvalException {
- return StarlarkList.copyOf(thread.mutability(), this.toList());
+ 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.");
+ }
}
/** Create a Depset from the given direct and transitive components. */
@@ -548,13 +559,17 @@
result = legacyDepsetConstructor(items, order, direct, transitive, semantics);
}
- // 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);
+ 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());
+ }
}
-
return result;
}
@@ -587,17 +602,4 @@
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 550dc76..fc2ff8c 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,6 +36,7 @@
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;
@@ -85,36 +86,31 @@
// 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 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'.
+ // 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".
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;
- private static final byte[] NO_MEMO = {};
- @AutoCodec static final Object[] EMPTY_CHILDREN = {0};
+ /**
+ * 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 = {};
/** 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 = NO_MEMO;
+ this.memo = LEAF_MEMO;
}
NestedSet(
@@ -149,10 +145,9 @@
// 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[1 + direct.size() + transitive.size()];
- int n = 1; // current position in children array (skip depth slot)
+ Object[] children = new Object[direct.size() + transitive.size()];
+ int n = 0; // current position in children
boolean leaf = true; // until we find otherwise
- int depth = 2;
for (int pass = 0; pass <= 1; ++pass) {
if ((pass == 0) == preorder && !direct.isEmpty()) {
@@ -175,10 +170,9 @@
Object c = subset.getChildrenInternal(interruptStrategy);
if (c instanceof Object[]) {
Object[] a = (Object[]) c;
- if (a.length < 3) {
+ if (a.length < 2) {
throw new AssertionError(a.length);
}
- depth = Math.max(depth, 1 + depth(a));
children[n++] = a;
leaf = false;
} else {
@@ -196,28 +190,27 @@
}
}
- // n == |successors| + 1
// If we ended up wrapping exactly one item or one other set, dereference it.
- if (n == 2) {
- this.children = children[1];
- } else if (n == 1) {
+ if (n == 1) {
+ this.children = children[0];
+ } else if (n == 0) {
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 = NO_MEMO;
+ this.memo = LEAF_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;
+ this.children =
+ children instanceof Object[] && ((Object[]) children).length == 0
+ ? EMPTY_CHILDREN
+ : children;
this.memo = memo;
}
@@ -237,7 +230,7 @@
boolean hasChildren =
children instanceof Object[]
&& (Arrays.stream((Object[]) children).anyMatch(child -> child instanceof Object[]));
- byte[] memo = hasChildren ? null : NO_MEMO;
+ byte[] memo = hasChildren ? null : LEAF_MEMO;
return new NestedSet<>(order, children, memo);
}
@@ -323,9 +316,7 @@
Predicate<Object> descend, Consumer<E> f, Object node) {
if (descend.test(node)) {
if (node instanceof Object[]) {
- Object[] children = (Object[]) node;
- for (int i = 1; i < children.length; i++) { // skip depth
- Object child = children[i];
+ for (Object child : (Object[]) node) {
forEachElementImpl(descend, f, child);
}
} else {
@@ -348,22 +339,6 @@
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.
@@ -541,13 +516,8 @@
*/
private ImmutableList<E> expand(Object[] children) {
// This value is only set in the constructor, so safe to test here with no lock.
- 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
+ if (memo == LEAF_MEMO) {
+ return ImmutableList.copyOf(new ArraySharingCollection<>(children));
}
CompactHashSet<E> members = lockedExpand(children);
if (members != null) {
@@ -584,26 +554,27 @@
/**
* If this is the first call for this object, fills {@code this.memo} and returns a set from
- * {@link #walk}. Otherwise returns null, in which case some other thread must have completely
- * populated memo; the caller should use {@link #replay} instead.
+ * {@link #walk}. Otherwise returns null; 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);
- 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);
+ 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;
if (bytes <= memo.length - 16) {
- memo = Arrays.copyOf(memo, bytes); // shrink to save space
+ memo = Arrays.copyOf(memo, bytes);
}
Preconditions.checkState(members.size() < (Integer.MAX_VALUE >> 2));
orderAndSize |= (members.size()) << 2;
@@ -618,9 +589,16 @@
* <p>Returns the final value of {@code pos}.
*/
private int walk(
- CompactHashSet<Object> sets, CompactHashSet<E> members, Object[] children, int pos) {
- for (int i = 1; i < children.length; i++) { // skip depth
- Object child = children[i];
+ 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) {
if ((pos >> 3) >= memo.length) {
memo = Arrays.copyOf(memo, memo.length * 2);
}
@@ -628,7 +606,7 @@
if (sets.add(child)) {
int prepos = pos;
int presize = members.size();
- pos = walk(sets, members, (Object[]) child, pos + 1);
+ pos = walk(sets, members, (Object[]) child, pos + 1, currentDepth + 1, maxDepth);
if (presize < members.size()) {
memo[prepos >> 3] |= (byte) (1 << (prepos & 7));
} else {
@@ -656,8 +634,7 @@
*/
private static <E> int replay(
ImmutableList.Builder<E> output, Object[] children, byte[] memo, int pos) {
- for (int i = 1; i < children.length; i++) { // skip depth
- Object child = children[i];
+ for (Object child : children) {
if ((memo[pos >> 3] & (1 << (pos & 7))) != 0) {
if (child instanceof Object[]) {
pos = replay(output, (Object[]) child, memo, pos + 1);
@@ -672,67 +649,60 @@
return pos;
}
- // ceildiv(x/y) returns ⌈x/y⌉.
- private static int ceildiv(int x, int y) {
- return (x + y - 1) / y;
+ /**
+ * 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;
+ }
}
/**
- * 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.
+ * 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.
*/
- // 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");
+ public NestedSet<E> splitIfExceedsMaximumSize(int maximumSize) {
+ Preconditions.checkArgument(maximumSize >= 2, "maximumSize must be at least 2");
Object children = getChildren(); // may wait for a future
if (!(children instanceof Object[])) {
return this;
}
- Object[] succs = (Object[]) children;
-
- int nsuccs = succs.length - 1; // skip depth
- if (nsuccs <= maxDegree) {
+ Object[] arr = (Object[]) children;
+ int size = arr.length;
+ if (size <= maximumSize) {
return this;
}
-
- // 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;
+ 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);
}
- // 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);
+ // 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);
}
/** Returns the list of this node's successors that are themselves non-leaf nodes. */
@@ -761,9 +731,7 @@
return ImmutableList.of((E) children);
}
ImmutableList.Builder<E> res = ImmutableList.builder();
- Object[] succs = (Object[]) children;
- for (int i = 1; i < succs.length; i++) { // skip depth
- Object c = succs[i];
+ for (Object c : (Object[]) children) {
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 4e73229..46eddd8 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,9 +79,8 @@
if (children instanceof Object[]) {
if (!digestMap.readDigest(children, fingerprint)) {
Fingerprint childrenFingerprint = new Fingerprint();
- Object[] succs = (Object[]) children;
- for (int i = 1; i < succs.length; i++) { // skip depth
- addToFingerprint(mapFn, childrenFingerprint, digestMap, succs[i]);
+ for (Object child : (Object[]) children) {
+ addToFingerprint(mapFn, childrenFingerprint, digestMap, child);
}
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 851d0f4..5e99a5e 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,15 +33,17 @@
documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
effectTags = {OptionEffectTag.LOADING_AND_ANALYSIS},
help =
- "The maximum depth of the graph internal to a depset (also known as NestedSet), above"
- + " which the depset() constructor will fail.")
+ "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.")
public int nestedSetDepthLimit;
}
@Override
public void beforeCommand(CommandEnvironment env) {
Options options = env.getOptions().getOptions(Options.class);
- boolean changed = Depset.setDepthLimit(options.nestedSetDepthLimit);
+ boolean changed = NestedSet.setApplicationDepthLimit(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 6b9f152..1a36ff9 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,6 +30,7 @@
*
* @param <E> the data type
*/
+// @ThreadSafety.ThreadSafe
public final class NestedSetVisitor<E> {
/**
@@ -76,9 +77,8 @@
private void visitRaw(Object node) {
if (visited.add(node)) {
if (node instanceof Object[]) {
- Object[] children = (Object[]) node;
- for (int i = 1; i < children.length; i++) { // skip depth
- visitRaw(children[i]);
+ for (Object child : (Object[]) node) {
+ visitRaw(child);
}
} 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 2a9ce32..1324ddd 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,6 +64,19 @@
// <== 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,
@@ -641,6 +654,7 @@
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 778019c..da812e8 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,6 +22,7 @@
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;
@@ -611,7 +612,17 @@
if (x instanceof Iterable) {
iterable = (Iterable<?>) x;
} else if (x instanceof Depset) {
- iterable = ((Depset) x).toList();
+ 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.");
+ }
} 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 74c17e3..5f90065 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
- * new NestedSet whose leaf successors are all ExpandedArtifact. Non-leaf successors are
- * unaltered.
+ * weird Frankenstein object with each leaf successor replaced by 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 0b81df0..79ff3d5 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,7 +291,20 @@
+ "str(8) == \"8\"</pre>",
parameters = {@Param(name = "x", doc = "The object to convert.", noneable = true)})
public String str(Object x) throws EvalException {
- return Starlark.str(x);
+ 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;
+ }
}
@StarlarkMethod(
@@ -721,7 +734,19 @@
String separator = "";
for (Object x : args) {
p.append(separator);
- p.debugPrint(x);
+ 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;
+ }
separator = sep;
}
// As part of the integration test "starlark_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 f859597..70c6f43 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,6 +194,8 @@
AutoValue_StarlarkSemantics.class;
// <== Add new options here in alphabetic order ==>
+ public abstract boolean debugDepsetDepth();
+
public abstract boolean experimentalActionArgs();
public abstract boolean experimentalAllowIncrementalRepositoryUpdates();
@@ -309,6 +311,7 @@
public static final StarlarkSemantics DEFAULT =
builder()
// <== Add new options here in alphabetic order ==>
+ .debugDepsetDepth(false)
.experimentalActionArgs(true)
.experimentalAllowTagsPropagation(false)
.experimentalBuiltinsBzlPath("")
@@ -357,6 +360,8 @@
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 3f66420..7990c1d 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,25 +431,19 @@
}
@Test
- public void testConstructorDepthLimit() throws Exception {
+ public void testDepthExceedsLimitDuringIteration() 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])")
- .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)");
+ " 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)");
}
@Test
@@ -514,4 +508,37 @@
+ "--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 41f20ab..83c2397 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,51 +286,50 @@
@Test
public void buildInterruptibly_propagatesInterrupt() {
- NestedSet<String> deserializingNestedSet =
+ NestedSet<String> deserialzingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
NestedSetBuilder<String> builder =
- NestedSetBuilder.<String>stableOrder().addTransitive(deserializingNestedSet).add("a");
+ NestedSetBuilder.<String>stableOrder().addTransitive(deserialzingNestedSet).add("a");
Thread.currentThread().interrupt();
assertThrows(InterruptedException.class, builder::buildInterruptibly);
}
@Test
public void getChildrenInterruptibly_propagatesInterrupt() {
- NestedSet<String> deserializingNestedSet =
+ NestedSet<String> deserialzingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
Thread.currentThread().interrupt();
- assertThrows(InterruptedException.class, deserializingNestedSet::getChildrenInterruptibly);
+ assertThrows(InterruptedException.class, deserialzingNestedSet::getChildrenInterruptibly);
}
@Test
public void toListWithTimeout_propagatesInterrupt() {
- NestedSet<String> deserializingNestedSet =
+ NestedSet<String> deserialzingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
Thread.currentThread().interrupt();
assertThrows(
InterruptedException.class,
- () -> deserializingNestedSet.toListWithTimeout(Duration.ofDays(1)));
+ () -> deserialzingNestedSet.toListWithTimeout(Duration.ofDays(1)));
}
@Test
public void toListWithTimeout_timesOut() {
- NestedSet<String> deserializingNestedSet =
+ NestedSet<String> deserialzingNestedSet =
NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
assertThrows(
- TimeoutException.class,
- () -> deserializingNestedSet.toListWithTimeout(Duration.ofNanos(1)));
+ TimeoutException.class, () -> deserialzingNestedSet.toListWithTimeout(Duration.ofNanos(1)));
}
@Test
public void toListWithTimeout_waits() throws Exception {
SettableFuture<Object[]> future = SettableFuture.create();
- NestedSet<String> deserializingNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, future);
+ NestedSet<String> deserialzingNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, future);
Future<ImmutableList<String>> result =
Executors.newSingleThreadExecutor()
- .submit(() -> deserializingNestedSet.toListWithTimeout(Duration.ofMinutes(1)));
+ .submit(() -> deserialzingNestedSet.toListWithTimeout(Duration.ofMinutes(1)));
Thread.sleep(100);
assertThat(result.isDone()).isFalse();
- future.set(new Object[] {/*depth=*/ 2, "a", "b"});
+ future.set(new Object[] {"a", "b"});
assertThat(result.get()).containsExactly("a", "b");
}
@@ -361,36 +360,4 @@
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 29c5261..5846eb8 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,10 +162,6 @@
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 6aa52d5..212a2f6 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,6 +119,7 @@
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(),
@@ -172,6 +173,7 @@
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 aad02c8..2ca12f1 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 depth 501 exceeds limit (500)"
+ expect_log "depset exceeded maximum depth 500"
bazel build //test:test --nested_set_depth_limit=100 &> $TEST_log \
&& fail "Build should have failed at depth limit 100"
- expect_log "depset depth 101 exceeds limit (100)"
+ expect_log "depset exceeded maximum depth 100"
bazel build //test:test --nested_set_depth_limit=3000 &> $TEST_log \
|| fail "Build should have succeeded at depth limit 3000"
