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 <[email protected]> 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 <[email protected]> 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
