Species-static members vs singletons

[Brian Goetz]

> Brian,**I see that you mentioned that generic instance methods are 
> messier.
> > The translation for generic instance methods is still somewhat 
> messier (will post separately), but still less messy than if we also 
> had to manage / cache a receiver.
> Is this issue part of that mess? Do you have a solution, or is this an 
> open issue? I tried making m species statics with a receiver argument, 
> but that makes the invocation non-virtual.

Here’s some more notes on how we might translate generic methods using 
species-static methods and nested classes.


        General strategy

  *

    A {static,species,instance} generic method m() in |Foo| is desugared
    into a species method |m()| in a {static,species,instance} nested
    class |Foo$m|.

  *

    The accessibility of the method |m()| is lifted onto the class |Foo$m|.

  *

    Foo also gets an erased bridge, that redirects to the erased
    invocation of the generic method (binary compatibility only.)

  *

    A generic method is invoked with indy. The indy call site statically
    captures the type parameters for the invocation, some representation
    of the owning class Foo, and the method m(). The dynamic argument
    list captures the Foo-valued receiver (for instance methods) and the
    arguments to the generic method.


        Goals

  *

    Dispatch should be fast :)

  *

    It would be nice if the name-mangling strategy (|Foo$m|) were
    private to |Foo| — that it does not appear in bytecode of Foo’s
    clients or subclasses.

  *

    It would be ideal if we could express what we want with bytecode
    alone, not indy, but that does not seem possible in all cases at
    this time.


        Static methods

Given source code:

|class Foo<any T> { ACC static<any U> void m(U u) { } } |

We translate this as:

|@Generic class Foo { // for binary compatibility only <where ref T> 
@Bridge ACC static void m(Object u) { Foo.Foo$m<erased>m(u); } @Generic 
ACC static class Foo$m<any U> { ACC species void m(U u) { } } } |

An invocation |Foo.<U>m(u)| (where U is known statically) can be 
translated in bytecode as

|invokespecies Foo.Foo$m<U>.m(U) |

However, since it was a goal to not let the mangled name |Foo$m| leak 
into client code, we can easily wrap this with an indy:

|invokedynamic GenericStaticMethod[Foo, "m", descriptor, U](u) ^bootstrap 
^static args ^dyn args |

and let the bootstrap put together the class name |Foo$m| from 
constituent parts (the bootstrap and the compiler share a conspiratorial 
connection, but the client bytecode doesn’t participate). Since 
everything is static at the call site, we can link to a 
|ConstantCallSite| that always dispatches to an |MH[invokespecies 
Foo$m<U>.m(U)]|.


        Species methods

Species-static generic methods are translated almost the same way; given 
class

|class Foo<any T> { ACC species<any U> void m(T t, U u) { } } |

we translate as

|@Generic class Foo { // for binary compatibility only <where ref T> 
@Bridge ACC species void m(Object t, Object u) { 
Foo<erased>.Foo$m<erased>m(t, u); } @Generic ACC species class Foo$m<any 
U> { ACC species void m(T t, U u) { } } } |

and an invocation |Foo<T>.<U>m(T,U)| is translated as

|invokespecies Foo<T>.Foo$m<U>.m(T, U) |


        Instance methods

Our translation strategy — desugaring to a helper class — introduces 
some challenges in instance method dispatch.

|class Foo<any T> { ACC <any U> void m(T t, U u) { } } class Bar<any T> 
extends Foo<T> { @Override ACC <any U> void m(T t, U u) { } } |

I am proposing we translate this as:

|@Generic class Foo { // for binary compatibility only <where ref T> 
@Bridge ACC void m(Object t, Object u) { this.Foo$m<erased>m(t, u); } 
@Generic ACC species class Foo$m<any U> { ACC species void m(Foo<T> 
outer, T t, U u) { } } } @Generic class Bar { // for binary 
compatibility only <where ref T> @Bridge ACC void m(Object t, Object u) 
{ this.Bar$m<erased>m(t, u); } @Generic ACC species class Bar$m<any U> { 
ACC species void m(Bar<T> outer, T t, U u) { } } } |

In this proposal, |Bar$m| does not extend |Foo$m|; this is to avoid 
leaking dependence on desugaring in subclass bytecode. The 
implementation methods in |Xxx$m| take an extra “outer” argument, which 
is the receiver for the instance generic method invocation. The use of 
species-static methods for the implementation methods mean that we need 
not maintain instances of Foo$m, but instead can pass the actual 
Fooreceiver directly to the implementation.

For an invocation:

|Foo<T> f = ... f.<U>m(t,u) |

We translate with indy as:

|invokedynamic InstanceStaticMethod[ParamType[Foo,T], "m", descriptor, 
U](r,t,u) |

