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 d8830e5..dd6b43c 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..6cd16d0 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().getApproxDepth();
+    int limit = depthLimit.get();
+    if (depth > limit) {
+      throw Starlark.errorf("depset depth %d exceeds limit (%d)", depth, limit);
     }
+
     return result;
   }
 
@@ -602,4 +587,19 @@
   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;
+  }
+
+  // The effective default value comes from the --nested_set_depth_limit
+  // flag in NestedSetOptionsModule, which overrides this.
+  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 ec6a1cd..81e20eb 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;
@@ -70,8 +69,15 @@
 @SuppressWarnings("unchecked")
 @AutoCodec
 public final class NestedSet<E> {
-  // Order of set, represented as numeric ordinal to save space.
-  private final int orderOrdinal;
+  // The set's order and approximate depth, packed to save space.
+  //
+  // The low 2 bits contain the Order.ordinal value.
+  //
+  // The high 30 bits, of which only about 12 are really necessary, contain the
+  // depth of the set; see getApproxDepth. Because the union constructor discards
+  // the depths of all but the deepest nonleaf child, the sets returned by
+  // getNonLeaves have inaccurate depths that may overapproximate the true depth.
+  private final int depthAndOrder;
 
   // children contains the "direct" elements and "transitive" nested sets.
   // Direct elements are never arrays.
@@ -82,9 +88,13 @@
   //
   // 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 compact encoding of facts computed by a complete traversal.
@@ -103,14 +113,6 @@
   // 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);
-
   // NO_MEMO is the distinguished memo for all nodes of depth < 2, that is,
   // leaf nodes and nodes whose successors are all leaf nodes.
   private static final byte[] NO_MEMO = {};
@@ -119,7 +121,7 @@
 
   /** Construct an empty NestedSet. Should only be called by Order's class initializer. */
   NestedSet(Order order) {
-    this.orderOrdinal = order.ordinal();
+    this.depthAndOrder = order.ordinal();
     this.children = EMPTY_CHILDREN;
     this.memo = NO_MEMO;
   }
@@ -127,8 +129,6 @@
   NestedSet(
       Order order, Set<E> direct, Set<NestedSet<E>> transitive, InterruptStrategy interruptStrategy)
       throws InterruptedException {
-    this.orderOrdinal = order.ordinal();
-
     // The iteration order of these collections is the order in which we add the items.
     Collection<E> directOrder = direct;
     Collection<NestedSet<E>> transitiveOrder = transitive;
@@ -157,8 +157,9 @@
     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
-    boolean shallow = true; // until we find otherwise
+    int approxDepth = 0;
+    int n = 0; // current position in children array
+    boolean shallow = true; // whether true depth < 3
 
     for (int pass = 0; pass <= 1; ++pass) {
       if ((pass == 0) == preorder && !direct.isEmpty()) {
@@ -171,12 +172,14 @@
           }
           if (!alreadyInserted.contains(member)) {
             children[n++] = member;
+            approxDepth = Math.max(approxDepth, 2);
           }
         }
         alreadyInserted = direct;
       } else if ((pass == 1) == preorder && !transitive.isEmpty()) {
         CompactHashSet<E> hoisted = null;
         for (NestedSet<E> subset : transitiveOrder) {
+          approxDepth = Math.max(approxDepth, 1 + subset.getApproxDepth());
           // If this is a deserialization future, this call blocks.
           Object c = subset.getChildrenInternal(interruptStrategy);
           if (c instanceof Object[]) {
@@ -201,27 +204,31 @@
       }
     }
 
-    // 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) {
+    // n == |successors|
+    if (n == 0) {
+      approxDepth = 0;
       this.children = EMPTY_CHILDREN;
-    } else if (n < children.length) {
-      this.children = Arrays.copyOf(children, n);
+    } else if (n == 1) {
+      // If we ended up wrapping exactly one item or one other set, dereference it.
+      approxDepth--;
+      this.children = children[0];
     } else {
+      if (n < children.length) {
+        children = Arrays.copyOf(children, n); // shrink to save space
+      }
       this.children = children;
     }
+    this.depthAndOrder = (approxDepth << 2) | order.ordinal();
+
     if (shallow) {
       this.memo = NO_MEMO;
     }
   }
 
-  private NestedSet(Order order, Object children, @Nullable byte[] memo) {
-    this.orderOrdinal = order.ordinal();
-    this.children =
-        children instanceof Object[] && ((Object[]) children).length == 0
-            ? EMPTY_CHILDREN
-            : children;
+  // Precondition: EMPTY_CHILDREN is used as the canonical empty array.
+  private NestedSet(Order order, int depth, Object children, @Nullable byte[] memo) {
+    this.depthAndOrder = (depth << 2) | order.ordinal();
+    this.children = children;
     this.memo = memo;
   }
 
@@ -230,24 +237,24 @@
    * complete, gives the contents of the NestedSet.
    */
   static <E> NestedSet<E> withFuture(
-      Order order, ListenableFuture<Object[]> deserializationFuture) {
-    return new NestedSet<>(order, deserializationFuture, /*memo=*/ null);
+      Order order, int depth, ListenableFuture<Object[]> deserializationFuture) {
+    return new NestedSet<>(order, depth, deserializationFuture, /*memo=*/ null);
   }
 
   // Only used by deserialization
   @AutoCodec.Instantiator
-  static <E> NestedSet<E> forDeserialization(Order order, Object children) {
+  static <E> NestedSet<E> forDeserialization(Order order, int approxDepth, Object children) {
     Preconditions.checkState(!(children instanceof ListenableFuture));
     boolean hasChildren =
         children instanceof Object[]
             && (Arrays.stream((Object[]) children).anyMatch(child -> child instanceof Object[]));
     byte[] memo = hasChildren ? null : NO_MEMO;
-    return new NestedSet<>(order, children, memo);
+    return new NestedSet<>(order, approxDepth, children, memo);
   }
 
   /** Returns the ordering of this nested set. */
   public Order getOrder() {
-    return Order.getOrder(orderOrdinal & 3);
+    return Order.getOrder(depthAndOrder & 3);
   }
 
   /**
@@ -350,6 +357,18 @@
     return isSingleton(children);
   }
 
+  /**
+   * Returns the approximate 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.
+   *
+   * <p>This function may return an overapproximation of the true depth if the NestedSet was derived
+   * from the result of calling {@link #getNonLeaves} or {@link #splitIfExceedsMaximumSize}.
+   */
+  int getApproxDepth() {
+    return this.depthAndOrder >>> 2;
+  }
+
   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.
@@ -585,10 +604,12 @@
 
   /**
    * 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) {
     // Precondition: this is a non-leaf node with non-leaf successors (depth > 2).
+    // Postcondition: memo is completely populated.
     if (memo != null) {
       return null;
     }
@@ -596,14 +617,7 @@
     CompactHashSet<Object> sets = CompactHashSet.createWithExpectedSize(128);
     sets.add(children);
     memo = new byte[3 + Math.min(ceildiv(children.length, 8), 8)]; // (+3 for size: a guess)
-    int pos =
-        walk(
-            sets,
-            members,
-            children,
-            /* pos= */ 0,
-            /* currentDepth= */ 1,
-            expansionDepthLimit.get());
+    int pos = walk(sets, members, children, /*pos=*/ 0);
     int bytes = ceildiv(pos, 8);
 
     // Append (nonzero) size to memo, in reverse varint encoding:
@@ -650,15 +664,7 @@
    * <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);
-    }
+      CompactHashSet<Object> sets, CompactHashSet<E> members, Object[] children, int pos) {
     for (Object child : children) {
       if ((pos >> 3) >= memo.length) {
         memo = Arrays.copyOf(memo, memo.length * 2);
@@ -667,7 +673,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 {
@@ -711,59 +717,36 @@
   }
 
   /**
-   * 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
+   * 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 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 logical graph
-   * with the specified maximum out-degree, which must be at least 2. 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;
+    if (nsuccs <= maxDegree) {
       return this;
     }
-    Object[][] pieces = new Object[ceildiv(size, maximumSize)][];
+    Object[][] pieces = new Object[ceildiv(nsuccs, maxDegree)][];
     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);
+      int max = Math.min((i + 1) * maxDegree, succs.length);
+      pieces[i] = Arrays.copyOfRange(succs, i * maxDegree, max);
     }
+    int depth = getApproxDepth() + 1; // may be an overapproximation
 
-    // 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);
+    // TODO(adonovan): (preexisting): if the last piece is a singleton, it must be inlined.
+
+    // 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(), depth, pieces, null).splitIfExceedsMaximumSize(maxDegree);
   }
 
   /** Returns the list of this node's successors that are themselves non-leaf nodes. */
@@ -775,7 +758,8 @@
     ImmutableList.Builder<NestedSet<E>> res = ImmutableList.builder();
     for (Object c : (Object[]) children) {
       if (c instanceof Object[]) {
-        res.add(new NestedSet<>(getOrder(), c, null));
+        int depth = getApproxDepth() - 1; // possible overapproximation
+        res.add(new NestedSet<>(getOrder(), depth, c, null));
       }
     }
     return res.build();
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
index 444db9d..595f092 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
@@ -32,7 +32,9 @@
 public class NestedSetCodecWithStore implements ObjectCodec<NestedSet<?>> {
 
   private enum NestedSetSize {
-    EMPTY, SINGLETON, GROUP
+    EMPTY, // distinguished empty node; size = 0, depth = 0
+    LEAF, // a single element; size = 1, depth = 1
+    NONLEAF // more than one element; size > 1, depth > 1
   }
 
   private final NestedSetStore nestedSetStore;
@@ -75,10 +77,11 @@
       codedOut.writeEnumNoTag(NestedSetSize.EMPTY.ordinal());
     } else if (obj.isSingleton()) {
       // If the NestedSet is a singleton, we serialize directly as an optimization.
-      codedOut.writeEnumNoTag(NestedSetSize.SINGLETON.ordinal());
+      codedOut.writeEnumNoTag(NestedSetSize.LEAF.ordinal());
       context.serialize(obj.getChildren(), codedOut);
     } else {
-      codedOut.writeEnumNoTag(NestedSetSize.GROUP.ordinal());
+      codedOut.writeEnumNoTag(NestedSetSize.NONLEAF.ordinal());
+      context.serialize(obj.getApproxDepth(), codedOut);
       FingerprintComputationResult fingerprintComputationResult =
           nestedSetStore.computeFingerprintAndStore((Object[]) obj.getChildren(), context);
       context.addFutureToBlockWritingOn(fingerprintComputationResult.writeStatus());
@@ -95,12 +98,13 @@
     switch (nestedSetSize) {
       case EMPTY:
         return NestedSetBuilder.emptySet(order);
-      case SINGLETON:
+      case LEAF:
         Object contents = context.deserialize(codedIn);
-        return intern(order, contents);
-      case GROUP:
+        return intern(order, 1, contents);
+      case NONLEAF:
+        int depth = context.deserialize(codedIn);
         ByteString fingerprint = ByteString.copyFrom(codedIn.readByteArray());
-        return intern(order, nestedSetStore.getContentsAndDeserialize(fingerprint, context));
+        return intern(order, depth, nestedSetStore.getContentsAndDeserialize(fingerprint, context));
     }
     throw new IllegalStateException("NestedSet size " + nestedSetSize + " not known");
   }
@@ -127,12 +131,12 @@
    * not before. This should be ok as long as the contained object properly implements equality.
    */
   @SuppressWarnings("unchecked")
-  private NestedSet<?> intern(Order order, Object contents) {
+  private NestedSet<?> intern(Order order, int depth, Object contents) {
     NestedSet<?> result;
     if (contents instanceof ListenableFuture) {
-      result = NestedSet.withFuture(order, (ListenableFuture<Object[]>) contents);
+      result = NestedSet.withFuture(order, depth, (ListenableFuture<Object[]>) contents);
     } else {
-      result = NestedSet.forDeserialization(order, contents);
+      result = NestedSet.forDeserialization(order, depth, contents);
     }
     try {
       return interner.get(new EqualsWrapper(result), () -> result);
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..804d0b3 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> {
 
   /**
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 828fc47..30e371c 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,
@@ -666,7 +653,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 79ff3d5..0b81df0 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 "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 cfafb13..91d35d5 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
@@ -198,8 +198,6 @@
       AutoValue_StarlarkSemantics.class;
 
   // <== Add new options here in alphabetic order ==>
-  public abstract boolean debugDepsetDepth();
-
   public abstract boolean experimentalActionArgs();
 
   public abstract boolean experimentalAllowIncrementalRepositoryUpdates();
@@ -317,7 +315,6 @@
   public static final StarlarkSemantics DEFAULT =
       builder()
           // <== Add new options here in alphabetic order ==>
-          .debugDepsetDepth(false)
           .experimentalActionArgs(true)
           .experimentalAllowTagsPropagation(false)
           .experimentalBuiltinsBzlPath("")
@@ -367,8 +364,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 d7f9a21..48b9751 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
@@ -190,14 +190,18 @@
     return new SetWrapper<>(builder.build());
   }
 
+  private static final int UNKNOWN_DEPTH = 7;
+
   @Test
   public void shallowEquality() {
     // Used below to check that inner nested sets can be compared by reference equality.
     SetWrapper<Integer> myRef = nest(nest(flat(7, 8)), flat(9));
     // Used to check equality for deserializing nested sets
     ListenableFuture<Object[]> contents = Futures.immediateFuture(new Object[] {"a", "b"});
-    NestedSet<String> referenceNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, contents);
-    NestedSet<String> otherReferenceNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, contents);
+    NestedSet<String> referenceNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, contents);
+    NestedSet<String> otherReferenceNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, contents);
 
     // Each "equality group" contains elements that are equal to one another
     // (according to equals() and hashCode()), yet distinct from all elements
@@ -231,15 +235,18 @@
     assertThat(nestedSetBuilder("a").build().shallowEquals(null)).isFalse();
     Object[] contents = {"a", "b"};
     assertThat(
-            NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents))
+            NestedSet.withFuture(
+                    Order.STABLE_ORDER, UNKNOWN_DEPTH, Futures.immediateFuture(contents))
                 .shallowEquals(null))
         .isFalse();
 
     // shallowEquals() should require reference equality for underlying futures
     assertThat(
-            NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents))
+            NestedSet.withFuture(
+                    Order.STABLE_ORDER, UNKNOWN_DEPTH, Futures.immediateFuture(contents))
                 .shallowEquals(
-                    NestedSet.withFuture(Order.STABLE_ORDER, Futures.immediateFuture(contents))))
+                    NestedSet.withFuture(
+                        Order.STABLE_ORDER, UNKNOWN_DEPTH, Futures.immediateFuture(contents))))
         .isFalse();
   }
 
@@ -334,47 +341,49 @@
 
   @Test
   public void buildInterruptibly_propagatesInterrupt() {
-    NestedSet<String> deserialzingNestedSet =
-        NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
+    NestedSet<String> deserializingNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, 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.withFuture(Order.STABLE_ORDER, SettableFuture.create());
+    NestedSet<String> deserializingNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, SettableFuture.create());
     Thread.currentThread().interrupt();
-    assertThrows(InterruptedException.class, deserialzingNestedSet::getChildrenInterruptibly);
+    assertThrows(InterruptedException.class, deserializingNestedSet::getChildrenInterruptibly);
   }
 
   @Test
   public void toListWithTimeout_propagatesInterrupt() {
-    NestedSet<String> deserialzingNestedSet =
-        NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
+    NestedSet<String> deserializingNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, 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.withFuture(Order.STABLE_ORDER, SettableFuture.create());
+    NestedSet<String> deserializingNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, 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, UNKNOWN_DEPTH, 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"});
@@ -384,7 +393,7 @@
   @Test
   public void isFromStorage_true() {
     NestedSet<?> deserializingNestedSet =
-        NestedSet.withFuture(Order.STABLE_ORDER, SettableFuture.create());
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, SettableFuture.create());
     assertThat(deserializingNestedSet.isFromStorage()).isTrue();
   }
 
@@ -403,9 +412,48 @@
   @Test
   public void isReady_fromStorage() {
     SettableFuture<Object[]> future = SettableFuture.create();
-    NestedSet<?> deserializingNestedSet = NestedSet.withFuture(Order.STABLE_ORDER, future);
+    NestedSet<?> deserializingNestedSet =
+        NestedSet.withFuture(Order.STABLE_ORDER, UNKNOWN_DEPTH, future);
     assertThat(deserializingNestedSet.isReady()).isFalse();
     future.set(new Object[] {"a", "b"});
     assertThat(deserializingNestedSet.isReady()).isTrue();
   }
+
+  @Test
+  public void getApproxDepth() {
+    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.getApproxDepth()).isEqualTo(0);
+    assertThat(
+            nestedSetBuilder().addTransitive(empty).addTransitive(empty).build().getApproxDepth())
+        .isEqualTo(0);
+    assertThat(justA.getApproxDepth()).isEqualTo(1);
+    assertThat(justB.getApproxDepth()).isEqualTo(1);
+    assertThat(
+            nestedSetBuilder().addTransitive(empty).addTransitive(empty).build().getApproxDepth())
+        .isEqualTo(0);
+    assertThat(
+            nestedSetBuilder().addTransitive(empty).addTransitive(justA).build().getApproxDepth())
+        .isEqualTo(1);
+    assertThat(
+            nestedSetBuilder().addTransitive(justA).addTransitive(empty).build().getApproxDepth())
+        .isEqualTo(1);
+    assertThat(
+            nestedSetBuilder().addTransitive(justA).addTransitive(justA).build().getApproxDepth())
+        .isEqualTo(1);
+    assertThat(
+            nestedSetBuilder().addTransitive(justA).addTransitive(justB).build().getApproxDepth())
+        .isEqualTo(2);
+    assertThat(
+            nestedSetBuilder("a", "b", "c")
+                .addTransitive(justA)
+                .addTransitive(justB)
+                .addTransitive(ab)
+                .build()
+                .getApproxDepth())
+        .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..a736e41 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.getApproxDepth()).isEqualTo(2);
+    assertThat(s.getApproxDepth()).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 63f2d10..0d5730b 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(),
@@ -174,7 +173,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"