tree 5a4728a6c6cda562cf8ff73a53248773a386800f
parent 04028ef5da253b3a1406d9f60399f2e7fbe6ca34
author adonovan <adonovan@google.com> 1591816552 -0700
committer Copybara-Service <copybara-worker@google.com> 1591816678 -0700

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