commit 621559cb02a4408b957932dc90bc3a0b7f9d1b23
author adonovan <adonovan@google.com> Tue Jun 16 07:21:58 2020 -0700
committer Copybara-Service <copybara-worker@google.com> Tue Jun 16 07:23:19 2020 -0700
tree d50b2b9f9e8b28d4b4c0fe514d34322a2dc03b22
parent 474c53094133ab1eb8dce16da036f4290290c77e

bazel collect: simplify NestedSet depth limit check

(Second attempt at commit ed9d6390eb78303631c25b3d4776cb07eeded544, which was rolled back in commit 867d232f27aa762d4b15e811df18b1939cc1a34b.)

This change causes NestedSet to record the depth of the graph,
exposed to the package as NestedSet.getApproxDepth().

To save space, we squirrel the value into the 30 bits liberated by the
removal of the size field, which since commit ea5ec545fbcf815163e419a0e853f65527028acf is now recorded
in the memo field, along with the traversal replay information.
The previous attempt recorded the depth in the graph, but this led
to a greater than expected RAM regression, of about 1%, causing it
to be rolled back.

This approach in this CL has a significant drawback: because NestedSet
is just a wrapper around the Object[] array that represents the graph
node, the depth is not durably recorded in the graph, as it was in the
previous approach. The union constructor effectively discards the depth of
all direct successors except the deepest, thus the getNonLeaves method cannot
restore the correct depth, so the NestedSets it returns may report a depth
larger than their true depth.

Having access to the (approximate) depth in constant time, without flattening,
allows the Starlark depset constructor to 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 could in principle add explicit checks at important boundaries, such as
rule construction, provider construction, and so on.
(That said, getApproxDepth is currently not public.)
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: 316676111