Relaxing immediate supertype requirements

[tlively]

We currently have this requirement:

A declared supertype of a type with a (descriptor $x) clause must either not have a descriptor clause or have a (descriptor $y) clause, where $y is a declared supertype of $x.

This makes this arrangement invalid (where the sideways arrows are "described by" and the upward arrows are "subtype of"):

B -> y
^    ^
|    z
|    ^
A -> x

The idea behind this requirement is that type validation should not require unbounded search up the supertype chain, but perhaps production implementations already have constant-time subtype checks available at this point?

We could potentially relax this restriction to allow y to be any supertype of x rather than having to be a declared supertype of x.

Maintaining the stricter requirement inhibits some optimization in Binaryen: WebAssembly/binaryen#7743

[jakobkummerow]

No objections -- on the contrary, upon inspection it turns out that I accidentally already implemented this as "where $y is a supertype of $x" (i.e. not declared, just any direct or transitive supertype). I'm generally not too worried about performance of validation-time type checks (as opposed to runtime type checks, which must be very fast).

[titzer]

One advantage of keeping the requirement is a 1-to-1 correspondence of exact types between descriptor types and their object types. That implies a ref.get_desc on an exact type can return an exact type of the descriptor type. Since we're requiring exact types for descriptors passed to struct.new, this makes it possible to take a reference of an exact struct type, get its descriptor (which is then exact), and then make more instances of that struct, without any dynamic checks.

[jakobkummerow]

@titzer Wouldn't that still be the case anyway? IIUC, the proposal here is to allow type z to exist; but B would still be described exactly by y and A would still be described exactly by x, so you could still ref.get_desc an (exact A) struct's descriptor, get an (exact x), and use that to produce more As.

[jakobkummerow]

I suppose the tricky question is what the describes: ___ property of z would be. It needs to have one, because inheritance between descriptors requires them all to be descriptors.

[rossberg]

@titzer, I also believe the 1:1 correspondence is preserved by this, it just allows redundant intermediate subtypes on one side, which seems fine at first glance. But some subtle inversion issue could arise from that, and I suspect @jakobkummerow's question indeed is pointing in that direction: wouldn't the type that the mid descriptor describes have to be mid of the two lhs types? That would create a contradiction with the intended goal of the relaxation.

From looking at the linked Binaryen issue I didn't quite get how the need for those intermediate types arises, or what optimisations are inhibited without them. @tlively, can you elaborate?

[tlively]

Here's a valid type graph this relaxation would allow:

A ---> X
^      ^
| C -> Y
|      ^
B ---> Z

It's worth noting that the inverse graph would not be valid:

X ---> A
^      ^
Y -> C |
^      |
Z ---> B

The latter is not valid because a ref.get_desc $X would have type [(ref null (exact_1 $X))] -> [(ref (exact_1 $A))], but at runtime could produce a value of type (ref $C). The asymmetry in the validity comes from the fact that you can get a descriptor from a described object, but you can't get a described object from a descriptor (except by allocation, where the descriptor and object types are exact anyways).

[rossberg]

Does the first diagram really make sense? Descriptors need to include the supertype vectors of their respective describee types. An invariant that I would expect to hold is that the supertype vector of a sub-descriptor is an extension of that of its super-descriptors (and not just of the descriptors of the supertypes of its describee). I believe that invariant is actually required if we want to enable implementations to flatten/fuse the supertype vector with the field vector. AFAICS, that invariant would be violated in a configuration like the above.

[tlively]

An invariant that I would expect to hold is that the supertype vector of a sub-descriptor is an extension of that of its super-descriptors (and not just of the descriptors of the supertypes of its describee). I believe that invariant is actually required if we want to enable implementations to flatten/fuse the supertype vector with the field vector.

So far implementations have not required nor upheld this invariant. Can you clarify what kind of flattening or fusing you have in mind that would require this?

My understanding is that you're referring to copying the supertype vector from the canonical RTT into the descriptor object to avoid the extra indirection on casts. Is that right? But in that case the space allocated in the descriptor object to hold supertype vectors must have some globally constant size so the field offsets can be known even with subsumption. So there's no need for the supertype vectors held in one descriptor type to be an extension of the supertype vectors held in its supertype.

[tlively]

From looking at the linked Binaryen issue I didn't quite get how the need for those intermediate types arises, or what optimisations are inhibited without them. @tlively, can you elaborate?

