i31 as a ref type dimension like null

[titzer]

In the course of discussion https://github.com/WebAssembly/gc/issues/100, @gasche proposed making i31ref not a type, but a dimension in the ref type constructor. I'd like to pull this idea out for a dedicated discussion because it is not entirely clear to me if we can add this later or must add this up front. It also seems like it can make a difference in code generation, so we should probably think it through.

Concretely, instead of (or perhaps, in addition to) a single i31ref type which is in the middle of the hierarchy between anyref and (ref $T), we have:

For each type $T, then: (ref $T) which is a subtype of (ref i31 $T)

It is thus another independent dimension much the same way as null is a dimension for this type constructor.

(ref i31 $T) subtype of (ref null i31 $T)

When thinking about the code that would be generated by an engine for various reference operations, some engines may (already) need to generate these null checks:

• null checks for struct.get, struct.set and corresponding array operations
• null checks for casts between struct and array types

Of course, most engines will hopefully be able to do these implicit null checks via virtual memory tricks, but not all can.

We've been discussing the additional checks that would be needed for i31 tag checks in the context of downcasts from i31ref to a more specific reference type. In particular, they would be implicitly needed because i31ref is proposed as a subtype of anyref above all declared heap types (AFAICT).

I'd like to point out that tag checks can be avoided if we think of i31 values as just a big group of nulls: engines can elide the checks based on static information, which is exactly the same information provided in the null ref type dimension.

It also gives more expressive power to programs, because it is a very limited union type. In particular, using (ref i31 $T), a module could perform a (struct.get $T i) that has an implicit tag check that would trap on an i31 value in much the same way as it would trap on null. Without this, a program would have to use i31ref types everywhere and downcast everywhere explicitly; a potentially more expensive check than just a tag check.

[sabine]

I see that WASM already has 64-bit integers, which suggests, that, eventually, WASM might be usable as a 64-bit compilation target. We are very interested in a spec that allows 63-bit unboxed scalars in addition to 31-bit unboxed scalars.

With ref i63 $T not being a subtype of anyref, it does not matter which pointer size the WASM engine uses internally.

Do you think it will be possible to import/export ref i31 $T explicitly from a WASM module (i.e. not as a private type or anything, just a plain import from one module and export from another)?

[jakobkummerow]

I'm generally supportive of this suggestion. In particular because it allows modules that don't need/use i31ref to avoid some i31 checks (they may be cheap, but not doing them at all is even cheaper).

I'm not sure how many checks would be avoidable in practice. I assume that the type lattice will have to be:

