A "RecursiveConstants" attribute

[Brian Goetz]

It seems to me that the rational thing to do is, in SE 11, to implicitly 
assume max-depth is zero, and be done.  (IE, pretend to implement this 
proposal, but don't actually allow classfiles to have the attribute.)  
Then we won't get any classfiles that have cycles, and the full spectrum 
of cycle-accepting approaches is still on the table.

This proposal is essentially about *enabling* recursive constants in the 
classfile; one would not need a RC attribute if one has no 
self-reference in the CP.  But allowing cycles merely creates a bigger 
problem down the road -- how should bytecode readers present such a 
recursive constant using the symbolic reference API?  You can't 
construct such a thing with the API we have, and that's by design; the 
API has been designed to be value-based (and let compilers intern away 
the duplication).  So allowing controlled cycles in the classfile still 
doesn't address the question of how to build a symbolic reference for 
them.  The result will probably be classfiles that blow up when you try 
to parse them -- not good.

What use cases are we really concerned about here?  I may have missed 
the meeting where these cases were brought up, but it feels a little bit 
like we're extrapolating from a single example (or maybe a single 
Future<Example>).







On 1/19/2018 3:11 PM, Dan Smith wrote:
> We had the following discussion in the Dec 20 meeting:
>
>> On Jan 3, 2018, at 9:11 AM, Karen Kinnear <Karen.Kinnear at oracle.com 
>> <mailto:Karen.Kinnear at oracle.com>> wrote:
>>
>> Dan S: Cycle handling
>> Array types can have cycles
>>   - rather than relying on ordering - perhaps tell tree depth - e.g. 
>> component type & dimensions - all in the CP
>> John: perhaps modify to include the depth indicators in an attribute 
>> (separate proof of acyclicity)
>> Remi: but if you insert a condy …
>> John: would need to discard the attribute
>> Dan H: concern about a constant array for each dimension
>> ? maybe some adhoc compression techniques
>> Remi: why do you want to be cycle free?
>> Dan S: hard to verify if types cyclical?
>> Remi: why do you need to check in the verifier?
>> John: maybe a structural constraint?
>> Remi: if value - ok, but not for an array of values?
>>   e.g. Object[] with first entity as itself
>> Dan: want array type convertible to finite string, benefit of 
>> attribute not tied to construct is it can evolve
>>
>> Dan H: Concerns about attributes - will this be as hard to maintain 
>> for e.g. class redefiners/bytecode generators as stackmaptables?
>> No - you have to keep the CP indices in sync, but stackmaptables 
>> required abstract interpretation - transformer
>> did not have the type information, and the compression mechanism was 
>> harder to implement and these
>> would just require bumping indices.
>
> To flesh the attribute idea out, here's a possible spec. Mentions 
> CONSTANT_Dynamic for now, and would be modified in the future to name 
> other constant types that allow cycles.
>
> Is this a happy solution to the problems raised in previous 
> discussions about constant cycles? Any new problems introduced?
>
> —Dan
>
>
> 4.7.28 The `RecursiveConstants` Attribute (new)
> -----------------------------------------
>
> The `RecursiveConstants` attribute is a variable-length attribute in 
> the `attributes` table of a `ClassFile` structure ([4.1]). The 
> `RecursiveConstants` attribute facilitates checks that a 
> `CONSTANT_Dynamic` entry in the `constant_pool` table does not refer, 
> directly or indirectly, to itself ([4.4.13]).
>
> ~~~~
> RecursiveConstants_attribute {
>     u2 attribute_name_index;
>     u4 attribute_length;
>     u2 num_recursive_constants;
>     {   u2 constant_index;
>         u2 max_recursion_depth;
>     } recursive_constants[num_recursive_constants];
> }
> ~~~~
>
> The items in the `RecursiveConstants_attribute` structure are as follows:
>
> `attribute_name_index`
>
> :  The value of the `attribute_name_index` item must be a valid index 
> into the `constant_pool` table. The `constant_pool` entry at that 
> index must be a `CONSTANT_Utf8_info` structure ([4.4.7]) representing 
> the string `"RecursiveConstants"`.
>
> `attribute_length`
>
> : The value of the `attribute_length` item indicates the length of the 
> attribute, excluding the initial six bytes.
>
> `num_recursive_constants`
>
> : The value of the `num_recursive_constants` item gives the number of 
> entries in the `recursive_constants` array.
>
> `recursive_constants`
>
> : Each entry in the `recursive_constants` table contains the following 
> two items:
>
>     `constant_index`
>     : The value of `constant_index` must be a valid index into the 
> `constant_pool` table. The `constant_pool` entry at that index must be 
> a `CONSTANT_Dynamic` structure ([4.4.13]).
>         There may be at most one entry in the `recursive_constants` 
> table for each `CONSTANT_Dynamic` structure in the `constant_pool`.
>     `max_recursion_depth`
>     : The value of `max_recursion_depth` designates a _maximum 
> recursion depth_ for the referenced constant.
>
>
> 4.4.13 The `CONSTANT_Dynamic_info` Structure (modified)
> --------------------------------------------
>
> The `CONSTANT_Dynamic_info` structure is used to describe a 
> _dynamically-computed constant_, an arbitrary primitive or reference 
> value produced by invocation of a _bootstrap method_ ([4.7.23]). The 
> structure specifies i) a bootstrap method handle with an optional 
> sequence of _static arguments_ and ii) a referenced name and type.
>
> ~~~~
> CONSTANT_Dynamic_info {
>    u1 tag;
>    u2 bootstrap_method_attr_index;
>    u2 name_and_type_index;
> }
> ~~~~
>
> The items of the `CONSTANT_Dynamic_info` structure are as follows:
>
> `tag`
>
> : The `tag` item of the `CONSTANT_Dynamic_info` structure has the value
> `CONSTANT_Dynamic` (17).
>
> `bootstrap_method_attr_index`
>
> : The value of the `bootstrap_method_attr_index` item must be a valid 
> index into the `bootstrap_methods` array of the bootstrap method table 
> ([4.7.23]) of this class file.
>
>     **The _maximum recursion depth_ of a `CONSTANT_Dynamic` structure 
> is the value given by `max_recursion_depth` of an entry referencing 
> the `CONSTANT_Dynamic` structure in the `recursive_constants` table of 
> the `RecursiveConstants` attribute ([4.7.28]); or, if no such entry 
> exists, 0. Let _d_ be the maximum recursion depth of this 
> `CONSTANT_Dynamic_info` structure. For each item in the 
> `bootstrap_arguments` array of the `bootstrap_methods` entry 
> referenced by `bootstrap_method_attr_index`, if the item references a 
> `CONSTANT_Dynamic_info` structure, the maximum recursion depth of that 
> structure must be less than (and not equal to) _d_.**
>
>     > **This check prevents a `CONSTANT_Dynamic_info` structure from 
> referring to itself via one of its static arguments.**
>
> `name_and_type_index`
>
> : The value of the `name_and_type_index` item must be a valid index 
> into the `constant_pool` table. The `constant_pool` entry at that 
> index must be a `CONSTANT_NameAndType_info` structure ([4.4.6]) 
> representing a name and field descriptor ([4.3.2]).
>