Remove the nominal type system (#5672)

And since the only type system left is the standard isorecursive type system,
remove `TypeSystem` and its associated APIs entirely. Delete a few tests that
only made sense under the isorecursive type system.

9 files changed, 65 insertions, 290 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 01f14f924..b23d53ad6 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -406,21 +406,6 @@ BinaryenType BinaryenTypeFromHeapType(BinaryenHeapType heapType,
     .getID();
 }
 
-// TypeSystem
-
-BinaryenTypeSystem BinaryenTypeSystemNominal() {
-  return static_cast<BinaryenTypeSystem>(TypeSystem::Nominal);
-}
-BinaryenTypeSystem BinaryenTypeSystemIsorecursive() {
-  return static_cast<BinaryenTypeSystem>(TypeSystem::Isorecursive);
-}
-BinaryenTypeSystem BinaryenGetTypeSystem() {
-  return BinaryenTypeSystem(getTypeSystem());
-}
-void BinaryenSetTypeSystem(BinaryenTypeSystem typeSystem) {
-  setTypeSystem(TypeSystem(typeSystem));
-}
-
 // Expression ids
 
 BinaryenExpressionId BinaryenInvalidId(void) {
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index afbc13782..d05bdf33b 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -188,15 +188,6 @@ BINARYEN_API bool BinaryenTypeIsNullable(BinaryenType type);
 BINARYEN_API BinaryenType BinaryenTypeFromHeapType(BinaryenHeapType heapType,
                                                    bool nullable);
 
-// TypeSystem
-
-typedef uint32_t BinaryenTypeSystem;
-
-BINARYEN_API BinaryenTypeSystem BinaryenTypeSystemNominal(void);
-BINARYEN_API BinaryenTypeSystem BinaryenTypeSystemIsorecursive(void);
-BINARYEN_API BinaryenTypeSystem BinaryenGetTypeSystem(void);
-BINARYEN_API void BinaryenSetTypeSystem(BinaryenTypeSystem typeSystem);
-
 // Expression ids (call to get the value of each; you can cache them)
 
 typedef uint32_t BinaryenExpressionId;
diff --git a/src/ir/module-utils.cpp b/src/ir/module-utils.cpp
index efab9e20b..ce6fadda7 100644
--- a/src/ir/module-utils.cpp
+++ b/src/ir/module-utils.cpp
@@ -345,7 +345,6 @@ std::vector<HeapType> getPrivateHeapTypes(Module& wasm) {
 }
 
 IndexedHeapTypes getOptimizedIndexedHeapTypes(Module& wasm) {
-  TypeSystem system = getTypeSystem();
   Counts counts = getHeapTypeCounts(wasm);
 
   // Types have to be arranged into topologically ordered recursion groups.
@@ -385,32 +384,21 @@ IndexedHeapTypes getOptimizedIndexedHeapTypes(Module& wasm) {
     // Update the reference count.
     info.useCount += counts.at(type);
     // Collect predecessor groups.
-    switch (system) {
-      case TypeSystem::Isorecursive:
-        for (auto child : type.getReferencedHeapTypes()) {
-          if (!child.isBasic()) {
-            RecGroup otherGroup = child.getRecGroup();
-            if (otherGroup != group) {
-              info.preds.insert(otherGroup);
-            }
-          }
-        }
-        break;
-      case TypeSystem::Nominal:
-        if (auto super = type.getSuperType()) {
-          info.preds.insert(super->getRecGroup());
+    for (auto child : type.getReferencedHeapTypes()) {
+      if (!child.isBasic()) {
+        RecGroup otherGroup = child.getRecGroup();
+        if (otherGroup != group) {
+          info.preds.insert(otherGroup);
         }
-        break;
+      }
     }
   }
 
   // Fix up the use counts to be averages to ensure groups are used comensurate
   // with the amount of index space they occupy. Skip this for nominal types
   // since their internal group size is always 1.
-  if (system != TypeSystem::Nominal) {
-    for (auto& [group, info] : groupInfos) {
-      info.useCount /= group.size();
-    }
+  for (auto& [group, info] : groupInfos) {
+    info.useCount /= group.size();
   }
 
   // Sort the predecessors so the most used will be visited first.
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 24054572d..e58c7f51d 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -65,8 +65,7 @@ struct HeapTypeGeneratorImpl {
     // 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. For simplicity, always choose a
-    // supertype to bea previous type, which is valid in all type systems.
+    // types we haven't constructed yet.
     typeKinds.reserve(builder.size());
     supertypeIndices.reserve(builder.size());
     Index numRoots = 1 + rand.upTo(builder.size());
@@ -90,31 +89,23 @@ struct HeapTypeGeneratorImpl {
 
     // Initialize the recursion groups.
     recGroupEnds.reserve(builder.size());
-    if (getTypeSystem() != TypeSystem::Isorecursive) {
-      // Recursion groups don't matter and we can choose children as though we
-      // had a single large recursion group.
-      for (Index i = 0; i < builder.size(); ++i) {
-        recGroupEnds.push_back(builder.size());
-      }
-    } else {
-      // We are using isorecursive types, so create groups. Choose an expected
-      // group size uniformly at random, then create groups with random sizes on
-      // a geometric distribution based on that expected size.
-      size_t expectedSize = 1 + rand.upTo(builder.size());
-      Index groupStart = 0;
-      for (Index i = 0; i < builder.size(); ++i) {
-        if (i == builder.size() - 1 || rand.oneIn(expectedSize)) {
-          // End the old group and create a new group.
-          Index newGroupStart = i + 1;
-          builder.createRecGroup(groupStart, newGroupStart - groupStart);
-          for (Index j = groupStart; j < newGroupStart; ++j) {
-            recGroupEnds.push_back(newGroupStart);
-          }
-          groupStart = newGroupStart;
+    // Create isorecursive recursion groups. Choose an expected group size
+    // uniformly at random, then create groups with random sizes on a geometric
+    // distribution based on that expected size.
+    size_t expectedSize = 1 + rand.upTo(builder.size());
+    Index groupStart = 0;
+    for (Index i = 0; i < builder.size(); ++i) {
+      if (i == builder.size() - 1 || rand.oneIn(expectedSize)) {
+        // End the old group and create a new group.
+        Index newGroupStart = i + 1;
+        builder.createRecGroup(groupStart, newGroupStart - groupStart);
+        for (Index j = groupStart; j < newGroupStart; ++j) {
+          recGroupEnds.push_back(newGroupStart);
         }
+        groupStart = newGroupStart;
       }
-      assert(recGroupEnds.size() == builder.size());
     }
+    assert(recGroupEnds.size() == builder.size());
 
     // Create the heap types.
     for (; index < builder.size(); ++index) {
diff --git a/src/tools/tool-options.h b/src/tools/tool-options.h
index 4e9d85d00..a6e57a76e 100644
--- a/src/tools/tool-options.h
+++ b/src/tools/tool-options.h
@@ -182,10 +182,6 @@ struct ToolOptions : public Options {
   void applyFeatures(Module& module) const {
     module.features.enable(enabledFeatures);
     module.features.disable(disabledFeatures);
-    // Non-default type systems only make sense with GC enabled.
-    if (!module.features.hasGC() && getTypeSystem() == TypeSystem::Nominal) {
-      Fatal() << "Nominal typing is only allowed when GC is enabled";
-    }
   }
 
 private:
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index ce393d133..0dc9f9d17 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -228,11 +228,6 @@ void Fuzzer::checkCanonicalization() {
   // Check that structural canonicalization is working correctly by building the
   // types again, choosing randomly between equivalent possible children for
   // each definition from both the new and old sets of built types.
-  if (getTypeSystem() == TypeSystem::Nominal) {
-    // No canonicalization to check.
-    return;
-  }
-
   TypeBuilder builder(types.size());
 
   // Helper for creating new definitions of existing types, randomly choosing
@@ -274,36 +269,29 @@ void Fuzzer::checkCanonicalization() {
       // Set up recursion groups and record group ends to ensure we only select
       // valid children.
       recGroupEnds.reserve(builder.size());
-      if (getTypeSystem() != TypeSystem::Isorecursive) {
-        // No rec groups.
-        for (size_t i = 0; i < builder.size(); ++i) {
-          recGroupEnds.push_back(builder.size());
+      // Set up recursion groups
+      std::optional<RecGroup> currGroup;
+      size_t currGroupStart = 0;
+      auto finishGroup = [&](Index end) {
+        builder.createRecGroup(currGroupStart, end - currGroupStart);
+        for (Index i = currGroupStart; i < end; ++i) {
+          recGroupEnds.push_back(end);
         }
-      } else {
-        // Set up recursion groups
-        std::optional<RecGroup> currGroup;
-        size_t currGroupStart = 0;
-        auto finishGroup = [&](Index end) {
-          builder.createRecGroup(currGroupStart, end - currGroupStart);
-          for (Index i = currGroupStart; i < end; ++i) {
-            recGroupEnds.push_back(end);
-          }
-          currGroupStart = end;
-        };
-        for (Index i = 0; i < types.size(); ++i) {
-          auto type = types[i];
-          if (type.isBasic()) {
-            continue;
-          }
-          auto newGroup = type.getRecGroup();
-          if (!currGroup || newGroup != currGroup ||
-              type == types[currGroupStart]) {
-            finishGroup(i);
-            currGroup = newGroup;
-          }
+        currGroupStart = end;
+      };
+      for (Index i = 0; i < types.size(); ++i) {
+        auto type = types[i];
+        if (type.isBasic()) {
+          continue;
+        }
+        auto newGroup = type.getRecGroup();
+        if (!currGroup || newGroup != currGroup ||
+            type == types[currGroupStart]) {
+          finishGroup(i);
+          currGroup = newGroup;
         }
-        finishGroup(builder.size());
       }
+      finishGroup(builder.size());
 
       // Copy the original types
       for (; index < types.size(); ++index) {
@@ -349,7 +337,7 @@ void Fuzzer::checkCanonicalization() {
         assert(old.isBasic());
         return {OldHeapType{old}};
       }
-      if (!old.isBasic() && getTypeSystem() == TypeSystem::Isorecursive) {
+      if (!old.isBasic()) {
         // Check whether this child heap type is supposed to be a self-reference
         // into the recursion group we are defining. If it is, we must use the
         // corresponding type in the new recursion group, since anything else
@@ -514,7 +502,7 @@ void Fuzzer::checkInhabitable() {
     }
     // TODO: We could also check that the transformed types are the same as the
     // original types up to nullability.
-  } else if (getTypeSystem() == TypeSystem::Isorecursive) {
+  } else {
     // Verify the produced inhabitable types are the same as the original types
     // (which also implies that they are indeed inhabitable).
     if (types.size() != inhabitable.size()) {
diff --git a/src/wasm-type.h b/src/wasm-type.h
index d72f5477d..ad0606d59 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -40,17 +40,6 @@
 
 namespace wasm {
 
-enum class TypeSystem {
-  Isorecursive,
-  Nominal,
-};
-
-// This should only ever be called before any Types or HeapTypes have been
-// created. The default system is equirecursive.
-void setTypeSystem(TypeSystem system);
-
-TypeSystem getTypeSystem();
-
 // Dangerous! Frees all types and heap types that have ever been created and
 // resets the type system's internal state. This is only really meant to be used
 // for tests.
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index e85740614..967356210 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -229,40 +229,22 @@ void WasmBinaryWriter::writeTypes() {
   // the type section. With nominal typing there is always one group and with
   // equirecursive typing there is one group per type.
   size_t numGroups = 0;
-  // MVP types are structural and do not use recursion groups.
-  TypeSystem typeSystem = getTypeSystem();
-  if (!wasm->features.hasGC()) {
-    typeSystem = TypeSystem::Isorecursive;
-  }
-  switch (typeSystem) {
-    case TypeSystem::Nominal:
-      numGroups = 1;
-      break;
-    case TypeSystem::Isorecursive: {
-      std::optional<RecGroup> lastGroup;
-      for (auto type : indexedTypes.types) {
-        auto currGroup = type.getRecGroup();
-        numGroups += lastGroup != currGroup;
-        lastGroup = currGroup;
-      }
+  {
+    std::optional<RecGroup> lastGroup;
+    for (auto type : indexedTypes.types) {
+      auto currGroup = type.getRecGroup();
+      numGroups += lastGroup != currGroup;
+      lastGroup = currGroup;
     }
   }
   BYN_TRACE("== writeTypes\n");
   auto start = startSection(BinaryConsts::Section::Type);
   o << U32LEB(numGroups);
-  if (typeSystem == TypeSystem::Nominal) {
-    // The nominal recursion group contains every type.
-    o << S32LEB(BinaryConsts::EncodedType::Rec)
-      << U32LEB(indexedTypes.types.size());
-  }
   std::optional<RecGroup> lastGroup = std::nullopt;
   for (Index i = 0; i < indexedTypes.types.size(); ++i) {
     auto type = indexedTypes.types[i];
     // Check whether we need to start a new recursion group. Recursion groups of
-    // size 1 are implicit, so only emit a group header for larger groups. This
-    // gracefully handles non-isorecursive type systems, which only have groups
-    // of size 1 internally (even though nominal types are emitted as a single
-    // large group).
+    // size 1 are implicit, so only emit a group header for larger groups.
     auto currGroup = type.getRecGroup();
     if (lastGroup != currGroup && currGroup.size() > 1) {
       o << S32LEB(BinaryConsts::EncodedType::Rec) << U32LEB(currGroup.size());
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 8b1dfb0af..c9c35ac49 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -44,12 +44,6 @@
 
 namespace wasm {
 
-static TypeSystem typeSystem = TypeSystem::Isorecursive;
-
-void setTypeSystem(TypeSystem system) { typeSystem = system; }
-
-TypeSystem getTypeSystem() { return typeSystem; }
-
 namespace {
 
 struct TypeInfo {
@@ -104,11 +98,10 @@ struct HeapTypeInfo {
   // Otherwise, the type definition tree is still being constructed via the
   // TypeBuilder interface, so hashing and equality use pointer identity.
   bool isFinalized = true;
-  // In nominal or isorecursive mode, the supertype of this HeapType, if it
-  // exists.
+  // The supertype of this HeapType, if it exists.
   HeapTypeInfo* supertype = nullptr;
-  // In isorecursive mode, the recursion group of this type or null if the
-  // recursion group is trivial (i.e. contains only this type).
+  // The recursion group of this type or null if the recursion group is trivial
+  // (i.e. contains only this type).
   RecGroupInfo* recGroup = nullptr;
   size_t recGroupIndex = 0;
   enum Kind {
@@ -714,12 +707,6 @@ private:
       return *canonical;
     }
     std::lock_guard<std::recursive_mutex> lock(mutex);
-    // Nominal HeapTypes are always unique, so don't bother deduplicating them.
-    if constexpr (std::is_same_v<Info, HeapTypeInfo>) {
-      if (typeSystem == TypeSystem::Nominal) {
-        return insertNew();
-      }
-    }
     // Check whether we already have a type for this structural Info.
     auto indexIt = typeIDs.find(std::cref(info));
     if (indexIt != typeIDs.end()) {
@@ -759,34 +746,6 @@ template<typename Info> bool Store<Info>::isGlobalStore() {
 }
 #endif
 
-// Cache canonical nominal signature types. See comment in
-// `HeapType::HeapType(Signature)`.
-struct SignatureTypeCache {
-  std::unordered_map<Signature, HeapType> cache;
-  std::mutex mutex;
-
-  HeapType getType(Signature sig) {
-    std::lock_guard<std::mutex> lock(mutex);
-    // Try inserting a placeholder type, then replace it with a real type if we
-    // don't already have a canonical type for this signature.
-    auto [entry, inserted] = cache.insert({sig, {}});
-    auto& [_, type] = *entry;
-    if (inserted) {
-      type = globalHeapTypeStore.insert(sig);
-    }
-    return type;
-  }
-
-  void insertType(HeapType type) {
-    std::lock_guard<std::mutex> lock(mutex);
-    cache.insert({type.getSignature(), type});
-  }
-
-  void clear() { cache.clear(); }
-};
-
-static SignatureTypeCache nominalSignatureCache;
-
 // Keep track of the constructed recursion groups.
 struct RecGroupStore {
   std::mutex mutex;
@@ -841,7 +800,6 @@ static RecGroupStore globalRecGroupStore;
 void destroyAllTypesForTestingPurposesOnly() {
   globalTypeStore.clear();
   globalHeapTypeStore.clear();
-  nominalSignatureCache.clear();
   globalRecGroupStore.clear();
 }
 
@@ -1222,24 +1180,8 @@ const Type& Type::Iterator::operator*() const {
 HeapType::HeapType(Signature sig) {
   assert(!isTemp(sig.params) && "Leaking temporary type!");
   assert(!isTemp(sig.results) && "Leaking temporary type!");
-  switch (getTypeSystem()) {
-    case TypeSystem::Nominal:
-      // Special case the creation of signature types in nominal mode to return
-      // a "canonical" type for the signature, which happens to be the first one
-      // created. We depend on being able to create new function signatures in
-      // many places, and historically they have always been structural, so
-      // creating a copy of an existing signature did not result in any code
-      // bloat or semantic changes. To avoid regressions or significant changes
-      // of behavior in nominal mode, we cache the canonical heap types for each
-      // signature to emulate structural behavior.
-      new (this) HeapType(nominalSignatureCache.getType(sig));
-      return;
-    case TypeSystem::Isorecursive:
-      new (this) HeapType(
-        globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(sig)));
-      return;
-  }
-  WASM_UNREACHABLE("unexpected type system");
+  new (this)
+    HeapType(globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(sig)));
 }
 
 HeapType::HeapType(const Struct& struct_) {
@@ -1248,16 +1190,8 @@ HeapType::HeapType(const Struct& struct_) {
     assert(!isTemp(field.type) && "Leaking temporary type!");
   }
 #endif
-  switch (getTypeSystem()) {
-    case TypeSystem::Nominal:
-      new (this) HeapType(globalHeapTypeStore.insert(struct_));
-      return;
-    case TypeSystem::Isorecursive:
-      new (this) HeapType(
-        globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(struct_)));
-      return;
-  }
-  WASM_UNREACHABLE("unexpected type system");
+  new (this) HeapType(
+    globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(struct_)));
 }
 
 HeapType::HeapType(Struct&& struct_) {
@@ -1266,30 +1200,14 @@ HeapType::HeapType(Struct&& struct_) {
     assert(!isTemp(field.type) && "Leaking temporary type!");
   }
 #endif
-  switch (getTypeSystem()) {
-    case TypeSystem::Nominal:
-      new (this) HeapType(globalHeapTypeStore.insert(std::move(struct_)));
-      return;
-    case TypeSystem::Isorecursive:
-      new (this) HeapType(globalRecGroupStore.insert(
-        std::make_unique<HeapTypeInfo>(std::move(struct_))));
-      return;
-  }
-  WASM_UNREACHABLE("unexpected type system");
+  new (this) HeapType(globalRecGroupStore.insert(
+    std::make_unique<HeapTypeInfo>(std::move(struct_))));
 }
 
 HeapType::HeapType(Array array) {
   assert(!isTemp(array.element.type) && "Leaking temporary type!");
-  switch (getTypeSystem()) {
-    case TypeSystem::Nominal:
-      new (this) HeapType(globalHeapTypeStore.insert(array));
-      return;
-    case TypeSystem::Isorecursive:
-      new (this) HeapType(
-        globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(array)));
-      return;
-  }
-  WASM_UNREACHABLE("unexpected type system");
+  new (this)
+    HeapType(globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(array)));
 }
 
 bool HeapType::isFunction() const {
@@ -2774,39 +2692,6 @@ validateSubtyping(const std::vector<HeapType>& types) {
   return {};
 }
 
-std::optional<TypeBuilder::Error>
-canonicalizeNominal(CanonicalizationState& state) {
-  for (auto& info : state.newInfos) {
-    info->recGroup = nullptr;
-  }
-
-  // Nominal types do not require separate canonicalization, so just validate
-  // that their subtyping is correct.
-
-  // 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*> 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);
-         curr != nullptr && !checked.count(curr);
-         curr = curr->supertype) {
-      if (!path.insert(curr).second) {
-        return TypeBuilder::Error{i, TypeBuilder::ErrorReason::SelfSupertype};
-      }
-    }
-    // None of the types in `path` reach themselves.
-    checked.insert(path.begin(), path.end());
-  }
-
-  return {};
-}
-
 std::optional<TypeBuilder::Error> canonicalizeIsorecursive(
   CanonicalizationState& state,
   std::vector<std::unique_ptr<RecGroupInfo>>& recGroupInfos) {
@@ -2992,17 +2877,8 @@ TypeBuilder::BuildResult TypeBuilder::build() {
   auto start = std::chrono::steady_clock::now();
 #endif
 
-  switch (typeSystem) {
-    case TypeSystem::Nominal:
-      if (auto error = canonicalizeNominal(state)) {
-        return {*error};
-      }
-      break;
-    case TypeSystem::Isorecursive:
-      if (auto error = canonicalizeIsorecursive(state, impl->recGroups)) {
-        return {*error};
-      }
-      break;
+  if (auto error = canonicalizeIsorecursive(state, impl->recGroups)) {
+    return {*error};
   }
 
 #if TIME_CANONICALIZATION
@@ -3026,17 +2902,6 @@ TypeBuilder::BuildResult TypeBuilder::build() {
     return {*error};
   }
 
-  // Note built signature types. See comment in `HeapType::HeapType(Signature)`.
-  for (auto type : state.results) {
-    // Do not cache types with explicit supertypes (that is, whose supertype is
-    // not HeapType::func). We don't want to reuse such types because then we'd
-    // be adding subtyping relationships that are not in the input.
-    if (type.isSignature() && (getTypeSystem() == TypeSystem::Nominal) &&
-        !type.getSuperType()) {
-      nominalSignatureCache.insertType(type);
-    }
-  }
-
   return {state.results};
 }