What's in a CONSTANT_Class?

John Rose john.r.rose at oracle.com
Wed Jun 14 21:55:23 UTC 2017

On Jun 14, 2017, at 9:22 AM, Remi Forax <forax at univ-mlv.fr> wrote:
> With my ASM Hat,
> both CONSTANT_Class_info “;Q<name>” and CONSTANT_ValueType_info that references an UTF8 are Ok for me.

Between those two I prefer the first since it doesn't require a new CP tag.

> Weirdly, having a CONSTANT_Value_info that reference a CONSTANT_Class_info is little harder to implement because the implementation of ASM is sensitive to the number of levels of indirection (it's hardcoded to be 4, a constant method handle has 4 levels).

Interesting fact.  Won't that have to change with condy?
That allows bootstrap specifications to be recursive.

> On the longer term, I think that the spec of CONSTANT_Class should changed to accept a class descriptor and not a class name (which is not BTW because array are accepted in order to encode a method call to an array clone()).
> It will allow more sharing and unlike a class name, a class descriptor is an extensible format.

[Flat strings won't take us there]

Remi, flat strings don't go far enough.  They are moderately
extensible, and certainly accommodate new ground types like
QFoo; and UFoo;, but there are two big problems.  First, they
suffer from combinatorial explosion (*less* sharingin flat strings)
and second they incompletely support expression-holes which
are required when we get to generics.

We live with the combinatorial problems of method type descriptors,
but I think that's a place we want to retreat from. (Look at the encoding
of (Object,Object,Object)Object:  The flatness requires repetition of
the whole qualified name four times, just in this one descriptor.)

When we go to parameterized types, ground types will have multiple
levels of nesting, which turns the problem from quadratic to
exponential.  That that point it's more than today's irritant.

You can patch this with repeat operators, but the natural format
is a tree, which represents all subparts uniformly, rather than some
as a defining use, and others as repeated uses.

[String-tagged shallow trees]

For non-ground generic types, a type string could to be something
like a format string.  (The format "hello, %s" has a string-typed hole.)
In that case, the string doesn't give you everything you need;
it must be joined by a vector of operands.  At that point you've
invented trees, and then the real question is whether tree nodes
should be tagged by format strings (an infinite number of them)
or by a handful of simple CP-style tags.

I handled both these issues in Pack200 by with the CONSTANT_Signature
CP type (present only in Pack200 archives), whose content is a format
string (with N>=0 holes) plus an implicitly counted vector of (N) CP refs
of type CONSTANT_Class.  (Primitives are inlined.)  For technical
reasons the hole syntax, if any, must be different from either string
format notations and Pack200 with future JVMs; I think it should be
a simple period '.'.  (For discussion signature meta-characters see
my "Symbolic Freedom" manifesto ca. 2008.)

For values+generics we'll probably want to look at an experimental design
like this that uses string-tagged tree nodes.  They are very compact (hence
their use in Pack200).

[Byte-tagged deep trees]

But I think for ease of tooling we will end up with the other option,
which is *more* tree nodes tagged by a very small finite set of
CP-style tags.  This is why I support designs like the ones
Dan has been sketching.

In that style of tree, a format string like "hello, %s" breaks down into
nested AST (Append[Literal["hello, "],Param[]]).  Instead of parsing
the string to find holes, the holes are directly represented, along
with every other part, in a strongly-typed AST tree.

An advantage of Dan-style trees is they are more strongly normalizing.
With the format-based trees you always have small types sliding inline
into the format strings, or out as explicit nodes (for uses like ldc).
The programmer's educated instincts prefer one way to say one
thing, rather than many ways to say the same thing.  Stronger
normalization leads to better compactness and fewer bugs.

[Constant inlining?]

Dan-style trees *could* be made much more compact, comparable
to format strings, by extending the CP to support inlining of constant
expressions into other expressions.  This weakens the strong normalization
of constants, but at a lower level where it can be hidden; constants
presented via tools like ASM can be normalized easily, with a single
clever rule ("unwind the inlining by making temporary CP nodes").
ASM does stuff like this in reverse already, by interning ("normalizing")

We probably need something like this anyway, for the future
CONSTANT_Group syntax, which doesn't pay for itself if it has to
burn its way through the limited (u2) index space of the CP; so it
needs some form of inlining, for constants that occur only inside
the group and don't need global sharing.

> From the VM point of view, it's easy to know if a CONSTANT_Class is a descriptor or not, if it's a descriptor, the last character is a ';'.

Actually, for the proposed extension, you look at the *first* character to see
if it is a ';'.  It's a different place (already existing) in the system where you
check to see whether the name is of the form Foo or "LFoo;", and strip
the decorations in the latter case.  You *could* get away with Class["QFoo;"]
but I don't recommend it, because it's a little harder to decode for both
human readers and parsers.

> I also think that the bytecode version corresponding to 10 should requires that all CONSTANT_Class are encoded as class descriptor.  

If I understand what you are saying, that's not MVT at all, since it
would force a revolution in tools.  So we won't do that.  It's overwhelmingly
likely that legacy uses of CONSTANT_Class will coexist with new
CP forms for multiple releases, even if this gives up the advantages
of normal forms.

[In the crystal ball]

Beyond MVT, the CONSTANT_Class[";QFoo;"] wants to become either
a Pack200 style thing like this:

  CONSTANT_Type[format="Q.;", args={ClassFile["Foo"]}]

or (preferentially) a Dan-tree-like thing like this:

  CONSTANT_ClassType[mode=Q, class=ClassFile["Foo"]]

— John

P.S. [Side notes on CP-ology]

When I write CP AST I like to omit "CONSTANT_" from
nested nodes, and elide Utf8 nodes completely around strings.
Makes it almost like a real notation.

Format-strings for CP nodes would use a previously-unusable
character for a hole; the period '.' fits nicely and looks like a hole.
The arity of the node is determined Pack200-style by counting
the holes, or else with an explicit u2 field. Pack200 simply counts
the 'L' characters, but this breaks down with 'Q' and 'U'.

Note that both format-strings and proper trees supply a solution
for the quadratic length of method type descriptors.  Pack200
uses CONSTANT_Signature for both method and field types.

CONSTANT_Signature["(L;L;L;)L;", Class("Object"), Class("Object"),
    Class("Object"), Class("Object")]  # one child node mentioned 4x

More information about the valhalla-spec-observers mailing list