[Wasm GC] Support and fuzz function subtyping (#5420)

Support function subtyping with contravariant parameters and covariant results.
The actual change is a single line in wasm-type.cpp, so most of the patch is
updating the type fuzzer to generate interesting function subtypes. Since
function parameters are covariant, generating a function subtype requires
generating supertypes of its parameter types, which required new functionality
in the fuzzer. Also update the fuzzer to choose to reuse types at a finer grain,
so for example individual function parameters or results might be reused
unmodified while other parameters or results are still modified.

3 files changed, 196 insertions, 53 deletions

diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 98f9ea733..d91266d49 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1967,7 +1967,7 @@ Expression* TranslateToFuzzReader::makeRefFuncConst(Type type) {
   }
   // TODO: randomize the order
   for (auto& func : wasm.functions) {
-    if (Type::isSubType(type, Type(func->type, NonNullable))) {
+    if (Type::isSubType(Type(func->type, NonNullable), type)) {
       return builder.makeRefFunc(func->name, func->type);
     }
   }
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 8b9d824d1..a356e8b5b 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -240,70 +240,115 @@ struct HeapTypeGeneratorImpl {
 
   Array generateArray() { return {generateField()}; }
 
-  template<typename Kind> std::optional<HeapType> pickKind() {
-    std::vector<Index> candidateIndices;
+  template<typename Kind> std::vector<HeapType> getKindCandidates() {
+    std::vector<HeapType> candidates;
     // Iterate through the top level kinds, finding matches for `Kind`. Since we
     // are constructing a child, we can only look through the end of the current
     // recursion group.
     for (Index i = 0, end = recGroupEnds[index]; i < end; ++i) {
       if (std::get_if<Kind>(&typeKinds[i])) {
-        candidateIndices.push_back(i);
+        candidates.push_back(builder[i]);
       }
     }
-    if (candidateIndices.size()) {
-      return builder[rand.pick(candidateIndices)];
+    return candidates;
+  }
+
+  template<typename Kind> std::optional<HeapType> pickKind() {
+    auto candidates = getKindCandidates<Kind>();
+    if (candidates.size()) {
+      return rand.pick(candidates);
     } else {
       return std::nullopt;
     }
   }
 
   HeapType pickSubFunc() {
-    if (auto type = pickKind<SignatureKind>()) {
-      return *type;
-    } else if (rand.oneIn(2)) {
-      return HeapType::nofunc;
-    } else {
-      return HeapType::func;
+    auto choice = rand.upTo(8);
+    switch (choice) {
+      case 0:
+        return HeapType::func;
+      case 1:
+        return HeapType::nofunc;
+      default:
+        if (auto type = pickKind<SignatureKind>()) {
+          return *type;
+        }
+        return (choice % 2) ? HeapType::func : HeapType::nofunc;
     }
   }
 
   HeapType pickSubStruct() {
-    if (auto type = pickKind<StructKind>()) {
-      return *type;
-    } else if (rand.oneIn(2)) {
-      return HeapType::none;
-    } else {
-      return HeapType::struct_;
+    auto choice = rand.upTo(8);
+    switch (choice) {
+      case 0:
+        return HeapType::struct_;
+      case 1:
+        return HeapType::none;
+      default:
+        if (auto type = pickKind<StructKind>()) {
+          return *type;
+        }
+        return (choice % 2) ? HeapType::struct_ : HeapType::none;
     }
   }
 
   HeapType pickSubArray() {
-    if (auto type = pickKind<ArrayKind>()) {
-      return *type;
-    } else if (rand.oneIn(2)) {
-      return HeapType::none;
-    } else {
-      return HeapType::array;
+    auto choice = rand.upTo(8);
+    switch (choice) {
+      case 0:
+        return HeapType::array;
+      case 1:
+        return HeapType::none;
+      default:
+        if (auto type = pickKind<ArrayKind>()) {
+          return *type;
+        }
+        return (choice % 2) ? HeapType::array : HeapType::none;
     }
   }
 
   HeapType pickSubEq() {
-    switch (rand.upTo(3)) {
+    auto choice = rand.upTo(16);
+    switch (choice) {
       case 0:
-        return HeapType::i31;
+        return HeapType::eq;
       case 1:
-        return pickSubStruct();
+        return HeapType::array;
       case 2:
-        return pickSubArray();
+        return HeapType::struct_;
+      case 3:
+        return HeapType::none;
+      default: {
+        auto candidates = getKindCandidates<StructKind>();
+        auto arrayCandidates = getKindCandidates<ArrayKind>();
+        candidates.insert(
+          candidates.end(), arrayCandidates.begin(), arrayCandidates.end());
+        if (candidates.size()) {
+          return rand.pick(candidates);
+        }
+        switch (choice >> 2) {
+          case 0:
+            return HeapType::eq;
+          case 1:
+            return HeapType::array;
+          case 2:
+            return HeapType::struct_;
+          case 3:
+            return HeapType::none;
+          default:
+            WASM_UNREACHABLE("unexpected index");
+        }
+      }
     }
-    WASM_UNREACHABLE("unexpected index");
   }
 
   HeapType pickSubAny() {
-    switch (rand.upTo(2)) {
+    switch (rand.upTo(8)) {
       case 0:
-        return HeapType::eq;
+        return HeapType::any;
       case 1:
+        return HeapType::none;
+      default:
         return pickSubEq();
     }
     WASM_UNREACHABLE("unexpected index");
@@ -315,13 +360,26 @@ struct HeapTypeGeneratorImpl {
       // This is a constructed type, so we know where its subtypes are, but we
       // can only choose those defined before the end of the current recursion
       // group.
-      std::vector<Index> candidateIndices;
+      std::vector<HeapType> candidates;
       for (auto i : subtypeIndices[it->second]) {
         if (i < recGroupEnds[index]) {
-          candidateIndices.push_back(i);
+          candidates.push_back(builder[i]);
+        }
+      }
+      // Very rarely choose the relevant bottom type instead. We can't just use
+      // `type.getBottom()` because `type` may not have been initialized yet in
+      // the builder.
+      if (rand.oneIn(candidates.size() * 8)) {
+        auto* kind = &typeKinds[it->second];
+        if (auto* basic = std::get_if<BasicKind>(kind)) {
+          return HeapType(*basic).getBottom();
+        } else if (std::get_if<SignatureKind>(kind)) {
+          return HeapType::nofunc;
+        } else {
+          return HeapType::none;
         }
       }
-      return builder[rand.pick(candidateIndices)];
+      return rand.pick(candidates);
     } else {
       // This is not a constructed type, so it must be a basic type.
       assert(type.isBasic());
@@ -352,10 +410,76 @@ struct HeapTypeGeneratorImpl {
         case HeapType::nofunc:
           return type;
       }
-      WASM_UNREACHABLE("unexpected kind");
+      WASM_UNREACHABLE("unexpected type");
     }
   }
 
+  HeapType pickSuperHeapType(HeapType type) {
+    std::vector<HeapType> candidates;
+    auto it = typeIndices.find(type);
+    if (it != typeIndices.end()) {
+      // This is a constructed type, so we know its supertypes. Collect the
+      // supertype chain as well as basic supertypes. We can't inspect `type`
+      // directly because it may not have been initialized yet in the builder.
+      for (std::optional<Index> curr = it->second; curr;
+           curr = supertypeIndices[*curr]) {
+        candidates.push_back(builder[*curr]);
+      }
+      auto* kind = &typeKinds[it->second];
+      if (std::get_if<StructKind>(kind)) {
+        candidates.push_back(HeapType::struct_);
+        candidates.push_back(HeapType::eq);
+        candidates.push_back(HeapType::any);
+        return rand.pick(candidates);
+      } else if (std::get_if<ArrayKind>(kind)) {
+        candidates.push_back(HeapType::array);
+        candidates.push_back(HeapType::eq);
+        candidates.push_back(HeapType::any);
+        return rand.pick(candidates);
+      } else if (std::get_if<SignatureKind>(kind)) {
+        candidates.push_back(HeapType::func);
+        return rand.pick(candidates);
+      } else {
+        // A constructed basic type. Fall through to add all of the basic
+        // supertypes as well.
+        type = *std::get_if<BasicKind>(kind);
+      }
+    }
+    // This is not a constructed type, so it must be a basic type.
+    assert(type.isBasic());
+    candidates.push_back(type);
+    switch (type.getBasic()) {
+      case HeapType::ext:
+      case HeapType::func:
+      case HeapType::any:
+        break;
+      case HeapType::eq:
+        candidates.push_back(HeapType::any);
+        break;
+      case HeapType::i31:
+      case HeapType::struct_:
+      case HeapType::array:
+        candidates.push_back(HeapType::eq);
+        candidates.push_back(HeapType::any);
+        break;
+      case HeapType::string:
+      case HeapType::stringview_wtf8:
+      case HeapType::stringview_wtf16:
+      case HeapType::stringview_iter:
+        candidates.push_back(HeapType::any);
+        break;
+      case HeapType::none:
+        return pickSubAny();
+      case HeapType::nofunc:
+        return pickSubFunc();
+      case HeapType::noext:
+        candidates.push_back(HeapType::ext);
+        break;
+    }
+    assert(!candidates.empty());
+    return rand.pick(candidates);
+  }
+
   // TODO: Make this part of the wasm-type.h API
   struct Ref {
     HeapType type;
@@ -369,8 +493,22 @@ struct HeapTypeGeneratorImpl {
     return {pickSubHeapType(super.type), nullability};
   }
 
+  Ref generateSuperRef(Ref sub) {
+    auto nullability = sub.nullability == Nullable ? Nullable
+                       : rand.oneIn(2)             ? Nullable
+                                                   : NonNullable;
+    return {pickSuperHeapType(sub.type), nullability};
+  }
+
   Type generateSubtype(Type type) {
-    if (type.isRef()) {
+    if (type.isTuple()) {
+      std::vector<Type> types;
+      types.reserve(type.size());
+      for (auto t : type) {
+        types.push_back(generateSubtype(t));
+      }
+      return builder.getTempTupleType(types);
+    } else if (type.isRef()) {
       auto ref = generateSubRef({type.getHeapType(), type.getNullability()});
       return builder.getTempRefType(ref.type, ref.nullability);
     } else if (type.isBasic()) {
@@ -381,9 +519,28 @@ struct HeapTypeGeneratorImpl {
     }
   }
 
+  Type generateSupertype(Type type) {
+    if (type.isTuple()) {
+      std::vector<Type> types;
+      types.reserve(type.size());
+      for (auto t : type) {
+        types.push_back(generateSupertype(t));
+      }
+      return builder.getTempTupleType(types);
+    } else if (type.isRef()) {
+      auto ref = generateSuperRef({type.getHeapType(), type.getNullability()});
+      return builder.getTempRefType(ref.type, ref.nullability);
+    } else if (type.isBasic()) {
+      // Non-reference basic types do not have supertypes.
+      return type;
+    } else {
+      WASM_UNREACHABLE("unexpected type kind");
+    }
+  }
+
   Signature generateSubSignature(Signature super) {
-    // TODO: Update this once we support nontrivial function subtyping.
-    return super;
+    return Signature(generateSupertype(super.params),
+                     generateSubtype(super.results));
   }
 
   Field generateSubField(Field super) {
@@ -399,9 +556,6 @@ struct HeapTypeGeneratorImpl {
   }
 
   Struct generateSubStruct(const Struct& super) {
-    if (rand.oneIn(2)) {
-      return super;
-    }
     std::vector<Field> fields;
     // Depth subtyping
     for (auto field : super.fields) {
@@ -416,9 +570,6 @@ struct HeapTypeGeneratorImpl {
   }
 
   Array generateSubArray(Array super) {
-    if (rand.oneIn(2)) {
-      return super;
-    }
     return {generateSubField(super.element)};
   }
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index d06bfcbe7..64fd07759 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1728,10 +1728,7 @@ bool SubTyper::isSubType(const Field& a, const Field& b) {
 }
 
 bool SubTyper::isSubType(const Signature& a, const Signature& b) {
-  // TODO: Implement proper signature subtyping, covariant in results and
-  // contravariant in params, once V8 implements it.
-  // return isSubType(b.params, a.params) && isSubType(a.results, b.results);
-  return a == b;
+  return isSubType(b.params, a.params) && isSubType(a.results, b.results);
 }
 
 bool SubTyper::isSubType(const Struct& a, const Struct& b) {
@@ -2906,11 +2903,6 @@ TypeBuilder::BuildResult TypeBuilder::build() {
     state.newInfos.emplace_back(std::move(info));
   }
 
-#if TRACE_CANONICALIZATION
-  std::cerr << "Before replacing basic heap types:\n";
-  state.dump();
-#endif
-
   // Eagerly replace references to built basic heap types so the more
   // complicated canonicalization algorithms don't need to consider them.
   canonicalizeBasicTypes(state);