Questions on Template Classes proposal
John Rose
john.r.rose at oracle.com
Thu Mar 14 03:44:36 UTC 2019
This is going to be a fun conversation. As you know, I've been quietly
hammering on a new version of templates for weeks and have (re-)discovered
a number of hard problems, plus some solutions. Thanks so much for
making a close reading of the previous draft; your questions are greatly
improving the new draft.
First I'll respond to Brian's comments, then go through Karen's.
> On Mar 13, 2019, at 11:21 AM, Brian Goetz <brian.goetz at oracle.com> wrote:
>
>
> Some quick answers…
>
>
>> • Where in the template class file are holes allowed? "almost anywhere in the constant pool”
Short answer (explanations below): A specialized hole is a loadable constant
(used by condy, ldc, etc.). In addition, a specialized hole can filter a couple
of new "descriptor patching" operators in the constant pool, assuming the
hole contains an appropriate type or type sentinel ("erased").
> The constant pool is divided into “segments”, and the holes are a property of the segment. In the original doc, the constraint was that the holes were the first N constants in the segment. An alternate way to do this is how M3 did it, where there was a “table of contents” early in the classfile, which enumerated the segments, and identified the holes that go with each.
>
> Whether a hole is defined by a constant pool entry or an entry in a segment table is largely a “syntax” choice.
>
> Since each segment is associated with a number of holes, and classes/members are associated with segments, it stands to reason that we need to type-check the relationship between the number and kinds of holes in a segment, and an attempt to specialize the class or method defined in that segment. If I have a segment with two holes of kind “TYPE”, its probably an error to instantiate it with three type parameters, or parameters that are not of kind TYPE. (Though there may be some need to support mismatches for reasons of compatible evolution.)
>
>
> Where we would previously reference a class (Constant_Class, or LFoo; descriptor), we instead need a way to reference a species. The M3 document showed one way to do this; a ParamType constant, which captures the template name and the parameters. Then, a species is allowed basically anywhere a class was previously — in descriptor strings, in Constant_Class, as the operand of a new/checkcast/instanceof, as the owner of a Field or Method ref, etc.
The forthcoming draft of the template class proposal takes this approach,
with some superficial changes (versus M3) in the way the CP data are
organized. One oddity in my updated template proposal is that it makes
descriptors (both field and method descriptors) patchable via a uniform
mechanism.
Thus, there are more places where the JVMS applies "bimorphically" to
both field and method descriptors; the way you patch holes in a field
type is the same way you patch holes in a method type.
Also, the special role of the "erased" sentinel is moved out of the JVMS,
with (instead) a mechanism for replacing a descriptor which "fails" with
another descriptor nominated by the compiler. (I hope this has more
uses than just patching "erased" sentinels per se. The result should be
the same as for M3, with more tricks in the back pocket.)
In the following explanations you may with to consult this diagram of
constant pool relations, which is derived from my current draft:
http://cr.openjdk.java.net/~jrose/values/template-jvms-4.4.pdf
In order to feed the enhanced descriptors back into uses of CONSTANT_Class,
the latter is allowed to consume a patched field descriptor, if it names a
class or interface or array (not a primitive). If the CONSTANT_Class consumes
a plain Utf8 string it's not a descriptor, as we have today.
The patching operator is called CONSTANT_Descriptor; it takes a template
string with marked holes and a variable number of CP references. There
is also an alternation operator CONSTANT_DefaultType to handle the
choice between non-type sentinels like "erased" (or in general
non-denotable types), and their compiler-assigned bounds.
I found an optional trick to avoid variadic CP entries: The CONSTANT_Descriptor
is followed by enough blank constant pool entries to hold the data, even if
CP entries are fixed in size. (There is a tag CONSTANT_Extra to hold the
space, which makes class files easier to parse. Such constants are useless.
We can also break the glass and make these CP fields variadic, but I remember
we chose *not* to do that for indy constants. We could also use an attribute
to carry the variadic information, as with BootstrapMethods. I don't really
care.)
So the bytecodes which refer to CONSTANT_Class still do so, without exception.
And CONSTANT_Methodref and its two brothers also refer uniformly to
CONSTANT_Class. That's my current take on how to conserve complexity
relative to the present JVMS.
As in the previous draft of template classes, there is also a CONSTANT_Hole
constant. The holes are the first move in the game, and require a patching
mechanism, such as the one Brian described or I just described.
To approach an answer to Karen's question: A CONSTANT_Hole is tightly associated
with a segment. In fact, the current draft requires that each CP segment occupies
a *contiguous* series of CP slots, and that the holes must be the first entries
in the segment. Actually, the first entry of all is a CONSTANT_Segment structure,
followed by its holes. This is similar to the CONSTANT_Descriptor followed
by CONSTANT_Extra structures that it requires; I'm using the same tactic
for variadic CP entries in both cases. But (unlike CONSTANT_Extra constants)
the CONSTANT_Holes are individually addressable. The CONSTANT_Segment
is also addressable as an opaque constant; this may be be useful for doing
certain complicated inter-segment operations; a condy may take one or more
reified segments as inputs, for example.
The specific list of uses of a CONSTANT_Hole is an interesting design question,
which I'm sure we will discuss. My current take on this is to make it happen in
fewer places, rather than more, and mediate holes through CONSTANT_Class
constants. This corrals the design complexity into a smaller space, that of
descriptor patching. It does create more CP entries, so at some point (much
later) we may wish to allow some users of CONSTANT_Class constants to
"short circuit" straight through to whatever the CONSTANT_Class points at.
I'd rather not do this in the first draft. More details later.
Not in the current draft: We could relax the restriction that segments must
occupy contiguous spans of slots in the CP, either allowing a single segment
to be sprinkled throughout the CP, or else having segments somehow occupy
a completely different set of CP indexes, such as downward from 0xFFFF.
In my enthusiasm, I wrote up a JVMS section for the first option (sprinkling).
The complexity of it horrified both me and Brian, and I deleted it. We might
want to add it back later, for the convenience of all 5 ASM implementors,
and other parties as yet unknown. But for now, there's plenty of complexity
in other places, and I'd rather not defend sparse segment allocations.
A hole can also be directly ldc-ed, and that's important when the content
of the hole is not a field-type. Here I'm aiming optimistically for something
like C++ templates which take non-type arguments: functions, numbers,
booleans, other tokens. The set of applications is very rich here, so I'm
aiming at it for the JVM too. E.g., a tuple type could be parameterized by
a list of types. This makes sense when you realize that a template might
be expanded using a library-defined bootstrap method, not just a
intrinsic hardwired JVM behavior. The fallback position is to require all
non-class arguments to be carried by types. (C++ does this sometimes,
but it's cheaper for them than it would be for us.) Clearly non-type
template arguments to templates is a debatable topic, and one we'll want
to craft a careful answer for.
Another reason to define a hole as a "loadable constant" is to allow it
to serve as a direct argument to condy/indy. In fact, once you allow
condy to accept hole data as inputs, it makes great sense to allow
condy to return the favor, and *produce* hole-like data as an output.
Thus, wherever a hole constant can be used, a condy constant can
*also* be used. This allows a segment to define derived constants
(derived from its holes) which serve the rest of the segment as
extra holes.
>> •
>> •
>> •
>> What about the user mode assumption that: if Foo extends Bar, Foo<Point> is a subclass of Bar<Point>
>
> This is handled by the translation scheme. If Foo<T> extends Bar<T>, then the superclass of Foo<T> will be Bar<T>. In M3, we’d write this as ParamType[Bar, TypeVar[0//Object]], which means that when Foo is specialized with a real type T, the super type is Bar<T>, and when Foo is specialized with erased, the suer type is erased Bar.
Yes. In the descriptor-centric syntax I'm working with it's isomorphic:
Descriptor["LBar[_];", DefaultType[(Hole#42), (Object)]]
In addition, the relation between Foo and Bar about *templates* only.
Meanwhile Foo<erased>, Foo<String>, etc., are species (specialized classes)
that relate in the ordinary way to Bar<erased>, Bar<String>, etc., simply
because that's what the translation strategy asks for, by plugging in
"class_info.super_class=Bar<String>" in the specialization Foo<String>.
No JVM magic there.
There is new JVM magic for templates, though: Foo<String> has a
*template super* of Foo, and Bar<String> has a *template super* of Bar.
This kind of super relation is new, and distinct from the existing relations,
which are now called *class super* and *interface super*. Inheritance
works through all of them. By distinguishing *template super* as separate
concept, we avoid the fruitless puzzling over whether a template is a
super class (but we need two now), or a super interface (but those only
carry public members), or a super protocol (a new kind of type altogether).
Template supers cause layouts and v-tables to become variable, so that's
the place where extra implementation care is required, and existing concepts
fail.
I don't think it's necessary that Foo (the template) has Bar (the template)
as any kind of super, as long as every species Foo<String> is wired up
to both Foo (the template) and Bar<String>. On the other hand, when
one template depends on another as with method templates inside
of class templates, or with nested class templates, then constants
from the parent template will appear in the child template. This is
a kind of scoping, but not inheritance, so I think the only new
inheritance mechanism here is from a species to its class template.
>
>> •
>> • Is it the case that a specialization could always have two segments
>
> As the proposal is written, a specialized class would have at least two segments — the “true constants” segment, and the “specialized class” segment. The intent, though, is that nested generic members (methods, and maybe even inner classes) would have their own segment too. And segments inherit holes from their parents.
(Yes. See above.)
> Note too that compilers often desugar one member into more than one; if a generic method has a lambda in it, that lambda will get its own method, but it should go into the segment for the generic method, not the class. Then the right things happen automatically.
This is a good example of why each class and each method needs more
than just an ACC_TEMPLATE bit, but rather a numeric segment designator.
The same point probably even applies to fields. For example, if some
desugaring mechanism needs a static constant, with a condy that depends
on holes, then it *might* want a static field whose segment designator
is aligned with whatever thingy is in that segment.
Thus, the correct way to view segments is as "locations" for mixtures of
classes, fields, and methods, even as those classes, fields and methods
inter-relate among themselves, using the relation of "membership".
The connection between "membership" and "location" is surprisingly
loose. You can't model "location" as a kind of membership, any more
than you can model "template super" as an existing type relation.
Specifically, suppose C contains M or F or N as a member (C=class,
M=method, F=field, N=nested class). Then S(C) can be the same
segment as S(M), S(F), or S(N), and often will be. But S(M), S(F), and
S(N) can *also* be parent or child segments of S(C). They cannot
be "cousins", I think.
So if C(M) is the same as S(C), then C and M are specialized together.
If S(M) is a parent of S(C), that means that M is invariant in C, and so
you can resolve M in the C-template (without specializing C).
Because of template-super inheritance, every C-species inherits
M (unspecialized) from its template-super. Also, you can
implement wildcards by resolving M directly against the
C-template.
If S(M) is a child of S(C), then M is a generic method in its own right.
If S(C) is the global segment, we have C as a normal class (not a
template) containing template methods. Think Arrays.sort<any T>.
The same considerations apply, with small modifications, to S(F)
and S(C). The only combination that *doesn't* show up clearly in
our requirements, yet, is for S(F) to be a child of S(C), *and* F to be
non-static. So there are 17 of 18 combinations: (static/instance)
S(M/F/N) is (same as/child of/parent of) S(C). That's a pretty rich
model, but I think it's the right one.
(Exercises for the reader: Figure out what it could mean for S(C)
to be a sibling of S(M), not parent or child. Also, how might a
source language ask for S(M) to be a grandparent of S(C)? Might
a translation strategy need this? Are only direct children relevant
to the above, or can S(M) be a grandchild segment of S(C)?)
> Bringing inner classes into a single template may sound like a radical move, but its a powerful one; inner classes share so much with their enclosing class, that being able to inherit holes and constants from the class would result in lots more sharing.
>
>> •
>> • Why extend super-interfaces to Constant_Dynamic? When would the BSM be invoked? Is the intent here to allow superinterfaces with holes - couldn't that be handled via a template type species?
>
> John is looking ahead here to a feature we would like to have. Suppose I have an interface like Comparable. And suppose I want to create a Box<T> type, and I want to lift the comparability of T onto Box<T>. That is, if T is ordered, then I can derive an order on Box<T> from the order on T. And I would like that to be reflected as a conditional super type. I might express that in Java code like:
>
> class Box<T>
> <when T extends Comparable<T>> implements Comparable<Box<T>> { … }
>
> Having a bootstrap that comes up with the list of supertypes as function of the type parameters allows such things to be represented.
Yep. Part of my thinking is that, if we are going to the trouble of patching
Collection<String> into List<String>, let's see if we can supply hooks
for ad hoc logic to do slightly more elaborate patching. Some cases:
- List<String> extends Collection<String> — basic interface user model
- List<String> extends Comparable<…> — optional interface (ad hoc BSM logic)
- MyRecord<Foo> extends Serializable — optional marker (ad hoc BSM logic)
- MyHandler<Foo> extends Foo — proxy template (ad hoc BSM logic)
Some of these are a little mind-blowing from the language design point
of view, but as a group they are all routine grist for the JVM's mill.
>
>> • Relationship between: raw type, template class, erased species
>
> There are two questions embedded here:
> - are the above all types, and if so what is their subtyping relationships,
> - what is the relationship between the _members_ of these various types
>
> Our working story is that in the VM, there are _class_ and_species_ types. From a template class, we derive a class type and a mechanism for deriving the species types from their type parameters. The compiler translates uses of wildcard and raw types as the class. The Class is a super type of all the species of that template.
Yes. I think it's also useful, in the JVM, to distinguish a plain class
from a class template. But (as described above), a C-species (a type)
inherits every member M of its C-template (a type). The details of the
inheritance differ depending on whether M is static or not, and whether
S(M) is same/parent/child of S(C). In the case of "same S", then the
two are specialized together, and it's not really inheritance at all,
since the M-species shows up at the same time as the C-species,
while the M-template is not usable in any way. In the case of S(M)
being in a child segment, M is a generic, and isn't usable even
now, until it is further specialized. In the case of S(M) being a
parent of S(C), then M is resolvable in C-template, invariantly,
before specialization. *That* is inheritance of the C-species
from its "template super", using a new inheritance mechanism.
> Separately, the compiler ensures (through the translation model) that the _class_ has all the same members as the erased species. So for any member m in the erased species, call sites / access sites for c.m will link, where c is of the class type.
Yep. This is a major use case (but not the only one) for S(M)
being a parent of S(C). Since M is located in a parent segment,
it is accessible without S(C) being available, which is the requirement
for backward compatibility with erased generics. It is also a
requirement (maybe the same requirement, or maybe not)
for the C-template to export an invariant protocol for dynamically
typed access (via wildcards, or reflection, or both). Doing this
requires invariant M members.
In this vein, a rather difficult requirement is invariant access to
instance fields. Old code accesses a public field Box.value of
type Object. The new reified version of this field is Box<erased>,
again of type Object. But now there is also Box<byte>.value
which has type byte. That's a hot potato; you can ask the
translation strategy to build bridges around it, but you still
have old code doing "getfield Box.value:Object" when the
box might have a byte or any old thing in its field.
I think the JVM needs to catch this particular hot potato, briefly,
and say that a CONSTANT_Fieldref can resolve covariantly on
the field type, not invariantly (as today). Thus, if old code
says "getfield Box.value:Object" and the field is really of type
"DoubleComplex", then (since Object is a super of DoubleComplex)
the getfield should resolve. The interpreter and complier have
to assume the burden of checking the type dynamically, which
is nasty, but similar to the problem with array loads. Same
deal with putfield (like array stores).
This *doesn't* cover primitives, so we have to toss the hot potato
at that point back to the language designers, and have them do
one of two things: 1. Disallow primitive parameters, 2. Wrap
primitive fields appropriately in values which take the bound
type. This become simpler when in LW1000 when we heal the
rift between primitives and values.
>
>> •
>> • proposal is that the template class is not instantiable
>
> Yes but …
>
> Old code (and maybe new) will have `new Foo` byptecodes in them; we’d like to redirect these to instantiate the erased species.
To me, this is another bridging problem. The move I think is fruitful
here is to separate *template resolution* from *class resolution*, and
*template references* from *class references*. In bytecode I propose
to spell a template with its brackets, always, even if there are only
hole symbols inside. Then a class of the same name will fail to load,
or (rather) run a fallback path which will derive the requested "vanilla"
class from the template.
BTW, I am proposing that, contrary to M3, we rely on currently illegal
characters only in spelling descriptors, and that means overloading
array brackets. So the template for `java.util.List` might be named
at the source code level by a wildcard `java.util.List<?>`, but in
the JVM it needs a separate name `java/util/List[_]`. The rule is
that when you change dots to slashes, you also straighten the pointy
brackets. The underscore character means "erased" in M3, but has
a more generic meaning in the current templates proposal; it just
means "this descriptor hole will need filling", like "#" in M3. I'm
gratuitously changing the character at that point, but I think the
underscore fits better with traditional notations, and that matters,
slightly.
>
>> •
>> • Request from vm runtime
>> •
>> • in the specialized class file, we need both the name/UTF8 string AND the Constant_Class to have a place to store the passed-in resolved type parameter
>
> Yes, definitely. M3 sidestepped this as a prototyping move, but we need to meet this head-on, and its a nasty problem.
As Karen says, we need to be very careful about when resolution
occurs. Given that names are sometimes used resolved and other
times used unresolved (but with CLCs) the landscape is already
treacherous, and will surely get more trickier, as we add more
complex names and dependencies between names.
I started writing a fuller response here and it got long. There are
as many design choices here as anywhere else in the templates
problem. So let's break that discussion out separately.
Now to Karen's other specifics…
On Mar 13, 2019, at 10:41 AM, Karen Kinnear <karen.kinnear at oracle.com> wrote:
>
> John,
>
> Lois and I have been studying the Template Classes in the VM proposal:
> http://cr.openjdk.java.net/~jrose/values/template-classes.html
>
> We had some questions we were hoping you could either answer in email or in the next draft.
>
> thanks,
> Karen
> • Where in the template class file are holes allowed? "almost anywhere in the constant pool"
> • Type parameters today are allowed in ClassFile, field_info and method_info for class, interface, constructor, method or field who declarations use type variables or parameterized types (JVMS 4.7.9)
Yes. BTW, Brian and I are now using the new term "class_info" for the specific
parts of the ClassFile which define the class or interface. This is because (a) it's
more in line with field_info and method_info, and (b) we want to preserve the option
of putting more than one class_info structures into a single ClassFile structure,
so they can share constant pool and segments.
(Note that submerging class_info into ClassFile only makes sense if there is
a strict 1-1 relation between the CP and the class_info. This is not a useful economy
when we start to break up the CP, and/or put nested classes under the same CP.)
> • Add at use sites for field and method descriptors. Assume this applies both to the reference class and the parameters/return types
Yes. Also, wherever a Hole can go, a Condy can also go. The user
of a hole is willing to pick up the resolved value of the hole and
decode it appropriately to the use. The same user, when presented
with a condy, forces resolution, and *then* decodes the resulting value
just as if it were a specialized hole. In this way, holes and condys
are almost the same thing; they are defined in different ways but used
in the same ways.
> • Add at use sites for CONSTANT_Class_info:
> • e.g. superclass
> • comment about other languages wanting to assign different superclasses for species
> • What about the user mode assumption that: if Foo extends Bar, Foo<Point> is a subclass of Bar<Point>
> • superinterfaces
(Stuff about supers was discussed earlier.)
I want to relax this a little. I think it would be helpful to place a Class
between a Hole (or Condy) for these uses, so that the "decode" logic
I mentioned above can be centralized, on the code that handles
CONSTANT_Class.
The basic rule is, if you are using a Hole (or Condy) inside the "guts"
of a Class, MethodType, or NameAndType constant, use it directly.
Otherwise, wrap it first in a Class, and then use it like today.
> • Add for annotations for field and method descriptors
> • other attributes?
Wrap in a Class in those cases. Also for instanceof and the other
bytecodes that consume Class today, wrap the descriptor in a Class.
This requirement, of wrapping in a Class for non-descriptor usage,
applies uniformly to every kind of descriptor other than Class itself:
Utf8, Condy, Hole, DefaultType, Descriptor (aka. ParamType).
You shouldn't wrap a Class in a Class, though, even though you can wrap
a different kind of descriptor in a Class, and a Class in other kinds of
descriptor. That wrinkle isn't captured by the diagrams I posted.
> • Where are holes allowed in specialized class files?
> • "API types, class instances and method invocations never have holes"
> • Assume add "field descriptors"
Yes, thanks.
> • "Because of overloading the type part of a method needs to be spelled with non-class holes intact, since that is how the API element seems to be distinguished from its peers. This seems to be a necessary exception to the rule that constants with holes cannot participate in resolution."
This bit interacts with the hard problem we address today with
class loader constraints. We need a way to ensure that "passive"
(non-resolved) uses of type names during API linkage mean the
same thing for both caller and callee. I think it boils down to
creating the species (with or without non-class holes) in the caller
and also in the callee, and determining that they are identical,
before letting the link resolution declare victory. This is different
from CLCs. It's a long conversation. But the above statement
is hopefully not going to be necessary; hopefully we just won't
allow some kinds of species to serve as API types, at least not
via flat strings.
(BTW, I see it as an *anti-requirement* to be able to assign a
stable name to every species of every template. This means
that some species just won't make sense as passive type names
in APIs. You can start to see this if you realize that a generic
method specialization doesn't need a name, as an API type;
you just call it via resolution instead of making a passive
reference to it. Then there are VMACs, which don't ever have
a name. And CLCs are complex and unwieldy, so you probably
can't allow Temp<Foo> to exist for two Foo's in different CLs,
at least in some kinds of Temp. Behavioral data like MHs and
lambdas makes for great template arguments but cannot be
uniquely named, until we solve the halting problem. And so
on. If you try to unwind all such objections, back to the
goal of giving a unique name to every species, you'll end up
with a much, much weaker mechanism, for a dubious gain.)
> • bytecodes can not be type-checked until all CP entries are complete
> • potential w/partial verification/2 pass - but that is an implementation optimization, not semantic
> • is the key point here that verifier can not see any holes, but e.g. attributes only viewed by e.g. reflection may see holes which are not caught by verification?
The easiest way to extend the verifier is to run it only after all holes
are filled. There are alternative paths we should examine, however.
Brian has suggested that a Hole with a non-denotable type could be
filled, for verification purposes, by a "nonce", a value known to be
different from every other class name. Such a nonce might not be
resolvable (so the verifier must be conservative about assignability
and subtyping). As long as such a "nonce" type is uniformly compatible
with a-class instructions (not iload/iastore/etc., but aload/aastore/etc.)
you can load it from arrays and fields, move it through stack and locals,
store it out to arrays and fields, and use it in *local* method calls.
This can be verified once, before template instantiation.
There's more: This "nonce" is really nothing other than a quasi-symbolic
("indexical"!) reference to a local constant pool entry. In fact, we could
require that it is a real and true CONSTANT_Class entry, even if it is built
on top of descriptors, holes, etc. This puts extra constraints on translation
strategies, in that they must be careful to use the same CONSTANT_Class
entry for everything the verifier touches, but the benefit is nice: You can
verify your template before specialization.
> • clearer if "no holes in specialized class file", verification only extends as far as it does today
If we don't adopt indexical types in the verifier, we still have the burden
of computing, in the verifier, the relation (equal, assignable, neither)
between two verifier types. Those are derived from CONSTANT_Class
constants and also from "passive" names that occur in various descriptors.
In fact, here's another reason to try to require passive species names to be
wrapped in CONSTANT_Class, uniformly. The verifier tries hard not to resolve
names, but it must sometimes. In the case of complicated species references,
two structurally distinct CP references might resolve to the same metadata
pointer. Should the verifier just assume they won't, and require an explicit
checkcast in places where you can't tell for sure? Probably. But there's a
slippery slope here. How dissimilar should two constants (or names) be
before the verifier gives up trying to prove they are identical? This is an
extension of the current problem with subtyping, in that distinct names
might be related, but the verifier can only extract the information it wants
by resolving them and querying the metadata.
I don't have a firm design on this point, but I think we should allow the
verifier (a) to use indexical types based on CP indexes, and (b) to "punt"
if two indexical types refer to different CP indexes, even if a little more
effort might discover that they somehow "boil down" to the same name.
And the verifier should "punt" for an indexical type vs. a named type,
except in the current case, backed up by CLCs, where the name is for
a non-species and the indexical points to a CONSTANT_Class whose
Utf8 is that same name.
(I guess I've just demonstrated that the verifier already uses indexicals.
That's really what an ITEM_Object structure is, in a stack map. But the
ITEM_Object has a "magic" equivalence with its underlying string, as
derived from various nearby descriptors. It's that equivalence that must
be broken, in the case of species.)
> • Is it the case that a specialization could always have two segments
> • There is a requirement that only the root segment can be shared
> • Could we therefore have two segments for a given specialization - a common root segment and a per-species segment and not need multiple segments in the specialized class file
Not sure what the proposed idea is here. Some constants are
invariant, and some are variant. More than that, a variant constant
is variant with respect to a *particular* non-root segment.
Why do we need more than two segments? In a word, nesting. Method
templates might nest inside of class templates, and classes in classes
too. Enumerating all the use cases gets up to the 18 or so combinations
I mentioned above. And it's not necessarily just depth-2, since the language
allows very deep nesting (in principle). When the dust settles, you find that
the natural structure here is a single root segment for global (invariant)
constants plus a parent-child relation for segments under the root segment.
Backing off from that, note that, even if there were just 2 segments, there's
a problem with assigning indexes to their constants. We don't want to add
a new "segment" field to every bytecode instruction (do we? what about a
a segment prefix?) so the bytecode instructions need a way to combine both
factors (segment S, constant in S) into one 16-bit index. The same uncomfortable
conversation applies to pretty much every 16-bit holder of CP references in
today's class file format.
So we need something like (a) a combined, flat, compact index space for
all constants in all segments and (b) a way to decode indexes in that space
into the two factor form, (S, K in S). The simplest way to do that, and what
I'm proposing to start with, is having each segment declare exclusive rights
to a specific range of CP indexes. The "global segment" is all the bits and
pieces left.
There is a table, loaded after the constant pool but before every class_info,
which declares these segments. Thus, the CP can be loaded "segment agnostic",
then the segments are checked, and finally the class is loaded (or classes are
loaded). The current published draft has segment info interspersed into the
CP; I now think it's a little easier to wedge segment metadata between the CP
proper and the class_info(s). Putting segment metadata in an attribute is a lose,
because it makes it impossible to check on the fly, while class_info gets loaded.
So we have ClassFile = header constant* segment_info* class_info*.
And then class_info = header field_info* method_info* class_attr*
> • and then, from an implementation standpoint, we could have a common root for all the raw types
Yes. I'd prefer to say "invariant" or "global" constants. The
infrastructure for "raw" stuff is the concern of language translators,
not the JVM proper.
> • Could we see more complex examples
> • more than one parameter type
> • segments that depends on multiple parameter types
> • template classfile and specialized result "reduction"
Map<K,V> has a two-hole segment
Map<K,V>.Entry is a type nested inside Map.
In the case of a "reduction", I think you mean a classfile or class_info
which somehow provides an ad hoc, manual specialization. A good
example of that might be an EnumMap, if somehow a general TreeMap
could be persuaded to specialized to EnumMap if it detected that its
K parameter were an enum. Even simpler, we could try to partially
specialize TreeMap<boolean,V> to a BooleanMap<V> whose state
is always just two fields of type V, falseValue and trueValue.
I'd like to provide JVM hooks for such things, without knowing the
full details of the user model. From a "hooks only" point of view,
the TreeMap template should have a specialization BSM which
can decide if the K type (and/or V type) meets some special condition,
and serve out a specialized version of the template, which has the
same API but different fields and methods (maybe supers too).
One way to do this would be to allow the template to just return
a foreign type for some of its specializations; this is very visible
in the user model, but easy to do in the JVM. So TreeMap<boolean,V>
would return a BooleanMap<V> and we muddle on. I think that's
a reasonable first thing to try, although it requires lots of laxity
at the user model level.
More subtly, the next thing to try will be to keep BSM as above,
but have it return an instantiation of a class_info other than the
template in question. It might have a similar name, like
TreeMap<special boolean, any V> which boils down to TreeMap[Z_],
on top of a Hole reference in a relevant segment (not the main
segment for TreeMap<?,?>, but one specially for this ad hoc
class_info). If you ask for the "class" of this specialization, you'll
be told "TreeMap", even though there are several class_info items
named TreeMap[something] in the ClassFile.
A separate thing to do, which I want to do anyway, is to allow
optional members of templates. In that case, one TreeMap
template would be just stuffed to the gills with all the fields
and methods that any version of TreeMap might want, but the
BSM would take care to enable only the ones necessary for a
particular ad hoc version, or the general version.
(What's an optional member of a template? Ah, that's a good
conversation. I haven't written this one up yet. I think the cleanest
way to formulate those is in terms of *optional child segments*.
I can think of many different ways to gate their optionality,
and BSM-based instantiation is probably the most general
and therefore adequate.)
> • JVMS level
> • does the specialization including the root segment
Yes. Segments inherit from their parent segments.
Everybody inherits from the root. Inheritance in this case
means "do I have a right to use this index", not "will
somebody find this index if they search me for it".
That's somewhat similar to inheritance with classes,
but it applies independently to related segments.
> • does verification verify the root segment
Verification of bytecodes applies as usual to all methods
*located in* the root segment, regardless of whether their
containing class is also located in the root segment.
BTW this means that the verifier must restrict itself
to the template-super type of 'this' for non-static
methods.
> • note: implementation may be able to optimize
Yes; even if we find a corner case which requires us to
re-verify some non-template method for every specialization
of an enclosing class, we can still look for such opportunities
to secretly verify. Basically, try verifying the invariant method,
and if something "goes wrong" mark it for re-verifying in each
specialization. Or (the other way around) if we can verify a
method (template or not, variant or invariant) when the template
is loaded, mark it as "done" and don't repeat the work on every
specialization. (Basic Hacking 101.)
> • e.g. implementation may be able to verify the root segment and separately verify specialization relative to the root segment
Yes. If the model allows strong guarantees of verification before
specialization, we can put that into the JVM spec. Otherwise we
say that errors are reported at specialization time, whether or not
they were (secretly) detected at template-load time.
> • Why extend super-interfaces to Constant_Dynamic? When would the BSM be invoked? Is the intent here to allow superinterfaces with holes - couldn't that be handled via a template type species?
Addressed above. Basic answer: Because we can. Modified answer:
We probably want to wrap such variant supers inside CONSTANT_Class,
as discussed above.
Another point: We might want a template to inject a *whole list of supers*
into a specialization, like a multi-proxy. In that case, the definition of
the specialization should happen via a reflective "load specialization"
VM-call that may refer to a class_info inside of the caller, but may *also*
say "please add the following lists of field, methods, and supers".
This would be slightly similar to the VMAC stuff we have now, but
it would inject the dynamically selected "stuff" at specialization time.
It seems to be a natural option in a BSM-centric world. It suggests
that there are simple automatic rules that the JVM can execute for
template specialization, without calling a BSM, and then various
levels of BSM-based customization, starting with "fill in a condy",
and then "fill in a super" (via a condy), and finally "fill in a whole
class-specialization" and/or "add to the standard class-specialization".
> • Relationship between: raw type, template class, erased species
> • proposal is that the erased species has exact match of members as template class
I'd like to support this, but not (in the JVM) mandate it. In other words,
the erased species might be the same as the raw type, and also the
wild type, but that's a call I wish to leave to the language folks.
This informs my treatment of the "erased" sentinel in M3. It's not
deeply "baked into" any version of the template class proposals, but
rather supported. A CONSTANT_DefaultType descriptor allows the
translation strategy to swap out a sentinel for a better type.
> • proposal is that the template class is not instantiable
Yes. See above; it's really not a class, but a "class template". This
serves as a type (can be resolved against) but it's inherently abstract.
*If* we need migration, then the template C[_] can nominate a specialization
to use in place of C, since (after an upgrade) the class C is absent,
even though old code (compiled before the upgrade) thinks C exists.
To me this feels like a decision for a BSM to make. "Do I allow myself
to be presented as a plain class, and if so which specialization is it?"
> • challenge is: older class files with instantiated raw type "new Foo" class file: new LFoo; – requires instantiation
> • one proposal: re-translate the bytecode into new LFoo<erased>;
If possible, I prefer to stick to keeping the bytecodes the same and,
instead, flexing the resolution of the Class of the Methodref.
> • and keep a non-instantiable template class, and keep the statics in java.lang.Class as they are today
> • TODO: walk examples of raw type bytecodes and BC
If we separate template names from class names, then resolving
a class just routes, as above, to a request to the template to make
a species. Then all the bytecodes apply to that resolved species.
> • Clarifications/explorations on relationship of template class
> • potential for multiple inheritance
I don't see a general solution for MI, and so I'd prefer to define a
very specific new kind of inheritance, from a "template super",
as discussed above. I think we've probably already discussed all
of the characteristics of such a thing, including elastic layouts
and elastic v-tables.
(BTW I think the special problems of virtual dispatch to generic
overrides are *not* part of the phenomenon of template supers;
they are a separate hard problem.)
> • Concern about the requirement for ordering of holes - must depend on an earlier one, also the requirement to point to the "last" hole in a segment
Brian and I are both comfortable, at the moment, with having holes
be more like arguments (with a position) and less like fields (with a name).
The basic structure is that a CP segment is of this form:
N: CONSTANT_Segment[J]
N+1: CONSTANT_Hole[kind_1]
… more holes …
N+J: CONSTANT_Hole[kind_J]
N+J+1: (some other constant)
… more constants …
N+L-1: (the last constant constant)
This just floats into the CP, and then much later on there
is a metadata block of this form:
segment_info {
parent_segment: 0 (global)
segment_constant_index: N (back link to CONSTANT_Segment)
highest_index: N+L-1 (gives span in CP)
holes_count: J (validates the sequence of CONSTANT_Hole items)
segment_hole_info[J] {
… more stuff for each of the J holes …
}
}
> • does this cause problems for Lookup.defineClass with re-use of byte[] and constant pool extension mechanisms?
I don't think so.
> • does this cause problems for bytecode instrumentors, redefinclasses - what if they want to add an additional hole in a segment - do they need to need to change all references to the "last" hole in a segment?
Yes, this causes a problem for those people, as I suggested above.
I don't want to solve this problem yet, because its complexity will
obscure the basic problem. If we *do* need to solve it, I think I
have a simple-enough, expressive-enough, compressive-enough
way for a segment_info to describe which constants are in it;
basically you add more "stuff" instead of the "highest_index" field,
which gives you a compressed bursty bitmap. Then the classfile
rewriter can add stuff to the end of the CP, and edit any relevant
segment. No CP indexes need editing in this case. The JVM
will have to maintain an extra side table, indexed by CP index,
and yielding (1) the segment, and (2) a compact re-indexing
of the constant within the segment. This is (drum roll please)
what HotSpot is already doing with the CP cache, except in this
new design each segment gets its own CP-cache-like array.
As with the CP cache, such reindexing *might* show up in the
internal form of the bytecodes (rewritten secretly) or it might
not; I think my tilt is towards "not".
But all that's more than I want to propose for the first version.
> • Could we explore having two segments in the template classfile, one root and one specializable, and each entry you could trace dependencies instead of requiring ordered segments?
Two segments is not enough.
But you are right that we should require appropriate referential
integrity of constants. For example, a CONSTANT_Methodref must
refer only to a CONSTANT_Class and CONSTANT_NameAndType
that are either (1) in the same segment, (2) inherited from its parent
segment or one of its ancestors, or (3) in the global segment.
(Actually 3 is a special case of 2 since the global segment is an
ancestor of everybody else.) Doing this is just basic sanity. It
can and should be checked as soon as the segment_info table
is loaded, before any class_info is inspected.
As a further constraint on translation strategies, I would like
to *require* that constants *not* be placed into segments
where they don't need to be placed. That is, if a constant only
depends on constants declared in the global segment, that's
where it needs to go also. The very rare case of a condy which
needs to "trigger" in each specialization, but doesn't "look at"
any of its nearby holes, needs to take the CONSTANT_Segment
of its desired segment as an argument, in order to be valid in
that segment.
So I want to constrain constant placement in both directions:
If a constant depends on some constant in some segment S,
it must be placed in either S or one of its children/descendants.
And vice versa, if a constant depends on no constant in some
segment S, then it must *not* be placed in S or any of its
children/descendants.
This implies that the basic segment tree structure can be inferred
or recovered from the raw constant pool, kind of like stack maps
can be inferred or recovered from the bytecodes. And yet it's worth
placing redundantly in the classfile format, because (a) it is expensive
to compute, and (b) we need a compact numbering of segments anyway
(which the inference doesn't produce), and also (c) segments need extra
metadata (which we don't want to stuff into the constant pool).
> • Request from vm runtime
> • in the specialized class file, we need both the name/UTF8 string AND the Constant_Class to have a place to store the passed-in resolved type parameter
> • It would be valuable to be able to share any resolved classes to achieve "same resolution" results going forward
Yes, this is super important, as already noted. It has a special
importance when checking *across* API points, as we do with CLCs.
> • Redefineclasses will need to have a way to indentify types resolved externally and passed in as live-types, so they are NOT re-reresolvable
Yes. For each specialization (class or method, maybe fields too) there
must be a live "species" object which gathers together (a) the Hole
values being proposed and (b) all of the resolution state of the constants
in that segment. (Oddly enough, the layout of this object is really easy
to compute, given the current design of contiguous CP segments. It's…
a segment… of the constant pool.) If you redefine a template local to this
segment, you have to figure out how to keep the resolution state in the
segment, and re-associate it with the new version of the template. I don't
think there's anything really new here, except that (as noted) the appending
technique will force some sort of discontinuity into segments.
> • Detail: How are Template Attributes used e.g. by Class, method, field? What does it mean to have a template attribute on a static field? Is that a way of clarifying which conditional species it belongs to?
The new version of the proposal gets rid of these attributes. Instead,
the *location* of each piece of metadata is hard-wired into it, as a
u16 segment_index item right along side the other items. This goes
for class_info, field_info, and method_info. This allows a simple and
comprehensive rule for referential integrity: A xxx_info block can refer
only to constants in its own (clearly marked) segment, or inherited
(perhaps from the root segment) into its own segment. This happens
independently of what any related metadata is doing with its own
segment. Yes, it's really that pervasive; see the discussion about the
18 or so cases above. Brian and I are comfortable with not prematurely
"compressing" this. (Actually a previous version *did* compress, and
we decided it was, as with non-contiguous segments, undesirable
complexity at least for a first cut. It's not the thing to optimize now.)
It's time for some code:
```
ClassFile {
u4 magic;
u2 minor_version;
u2 major_version;
u2 constant_pool_count;
cp_info constant_pool[constant_pool_count-1];
u2 segments_count;
segment_info segments[segments_count];
u2 classes_count;
class_info classes[classes_count];
}
segment_info {
u2 parent_segment;
u2 segment_constant_index;
u2 highest_index;
u1 holes_count;
segment_hole_info holes[holes_count];
}
class_info {
u2 segment_index;
u2 access_flags;
u2 this_class;
u2 super_class;
u2 interfaces_count;
u2 interfaces[interfaces_count];
u2 fields_count;
field_info fields[fields_count];
u2 methods_count;
method_info methods[methods_count];
u2 attributes_count;
attribute_info attributes[attributes_count];
}
field_info {
u2 segment_index;
u2 access_flags;
u2 name_index;
u2 descriptor_index;
u2 attributes_count;
attribute_info attributes[attributes_count];
}
method_info {
u2 segment_index;
u2 access_flags;
u2 name_index;
u2 descriptor_index;
u2 attributes_count;
attribute_info attributes[attributes_count];
}
```
(You read that right. I'm proposing 16 bits of new "slack" on every
class, field, and method info struct. We'll compress it later if we really
must. And, yes, we've considered several obvious alternatives, such
as reshuffling the foo_info inside of the segment_info blocks where
they live, but then they need a different pointer, to their metadata
container. And, it doesn't work, or help, for parts of a class to
"inherit" a segment from the class itself, unless there is a way to
override that "inheritance". And putting such an "override" into
an Attribute would be nice, except it makes it hard to structurally
check the part containing the Attribute until after the whole part
is read. Having two bytes up front is far cleaner. I have an alternative
design that cheaply removes the extra bytes when they are inherited,
but it incrementally complicates the whole proposal, and so… not now.)
> • Template Attribute and TemplateParameter dependency relationship?
The basic integrity constraint holds: If some part of a class file
has a constant reference CP[N], then that part *must* be inside
a chunk that is located in the segment where CP[N] is defined.
That goes for xxx_info blocks and for CP constants themselves,
if they mention other CP constants.
> • Later email: not clear why a BSM-based template expansion logic would not use existing class loaders, system dictionary and loader constraints
See discussion above. The fit is imperfect; there are some corners
to round here. There are maybe some new uses of these existing
mechanisms, but we have to be sure they are appropriate to the
new uses.
That was a good day's work! Good luck reading it. Oh, wait, you
did if you got here. Congratulations!
— John
More information about the valhalla-spec-observers
mailing list