Support comparing, subtyping, and naming recursive types (#3610)

When the type section is emitted, types with an equal amount of references are
ordered by an arbitrary measure of simplicity, which previously would infinitely
recurse on structurally equivalent recursive types. Similarly, calculating
whether an recursive type was a subtype of another recursive type could have
infinitely recursed. This PR avoids infinite recursions in both cases by
switching the algorithms from using normal inductive recursion to using
coinductive recursion. The difference is that while the inductive algorithms
assume the relations do not hold for a pair of HeapTypes until they have been
exhaustively shown to hold, the coinductive algorithms assume the relations hold
unless a counterexample can be found.

In addition to those two algorithms, this PR also implement name generation for
recursive types, using de Bruijn indices to stand in for inner uses of the
recursive types.

There are additional algorithms that will need to be switched from inductive to
coinductive recursion, such as least upper bound generation, but these presented
a good starting point and are sufficient to get some interesting programs
working end-to-end.

6 files changed, 453 insertions, 290 deletions

diff --git a/src/ir/module-splitting.cpp b/src/ir/module-splitting.cpp
index b8abbb42e..7215629e4 100644
--- a/src/ir/module-splitting.cpp
+++ b/src/ir/module-splitting.cpp
@@ -80,19 +80,6 @@
 #include "wasm-builder.h"
 #include "wasm.h"
 
-namespace std {
-
-// Used in ModuleSplitter::shareImportableItems
-template<> struct hash<pair<wasm::ExternalKind, wasm::Name>> {
-  size_t operator()(const pair<wasm::ExternalKind, wasm::Name>& p) const {
-    auto digest = wasm::hash(p.first);
-    wasm::rehash(digest, p.second);
-    return digest;
-  }
-};
-
-} // namespace std
-
 namespace wasm {
 
 namespace ModuleSplitting {
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 84ef3a508..4792c5d23 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -485,11 +485,8 @@ inline void collectHeapTypes(Module& wasm,
   for (auto& curr : wasm.functions) {
     counts.note(curr->sig);
     for (auto type : curr->vars) {
-      counts.maybeNote(type);
-      if (type.isTuple()) {
-        for (auto t : type) {
-          counts.maybeNote(t);
-        }
+      for (auto t : type) {
+        counts.maybeNote(t);
       }
     }
   }
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 445021bcf..8c32642b4 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -67,70 +67,56 @@ static std::ostream& printLocal(Index index, Function* func, std::ostream& o) {
   return printName(name, o);
 }
 
-static void printHeapTypeName(std::ostream& os,
-                              HeapType type,
-                              Module* wasm = nullptr,
-                              bool first = true);
+namespace {
+
+// Helper for printing the name of a type. This output is guaranteed to not
+// contain spaces.
+struct TypeNamePrinter {
+  // Optional. If present, the module's HeapType names will be used.
+  Module* wasm;
+
+  // Keep track of the first depth at which we see each HeapType so if we see it
+  // again, we can unambiguously refer to it without infinitely recursing.
+  size_t currHeapTypeDepth = 0;
+  std::unordered_map<HeapType, size_t> heapTypeDepths;
+
+  // The stream we are printing to.
+  std::ostream& os;
+
+  TypeNamePrinter(std::ostream& os, Module* wasm = nullptr)
+    : wasm(wasm), os(os) {}
+
+  void print(Type type);
+  void print(HeapType heapType);
+  void print(const Tuple& tuple);
+  void print(const Field& field);
+  void print(const Signature& sig);
+  void print(const Struct& struct_);
+  void print(const Array& array);
+  void print(const Rtt& rtt);
+};
 
-// Prints the name of a type. This output is guaranteed to not contain spaces.
-static void printTypeName(std::ostream& os, Type type, Module* wasm = nullptr) {
+void TypeNamePrinter::print(Type type) {
   if (type.isBasic()) {
     os << type;
-    return;
-  }
-  if (type.isRtt()) {
-    auto rtt = type.getRtt();
-    os << "rtt_";
-    if (rtt.hasDepth()) {
-      os << rtt.depth << '_';
-    }
-    printHeapTypeName(os, rtt.heapType, wasm);
-    return;
-  }
-  if (type.isTuple()) {
-    auto sep = "";
-    for (auto t : type) {
-      os << sep;
-      sep = "_";
-      printTypeName(os, t, wasm);
-    }
-    return;
-  }
-  if (type.isRef()) {
+  } else if (type.isTuple()) {
+    print(type.getTuple());
+  } else if (type.isRtt()) {
+    print(type.getRtt());
+  } else if (type.isRef()) {
     os << "ref";
     if (type.isNullable()) {
       os << "?";
     }
-    os << "|";
-    printHeapTypeName(os, type.getHeapType(), wasm, false);
-    os << "|";
-    return;
-  }
-  WASM_UNREACHABLE("unsupported print type");
-}
-
-static void
-printFieldName(std::ostream& os, const Field& field, Module* wasm = nullptr) {
-  if (field.mutable_) {
-    os << "mut:";
-  }
-  if (field.type == Type::i32 && field.packedType != Field::not_packed) {
-    if (field.packedType == Field::i8) {
-      os << "i8";
-    } else if (field.packedType == Field::i16) {
-      os << "i16";
-    } else {
-      WASM_UNREACHABLE("invalid packed type");
-    }
+    os << '|';
+    print(type.getHeapType());
+    os << '|';
   } else {
-    printTypeName(os, field.type, wasm);
+    WASM_UNREACHABLE("unexpected type");
   }
 }
 
-// Prints the name of a heap type. As with printTypeName, this output is
-// guaranteed to not contain spaces.
-static void
-printHeapTypeName(std::ostream& os, HeapType type, Module* wasm, bool first) {
+void TypeNamePrinter::print(HeapType type) {
   if (type.isBasic()) {
     os << type;
     return;
@@ -144,37 +130,104 @@ printHeapTypeName(std::ostream& os, HeapType type, Module* wasm, bool first) {
     os << '$' << wasm->typeNames[type].name;
     return;
   }
-  if (first) {
-    os << '$';
+  // If we have seen this HeapType before, just print its relative depth instead
+  // of infinitely recursing.
+  auto it = heapTypeDepths.find(type);
+  if (it != heapTypeDepths.end()) {
+    assert(it->second <= currHeapTypeDepth);
+    size_t relativeDepth = currHeapTypeDepth - it->second;
+    os << "..." << relativeDepth;
+    return;
+  }
+
+  // If this is the top-level heap type, add a $
+  if (currHeapTypeDepth == 0) {
+    os << "$";
   }
+
+  // Update the context for the current HeapType before recursing.
+  heapTypeDepths[type] = ++currHeapTypeDepth;
+
   if (type.isSignature()) {
-    auto sig = type.getSignature();
-    printTypeName(os, sig.params, wasm);
-    if (first) {
-      os << "_=>_";
-    } else {
-      os << "_->_";
-    }
-    printTypeName(os, sig.results, wasm);
+    print(type.getSignature());
   } else if (type.isStruct()) {
-    auto struct_ = type.getStruct();
-    os << "{";
-    auto sep = "";
-    for (auto& field : struct_.fields) {
-      os << sep;
-      sep = "_";
-      printFieldName(os, field, wasm);
-    }
-    os << "}";
+    print(type.getStruct());
   } else if (type.isArray()) {
-    os << "[";
-    printFieldName(os, type.getArray().element, wasm);
-    os << "]";
+    print(type.getArray());
   } else {
-    os << type;
+    WASM_UNREACHABLE("unexpected type");
+  }
+
+  // Restore the previous context after the recursion.
+  heapTypeDepths.erase(type);
+  --currHeapTypeDepth;
+}
+
+void TypeNamePrinter::print(const Tuple& tuple) {
+  auto sep = "";
+  for (auto type : tuple.types) {
+    os << sep;
+    sep = "_";
+    print(type);
   }
 }
 
+void TypeNamePrinter::print(const Field& field) {
+  if (field.mutable_) {
+    os << "mut:";
+  }
+  if (field.type == Type::i32 && field.packedType != Field::not_packed) {
+    if (field.packedType == Field::i8) {
+      os << "i8";
+    } else if (field.packedType == Field::i16) {
+      os << "i16";
+    } else {
+      WASM_UNREACHABLE("invalid packed type");
+    }
+  } else {
+    print(field.type);
+  }
+}
+
+void TypeNamePrinter::print(const Signature& sig) {
+  // TODO: Switch to using an unambiguous delimiter rather than differentiating
+  // only the top level with a different arrow.
+  print(sig.params);
+  if (currHeapTypeDepth == 1) {
+    os << "_=>_";
+  } else {
+    os << "_->_";
+  }
+  print(sig.results);
+}
+
+void TypeNamePrinter::print(const Struct& struct_) {
+  os << '{';
+  auto sep = "";
+  for (const auto& field : struct_.fields) {
+    os << sep;
+    sep = "_";
+    print(field);
+  }
+  os << '}';
+}
+
+void TypeNamePrinter::print(const Array& array) {
+  os << '[';
+  print(array.element);
+  os << ']';
+}
+
+void TypeNamePrinter::print(const Rtt& rtt) {
+  os << "rtt_";
+  if (rtt.hasDepth()) {
+    os << rtt.depth << '_';
+  }
+  print(rtt.heapType);
+}
+
+} // anonymous namespace
+
 // Unlike the default format, tuple types in s-expressions should not have
 // commas.
 struct SExprType {
@@ -186,7 +239,9 @@ static std::ostream& printSExprType(std::ostream& o,
                                     const SExprType& sType,
                                     Module* wasm = nullptr) {
   Type type = sType.type;
-  if (type.isTuple()) {
+  if (type.isBasic()) {
+    o << type;
+  } else if (type.isTuple()) {
     o << '(';
     auto sep = "";
     for (const auto& t : type) {
@@ -201,17 +256,17 @@ static std::ostream& printSExprType(std::ostream& o,
     if (rtt.hasDepth()) {
       o << rtt.depth << ' ';
     }
-    printHeapTypeName(o, rtt.heapType, wasm);
+    TypeNamePrinter(o, wasm).print(rtt.heapType);
     o << ')';
   } else if (type.isRef() && !type.isBasic()) {
     o << "(ref ";
     if (type.isNullable()) {
       o << "null ";
     }
-    printHeapTypeName(o, type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(type.getHeapType());
     o << ')';
   } else {
-    printTypeName(o, sType.type, wasm);
+    WASM_UNREACHABLE("unexpected type");
   }
   return o;
 }
@@ -356,7 +411,7 @@ struct PrintExpressionContents
 
     o << '(';
     printMinor(o, "type ");
-    printHeapTypeName(o, curr->sig, wasm);
+    TypeNamePrinter(o, wasm).print(HeapType(curr->sig));
     o << ')';
   }
   void visitLocalGet(LocalGet* curr) {
@@ -1793,7 +1848,7 @@ struct PrintExpressionContents
   void visitMemoryGrow(MemoryGrow* curr) { printMedium(o, "memory.grow"); }
   void visitRefNull(RefNull* curr) {
     printMedium(o, "ref.null ");
-    printHeapTypeName(o, curr->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->type.getHeapType());
   }
   void visitRefIs(RefIs* curr) {
     switch (curr->op) {
@@ -1864,11 +1919,11 @@ struct PrintExpressionContents
   }
   void visitRefTest(RefTest* curr) {
     printMedium(o, "ref.test ");
-    printHeapTypeName(o, curr->getCastType().getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->getCastType().getHeapType());
   }
   void visitRefCast(RefCast* curr) {
     printMedium(o, "ref.cast ");
-    printHeapTypeName(o, curr->getCastType().getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->getCastType().getHeapType());
   }
   void visitBrOn(BrOn* curr) {
     switch (curr->op) {
@@ -1894,11 +1949,11 @@ struct PrintExpressionContents
   }
   void visitRttCanon(RttCanon* curr) {
     printMedium(o, "rtt.canon ");
-    printHeapTypeName(o, curr->type.getRtt().heapType, wasm);
+    TypeNamePrinter(o, wasm).print(curr->type.getRtt().heapType);
   }
   void visitRttSub(RttSub* curr) {
     printMedium(o, "rtt.sub ");
-    printHeapTypeName(o, curr->type.getRtt().heapType, wasm);
+    TypeNamePrinter(o, wasm).print(curr->type.getRtt().heapType);
   }
   void visitStructNew(StructNew* curr) {
     printMedium(o, "struct.new_");
@@ -1906,7 +1961,7 @@ struct PrintExpressionContents
       o << "default_";
     }
     o << "with_rtt ";
-    printHeapTypeName(o, curr->rtt->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->rtt->type.getHeapType());
   }
   void printUnreachableReplacement() {
     // If we cannot print a valid unreachable instruction (say, a struct.get,
@@ -1940,7 +1995,7 @@ struct PrintExpressionContents
     } else {
       printMedium(o, "struct.get ");
     }
-    printHeapTypeName(o, heapType, wasm);
+    TypeNamePrinter(o, wasm).print(heapType);
     o << ' ';
     printFieldName(heapType, curr->index);
   }
@@ -1951,7 +2006,7 @@ struct PrintExpressionContents
     }
     printMedium(o, "struct.set ");
     auto heapType = curr->ref->type.getHeapType();
-    printHeapTypeName(o, heapType, wasm);
+    TypeNamePrinter(o, wasm).print(heapType);
     o << ' ';
     printFieldName(heapType, curr->index);
   }
@@ -1961,7 +2016,7 @@ struct PrintExpressionContents
       o << "default_";
     }
     o << "with_rtt ";
-    printHeapTypeName(o, curr->rtt->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->rtt->type.getHeapType());
   }
   void visitArrayGet(ArrayGet* curr) {
     const auto& element = curr->ref->type.getHeapType().getArray().element;
@@ -1974,15 +2029,15 @@ struct PrintExpressionContents
     } else {
       printMedium(o, "array.get ");
     }
-    printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
   }
   void visitArraySet(ArraySet* curr) {
     printMedium(o, "array.set ");
-    printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
   }
   void visitArrayLen(ArrayLen* curr) {
     printMedium(o, "array.len ");
-    printHeapTypeName(o, curr->ref->type.getHeapType(), wasm);
+    TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
   }
   void visitRefAs(RefAs* curr) {
     switch (curr->op) {
@@ -3251,7 +3306,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
       doIndent(o, indent);
       o << '(';
       printMedium(o, "type") << ' ';
-      printHeapTypeName(o, type, curr);
+      TypeNamePrinter(o, curr).print(type);
       o << ' ';
       handleHeapType(type);
       o << ")" << maybeNewLine;
@@ -3432,7 +3487,7 @@ printStackInst(StackInst* inst, std::ostream& o, Function* func) {
     case StackInst::TryEnd: {
       printMedium(o, "end");
       o << " ;; type: ";
-      printTypeName(o, inst->type);
+      TypeNamePrinter(o).print(inst->type);
       break;
     }
     case StackInst::IfElse: {
diff --git a/src/support/hash.h b/src/support/hash.h
index 1af462b7e..d3a858698 100644
--- a/src/support/hash.h
+++ b/src/support/hash.h
@@ -50,4 +50,17 @@ template<typename T> inline void rehash(std::size_t& digest, const T& value) {
 
 } // namespace wasm
 
+namespace std {
+
+// Hashing pairs is often useful
+template<typename T1, typename T2> struct hash<pair<T1, T2>> {
+  size_t operator()(const pair<T1, T2>& p) const {
+    auto digest = wasm::hash(p.first);
+    wasm::rehash(digest, p.second);
+    return digest;
+  }
+};
+
+} // namespace std
+
 #endif // wasm_support_hash_h
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 3dcd53d0e..d0008d357 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -171,7 +171,7 @@ public:
   bool operator!=(const Type& other) const { return id != other.id; }
   bool operator!=(const BasicType& other) const { return id != other; }
 
-  // Order types by some notion of simplicity
+  // Order types by some notion of simplicity.
   bool operator<(const Type& other) const;
 
   // Returns the type size in bytes. Only single types are supported.
@@ -184,6 +184,10 @@ public:
   // Returns the feature set required to use this type.
   FeatureSet getFeatures() const;
 
+  // Returns the tuple, assuming that this is a tuple type. Note that it is
+  // normally simpler to use operator[] and size() on the Type directly.
+  const Tuple& getTuple() const;
+
   // Gets the heap type corresponding to this type, assuming that it is a
   // reference or Rtt type.
   HeapType getHeapType() const;
@@ -349,6 +353,7 @@ public:
   bool operator!=(const HeapType& other) const { return id != other.id; }
   bool operator!=(const BasicHeapType& other) const { return id != other; }
 
+  // Order heap types by some notion of simplicity.
   bool operator<(const HeapType& other) const;
   std::string toString() const;
 
@@ -368,7 +373,6 @@ struct Tuple {
   Tuple(TypeList&& types) : types(std::move(types)) { validate(); }
   bool operator==(const Tuple& other) const { return types == other.types; }
   bool operator!=(const Tuple& other) const { return !(*this == other); }
-  bool operator<(const Tuple& other) const { return types < other.types; }
   std::string toString() const;
 
   // Prevent accidental copies
@@ -424,7 +428,6 @@ struct Field {
            mutable_ == other.mutable_;
   }
   bool operator!=(const Field& other) const { return !(*this == other); }
-  bool operator<(const Field& other) const;
   std::string toString() const;
 };
 
@@ -439,7 +442,6 @@ struct Struct {
   Struct(FieldList&& fields) : fields(std::move(fields)) {}
   bool operator==(const Struct& other) const { return fields == other.fields; }
   bool operator!=(const Struct& other) const { return !(*this == other); }
-  bool operator<(const Struct& other) const { return fields < other.fields; }
   std::string toString() const;
 
   // Prevent accidental copies
@@ -452,7 +454,6 @@ struct Array {
   Array(Field element) : element(element) {}
   bool operator==(const Array& other) const { return element == other.element; }
   bool operator!=(const Array& other) const { return !(*this == other); }
-  bool operator<(const Array& other) const { return element < other.element; }
   std::string toString() const;
 };
 
@@ -467,8 +468,7 @@ struct Rtt {
     return depth == other.depth && heapType == other.heapType;
   }
   bool operator!=(const Rtt& other) const { return !(*this == other); }
-  bool operator<(const Rtt& other) const;
-  bool hasDepth() { return depth != uint32_t(NoDepth); }
+  bool hasDepth() const { return depth != uint32_t(NoDepth); }
   std::string toString() const;
 };
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index b920dd587..a2132d09a 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -64,7 +64,6 @@ struct TypeInfo {
 
   bool operator==(const TypeInfo& other) const;
   bool operator!=(const TypeInfo& other) const { return !(*this == other); }
-  bool operator<(const TypeInfo& other) const;
 };
 
 struct HeapTypeInfo {
@@ -96,7 +95,41 @@ struct HeapTypeInfo {
   HeapTypeInfo& operator=(const HeapTypeInfo& other);
   bool operator==(const HeapTypeInfo& other) const;
   bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
-  bool operator<(const HeapTypeInfo& other) const;
+};
+
+// Helper for coinductively comparing Types and HeapTypes according to some
+// arbitrary notion of complexity.
+struct TypeComparator {
+  // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
+  // prove otherwise.
+  std::unordered_set<std::pair<HeapType, HeapType>> seen;
+  bool lessThan(Type a, Type b);
+  bool lessThan(HeapType a, HeapType b);
+  bool lessThan(const TypeInfo& a, const TypeInfo& b);
+  bool lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b);
+  bool lessThan(const Tuple& a, const Tuple& b);
+  bool lessThan(const Field& a, const Field& b);
+  bool lessThan(const Signature& a, const Signature& b);
+  bool lessThan(const Struct& a, const Struct& b);
+  bool lessThan(const Array& a, const Array& b);
+  bool lessThan(const Rtt& a, const Rtt& b);
+};
+
+// Helper for coinductively checking whether a pair of Types or HeapTypes are in
+// a subtype relation.
+struct SubTyper {
+  // Set of HeapTypes we are assuming satisfy the relation as long as we cannot
+  // prove otherwise.
+  std::unordered_set<std::pair<HeapType, HeapType>> seen;
+  bool isSubType(Type a, Type b);
+  bool isSubType(HeapType a, HeapType b);
+  bool isSubType(const Tuple& a, const Tuple& b);
+  bool isSubType(const Field& a, const Field& b);
+  bool isSubType(const HeapTypeInfo& a, const HeapTypeInfo& b);
+  bool isSubType(const Signature& a, const Signature& b);
+  bool isSubType(const Struct& a, const Struct& b);
+  bool isSubType(const Array& a, const Array& b);
+  bool isSubType(const Rtt& a, const Rtt& b);
 };
 
 } // anonymous namespace
@@ -176,24 +209,6 @@ bool TypeInfo::operator==(const TypeInfo& other) const {
   WASM_UNREACHABLE("unexpected kind");
 }
 
-bool TypeInfo::operator<(const TypeInfo& other) const {
-  if (kind != other.kind) {
-    return kind < other.kind;
-  }
-  switch (kind) {
-    case TupleKind:
-      return tuple < other.tuple;
-    case RefKind:
-      if (ref.nullable != other.ref.nullable) {
-        return ref.nullable < other.ref.nullable;
-      }
-      return ref.heapType < other.ref.heapType;
-    case RttKind:
-      return rtt < other.rtt;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 HeapTypeInfo::HeapTypeInfo(const HeapTypeInfo& other) {
   kind = other.kind;
   switch (kind) {
@@ -248,21 +263,6 @@ bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const {
   WASM_UNREACHABLE("unexpected kind");
 }
 
-bool HeapTypeInfo::operator<(const HeapTypeInfo& other) const {
-  if (kind != other.kind) {
-    return kind < other.kind;
-  }
-  switch (kind) {
-    case SignatureKind:
-      return signature < other.signature;
-    case StructKind:
-      return struct_ < other.struct_;
-    case ArrayKind:
-      return array < other.array;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 template<typename Info> struct Store {
   std::mutex mutex;
 
@@ -423,20 +423,8 @@ bool Type::isDefaultable() const {
 }
 
 bool Type::operator<(const Type& other) const {
-  if (*this == other) {
-    return false;
-  }
-  if (isBasic() && other.isBasic()) {
-    return getBasic() < other.getBasic();
-  }
-  if (isBasic()) {
-    return true;
-  }
-  if (other.isBasic()) {
-    return false;
-  }
-  return *getTypeInfo(*this) < *getTypeInfo(other);
-};
+  return TypeComparator().lessThan(*this, other);
+}
 
 unsigned Type::getByteSize() const {
   // TODO: alignment?
@@ -536,6 +524,11 @@ FeatureSet Type::getFeatures() const {
   return getSingleFeatures(*this);
 }
 
+const Tuple& Type::getTuple() const {
+  assert(isTuple());
+  return getTypeInfo(*this)->tuple;
+}
+
 HeapType Type::getHeapType() const {
   if (isBasic()) {
     switch (getBasic()) {
@@ -597,39 +590,7 @@ Type Type::get(unsigned byteSize, bool float_) {
 }
 
 bool Type::isSubType(Type left, Type right) {
-  if (left == right) {
-    return true;
-  }
-  if (left.isRef() && right.isRef()) {
-    // Consider HeapType subtyping as well, and also that a non-nullable type is
-    // potentially a supertype of a nullable one.
-    if (HeapType::isSubType(left.getHeapType(), right.getHeapType()) &&
-        (left.isNullable() == right.isNullable() || !left.isNullable())) {
-      return true;
-    }
-    return false;
-  }
-  if (left.isTuple() && right.isTuple()) {
-    if (left.size() != right.size()) {
-      return false;
-    }
-    for (size_t i = 0; i < left.size(); ++i) {
-      if (!isSubType(left[i], right[i])) {
-        return false;
-      }
-    }
-    return true;
-  }
-  if (left.isRtt() && right.isRtt()) {
-    auto leftRtt = left.getRtt();
-    auto rightRtt = right.getRtt();
-    // (rtt n $x) is a subtype of (rtt $x), that is, if the only difference in
-    // information is that the left side specifies a depth while the right side
-    // allows any depth.
-    return leftRtt.heapType == rightRtt.heapType && leftRtt.hasDepth() &&
-           !rightRtt.hasDepth();
-  }
-  return false;
+  return SubTyper().isSubType(left, right);
 }
 
 Type Type::getLeastUpperBound(Type a, Type b) {
@@ -774,19 +735,7 @@ bool HeapType::isArray() const {
 }
 
 bool HeapType::operator<(const HeapType& other) const {
-  if (*this == other) {
-    return false;
-  }
-  if (isBasic() && other.isBasic()) {
-    return getBasic() < other.getBasic();
-  }
-  if (isBasic()) {
-    return true;
-  }
-  if (other.isBasic()) {
-    return false;
-  }
-  return *getHeapTypeInfo(*this) < *getHeapTypeInfo(other);
+  return TypeComparator().lessThan(*this, other);
 }
 
 Signature HeapType::getSignature() const {
@@ -804,85 +753,12 @@ Array HeapType::getArray() const {
   return getHeapTypeInfo(*this)->array;
 }
 
-static bool isFieldSubType(const Field& left, const Field& right) {
-  if (left == right) {
-    return true;
-  }
-  // Immutable fields can be subtypes.
-  if (left.mutable_ == Immutable && right.mutable_ == Immutable) {
-    return left.packedType == right.packedType &&
-           Type::isSubType(left.type, right.type);
-  }
-  return false;
-}
-
 bool HeapType::isSubType(HeapType left, HeapType right) {
-  // See:
-  // https://github.com/WebAssembly/function-references/blob/master/proposals/function-references/Overview.md#subtyping
-  // https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#defined-types
-  if (left == right) {
-    return true;
-  }
-  // Everything is a subtype of any.
-  if (right == HeapType::any) {
-    return true;
-  }
-  // Various things are subtypes of eq.
-  if ((left == HeapType::i31 || left.isArray() || left.isStruct()) &&
-      right == HeapType::eq) {
-    return true;
-  }
-  // All typed function signatures are subtypes of funcref.
-  // Note: signatures may get covariance at some point, but do not yet.
-  if (left.isSignature() && right == HeapType::func) {
-    return true;
-  }
-  if (left.isArray() && right.isArray()) {
-    auto leftField = left.getArray().element;
-    auto rightField = left.getArray().element;
-    // Array types support depth subtyping.
-    return isFieldSubType(leftField, rightField);
-  }
-  if (left.isStruct() && right.isStruct()) {
-    // Structure types support width and depth subtyping.
-    auto leftFields = left.getStruct().fields;
-    auto rightFields = left.getStruct().fields;
-    // There may be more fields on the left, but not less.
-    if (leftFields.size() < rightFields.size()) {
-      return false;
-    }
-    for (size_t i = 0; i < rightFields.size(); i++) {
-      if (!isFieldSubType(leftFields[i], rightFields[i])) {
-        return false;
-      }
-    }
-    return true;
-  }
-  return false;
+  return SubTyper().isSubType(left, right);
 }
 
 bool Signature::operator<(const Signature& other) const {
-  if (results != other.results) {
-    return results < other.results;
-  }
-  return params < other.params;
-}
-
-bool Field::operator<(const Field& other) const {
-  if (mutable_ != other.mutable_) {
-    return mutable_ < other.mutable_;
-  }
-  if (type == Type::i32 && other.type == Type::i32) {
-    return packedType < other.packedType;
-  }
-  return type < other.type;
-}
-
-bool Rtt::operator<(const Rtt& other) const {
-  if (depth != other.depth) {
-    return depth < other.depth;
-  }
-  return heapType < other.heapType;
+  return TypeComparator().lessThan(*this, other);
 }
 
 namespace {
@@ -1087,6 +963,241 @@ std::ostream& operator<<(std::ostream& os, HeapTypeInfo info) {
   WASM_UNREACHABLE("unexpected kind");
 }
 
+namespace {
+
+bool TypeComparator::lessThan(Type a, Type b) {
+  if (a == b) {
+    return false;
+  }
+  if (a.isBasic() && b.isBasic()) {
+    return a.getBasic() < b.getBasic();
+  }
+  if (a.isBasic()) {
+    return true;
+  }
+  if (b.isBasic()) {
+    return false;
+  }
+  return lessThan(*getTypeInfo(a), *getTypeInfo(b));
+}
+
+bool TypeComparator::lessThan(HeapType a, HeapType b) {
+  if (a == b) {
+    return false;
+  }
+  if (seen.count({a, b})) {
+    // We weren't able to disprove that a < b since we last saw them, so the
+    // relation holds coinductively.
+    return true;
+  }
+  if (a.isBasic() && b.isBasic()) {
+    return a.getBasic() < b.getBasic();
+  }
+  if (a.isBasic()) {
+    return true;
+  }
+  if (b.isBasic()) {
+    return false;
+  }
+  // As we recurse, we will coinductively assume that a < b unless proven
+  // otherwise.
+  seen.insert({a, b});
+  return lessThan(*getHeapTypeInfo(a), *getHeapTypeInfo(b));
+}
+
+bool TypeComparator::lessThan(const TypeInfo& a, const TypeInfo& b) {
+  if (a.kind != b.kind) {
+    return a.kind < b.kind;
+  }
+  switch (a.kind) {
+    case TypeInfo::TupleKind:
+      return lessThan(a.tuple, b.tuple);
+    case TypeInfo::RefKind:
+      if (a.ref.nullable != b.ref.nullable) {
+        return a.ref.nullable < b.ref.nullable;
+      }
+      return lessThan(a.ref.heapType, b.ref.heapType);
+    case TypeInfo::RttKind:
+      return lessThan(a.rtt, b.rtt);
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+bool TypeComparator::lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b) {
+  if (a.kind != b.kind) {
+    return a.kind < b.kind;
+  }
+  switch (a.kind) {
+    case HeapTypeInfo::SignatureKind:
+      return lessThan(a.signature, b.signature);
+    case HeapTypeInfo::StructKind:
+      return lessThan(a.struct_, b.struct_);
+    case HeapTypeInfo::ArrayKind:
+      return lessThan(a.array, b.array);
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+bool TypeComparator::lessThan(const Tuple& a, const Tuple& b) {
+  return std::lexicographical_compare(
+    a.types.begin(),
+    a.types.end(),
+    b.types.begin(),
+    b.types.end(),
+    [&](Type ta, Type tb) { return lessThan(ta, tb); });
+}
+
+bool TypeComparator::lessThan(const Field& a, const Field& b) {
+  if (a.mutable_ != b.mutable_) {
+    return a.mutable_ < b.mutable_;
+  }
+  if (a.type == Type::i32 && b.type == Type::i32) {
+    return a.packedType < b.packedType;
+  }
+  return lessThan(a.type, b.type);
+}
+
+bool TypeComparator::lessThan(const Signature& a, const Signature& b) {
+  if (a.results != b.results) {
+    return lessThan(a.results, b.results);
+  }
+  return lessThan(a.params, b.params);
+}
+
+bool TypeComparator::lessThan(const Struct& a, const Struct& b) {
+  return std::lexicographical_compare(
+    a.fields.begin(),
+    a.fields.end(),
+    b.fields.begin(),
+    b.fields.end(),
+    [&](const Field& fa, const Field& fb) { return lessThan(fa, fb); });
+}
+
+bool TypeComparator::lessThan(const Array& a, const Array& b) {
+  return lessThan(a.element, b.element);
+}
+
+bool TypeComparator::lessThan(const Rtt& a, const Rtt& b) {
+  if (a.depth != b.depth) {
+    return a.depth < b.depth;
+  }
+  return lessThan(a.heapType, b.heapType);
+}
+
+bool SubTyper::isSubType(Type a, Type b) {
+  if (a == b) {
+    return true;
+  }
+  if (a.isRef() && b.isRef()) {
+    return (a.isNullable() == b.isNullable() || !a.isNullable()) &&
+           isSubType(a.getHeapType(), b.getHeapType());
+  }
+  if (a.isTuple() && b.isTuple()) {
+    return isSubType(a.getTuple(), b.getTuple());
+  }
+  if (a.isRtt() && b.isRtt()) {
+    return isSubType(a.getRtt(), b.getRtt());
+  }
+  return false;
+}
+
+bool SubTyper::isSubType(HeapType a, HeapType b) {
+  // See:
+  // https://github.com/WebAssembly/function-references/blob/master/proposals/function-references/Overview.md#subtyping
+  // https://github.com/WebAssembly/gc/blob/master/proposals/gc/MVP.md#defined-types
+  if (a == b) {
+    return true;
+  }
+  if (seen.count({a, b})) {
+    // We weren't able to disprove that a is a subtype of b since we last saw
+    // them, so the relation holds coinductively.
+    return true;
+  }
+  // Everything is a subtype of any.
+  if (b == HeapType::any) {
+    return true;
+  }
+  // Various things are subtypes of eq.
+  if (b == HeapType::eq) {
+    return a == HeapType::i31 || a.isArray() || a.isStruct();
+  }
+  // Some are also subtypes of data.
+  if (b == HeapType::data) {
+    return a.isData();
+  }
+  // Signatures are subtypes of funcref.
+  if (b == HeapType::func) {
+    return a.isSignature();
+  }
+  // As we recurse, we will coinductively assume that a is a subtype of b unless
+  // proven otherwise.
+  seen.insert({a, b});
+  if (a.isSignature() && b.isSignature()) {
+    return isSubType(a.getSignature(), b.getSignature());
+  }
+  if (a.isArray() && b.isArray()) {
+    return isSubType(a.getArray(), b.getArray());
+  }
+  if (a.isStruct() && b.isStruct()) {
+    return isSubType(a.getStruct(), b.getStruct());
+  }
+  return false;
+}
+
+bool SubTyper::isSubType(const Tuple& a, const Tuple& b) {
+  if (a.types.size() != b.types.size()) {
+    return false;
+  }
+  for (size_t i = 0; i < a.types.size(); ++i) {
+    if (!isSubType(a.types[i], b.types[i])) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool SubTyper::isSubType(const Field& a, const Field& b) {
+  if (a == b) {
+    return true;
+  }
+  // Immutable fields can be subtypes.
+  return a.mutable_ == Immutable && b.mutable_ == Immutable &&
+         a.packedType == b.packedType && isSubType(a.type, b.type);
+}
+
+bool SubTyper::isSubType(const Signature& a, const Signature& b) {
+  // TODO: Implement proper signature subtyping, covariant in results and
+  // contravariant in params, once V8 implements it.
+  // return isSubType(b.params, a.params) && isSubType(a.results, b.results);
+  return a == b;
+}
+
+bool SubTyper::isSubType(const Struct& a, const Struct& b) {
+  // There may be more fields on the left, but not fewer.
+  if (a.fields.size() < b.fields.size()) {
+    return false;
+  }
+  for (size_t i = 0; i < b.fields.size(); ++i) {
+    if (!isSubType(a.fields[i], b.fields[i])) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool SubTyper::isSubType(const Array& a, const Array& b) {
+  return isSubType(a.element, b.element);
+}
+
+bool SubTyper::isSubType(const Rtt& a, const Rtt& b) {
+  // (rtt n $x) is a subtype of (rtt $x), that is, if the only difference in
+  // information is that the left side specifies a depth while the right side
+  // allows any depth.
+  return a.heapType == b.heapType && a.hasDepth() && !b.hasDepth();
+}
+
+} // anonymous namespace
+
 struct TypeBuilder::Impl {
   TypeStore typeStore;