Make `TypeBuilder::build()` fallible (#4474)

It is possible for type building to fail, for example if the declared nominal
supertypes form a cycle or are structurally invalid. Previously we would report
a fatal error and kill the program from inside `TypeBuilder::build()` in these
situations, but this handles errors at the wrong layer of the code base and is
inconvenient for testing the error cases.

In preparation for testing the new error cases introduced by isorecursive
typing, make type building fallible and add new tests for existing error cases.
Also fix supertype cycle detection, which it turns out did not work correctly.

6 files changed, 85 insertions, 27 deletions

diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 3516a10a9..10b8f1bb8 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -74,7 +74,8 @@ void GlobalTypeRewriter::update() {
     }
   }
 
-  auto newTypes = typeBuilder.build();
+  auto buildResults = typeBuilder.build();
+  auto& newTypes = *buildResults;
 
   // Map the old types to the new ones. This uses the fact that type indices
   // are the same in the old and new types, that is, we have not added or
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index d0baec748..e736c8977 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -51,7 +51,12 @@ struct Fuzzer {
     // TODO: Options to control the size or set it randomly.
     HeapTypeGenerator generator =
       HeapTypeGenerator::create(rand, FeatureSet::All, 20);
-    std::vector<HeapType> types = generator.builder.build();
+    auto result = generator.builder.build();
+    if (auto* err = result.getError()) {
+      Fatal() << "Failed to build types: " << err->reason << " at index "
+              << err->index;
+    }
+    auto types = *result;
 
     if (verbose) {
       printTypes(types);
diff --git a/src/wasm-type.h b/src/wasm-type.h
index fa5650a31..4c050ed35 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -22,6 +22,7 @@
 #include "wasm-features.h"
 #include <optional>
 #include <ostream>
+#include <variant>
 #include <vector>
 
 // TODO: At various code locations we were assuming that single types are basic
@@ -588,12 +589,35 @@ struct TypeBuilder {
   // not overlap or go out of bounds.
   void createRecGroup(size_t i, size_t length);
 
+  enum class ErrorReason {
+    // There is a cycle in the supertype relation.
+    SelfSupertype,
+    // The declared supertype of a type is invalid.
+    InvalidSupertype,
+  };
+
+  struct Error {
+    // The index of the type causing the failure.
+    size_t index;
+    ErrorReason reason;
+  };
+
+  struct BuildResult : std::variant<std::vector<HeapType>, Error> {
+    operator bool() const {
+      return bool(std::get_if<std::vector<HeapType>>(this));
+    }
+    const std::vector<HeapType>& operator*() const {
+      return std::get<std::vector<HeapType>>(*this);
+    }
+    const Error* getError() const { return std::get_if<Error>(this); }
+  };
+
   // Returns all of the newly constructed heap types. May only be called once
   // all of the heap types have been initialized with `setHeapType`. In nominal
   // mode, all of the constructed HeapTypes will be fresh and distinct. In
   // nominal mode, will also produce a fatal error if the declared subtype
   // relationships are not valid.
-  std::vector<HeapType> build();
+  BuildResult build();
 
   // Utility for ergonomically using operator[] instead of explicit setHeapType
   // and getTempHeapType methods.
@@ -639,6 +663,7 @@ std::ostream& operator<<(std::ostream&, Field);
 std::ostream& operator<<(std::ostream&, Struct);
 std::ostream& operator<<(std::ostream&, Array);
 std::ostream& operator<<(std::ostream&, Rtt);
+std::ostream& operator<<(std::ostream&, TypeBuilder::ErrorReason);
 
 } // namespace wasm
 
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index b20269f9b..13bcc5110 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1989,7 +1989,11 @@ void WasmBinaryBuilder::readTypes() {
     }
   }
 
-  types = builder.build();
+  auto result = builder.build();
+  if (auto* err = result.getError()) {
+    Fatal() << "Invalid type: " << err->reason << " at index " << err->index;
+  }
+  types = *result;
 }
 
 Name WasmBinaryBuilder::getFunctionName(Index index) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 01e1789cd..0cb58746c 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -934,7 +934,11 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     ++index;
   });
 
