Java array types

[konsoletyper]

According to https://webassembly.github.io/gc/core/valid/matching.html#composite-types array types are covariant only if they are immutable (i.e. A <: B => const array(A) <: const array(B) , but !(A <: B => mut array(A) <: mut array(B))). However, in Java type system there are no immutable array types and yet all arrays are covariant. This can cause runtime exception (namely, ArrayStoreException). This makes WebAssembly GC type system inconvenient for representing Java arrays. I'm struggling with this issue and could not make up anything better than representing all Java arrays as array (null struct $java_lang_Object) and do a type cast on get. I believe doing a type cast on each read from array is not quite efficient. Also, this requires extra bytes in binary representation.

I have an idea how to make this look better. If there were "contravariant" array types (e.g. something like writeonly array), then I could represent writing to an array as two instructions:

• cast covariant read-only array to contravariant write-only array. Here trap can occur which corresponds to ArrayStoreException (or additional check can be performed prior to this cast to throw actual ASE).
• write to the write-only array without any possible trap.

This would be more efficient, since first cast can be optimized out for further writes using some combination of loop invariant motion and global value numbering.

Or am I missing something and there's already a way to represent Java arrays efficiently?

[sjrd]

I'm struggling with this issue and could not make up anything better than representing all Java arrays as array (null struct $java_lang_Object) and do a type cast on get.

Indeed, it seems that is the best we can do. Some pointers about what we did in Scala.js:

• High-level presentation of the array encoding
• Codegen to read an element, including the extra ref.cast
• Codegen to write an element
• Commit that implements all the right ArrayStoreExceptions

I'm not sure how a write-only contravariant array would help. It might but you would also need the read-only covariant correspondant to read values of the arrays. Currently an (array (mut A)) is not a subtype of (array A), so you can't even do that direction. In fact, if that subtype relationship did exist, we would not necessarily need the contravariant direction. All we need is a virtual call on sets:

• When allocating a String[], create a (array (mut String)), and store it as a (array String).
• Upon reading, you get a String (yeah!)
• You can upcast further to (array Object), so your String[] can be a subtype of Object[] (yeah!)
• Upon reading, you don't known the precise mutable subtype of array, so you cannot statically perform any correct ref.cast. However, you can call a virtual set method on your array class, which is implemented for every concrete type of array. That set method can cast the argument and the array to the correct type (or throw an ASE).

That shifts the inefficiency from reading to writing, which is what we want.

But we can't do that because (array (mut String)) is not a sub-heap type of (array String), unfortunately.

[sjrd]

In fact, if that subtype relationship did exist, we would not necessarily need the contravariant direction.

Note that there is a good reason for that relationship not to exist. It guarantees that an array.get on an immutable array is an idempotent operation, which can therefore be deduplicated under optimizations such as CSE and loop-invariant code motion.

So really we would need a new kind of field type that is (read A), such as in (array (read A)). That one could be a super field type of both A and (mut A), while being soundly covariant.

[konsoletyper]

Currently an (array (mut A)) is not a subtype of (array A), so you can't even do that direction

Ah, sure, missed this point. Yes, introduction of (read A) would help, but then contravariant (write A) would also improve set performance

[rossberg]

Distinguishing readonly fields and a corresponding mutability lattice is on the Post-MVP feature list. But even with that there is no free lunch.

Covariant mutable arrays would require building in appropriate implicit runtime checks for assignments into Wasm to maintain soundness. But if built-in in Wasm, this would of course be Wasm-level runtime checks, relative to Wasm types. Since the Wasm type system is different and generally much simpler than that of source languages and not expressive enough to encode those, these checks would almost never be sufficient. Source-level checks still need to be implemented on top of Wasm's checks, and usually require extra tests and a custom representation for runtime types – already in the Java case, e.g., to represent array types faithfully, but even more so in languages with richer runtime types, such as C#.

Hence, overall I suspect the cost savings are gonna be much smaller than what you might expect, for the price of a fat and fairly language-specific feature. At the same time, there are a thousand other type system features in other languages that have similar problems but would not benefit.