[GC] Support reading and writing of Struct and Array types (#3423)

This adds support in the text and binary format handling, which allows us
to have a full test of reading and writing the types.

This also adds a "name" field to struct fields, which the text format supports.

7 files changed, 246 insertions, 118 deletions

diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index ba3981e21..711c1b604 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -80,59 +80,6 @@ static std::ostream& operator<<(std::ostream& o, const SExprType& localType) {
   return o;
 }
 
-// Wrapper for printing signature names
-struct SigName {
-  Signature sig;
-  SigName(Signature sig) : sig(sig) {}
-};
-
-std::ostream& operator<<(std::ostream& os, SigName sigName) {
-  std::function<void(Type)> printType = [&](Type type) {
-    if (type == Type::none) {
-      os << "none";
-    } else {
-      auto sep = "";
-      for (const auto& t : type) {
-        os << sep;
-        sep = "_";
-        if (t.isRef()) {
-          auto heapType = t.getHeapType();
-          if (heapType.isSignature()) {
-            auto sig = heapType.getSignature();
-            os << "ref";
-            if (t.isNullable()) {
-              os << "_null";
-            }
-            os << "[";
-            auto subsep = "";
-            for (auto s : sig.params) {
-              os << subsep;
-              subsep = "_";
-              printType(s);
-            }
-            os << "_->_";
-            subsep = "";
-            for (auto s : sig.results) {
-              os << subsep;
-              subsep = "_";
-              printType(s);
-            }
-            os << "]";
-            continue;
-          }
-        }
-        os << t;
-      }
-    }
-  };
-
-  os << '$';
-  printType(sigName.sig.params);
-  os << "_=>_";
-  printType(sigName.sig.results);
-  return os;
-}
-
 // Wrapper for printing a type when we try to print the type name as much as
 // possible. For example, for a signature we will print the signature's name,
 // not its contents.
@@ -141,11 +88,82 @@ struct TypeName {
   TypeName(Type type) : type(type) {}
 };
 
-struct HeapTypeName {
-  HeapType type;
-  HeapTypeName(HeapType type) : type(type) {}
+struct ResultTypeName {
+  Type type;
+  ResultTypeName(Type type) : type(type) {}
 };
 
+static void
+printHeapTypeName(std::ostream& os, HeapType type, bool first = true);
+
+static void printTypeName(std::ostream& os, Type type) {
+  if (type.isBasic()) {
+    os << type;
+    return;
+  }
+  if (type.isTuple()) {
+    auto sep = "";
+    for (auto t : type) {
+      os << sep;
+      sep = "_";
+      printTypeName(os, t);
+    }
+  } else if (type.isRef()) {
+    os << "ref";
+    if (type.isNullable()) {
+      os << "?";
+    }
+    os << "|";
+    printHeapTypeName(os, type.getHeapType(), false);
+    os << "|";
+  } else {
+    WASM_UNREACHABLE("unsupported print type");
+  }
+}
+
+static void printHeapTypeName(std::ostream& os, HeapType type, bool first) {
+  if (type.isBasic()) {
+    os << type;
+    return;
+  }
+  if (first) {
+    os << '$';
+  }
+  if (type.isSignature()) {
+    auto sig = type.getSignature();
+    printTypeName(os, sig.params);
+    if (first) {
+      os << "_=>_";
+    } else {
+      os << "_->_";
+    }
+    printTypeName(os, sig.results);
+  } else if (type.isStruct()) {
+    auto struct_ = type.getStruct();
+    os << "{";
+    auto sep = "";
+    for (auto& field : struct_.fields) {
+      os << sep;
+      sep = "_";
+      if (field.mutable_) {
+        os << "mut:";
+      }
+      printTypeName(os, field.type);
+    }
+    os << "}";
+  } else if (type.isArray()) {
+    os << "[";
+    auto element = type.getArray().element;
+    if (element.mutable_) {
+      os << "mut:";
+    }
+    printTypeName(os, element.type);
+    os << "]";
+  } else {
+    os << type;
+  }
+}
+
 std::ostream& operator<<(std::ostream& os, TypeName typeName) {
   auto type = typeName.type;
   if (type.isRef() && !type.isBasic()) {
@@ -153,25 +171,29 @@ std::ostream& operator<<(std::ostream& os, TypeName typeName) {
     if (type.isNullable()) {
       os << "null ";
     }
-    auto heapType = type.getHeapType();
-    if (heapType.isSignature()) {
-      os << SigName(heapType.getSignature());
-    } else {
-      os << heapType;
-    }
+    printHeapTypeName(os, type.getHeapType());
     os << ')';
     return os;
   }
   return os << SExprType(typeName.type);
 }
 
-std::ostream& operator<<(std::ostream& os, HeapTypeName typeName) {
+std::ostream& operator<<(std::ostream& os, ResultTypeName typeName) {
   auto type = typeName.type;
-  if (type.isSignature()) {
-    os << SigName(type.getSignature());
+  os << "(result ";
+  if (type.isTuple()) {
+    // Tuple types are not printed in parens, we can just emit them one after
+    // the other in the same list as the "result".
+    auto sep = "";
+    for (auto t : type) {
+      os << sep;
+      sep = " ";
+      os << TypeName(t);
+    }
   } else {
-    os << type;
+    os << TypeName(type);
   }
+  os << ')';
   return os;
 }
 
@@ -250,7 +272,8 @@ struct PrintExpressionContents
     } else {
       printMedium(o, "call_indirect (type ");
     }
-    o << SigName(curr->sig) << ')';
+    printHeapTypeName(o, curr->sig);
+    o << ')';
   }
   void visitLocalGet(LocalGet* curr) {
     printMedium(o, "local.get ");
@@ -2390,11 +2413,40 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     }
     o << ")";
   }
+  void handleFieldBody(const Field& field) {
+    if (field.mutable_) {
+      o << "(mut ";
+    }
+    o << TypeName(field.type);
+    if (field.mutable_) {
+      o << ')';
+    }
+  }
+  void handleArray(const Array& curr) {
+    o << "(array ";
+    handleFieldBody(curr.element);
+    o << ')';
+  }
+  void handleStruct(const Struct& curr) {
+    o << "(struct ";
+    auto sep = "";
+    for (auto field : curr.fields) {
+      o << sep << "(field ";
+      handleFieldBody(field);
+      o << ')';
+      sep = " ";
+    }
+    o << ')';
+  }
   void handleHeapType(HeapType type) {
     if (type.isSignature()) {
       handleSignature(type.getSignature());
+    } else if (type.isArray()) {
+      handleArray(type.getArray());
+    } else if (type.isStruct()) {
+      handleStruct(type.getStruct());
     } else {
-      WASM_UNREACHABLE("unsupported heap type");
+      o << type;
     }
   }
   void visitExport(Export* curr) {
@@ -2505,7 +2557,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     }
     if (curr->sig.results != Type::none) {
       o << maybeSpace;
-      o << ResultType(curr->sig.results);
+      o << ResultTypeName(curr->sig.results);
     }
     incIndent();
     for (size_t i = curr->getVarIndexBase(); i < curr->getNumLocals(); i++) {
@@ -2731,7 +2783,8 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
       doIndent(o, indent);
       o << '(';
       printMedium(o, "type") << ' ';
-      o << HeapTypeName(type) << ' ';
+      printHeapTypeName(o, type);
+      o << ' ';
       handleHeapType(type);
       o << ")" << maybeNewLine;
     }
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index d7257f560..d22205a0a 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -355,7 +355,9 @@ enum EncodedType {
   // exception reference type
   exnref = -0x18, // 0x68
   // func_type form
-  Func = -0x20, // 0x60
+  Func = -0x20,   // 0x60
+  Struct = -0x21, // 0x5f
+  Array = -0x22,  // 0x5e
   // block_type
   Empty = -0x40 // 0x40
 };
@@ -1125,7 +1127,7 @@ public:
   uint32_t getFunctionIndex(Name name) const;
   uint32_t getGlobalIndex(Name name) const;
   uint32_t getEventIndex(Name name) const;
-  uint32_t getTypeIndex(Signature sig) const;
+  uint32_t getTypeIndex(HeapType type) const;
 
   void writeFunctionTableDeclaration();
   void writeTableElements();
@@ -1170,6 +1172,7 @@ public:
 
   void writeType(Type type);
   void writeHeapType(HeapType type);
+  void writeField(const Field& field);
 
 private:
   Module* wasm;
@@ -1251,6 +1254,7 @@ public:
   uint64_t getUPtrLEB();
   Type getType();
   HeapType getHeapType();
+  Field getField();
   Type getConcreteType();
   Name getInlineString();
   void verifyInt8(int8_t x);
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 88237249a..7e20ff4c9 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -262,8 +262,7 @@ private:
   Expression* makeRttCanon(Element& s);
   Expression* makeRttSub(Element& s);
   Expression* makeStructNew(Element& s, bool default_);
-  Expression* makeStructGet(Element& s);
-  Expression* makeStructGet(Element& s, bool signed_);
+  Expression* makeStructGet(Element& s, bool signed_ = false);
   Expression* makeStructSet(Element& s);
   Expression* makeArrayNew(Element& s, bool default_);
   Expression* makeArrayGet(Element& s);
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 39ec1640e..98c6c70ed 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -17,6 +17,7 @@
 #ifndef wasm_wasm_type_h
 #define wasm_wasm_type_h
 
+#include "support/name.h"
 #include "wasm-features.h"
 #include <ostream>
 #include <vector>
@@ -285,11 +286,12 @@ struct Field {
     i16,
   } packedType; // applicable iff type=i32
   bool mutable_;
+  Name name;
 
-  Field(Type type, bool mutable_ = false)
-    : type(type), packedType(not_packed), mutable_(mutable_) {}
-  Field(PackedType packedType, bool mutable_ = false)
-    : type(Type::i32), packedType(packedType), mutable_(mutable_) {}
+  Field(Type type, bool mutable_, Name name = Name())
+    : type(type), packedType(not_packed), mutable_(mutable_), name(name) {}
+  Field(PackedType packedType, bool mutable_, Name name = Name())
+    : type(Type::i32), packedType(packedType), mutable_(mutable_), name(name) {}
 
   constexpr bool isPacked() const {
     if (packedType != not_packed) {
@@ -300,6 +302,8 @@ struct Field {
   }
 
   bool operator==(const Field& other) const {
+    // Note that the name is not checked here - it is pure metadata for printing
+    // purposes only.
     return type == other.type && packedType == other.packedType &&
            mutable_ == other.mutable_;
   }
@@ -362,6 +366,7 @@ struct HeapType {
   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");
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 54e417b8c..3aace6721 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -226,6 +226,16 @@ void WasmBinaryWriter::writeTypes() {
           writeType(type);
         }
       }
+    } else if (type.isStruct()) {
+      o << S32LEB(BinaryConsts::EncodedType::Struct);
+      auto fields = type.getStruct().fields;
+      o << U32LEB(fields.size());
+      for (const auto& field : fields) {
+        writeField(field);
+      }
+    } else if (type.isArray()) {
+      o << S32LEB(BinaryConsts::EncodedType::Array);
+      writeField(type.getArray().element);
     } else {
       WASM_UNREACHABLE("TODO GC type writing");
     }
@@ -495,11 +505,11 @@ uint32_t WasmBinaryWriter::getEventIndex(Name name) const {
   return it->second;
 }
 
-uint32_t WasmBinaryWriter::getTypeIndex(Signature sig) const {
-  auto it = typeIndices.find(sig);
+uint32_t WasmBinaryWriter::getTypeIndex(HeapType type) const {
+  auto it = typeIndices.find(type);
 #ifndef NDEBUG
   if (it == typeIndices.end()) {
-    std::cout << "Missing signature: " << sig << '\n';
+    std::cout << "Missing type: " << type << '\n';
     assert(0);
   }
 #endif
@@ -963,18 +973,14 @@ void WasmBinaryWriter::finishUp() {
 }
 
 void WasmBinaryWriter::writeType(Type type) {
-  if (type.isRef()) {
-    auto heapType = type.getHeapType();
-    // TODO: fully handle non-signature reference types (GC), and in reading
-    if (heapType.isSignature()) {
-      if (type.isNullable()) {
-        o << S32LEB(BinaryConsts::EncodedType::nullable);
-      } else {
-        o << S32LEB(BinaryConsts::EncodedType::nonnullable);
-      }
-      writeHeapType(heapType);
-      return;
+  if (type.isRef() && !type.isBasic()) {
+    if (type.isNullable()) {
+      o << S32LEB(BinaryConsts::EncodedType::nullable);
+    } else {
+      o << S32LEB(BinaryConsts::EncodedType::nonnullable);
     }
+    writeHeapType(type.getHeapType());
+    return;
   }
   int ret = 0;
   TODO_SINGLE_COMPOUND(type);
@@ -1023,9 +1029,8 @@ void WasmBinaryWriter::writeType(Type type) {
 }
 
 void WasmBinaryWriter::writeHeapType(HeapType type) {
-  if (type.isSignature()) {
-    auto sig = type.getSignature();
-    o << S32LEB(getTypeIndex(sig));
+  if (type.isSignature() || type.isStruct() || type.isArray()) {
+    o << S32LEB(getTypeIndex(type));
     return;
   }
   int ret = 0;
@@ -1056,6 +1061,11 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
   o << S32LEB(ret); // TODO: Actually encoded as s33
 }
 
+void WasmBinaryWriter::writeField(const Field& field) {
+  writeType(field.type);
+  o << U32LEB(field.mutable_);
+}
+
 // reader
 
 bool WasmBinaryBuilder::hasDWARFSections() {
@@ -1397,6 +1407,12 @@ HeapType WasmBinaryBuilder::getHeapType() {
   WASM_UNREACHABLE("unexpected type");
 }
 
+Field WasmBinaryBuilder::getField() {
+  auto type = getConcreteType();
+  auto mutable_ = getU32LEB();
+  return Field(type, mutable_);
+}
+
 Type WasmBinaryBuilder::getConcreteType() {
   auto type = getType();
   if (!type.isConcrete()) {
@@ -1493,23 +1509,34 @@ void WasmBinaryBuilder::readTypes() {
   BYN_TRACE("num: " << numTypes << std::endl);
   for (size_t i = 0; i < numTypes; i++) {
     BYN_TRACE("read one\n");
-    std::vector<Type> params;
-    std::vector<Type> results;
     auto form = getS32LEB();
-    if (form != BinaryConsts::EncodedType::Func) {
-      throwError("bad signature form " + std::to_string(form));
-    }
-    size_t numParams = getU32LEB();
-    BYN_TRACE("num params: " << numParams << std::endl);
-    for (size_t j = 0; j < numParams; j++) {
-      params.push_back(getConcreteType());
-    }
-    auto numResults = getU32LEB();
-    BYN_TRACE("num results: " << numResults << std::endl);
-    for (size_t j = 0; j < numResults; j++) {
-      results.push_back(getConcreteType());
+    if (form == BinaryConsts::EncodedType::Func) {
+      std::vector<Type> params;
+      std::vector<Type> results;
+      size_t numParams = getU32LEB();
+      BYN_TRACE("num params: " << numParams << std::endl);
+      for (size_t j = 0; j < numParams; j++) {
+        params.push_back(getConcreteType());
+      }
+      auto numResults = getU32LEB();
+      BYN_TRACE("num results: " << numResults << std::endl);
+      for (size_t j = 0; j < numResults; j++) {
+        results.push_back(getConcreteType());
+      }
+      types.emplace_back(Signature(Type(params), Type(results)));
+    } else if (form == BinaryConsts::EncodedType::Struct) {
+      FieldList fields;
+      size_t numFields = getU32LEB();
+      BYN_TRACE("num fields: " << numFields << std::endl);
+      for (size_t j = 0; j < numFields; j++) {
+        fields.push_back(getField());
+      }
+      types.emplace_back(Struct(fields));
+    } else if (form == BinaryConsts::EncodedType::Array) {
+      types.emplace_back(Array(getField()));
+    } else {
+      throwError("bad type form " + std::to_string(form));
     }
-    types.emplace_back(Signature(Type(params), Type(results)));
   }
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 47ef33371..c5296aec3 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -23,6 +23,7 @@
 #include "ir/branch-utils.h"
 #include "shared-constants.h"
 #include "wasm-binary.h"
+#include "wasm-builder.h"
 
 #define abort_on(str)                                                          \
   { throw ParseException(std::string("abort_on ") + str); }
@@ -48,6 +49,8 @@ int unhex(char c) {
 
 namespace wasm {
 
+static Name STRUCT("struct"), FIELD("field"), ARRAY("array");
+
 static Address getAddress(const Element* s) { return atoll(s->c_str()); }
 
 static void
@@ -61,6 +64,10 @@ static bool elementStartsWith(Element& s, IString str) {
   return s.isList() && s.size() > 0 && s[0]->isStr() && s[0]->str() == str;
 }
 
+static bool elementStartsWith(Element* s, IString str) {
+  return elementStartsWith(*s, str);
+}
+
 Element::List& Element::list() {
   if (!isList()) {
     throw ParseException("expected list", line, col);
@@ -908,7 +915,7 @@ Type SExpressionWasmBuilder::elementToType(Element& s) {
   }
   auto& list = s.list();
   auto size = list.size();
-  if (size > 0 && elementStartsWith(s, REF)) {
+  if (elementStartsWith(s, REF)) {
     // It's a reference. It should be in the form
     //   (ref $name)
     // or
@@ -2129,13 +2136,6 @@ Expression* SExpressionWasmBuilder::makeStructNew(Element& s, bool default_) {
   return ret;
 }
 
-Expression* SExpressionWasmBuilder::makeStructGet(Element& s) {
-  auto ret = allocator.alloc<StructGet>();
-  WASM_UNREACHABLE("TODO (gc): struct.get");
-  ret->finalize();
-  return ret;
-}
-
 Expression* SExpressionWasmBuilder::makeStructGet(Element& s, bool signed_) {
   auto ret = allocator.alloc<StructGet>();
   WASM_UNREACHABLE("TODO (gc): struct.get_s/u");
@@ -2790,6 +2790,44 @@ HeapType SExpressionWasmBuilder::parseHeapType(Element& s) {
     }
     return Signature(Type(params), Type(results));
   }
+  // It's a struct or an array.
+  auto parseField = [&](Element* t) {
+    bool mutable_ = false;
+    if (t->isStr()) {
+      // t is a simple string name like "i32"
+      return Field(elementToType(*t), mutable_);
+    }
+    // t is a list, containing either
+    //   TYPE
+    // or
+    //   (field TYPE)
+    // or
+    //   (field $name TYPE)
+    Name name;
+    if (elementStartsWith(t, FIELD)) {
+      if (t->size() == 3) {
+        name = (*t)[1]->str();
+      }
+      t = (*t)[t->size() - 1];
+    }
+    // The element may also be (mut (..)).
+    if (elementStartsWith(t, MUT)) {
+      mutable_ = true;
+      t = (*t)[1];
+    }
+    // Otherwise it's an arbitrary type.
+    return Field(elementToType(*t), mutable_, name);
+  };
+  if (elementStartsWith(s, STRUCT)) {
+    FieldList fields;
+    for (size_t k = 1; k < s.size(); k++) {
+      fields.emplace_back(parseField(s[k]));
+    }
+    return Struct(fields);
+  }
+  if (elementStartsWith(s, ARRAY)) {
+    return Array(parseField(s[1]));
+  }
   throw ParseException("invalid heap type", s.line, s.col);
 }
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index fd49c5b93..286542303 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -186,6 +186,8 @@ 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;
 }