Parsing and emitting nominal types (#3933)

Adds a `--nominal` option to switch the type machinery from equirecursive to
nominal. Implements binary and text parsing and emitting of nominal types using
new type constructor opcodes and an `(extends $super)` text syntax extension.
When not in nominal mode, these extensions will still be parsed but will not
have any effect and will not be used when emitting.

8 files changed, 85 insertions, 16 deletions

diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 486838aea..aaf484036 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -566,6 +566,13 @@ inline void collectHeapTypes(Module& wasm,
         counts.note(child);
       }
     }
+    HeapType super;
+    if (ht.getSuperType(super)) {
+      if (!counts.count(super)) {
+        newTypes.insert(super);
+      }
+      counts.note(super);
+    }
   }
 
   // Sort by frequency and then original insertion order.
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 47db029ab..dbe4f2557 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -2496,7 +2496,7 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> {
     }
     o << ')';
   }
-  void handleHeapType(HeapType type) {
+  void handleHeapType(HeapType type, Module* module) {
     if (type.isSignature()) {
       handleSignature(type.getSignature());
     } else if (type.isArray()) {
@@ -2506,6 +2506,12 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> {
     } else {
       o << type;
     }
+    HeapType super;
+    if (type.getSuperType(super)) {
+      o << " (extends ";
+      TypeNamePrinter(o, module).print(super);
+      o << ')';
+    }
   }
   void visitExport(Export* curr) {
     o << '(';
@@ -2889,7 +2895,7 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> {
       printMedium(o, "type") << ' ';
       TypeNamePrinter(o, curr).print(type);
       o << ' ';
-      handleHeapType(type);
+      handleHeapType(type, curr);
       o << ")" << maybeNewLine;
     }
     ModuleUtils::iterImportedMemories(
diff --git a/src/tools/tool-options.h b/src/tools/tool-options.h
index bc768c1da..49eca1adc 100644
--- a/src/tools/tool-options.h
+++ b/src/tools/tool-options.h
@@ -114,6 +114,14 @@ struct ToolOptions : public Options {
                value = argument.substr(colon + 1);
              }
              passOptions.arguments[key] = value;
+           })
+      .add("--nominal",
+           "",
+           "Use the prototype nominal type system instead of the normal "
+           "equirecursive type system.",
+           Options::Arguments::Zero,
+           [](Options* o, const std::string& argument) {
+             setTypeSystem(TypeSystem::Nominal);
            });
   }
 
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 715600f14..ca4d8612c 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -380,9 +380,12 @@ enum EncodedType {
   rtt = -0x18,     // 0x68
   dataref = -0x19, // 0x67
   // func_type form
-  Func = -0x20,   // 0x60
-  Struct = -0x21, // 0x5f
-  Array = -0x22,  // 0x5e
+  Func = -0x20,            // 0x60
+  Struct = -0x21,          // 0x5f
+  Array = -0x22,           // 0x5e
+  FuncExtending = -0x23,   // 0x5d
+  StructExtending = -0x24, // 0x5c
+  ArrayExtending = -0x25,  // 0x5b
   // block_type
   Empty = -0x40 // 0x40
 };
diff --git a/src/wasm-type.h b/src/wasm-type.h
index ff7e9af9c..12b4f3df7 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -363,6 +363,8 @@ public:
   const Struct& getStruct() const;
   Array getArray() const;
 
+  bool getSuperType(HeapType& out) const;
+
   constexpr TypeID getID() const { return id; }
   constexpr BasicHeapType getBasic() const {
     assert(isBasic() && "Basic heap type expected");
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index db253fa6e..a4df4ed16 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -219,8 +219,11 @@ void WasmBinaryWriter::writeTypes() {
   for (Index i = 0; i < types.size(); ++i) {
     auto type = types[i];
     BYN_TRACE("write " << type << std::endl);
+    HeapType super;
+    bool hasSuper = type.getSuperType(super);
     if (type.isSignature()) {
-      o << S32LEB(BinaryConsts::EncodedType::Func);
+      o << S32LEB(hasSuper ? BinaryConsts::EncodedType::FuncExtending
+                           : BinaryConsts::EncodedType::Func);
       auto sig = type.getSignature();
       for (auto& sigType : {sig.params, sig.results}) {
         o << U32LEB(sigType.size());
@@ -229,18 +232,23 @@ void WasmBinaryWriter::writeTypes() {
         }
       }
     } else if (type.isStruct()) {
-      o << S32LEB(BinaryConsts::EncodedType::Struct);
+      o << S32LEB(hasSuper ? BinaryConsts::EncodedType::StructExtending
+                           : 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);
+      o << S32LEB(hasSuper ? BinaryConsts::EncodedType::ArrayExtending
+                           : BinaryConsts::EncodedType::Array);
       writeField(type.getArray().element);
     } else {
       WASM_UNREACHABLE("TODO GC type writing");
     }
+    if (hasSuper) {
+      o << U32LEB(getTypeIndex(super));
+    }
   }
   finishSection(start);
 }
@@ -1901,15 +1909,27 @@ void WasmBinaryBuilder::readTypes() {
   for (size_t i = 0; i < numTypes; i++) {
     BYN_TRACE("read one\n");
     auto form = getS32LEB();
-    if (form == BinaryConsts::EncodedType::Func) {
+    if (form == BinaryConsts::EncodedType::Func ||
+        form == BinaryConsts::EncodedType::FuncExtending) {
       builder[i] = readSignatureDef();
-    } else if (form == BinaryConsts::EncodedType::Struct) {
+    } else if (form == BinaryConsts::EncodedType::Struct ||
+               form == BinaryConsts::EncodedType::StructExtending) {
       builder[i] = readStructDef();
-    } else if (form == BinaryConsts::EncodedType::Array) {
+    } else if (form == BinaryConsts::EncodedType::Array ||
+               form == BinaryConsts::EncodedType::ArrayExtending) {
       builder[i] = Array(readFieldDef());
     } else {
       throwError("bad type form " + std::to_string(form));
     }
+    if (form == BinaryConsts::EncodedType::FuncExtending ||
+        form == BinaryConsts::EncodedType::StructExtending ||
+        form == BinaryConsts::EncodedType::ArrayExtending) {
+      auto superIndex = getU32LEB();
+      if (superIndex >= numTypes) {
+        throwError("bad supertype index " + std::to_string(superIndex));
+      }
+      builder[i].subTypeOf(builder[superIndex]);
+    }
   }
 
   types = builder.build();
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 8c0fb9b2d..6ca0bcfd1 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -50,8 +50,9 @@ int unhex(char c) {
 
 namespace wasm {
 
-static Name STRUCT("struct"), FIELD("field"), ARRAY("array"), I8("i8"),
-  I16("i16"), RTT("rtt"), DECLARE("declare"), ITEM("item"), OFFSET("offset");
+static Name STRUCT("struct"), FIELD("field"), ARRAY("array"),
+  EXTENDS("extends"), I8("i8"), I16("i16"), RTT("rtt"), DECLARE("declare"),
+  ITEM("item"), OFFSET("offset");
 
 static Address getAddress(const Element* s) { return atoll(s->c_str()); }
 
@@ -857,15 +858,25 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     Element& def = elem[1]->dollared() ? *elem[2] : *elem[1];
     Element& kind = *def[0];
     if (kind == FUNC) {
-      builder[index++] = parseSignatureDef(def);
+      builder[index] = parseSignatureDef(def);
     } else if (kind == STRUCT) {
       builder[index] = parseStructDef(def, index);
-      index++;
     } else if (kind == ARRAY) {
-      builder[index++] = parseArrayDef(def);
+      builder[index] = parseArrayDef(def);
     } else {
       throw ParseException("unknown heaptype kind", kind.line, kind.col);
     }
+    if (elementStartsWith(elem[elem.size() - 1], EXTENDS)) {
+      // '(' 'extends' $supertype ')'
+      Element& extends = *elem[elem.size() - 1];
+      auto it = typeIndices.find(extends[1]->c_str());
+      if (it == typeIndices.end()) {
+        throw ParseException(
+          "unknown dollared function type", elem.line, elem.col);
+      }
+      builder[index].subTypeOf(builder[it->second]);
+    }
+    ++index;
   });
 
   types = builder.build();
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 96cb0b557..9bae42e98 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1176,6 +1176,18 @@ Array HeapType::getArray() const {
   return getHeapTypeInfo(*this)->array;
 }
 
+bool HeapType::getSuperType(HeapType& out) const {
+  if (isBasic()) {
+    return false;
+  }
+  HeapTypeInfo* super = getHeapTypeInfo(*this)->supertype;
+  if (super != nullptr) {
+    out = HeapType(uintptr_t(super));
+    return true;
+  }
+  return false;
+}
+
 bool HeapType::isSubType(HeapType left, HeapType right) {
   return SubTyper().isSubType(left, right);
 }