Possible extension: useful casts for source-level nominal types

Custom descriptors are an efficient place to store information associated with source-level types, e.g. vtables and user space runtime type information. This is a sketch of how they could be used to implement source-level casts on nominal type hierarchies. We will start out with an implementation in user space and then consider an extension to the proposal that could give the same functionality with slightly better performance.

In practice, producers already implement source-level casts in terms of WebAssembly casts by abusing recursion groups to ensure that different source-level nominal types lower to different WebAssembly types. This means that the benefit over the status quo of using custom descriptors to implement casts is not performance, but rather that producers could stop abusing rec groups to emulate nominal types, which would make their modules more robust in various open-world situations.

Consider source types A, B, X, and Y:

class A {
  int foo() { return 42; }
}
final class B extends A {
  int foo() { return 43; }
}

class X {
  int foo() { return 10; }
}
final class Y extends X {
  int foo() { return 11; }
}

A has the same structure as X and B has the same structure as Y, so a producer that does not abuse rec groups to emulate nominal types will lower these to the same types $AX and $BY. The instances will still be distinguishable by the values of their descriptors.

(type $Object (sub (struct)))
(rec
  (type $AX (descriptor $AX.desc) (sub $Object (struct)))
  (type $AX.desc (describes $AX) (sub (struct
    (field $foo (ref $foo)))))
)
(rec
  (type $BY (descriptor $BY.desc) (sub $AX (struct)))
  (type $BY.desc (describes $BY) (sub $AX.desc (struct
    (field $foo (ref $foo)))))
)

(global $A.vtable (ref (exact $AX.desc)) (struct.new $AX.desc (ref.func $A.foo)))
(global $B.vtable (ref (exact $BY.desc)) (struct.new $BY.desc (ref.func $B.foo)))

(global $X.vtable (ref (exact $AX.desc)) (struct.new $AX.desc (ref.func $X.foo)))
(global $Y.vtable (ref (exact $BY.desc)) (struct.new $BY.desc (ref.func $Y.foo)))

(global $a (ref null $AX) (struct.new_desc (global.get $A.vtable)))
(global $b (ref null $BY) (struct.new_desc (global.get $B.vtable)))
(global $x (ref null $AX) (struct.new_desc (global.get $X.vtable)))
(global $y (ref null $BY) (struct.new_desc (global.get $Y.vtable)))

The question is how we can lower source-level casts with these types. Normal WebAssembly casts won't work; A cast to B would become ref.cast (ref null $BY) and would incorrectly succeed for instances of Y. The new ref.cast_desc_eq instruction almost works, though. We can lower the cast to (ref.cast_desc_eq (ref null $BY) ... (global.get $B.vtable)). Instances of B will pass this cast because they have the expected descriptor value, but instances of Y will not pass this cast because they have a different descriptor value. The problem is that ref.cast_desc_eq does not work the way we want in the presence of subtypes. If we have a source-level cast to A, we want it to succeed for instances of both A and B, but (ref.cast_desc_eq (ref null $A) ... (global.get $A.vtable)) will not succeed for instances of B because they will have a different descriptor value.

Since neither ref.cast nor ref.cast_desc_eq do what we want in general, we need to do more work in user space to implement the general case of the cast. We can use the same constant-time casting trick that engines use to implement WebAssembly casts, where the runtime type information contains a vector of pointers to the runtime type information (in this case descriptors) of the supertypes. We know the subtyping depth of the cast target and we can look up the subtyping depth of the cast value at runtime. Taking their difference gives an index into the supertype vector where we will find the descriptor for the cast target if and only if the cast succeeds.

(array $supers eqref)
(rec
  (type $Object (descriptor $Object.desc) (sub (struct)))
  (type $Object.desc (describes $Object) (sub (struct
    (field $supers (ref $supers)))))
)
(rec
  (type $AX (descriptor $AX.desc) (sub $Object (struct)))
  (type $AX.desc (describes $AX) (sub $Object.desc (struct
    (field $supers (ref $supers))
    (field $foo (ref $foo)))))
)
(rec
  (type $BY (descriptor $BY.desc) (sub $AX (struct)))
  (type $BY.desc (describes $BY) (sub $AX.desc (struct
    (field $supers (ref $supers))
    (field $foo (ref $foo)))))
)