The static receiver type — here |Foo<T>| — is a static parameter to the 
bootstrap. Let’s call this class SR (the actual target will be |Xxx$m| 
where |Xxx| may be SR or a subclass of SR.) The dynamic receiver (a 
|Foo<T>|) is passed in the dynamic argument list as |r|.

The linking of the callsite is somewhat complex, but should optimize 
reasonably well. It proceeds as follows:

  * For each (static receiver class, method, specialization args) — all
    static properties of the callsite — there is a dispatch table, which
    is found statically at linkage time and stored as part of the
    callsite state;
  * The dispatch table is a |ClassValue<MethodHandle>|, which maps the
    dynamic receiver type (a subtype of SR) to a |MethodHandle| for the
    |invokespecies| implementation method;
  * Invocation performs
    |ClassValue.get(receiver.getClass()).invokeExact(receiver, args)|
  * This dispatch can be optionally wrapped with a PIC against
    |receiver.getClass()|

The first thing the bootstrap must do (at linkage time) is compute SR. 
This is done by taking the owner class |Foo<T>|, along with the method 
name and descriptor, computing the name-mangled class |Foo<T>.Foo$m|, 
call it SR’. We then take this class and compute 
|SR=Crass.forSpecialization(SR', U)|. (Both of these computations are 
done with the classloader for |Foo<T>|, and we should check that both 
SR’ and SR share the classloader with |Foo<T>|.) SR corresponds to the 
fully specialized class |Foo<T>.Foo$m<U>|.

Once we’ve computed SR, we have to find the dispatch table for SR, which 
is a multi-step lookup first by |ClassLoader| (to allow for classloader 
unloading) and then by SR, which results in a |DispatchTable| mapping a 
dynamic receiver type |R| to a fully specialized desugared 
species-static MH.

|class DispatchTable extends ClassValue<MethodHandle> { ... } class 
MetaDispatchTable extends ClassValue<DispatchTable> { ... } private 
static final WeakHashMap<ClassLoader, MetaDispatchTable> mdt = ... |

We compute |mdt.computeIfAbsent(SR.getClassLoader(), ...).get(SR)| and 
store that as |DT| in the |CallSite|. The |ClassValue| implementation 
for |MetaDispatchTable| simply creates a new |ClassValue<MH>| entry.

The callsite target is linked to the following logic:

|Class<?> R = r.getClass(); DT.get(R).invokeExact(r, args) |

The |computeValue()| method of |DispatchTable| does the meat of the 
work. For the receiver type R, we have to find the corresponding |Xxx$m| 
class, which might be declared in a superclass of R, specialize it to 
the desired method type parameters, and look up (findSpecies) the 
appropriate specialized MH. (Finding the corresponding |Xxx$m| class 
could be done by walking the hierarchy directly, or by doing a 
|MethodHandle.resolveOrFail| on the erased bridge.)

The cost of an invocation is one |ClassValue| lookup, plus the overhead 
of folding the arguments together appropriately and doing a MH invoke. 
The above logic seems representable as a single method handle expression 
using |fold| and |filter| combinators, but if not, might also introduce 
some varargs spreading/collecting overhead. (It could be further 
optimized by wrapping the the result of DT.get(R) with a PIC on R.) This 
doesn’t seem so bad.

The first time a given target is resolved (a given combination of 
enclosing |Foo<T>|, |m(...)|, type arguments U, and receiver class), a 
relatively expensive linkage step is performed — but is then cached in a 
table specific to the members involved, not the call site — so this 
should stabilize quickly.


        Interface methods

Interface methods add an additional layer, but do not change the story 
fundamentally. If I have:

|interface I<any T> { ACC <any U> void m(T t, U u) { } } class Foo<any T> 
implements I<T> { @Override ACC <any U> void m(T t, U u) { } } |

then we need to generate an artifact |I$m| artifact as we do with 
classes. When linking an invocation which static receiver is a 
specialization of an interface rather than a class, we compute |I$m| as 
our SR, and proceed as before. (In this case, our linkage strategy 
should probably use |resolveOrFail| rather than manual hierarchy 
walking, so we should probably do this in both cases.) Additionally, we 
may need to do a check that the |Xxx| class corresponding to the 
resolved |Xxx$m| holder class actually implements |I<T>| — again this 
can be done at linkage time, not dispatch time.


        Default methods

If we do our dispatch using |resolveOrFail| against the erased bridges, 
and the method is not implemented in the receiver’s superclass 
hierarchy, then I believe that resolution will hand us the MH for the 
default? If, so, we’re good; we resolve to the default, just like any 
other implementation.

One integrity risk here is that the |Xxx$m| hierarchy is properly 
aligned to the |Foo| hierarchy. I think we can validate that (at the 
time we lazily populate the dispatch table) simply by checking that the 
resolved erased target |Xxx.m()| and the corresponding specialized class 
|Xxx$m.m()| share a nest (and hence derive from the same source class.)

​