11 files changed, 875 insertions, 120 deletions

diff --git a/src/tools/CMakeLists.txt b/src/tools/CMakeLists.txt
index cda38a369..ac8927d54 100644
--- a/src/tools/CMakeLists.txt
+++ b/src/tools/CMakeLists.txt
@@ -12,6 +12,7 @@ include_directories(fuzzing)
 FILE(GLOB fuzzing_HEADERS fuzzing/*h)
 set(fuzzing_SOURCES
   fuzzing/fuzzing.cpp
+  fuzzing/heap-types.cpp
   fuzzing/random.cpp
   ${fuzzing_HEADERS}
 )
@@ -25,5 +26,6 @@ binaryen_add_executable(wasm-as wasm-as.cpp)
 binaryen_add_executable(wasm-dis wasm-dis.cpp)
 binaryen_add_executable(wasm-ctor-eval wasm-ctor-eval.cpp)
 binaryen_add_executable(wasm-reduce wasm-reduce.cpp)
+binaryen_add_executable(wasm-fuzz-types "${fuzzing_SOURCES};wasm-fuzz-types.cpp")
 
 add_subdirectory(wasm-split)
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index bc3516d4c..a9cc9eec0 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -142,6 +142,19 @@ private:
   bool oneIn(Index x) { return random.oneIn(x); }
   Index upToSquared(Index x) { return random.upToSquared(x); }
 
+  // Pick from a vector-like container or a fixed list.
+  template<typename T> const typename T::value_type& pick(const T& vec) {
+    return random.pick(vec);
+  }
+  template<typename T, typename... Args> T pick(T first, Args... args) {
+    return random.pick(first, args...);
+  }
+  // Pick from options associated with features.
+  template<typename T> using FeatureOptions = Random::FeatureOptions<T>;
+  template<typename T> const T pick(FeatureOptions<T>& picker) {
+    return random.pick(picker);
+  }
+
   // Setup methods
   void setupMemory();
   void setupHeapTypes();
@@ -296,87 +309,6 @@ private:
   Index logify(Index x) {
     return std::floor(std::log(std::max(Index(1) + x, Index(1))));
   }
-
-  // Pick from a vector-like container
-  template<typename T> const typename T::value_type& pick(const T& vec) {
-    assert(!vec.empty());
-    auto index = upTo(vec.size());
-    return vec[index];
-  }
-
-  // pick from a fixed list
-  template<typename T, typename... Args> T pick(T first, Args... args) {
-    auto num = sizeof...(Args) + 1;
-    auto temp = upTo(num);
-    return pickGivenNum<T>(temp, first, args...);
-  }
-
-  template<typename T> T pickGivenNum(size_t num, T first) {
-    assert(num == 0);
-    return first;
-  }
-
-// Trick to avoid a bug in GCC 7.x.
-// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
-#define GCC_VERSION                                                            \
-  (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
-#if GCC_VERSION > 70000 && GCC_VERSION < 70300
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
-#endif
-
-  template<typename T, typename... Args>
-  T pickGivenNum(size_t num, T first, Args... args) {
-    if (num == 0) {
-      return first;
-    }
-    return pickGivenNum<T>(num - 1, args...);
-  }
-
-#if GCC_VERSION > 70000 && GCC_VERSION < 70300
-#pragma GCC diagnostic pop
-#endif
-
-  template<typename T> struct FeatureOptions {
-    template<typename... Ts>
-    FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
-      options[feature].push_back(option);
-      return add(feature, rest...);
-    }
-
-    struct WeightedOption {
-      T option;
-      size_t weight;
-    };
-
-    template<typename... Ts>
-    FeatureOptions<T>&
-    add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
-      for (size_t i = 0; i < weightedOption.weight; i++) {
-        options[feature].push_back(weightedOption.option);
-      }
-      return add(feature, rest...);
-    }
-
-    FeatureOptions<T>& add(FeatureSet feature) { return *this; }
-
-    std::map<FeatureSet, std::vector<T>> options;
-  };
-
-  template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
-    std::vector<T> matches;
-    for (const auto& item : picker.options) {
-      if (wasm.features.has(item.first)) {
-        matches.reserve(matches.size() + item.second.size());
-        matches.insert(matches.end(), item.second.begin(), item.second.end());
-      }
-    }
-    return matches;
-  }
-
-  template<typename T> const T pick(FeatureOptions<T>& picker) {
-    return pick(items(picker));
-  }
 };
 
 } // namespace wasm
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 1f745f1ee..84b0e2c5c 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -1,53 +1,35 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 #include "tools/fuzzing.h"
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
 
 namespace wasm {
 
-// Constants that control fuzzing.
 namespace {
-// The maximum amount of params to each function.
-constexpr int MAX_PARAMS = 10;
-
-// The maximum amount of vars in each function.
-constexpr int MAX_VARS = 20;
-
-// The maximum number of globals in a module.
-constexpr int MAX_GLOBALS = 20;
-
-// The maximum number of tuple elements.
-constexpr int MAX_TUPLE_SIZE = 6;
-
-// The maximum rtt depth.
-constexpr int MAX_RTT_DEPTH = 3;
-
-// some things require luck, try them a few times
-constexpr int TRIES = 10;
-
-// beyond a nesting limit, greatly decrease the chance to continue to nest
-constexpr int NESTING_LIMIT = 11;
-
-// the maximum size of a block
-constexpr int BLOCK_FACTOR = 5;
-
-// the memory that we use, a small portion so that we have a good chance of
-// looking at writes (we also look outside of this region with small
-// probability) this should be a power of 2
-constexpr Address USABLE_MEMORY = 16;
-
-// the number of runtime iterations (function calls, loop backbranches) we
-// allow before we stop execution with a trap, to prevent hangs. 0 means
-// no hang protection.
-constexpr int HANG_LIMIT = 10;
 
 // Weighting for the core make* methods. Some nodes are important enough that
 // we should do them quite often.
-constexpr size_t VeryImportant = 4;
-constexpr size_t Important = 2;
 
 } // anonymous namespace
 
 TranslateToFuzzReader::TranslateToFuzzReader(Module& wasm,
                                              std::vector<char>&& input)
-  : wasm(wasm), builder(wasm), random(std::move(input)) {
+  : wasm(wasm), builder(wasm), random(std::move(input), wasm.features) {
   // - funcref cannot be logged because referenced functions can be inlined or
   // removed during optimization
   // - there's no point in logging externref or anyref because these are opaque
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
new file mode 100644
index 000000000..71f701860
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -0,0 +1,499 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <variant>
+
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/parameters.h"
+
+namespace wasm {
+
+namespace {
+
+struct HeapTypeGenerator {
+  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>;
+
+  // Top-level kinds, chosen before the types are actually constructed. This
+  // allows us to choose HeapTypes that we know will be subtypes of data or func
+  // before we actually generate the types.
+  using BasicKind = HeapType::BasicHeapType;
+  struct SignatureKind {};
+  struct DataKind {};
+  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) {}
+
+  HeapType::BasicHeapType generateBasicHeapType() {
+    return rand.pick(HeapType::func,
+                     HeapType::ext,
+                     HeapType::any,
+                     HeapType::eq,
+                     HeapType::i31,
+                     HeapType::data);
+  }
+
+  Type::BasicType generateBasicType() {
+    return rand.pick(
+      Random::FeatureOptions<Type::BasicType>{}
+        .add(FeatureSet::MVP, Type::i32, Type::i64, Type::f32, Type::f64)
+        .add(FeatureSet::SIMD, Type::v128)
+        .add(FeatureSet::ReferenceTypes | FeatureSet::GC,
+             Type::funcref,
+             Type::externref,
+             Type::anyref,
+             Type::eqref,
+             Type::i31ref,
+             Type::dataref));
+  }
+
+  HeapType generateHeapType() {
+    if (rand.oneIn(4)) {
+      return generateBasicHeapType();
+    } else {
+      return builder[rand.upTo(builder.size())];
+    }
+  }
+
+  // TODO: Create an enum for `Defaultable, NonDefaultable` in wasm-type.h.
+  Type generateRefType(bool defaultable = false) {
+    auto heapType = generateHeapType();
+    auto nullability = (defaultable || rand.oneIn(2)) ? Nullable : NonNullable;
+    return builder.getTempRefType(heapType, nullability);
+  }
+
+  Type generateRttType() {
+    auto heapType = generateHeapType();
+    auto depth = rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+    return builder.getTempRttType(Rtt(depth, heapType));
+  }
+
+  Type generateSingleType(bool defaultable = false) {
+    switch (rand.upTo(defaultable ? 2 : 3)) {
+      case 0:
+        return generateBasicType();
+      case 1:
+        return generateRefType(defaultable);
+      case 2:
+        return generateRttType();
+    }
+    WASM_UNREACHABLE("unexpected");
+  }
+
+  Type generateTupleType() {
+    std::vector<Type> types(2 + rand.upTo(MAX_TUPLE_SIZE - 1));
+    for (auto& type : types) {
+      // Make sure tuples are defaultable. See comment in
+      // TranslateToFuzzReader::getTupleType.
+      type = generateSingleType(/*defaultable=*/true);
+    }
+    return builder.getTempTupleType(Tuple(types));
+  }
+
+  Type generateReturnType() {
+    // This is similar to TranslateToFuzzreader::getControlFlowType.
+    if (rand.oneIn(10)) {
+      return Type::none;
+    } else if (features.hasMultivalue() && rand.oneIn(5)) {
+      return generateTupleType();
+    } else {
+      return generateSingleType(/*defaultable=*/true);
+    }
+  }
+
+  Signature generateSignature() {
+    std::vector<Type> types(rand.upToSquared(MAX_PARAMS));
+    for (auto& type : types) {
+      type = generateSingleType();
+    }
+    auto params = builder.getTempTupleType(types);
+    return {params, generateReturnType()};
+  }
+
+  Field generateField() {
+    auto mutability = rand.oneIn(2) ? Mutable : Immutable;
+    if (rand.oneIn(6)) {
+      return {rand.oneIn(2) ? Field::i8 : Field::i16, mutability};
+    } else {
+      return {generateSingleType(), mutability};
+    }
+  }
+
+  Struct generateStruct() {
+    std::vector<Field> fields(rand.upTo(MAX_STRUCT_SIZE + 1));
+    for (auto& field : fields) {
+      field = generateField();
+    }
+    return {fields};
+  }
+
+  Array generateArray() { return {generateField()}; }
+
+  Assignable generateSubData() {
+    switch (rand.upTo(2)) {
+      case 0:
+        return generateStruct();
+      case 1:
+        return generateArray();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubEq() {
+    switch (rand.upTo(3)) {
+      case 0:
+        return HeapType::i31;
+      case 1:
+        return HeapType::data;
+      case 2:
+        return generateSubData();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubAny() {
+    switch (rand.upTo(4)) {
+      case 0:
+        return HeapType::eq;
+      case 1:
+        return HeapType::func;
+      case 2:
+        return generateSubEq();
+      case 3:
+        return generateSignature();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  Assignable generateSubBasic(HeapType::BasicHeapType type) {
+    if (rand.oneIn(2)) {
+      return type;
+    } else {
+      switch (type) {
+        case HeapType::ext:
+        case HeapType::i31:
+          // No other subtypes.
+          return type;
+        case HeapType::func:
+          return generateSignature();
+        case HeapType::any:
+          return generateSubAny();
+        case HeapType::eq:
+          return generateSubEq();
+        case HeapType::data:
+          return generateSubData();
+      }
+      WASM_UNREACHABLE("unexpected index");
+    }
+  }
+
+  template<typename Kind> std::optional<HeapType> pickKind() {
+    std::vector<HeapType> candidates;
+    // Iterate through the top level kinds, finding matches for `Kind`.
+    for (Index i = 0; i < typeKinds.size(); ++i) {
+      if (std::get_if<Kind>(&typeKinds[i])) {
+        candidates.push_back(builder[i]);
+      }
+    }
+    if (candidates.size()) {
+      return rand.pick(candidates);
+    } else {
+      return {};
+    }
+  }
+
+  HeapType pickSubFunc() {
+    if (auto type = pickKind<SignatureKind>()) {
+      return *type;
+    } else {
+      return HeapType::func;
+    }
+  }
+
+  HeapType pickSubData() {
+    if (auto type = pickKind<DataKind>()) {
+      return *type;
+    } else {
+      return HeapType::data;
+    }
+  }
+
+  HeapType pickSubEq() {
+    if (rand.oneIn(2)) {
+      return HeapType::i31;
+    } else {
+      return pickSubData();
+    }
+  }
+
+  HeapType pickSubAny() {
+    switch (rand.upTo(4)) {
+      case 0:
+        return HeapType::func;
+      case 1:
+        return HeapType::eq;
+      case 2:
+        return pickSubFunc();
+      case 3:
+        return pickSubEq();
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  HeapType pickSubHeapType(HeapType type) {
+    auto it = typeIndices.find(type);
+    if (it != typeIndices.end()) {
+      // This is a constructed type, so we know where its subtypes are.
+      return builder[rand.pick(subtypeIndices[typeIndices[type]])];
+    } else {
+      // This is not a constructed type, so it must be a basic type.
+      assert(type.isBasic());
+      switch (type.getBasic()) {
+        case HeapType::func:
+          return pickSubFunc();
+        case HeapType::ext:
+          return HeapType::ext;
+        case HeapType::any:
+          return pickSubAny();
+        case HeapType::eq:
+          return pickSubEq();
+        case HeapType::i31:
+          return HeapType::i31;
+        case HeapType::data:
+          return pickSubData();
+      }
+      WASM_UNREACHABLE("unexpected kind");
+    }
+  }
+
+  // TODO: Make this part of the wasm-type.h API
+  struct Ref {
+    HeapType type;
+    Nullability nullability;
+  };
+
+  Ref generateSubRef(Ref super) {
+    auto nullability = super.nullability == NonNullable
+                         ? NonNullable
+                         : rand.oneIn(2) ? Nullable : NonNullable;
+    return {pickSubHeapType(super.type), nullability};
+  }
+
+  Rtt generateSubRtt(Rtt super) {
+    auto depth = super.hasDepth()
+                   ? super.depth
+                   : rand.oneIn(2) ? Rtt::NoDepth : rand.upTo(MAX_RTT_DEPTH);
+    return {depth, super.heapType};
+  }
+
+  Type generateSubtype(Type type) {
+    if (type.isBasic()) {
+      // We do not construct types with basic reference types (we go through the
+      // TypeBuilder for those instead), so this must be a non-reference basic
+      // type, which means it has no other subtypes.
+      return type;
+    } else if (type.isRef()) {
+      auto ref = generateSubRef({type.getHeapType(), type.getNullability()});
+      return builder.getTempRefType(ref.type, ref.nullability);
+    } else if (type.isRtt()) {
+      auto rtt = generateSubRtt(type.getRtt());
+      return builder.getTempRttType(rtt);
+    } else {
+      WASM_UNREACHABLE("unexpected type kind");
+    }
+  }
+
+  Signature generateSubSignature(Signature super) {
+    // TODO: Update this once we support nontrivial function subtyping.
+    return super;
+  }
+
+  Field generateSubField(Field super) {
+    if (super.mutable_ == Mutable) {
+      // Only immutable fields support subtyping.
+      return super;
+    }
+    if (super.isPacked()) {
+      // No other subtypes of i8 or i16.
+      return super;
+    }
+    return {generateSubtype(super.type), Immutable};
+  }
+
+  Struct generateSubStruct(const Struct& super) {
+    if (rand.oneIn(2)) {
+      return super;
+    }
+    std::vector<Field> fields;
+    // Depth subtyping
+    for (auto field : super.fields) {
+      fields.push_back(generateSubField(field));
+    }
+    // Width subtyping
+    Index extra = rand.upTo(MAX_STRUCT_SIZE + 1 - fields.size());
+    for (Index i = 0; i < extra; ++i) {
+      fields.push_back(generateField());
+    }
+    return {fields};
+  }
+
+  Array generateSubArray(Array super) {
+    if (rand.oneIn(2)) {
+      return super;
+    }
+    return {generateSubField(super.element)};
+  }
+
+  HeapTypeKind generateHeapTypeKind() {
+    // Building basic heap types is only allowed in equirecursive mode.
+    // TODO: Relax this.
+    size_t options = 2;
+    if (getTypeSystem() == TypeSystem::Equirecursive) {
+      ++options;
+    }
+    switch (rand.upTo(options)) {
+      case 0:
+        return SignatureKind{};
+      case 1:
+        return DataKind{};
+      case 2:
+        return BasicKind{generateBasicHeapType()};
+    }
+    WASM_UNREACHABLE("unexpected index");
+  }
+
+  HeapTypeKind getSubKind(HeapTypeKind super) {
+    if (auto* basic = std::get_if<BasicKind>(&super)) {
+      if (rand.oneIn(8)) {
+        return super;
+      }
+      switch (*basic) {
+        case HeapType::func:
+          return SignatureKind{};
+        case HeapType::ext:
+        case HeapType::i31:
+          return super;
+        case HeapType::any:
+          return generateHeapTypeKind();
+        case HeapType::eq:
+          if (rand.oneIn(4)) {
+            return HeapType::i31;
+          } else {
+            return DataKind{};
+          }
+        case HeapType::data:
+          return DataKind{};
+      }
+      WASM_UNREACHABLE("unexpected kind");
+    } else {
+      // Signature and Data types can only have Signature and Data subtypes.
+      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) {
+      if (!supertypeIndices[i]) {
+        // Create a root type.
+        auto kind = typeKinds[i];
+        if (auto* basic = std::get_if<BasicKind>(&kind)) {
+          builder[i] = *basic;
+        } else 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.
+        Index super = *supertypeIndices[i];
+        HeapType supertype = builder[super];
+        if (builder.isBasic(super)) {
+          auto assignable = generateSubBasic(builder.getBasic(super));
+          std::visit([&](auto&& arg) { builder[i] = arg; }, assignable);
+        } else 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();
+}
+
+} // namespace HeapTypeFuzzer
+
+} // namespace wasm
diff --git a/src/tools/fuzzing/heap-types.h b/src/tools/fuzzing/heap-types.h
new file mode 100644
index 000000000..a9a580cf6
--- /dev/null
+++ b/src/tools/fuzzing/heap-types.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_tools_fuzzing_heap_types_h
+#define wasm_tools_fuzzing_heap_types_h
+
+#include "tools/fuzzing/random.h"
+#include "wasm-type.h"
+#include <vector>
+
+namespace wasm::HeapTypeFuzzer {
+
+// Generate a vector of `n` random HeapTypes with interesting subtyping.
+std::vector<HeapType>
+generateHeapTypes(Random& rand, FeatureSet features, size_t n);
+
+} // namespace wasm::HeapTypeFuzzer
+
+#endif // wasm_tools_fuzzing_heap_types_h
diff --git a/src/tools/fuzzing/parameters.h b/src/tools/fuzzing/parameters.h
new file mode 100644
index 000000000..6618ce6db
--- /dev/null
+++ b/src/tools/fuzzing/parameters.h
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Constants that control fuzzing.
+
+#ifndef wasm_tools_fuzzing_parameters_h
+#define wasm_tools_fuzzing_parameters_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+// The maximum amount of params to each function.
+constexpr int MAX_PARAMS = 10;
+
+// The maximum amount of vars in each function.
+constexpr int MAX_VARS = 20;
+
+// The maximum number of globals in a module.
+constexpr int MAX_GLOBALS = 20;
+
+// The maximum number of tuple elements.
+constexpr int MAX_TUPLE_SIZE = 6;
+
+// The maximum number of struct fields.
+static const int MAX_STRUCT_SIZE = 6;
+
+// The maximum rtt depth.
+constexpr int MAX_RTT_DEPTH = 3;
+
+// The number of nontrivial heap types to generate.
+constexpr int MIN_HEAPTYPES = 4;
+constexpr int MAX_HEAPTYPES = 20;
+
+// some things require luck, try them a few times
+constexpr int TRIES = 10;
+
+// beyond a nesting limit, greatly decrease the chance to continue to nest
+constexpr int NESTING_LIMIT = 11;
+
+// the maximum size of a block
+constexpr int BLOCK_FACTOR = 5;
+
+// the memory that we use, a small portion so that we have a good chance of
+// looking at writes (we also look outside of this region with small
+// probability) this should be a power of 2
+constexpr Address USABLE_MEMORY = 16;
+
+// the number of runtime iterations (function calls, loop backbranches) we
+// allow before we stop execution with a trap, to prevent hangs. 0 means
+// no hang protection.
+constexpr int HANG_LIMIT = 10;
+
+//
+constexpr size_t VeryImportant = 4;
+constexpr size_t Important = 2;
+
+} // namespace wasm
+
+#endif // wasm_tools_fuzzing_parameters_h
diff --git a/src/tools/fuzzing/random.cpp b/src/tools/fuzzing/random.cpp
index 38a86924e..3d8297c15 100644
--- a/src/tools/fuzzing/random.cpp
+++ b/src/tools/fuzzing/random.cpp
@@ -20,7 +20,8 @@
 
 namespace wasm {
 
-Random::Random(std::vector<char>&& bytes) : bytes(std::move(bytes)) {
+Random::Random(std::vector<char>&& bytes, FeatureSet features)
+  : bytes(std::move(bytes)), features(features) {
   // Ensure there is *some* input to be read.
   if (bytes.empty()) {
     bytes.push_back(0);
diff --git a/src/tools/fuzzing/random.h b/src/tools/fuzzing/random.h
index 156f248ca..845aa2fa5 100644
--- a/src/tools/fuzzing/random.h
+++ b/src/tools/fuzzing/random.h
@@ -18,8 +18,11 @@
 #define wasm_tools_fuzzing_random_h
 
 #include <cstdint>
+#include <map>
 #include <vector>
 
+#include "wasm-features.h"
+
 namespace wasm {
 
 class Random {
@@ -33,9 +36,13 @@ class Random {
   // After we finish the input, we start going through it again, but xoring
   // so it's not identical.
   int xorFactor = 0;
+  // Features used for picking among FeatureOptions.
+  FeatureSet features;
 
 public:
-  Random(std::vector<char>&& bytes);
+  Random(std::vector<char>&& bytes, FeatureSet features);
+  Random(std::vector<char>&& bytes)
+    : Random(std::move(bytes), FeatureSet::All) {}
 
   // Methods for getting random data.
   int8_t get();
@@ -55,6 +62,87 @@ public:
   uint32_t upToSquared(uint32_t x) { return upTo(upTo(x)); }
 
   bool finished() { return finishedInput; }
+
+  // Pick from a vector-like container
+  template<typename T> const typename T::value_type& pick(const T& vec) {
+    assert(!vec.empty());
+    auto index = upTo(vec.size());
+    return vec[index];
+  }
+
+  // Pick from a fixed list
+  template<typename T, typename... Args> T pick(T first, Args... args) {
+    auto num = sizeof...(Args) + 1;
+    auto temp = upTo(num);
+    return pickGivenNum<T>(temp, first, args...);
+  }
+
+  template<typename T> T pickGivenNum(size_t num, T first) {
+    assert(num == 0);
+    return first;
+  }
+
+// Trick to avoid a bug in GCC 7.x.
+// Upstream bug report: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82800
+#define GCC_VERSION                                                            \
+  (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__)
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#endif
+
+  template<typename T, typename... Args>
+  T pickGivenNum(size_t num, T first, Args... args) {
+    if (num == 0) {
+      return first;
+    }
+    return pickGivenNum<T>(num - 1, args...);
+  }
+
+#if GCC_VERSION > 70000 && GCC_VERSION < 70300
+#pragma GCC diagnostic pop
+#endif
+
+  template<typename T> struct FeatureOptions {
+    template<typename... Ts>
+    FeatureOptions<T>& add(FeatureSet feature, T option, Ts... rest) {
+      options[feature].push_back(option);
+      return add(feature, rest...);
+    }
+
+    struct WeightedOption {
+      T option;
+      size_t weight;
+    };
+
+    template<typename... Ts>
+    FeatureOptions<T>&
+    add(FeatureSet feature, WeightedOption weightedOption, Ts... rest) {
+      for (size_t i = 0; i < weightedOption.weight; i++) {
+        options[feature].push_back(weightedOption.option);
+      }
+      return add(feature, rest...);
+    }
+
+    FeatureOptions<T>& add(FeatureSet feature) { return *this; }
+
+    std::map<FeatureSet, std::vector<T>> options;
+  };
+
+  template<typename T> std::vector<T> items(FeatureOptions<T>& picker) {
+    std::vector<T> matches;
+    for (const auto& item : picker.options) {
+      if (features.has(item.first)) {
+        matches.reserve(matches.size() + item.second.size());
+        matches.insert(matches.end(), item.second.begin(), item.second.end());
+      }
+    }
+    return matches;
+  }
+
+  template<typename T> const T pick(FeatureOptions<T>& picker) {
+    return pick(items(picker));
+  }
 };
 
 } // namespace wasm
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
new file mode 100644
index 000000000..5df0c50ba
--- /dev/null
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <optional>
+#include <random>
+#include <string>
+
+#include "support/command-line.h"
+#include "tools/fuzzing/heap-types.h"
+#include "tools/fuzzing/random.h"
+
+namespace wasm {
+
+using RandEngine = std::mt19937_64;
+
+uint64_t getSeed() {
+  // Return a (truly) random 64-bit value.
+  std::random_device rand;
+  return std::uniform_int_distribution<uint64_t>{}(rand);
+}
+
+struct Fuzzer {
+  bool verbose;
+
+  void run(uint64_t seed) {
+    // TODO: Reset the global type state to avoid monotonically increasing
+    // memory use.
+    RandEngine getRand(seed);
+    std::cout << "Running with seed " << seed << "\n";
+
+    // 4kb of random bytes should be enough for anyone!
+    std::vector<char> bytes(4096);
+    for (size_t i = 0; i < bytes.size(); i += sizeof(uint64_t)) {
+      *(uint64_t*)(bytes.data() + i) = getRand();
+    }
+    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);
+
+    // TODO: Do some sort of checking or manipulation on the types
+    if (verbose) {
+      std::cerr << "Built " << types.size() << " types:\n";
+      for (size_t i = 0; i < types.size(); ++i) {
+        std::cerr << i << ": " << types[i] << "\n";
+      }
+    }
+  }
+};
+
+} // namespace wasm
+
+int main(int argc, const char* argv[]) {
+  using namespace wasm;
+
+  Options options("wasm-fuzz-types",
+                  "Fuzz type construction, canonicalization, and operations");
+
+  std::optional<uint64_t> seed;
+  options.add("--seed",
+              "",
+              "Run a single workload generated by the given seed",
+              Options::Arguments::One,
+              [&](Options*, const std::string& arg) {
+                seed = uint64_t(std::stoull(arg));
+              });
+
+  bool verbose = false;
+  options.add("--verbose",
+              "-v",
+              "Print extra information",
+              Options::Arguments::Zero,
+              [&](Options*, const std::string& arg) { verbose = true; });
+
+  TypeSystem system = TypeSystem::Nominal;
+  options.add(
+    "--nominal",
+    "",
+    "Use the nominal type system (default)",
+    Options::Arguments::Zero,
+    [&](Options*, const std::string& arg) { system = TypeSystem::Nominal; });
+  options.add("--structural",
+              "",
+              "Use the equirecursive type system",
+              Options::Arguments::Zero,
+              [&](Options*, const std::string& arg) {
+                system = TypeSystem::Equirecursive;
+              });
+
+  options.parse(argc, argv);
+
+  setTypeSystem(system);
+
+  Fuzzer fuzzer{verbose};
+  if (seed) {
+    // Run just a single workload with the given seed.
+    fuzzer.run(*seed);
+  } else {
+    // Continuously run workloads with new randomly generated seeds.
+    size_t i = 0;
+    RandEngine nextSeed(getSeed());
+    while (true) {
+      std::cout << "Iteration " << ++i << "\n";
+      fuzzer.run(nextSeed());
+    }
+  }
+  return 0;
+}
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 1f6c5a7de..2362a95aa 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -576,6 +576,13 @@ struct TypeBuilder {
   void setHeapType(size_t i, Struct&& struct_);
   void setHeapType(size_t i, Array array);
 
+  // This is an ugly hack around the fact that temp heap types initialized with
+  // BasicHeapTypes are not themselves considered basic, so `HeapType::isBasic`
+  // and `HeapType::getBasic` do not work as expected with them. Call these
+  // methods instead.
+  bool isBasic(size_t i);
+  HeapType::BasicHeapType getBasic(size_t i);
+
   // Gets the temporary HeapType at index `i`. This HeapType should only be used
   // to construct temporary Types using the methods below.
   HeapType getTempHeapType(size_t i);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 002b401b5..1df14848c 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -2313,6 +2313,16 @@ void TypeBuilder::setHeapType(size_t i, Array array) {
   impl->entries[i].set(array);
 }
 
+bool TypeBuilder::isBasic(size_t i) {
+  assert(i < size() && "index out of bounds");
+  return impl->entries[i].info->kind == HeapTypeInfo::BasicKind;
+}
+
+HeapType::BasicHeapType TypeBuilder::getBasic(size_t i) {
+  assert(isBasic(i));
+  return impl->entries[i].info->basic;
+}
+
 HeapType TypeBuilder::getTempHeapType(size_t i) {
   assert(i < size() && "index out of bounds");
   return impl->entries[i].get();
@@ -3136,6 +3146,13 @@ std::vector<HeapType> buildNominal(TypeBuilder& builder) {
   auto afterMove = std::chrono::steady_clock::now();
 #endif
 
+#if TRACE_CANONICALIZATION
+  std::cerr << "After building:\n";
+  for (size_t i = 0; i < heapTypes.size(); ++i) {
+    std::cerr << i << ": " << heapTypes[i] << "\n";
+  }
+#endif // TRACE_CANONICALIZATION
+
   validateNominalSubTyping(heapTypes);
 
 #if TIME_CANONICALIZATION