The linked Unsubtyping optimization is finding the minimal subtype relation that preserves validity and observable cast behavior. It starts by examining the code for subtypings necessary to maintain validity of the code, then it iteratively finds further subtypings required by the type definitions for those established subtypings until it reaches a fixed point.

Consider a module starting with this type graph:

A ---> X
^      ^
B ---> Y
^      ^
C ---> Z

If the module code requires C <: A and Z <: Y, then Unsubtyping will start with this graph:

A ---> X
^
| B -> Y
|      ^
C ---> Z

Then it starts iterating. C <: A requires Z <: X, so then we have this graph:

A ---> X
^      ^
| B -> Y
|      ^
C ---> Z

With this relaxation, we could stop there. Without it, this further requires C <: B, getting us back to the original graph.

Being able to optimize out subtypings not only directly saves bytes in the type section; it also removes constraints that would prevent other optimizations from e.g. reordering or removing fields.

[rossberg]

@tlively:

Can you clarify what kind of flattening or fusing you have in mind that would require this?

An optimisation for single inheritance OO languages that have both casts and method tables is to interleave the supertype vector with the method vector, hence avoiding extra indirection. For example, if you have C extends B extends A, then the combined meta-data vector of C would be laid out like this:

[A-classid | A methods ... | B-classid | B methods ... | C-classid | C methods ...]

This works because the number of methods introduced in each supertype is statically known, and hence so are the offsets to check for the super class ids during a cast. No global maximum size has to be fixed for this.

I expect the same optimised representation to be possible (and desirable) for descriptors, just substituting canonical type ids for class ids and descriptor fields for methods. I believe canonical types themselves do not even need to carry the supertype vector in that case.

[tlively]

To be clear, this is an optimization you expect the engine would do, right? So the engine would interleave the user-visible method fields with the internal supertype vector fields?

I don't see how this can work with WebAssembly. Say I have these types:

(type $A (sub (struct ... A fields ...)))
(type $B (sub $A (struct ... A fields ... B fields ...)))
(type $other (struct ... other fields ....)))

Then ref.cast (ref $B) needs to look at the depth-1 supertype ID and see whether it is $B. But the codegen cannot assume that this supertype ID is interleaved into the object at an offset after ... A fields ... because the actual type of the object might be $other, which has nothing to do with $A and whose offsets cannot depend on $A's fields. This is all true whether or not $A, $B, or $other are descriptor types.

Maybe other languages can get away with this because they never have to handle userspace casts of their descriptors.

[rossberg]

The optimisation I described applies to descriptor fields (which are a natural place to store method tables). So the actual scenario is:

(rec
  (type $A (descriptor $DA) (sub (struct ...)))
  (type $B (descriptor $DB) (sub $A (struct ...)))
  (type $other (descriptor $DOther) (struct ...)))
  (type $DA (describes $A) (sub (struct ...DA fields...)))
  (type $DB (describes $B) (sub $DA (struct ...DA fields...DB fields...)))
  (type $Dother (describes $Other) (struct ...DOther fields...)))
)

When casting from $A to $B, all we need to check is whether the value's descriptor has the typeid of $B in the expected position determined by the DA and DB fields. If we instead encounter a DOther then that is no problem, as it is guaranteed to not have that typeid in the required location, regardless of what else might be there.

Well, okay, except that $DOther might have a numeric field in that same place whose bit pattern happens to match that of B's typeid. :( So with Wasm's heterogenous mixture of ref and number fields this optimisation is more delicate. Off-hand, the only way I can think of to work around this would be a butterfly layout for structs, where numeric fields are laid out in one direction and refs (and typeids) in the other. Then such an overlap cannot occur. But such a representation comes with its own set of problems.

[tlively]

Anyway, the question of whether to allow B below (which we've been discussing) only makes sense to ask if we first settle the original question and allow Y: Edit: never mind, Y needs to describe something for this to be valid, so B is necessary.

A ---> X
^      ^
| B -> Y
|      ^
C ---> Z

This would require validation of C (or Z) to search Z's supertype chain to find X. @jakobkummerow has said this is not a problem in V8, but I'd like to make sure other implementers agree before resolving this. @eqrion, do you have an opinion here?

[rossberg]

How can you allow Y without allowing B? What would its describes-clause say? These questions look inseparable to me.