-  types = builder.build();
+  auto result = builder.build();
+  if (auto* err = result.getError()) {
+    Fatal() << "Invalid type: " << err->reason << " at index " << err->index;
+  }
+  types = *result;
 
   for (auto& [name, index] : typeIndices) {
     auto type = types[index];
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 4c2922c73..b69977426 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1317,6 +1317,15 @@ std::ostream& operator<<(std::ostream& os, Array array) {
 std::ostream& operator<<(std::ostream& os, Rtt rtt) {
   return TypePrinter(os).print(rtt);
 }
+std::ostream& operator<<(std::ostream& os, TypeBuilder::ErrorReason reason) {
+  switch (reason) {
+    case TypeBuilder::ErrorReason::SelfSupertype:
+      return os << "Heap type is a supertype of itself";
+    case TypeBuilder::ErrorReason::InvalidSupertype:
+      return os << "Heap type has an invalid supertype";
+  }
+  WASM_UNREACHABLE("Unexpected error reason");
+}
 
 unsigned Field::getByteSize() const {
   if (type != Type::i32) {
@@ -1482,7 +1491,7 @@ Type TypeBounder::getLeastUpperBound(Type a, Type b) {
   // Array is arbitrary; it might as well have been a Struct.
   builder.grow(1);
   builder[builder.size() - 1] = Array(Field(*tempLUB, Mutable));
-  std::vector<HeapType> built = builder.build();
+  std::vector<HeapType> built = *builder.build();
   return built.back().getArray().element.type;
 }
 
@@ -1498,7 +1507,7 @@ HeapType TypeBounder::getLeastUpperBound(HeapType a, HeapType b) {
     ++index;
   }
   // Canonicalize and return the LUB.
-  return builder.build()[index];
+  return (*builder.build())[index];
 }
 
 std::optional<Type> TypeBounder::lub(Type a, Type b) {
@@ -1847,7 +1856,6 @@ std::ostream& TypePrinter::print(HeapType heapType) {
     }
 #if TRACE_CANONICALIZATION
     os << "[" << ((heapType.getID() >> 4) % 1000) << "]";
-    HeapType super;
     if (auto super = heapType.getSuperType()) {
       os << "[super " << ((super->getID() >> 4) % 1000) << "]";
     }
@@ -3104,7 +3112,8 @@ void canonicalizeEquirecursive(CanonicalizationState& state) {
 #endif
 }
 
-void canonicalizeNominal(CanonicalizationState& state) {
+std::optional<TypeBuilder::Error>
+canonicalizeNominal(CanonicalizationState& state) {
   // TODO: clear recursion groups once we are no longer piggybacking the
   // isorecursive system on the nominal system.
   // if (typeSystem != TypeSystem::Isorecursive) {
@@ -3123,24 +3132,27 @@ void canonicalizeNominal(CanonicalizationState& state) {
   // Ensure there are no cycles in the subtype graph. This is the classic DFA
   // algorithm for detecting cycles, but in the form of a simple loop because
   // each node (type) has at most one child (supertype).
-  std::unordered_set<HeapTypeInfo*> seen;
-  for (auto type : state.results) {
+  std::unordered_set<HeapTypeInfo*> checked;
+  for (size_t i = 0; i < state.results.size(); ++i) {
+    HeapType type = state.results[i];
     if (type.isBasic()) {
       continue;
     }
     std::unordered_set<HeapTypeInfo*> path;
     for (auto* curr = getHeapTypeInfo(type);
-         seen.insert(curr).second && curr->supertype != nullptr;
+         curr != nullptr && !checked.count(curr);
          curr = curr->supertype) {
       if (!path.insert(curr).second) {
-        Fatal() << HeapType(uintptr_t(curr))
-                << " cannot be a subtype of itself";
+        return TypeBuilder::Error{i, TypeBuilder::ErrorReason::SelfSupertype};
       }
     }
+    // None of the types in `path` reach themselves.
+    checked.insert(path.begin(), path.end());
   }
 
   // Ensure that all the subtype relations are valid.
-  for (HeapType type : state.results) {
+  for (size_t i = 0; i < state.results.size(); ++i) {
+    HeapType type = state.results[i];
     if (type.isBasic()) {
       continue;
     }
@@ -3151,12 +3163,11 @@ void canonicalizeNominal(CanonicalizationState& state) {
     }
 
     auto fail = [&]() {
-      Fatal() << type << " cannot be a subtype of "
-              << HeapType(uintptr_t(super));
+      return TypeBuilder::Error{i, TypeBuilder::ErrorReason::InvalidSupertype};
     };
 
     if (sub->kind != super->kind) {
-      fail();
+      return fail();
     }
     SubTyper typer;
     switch (sub->kind) {
@@ -3164,17 +3175,17 @@ void canonicalizeNominal(CanonicalizationState& state) {
         WASM_UNREACHABLE("unexpected kind");
       case HeapTypeInfo::SignatureKind:
         if (!typer.isSubType(sub->signature, super->signature)) {
-          fail();
+          return fail();
         }
         break;
       case HeapTypeInfo::StructKind:
         if (!typer.isSubType(sub->struct_, super->struct_)) {
-          fail();
+          return fail();
         }
         break;
       case HeapTypeInfo::ArrayKind:
         if (!typer.isSubType(sub->array, super->array)) {
-          fail();
+          return fail();
         }
         break;
     }
@@ -3188,9 +3199,10 @@ void canonicalizeNominal(CanonicalizationState& state) {
                  .count()
             << " ms\n";
 #endif
+  return {};
 }
 
-void canonicalizeIsorecursive(
+std::optional<TypeBuilder::Error> canonicalizeIsorecursive(
   CanonicalizationState& state,
   std::vector<std::unique_ptr<RecGroupInfo>>& recGroupInfos) {
   // Fill out the recursion groups.
@@ -3202,7 +3214,9 @@ void canonicalizeIsorecursive(
 
   // TODO: proper isorecursive validation and canonicalization. For now just
   // piggyback on the nominal system.
-  canonicalizeNominal(state);
+  if (auto err = canonicalizeNominal(state)) {
+    return err;
+  }
 
   // Move the recursion groups into the global store. TODO: after proper
   // isorecursive canonicalization, some groups may no longer be used, so they
@@ -3211,6 +3225,7 @@ void canonicalizeIsorecursive(
   for (auto& info : recGroupInfos) {
     recGroups.emplace_back(std::move(info));
   }
+  return {};
 }
 
 void canonicalizeBasicHeapTypes(CanonicalizationState& state) {
@@ -3233,7 +3248,7 @@ void canonicalizeBasicHeapTypes(CanonicalizationState& state) {
 
 } // anonymous namespace
 
-std::vector<HeapType> TypeBuilder::build() {
+TypeBuilder::BuildResult TypeBuilder::build() {
   size_t entryCount = impl->entries.size();
 
   // Initialize the canonicalization state using the HeapTypeInfos from the
@@ -3269,10 +3284,14 @@ std::vector<HeapType> TypeBuilder::build() {
       canonicalizeEquirecursive(state);
       break;
     case TypeSystem::Nominal:
-      canonicalizeNominal(state);
+      if (auto error = canonicalizeNominal(state)) {
+        return {*error};
+      }
       break;
     case TypeSystem::Isorecursive:
-      canonicalizeIsorecursive(state, impl->recGroups);
+      if (auto error = canonicalizeIsorecursive(state, impl->recGroups)) {
+        return {*error};
+      }
       break;
   }
 
@@ -3298,7 +3317,7 @@ std::vector<HeapType> TypeBuilder::build() {
     }
   }
 
-  return state.results;
+  return {state.results};
 }
 
 } // namespace wasm