(global $A.vtable (ref (exact $AX.desc)) (struct.new $AX.desc
  (array.new_fixed $supers 0)
  (ref.func $A.foo)))

(global $B.vtable (ref (exact $BY.desc)) (struct.new $BY.desc
  (array.new_fixed $supers 1 (global.get $A.vtable))
  (ref.func $B.foo)))

(global $X.vtable (ref (exact $AX.desc)) (struct.new $AX.desc
  (array.new_fixed $supers 0)
  (ref.func $X.foo)))

(global $Y.vtable (ref (exact $BY.desc)) (struct.new $BY.desc
  (array.new_fixed $supers 1 (global.get $B.vtable))
  (ref.func $Y.foo)))

Then a cast to e.g. B could be lowered to a call to this function:

(func $castToB (param $o (ref null $Object)) (result (ref $B))
  (local $supers (ref $supers))
  (local $depth i32)
  (local $desc eqref)
  ;; Get supertype vector.
  (local.set $supers
    (struct.get $Object.desc $supers (ref.get_desc $Object (local.get $o))))
  ;; The subtyping depth of $o is the length of its supertypes vector.
  (local.set $depth (array.len (local.get $supers)))
  ;; If the depth matches the depth of $B, i.e. 1, then we must have exactly a $B to pass.
  (if (i32.eq (local.get $depth) (i32.const 1))
    (then (return (ref.get_desc_eq $B (local.get $o) (global.get $B.vtable)))))
  ;; Get the descriptor at index 1 (or trap if oob when the cast must fail).
  (local.set $desc (array.get $supers (local.get $supers) (i32.const 1))
  ;; Check the identity of the descriptor against the expected vtable.
  (if (ref.eq (local.get $desc) (global.get $B.vtable))
    (then (return (ref.cast (ref $B) (local.get $o)))))
  ;; Unexpected descriptor; the cast fails.
  (unreachable)
)

Obviously this is strictly more work than a normal cast. This means that in practice producers would continue to abuse rec groups to use normal WebAssembly casts rather than use a user space solution like this. But we could also extend custom descriptors to support constant time casting with engine-managed vectors of descriptor values, just like we already support constant time casting with canonical RTTs.

We could have the engine store such a vector on each descriptor value. By default the slots in the vector would be null, but we could add new struct.new_{default_}{desc_}super instructions for allocating descriptor values that can take a descriptor of the immediate supertype as an additional operand. These instructions would copy the supertype descriptor vector from the supertype descriptor, append that same supertype descriptor, and attach the lengthened vector to the newly allocated supertype.

C |- struct.new_super x : t* (ref null (exact y)) -> (ref (exact x))
-- if C.TYPES[x] ~~ (describes z) descriptortype? (sub y (struct ft*))
-- if t* = $unpack(ft)*

We would also add a new ref.cast_desc instruction (possibly replacing ref.cast_desc_eq) and branching versions that performed the equivalent of the user space cast above, but without needing to do a normal WebAssembly cast. In fact, the implementation of ref.cast_desc would be almost exactly equivalent to the implementation of ref.cast, except that it would operate on a vector of supertype descriptors rather than a vector of supertype canonical RTTs.

C |- ref.cast_desc (ref null? (exact? x))
    : (ref null ht) (ref null (exact? y)) -> (ref null? (exact? x))
-- if C.TYPES[x] ~~ describestype? (descriptor y)
-- if C |- ht <: ht'
-- if C |- x <: ht'

An alternative solution that would allow producers to stop abusing recursion groups would be to add nominal rec groups and type imports to the type system. This solution would be completely orthogonal to custom descriptors.

cc @eqrion

Start by reading the custom-descriptor cast examples and the proposed ref.cast_desc and struct.new_super instructions in this issue. Compare the user-space supertype-vector approach with the engine-managed descriptor-vector alternative and the nominal rec-group option. Done means reaching a settled design for source-level casts and the required type-system instructions.