Add new compound Rtt type (#3076)

Extends compound types introduced in #3012 with a representation of `Rtt`s as described in the GC proposal, by also introducing the concept of a `HeapType` shared between `TypeInfo` and `Rtt`. Again, this should be a non-functional change since `Rtt`s are not used anywhere yet. Subtyping rules and updating the `xref` aliases is left for future work.

2 files changed, 311 insertions, 137 deletions

diff --git a/src/wasm-type.h b/src/wasm-type.h
index cee8dae03..8a9e58ec9 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -31,13 +31,6 @@
 
 namespace wasm {
 
-struct Tuple;
-struct Signature;
-struct Struct;
-struct Array;
-
-typedef std::vector<class Type> TypeList;
-
 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 `BasicID`
@@ -73,16 +66,14 @@ public:
   Type(std::initializer_list<Type>);
 
   // Construct from tuple description
-  explicit Type(const Tuple&);
-
-  // Construct from signature description
-  explicit Type(const Signature, bool nullable);
+  explicit Type(const struct Tuple&);
 
-  // Construct from struct description
-  explicit Type(const Struct&, bool nullable);
+  // 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);
 
-  // Construct from array description
-  explicit Type(const Array&, bool nullable);
+  // Construct from rtt description
+  explicit Type(const struct Rtt&);
 
   // Predicates
   //                 Compound Concrete
@@ -96,16 +87,18 @@ public:
   // │ f32         ║ x │   │ x │ x │   F   │ │  F_loat
   // │ f64         ║ x │   │ x │ x │   F   │ │  V_ector
   // │ v128        ║ x │   │ x │ x │     V │ ┘
-  // ├─────────────╫───┼───┼───┼───┤───────┤
-  // │ funcref     ║ x │   │ x │ x │ f     │ ┐ Ref
-  // │ externref   ║ x │   │ x │ x │       │ │  f_unc
-  // │ nullref     ║ x │   │ x │ x │       │ │
-  // │ exnref      ║ x │   │ x │ x │       │ │
-  // ├─────────────╫───┼───┼───┼───┤───────┤ │
-  // │ Signature   ║   │ x │ x │ x │ f     │ │
-  // │ Struct      ║   │ x │ x │ x │       │ │
-  // │ Array       ║   │ x │ x │ x │       │ ┘
+  // ├─ Aliases ───╫───┼───┼───┼───┤───────┤
+  // │ funcref     ║ x │   │ x │ x │ f  n  │ ┐ Ref
+  // │ externref   ║ x │   │ x │ x │ f? n  │ │  f_unc, n_ullable
+  // │ anyref      ║ x │   │ x │ x │ f? n  │ │ ┐
+  // │ eqref       ║ x │   │ x │ x │    n  │ │ │ TODO (GC)
+  // │ i31ref      ║ x │   │ x │ x │       │ │ ┘
+  // │ nullref     ║ x │   │ x │ x │ f? n  │ │ ◄ TODO (removed)
+  // │ exnref      ║ x │   │ x │ x │    n  │ │
+  // ├─ Compound ──╫───┼───┼───┼───┤───────┤ │
+  // │ Ref         ║   │ x │ x │ x │ f? n? │◄┘
   // │ 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; }
@@ -118,6 +111,7 @@ public:
   bool isSingle() const { return isConcrete() && !isTuple(); }
   bool isRef() const;
   bool isNullable() const;
+  bool isRtt() const;
 
 private:
   template<bool (Type::*pred)() const> bool hasPredicate() {
@@ -227,6 +221,8 @@ struct ResultType {
   std::string toString() const;
 };
 
+typedef std::vector<Type> TypeList;
+
 struct Tuple {
   TypeList types;
   Tuple() : types() {}
@@ -303,6 +299,72 @@ struct Array {
   std::string toString() const;
 };
 
+struct HeapType {
+  enum Kind {
+    FuncKind,
+    ExternKind,
+    AnyKind,
+    EqKind,
+    I31Kind,
+    ExnKind,
+    _last_basic_kind = ExnKind,
+    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 isSignature() const { return kind == SignatureKind; }
+  Signature getSignature() const {
+    assert(isSignature() && "Not a signature");
+    return signature;
+  }
+  bool isStruct() const { return kind == StructKind; }
+  Struct getStruct() const {
+    assert(isStruct() && "Not a struct");
+    return struct_;
+  }
+  bool isArray() const { return kind == ArrayKind; }
+  Array getArray() const {
+    assert(isArray() && "Not an array");
+    return array;
+  }
+
+  bool operator==(const HeapType& other) const;
+  bool operator!=(const HeapType& other) const { return !(*this == other); }
+  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)) {}
+  bool operator==(const Rtt& other) const {
+    return depth == other.depth && heapType == other.heapType;
+  }
+  bool operator!=(const Rtt& other) const { return !(*this == other); }
+  std::string toString() const;
+};
+
 std::ostream& operator<<(std::ostream&, Type);
 std::ostream& operator<<(std::ostream&, ParamType);
 std::ostream& operator<<(std::ostream&, ResultType);
@@ -311,6 +373,8 @@ std::ostream& operator<<(std::ostream&, Signature);
 std::ostream& operator<<(std::ostream&, Field);
 std::ostream& operator<<(std::ostream&, Struct);
 std::ostream& operator<<(std::ostream&, Array);
+std::ostream& operator<<(std::ostream&, HeapType);
+std::ostream& operator<<(std::ostream&, Rtt);
 
 } // namespace wasm
 
@@ -340,6 +404,14 @@ template<> class hash<wasm::Array> {
 public:
   size_t operator()(const wasm::Array&) const;
 };
+template<> class hash<wasm::HeapType> {
+public:
+  size_t operator()(const wasm::HeapType&) const;
+};
+template<> class hash<wasm::Rtt> {
+public:
+  size_t operator()(const wasm::Rtt&) const;
+};
 
 } // namespace std
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 5247ebb6f..e46cb5886 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -28,48 +28,40 @@
 namespace wasm {
 
 struct TypeInfo {
-  enum Kind { TupleKind, SignatureRefKind, StructRefKind, ArrayRefKind } kind;
-  struct SignatureRef {
-    Signature signature;
-    bool nullable;
-  };
-  struct StructRef {
-    Struct struct_;
-    bool nullable;
-  };
-  struct ArrayRef {
-    Array array;
+  enum Kind {
+    TupleKind,
+    RefKind,
+    RttKind,
+  } kind;
+  struct Ref {
+    HeapType heapType;
     bool nullable;
   };
   union {
     Tuple tuple;
-    SignatureRef signatureRef;
-    StructRef structRef;
-    ArrayRef arrayRef;
+    Ref ref;
+    Rtt rtt;
   };
 
   TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {}
   TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {}
-  TypeInfo(const Signature& signature, bool nullable)
-    : kind(SignatureRefKind), signatureRef{signature, nullable} {}
-  TypeInfo(const Struct& struct_, bool nullable)
-    : kind(StructRefKind), structRef{struct_, nullable} {}
-  TypeInfo(const Array& array, bool nullable)
-    : kind(ArrayRefKind), arrayRef{array, nullable} {}
+  TypeInfo(const 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 SignatureRefKind:
-        new (&signatureRef) auto(other.signatureRef);
+      case RefKind:
+        new (&ref) auto(other.ref);
         return;
-      case StructRefKind:
-        new (&structRef) auto(other.structRef);
-        return;
-      case ArrayRefKind:
-        new (&arrayRef) auto(other.arrayRef);
+      case RttKind:
+        new (&rtt) auto(other.rtt);
         return;
     }
     WASM_UNREACHABLE("unexpected kind");
@@ -80,16 +72,12 @@ struct TypeInfo {
         tuple.~Tuple();
         return;
       }
-      case SignatureRefKind: {
-        signatureRef.~SignatureRef();
-        return;
-      }
-      case StructRefKind: {
-        structRef.~StructRef();
+      case RefKind: {
+        ref.~Ref();
         return;
       }
-      case ArrayRefKind: {
-        arrayRef.~ArrayRef();
+      case RttKind: {
+        rtt.~Rtt();
         return;
       }
     }
@@ -97,23 +85,10 @@ struct TypeInfo {
   }
 
   constexpr bool isTuple() const { return kind == TupleKind; }
-  constexpr bool isSignatureRef() const { return kind == SignatureRefKind; }
-  constexpr bool isStructRef() const { return kind == StructRefKind; }
-  constexpr bool isArrayRef() const { return kind == ArrayRefKind; }
+  constexpr bool isRef() const { return kind == RefKind; }
+  constexpr bool isRtt() const { return kind == RttKind; }
 
-  bool isNullable() const {
-    switch (kind) {
-      case TupleKind:
-        return false;
-      case SignatureRefKind:
-        return signatureRef.nullable;
-      case StructRefKind:
-        return structRef.nullable;
-      case ArrayRefKind:
-        return arrayRef.nullable;
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
+  bool isNullable() const { return kind == RefKind && ref.nullable; }
 
   bool operator==(const TypeInfo& other) const {
     if (kind != other.kind) {
@@ -122,15 +97,11 @@ struct TypeInfo {
     switch (kind) {
       case TupleKind:
         return tuple == other.tuple;
-      case SignatureRefKind:
-        return signatureRef.nullable == other.signatureRef.nullable &&
-               signatureRef.signature == other.signatureRef.signature;
-      case StructRefKind:
-        return structRef.nullable == other.structRef.nullable &&
-               structRef.struct_ == other.structRef.struct_;
-      case ArrayRefKind:
-        return arrayRef.nullable == other.arrayRef.nullable &&
-               arrayRef.array == other.arrayRef.array;
+      case RefKind:
+        return ref.heapType == other.ref.heapType &&
+               ref.nullable == other.ref.nullable;
+      case RttKind:
+        return rtt == other.rtt;
     }
     WASM_UNREACHABLE("unexpected kind");
   }
@@ -180,22 +151,16 @@ public:
     auto digest = wasm::hash(info.kind);
     switch (info.kind) {
       case wasm::TypeInfo::TupleKind: {
-        wasm::rehash(digest, info.tuple.types);
-        return digest;
-      }
-      case wasm::TypeInfo::SignatureRefKind: {
-        wasm::rehash(digest, info.signatureRef.signature);
-        wasm::rehash(digest, info.signatureRef.nullable);
+        wasm::rehash(digest, info.tuple);
         return digest;
       }
-      case wasm::TypeInfo::StructRefKind: {
-        wasm::rehash(digest, info.structRef.struct_);
-        wasm::rehash(digest, info.structRef.nullable);
+      case wasm::TypeInfo::RefKind: {
+        wasm::rehash(digest, info.ref.heapType);
+        wasm::rehash(digest, info.ref.nullable);
         return digest;
       }
-      case wasm::TypeInfo::ArrayRefKind: {
-        wasm::rehash(digest, info.arrayRef.array);
-        wasm::rehash(digest, info.arrayRef.nullable);
+      case wasm::TypeInfo::RttKind: {
+        wasm::rehash(digest, info.rtt);
         return digest;
       }
     }
@@ -225,15 +190,42 @@ size_t hash<wasm::Field>::operator()(const wasm::Field& field) const {
 }
 
 size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
-  auto digest = wasm::hash(0);
-  wasm::rehash(digest, struct_.fields);
-  return digest;
+  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 {
+  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;
+  }
+  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;
+}
+
 } // namespace std
 
 namespace wasm {
@@ -261,9 +253,16 @@ std::unordered_map<TypeInfo, uintptr_t> indices = {
   {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({Type::nullref}), Type::nullref},
+  {TypeInfo(HeapType(HeapType::ExternKind), true), Type::externref},
+  // TODO (GC): Add canonical ids
+  // * `(ref null any) == anyref`
+  // * `(ref null eq) == eqref`
+  // * `(ref i31) == i31ref`
+  {TypeInfo({Type::nullref}), Type::nullref}, // TODO (removed)
   {TypeInfo({Type::exnref}), Type::exnref},
+  {TypeInfo(HeapType(HeapType::ExnKind), true), Type::exnref},
 };
 
 } // anonymous namespace
@@ -306,23 +305,31 @@ Type::Type(const Tuple& tuple) {
   id = canonicalize(TypeInfo(tuple));
 }
 
-Type::Type(const Signature signature, bool nullable) {
-  id = canonicalize(TypeInfo(signature, nullable));
-}
-
-Type::Type(const Struct& struct_, bool nullable) {
+Type::Type(const HeapType& heapType, bool nullable) {
 #ifndef NDEBUG
-  for (Field f : struct_.fields) {
-    assert(f.type.isSingle());
+  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());
+      }
+      break;
+    case HeapType::ArrayKind:
+      assert(heapType.array.element.type.isSingle());
+      break;
   }
 #endif
-  id = canonicalize(TypeInfo(struct_, nullable));
+  id = canonicalize(TypeInfo(heapType, nullable));
 }
 
-Type::Type(const Array& array, bool nullable) {
-  assert(array.element.type.isSingle());
-  id = canonicalize(TypeInfo(array, nullable));
-}
+Type::Type(const Rtt& rtt) { id = canonicalize(TypeInfo(rtt)); }
 
 bool Type::isTuple() const {
   if (isBasic()) {
@@ -336,15 +343,7 @@ bool Type::isRef() const {
   if (isBasic()) {
     return id >= funcref && id <= exnref;
   } else {
-    switch (getTypeInfo(*this)->kind) {
-      case TypeInfo::TupleKind:
-        return false;
-      case TypeInfo::SignatureRefKind:
-      case TypeInfo::StructRefKind:
-      case TypeInfo::ArrayRefKind:
-        return true;
-    }
-    WASM_UNREACHABLE("unexpected kind");
+    return getTypeInfo(*this)->isRef();
   }
 }
 
@@ -356,6 +355,14 @@ bool Type::isNullable() const {
   }
 }
 
+bool Type::isRtt() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getTypeInfo(*this)->isRtt();
+  }
+}
+
 bool Type::operator<(const Type& other) const {
   return std::lexicographical_compare(begin(),
                                       end(),
@@ -547,6 +554,80 @@ 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() {
+  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;
+  }
+}
+
+bool HeapType::operator==(const HeapType& other) const {
+  if (kind != other.kind) {
+    return false;
+  }
+  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;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+HeapType& HeapType::operator=(const HeapType& other) {
+  if (&other != this) {
+    this->~HeapType();
+    new (this) auto(other);
+  }
+  return *this;
+}
+
 namespace {
 
 std::ostream&
@@ -581,6 +662,10 @@ std::string Struct::toString() const { return genericToString(*this); }
 
 std::string Array::toString() const { return genericToString(*this); }
 
+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 {
@@ -708,31 +793,48 @@ std::ostream& operator<<(std::ostream& os, Array array) {
   return os << "(array " << array.element << ")";
 }
 
+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;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+std::ostream& operator<<(std::ostream& os, Rtt rtt) {
+  return os << "(rtt " << rtt.depth << " " << rtt.heapType << ")";
+}
+
 std::ostream& operator<<(std::ostream& os, TypeInfo info) {
   switch (info.kind) {
     case TypeInfo::TupleKind: {
       return os << info.tuple;
     }
-    case TypeInfo::SignatureRefKind: {
-      os << "(ref ";
-      if (info.signatureRef.nullable) {
-        os << "null ";
-      }
-      return os << info.signatureRef.signature << ")";
-    }
-    case TypeInfo::StructRefKind: {
+    case TypeInfo::RefKind: {
       os << "(ref ";
-      if (info.structRef.nullable) {
+      if (info.ref.nullable) {
         os << "null ";
       }
-      return os << info.structRef.struct_ << ")";
+      return os << info.ref.heapType << ")";
     }
-    case TypeInfo::ArrayRefKind: {
-      os << "(ref ";
-      if (info.arrayRef.nullable) {
-        os << "null ";
-      }
-      return os << info.arrayRef.array << ")";
+    case TypeInfo::RttKind: {
+      return os << info.rtt;
     }
   }
   WASM_UNREACHABLE("unexpected kind");