Intern HeapTypes and clean up types code (#3428)

Interns HeapTypes using the same patterns and utilities already used to intern
Types. This allows HeapTypes to efficiently be compared for equality and hashed,
which may be important for very large struct types in the future. This change
also has the benefit of increasing symmetry between the APIs of Type and
HeapType, which will make the developer experience more consistent. Finally,
this change will make TypeBuilder (#3418) much simpler because it will no longer
have to introduce TypeInfo variants to refer to HeapTypes indirectly.

4 files changed, 633 insertions, 524 deletions

diff --git a/src/wasm-type.h b/src/wasm-type.h
index 4d842cdca..0e159b3a9 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -32,11 +32,24 @@
 
 namespace wasm {
 
+// The types defined in this file. All of them are small and typically passed by
+// value except for `Tuple` and `Struct`, which may own an unbounded amount of
+// data.
+class Type;
+class HeapType;
+struct Tuple;
+struct Signature;
+struct Field;
+struct Struct;
+struct Array;
+struct Rtt;
+
 class Type {
   // The `id` uniquely represents each type, so type equality is just a
   // comparison of the ids. For basic types the `id` is just the `BasicType`
   // enum value below, and for constructed types the `id` is the address of the
   // canonical representation of the type, making lookups cheap for all types.
+  // Since `Type` is really just a single integer, it should be passed by value.
   uintptr_t id;
 
 public:
@@ -54,29 +67,30 @@ public:
     anyref,
     eqref,
     i31ref,
-    _last_basic_id = i31ref,
   };
+  static constexpr BasicType _last_basic_type = i31ref;
 
-  Type() = default;
+  Type() : id(none) {}
 
   // BasicType can be implicitly upgraded to Type
-  constexpr Type(BasicType id) : id(id){};
+  constexpr Type(BasicType id) : id(id) {}
 
-  // But converting raw uint32_t is more dangerous, so make it explicit
-  explicit Type(uint64_t id) : id(id){};
+  // But converting raw uint64_t is more dangerous, so make it explicit
+  explicit Type(uint64_t id) : id(id) {}
 
   // Construct tuple from a list of single types
   Type(std::initializer_list<Type>);
 
   // Construct from tuple description
-  explicit Type(const struct Tuple&);
+  Type(const Tuple&);
+  Type(Tuple&&);
 
   // Construct from a heap type description. Also covers construction from
   // Signature, Struct or Array via implicit conversion to HeapType.
-  explicit Type(const struct HeapType&, bool nullable);
+  Type(HeapType, bool nullable);
 
   // Construct from rtt description
-  explicit Type(const struct Rtt&);
+  Type(Rtt);
 
   // Predicates
   //                 Compound Concrete
@@ -102,8 +116,8 @@ public:
   // │ Tuple       ║   │ x │   │ x │       │
   // │ Rtt         ║   │ x │ x │ x │       │
   // └─────────────╨───┴───┴───┴───┴───────┘
-  constexpr bool isBasic() const { return id <= _last_basic_id; }
-  constexpr bool isCompound() const { return id > _last_basic_id; }
+  constexpr bool isBasic() const { return id <= _last_basic_type; }
+  constexpr bool isCompound() const { return id > _last_basic_type; }
   constexpr bool isConcrete() const { return id >= i32; }
   constexpr bool isInteger() const { return id == i32 || id == i64; }
   constexpr bool isFloat() const { return id == f32 || id == f64; }
@@ -143,9 +157,9 @@ public:
   // otherwise ambiguous whether to convert both this and other to int or
   // convert other to Type.
   bool operator==(const Type& other) const { return id == other.id; }
-  bool operator==(const BasicType& otherId) const { return id == otherId; }
+  bool operator==(const BasicType& other) const { return id == other; }
   bool operator!=(const Type& other) const { return id != other.id; }
-  bool operator!=(const BasicType& otherId) const { return id != otherId; }
+  bool operator!=(const BasicType& other) const { return id != other; }
 
   // Order types by some notion of simplicity
   bool operator<(const Type& other) const;
@@ -161,7 +175,7 @@ public:
   FeatureSet getFeatures() const;
 
   // Gets the heap type corresponding to this type
-  const HeapType& getHeapType() const;
+  HeapType getHeapType() const;
 
   // Returns a number type based on its size in bytes and whether it is a float
   // type.
@@ -254,17 +268,90 @@ struct ResultType {
   std::string toString() const;
 };
 
+class HeapType {
+  // Unlike `Type`, which represents the types of values on the WebAssembly
+  // stack, `HeapType` is used to describe the structures that reference types
+  // refer to. HeapTypes are canonicalized and interned exactly like Types and
+  // should also be passed by value.
+  uintptr_t id;
+
+public:
+  enum BasicHeapType : uint32_t {
+    func,
+    ext,
+    exn,
+    any,
+    eq,
+    i31,
+  };
+  static constexpr BasicHeapType _last_basic_type = i31;
+
+  // BasicHeapType can be implicitly upgraded to HeapType
+  constexpr HeapType(BasicHeapType id) : id(id) {}
+
+  // But converting raw uint64_t is more dangerous, so make it explicit
+  explicit HeapType(uint64_t id) : id(id) {}
+
+  HeapType(Signature signature);
+  HeapType(const Struct& struct_);
+  HeapType(Struct&& struct_);
+  HeapType(Array array);
+
+  constexpr bool isBasic() const { return id <= _last_basic_type; }
+  constexpr bool isCompound() const { return id > _last_basic_type; }
+  bool isFunction() const;
+  bool isSignature() const;
+  bool isStruct() const;
+  bool isArray() const;
+
+  Signature getSignature() const;
+  const Struct& getStruct() const;
+  Array getArray() const;
+
+  constexpr uint64_t getID() const { return id; }
+  constexpr BasicHeapType getBasic() const {
+    assert(isBasic() && "Basic heap type expected");
+    return static_cast<BasicHeapType>(id);
+  }
+
+  // (In)equality must be defined for both HeapType and BasicHeapType because it
+  // is otherwise ambiguous whether to convert both this and other to int or
+  // convert other to HeapType.
+  bool operator==(const HeapType& other) const { return id == other.id; }
+  bool operator==(const BasicHeapType& other) const { return id == other; }
+  bool operator!=(const HeapType& other) const { return id != other.id; }
+  bool operator!=(const BasicHeapType& other) const { return id != other; }
+
+  bool operator<(const HeapType& other) const;
+  std::string toString() const;
+};
+
 typedef std::vector<Type> TypeList;
 
+// Passed by reference rather than by value because it can own an unbounded
+// amount of data.
 struct Tuple {
   TypeList types;
   Tuple() : types() {}
-  Tuple(std::initializer_list<Type> types) : types(types) {}
-  Tuple(const TypeList& types) : types(types) {}
-  Tuple(TypeList&& types) : types(std::move(types)) {}
+  Tuple(std::initializer_list<Type> types) : types(types) { validate(); }
+  Tuple(const TypeList& types) : types(types) { validate(); }
+  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
+  Struct& operator=(const Struct&) = delete;
+
+private:
+  void validate() {
+#ifndef NDEBUG
+    for (auto type : types) {
+      assert(type.isSingle());
+    }
+#endif
+  }
 };
 
 struct Signature {
@@ -316,6 +403,8 @@ struct Field {
 
 typedef std::vector<Field> FieldList;
 
+// Passed by reference rather than by value because it can own an unbounded
+// amount of data.
 struct Struct {
   FieldList fields;
   Struct(const Struct& other) : fields(other.fields) {}
@@ -325,85 +414,30 @@ struct Struct {
   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
+  Struct& operator=(const Struct&) = delete;
 };
 
 struct Array {
   Field element;
   Array(const Array& other) : element(other.element) {}
-  Array(const Field& element) : element(element) {}
-  Array(Field&& element) : element(std::move(element)) {}
+  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;
 };
 
-struct HeapType {
-  enum Kind {
-    FuncKind,
-    ExternKind,
-    ExnKind,
-    AnyKind,
-    EqKind,
-    I31Kind,
-    _last_basic_kind = I31Kind,
-    SignatureKind,
-    StructKind,
-    ArrayKind,
-  } kind;
-  union {
-    Signature signature;
-    Struct struct_;
-    Array array;
-  };
-  HeapType(Kind kind) : kind(kind) { assert(kind <= _last_basic_kind); }
-  HeapType(const Signature& signature)
-    : kind(SignatureKind), signature(signature) {}
-  HeapType(Signature&& signature)
-    : kind(SignatureKind), signature(std::move(signature)) {}
-  HeapType(const Struct& struct_) : kind(StructKind), struct_(struct_) {}
-  HeapType(Struct&& struct_) : kind(StructKind), struct_(std::move(struct_)) {}
-  HeapType(const Array& array) : kind(ArrayKind), array(array) {}
-  HeapType(Array&& array) : kind(ArrayKind), array(std::move(array)) {}
-  HeapType(const HeapType& other);
-  ~HeapType();
-
-  bool isBasic() const { return kind <= _last_basic_kind; }
-  bool isSignature() const { return kind == SignatureKind; }
-  Signature getSignature() const {
-    assert(isSignature() && "Not a signature");
-    return signature;
-  }
-  bool isStruct() const { return kind == StructKind; }
-  const Struct& getStruct() const {
-    assert(isStruct() && "Not a struct");
-    return struct_;
-  }
-  bool isArray() const { return kind == ArrayKind; }
-  const Array& getArray() const {
-    assert(isArray() && "Not an array");
-    return array;
-  }
-  bool isException() const { return kind == ExnKind; }
-
-  bool operator==(const HeapType& other) const;
-  bool operator!=(const HeapType& other) const { return !(*this == other); }
-  bool operator<(const HeapType& other) const;
-  HeapType& operator=(const HeapType& other);
-  std::string toString() const;
-};
-
 struct Rtt {
   uint32_t depth;
   HeapType heapType;
-  Rtt(uint32_t depth, const HeapType& heapType)
-    : depth(depth), heapType(heapType) {}
-  Rtt(uint32_t depth, HeapType&& heapType)
-    : depth(depth), heapType(std::move(heapType)) {}
+  Rtt(uint32_t depth, HeapType heapType) : depth(depth), heapType(heapType) {}
   bool operator==(const Rtt& other) const {
     return depth == other.depth && heapType == other.heapType;
   }
   bool operator!=(const Rtt& other) const { return !(*this == other); }
+  bool operator<(const Rtt& other) const;
   std::string toString() const;
 };
 
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index e70dc4a29..25c1eea8c 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1034,29 +1034,29 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
     return;
   }
   int ret = 0;
-  switch (type.kind) {
-    case HeapType::FuncKind:
-      ret = BinaryConsts::EncodedHeapType::func;
-      break;
-    case HeapType::ExternKind:
-      ret = BinaryConsts::EncodedHeapType::extern_;
-      break;
-    case HeapType::ExnKind:
-      ret = BinaryConsts::EncodedHeapType::exn;
-      break;
-    case HeapType::AnyKind:
-      ret = BinaryConsts::EncodedHeapType::any;
-      break;
-    case HeapType::EqKind:
-      ret = BinaryConsts::EncodedHeapType::eq;
-      break;
-    case HeapType::I31Kind:
-      ret = BinaryConsts::EncodedHeapType::i31;
-      break;
-    case HeapType::SignatureKind:
-    case HeapType::StructKind:
-    case HeapType::ArrayKind:
-      WASM_UNREACHABLE("TODO: compound GC types");
+  if (type.isBasic()) {
+    switch (type.getBasic()) {
+      case HeapType::func:
+        ret = BinaryConsts::EncodedHeapType::func;
+        break;
+      case HeapType::ext:
+        ret = BinaryConsts::EncodedHeapType::extern_;
+        break;
+      case HeapType::exn:
+        ret = BinaryConsts::EncodedHeapType::exn;
+        break;
+      case HeapType::any:
+        ret = BinaryConsts::EncodedHeapType::any;
+        break;
+      case HeapType::eq:
+        ret = BinaryConsts::EncodedHeapType::eq;
+        break;
+      case HeapType::i31:
+        ret = BinaryConsts::EncodedHeapType::i31;
+        break;
+    }
+  } else {
+    WASM_UNREACHABLE("TODO: compound GC types");
   }
   o << S64LEB(ret); // TODO: Actually s33
 }
@@ -1401,17 +1401,17 @@ HeapType WasmBinaryBuilder::getHeapType() {
   }
   switch (type) {
     case BinaryConsts::EncodedHeapType::func:
-      return HeapType::FuncKind;
+      return HeapType::func;
     case BinaryConsts::EncodedHeapType::extern_:
-      return HeapType::ExternKind;
+      return HeapType::ext;
     case BinaryConsts::EncodedHeapType::exn:
-      return HeapType::ExnKind;
+      return HeapType::exn;
     case BinaryConsts::EncodedHeapType::any:
-      return HeapType::AnyKind;
+      return HeapType::any;
     case BinaryConsts::EncodedHeapType::eq:
-      return HeapType::EqKind;
+      return HeapType::eq;
     case BinaryConsts::EncodedHeapType::i31:
-      return HeapType::I31Kind;
+      return HeapType::i31;
     default:
       throwError("invalid wasm heap type: " + std::to_string(type));
   }
@@ -5630,7 +5630,8 @@ bool WasmBinaryBuilder::maybeVisitStructGet(Expression*& out, uint32_t code) {
     default:
       return false;
   }
-  auto type = getHeapType();
+  // This type annotation is unused. Beware it needing to be used in the future!
+  getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
   curr->finalize();
@@ -5643,7 +5644,8 @@ bool WasmBinaryBuilder::maybeVisitStructSet(Expression*& out, uint32_t code) {
     return false;
   }
   auto* curr = allocator.alloc<StructSet>();
-  auto type = getHeapType();
+  // This type annotation is unused. Beware it needing to be used in the future!
+  getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
   curr->value = popNonVoidExpression();
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 37592fcd5..21104d0fe 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -879,32 +879,32 @@ HeapType SExpressionWasmBuilder::stringToHeapType(const char* str,
                                                   bool prefix) {
   if (str[0] == 'a') {
     if (str[1] == 'n' && str[2] == 'y' && (prefix || str[3] == 0)) {
-      return HeapType::AnyKind;
+      return HeapType::any;
     }
   }
   if (str[0] == 'e') {
     if (str[1] == 'q' && (prefix || str[2] == 0)) {
-      return HeapType::EqKind;
+      return HeapType::eq;
     }
     if (str[1] == 'x') {
       if (str[2] == 'n' && (prefix || str[3] == 0)) {
-        return HeapType::ExnKind;
+        return HeapType::exn;
       }
       if (str[2] == 't' && str[3] == 'e' && str[4] == 'r' && str[5] == 'n' &&
           (prefix || str[6] == 0)) {
-        return HeapType::ExternKind;
+        return HeapType::ext;
       }
     }
   }
   if (str[0] == 'i') {
     if (str[1] == '3' && str[2] == '1' && (prefix || str[3] == 0)) {
-      return HeapType::I31Kind;
+      return HeapType::i31;
     }
   }
   if (str[0] == 'f') {
     if (str[1] == 'u' && str[2] == 'n' && str[3] == 'c' &&
         (prefix || str[4] == 0)) {
-      return HeapType::FuncKind;
+      return HeapType::func;
     }
   }
   throw ParseException(std::string("invalid wasm heap type: ") + str);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 22a7c9888..48b37a864 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -27,7 +27,10 @@
 
 namespace wasm {
 
+namespace {
+
 struct TypeInfo {
+  using type_t = Type;
   enum Kind {
     TupleKind,
     RefKind,
@@ -45,44 +48,11 @@ struct TypeInfo {
 
   TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {}
   TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {}
-  TypeInfo(const HeapType& heapType, bool nullable)
+  TypeInfo(HeapType heapType, bool nullable)
     : kind(RefKind), ref{heapType, nullable} {}
-  TypeInfo(HeapType&& heapType, bool nullable)
-    : kind(RefKind), ref{std::move(heapType), nullable} {}
-  TypeInfo(const Rtt& rtt) : kind(RttKind), rtt(rtt) {}
-  TypeInfo(Rtt&& rtt) : kind(RttKind), rtt(std::move(rtt)) {}
-  TypeInfo(const TypeInfo& other) {
-    kind = other.kind;
-    switch (kind) {
-      case TupleKind:
-        new (&tuple) auto(other.tuple);
-        return;
-      case RefKind:
-        new (&ref) auto(other.ref);
-        return;
-      case RttKind:
-        new (&rtt) auto(other.rtt);
-        return;
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
-  ~TypeInfo() {
-    switch (kind) {
-      case TupleKind: {
-        tuple.~Tuple();
-        return;
-      }
-      case RefKind: {
-        ref.~Ref();
-        return;
-      }
-      case RttKind: {
-        rtt.~Rtt();
-        return;
-      }
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
+  TypeInfo(Rtt rtt) : kind(RttKind), rtt(rtt) {}
+  TypeInfo(const TypeInfo& other);
+  ~TypeInfo();
 
   constexpr bool isTuple() const { return kind == TupleKind; }
   constexpr bool isRef() const { return kind == RefKind; }
@@ -90,257 +60,272 @@ struct TypeInfo {
 
   bool isNullable() const { return kind == RefKind && ref.nullable; }
 
-  bool operator==(const TypeInfo& other) const {
-    if (kind != other.kind) {
-      return false;
-    }
-    switch (kind) {
-      case TupleKind:
-        return tuple == other.tuple;
-      case RefKind:
-        return ref.heapType == other.ref.heapType &&
-               ref.nullable == other.ref.nullable;
-      case RttKind:
-        return rtt == other.rtt;
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
+  bool operator==(const TypeInfo& other) const;
   bool operator!=(const TypeInfo& other) const { return !(*this == other); }
-  TypeInfo& operator=(const TypeInfo& other) {
-    if (&other != this) {
-      this->~TypeInfo();
-      new (this) auto(other);
-    }
-    return *this;
-  }
-
-  std::string toString() const;
+  bool operator<(const TypeInfo& other) const;
 };
 
-std::ostream& operator<<(std::ostream&, TypeInfo);
+struct HeapTypeInfo {
+  using type_t = HeapType;
+  enum Kind {
+    SignatureKind,
+    StructKind,
+    ArrayKind,
+  } kind;
+  union {
+    Signature signature;
+    Struct struct_;
+    Array array;
+  };
+
+  HeapTypeInfo(Signature sig) : kind(SignatureKind), signature(sig) {}
+  HeapTypeInfo(const Struct& struct_) : kind(StructKind), struct_(struct_) {}
+  HeapTypeInfo(Struct&& struct_)
+    : kind(StructKind), struct_(std::move(struct_)) {}
+  HeapTypeInfo(Array array) : kind(ArrayKind), array(array) {}
+  HeapTypeInfo(const HeapTypeInfo& other);
+  ~HeapTypeInfo();
+
+  constexpr bool isSignature() const { return kind == SignatureKind; }
+  constexpr bool isStruct() const { return kind == StructKind; }
+  constexpr bool isArray() const { return kind == ArrayKind; }
+
+  bool operator==(const HeapTypeInfo& other) const;
+  bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
+  bool operator<(const HeapTypeInfo& other) const;
+};
 
+} // anonymous namespace
 } // namespace wasm
 
 namespace std {
 
-template<> class hash<wasm::TypeList> {
+template<> class hash<wasm::TypeInfo> {
 public:
-  size_t operator()(const wasm::TypeList& types) const {
-    auto digest = wasm::hash(types.size());
-    for (auto type : types) {
-      wasm::rehash(digest, type);
-    }
-    return digest;
-  }
+  size_t operator()(const wasm::TypeInfo&) const;
 };
 
-template<> class hash<wasm::FieldList> {
+template<> class hash<wasm::HeapTypeInfo> {
 public:
-  size_t operator()(const wasm::FieldList& fields) const {
-    auto digest = wasm::hash(fields.size());
-    for (auto field : fields) {
-      wasm::rehash(digest, field);
-    }
-    return digest;
-  }
+  size_t operator()(const wasm::HeapTypeInfo&) const;
 };
 
-template<> class hash<wasm::TypeInfo> {
-public:
-  size_t operator()(const wasm::TypeInfo& info) const {
-    auto digest = wasm::hash(info.kind);
-    switch (info.kind) {
-      case wasm::TypeInfo::TupleKind: {
-        wasm::rehash(digest, info.tuple);
-        return digest;
-      }
-      case wasm::TypeInfo::RefKind: {
-        wasm::rehash(digest, info.ref.heapType);
-        wasm::rehash(digest, info.ref.nullable);
-        return digest;
-      }
-      case wasm::TypeInfo::RttKind: {
-        wasm::rehash(digest, info.rtt);
-        return digest;
-      }
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
-};
+} // namespace std
 
-size_t hash<wasm::Type>::operator()(const wasm::Type& type) const {
-  return wasm::hash(type.getID());
-}
+namespace wasm {
+namespace {
 
-size_t hash<wasm::Tuple>::operator()(const wasm::Tuple& tuple) const {
-  return wasm::hash(tuple.types);
-}
+TypeInfo* getTypeInfo(Type type) { return (TypeInfo*)type.getID(); }
+HeapTypeInfo* getHeapTypeInfo(HeapType ht) { return (HeapTypeInfo*)ht.getID(); }
 
-size_t hash<wasm::Signature>::operator()(const wasm::Signature& sig) const {
-  auto digest = wasm::hash(sig.params);
-  wasm::rehash(digest, sig.results);
-  return digest;
+TypeInfo::TypeInfo(const TypeInfo& other) {
+  kind = other.kind;
+  switch (kind) {
+    case TupleKind:
+      new (&tuple) auto(other.tuple);
+      return;
+    case RefKind:
+      new (&ref) auto(other.ref);
+      return;
+    case RttKind:
+      new (&rtt) auto(other.rtt);
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Field>::operator()(const wasm::Field& field) const {
-  auto digest = wasm::hash(field.type);
-  wasm::rehash(digest, field.packedType);
-  wasm::rehash(digest, field.mutable_);
-  // Note that the name is not hashed here - it is pure metadata for printing
-  // purposes only.
-  return digest;
+TypeInfo::~TypeInfo() {
+  switch (kind) {
+    case TupleKind:
+      tuple.~Tuple();
+      return;
+    case RefKind:
+      ref.~Ref();
+      return;
+    case RttKind:
+      rtt.~Rtt();
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
-  return wasm::hash(struct_.fields);
+bool TypeInfo::operator==(const TypeInfo& other) const {
+  if (kind != other.kind) {
+    return false;
+  }
+  switch (kind) {
+    case TupleKind:
+      return tuple == other.tuple;
+    case RefKind:
+      return ref.heapType == other.ref.heapType &&
+             ref.nullable == other.ref.nullable;
+    case RttKind:
+      return rtt == other.rtt;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Array>::operator()(const wasm::Array& array) const {
-  return wasm::hash(array.element);
+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");
 }
 
-size_t hash<wasm::HeapType>::operator()(const wasm::HeapType& heapType) const {
-  auto digest = wasm::hash(heapType.kind);
-  switch (heapType.kind) {
-    case wasm::HeapType::FuncKind:
-    case wasm::HeapType::ExternKind:
-    case wasm::HeapType::AnyKind:
-    case wasm::HeapType::EqKind:
-    case wasm::HeapType::I31Kind:
-    case wasm::HeapType::ExnKind:
-      return digest;
-    case wasm::HeapType::SignatureKind:
-      wasm::rehash(digest, heapType.signature);
-      return digest;
-    case wasm::HeapType::StructKind:
-      wasm::rehash(digest, heapType.struct_);
-      return digest;
-    case wasm::HeapType::ArrayKind:
-      wasm::rehash(digest, heapType.array);
-      return digest;
+HeapTypeInfo::HeapTypeInfo(const HeapTypeInfo& other) {
+  kind = other.kind;
+  switch (kind) {
+    case SignatureKind:
+      new (&signature) auto(other.signature);
+      return;
+    case StructKind:
+      new (&struct_) auto(other.struct_);
+      return;
+    case ArrayKind:
+      new (&array) auto(other.array);
+      return;
   }
   WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Rtt>::operator()(const wasm::Rtt& rtt) const {
-  auto digest = wasm::hash(rtt.depth);
-  wasm::rehash(digest, rtt.heapType);
-  return digest;
+HeapTypeInfo::~HeapTypeInfo() {
+  switch (kind) {
+    case SignatureKind:
+      signature.~Signature();
+      return;
+    case StructKind:
+      struct_.~Struct();
+      return;
+    case ArrayKind:
+      array.~Array();
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-} // namespace std
-
-namespace wasm {
+bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const {
+  if (kind != other.kind) {
+    return false;
+  }
+  switch (kind) {
+    case SignatureKind:
+      return signature == other.signature;
+    case StructKind:
+      return struct_ == other.struct_;
+    case ArrayKind:
+      return array == other.array;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
 
-namespace {
+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");
+}
 
-struct TypeStore {
+template<typename Info> struct Store {
   std::mutex mutex;
 
-  // Track unique_ptrs for constructed types to avoid leaks
-  std::vector<std::unique_ptr<TypeInfo>> constructedTypes;
-
-  // Maps from constructed types to the canonical Type ID.
-  std::unordered_map<TypeInfo, uintptr_t> indices = {
-    // If a Type is constructed from a list of types, the list of types becomes
-    // implicitly converted to a TypeInfo before canonicalizing its id. This is
-    // also the case if a list of just one type is provided, even though such a
-    // list of types will be canonicalized to the BasicType of the single type.
-    // As such, the following entries are solely placeholders to enable the
-    // lookup of lists of just one type to the BasicType of the single type.
-    {TypeInfo(Tuple()), Type::none},
-    {TypeInfo({Type::unreachable}), Type::unreachable},
-    {TypeInfo({Type::i32}), Type::i32},
-    {TypeInfo({Type::i64}), Type::i64},
-    {TypeInfo({Type::f32}), Type::f32},
-    {TypeInfo({Type::f64}), Type::f64},
-    {TypeInfo({Type::v128}), Type::v128},
-    {TypeInfo({Type::funcref}), Type::funcref},
-    {TypeInfo(HeapType(HeapType::FuncKind), true), Type::funcref},
-    {TypeInfo({Type::externref}), Type::externref},
-    {TypeInfo(HeapType(HeapType::ExternKind), true), Type::externref},
-    {TypeInfo({Type::exnref}), Type::exnref},
-    {TypeInfo(HeapType(HeapType::ExnKind), true), Type::exnref},
-    {TypeInfo({Type::anyref}), Type::anyref},
-    {TypeInfo(HeapType(HeapType::AnyKind), true), Type::anyref},
-    {TypeInfo({Type::eqref}), Type::eqref},
-    {TypeInfo(HeapType(HeapType::EqKind), true), Type::eqref},
-    {TypeInfo({Type::i31ref}), Type::i31ref},
-    {TypeInfo(HeapType(HeapType::I31Kind), false), Type::i31ref},
-  };
+  // Track unique_ptrs for constructed types to avoid leaks.
+  std::vector<std::unique_ptr<Info>> constructedTypes;
 
-  uintptr_t canonicalize(const TypeInfo& info) {
+  // Maps from constructed types to their canonical Type IDs.
+  std::unordered_map<Info, uintptr_t> typeIDs;
+
+  typename Info::type_t canonicalize(const Info& info) {
     std::lock_guard<std::mutex> lock(mutex);
-    auto indexIt = indices.find(info);
-    if (indexIt != indices.end()) {
-      return indexIt->second;
+    auto indexIt = typeIDs.find(info);
+    if (indexIt != typeIDs.end()) {
+      return typename Info::type_t(indexIt->second);
     }
-    auto ptr = std::make_unique<TypeInfo>(info);
+    auto ptr = std::make_unique<Info>(info);
     auto id = uintptr_t(ptr.get());
     constructedTypes.push_back(std::move(ptr));
-    assert(id > Type::_last_basic_id);
-    indices[info] = id;
-    return id;
+    assert(id > Info::type_t::_last_basic_type);
+    typeIDs[info] = id;
+    return typename Info::type_t(id);
   }
+};
 
-  Type makeType(const Tuple& tuple) {
-    auto& types = tuple.types;
-#ifndef NDEBUG
-    for (Type t : types) {
-      assert(t.isSingle());
-    }
-#endif
-    if (types.size() == 0) {
-      return Type::none;
-    }
-    if (types.size() == 1) {
-      return types[0];
+struct TypeStore : Store<TypeInfo> {
+  Type canonicalize(TypeInfo info) {
+    if (info.isTuple()) {
+      if (info.tuple.types.size() == 0) {
+        return Type::none;
+      }
+      if (info.tuple.types.size() == 1) {
+        return info.tuple.types[0];
+      }
     }
-    return Type(canonicalize(TypeInfo(tuple)));
-  }
-
-  Type makeType(const HeapType& heapType, bool nullable) {
-#ifndef NDEBUG
-    switch (heapType.kind) {
-      case HeapType::FuncKind:
-      case HeapType::ExternKind:
-      case HeapType::AnyKind:
-      case HeapType::EqKind:
-      case HeapType::I31Kind:
-      case HeapType::ExnKind:
-      case HeapType::SignatureKind:
-        break;
-      case HeapType::StructKind:
-        for (Field f : heapType.struct_.fields) {
-          assert(f.type.isSingle());
+    if (info.isRef() && info.ref.heapType.isBasic()) {
+      if (info.ref.nullable) {
+        switch (info.ref.heapType.getBasic()) {
+          case HeapType::func:
+            return Type::funcref;
+          case HeapType::ext:
+            return Type::externref;
+          case HeapType::exn:
+            return Type::exnref;
+          case HeapType::any:
+            return Type::anyref;
+          case HeapType::eq:
+            return Type::eqref;
+          case HeapType::i31:
+            break;
         }
-        break;
-      case HeapType::ArrayKind:
-        assert(heapType.array.element.type.isSingle());
-        break;
+      } else {
+        if (info.ref.heapType == HeapType::i31) {
+          return Type::i31ref;
+        }
+      }
     }
-#endif
-    return Type(canonicalize(TypeInfo(heapType, nullable)));
+    return Store<TypeInfo>::canonicalize(info);
   }
-
-  Type makeType(const Rtt& rtt) { return Type(canonicalize(TypeInfo(rtt))); }
 };
 
-TypeStore globalTypeStore;
+using HeapTypeStore = Store<HeapTypeInfo>;
 
-TypeInfo* getTypeInfo(const Type& type) { return (TypeInfo*)type.getID(); }
+TypeStore globalTypeStore;
+HeapTypeStore globalHeapTypeStore;
 
 } // anonymous namespace
 
 Type::Type(std::initializer_list<Type> types) : Type(Tuple(types)) {}
 
-Type::Type(const Tuple& tuple) { *this = globalTypeStore.makeType(tuple); }
+Type::Type(const Tuple& tuple) {
+  new (this) Type(globalTypeStore.canonicalize(tuple));
+}
 
-Type::Type(const HeapType& heapType, bool nullable) {
-  *this = globalTypeStore.makeType(heapType, nullable);
+Type::Type(Tuple&& tuple) {
+  new (this) Type(globalTypeStore.canonicalize(std::move(tuple)));
 }
 
-Type::Type(const Rtt& rtt) { *this = globalTypeStore.makeType(rtt); }
+Type::Type(HeapType heapType, bool nullable) {
+  new (this) Type(globalTypeStore.canonicalize(TypeInfo(heapType, nullable)));
+}
+
+Type::Type(Rtt rtt) { new (this) Type(globalTypeStore.canonicalize(rtt)); }
 
 bool Type::isTuple() const {
   if (isBasic()) {
@@ -363,7 +348,7 @@ bool Type::isFunction() const {
     return id == funcref;
   } else {
     auto* info = getTypeInfo(*this);
-    return info->isRef() && info->ref.heapType.isSignature();
+    return info->isRef() && info->ref.heapType.isFunction();
   }
 }
 
@@ -372,7 +357,7 @@ bool Type::isException() const {
     return id == exnref;
   } else {
     auto* info = getTypeInfo(*this);
-    return info->isRef() && info->ref.heapType.isException();
+    return info->isRef() && info->ref.heapType == HeapType::exn;
   }
 }
 
@@ -397,25 +382,20 @@ bool Type::isStruct() const { return isRef() && getHeapType().isStruct(); }
 bool Type::isArray() const { return isRef() && getHeapType().isArray(); }
 
 bool Type::operator<(const Type& other) const {
-  auto comp = [](const Type& a, const Type& b) {
-    if (a.isBasic() && b.isBasic()) {
-      return a.getBasic() < b.getBasic();
-    }
-    if (a.isBasic()) {
-      return true;
-    }
-    if (b.isBasic()) {
-      return false;
-    }
-    // Both are compound.
-    if (a.isNullable() != b.isNullable()) {
-      return a.isNullable();
-    }
-    return a.getHeapType() < b.getHeapType();
-  };
-  return std::lexicographical_compare(
-    begin(), end(), other.begin(), other.end(), comp);
-}
+  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);
+};
 
 unsigned Type::getByteSize() const {
   // TODO: alignment?
@@ -512,39 +492,43 @@ FeatureSet Type::getFeatures() const {
   return getSingleFeatures(*this);
 }
 
-// getHeapType() returns a const HeapType&, so we need a canonical object to
-// return for the basic types, so that we don't create a temporary copy on each
-// call.
-namespace statics {
-static HeapType funcHeapType(HeapType::FuncKind),
-  externHeapType(HeapType::ExternKind), exnHeapType(HeapType::ExnKind),
-  anyHeapType(HeapType::AnyKind), eqHeapType(HeapType::EqKind),
-  i31HeapType(HeapType::I31Kind);
-}
-
-const HeapType& Type::getHeapType() const {
-  if (isRef()) {
-    if (isCompound()) {
-      return getTypeInfo(*this)->ref.heapType;
-    }
+HeapType Type::getHeapType() const {
+  if (isBasic()) {
     switch (getBasic()) {
-      case funcref:
-        return statics::funcHeapType;
-      case externref:
-        return statics::externHeapType;
-      case exnref:
-        return statics::exnHeapType;
-      case anyref:
-        return statics::anyHeapType;
-      case eqref:
-        return statics::eqHeapType;
-      case i31ref:
-        return statics::i31HeapType;
-      default:
+      case Type::none:
+      case Type::unreachable:
+      case Type::i32:
+      case Type::i64:
+      case Type::f32:
+      case Type::f64:
+      case Type::v128:
         break;
+      case Type::funcref:
+        return HeapType::func;
+      case Type::externref:
+        return HeapType::ext;
+      case Type::exnref:
+        return HeapType::exn;
+      case Type::anyref:
+        return HeapType::any;
+      case Type::eqref:
+        return HeapType::eq;
+      case Type::i31ref:
+        return HeapType::i31;
     }
+    WASM_UNREACHABLE("Unexpected type");
+  } else {
+    auto* info = getTypeInfo(*this);
+    switch (info->kind) {
+      case TypeInfo::TupleKind:
+        break;
+      case TypeInfo::RefKind:
+        return info->ref.heapType;
+      case TypeInfo::RttKind:
+        return info->rtt.heapType;
+    }
+    WASM_UNREACHABLE("Unexpected type");
   }
-  WASM_UNREACHABLE("unexpected type");
 }
 
 Type Type::get(unsigned byteSize, bool float_) {
@@ -672,93 +656,90 @@ const Type& Type::operator[](size_t index) const {
   }
 }
 
-HeapType::HeapType(const HeapType& other) : kind(other.kind) {
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return;
-    case SignatureKind:
-      new (&signature) auto(other.signature);
-      return;
-    case StructKind:
-      new (&struct_) auto(other.struct_);
-      return;
-    case ArrayKind:
-      new (&array) auto(other.array);
-      return;
-  }
-  WASM_UNREACHABLE("unexpected kind");
+HeapType::HeapType(Signature signature) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(signature));
 }
 
-HeapType::~HeapType() {
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return;
-    case SignatureKind:
-      signature.~Signature();
-      return;
-    case StructKind:
-      struct_.~Struct();
-      return;
-    case ArrayKind:
-      array.~Array();
-      return;
+HeapType::HeapType(const Struct& struct_) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(struct_));
+}
+
+HeapType::HeapType(Struct&& struct_) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(std::move(struct_)));
+}
+
+HeapType::HeapType(Array array) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(array));
+}
+
+bool HeapType::isFunction() const {
+  if (isBasic()) {
+    return id == func;
+  } else {
+    return getHeapTypeInfo(*this)->isSignature();
   }
 }
 
-bool HeapType::operator==(const HeapType& other) const {
-  if (kind != other.kind) {
+bool HeapType::isSignature() const {
+  if (isBasic()) {
     return false;
+  } else {
+    return getHeapTypeInfo(*this)->isSignature();
   }
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return true;
-    case SignatureKind:
-      return signature == other.signature;
-    case StructKind:
-      return struct_ == other.struct_;
-    case ArrayKind:
-      return array == other.array;
+}
+
+bool HeapType::isStruct() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isStruct();
   }
-  WASM_UNREACHABLE("unexpected kind");
 }
 
 bool HeapType::operator<(const HeapType& other) const {
-  if (kind != other.kind) {
-    return kind < other.kind;
+  if (*this == other) {
+    return false;
+  }
+  if (isBasic() && other.isBasic()) {
+    return getBasic() < other.getBasic();
   }
-  if (isSignature()) {
-    return getSignature() < other.getSignature();
+  if (isBasic()) {
+    return true;
   }
-  if (isStruct()) {
-    return getStruct() < other.getStruct();
+  if (other.isBasic()) {
+    return false;
   }
-  if (isArray()) {
-    return getArray() < other.getArray();
+  return *getHeapTypeInfo(*this) < *getHeapTypeInfo(other);
+}
+
+bool HeapType::isArray() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isArray();
   }
-  WASM_UNREACHABLE("unimplemented type comparison");
 }
 
-HeapType& HeapType::operator=(const HeapType& other) {
-  if (&other != this) {
-    this->~HeapType();
-    new (this) auto(other);
+Signature HeapType::getSignature() const {
+  assert(isSignature());
+  return getHeapTypeInfo(*this)->signature;
+}
+
+const Struct& HeapType::getStruct() const {
+  assert(isStruct());
+  return getHeapTypeInfo(*this)->struct_;
+}
+
+Array HeapType::getArray() const {
+  assert(isArray());
+  return getHeapTypeInfo(*this)->array;
+}
+
+bool Signature::operator<(const Signature& other) const {
+  if (results != other.results) {
+    return results < other.results;
   }
-  return *this;
+  return params < other.params;
 }
 
 bool Field::operator<(const Field& other) const {
@@ -771,6 +752,13 @@ bool Field::operator<(const Field& other) const {
   return type < other.type;
 }
 
+bool Rtt::operator<(const Rtt& other) const {
+  if (depth != other.depth) {
+    return depth < other.depth;
+  }
+  return heapType < other.heapType;
+}
+
 namespace {
 
 std::ostream&
@@ -809,65 +797,41 @@ std::string HeapType::toString() const { return genericToString(*this); }
 
 std::string Rtt::toString() const { return genericToString(*this); }
 
-std::string TypeInfo::toString() const { return genericToString(*this); }
-
-bool Signature::operator<(const Signature& other) const {
-  if (results < other.results) {
-    return true;
-  } else if (other.results < results) {
-    return false;
-  } else {
-    return params < other.params;
-  }
-}
+std::ostream& operator<<(std::ostream&, TypeInfo);
+std::ostream& operator<<(std::ostream&, HeapTypeInfo);
 
 std::ostream& operator<<(std::ostream& os, Type type) {
   if (type.isBasic()) {
     switch (type.getBasic()) {
       case Type::none:
-        os << "none";
-        break;
+        return os << "none";
       case Type::unreachable:
-        os << "unreachable";
-        break;
+        return os << "unreachable";
       case Type::i32:
-        os << "i32";
-        break;
+        return os << "i32";
       case Type::i64:
-        os << "i64";
-        break;
+        return os << "i64";
       case Type::f32:
-        os << "f32";
-        break;
+        return os << "f32";
       case Type::f64:
-        os << "f64";
-        break;
+        return os << "f64";
       case Type::v128:
-        os << "v128";
-        break;
+        return os << "v128";
       case Type::funcref:
-        os << "funcref";
-        break;
+        return os << "funcref";
       case Type::externref:
-        os << "externref";
-        break;
+        return os << "externref";
       case Type::exnref:
-        os << "exnref";
-        break;
+        return os << "exnref";
       case Type::anyref:
-        os << "anyref";
-        break;
+        return os << "anyref";
       case Type::eqref:
-        os << "eqref";
-        break;
+        return os << "eqref";
       case Type::i31ref:
-        os << "i31ref";
-        break;
+        return os << "i31ref";
     }
-  } else {
-    os << *getTypeInfo(type);
   }
-  return os;
+  return os << *getTypeInfo(type);
 }
 
 std::ostream& operator<<(std::ostream& os, ParamType param) {
@@ -943,27 +907,23 @@ std::ostream& operator<<(std::ostream& os, Array array) {
 }
 
 std::ostream& operator<<(std::ostream& os, HeapType heapType) {
-  switch (heapType.kind) {
-    case wasm::HeapType::FuncKind:
-      return os << "func";
-    case wasm::HeapType::ExternKind:
-      return os << "extern";
-    case wasm::HeapType::AnyKind:
-      return os << "any";
-    case wasm::HeapType::EqKind:
-      return os << "eq";
-    case wasm::HeapType::I31Kind:
-      return os << "i31";
-    case wasm::HeapType::ExnKind:
-      return os << "exn";
-    case wasm::HeapType::SignatureKind:
-      return os << heapType.signature;
-    case wasm::HeapType::StructKind:
-      return os << heapType.struct_;
-    case wasm::HeapType::ArrayKind:
-      return os << heapType.array;
+  if (heapType.isBasic()) {
+    switch (heapType.getBasic()) {
+      case HeapType::func:
+        return os << "func";
+      case HeapType::ext:
+        return os << "extern";
+      case HeapType::exn:
+        return os << "exn";
+      case HeapType::any:
+        return os << "any";
+      case HeapType::eq:
+        return os << "eq";
+      case HeapType::i31:
+        return os << "i31";
+    }
   }
-  WASM_UNREACHABLE("unexpected kind");
+  return os << *getHeapTypeInfo(heapType);
 }
 
 std::ostream& operator<<(std::ostream& os, Rtt rtt) {
@@ -989,4 +949,117 @@ std::ostream& operator<<(std::ostream& os, TypeInfo info) {
   WASM_UNREACHABLE("unexpected kind");
 }
 
+std::ostream& operator<<(std::ostream& os, HeapTypeInfo info) {
+  switch (info.kind) {
+    case HeapTypeInfo::SignatureKind:
+      return os << info.signature;
+    case HeapTypeInfo::StructKind:
+      return os << info.struct_;
+    case HeapTypeInfo::ArrayKind:
+      return os << info.array;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
 } // namespace wasm
+
+namespace std {
+
+template<> class hash<wasm::TypeList> {
+public:
+  size_t operator()(const wasm::TypeList& types) const {
+    auto digest = wasm::hash(types.size());
+    for (auto type : types) {
+      wasm::rehash(digest, type);
+    }
+    return digest;
+  }
+};
+
+template<> class hash<wasm::FieldList> {
+public:
+  size_t operator()(const wasm::FieldList& fields) const {
+    auto digest = wasm::hash(fields.size());
+    for (auto field : fields) {
+      wasm::rehash(digest, field);
+    }
+    return digest;
+  }
+};
+
+size_t hash<wasm::TypeInfo>::operator()(const wasm::TypeInfo& info) const {
+  auto digest = wasm::hash(info.kind);
+  switch (info.kind) {
+    case wasm::TypeInfo::TupleKind:
+      wasm::rehash(digest, info.tuple);
+      return digest;
+    case wasm::TypeInfo::RefKind:
+      wasm::rehash(digest, info.ref.heapType);
+      wasm::rehash(digest, info.ref.nullable);
+      return digest;
+    case wasm::TypeInfo::RttKind:
+      wasm::rehash(digest, info.rtt);
+      return digest;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+size_t hash<wasm::HeapTypeInfo>::
+operator()(const wasm::HeapTypeInfo& info) const {
+  auto digest = wasm::hash(info.kind);
+  switch (info.kind) {
+    case wasm::HeapTypeInfo::SignatureKind:
+      wasm::rehash(digest, info.signature);
+      return digest;
+    case wasm::HeapTypeInfo::StructKind:
+      wasm::rehash(digest, info.struct_);
+      return digest;
+    case wasm::HeapTypeInfo::ArrayKind:
+      wasm::rehash(digest, info.array);
+      return digest;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+size_t hash<wasm::Type>::operator()(const wasm::Type& type) const {
+  return wasm::hash(type.getID());
+}
+
+size_t hash<wasm::Tuple>::operator()(const wasm::Tuple& tuple) const {
+  return wasm::hash(tuple.types);
+}
+
+size_t hash<wasm::Signature>::operator()(const wasm::Signature& sig) const {
+  auto digest = wasm::hash(sig.params);
+  wasm::rehash(digest, sig.results);
+  return digest;
+}
+
+size_t hash<wasm::Field>::operator()(const wasm::Field& field) const {
+  auto digest = wasm::hash(field.type);
+  wasm::rehash(digest, field.packedType);
+  wasm::rehash(digest, field.mutable_);
+  // Note that the name is not hashed here - it is pure metadata for printing
+  // purposes only.
+  return digest;
+}
+
+size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
+  return wasm::hash(struct_.fields);
+}
+
+size_t hash<wasm::Array>::operator()(const wasm::Array& array) const {
+  return wasm::hash(array.element);
+}
+
+size_t hash<wasm::HeapType>::operator()(const wasm::HeapType& heapType) const {
+  return wasm::hash(heapType.getID());
+}
+
+size_t hash<wasm::Rtt>::operator()(const wasm::Rtt& rtt) const {
+  auto digest = wasm::hash(rtt.depth);
+  wasm::rehash(digest, rtt.heapType);
+  return digest;
+}
+
+} // namespace std