[threads] Parse, build, and print shared composite types (#6654)

Parse the text format for shared composite types as described in the
shared-everything thread proposal. Update the parser to use 'comptype' instead
of 'strtype' to match the final GC spec and add the new syntactic class
'sharecomptype'.

Update the type canonicalization logic to take sharedness into account to avoid
merging shared and unshared types. Make the same change in the TypeMerging pass.
Ensure that shared and unshared types cannot be in a subtype relationship with
each other.

Follow-up PRs will add shared abstract heap types, binary parsing and emitting
for shared types, and fuzzer support for shared types.

8 files changed, 178 insertions, 13 deletions

diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 520408d44..d9935ee32 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -90,6 +90,7 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
   i = 0;
   for (auto [type, _] : typeIndices) {
     typeBuilder[i].setOpen(type.isOpen());
+    typeBuilder[i].setShared(type.isShared());
     if (type.isSignature()) {
       auto sig = type.getSignature();
       TypeList newParams, newResults;
diff --git a/src/parser/contexts.h b/src/parser/contexts.h
index bce051a93..7c1a07b53 100644
--- a/src/parser/contexts.h
+++ b/src/parser/contexts.h
@@ -907,6 +907,7 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
   void addStructType(StructT) {}
   void addArrayType(ArrayT) {}
   void setOpen() {}
+  void setShared() {}
   Result<> addSubtype(Index) { return Ok{}; }
   void finishSubtype(Name name, Index pos) {
     // TODO: type annotations
@@ -1077,6 +1078,8 @@ struct ParseTypeDefsCtx : TypeParserCtx<ParseTypeDefsCtx> {
 
   void setOpen() { builder[index].setOpen(); }
 
+  void setShared() { builder[index].setShared(); }
+
   Result<> addSubtype(Index super) {
     if (super >= builder.size()) {
       return in.err("supertype index out of bounds");
diff --git a/src/parser/parsers.h b/src/parser/parsers.h
index c4eaf5fc6..a3fe5e5eb 100644
--- a/src/parser/parsers.h
+++ b/src/parser/parsers.h
@@ -331,7 +331,8 @@ template<typename Ctx>
 Result<typename Ctx::TypeUseT> typeuse(Ctx&, bool allowNames = true);
 MaybeResult<ImportNames> inlineImport(Lexer&);
 Result<std::vector<Name>> inlineExports(Lexer&);
-template<typename Ctx> Result<> strtype(Ctx&);
+template<typename Ctx> Result<> comptype(Ctx&);
+template<typename Ctx> Result<> sharecomptype(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::ModuleNameT> subtype(Ctx&);
 template<typename Ctx> MaybeResult<> deftype(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::LocalsT> locals(Ctx&);
@@ -2709,11 +2710,11 @@ inline Result<std::vector<Name>> inlineExports(Lexer& in) {
   return exports;
 }
 
-// strtype ::= ft:functype   => ft
-//           | ct:conttype   => ct
-//           | st:structtype => st
-//           | at:arraytype  => at
-template<typename Ctx> Result<> strtype(Ctx& ctx) {
+// comptype ::= ft:functype   => ft
+//            | ct:conttype   => ct
+//            | st:structtype => st
+//            | at:arraytype  => at
+template<typename Ctx> Result<> comptype(Ctx& ctx) {
   if (auto type = functype(ctx)) {
     CHECK_ERR(type);
     ctx.addFuncType(*type);
@@ -2737,8 +2738,23 @@ template<typename Ctx> Result<> strtype(Ctx& ctx) {
   return ctx.in.err("expected type description");
 }
 
-// subtype ::= '(' 'type' id? '(' 'sub' typeidx? strtype ')' ')'
-//           | '(' 'type' id? strtype ')'
+// sharecomptype ::= '(' 'shared' t:comptype ')' => shared t
+//                 | t:comptype => unshared t
+template<typename Ctx> Result<> sharecomptype(Ctx& ctx) {
+  if (ctx.in.takeSExprStart("shared"sv)) {
+    ctx.setShared();
+    CHECK_ERR(comptype(ctx));
+    if (!ctx.in.takeRParen()) {
+      return ctx.in.err("expected end of shared comptype");
+    }
+  } else {
+    CHECK_ERR(comptype(ctx));
+  }
+  return Ok{};
+}
+
+// subtype ::= '(' 'type' id? '(' 'sub' typeidx? sharecomptype ')' ')'
+//           | '(' 'type' id? sharecomptype ')'
 template<typename Ctx> MaybeResult<> subtype(Ctx& ctx) {
   auto pos = ctx.in.getPos();
 
@@ -2760,13 +2776,13 @@ template<typename Ctx> MaybeResult<> subtype(Ctx& ctx) {
       CHECK_ERR(ctx.addSubtype(*super));
     }
 
-    CHECK_ERR(strtype(ctx));
+    CHECK_ERR(sharecomptype(ctx));
 
     if (!ctx.in.takeRParen()) {
       return ctx.in.err("expected end of subtype definition");
     }
   } else {
-    CHECK_ERR(strtype(ctx));
+    CHECK_ERR(sharecomptype(ctx));
   }
 
   if (!ctx.in.takeRParen()) {
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index f827e097c..e5ac7888b 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -541,6 +541,9 @@ bool shapeEq(HeapType a, HeapType b) {
   if (a.isOpen() != b.isOpen()) {
     return false;
   }
+  if (a.isShared() != b.isShared()) {
+    return false;
+  }
   if (a.isStruct() && b.isStruct()) {
     return shapeEq(a.getStruct(), b.getStruct());
   }
@@ -555,6 +558,7 @@ bool shapeEq(HeapType a, HeapType b) {
 
 size_t shapeHash(HeapType a) {
   size_t digest = hash(a.isOpen());
+  rehash(digest, a.isShared());
   if (a.isStruct()) {
     rehash(digest, 0);
     hash_combine(digest, shapeHash(a.getStruct()));
diff --git a/src/wasm-type.h b/src/wasm-type.h
index b02484ae3..3e9fa4db3 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -377,6 +377,7 @@ public:
   bool isString() const;
   bool isBottom() const;
   bool isOpen() const;
+  bool isShared() const;
 
   Signature getSignature() const;
   Continuation getContinuation() const;
@@ -614,9 +615,8 @@ struct TypeBuilder {
   Type getTempTupleType(const Tuple&);
   Type getTempRefType(HeapType heapType, Nullability nullable);
 
-  // In nominal mode, or for nominal types, declare the HeapType being built at
-  // index `i` to be an immediate subtype of the given HeapType. Does nothing
-  // for equirecursive types.
+  // Declare the HeapType being built at index `i` to be an immediate subtype of
+  // the given HeapType.
   void setSubType(size_t i, HeapType super);
 
   // Create a new recursion group covering slots [i, i + length). Groups must
@@ -624,6 +624,7 @@ struct TypeBuilder {
   void createRecGroup(size_t i, size_t length);
 
   void setOpen(size_t i, bool open = true);
+  void setShared(size_t i, bool shared = true);
 
   enum class ErrorReason {
     // There is a cycle in the supertype relation.
@@ -696,6 +697,10 @@ struct TypeBuilder {
       builder.setOpen(index, open);
       return *this;
     }
+    Entry& setShared(bool shared = true) {
+      builder.setShared(index, shared);
+      return *this;
+    }
   };
 
   Entry operator[](size_t i) { return Entry{*this, i}; }
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 3e215b23a..83bf47107 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -86,6 +86,7 @@ struct HeapTypeInfo {
   // global store.
   bool isTemp = false;
   bool isOpen = false;
+  bool isShared = false;
   // The supertype of this HeapType, if it exists.
   HeapTypeInfo* supertype = nullptr;
   // The recursion group of this type or null if the recursion group is trivial
@@ -1251,6 +1252,15 @@ bool HeapType::isOpen() const {
   }
 }
 
+bool HeapType::isShared() const {
+  if (isBasic()) {
+    // TODO: shared basic heap types
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isShared;
+  }
+}
+
 Signature HeapType::getSignature() const {
   assert(isSignature());
   return getHeapTypeInfo(*this)->signature;
@@ -1953,6 +1963,9 @@ std::ostream& TypePrinter::print(HeapType type) {
       os << ' ';
     }
   }
+  if (type.isShared()) {
+    os << "(shared ";
+  }
   if (type.isSignature()) {
     print(type.getSignature());
   } else if (type.isContinuation()) {
@@ -1964,6 +1977,9 @@ std::ostream& TypePrinter::print(HeapType type) {
   } else {
     WASM_UNREACHABLE("unexpected type");
   }
+  if (type.isShared()) {
+    os << ')';
+  }
   if (useSub) {
     os << ')';
   }
@@ -2121,6 +2137,7 @@ size_t RecGroupHasher::hash(const HeapTypeInfo& info) const {
     hash_combine(digest, hash(HeapType(uintptr_t(info.supertype))));
   }
   wasm::rehash(digest, info.isOpen);
+  wasm::rehash(digest, info.isShared);
   wasm::rehash(digest, info.kind);
   switch (info.kind) {
     case HeapTypeInfo::SignatureKind:
@@ -2257,6 +2274,9 @@ bool RecGroupEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const {
   if (a.isOpen != b.isOpen) {
     return false;
   }
+  if (a.isShared != b.isShared) {
+    return false;
+  }
   if (a.kind != b.kind) {
     return false;
   }
@@ -2532,12 +2552,20 @@ void TypeBuilder::setOpen(size_t i, bool open) {
   impl->entries[i].info->isOpen = open;
 }
 
+void TypeBuilder::setShared(size_t i, bool shared) {
+  assert(i < size() && "index out of bounds");
+  impl->entries[i].info->isShared = shared;
+}
+
 namespace {
 
 bool isValidSupertype(const HeapTypeInfo& sub, const HeapTypeInfo& super) {
   if (!super.isOpen) {
     return false;
   }
+  if (sub.isShared != super.isShared) {
+    return false;
+  }
   if (sub.kind != super.kind) {
     return false;
   }
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 443a7ee66..c0a27b229 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -273,6 +273,40 @@ TEST_F(TypeTest, InvalidFinalSupertype) {
   EXPECT_EQ(error->index, 1u);
 }
 
+TEST_F(TypeTest, InvalidSharedSupertype) {
+  TypeBuilder builder(2);
+  builder[0] = Struct{};
+  builder[1] = Struct{};
+  builder[0].setShared(true);
+  builder[1].setShared(false);
+  builder[1].subTypeOf(builder[0]);
+
+  auto result = builder.build();
+  EXPECT_FALSE(result);
+
+  const auto* error = result.getError();
+  ASSERT_TRUE(error);
+  EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::InvalidSupertype);
+  EXPECT_EQ(error->index, 1u);
+}
+
+TEST_F(TypeTest, InvalidUnsharedSupertype) {
+  TypeBuilder builder(2);
+  builder[0] = Struct{};
+  builder[1] = Struct{};
+  builder[0].setShared(false);
+  builder[1].setShared(true);
+  builder[1].subTypeOf(builder[0]);
+
+  auto result = builder.build();
+  EXPECT_FALSE(result);
+
+  const auto* error = result.getError();
+  ASSERT_TRUE(error);
+  EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::InvalidSupertype);
+  EXPECT_EQ(error->index, 1u);
+}
+
 TEST_F(TypeTest, ForwardReferencedChild) {
   TypeBuilder builder(3);
   builder.createRecGroup(0, 2);
diff --git a/test/lit/passes/type-merging-shared.wast b/test/lit/passes/type-merging-shared.wast
new file mode 100644
index 000000000..aefeccc3b
--- /dev/null
+++ b/test/lit/passes/type-merging-shared.wast
@@ -0,0 +1,74 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: foreach %s %t wasm-opt --closed-world --type-merging --remove-unused-types -all -S -o - | filecheck %s
+
+(module
+ ;; Shared and non-shared types are not merged.
+ ;; CHECK:      (rec
+ ;; CHECK-NEXT:  (type $C' (shared (func)))
+
+ ;; CHECK:       (type $B' (shared (array i8)))
+
+ ;; CHECK:       (type $B (array i8))
+
+ ;; CHECK:       (type $A' (shared (struct )))
+
+ ;; CHECK:       (type $A (struct ))
+ (type $A (struct))
+ (type $A' (shared (struct)))
+ (type $B (array i8))
+ (type $B' (shared (array i8)))
+ ;; CHECK:       (type $C (func))
+ (type $C (func))
+ (type $C' (shared (func)))
+
+ ;; CHECK:      (func $foo (type $C)
+ ;; CHECK-NEXT:  (local $a (ref null $A))
+ ;; CHECK-NEXT:  (local $a' (ref null $A'))
+ ;; CHECK-NEXT:  (local $b (ref null $B))
+ ;; CHECK-NEXT:  (local $b' (ref null $B'))
+ ;; CHECK-NEXT:  (local $c (ref null $C))
+ ;; CHECK-NEXT:  (local $c' (ref null $C'))
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT: )
+ (func $foo
+  (local $a (ref null $A))
+  (local $a' (ref null $A'))
+  (local $b (ref null $B))
+  (local $b' (ref null $B'))
+  (local $c (ref null $C))
+  (local $c' (ref null $C'))
+ )
+)
+
+(module
+ ;; But two shared types can be merged.
+ ;; CHECK:      (rec
+ ;; CHECK-NEXT:  (type $B (shared (array i8)))
+
+ ;; CHECK:       (type $A (shared (struct )))
+ (type $A (shared (struct)))
+ (type $A' (shared (struct)))
+ (type $B (shared (array i8)))
+ (type $B' (shared (array i8)))
+ ;; CHECK:       (type $C (shared (func)))
+ (type $C (shared (func)))
+ (type $C' (shared (func)))
+
+ ;; CHECK:      (func $foo (type $C)
+ ;; CHECK-NEXT:  (local $a (ref null $A))
+ ;; CHECK-NEXT:  (local $a' (ref null $A))
+ ;; CHECK-NEXT:  (local $b (ref null $B))
+ ;; CHECK-NEXT:  (local $b' (ref null $B))
+ ;; CHECK-NEXT:  (local $c (ref null $C))
+ ;; CHECK-NEXT:  (local $c' (ref null $C))
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT: )
+ (func $foo
+  (local $a (ref null $A))
+  (local $a' (ref null $A'))
+  (local $b (ref null $B))
+  (local $b' (ref null $B'))
+  (local $c (ref null $C))
+  (local $c' (ref null $C'))
+ )
+)