Check for correct subtyping in the type fuzzer (#4350)

Check that types that were meant to have a subtype relationship actually do. To
expose the intended subtyping to the fuzzer, expose `subtypeIndices` in the
return value of the type generation function.

5 files changed, 126 insertions, 91 deletions

diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 9992baf55..ce14d129f 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -23,17 +23,17 @@ namespace wasm {
 
 namespace {
 
-struct HeapTypeGenerator {
+struct HeapTypeGeneratorImpl {
+  HeapTypeGenerator result;
+  TypeBuilder& builder;
+  std::vector<std::vector<Index>>& subtypeIndices;
+  std::vector<std::optional<Index>> supertypeIndices;
   Random& rand;
   FeatureSet features;
-  TypeBuilder builder;
 
   // Map the HeapTypes we are building to their indices in the builder.
   std::unordered_map<HeapType, Index> typeIndices;
 
-  // For each type we will build, the indices of its subtypes we will build.
-  std::vector<std::vector<Index>> subtypeIndices;
-
   // Abstract over all the types that may be assigned to a builder slot.
   using Assignable =
     std::variant<HeapType::BasicHeapType, Signature, Struct, Array>;
@@ -47,8 +47,74 @@ struct HeapTypeGenerator {
   using HeapTypeKind = std::variant<BasicKind, SignatureKind, DataKind>;
   std::vector<HeapTypeKind> typeKinds;
 
-  HeapTypeGenerator(Random& rand, FeatureSet features, size_t n)
-    : rand(rand), features(features), builder(n), subtypeIndices(n) {}
+  HeapTypeGeneratorImpl(Random& rand, FeatureSet features, size_t n)
+    : result{TypeBuilder(n),
+             std::vector<std::vector<Index>>(n),
+             std::vector<std::optional<Index>>(n)},
+      builder(result.builder), subtypeIndices(result.subtypeIndices),
+      supertypeIndices(n), rand(rand), features(features) {
+    // Set up the subtype relationships. Start with some number of root types,
+    // then after that start creating subtypes of existing types. Determine the
+    // top-level kind of each type in advance so that we can appropriately use
+    // types we haven't constructed yet.
+    // TODO: Determine individually whether each HeapType is nominal once
+    // mixing type systems is expected to work.
+    typeKinds.reserve(builder.size());
+    supertypeIndices.reserve(builder.size());
+    Index numRoots = 1 + rand.upTo(builder.size());
+    for (Index i = 0; i < builder.size(); ++i) {
+      typeIndices.insert({builder[i], i});
+      // Everything is a subtype of itself.
+      subtypeIndices[i].push_back(i);
+      if (i < numRoots) {
+        // This is a root type with no supertype. Choose a kind for this type.
+        typeKinds.emplace_back(generateHeapTypeKind());
+      } else {
+        // This is a subtype. Choose one of the previous types to be the
+        // supertype.
+        Index super = rand.upTo(i);
+        builder[i].subTypeOf(builder[super]);
+        supertypeIndices[i] = super;
+        subtypeIndices[super].push_back(i);
+        typeKinds.push_back(getSubKind(typeKinds[super]));
+      }
+    }
+
+    // Create the heap types.
+    for (Index i = 0; i < builder.size(); ++i) {
+      auto kind = typeKinds[i];
+      if (auto* basic = std::get_if<BasicKind>(&kind)) {
+        // The type is already determined.
+        builder[i] = *basic;
+      } else if (!supertypeIndices[i] ||
+                 builder.isBasic(*supertypeIndices[i])) {
+        // No nontrivial supertype, so create a root type.
+        if (std::get_if<SignatureKind>(&kind)) {
+          builder[i] = generateSignature();
+        } else if (std::get_if<DataKind>(&kind)) {
+          if (rand.oneIn(2)) {
+            builder[i] = generateStruct();
+          } else {
+            builder[i] = generateArray();
+          }
+        } else {
+          WASM_UNREACHABLE("unexpected kind");
+        }
+      } else {
+        // We have a supertype, so create a subtype.
+        HeapType supertype = builder[*supertypeIndices[i]];
+        if (supertype.isSignature()) {
+          builder[i] = generateSubSignature(supertype.getSignature());
+        } else if (supertype.isStruct()) {
+          builder[i] = generateSubStruct(supertype.getStruct());
+        } else if (supertype.isArray()) {
+          builder[i] = generateSubArray(supertype.getArray());
+        } else {
+          WASM_UNREACHABLE("unexpected kind");
+        }
+      }
+    }
+  }
 
   HeapType::BasicHeapType generateBasicHeapType() {
     return rand.pick(HeapType::func,
@@ -404,82 +470,13 @@ struct HeapTypeGenerator {
       return super;
     }
   }
-
-  std::vector<HeapType> generate() {
-    // Set up the subtype relationships. Start with some number of root types,
-    // then after that start creating subtypes of existing types. Determine the
-    // top-level kind of each type in advance so that we can appropriately use
-    // types we haven't constructed yet.
-    // TODO: Determine individually whether each HeapType is nominal once
-    // mixing type systems is expected to work.
-    typeKinds.reserve(builder.size());
-    std::vector<std::optional<Index>> supertypeIndices(builder.size());
-    Index numRoots = 1 + rand.upTo(builder.size());
-    for (Index i = 0; i < builder.size(); ++i) {
-      typeIndices.insert({builder[i], i});
-      // Everything is a subtype of itself.
-      subtypeIndices[i].push_back(i);
-      if (i < numRoots) {
-        // This is a root type with no supertype. Choose a kind for this type.
-        typeKinds.emplace_back(generateHeapTypeKind());
-      } else {
-        // This is a subtype. Choose one of the previous types to be the
-        // supertype.
-        Index super = rand.upTo(i);
-        builder[i].subTypeOf(builder[super]);
-        supertypeIndices[i] = super;
-        subtypeIndices[super].push_back(i);
-        typeKinds.push_back(getSubKind(typeKinds[super]));
-      }
-    }
-
-    // Create the heap types.
-    for (Index i = 0; i < builder.size(); ++i) {
-      auto kind = typeKinds[i];
-      if (auto* basic = std::get_if<BasicKind>(&kind)) {
-        // The type is already determined.
-        builder[i] = *basic;
-      } else if (!supertypeIndices[i] ||
-                 builder.isBasic(*supertypeIndices[i])) {
-        // No nontrivial supertype, so create a root type.
-        if (std::get_if<SignatureKind>(&kind)) {
-          builder[i] = generateSignature();
-        } else if (std::get_if<DataKind>(&kind)) {
-          if (rand.oneIn(2)) {
-            builder[i] = generateStruct();
-          } else {
-            builder[i] = generateArray();
-          }
-        } else {
-          WASM_UNREACHABLE("unexpected kind");
-        }
-      } else {
-        // We have a supertype, so create a subtype.
-        HeapType supertype = builder[*supertypeIndices[i]];
-        if (supertype.isSignature()) {
-          builder[i] = generateSubSignature(supertype.getSignature());
-        } else if (supertype.isStruct()) {
-          builder[i] = generateSubStruct(supertype.getStruct());
-        } else if (supertype.isArray()) {
-          builder[i] = generateSubArray(supertype.getArray());
-        } else {
-          WASM_UNREACHABLE("unexpected kind");
-        }
-      }
-    }
-    return builder.build();
-  }
 };
 
 } // anonymous namespace
 
-namespace HeapTypeFuzzer {
-
-std::vector<HeapType>
-generateHeapTypes(Random& rand, FeatureSet features, size_t n) {
-  return HeapTypeGenerator(rand, features, n).generate();
+HeapTypeGenerator
+HeapTypeGenerator::create(Random& rand, FeatureSet features, size_t n) {
+  return HeapTypeGeneratorImpl(rand, features, n).result;
 }
 
-} // namespace HeapTypeFuzzer
-
 } // namespace wasm
diff --git a/src/tools/fuzzing/heap-types.h b/src/tools/fuzzing/heap-types.h
index a9a580cf6..c54e3053d 100644
--- a/src/tools/fuzzing/heap-types.h
+++ b/src/tools/fuzzing/heap-types.h
@@ -19,14 +19,27 @@
 
 #include "tools/fuzzing/random.h"
 #include "wasm-type.h"
+#include "wasm.h"
+#include <optional>
 #include <vector>
 
-namespace wasm::HeapTypeFuzzer {
+namespace wasm {
 
-// Generate a vector of `n` random HeapTypes with interesting subtyping.
-std::vector<HeapType>
-generateHeapTypes(Random& rand, FeatureSet features, size_t n);
+struct HeapTypeGenerator {
+  // The builder containing the randomly generated types.
+  TypeBuilder builder;
 
-} // namespace wasm::HeapTypeFuzzer
+  // The intended subtypes of each built type.
+  std::vector<std::vector<Index>> subtypeIndices;
+
+  // The intended supertype of each built type, if any.
+  std::vector<std::optional<Index>> supertypeIndices;
+
+  // Create a populated `HeapTypeGenerator` with `n` random HeapTypes with
+  // interesting subtyping.
+  static HeapTypeGenerator create(Random& rand, FeatureSet features, size_t n);
+};
+
+} // namespace wasm
 
 #endif // wasm_tools_fuzzing_heap_types_h
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index 564bfa212..bea43e500 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -49,14 +49,34 @@ struct Fuzzer {
     Random rand(std::move(bytes));
 
     // TODO: Options to control the size or set it randomly.
-    std::vector<HeapType> types =
-      HeapTypeFuzzer::generateHeapTypes(rand, FeatureSet::All, 20);
+    HeapTypeGenerator generator =
+      HeapTypeGenerator::create(rand, FeatureSet::All, 20);
+    std::vector<HeapType> types = generator.builder.build();
 
-    // TODO: Do some sort of checking or manipulation on the types
     if (verbose) {
-      std::cout << "Built " << types.size() << " types:\n";
-      for (size_t i = 0; i < types.size(); ++i) {
-        std::cout << i << ": " << types[i] << "\n";
+      printTypes(types);
+    }
+
+    checkSubtypes(types, generator.subtypeIndices);
+  }
+
+  void printTypes(const std::vector<HeapType>& types) {
+    std::cout << "Built " << types.size() << " types:\n";
+    for (size_t i = 0; i < types.size(); ++i) {
+      std::cout << i << ": " << types[i] << "\n";
+    }
+  }
+
+  void checkSubtypes(const std::vector<HeapType>& types,
+                     const std::vector<std::vector<Index>>& subtypeIndices) {
+    for (size_t super = 0; super < types.size(); ++super) {
+      for (auto sub : subtypeIndices[super]) {
+        if (!HeapType::isSubType(types[sub], types[super])) {
+          Fatal() << "HeapType " << sub << " should be a subtype of HeapType "
+                  << super << " but is not!\n"
+                  << sub << ": " << types[sub] << "\n"
+                  << super << ": " << types[super] << "\n";
+        }
       }
     }
   }
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 2362a95aa..fc2a3b290 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -559,9 +559,11 @@ struct TypeBuilder {
   ~TypeBuilder();
 
   TypeBuilder(TypeBuilder& other) = delete;
-  TypeBuilder(TypeBuilder&& other) = delete;
   TypeBuilder& operator=(TypeBuilder&) = delete;
 
+  TypeBuilder(TypeBuilder&& other);
+  TypeBuilder& operator=(TypeBuilder&& other);
+
   // Append `n` new uninitialized HeapType slots to the end of the TypeBuilder.
   void grow(size_t n);
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 443ab9da2..7dc336d87 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -2270,6 +2270,9 @@ TypeBuilder::TypeBuilder(size_t n) {
 
 TypeBuilder::~TypeBuilder() = default;
 
+TypeBuilder::TypeBuilder(TypeBuilder&& other) = default;
+TypeBuilder& TypeBuilder::operator=(TypeBuilder&& other) = default;
+
 void TypeBuilder::grow(size_t n) {
   assert(size() + n > size());
   impl->entries.resize(size() + n);