[GC] Add subtyping support for HeapTypes (#3597)

6 files changed, 206 insertions, 22 deletions

diff --git a/src/wasm-type.h b/src/wasm-type.h
index b61fe68a6..1b7ec5081 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -351,6 +351,9 @@ public:
 
   bool operator<(const HeapType& other) const;
   std::string toString() const;
+
+  // Returns true if left is a subtype of right. Subtype includes itself.
+  static bool isSubType(HeapType left, HeapType right);
 };
 
 typedef std::vector<Type> TypeList;
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 4936bc3ff..de98ffcdb 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -601,28 +601,10 @@ bool Type::isSubType(Type left, Type right) {
     return true;
   }
   if (left.isRef() && right.isRef()) {
-    // Everything is a subtype of anyref.
-    if (right == Type::anyref) {
-      return true;
-    }
-    // Various things are subtypes of eqref.
-    auto leftHeap = left.getHeapType();
-    auto rightHeap = right.getHeapType();
-    if ((leftHeap == HeapType::i31 || leftHeap.isArray() ||
-         leftHeap.isStruct()) &&
-        rightHeap == HeapType::eq &&
-        (!left.isNullable() || right.isNullable())) {
-      return true;
-    }
-    // All typed function signatures are subtypes of funcref.
-    if (leftHeap.isSignature() && rightHeap == HeapType::func &&
-        (!left.isNullable() || right.isNullable())) {
-      return true;
-    }
-    // A non-nullable type is a supertype of a nullable one
-    if (leftHeap == rightHeap && !left.isNullable()) {
-      // The only difference is the nullability.
-      assert(right.isNullable());
+    // Consider HeapType subtyping as well, and also that a non-nullable type is
+    // potentially a supertype of a nullable one.
+    if (HeapType::isSubType(left.getHeapType(), right.getHeapType()) &&
+        (left.isNullable() == right.isNullable() || !left.isNullable())) {
       return true;
     }
     return false;
@@ -822,6 +804,63 @@ Array HeapType::getArray() const {
   return getHeapTypeInfo(*this)->array;
 }
 
+static bool isFieldSubType(const Field& left, const Field& right) {
+  if (left == right) {
+    return true;
+  }
+  // Immutable fields can be subtypes.
+  if (left.mutable_ == Immutable && right.mutable_ == Immutable) {
+    return left.packedType == right.packedType &&
+           Type::isSubType(left.type, right.type);
+  }
+  return false;
+}
+
+bool HeapType::isSubType(HeapType left, HeapType right) {
+  // See:
+  // https://github.com/WebAssembly/function-references/blob/master/proposals/function-references/Overview.md#subtyping
+  // https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#defined-types
+  if (left == right) {
+    return true;
+  }
+  // Everything is a subtype of any.
+  if (right == HeapType::any) {
+    return true;
+  }
+  // Various things are subtypes of eq.
+  if ((left == HeapType::i31 || left.isArray() || left.isStruct()) &&
+      right == HeapType::eq) {
+    return true;
+  }
+  // All typed function signatures are subtypes of funcref.
+  // Note: signatures may get covariance at some point, but do not yet.
+  if (left.isSignature() && right == HeapType::func) {
+    return true;
+  }
+  if (left.isArray() && right.isArray()) {
+    auto leftField = left.getArray().element;
+    auto rightField = left.getArray().element;
+    // Array types support depth subtyping.
+    return isFieldSubType(leftField, rightField);
+  }
+  if (left.isStruct() && right.isStruct()) {
+    // Structure types support width and depth subtyping.
+    auto leftFields = left.getStruct().fields;
+    auto rightFields = left.getStruct().fields;
+    // There may be more fields on the left, but not less.
+    if (leftFields.size() < rightFields.size()) {
+      return false;
+    }
+    for (size_t i = 0; i < rightFields.size(); i++) {
+      if (!isFieldSubType(leftFields[i], rightFields[i])) {
+        return false;
+      }
+    }
+    return true;
+  }
+  return false;
+}
+
 bool Signature::operator<(const Signature& other) const {
   if (results != other.results) {
     return results < other.results;
diff --git a/test/subtypes.wast b/test/subtypes.wast
new file mode 100644
index 000000000..d37735777
--- /dev/null
+++ b/test/subtypes.wast
@@ -0,0 +1,44 @@
+;; Test that we can roundtrip struct and array types
+(module
+  ;; Arrays
+  (type $vector-i32 (array i32))
+
+  (type $vector-i31 (array (ref i31)))
+  (type $vector-any (array (ref any)))
+
+  ;; Structs
+  (type $struct-i31 (struct
+    (field (ref i31))
+  ))
+  (type $struct-any (struct
+    (field (ref any))
+  ))
+  (type $struct-i31_any (struct
+    (field (ref i31))
+    (field (ref any))
+  ))
+
+  (func $foo (param $no-null (ref $vector-i32))
+             (param $yes-null (ref null $vector-i32))
+    ;; ok to set a non-nullable reference to a nullable target
+    (local.set $no-null (local.get $yes-null))
+  )
+
+  (func $bar (param $v-i31 (ref $vector-i31))
+             (param $v-any (ref $vector-any))
+    ;; ok to set a vector of (immutable) i31s to a vector of anyies
+    (local.set $v-any (local.get $v-i31))
+  )
+
+  (func $baz (param $s-i31 (ref $struct-i31))
+             (param $s-any (ref $struct-any))
+    ;; ok to set a struct of an (immutable) i31 to a one of an any
+    (local.set $s-any (local.get $s-i31))
+  )
+
+  (func $boo (param $s-i31 (ref $struct-i31))
+             (param $s-i31_any (ref $struct-i31_any))
+    ;; also ok to have extra fields
+    (local.set $s-i31 (local.get $s-i31_any))
+  )
+)
diff --git a/test/subtypes.wast.from-wast b/test/subtypes.wast.from-wast
new file mode 100644
index 000000000..249421578
--- /dev/null
+++ b/test/subtypes.wast.from-wast
@@ -0,0 +1,32 @@
+(module
+ (type ${ref?|i31|} (struct (field (ref null i31))))
+ (type $[i32] (array i32))
+ (type $ref?|{ref?|i31|}|_ref?|{anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${anyref}))))
+ (type $ref?|{ref?|i31|}|_ref?|{ref?|i31|_anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${ref?|i31|_anyref}))))
+ (type $ref?|[i32]|_ref?|[i32]|_=>_none (func (param (ref null $[i32]) (ref null $[i32]))))
+ (type $ref?|[ref?|i31|]|_ref?|[anyref]|_=>_none (func (param (ref null $[ref?|i31|]) (ref null $[anyref]))))
+ (type ${anyref} (struct (field anyref)))
+ (type ${ref?|i31|_anyref} (struct (field (ref null i31)) (field anyref)))
+ (type $[anyref] (array anyref))
+ (type $[ref?|i31|] (array (ref null i31)))
+ (func $foo (param $no-null (ref null $[i32])) (param $yes-null (ref null $[i32]))
+  (local.set $no-null
+   (local.get $yes-null)
+  )
+ )
+ (func $bar (param $v-i31 (ref null $[ref?|i31|])) (param $v-any (ref null $[anyref]))
+  (local.set $v-any
+   (local.get $v-i31)
+  )
+ )
+ (func $baz (param $s-i31 (ref null ${ref?|i31|})) (param $s-any (ref null ${anyref}))
+  (local.set $s-any
+   (local.get $s-i31)
+  )
+ )
+ (func $boo (param $s-i31 (ref null ${ref?|i31|})) (param $s-i31_any (ref null ${ref?|i31|_anyref}))
+  (local.set $s-i31
+   (local.get $s-i31_any)
+  )
+ )
+)
diff --git a/test/subtypes.wast.fromBinary b/test/subtypes.wast.fromBinary
new file mode 100644
index 000000000..44f441f42
--- /dev/null
+++ b/test/subtypes.wast.fromBinary
@@ -0,0 +1,33 @@
+(module
+ (type ${ref?|i31|} (struct (field (ref null i31))))
+ (type $[i32] (array i32))
+ (type $ref?|{ref?|i31|}|_ref?|{anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${anyref}))))
+ (type $ref?|{ref?|i31|}|_ref?|{ref?|i31|_anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${ref?|i31|_anyref}))))
+ (type $ref?|[i32]|_ref?|[i32]|_=>_none (func (param (ref null $[i32]) (ref null $[i32]))))
+ (type $ref?|[ref?|i31|]|_ref?|[anyref]|_=>_none (func (param (ref null $[ref?|i31|]) (ref null $[anyref]))))
+ (type ${anyref} (struct (field anyref)))
+ (type ${ref?|i31|_anyref} (struct (field (ref null i31)) (field anyref)))
+ (type $[anyref] (array anyref))
+ (type $[ref?|i31|] (array (ref null i31)))
+ (func $foo (param $no-null (ref null $[i32])) (param $yes-null (ref null $[i32]))
+  (local.set $no-null
+   (local.get $yes-null)
+  )
+ )
+ (func $bar (param $v-i31 (ref null $[ref?|i31|])) (param $v-any (ref null $[anyref]))
+  (local.set $v-any
+   (local.get $v-i31)
+  )
+ )
+ (func $baz (param $s-i31 (ref null ${ref?|i31|})) (param $s-any (ref null ${anyref}))
+  (local.set $s-any
+   (local.get $s-i31)
+  )
+ )
+ (func $boo (param $s-i31 (ref null ${ref?|i31|})) (param $s-i31_any (ref null ${ref?|i31|_anyref}))
+  (local.set $s-i31
+   (local.get $s-i31_any)
+  )
+ )
+)
+
diff --git a/test/subtypes.wast.fromBinary.noDebugInfo b/test/subtypes.wast.fromBinary.noDebugInfo
new file mode 100644
index 000000000..d80e5afd0
--- /dev/null
+++ b/test/subtypes.wast.fromBinary.noDebugInfo
@@ -0,0 +1,33 @@
+(module
+ (type ${ref?|i31|} (struct (field (ref null i31))))
+ (type $[i32] (array i32))
+ (type $ref?|{ref?|i31|}|_ref?|{anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${anyref}))))
+ (type $ref?|{ref?|i31|}|_ref?|{ref?|i31|_anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${ref?|i31|_anyref}))))
+ (type $ref?|[i32]|_ref?|[i32]|_=>_none (func (param (ref null $[i32]) (ref null $[i32]))))
+ (type $ref?|[ref?|i31|]|_ref?|[anyref]|_=>_none (func (param (ref null $[ref?|i31|]) (ref null $[anyref]))))
+ (type ${anyref} (struct (field anyref)))
+ (type ${ref?|i31|_anyref} (struct (field (ref null i31)) (field anyref)))
+ (type $[anyref] (array anyref))
+ (type $[ref?|i31|] (array (ref null i31)))
+ (func $0 (param $0 (ref null $[i32])) (param $1 (ref null $[i32]))
+  (local.set $0
+   (local.get $1)
+  )
+ )
+ (func $1 (param $0 (ref null $[ref?|i31|])) (param $1 (ref null $[anyref]))
+  (local.set $1
+   (local.get $0)
+  )
+ )
+ (func $2 (param $0 (ref null ${ref?|i31|})) (param $1 (ref null ${anyref}))
+  (local.set $1
+   (local.get $0)
+  )
+ )
+ (func $3 (param $0 (ref null ${ref?|i31|})) (param $1 (ref null ${ref?|i31|_anyref}))
+  (local.set $0
+   (local.get $1)
+  )
+ )
+)
+