A "RecursiveConstants" attribute

[Karen Kinnear]

Dan H,

Thank you for the suggestion. I need to study this in more detail. 

Would it work for you if we finalize the latest Condy JVMS that Dan S sent out and look into
recursion handling in more detail as part of a future cycle?

http://mail.openjdk.java.net/pipermail/valhalla-spec-experts/2018-January/000505.html <http://mail.openjdk.java.net/pipermail/valhalla-spec-experts/2018-January/000505.html>

thanks,
Karen

> On Jan 19, 2018, at 3:11 PM, Dan Smith <daniel.smith at oracle.com> 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]).
>