eqref == (ref null i31 eq) <: anyref == (ref null i31 any)
(ref null i31 $T) <: eqref  (for $T being a struct or array type)
(ref $T <: (ref null $T) <: (ref null i31 $T)
(ref $T <: (ref i31 $T) <: (ref null i31 $T)

So in particular, downcasts from anyref/eqref to (ref $T)/(ref null $T) will still have to include i31 checks; only downcasts from (ref any) or (ref null any) or (ref eq) or (ref null eq) can skip the i31 checks.

With ref i63 $T not being a subtype of anyref

@sabine : I would have assumed that all (ref ...) types will continue to be subtypes of anyref, in which case (ref i63 ...) would force all pointers to be 64 bit wide (and would rule out NaN boxing as an implementation strategy). At any rate, I think i63 is a separate discussion, and fairly orthogonal to this issue.

[sabine]

Ah, sorry about derailing. If all (ref ...) types must still be subtypes of anyref, then (ref i63 ...) is obviously not a reasonable thing to have.

[jakobkummerow]

I just realized that #76 creates an interesting wrinkle here. If we have to disallow (ref i31 extern), then I think we have to disallow (ref i31 any) too, but if anyref means (non-i31!) (ref null any), then all the (ref i31 $T) can't be subtypes of it, and the eqref shorthand can't have the i31 bit either. Modules could still define (ref i31 eq), but the type would be incompatible with anyref or eqref.

So on the one hand, that would imply that (contrary to my previous post) downcasts from anyref would not have to include i31 checks; but on the other hand, it would also mean that there's no way to define a type for a global/local/parameter/field that can hold a struct/array ref, or an i31, or a funcref (which would have been nice in order to close a functionality gap compared with the "two-types" proposal).

One solution would be to introduce more general union types.

One solution would be to introduce another built-in type that sits between anyref and its non-externref subtypes, i.e. would be the new supertype of funcref and eqref.

Am I overlooking anything?

[RossTate]

Nice catch, @jakobkummerow! To rephrase, no GC proposal with i31ref can have a common supertype between i31ref and externref, which in particular means no top type. Currently the designs of the Type Imports and GC proposals (and, to a lesser extent, Typed Function References) are premised around having a top type. So either we redesign around not having a top type and instead letting each related family of reference types specify whether it needs boxed scalars (and possibly what kind of boxed scalars), or it seems we need to remove i31ref (likely forever).

[tlively]

It seems like this simplest and least intrusive change would be to split externref off of the type hierarchy. Applications that need to use subtyping and casting could just use anyref in its place. But just to check my understanding, #76 means that there would be some conversion overhead under this solution because JS numbers as anyrefs would need to be boxed to be differentiated from i31refs?

[RossTate]

You would also have to either disallow imported types from representing externref or also split imported types off of the type hierarchy.

[jakobkummerow]

#76 means that there would be some conversion overhead under this solution because JS numbers as anyrefs would need to be boxed to be differentiated from i31refs?

That boxing would have to happen only if externref and i31ref overlap. It's a specific instance of a more general problem though: an externref pointer, being host-controlled, can have any arbitrary bit pattern. If we specify i31ref in Wasm with the expectation that it is encoded by giving one or more bits in a pointer particular meaning, then that means that in general, externref pointers could accidentally "look like an i31", which might lead to weird/unspecified behavior. Making sure that there is no overlap between externref and i31ref (or i31 type dimensions) means that externref pointers (including JS numbers) never have to go out of their way to accommodate the existence of i31 in Wasm.

[titzer]

@rossberg any thoughts?

If externref is a completely foreign reference type and split off the hierarchy, then an easy way to incorporate this into the binary format would be instead of the type construcotrs (ref null T) and (ref T) being 0x6C and 0x6B respectively (if encoded as a single byte), we could do:

(ref T) : 0x68 (0b01101000) (ref null T) : 0x69 (0b01101001) (ref i31 T) : 0x6A (0b01101010) (ref i31 null T) : 0x6B (0b01101011)

Basically, the low order two bits indicate the two orthogonal dimensions of the type: whether null or i31 values are allowed.

Also, currently anyref has its own type constructor, but we could just as easily specify that heap type index -1 (i.e. invalid) means any, so anyref would be encoded by one of the four above type constructors, followed by a -1 for the heap type index.

[dcodeIO]

What would be the non-canonical type of i31ref? (ref i31 i31)?

        any               i31
   ┌─────┼────┬─────┐
extern  func  eq   exn
         │    │
   signature* │
              │
          ┌───┴────┐
       struct*   array*

Dimensions: null? i31?

Given the i31 and extern overlap, I guess what's proposed above is

          any        i31     extern
    ┌──────┼─────┐
  func     eq   exn
    │      │
signature* │
           │
       ┌───┴────┐
    struct*   array*

Dimensions: null? (i31 | extern)?

disallowing mixing (ref i31 extern T)?

Makes me wonder, how does (ref null extern) work if the underlying extern pointer can have any bit pattern, as mentioned above, and is the exact pattern indicating null? Edit: Thinking further, that's probably covered by the type system, and while a host can theoretically pass in the bit pattern for null into an (ref extern), that's not a problem in practice?

[titzer]

I'm not sure what is meant by the "non-canonical type" of i31ref. Under this idea, i31 is not a type, in the same way that null is not a type.

I am also skeptical about the claim that externref values can have any bit pattern. If that were the case, then it could not have a common supertype with any other wasm value, heap or not, regardless of i31, since it would then be impossible to distinguish it (e.g. for a downcast) based on its bits alone. That's part of what that other issue was getting at: externrefs would have to be tagged by either being boxed or the top type being a fat pointer. The mapping of JavaScript numbers onto Wasm numbers is a semantic concern, and we're talking about representations here.

I think it's closer to the truth that a Wasm engine generally knows something about the encoding of externrefs of its host environment (e.g. they must be valid pointers into a common address space) and perhaps can work around those encodings if necessary. They generally aren't arbitrary bits.

[dcodeIO]

I'm not sure what is meant by the "non-canonical type" of i31ref. Under this idea, i31 is not a type, in the same way that null is not a type.

Hmm, interesting, so the closest type is (ref i31 eq) if non-nullable respectively (ref null i31 eq) if nullable, with initializers (i31.new (i31.const 0)) or (ref.null eq).

Makes me wonder about solving the i31 and extern overlap using a dimension then, since that'd imply removing externref as well which is already in phase 4 as part of reference types.

I am also skeptical about the claim that externref values can have any bit pattern. If that were the case, then it could not have a common supertype with any other wasm value

I am skeptical about externref in general. Once there's anyref, there isn't really much use for it anymore, and the last minute change of removing anyref and introducing externref made to reference types was already quite surprising to me. If there is indeed an overlap introduced here, which I'm not sure about anymore given your comment, then I think re-evaluating whether we really need the distinction might make sense. For instance, a clean approach to solve the overlap might be to rename externref to anyref in reference types (text format only change), and then build GC on top of that anyref, as initially planned. Or what am I missing?

[rossberg]

This is not a bad idea. It is one step further in the direction of a union type -- really, (ref null i31 $t) is (ref (union null i31 $t)). That raises the question, though, why stop there? Why shouldn't we also enable (ref (union null i31 $t $u $v)), which allows even more refined tracking of possible sets of references, and likewise allows eliding more checks.

In principle, any such refinement is useful. However, union types have rather problematic properties in terms of type-checking complexity and worst cases, which can explode quickly, in particular when also combined with intersection type, forms of which have also been suggested. And it's always possible to fall back to anyref as the largest union type, for the price of losing some precision. So it's a slippery slope, and I might be a bit hesitant to go there too quickly.

OTOH, maybe i31 is enough of a common case to justify tracking it specially (like null).

[jakobkummerow]

In the meantime, I've heard specific feedback that making i31 a ref type dimension would be more efficient/useful than the current proposal for surface languages that have primitive integers: they would typically represent such source-level integers as i31|$BoxedInt (for some custom $BoxedInt type). In the current proposal, this conceptual union type cannot be expressed more specifically than eqref, which has the downside that code processing such values must perform two checks: an i31 check, and then a checked cast to $BoxedInt. If there were a way to express this union type more accurately (either by making i31 a dimensional attribute (ref i31 $BoxedInt), or by introducing more general union types), then a single i31 check would be enough; at least if we type br_on_i31 properly.

[rossberg]

Yes, that's one obvious use case. Although you can easily find similar use cases for other kinds of small unions, so that alone isn't necessarily enough to justify special casing i31.

One problem I realised with making i31 a dimension unlike other reftypes is that that creates a problem for type imports/exports (and possibly generics): naturally, you want to be able to instantiate a type import with i31, but that wouldn't be possible if it was segregated into a separate dimension.

Proper union types would provide a coherent solution, but suffer from complexity (in particular, quadratic subtyping). Maybe we need to look for some middle ground.

[taralx]

Is it still quadratic if we don't support width subtyping of unions? The use cases I've gathered don't need it.

[rossberg]

@taralx, do you mean that A or A | B would not be subtypes of A | B | C? Wouldn't that defeat the purpose?

[taralx]

A|B wouldn't be a subtype of A|B|C, but A and B would be subtypes of both.

[rossberg]

That wouldn't compose, though. Imagine you have A|T, where T is an import, and that is latter instantiated with B|C. You'd need to either disallow unions over imports or disallow instantiating imports with unions, both of which seem like rather severe restrictions.

[taralx]

Let me think a bit more about it, but that might be ok. It probably requires coercive subtyping, though, which we've been avoiding so far.

[RossTate]

Subtyping for arbitrary union types is quadratic without recursive types. Subtyping for equi-recursive types is quadratic without arbitrary union types. The combination of these features is not quadratic and in fact may not even be polynomial. At least for the subtyping rules that would enable the standard automata-based subtyping algorithms, subtyping is PSPACE-complete. And that's without taking into account the contravariance that would be introduced by function types.

[taralx]

I'm left feeling like the correct thing is just to bound the "size" of types to make the problem tractable rather than restricting functionality to linear or near-linear complexity.

[RossTate]

Unfortunately low-level structural heap types tend to be quite large. If you think of a language like Java, a class's structural type includes not only all of its fields but also all of its overridable methods (as they are part of the v-table) as well as its meta-data (e.g. the data-structures used for interface-method dispatch, casting, and reflection) and then recursively the same components of any classes referenced by those fields or methods.

[askeksa-google]

I would like to resurface this issue. As @jakobkummerow mentions in https://github.com/WebAssembly/gc/issues/130#issuecomment-725415964, having i31 as a type dimension will save a cast during integer unboxing when integers use a hybrid i31-or-heap-box representation, which is the typical use of i31.

It goes further than this, though. When the source-language integer type is a subtype of other types (as is the case in Dart, where int has 3 supertypes: num, Object and Comparable), all of those supertypes can also potentially be i31, which means that every use of them requires an explicit cast on top of the i31 check. With i31 as a type dimension, that extra cast can be avoided.

There has been some discussion here about how to express in the type that a value is definitely an i31. My suggestion would be to not have such possibility, just like we currently don't have any possibility to express that a value is definitely null, even though that situation arises frequently. If you know that something is an integer, use an integer type for it.

With that in mind, it makes sense for br_on_i31 and br_on_non_i31 to convert the value to an i32 on the i31 branch. This is basically the only reasonable thing you can do with an i31 value, and with the typical representation of i31, such a combined check and conversion can be done very efficiently (just shift one to the right and branch on the carry flag).

Concretely, I propose to change the i31-related instructions as follows:

Instruction	Change
i31.new	Now takes a type immediate, similarly to ref.null.
i31.get_s, i31.get_u	Take any reference. Trap if the input is not an i31.
ref.is_i31	As before.
ref.as_i31	Replaced by ref.as_non_i31.
br_on_i31	Split into two: br_on_i31_s and br_on_i31_u. The i31 branch delivers an i32.
br_on_non_i31	Split into two: br_on_non_i31_s and br_on_non_i31_u. Fall-through delivers an i32.

Conceptually, it would make sense for many of these instructions to require the input to be i31able, but due to implicit upcasting, such a requirement would be inconsequential.

[askeksa-google]

Another consideration is how other instructions will handle i31able types and i31 values. For maximum consistency with the current treatment of null, this would look something like:

Instructions that currently perform an implicit null check for nullable inputs will also perform an implicit i31 check for i31able inputs.

The type sharpening instructions ref.as_func, ref.as_data, ref.as_array, ref.as_non_null and ref.cast will preserve the i31ness of the input type and will let i31 values through at runtime. This means that a cast all the way from anything to a specific type could involve up to four steps: ref.as_non_i31 ref.as_non_null ref.as_data ref.cast While the only requirement on the ordering of these is that ref.as_data must come before ref.cast, there could be a "recommended" ordering that is like to produce the best code in (baseline) compilers by avoiding redundant checks.

br_on_ instructions will reject i31 values.

We could also decide to diverge from null here, or to reconsider how null is treated.

[rossberg]

Not having a non-nullable i31ref would be bad. Then we would perhaps save some casts here, but for the price of requiring more checks there. FWIW, I use the positive knowledge that something is a proper i31 in various places in my compilers, avoiding unnecessary checks.

The fact that we cannot express a nullref type is not a good reason – quite the opposite, in fact, since both @titzer and I have already run into that limitation, which causes significant pain. So we already know it's bad design, and should rather fix that for null rather than proliferating it.

(Fortunately, that seems easy enough: we could treat null and i31 as two separate, compositional dimensions, as sketched earlier.)

However, a more fundamental problem is what I mentioned above: with type im/exports, we need a way to define a type export to be i31. Otherwise we lack essential expressiveness. That implies that we cannot treat i31 as an orthogonal dimension like null (where this does not matter), because any type import could be i31.

Bottom-line: if we want to separate i31, then we need union types in a more principled manner. Before, we thought that's not viable, because were concerned with the quadratic complexity of subtyping that unions implies. But perhaps the explicit subtype declarations introduced with the iso-recursive types proposal eliminates that problem?

[titzer]

@rossberg IIUC, you are referring to a scenario where a module B has a declared type import and module A would like to export a type (whatever we decide to call that type) that is only i31 values, and instantiate B with that type? And therefore A has to name some type that is only i31 values?

@askeksa-google I think it makes sense that i31.get_? would require the i31 dimension. If the input type doesn't have that dimension, they would statically be known to always trap, so it'd be degenerate. My design inclination would be to reject degenerate cases in validation--we do that for impossible casts right now, IIRC.

[askeksa-google]

(Fortunately, that seems easy enough: we could treat null and i31 as two separate, compositional dimensions, as sketched earlier.)

Yes, that is certainly the model I have been assuming all along.

All of the issues you mention would seem to be solved by introducing an empty (aka never aka bottom) heap type. Then a definite null is ref null empty, a definite i31 is ref i31 empty, and a nullable i31 is ref null i31 empty. I have run into the null limitation myself and would be in favor of introducing such a type. Even a plain ref empty can be useful sometimes.

Whether the br_on_ instructions will convert the i31 value to i32 or not is then a somewhat separable issue. Both would work in the empty-type scenario, since this retains the possibility of sharpening to specifically i31.

@askeksa-google I think it makes sense that i31.get_? would require the i31 dimension. If the input type doesn't have that dimension, they would statically be known to always trap, so it'd be degenerate. My design inclination would be to reject degenerate cases in validation--we do that for impossible casts right now, IIRC.

It certainly makes sense, but we can't express such a requirement without enacting an exception to implicit upcasting. This would be confusing and could potentially break instruction sequence composability. Though with empty, we could specify their input type to be ref null i31 empty (essentially reverting to their current requirement).

[titzer]

I was also thinking through the implications of an explicit empty heaptype and I think it would also work to sneak in the "universal" null by way of ref.null empty.

I don't understand the issue with implicit upcasting (by this I assume you mean subsumption). Can you give a more concrete example?

[askeksa-google]

I was also thinking through the implications of an explicit empty heaptype and I think it would also work to sneak in the "universal" null by way of ref.null empty.

We could drop the type immediate on ref.null and always type it as ref null empty, since that is assignable to any nullable type.

I don't understand the issue with implicit upcasting (by this I assume you mean subsumption). Can you give a more concrete example?

Say we specify that an instruction requires its input to be ref i31 T for some T. Since ref T is a subtype of ref i31 T, it would be valid to give the instruction something which has static type ref T, essentially making the i31 requirement ineffective. We can only allow an input to be i31, not require it.

This is no longer the case with empty, since we can then specify the input type as ref i31 empty, meaning "i31 or nothing", thus practically requiring it to be i31.

With empty, the instruction changes listed above are no longer needed. We could keep the existing i31 instructions as they are (replacing ref null? i31 by ref null? i31 empty) and just add ref.as_non_i31.