Implement standalone nominal types (#4201)

These new nominal types do not depend on the global type sytem being changed
with the --nominal flag. Instead, they can coexist with the existing
equirecursive structural types, as required in the new milestone 4 spec. This PR
implements subtyping, upper bounding, canonicalizing, and other type operations
but using the new types in the parsers and elsewhere in Binaryen is left to a
follow-on PR.

4 files changed, 624 insertions, 21 deletions

diff --git a/src/wasm-type.h b/src/wasm-type.h
index 0d0b49c70..a673b936f 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -382,8 +382,19 @@ public:
   const Struct& getStruct() const;
   Array getArray() const;
 
+  // Return whether there is a nontrivial (i.e. non-basic) nominal supertype and
+  // store it in `out` if there is. Nominal types (in the sense of isNominal,
+  // i.e. Milestone 4 nominal types) may always have supertypes and other types
+  // may have supertypes in `TypeSystem::Nominal` mode but not in
+  // `TypeSystem::Equirecursive` mode.
   bool getSuperType(HeapType& out) const;
 
+  // Whether this is a nominal type in the sense of being a GC Milestone 4
+  // nominal type. Although all non-basic HeapTypes are nominal in
+  // `TypeSystem::Nominal` mode, this will still return false unless the type is
+  // specifically constructed as a Milestone 4 nominal type.
+  bool isNominal() const;
+
   constexpr TypeID getID() const { return id; }
   constexpr BasicHeapType getBasic() const {
     assert(isBasic() && "Basic heap type expected");
@@ -571,11 +582,15 @@ struct TypeBuilder {
   Type getTempRefType(HeapType heapType, Nullability nullable);
   Type getTempRttType(Rtt rtt);
 
-  // In nominal mode, declare the HeapType being built at index `i` to be an
-  // immediate subtype of the HeapType being built at index `j`. Does nothing in
-  // equirecursive mode.
+  // In nominal mode, or for nominal types, declare the HeapType being built at
+  // index `i` to be an immediate subtype of the HeapType being built at index
+  // `j`. Does nothing for equirecursive types.
   void setSubType(size_t i, size_t j);
 
+  // Make this type nominal in the sense of the Milestone 4 GC spec, independent
+  // of the current TypeSystem configuration.
+  void setNominal(size_t i);
+
   // 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
@@ -614,6 +629,10 @@ struct TypeBuilder {
       builder.setSubType(index, other.index);
       return *this;
     }
+    Entry& setNominal() {
+      builder.setNominal(index);
+      return *this;
+    }
   };
 
   Entry operator[](size_t i) { return Entry{*this, i}; }
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index e86843f10..284a7e23b 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -104,6 +104,7 @@ 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;
+  bool isNominal = false;
   // In nominal mode, the supertype of this HeapType, if it exists.
   HeapTypeInfo* supertype = nullptr;
   enum Kind {
@@ -590,6 +591,7 @@ bool TypeInfo::operator==(const TypeInfo& other) const {
 HeapTypeInfo::HeapTypeInfo(const HeapTypeInfo& other) {
   kind = other.kind;
   supertype = other.supertype;
+  isNominal = other.isNominal;
   switch (kind) {
     case BasicKind:
       new (&basic) auto(other.basic);
@@ -641,11 +643,15 @@ HeapTypeInfo& HeapTypeInfo::operator=(const HeapTypeInfo& other) {
 }
 
 bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const {
-  // HeapTypeInfos with the same shape are considered equivalent. This is
-  // important during global canonicalization, when newly created
+  if (isNominal != other.isNominal) {
+    return false;
+  }
+
+  // Structural HeapTypeInfos with the same shape are considered equivalent.
+  // This is important during global canonicalization, when newly created
   // canonically-shaped graphs are checked against the existing globally
   // canonical graphs.
-  if (typeSystem == TypeSystem::Equirecursive) {
+  if (!isNominal && typeSystem == TypeSystem::Equirecursive) {
     return FiniteShapeEquator().eq(*this, other);
   }
 
@@ -1212,6 +1218,14 @@ bool HeapType::getSuperType(HeapType& out) const {
   return false;
 }
 
+bool HeapType::isNominal() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isNominal;
+  }
+}
+
 bool HeapType::isSubType(HeapType left, HeapType right) {
   return SubTyper().isSubType(left, right);
 }
@@ -1323,7 +1337,11 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
     // Basic HeapTypes are never subtypes of compound HeapTypes.
     return false;
   }
-  if (typeSystem == TypeSystem::Nominal) {
+  // Nominal and structural types are never subtypes of each other.
+  if (a.isNominal() != b.isNominal()) {
+    return false;
+  }
+  if (a.isNominal() || typeSystem == TypeSystem::Nominal) {
     // Subtyping must be declared in a nominal system, not derived from
     // structure, so we will not recurse. TODO: optimize this search with some
     // form of caching.
@@ -1497,6 +1515,9 @@ HeapType TypeBounder::lub(HeapType a, HeapType b) {
   if (a.isBasic() || b.isBasic()) {
     return getBasicLUB();
   }
+  if (a.isNominal() != b.isNominal()) {
+    return getBasicLUB();
+  }
 
   HeapTypeInfo* infoA = getHeapTypeInfo(a);
   HeapTypeInfo* infoB = getHeapTypeInfo(b);
@@ -1505,7 +1526,7 @@ HeapType TypeBounder::lub(HeapType a, HeapType b) {
     return getBasicLUB();
   }
 
-  if (typeSystem == TypeSystem::Nominal) {
+  if (a.isNominal() || typeSystem == TypeSystem::Nominal) {
     // Walk up the subtype tree to find the LUB. Ascend the tree from both `a`
     // and `b` in lockstep. The first type we see for a second time must be the
     // LUB because there are no cycles and the only way to encounter a type
@@ -1781,6 +1802,10 @@ std::ostream& TypePrinter::print(HeapType heapType) {
     }
 #if TRACE_CANONICALIZATION
     os << "[" << ((heapType.getID() >> 4) % 1000) << "]";
+    HeapType super;
+    if (heapType.getSuperType(super)) {
+      os << "[super " << ((super.getID() >> 4) % 1000) << "]";
+    }
 #endif
     if (getHeapTypeInfo(heapType)->kind == HeapTypeInfo::BasicKind) {
       os << '*';
@@ -1934,10 +1959,15 @@ size_t FiniteShapeHasher::hash(const TypeInfo& info) {
 }
 
 size_t FiniteShapeHasher::hash(const HeapTypeInfo& info) {
+  size_t digest = wasm::hash(info.isNominal);
+  if (info.isNominal) {
+    rehash(digest, uintptr_t(&info));
+    return digest;
+  }
   // If the HeapTypeInfo is not finalized, then it is mutable and its shape
   // might change in the future. In that case, fall back to pointer identity to
   // keep the hash consistent until all the TypeBuilder's types are finalized.
-  size_t digest = wasm::hash(info.isFinalized);
+  digest = wasm::hash(info.isFinalized);
   if (!info.isFinalized) {
     rehash(digest, uintptr_t(&info));
     return digest;
@@ -2052,6 +2082,11 @@ bool FiniteShapeEquator::eq(const TypeInfo& a, const TypeInfo& b) {
 }
 
 bool FiniteShapeEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) {
+  if (a.isNominal != b.isNominal) {
+    return false;
+  } else if (a.isNominal) {
+    return &a == &b;
+  }
   if (a.isFinalized != b.isFinalized) {
     return false;
   } else if (!a.isFinalized) {
@@ -2213,9 +2248,11 @@ struct TypeBuilder::Impl {
       // value.
       info = std::make_unique<HeapTypeInfo>(Signature());
       set(Signature());
+      initialized = false;
     }
     void set(HeapTypeInfo&& hti) {
       hti.supertype = info->supertype;
+      hti.isNominal = info->isNominal;
       *info = std::move(hti);
       info->isTemp = true;
       info->isFinalized = false;
@@ -2249,7 +2286,7 @@ void TypeBuilder::setHeapType(size_t i, HeapType::BasicHeapType basic) {
 }
 
 void TypeBuilder::setHeapType(size_t i, Signature signature) {
-  assert(i < size() && "Index out of bounds");
+  assert(i < size() && "index out of bounds");
   impl->entries[i].set(signature);
 }
 
@@ -2302,11 +2339,14 @@ Type TypeBuilder::getTempRttType(Rtt rtt) {
 
 void TypeBuilder::setSubType(size_t i, size_t j) {
   assert(i < size() && j < size() && "index out of bounds");
-  if (typeSystem == TypeSystem::Nominal) {
-    HeapTypeInfo* sub = impl->entries[i].info.get();
-    HeapTypeInfo* super = impl->entries[j].info.get();
-    sub->supertype = super;
-  }
+  HeapTypeInfo* sub = impl->entries[i].info.get();
+  HeapTypeInfo* super = impl->entries[j].info.get();
+  sub->supertype = super;
+}
+
+void TypeBuilder::setNominal(size_t i) {
+  assert(i < size() && "index out of bounds");
+  impl->entries[i].info->isNominal = true;
 }
 
 namespace {
@@ -2513,6 +2553,7 @@ private:
   Partitions splitters;
 
   void initialize(std::vector<HeapType>& roots);
+  bool replaceHeapType(HeapType* heapType);
   void translatePartitionsToTypes();
 
   // Return pointers to the non-basic HeapType children of `ht`, including
@@ -2759,6 +2800,17 @@ void ShapeCanonicalizer::initialize(std::vector<HeapType>& roots) {
   }
 }
 
+bool ShapeCanonicalizer::replaceHeapType(HeapType* heapType) {
+  auto it = states.find(*heapType);
+  if (it != states.end()) {
+    // heapType hasn't already been replaced; replace it.
+    auto set = partitions.getSetForElem(it->second);
+    *heapType = results.at(set.index);
+    return true;
+  }
+  return false;
+}
+
 void ShapeCanonicalizer::translatePartitionsToTypes() {
   // Create a single new HeapTypeInfo for each partition. Initialize each new
   // HeapTypeInfo as a copy of a representative HeapTypeInfo from its partition,
@@ -2807,16 +2859,18 @@ void ShapeCanonicalizer::translatePartitionsToTypes() {
           // Child doesn't need replacement.
           return;
         }
-        auto it = canonicalizer.states.find(*child);
-        if (it != canonicalizer.states.end()) {
-          // Child hasn't already been replaced; replace it.
-          auto set = canonicalizer.partitions.getSetForElem(it->second);
-          *child = canonicalizer.results.at(set.index);
-        }
+        canonicalizer.replaceHeapType(child);
       }
     };
     HeapType root = asHeapType(info);
     ChildUpdater(*this).walkRoot(&root);
+
+    // If this is a nominal type, we may need to update its supertype as well.
+    if (info->supertype) {
+      HeapType heapType(uintptr_t(info->supertype));
+      replaceHeapType(&heapType);
+      info->supertype = getHeapTypeInfo(heapType);
+    }
   }
 
 #if TRACE_CANONICALIZATION
@@ -2943,6 +2997,9 @@ std::vector<HeapType> buildEquirecursive(TypeBuilder& builder) {
   for (auto& entry : builder.impl->entries) {
     assert(entry.initialized && "Cannot access uninitialized HeapType");
     entry.info->isFinalized = true;
+    if (!entry.info->isNominal) {
+      entry.info->supertype = nullptr;
+    }
     heapTypes.push_back(entry.get());
   }
 
diff --git a/test/example/type-builder-nominal-new.cpp b/test/example/type-builder-nominal-new.cpp
new file mode 100644
index 000000000..d7fe83e5f
--- /dev/null
+++ b/test/example/type-builder-nominal-new.cpp
@@ -0,0 +1,435 @@
+#include <cassert>
+#include <iostream>
+
+#include "wasm-type.h"
+
+/* This file is identical to type-builder-nominal.cpp, except that instead of
+ * setting the global type system to be nominal, it instead individually sets
+ * each type to be nominal. test_signatures has been removed because the new
+ * nominal types are never considered canonical, so that test was
+ * meaningless. */
+
+using namespace wasm;
+
+static void makeNominal(TypeBuilder& builder) {
+  for (size_t i = 0; i < builder.size(); ++i) {
+    builder[i].setNominal();
+  }
+}
+
+// Construct Signature, Struct, and Array heap types using undefined types.
+void test_builder() {
+  std::cout << ";; Test TypeBuilder\n";
+
+  // (type $sig (func (param (ref $struct)) (result (ref $array) i32)))
+  // (type $struct (struct (field (ref null $array) (mut rtt 0 $array))))
+  // (type $array (array (mut externref)))
+
+  TypeBuilder builder;
+  assert(builder.size() == 0);
+  builder.grow(3);
+  assert(builder.size() == 3);
+
+  makeNominal(builder);
+
+  Type refSig = builder.getTempRefType(builder[0], NonNullable);
+  Type refStruct = builder.getTempRefType(builder[1], NonNullable);
+  Type refArray = builder.getTempRefType(builder[2], NonNullable);
+  Type refNullArray = builder.getTempRefType(builder[2], Nullable);
+  Type rttArray = builder.getTempRttType(Rtt(0, builder[2]));
+  Type refNullExt(HeapType::ext, Nullable);
+
+  Signature sig(refStruct, builder.getTempTupleType({refArray, Type::i32}));
+  Struct struct_({Field(refNullArray, Immutable), Field(rttArray, Mutable)});
+  Array array(Field(refNullExt, Mutable));
+
+  std::cout << "Before setting heap types:\n";
+  std::cout << "(ref $sig) => " << refSig << "\n";
+  std::cout << "(ref $struct) => " << refStruct << "\n";
+  std::cout << "(ref $array) => " << refArray << "\n";
+  std::cout << "(ref null $array) => " << refNullArray << "\n";
+  std::cout << "(rtt 0 $array) => " << rttArray << "\n\n";
+
+  builder[0] = sig;
+  builder[1] = struct_;
+  builder[2] = array;
+
+  std::cout << "After setting heap types:\n";
+  std::cout << "(ref $sig) => " << refSig << "\n";
+  std::cout << "(ref $struct) => " << refStruct << "\n";
+  std::cout << "(ref $array) => " << refArray << "\n";
+  std::cout << "(ref null $array) => " << refNullArray << "\n";
+  std::cout << "(rtt 0 $array) => " << rttArray << "\n\n";
+
+  std::vector<HeapType> built = builder.build();
+
+  Type newRefSig = Type(built[0], NonNullable);
+  Type newRefStruct = Type(built[1], NonNullable);
+  Type newRefArray = Type(built[2], NonNullable);
+  Type newRefNullArray = Type(built[2], Nullable);
+  Type newRttArray = Type(Rtt(0, built[2]));
+
+  std::cout << "After building types:\n";
+  std::cout << "(ref $sig) => " << newRefSig << "\n";
+  std::cout << "(ref $struct) => " << newRefStruct << "\n";
+  std::cout << "(ref $array) => " << newRefArray << "\n";
+  std::cout << "(ref null $array) => " << newRefNullArray << "\n";
+  std::cout << "(rtt 0 $array) => " << newRttArray << "\n\n";
+}
+
+// Check that the builder works when there are duplicate definitions
+void test_canonicalization() {
+  std::cout << ";; Test canonicalization\n";
+
+  // (type $struct (struct (field (ref null $sig) (ref null $sig))))
+  // (type $sig (func))
+  HeapType sig = Signature(Type::none, Type::none);
+  HeapType struct_ = Struct({Field(Type(sig, Nullable), Immutable),
+                             Field(Type(sig, Nullable), Immutable)});
+
+  TypeBuilder builder(4);
+  makeNominal(builder);
+
+  Type tempSigRef1 = builder.getTempRefType(builder[2], Nullable);
+  Type tempSigRef2 = builder.getTempRefType(builder[3], Nullable);
+
+  assert(tempSigRef1 != tempSigRef2);
+  assert(tempSigRef1 != Type(sig, Nullable));
+  assert(tempSigRef2 != Type(sig, Nullable));
+
+  builder[0] =
+    Struct({Field(tempSigRef1, Immutable), Field(tempSigRef1, Immutable)});
+  builder[1] =
+    Struct({Field(tempSigRef2, Immutable), Field(tempSigRef2, Immutable)});
+  builder[2] = Signature(Type::none, Type::none);
+  builder[3] = Signature(Type::none, Type::none);
+
+  std::vector<HeapType> built = builder.build();
+
+  assert(built[0] != struct_);
+  assert(built[1] != struct_);
+  assert(built[0] != built[1]);
+  assert(built[2] != sig);
+  assert(built[3] != sig);
+  assert(built[2] != built[3]);
+}
+
+void test_recursive() {
+  std::cout << ";; Test recursive types\n";
+
+  {
+    // Trivial recursion
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(1);
+      makeNominal(builder);
+
+      Type temp = builder.getTempRefType(builder[0], Nullable);
+      builder[0] = Signature(Type::none, temp);
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n\n";
+    assert(built[0] == built[0].getSignature().results.getHeapType());
+    assert(Type(built[0], Nullable) == built[0].getSignature().results);
+  }
+
+  {
+    // Mutual recursion
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(2);
+      makeNominal(builder);
+
+      Type temp0 = builder.getTempRefType(builder[0], Nullable);
+      Type temp1 = builder.getTempRefType(builder[1], Nullable);
+      builder[0] = Signature(Type::none, temp1);
+      builder[1] = Signature(Type::none, temp0);
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n";
+    std::cout << built[1] << "\n\n";
+    assert(built[0].getSignature().results.getHeapType() == built[1]);
+    assert(built[1].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] != built[1]);
+  }
+
+  {
+    // A longer chain of recursion
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(5);
+      makeNominal(builder);
+
+      Type temp0 = builder.getTempRefType(builder[0], Nullable);
+      Type temp1 = builder.getTempRefType(builder[1], Nullable);
+      Type temp2 = builder.getTempRefType(builder[2], Nullable);
+      Type temp3 = builder.getTempRefType(builder[3], Nullable);
+      Type temp4 = builder.getTempRefType(builder[4], Nullable);
+      builder[0] = Signature(Type::none, temp1);
+      builder[1] = Signature(Type::none, temp2);
+      builder[2] = Signature(Type::none, temp3);
+      builder[3] = Signature(Type::none, temp4);
+      builder[4] = Signature(Type::none, temp0);
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n";
+    std::cout << built[1] << "\n";
+    std::cout << built[2] << "\n";
+    std::cout << built[3] << "\n";
+    std::cout << built[4] << "\n\n";
+    assert(built[0].getSignature().results.getHeapType() == built[1]);
+    assert(built[1].getSignature().results.getHeapType() == built[2]);
+    assert(built[2].getSignature().results.getHeapType() == built[3]);
+    assert(built[3].getSignature().results.getHeapType() == built[4]);
+    assert(built[4].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] != built[1]);
+    assert(built[0] != built[2]);
+    assert(built[0] != built[3]);
+    assert(built[0] != built[4]);
+    assert(built[1] != built[2]);
+    assert(built[1] != built[3]);
+    assert(built[1] != built[4]);
+    assert(built[2] != built[3]);
+    assert(built[2] != built[4]);
+    assert(built[3] != built[4]);
+  }
+
+  {
+    // Check canonicalization for non-recursive parents and children of
+    // recursive HeapTypes.
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(6);
+      makeNominal(builder);
+
+      Type temp0 = builder.getTempRefType(builder[0], Nullable);
+      Type temp1 = builder.getTempRefType(builder[1], Nullable);
+      Type temp2 = builder.getTempRefType(builder[2], Nullable);
+      Type temp3 = builder.getTempRefType(builder[3], Nullable);
+      Type tuple0_2 = builder.getTempTupleType({temp0, temp2});
+      Type tuple1_3 = builder.getTempTupleType({temp1, temp3});
+      builder[0] = Signature(Type::none, tuple0_2);
+      builder[1] = Signature(Type::none, tuple1_3);
+      builder[2] = Signature();
+      builder[3] = Signature();
+      builder[4] = Signature(Type::none, temp0);
+      builder[5] = Signature(Type::none, temp1);
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n";
+    std::cout << built[1] << "\n";
+    std::cout << built[2] << "\n";
+    std::cout << built[3] << "\n";
+    std::cout << built[4] << "\n";
+    std::cout << built[5] << "\n\n";
+    assert(built[0] != built[1]);
+    assert(built[2] != built[3]);
+    assert(built[4] != built[5]);
+    assert(built[4].getSignature().results.getHeapType() == built[0]);
+    assert(built[5].getSignature().results.getHeapType() == built[1]);
+    assert(built[0].getSignature().results ==
+           Type({Type(built[0], Nullable), Type(built[2], Nullable)}));
+    assert(built[1].getSignature().results ==
+           Type({Type(built[1], Nullable), Type(built[3], Nullable)}));
+  }
+
+  {
+    // Folded and unfolded
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(2);
+      makeNominal(builder);
+
+      Type temp0 = builder.getTempRefType(builder[0], Nullable);
+      builder[0] = Signature(Type::none, temp0);
+      builder[1] = Signature(Type::none, temp0);
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n";
+    std::cout << built[1] << "\n\n";
+    assert(built[0].getSignature().results.getHeapType() == built[0]);
+    assert(built[1].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] != built[1]);
+  }
+}
+
+void test_subtypes() {
+  std::cout << ";; Test subtyping\n";
+
+  auto LUB = [&](HeapType a, HeapType b) {
+    Type refA = Type(a, Nullable);
+    Type refB = Type(b, Nullable);
+    Type lubAB = Type::getLeastUpperBound(refA, refB);
+    Type lubBA = Type::getLeastUpperBound(refB, refA);
+    assert(lubAB == lubBA);
+    assert(lubAB != Type::none);
+    HeapType lub = lubAB.getHeapType();
+    assert(Type::hasLeastUpperBound(refA, refB));
+    assert(Type::hasLeastUpperBound(refB, refA));
+    assert(Type::isSubType(refA, lubAB));
+    assert(Type::isSubType(refB, lubAB));
+    assert(HeapType::isSubType(a, lub));
+    assert(HeapType::isSubType(b, lub));
+    assert(lub == a || !HeapType::isSubType(lub, a));
+    assert(lub == b || !HeapType::isSubType(lub, b));
+    return lub;
+  };
+
+  {
+    // Basic Types
+    for (auto other : {HeapType::func,
+                       HeapType::ext,
+                       HeapType::any,
+                       HeapType::eq,
+                       HeapType::i31,
+                       HeapType::data}) {
+      assert(LUB(HeapType::any, other) == HeapType::any);
+    }
+    assert(LUB(HeapType::eq, HeapType::func) == HeapType::any);
+    assert(LUB(HeapType::i31, HeapType::data) == HeapType::eq);
+  }
+
+  {
+    // Identity
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(3);
+      makeNominal(builder);
+
+      builder[0] = Signature(Type::none, Type::none);
+      builder[1] = Struct{};
+      builder[2] = Array(Field(Type::i32, Mutable));
+      built = builder.build();
+    }
+    assert(LUB(built[0], built[0]) == built[0]);
+    assert(LUB(built[1], built[1]) == built[1]);
+    assert(LUB(built[2], built[2]) == built[2]);
+  }
+
+  {
+    // No subtype declarations mean no subtypes
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(5);
+      makeNominal(builder);
+
+      Type structRef0 = builder.getTempRefType(builder[0], Nullable);
+      Type structRef1 = builder.getTempRefType(builder[1], Nullable);
+      builder[0] = Struct{};
+      builder[1] = Struct{};
+      builder[2] = Signature(Type::none, Type::anyref);
+      builder[3] = Signature(Type::none, structRef0);
+      builder[4] = Signature(Type::none, structRef1);
+      built = builder.build();
+    }
+    assert(LUB(built[0], built[1]) == HeapType::data);
+    assert(LUB(built[2], built[3]) == HeapType::func);
+    assert(LUB(built[2], built[4]) == HeapType::func);
+  }
+
+  {
+    // Subtype declarations, but still no subtypes
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(3);
+      makeNominal(builder);
+
+      builder[0].subTypeOf(builder[1]);
+      builder[0] = Struct{};
+      builder[1] = Struct{};
+      builder[2] = Struct{};
+      built = builder.build();
+    }
+    assert(LUB(built[0], built[2]) == HeapType::data);
+  }
+
+  {
+    // Subtyping of identical types
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(6);
+      makeNominal(builder);
+
+      builder[0].subTypeOf(builder[1]);
+      builder[2].subTypeOf(builder[3]);
+      builder[4].subTypeOf(builder[5]);
+      builder[0] =
+        Struct({Field(Type::i32, Mutable), Field(Type::anyref, Mutable)});
+      builder[1] =
+        Struct({Field(Type::i32, Mutable), Field(Type::anyref, Mutable)});
+      builder[2] = Signature(Type::i32, Type::anyref);
+      builder[3] = Signature(Type::i32, Type::anyref);
+      builder[4] = Array(Field(Type::i32, Mutable));
+      builder[5] = Array(Field(Type::i32, Mutable));
+      built = builder.build();
+    }
+    assert(LUB(built[0], built[1]) == built[1]);
+    assert(LUB(built[2], built[3]) == built[3]);
+    assert(LUB(built[4], built[5]) == built[5]);
+  }
+
+  {
+    // Width subtyping
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(2);
+      makeNominal(builder);
+
+      builder[0] = Struct({Field(Type::i32, Immutable)});
+      builder[1] =
+        Struct({Field(Type::i32, Immutable), Field(Type::i32, Immutable)});
+      builder[1].subTypeOf(builder[0]);
+      built = builder.build();
+    }
+    assert(LUB(built[1], built[0]) == built[0]);
+  }
+
+  {
+    // Depth subtyping
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(2);
+      makeNominal(builder);
+
+      builder[0] = Struct({Field(Type::anyref, Immutable)});
+      builder[1] = Struct({Field(Type::funcref, Immutable)});
+      builder[1].subTypeOf(builder[0]);
+      built = builder.build();
+    }
+    assert(LUB(built[1], built[0]) == built[0]);
+  }
+
+  {
+    // Mutually recursive subtyping
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(4);
+      makeNominal(builder);
+
+      Type a = builder.getTempRefType(builder[0], Nullable);
+      Type b = builder.getTempRefType(builder[1], Nullable);
+      Type c = builder.getTempRefType(builder[2], Nullable);
+      Type d = builder.getTempRefType(builder[3], Nullable);
+      builder[1].subTypeOf(builder[0]);
+      builder[3].subTypeOf(builder[2]);
+      builder[0] = Struct({Field(c, Immutable)});
+      builder[1] = Struct({Field(d, Immutable)});
+      builder[2] = Struct({Field(a, Immutable)});
+      builder[3] = Struct({Field(b, Immutable)});
+      built = builder.build();
+    }
+    assert(LUB(built[0], built[1]) == built[0]);
+    assert(LUB(built[2], built[3]) == built[2]);
+  }
+}
+
+int main() {
+  // Run the tests twice to ensure things still work when the global stores are
+  // already populated.
+  for (size_t i = 0; i < 2; ++i) {
+    test_builder();
+    test_canonicalization();
+    test_recursive();
+    test_subtypes();
+  }
+}
diff --git a/test/example/type-builder-nominal-new.txt b/test/example/type-builder-nominal-new.txt
new file mode 100644
index 000000000..036dd9374
--- /dev/null
+++ b/test/example/type-builder-nominal-new.txt
@@ -0,0 +1,92 @@
+;; Test TypeBuilder
+Before setting heap types:
+(ref $sig) => [T](ref [T](func))
+(ref $struct) => [T](ref [T](func))
+(ref $array) => [T](ref [T](func))
+(ref null $array) => [T](ref null [T](func))
+(rtt 0 $array) => [T](rtt 0 [T](func))
+
+After setting heap types:
+(ref $sig) => [T](ref [T](func (param [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))) (result [T](ref [T](array (mut externref))) i32)))
+(ref $struct) => [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))
+(ref $array) => [T](ref [T](array (mut externref)))
+(ref null $array) => [T](ref null [T](array (mut externref)))
+(rtt 0 $array) => [T](rtt 0 [T](array (mut externref)))
+
+After building types:
+(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
+(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))
+(ref $array) => (ref (array (mut externref)))
+(ref null $array) => (ref null (array (mut externref)))
+(rtt 0 $array) => (rtt 0 (array (mut externref)))
+
+;; Test canonicalization
+;; Test recursive types
+(func (result (ref null ...1)))
+
+(func (result (ref null (func (result (ref null ...3))))))
+(func (result (ref null (func (result (ref null ...3))))))
+
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+
+(func (result (ref null ...1) (ref null (func))))
+(func (result (ref null ...1) (ref null (func))))
+(func)
+(func)
+(func (result (ref null (func (result ...1 (ref null (func)))))))
+(func (result (ref null (func (result ...1 (ref null (func)))))))
+
+(func (result (ref null ...1)))
+(func (result (ref null (func (result ...1)))))
+
+;; Test subtyping
+;; Test TypeBuilder
+Before setting heap types:
+(ref $sig) => [T](ref [T](func))
+(ref $struct) => [T](ref [T](func))
+(ref $array) => [T](ref [T](func))
+(ref null $array) => [T](ref null [T](func))
+(rtt 0 $array) => [T](rtt 0 [T](func))
+
+After setting heap types:
+(ref $sig) => [T](ref [T](func (param [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))) (result [T](ref [T](array (mut externref))) i32)))
+(ref $struct) => [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))
+(ref $array) => [T](ref [T](array (mut externref)))
+(ref null $array) => [T](ref null [T](array (mut externref)))
+(rtt 0 $array) => [T](rtt 0 [T](array (mut externref)))
+
+After building types:
+(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
+(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))
+(ref $array) => (ref (array (mut externref)))
+(ref null $array) => (ref null (array (mut externref)))
+(rtt 0 $array) => (rtt 0 (array (mut externref)))
+
+;; Test canonicalization
+;; Test recursive types
+(func (result (ref null ...1)))
+
+(func (result (ref null (func (result (ref null ...3))))))
+(func (result (ref null (func (result (ref null ...3))))))
+
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+
+(func (result (ref null ...1) (ref null (func))))
+(func (result (ref null ...1) (ref null (func))))
+(func)
+(func)
+(func (result (ref null (func (result ...1 (ref null (func)))))))
+(func (result (ref null (func (result ...1 (ref null (func)))))))
+
+(func (result (ref null ...1)))
+(func (result (ref null (func (result ...1)))))
+
+;; Test subtyping