A "RecursiveConstants" attribute

[Dan Smith]

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> 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]).