Question about the sub-typing rules

[birbe]

Hello, I'm writing a toy JVM in Rust that compiles to WASM. It dynamically generates WASM files that correspond to Java classes so that I can allocate the Java objects in the WASM heap using the GC types. It has an interpreter and a JIT compiler, and my question is about how sub-typing works with struct types on the heap. From my testing it looks like either the sub-typing rules in the GC spec are too strict or I'm using them incorrectly (I assume it's the latter). My test-case reduced down to having two modules generated from two classes:

public class ClassA {
     public int fieldA;
}

and the second class

public class ClassB extends ClassA {
    public int fieldB;
}

Essentially, ClassA would be represented as (struct (field i32)) and ClassB would be (struct (field i32) (field i32)) (Apologies if I wrote this syntax incorrectly). The module generated for ClassB would insert the corresponding struct type into the end of a recursive type definition, specifying that the struct type definition for ClassA is the supertype. My issue is that I do not know ahead of time which classes will be extended. Meaning that it appears a function compiled from Java to WebAssembly in a module which strictly defines ClassA (and does not define ClassB as a sub-type, as it is not aware of it's existence) will not be able to accept a (ref $ClassB) in place of a (ref $ClassA). Did I simply misinterpret what I was seeing in the debugger or is this correct behavior?

[birbe]

specifically, I encountered this issue when I tried to add headers to each struct I allocate into the heap. Java objects have metadata (such as to which class they belong to) and I was trying to emulate this in WASM by having every object begin with a (field i32) (which would be initialized as a pointer to a data structure in memory). Every struct began with said i32 field; they also specified that they had a super-type which was nothing but (struct (field i32)). When I tried to pass arbitrary references to structs (which began with the i32 field but contained other fields) into a function which expected a reference to just a (struct (field i32)), I got a cast error in the debugger. The cast error went away when I manually added the definition for the sub-type into the module inside of a recursive type definition. This isn't feasible to do automatically as I am not aware when generating a class which classes will extend it or what their field layouts would be, and things are therefore put into separate modules

[kripken]

In the example should public class ClassB { be public class ClassB extends ClassA {?

[tlively]

Can you share the text format of the modules/types you are generating? That will make it easier to spot the problem.

[birbe]

In the example should public class ClassB { be public class ClassB extends ClassA {?

good catch, i've just updated it

[birbe]

Can you share the text format of the modules/types you are generating? That will make it easier to spot the problem.

sure, i'll grab them

[rossberg]

When defining the representation type for A you don't need to know what types extend it later. But when you define the representation type for B you of course need to know which types it extends. This is no different from Java itself.

If I understand your question correctly, all representations share a common ancestor, which is your struct with just i32. So what is the problem with declaring all types subtypes of this one?

Note that type definitions do not have to be within the same recursion group to be subtypes. You can do this:

(rec
  (type $obj (sub (struct (field i32))))
)

(rec
  (type $A (sub $obj (struct (field i32 i32))))
)

(rec
  (type $B (sub $A (struct (field i32 i32 i32))))
)

Furthermore, if these definitions occur in multiple modules they will still be compatible, even when some of these modules do not contain $A or $B.

[birbe]

When defining the representation type for A you don't need to know what types extend it later. But when you define the representation type for B you of course need to know which types it extends. This is no different from Java itself.

If I understand your question correctly, all representations share a common ancestor, which is your struct with just i32. So what is the problem with declaring all types subtypes of this one?

Note that type definitions do not have to be within the same recursion group to be subtypes. You can do this:

(rec
  (type $obj (sub (struct (field i32))))
)

(rec
  (type $A (sub $obj (struct (field i32 i32))))
)

(rec
  (type $B (sub $A (struct (field i32 i32 i32))))
)

Furthermore, if these definitions occur in multiple modules they will still be compatible, even when some of these modules do not contain $A or $B.

I already am defining all the classes as ancestors of the (struct (field i32)), or, at least, I'm pretty sure I am; here's the helper module I generate when the JVM first loads (the array types can be ignored, I've disabled their usage atm):

(module
  (type $type0 (struct (field $field0 (mut i32))))
  (type $type1 (array (field (mut structref))))
  (type $type2 (array (field (mut i8))))
  (type $type3 (array (field (mut i16))))
  (type $type4 (array (field (mut i32))))
  (type $type5 (array (field (mut i64))))
  (type $type6 (array (field (mut f32))))
  (type $type7 (array (field (mut f64))))
  (table $jvm.objects (;0;) (import "jvm" "objects") 0 anyref)
  (func $jvm.alloc_ref (;0;) (import "jvm" "alloc_ref") (result i32))
  (func $obj_class (;1;) (export "obj_class") (param $var0 i32) (result i32)
    local.get $var0
    table.get $jvm.objects
    ref.cast null $type0
    struct.get $type0 $field0
  )
)

Here's the shortened version of the WASM module that created the struct that's passed in. I've attached the full version as a file

(module
  (type $type0 (struct (field $field0 (mut i32))))
  (type $type1 (struct_subtype (field $field0 (mut i32)) $type0))
  (type $type2 (struct_subtype (field $field0 (mut i32)) (field $field1 (mut i32)) $type1))
  (type $type3 (struct_subtype
    (field $field0 (mut i32))
    (field $field1 (mut i32))
    (field $field2 (mut i32))
    $type2))
)

Main$Test wat.txt

Here's the error I get in Edge's debugger

[kripken]

You may be declaring your base type as final, which does not allow subtyping. Try to use struct_subtype on the base type and not just struct. Or, in the final text format, this:

(module
  (type $type0 (sub (struct (field $field0 (mut i32)))))
  (type $type1 (sub $type0 (struct (field $field0 (mut i32)))))
  (type $type2 (sub $type1 (struct (field $field0 (mut i32)) (field $field1 (mut i32)))))
  (type $type3 (sub $type2 (struct
    (field $field0 (mut i32))
    (field $field1 (mut i32))
    (field $field2 (mut i32))
  )))
)

Note the use of (sub ..) for $type0 even though it has no declared supertype, without which it will error on attempts to subtype it.

[birbe]

I'm using the wasm_encoder crate for generating the WASM modules. after checking my code, I can confirm that nowhere do I have it set to final for any type. The base type is also already declared as a sub-type, specifically I use this https://docs.rs/wasm-encoder/latest/wasm_encoder/struct.TypeSection.html#method.rec and all of the types in the hierarchy are in the provided iterator

[tlively]

What tool are you using to generate the text here? I ask because parts of this text use older pre-standard syntax (e.g. struct_subtype and ref.cast null) and using an out-of-date disassembler may be hiding the real issue.

(FWIW it looks like Edge's disassembler is also out-of-date)

Even with the older text format, it looks like none of your structs are actually declaring a supertype. Could that be the issue?

[birbe]

What tool are you using to generate the text here? I ask because parts of this text use older pre-standard syntax (e.g. struct_subtype and ref.cast null) and using an out-of-date disassembler may be hiding the real issue.

(FWIW it looks like Edge's disassembler is also out-of-date)

Even with the older text format, it looks like none of your structs are actually declaring a supertype. Could that be the issue?

yeah it looks like Edge is printing it out improperly. here's it debugged with wasmprinter

(module
  (rec
    (type (;0;) (sub (struct (field (mut i32)))))
    (type (;1;) (sub 0 (struct (field (mut i32)))))
    (type (;2;) (sub 1 (struct (field (mut i32)) (field (mut i32)))))
    (type (;3;) (sub 2 (struct (field (mut i32)) (field (mut i32)) (field (mut i32)))))
  )
)

[birbe]

and the helper class:

(module
  (rec
    (type (;0;) (sub (struct (field (mut i32)))))
  )
  (type (;1;) (array (mut structref)))
  (type (;2;) (array (mut i8)))
  (type (;3;) (array (mut i16)))
  (type (;4;) (array (mut i32)))
  (type (;5;) (array (mut i64)))
  (type (;6;) (array (mut f32)))
  (type (;7;) (array (mut f64)))
  (type (;8;) (func (result i32)))
  (type (;9;) (func (param i32) (result i32)))
  (type (;10;) (func (param i32 i32) (result i32)))
  (type (;11;) (func (param i32 i32 i32)))
  (import "jvm" "objects" (table (;0;) 0 anyref))
  (import "jvm" "alloc_ref" (func (;0;) (type 8)))
  (func (;1;) (type 9) (param i32) (result i32)
    local.get 0
    table.get 0
    ref.cast (ref null 0)
    struct.get 0 0
  )
  (export "obj_class" (func 1))
)

[tlively]

Alright, great, I think I know what the issue is now.

In the one module, your top Object type ((type (;0;) (sub (struct (field (mut i32)))))) is declared in the same rec group as a bunch of other things and in the other module it is in its own rec group.

Since type identity is determined by index into a rec group and these Object types are defined in rec groups with different structures, you're actually defining two different Object types rather than the same Object type in two places. That's why the cast is failing; the Object types are incompatible with each other.

The fix is to make sure the rec groups are the same in every module, probably by making them as small as possible, as @rossberg suggested.

[birbe]

I think I understand, I'll try it out and report back. tysm!

[birbe]

making all of the struct types be in their own recursive group fixed my issue. thank you for being so helpful!