Parse milestone 4 nominal types (#4222)

Implement parsing the new {func,struct,array}_subtype format for nominal types.
For now, the new format is parsed the same way the old-style (extends X) format
is parsed, i.e. in --nominal mode types are parsed as nominal but otherwise they
are parsed as equirecursive. Intentionally do not parse the new types
unconditionally as nominal for now to allow frontends to update their nominal
text format while continuing to use the workflow of running wasm-opt without
--nominal to lower nominal types to structural types.

3 files changed, 169 insertions, 15 deletions

diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 417a0ac0e..854228e9f 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -52,8 +52,9 @@ int unhex(char c) {
 namespace wasm {
 
 static Name STRUCT("struct"), FIELD("field"), ARRAY("array"),
-  EXTENDS("extends"), I8("i8"), I16("i16"), RTT("rtt"), DECLARE("declare"),
-  ITEM("item"), OFFSET("offset");
+  FUNC_SUBTYPE("func_subtype"), STRUCT_SUBTYPE("struct_subtype"),
+  ARRAY_SUBTYPE("array_subtype"), 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()); }
 
@@ -786,12 +787,13 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     return results;
   };
 
-  auto parseSignatureDef = [&](Element& elem) {
+  auto parseSignatureDef = [&](Element& elem, bool nominal) {
     // '(' 'func' vec(param) vec(result) ')'
     // param ::= '(' 'param' id? valtype ')'
     // result ::= '(' 'result' valtype ')'
     std::vector<Type> params, results;
-    for (auto it = ++elem.begin(), end = elem.end(); it != end; ++it) {
+    auto end = elem.end() - (nominal ? 1 : 0);
+    for (auto it = ++elem.begin(); it != end; ++it) {
       Element& curr = **it;
       if (elementStartsWith(curr, PARAM)) {
         auto newParams = parseParams(curr);
@@ -838,9 +840,10 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     return Field(parseValType(*elem), mutable_);
   };
 
-  auto parseStructDef = [&](Element& elem, size_t typeIndex) {
+  auto parseStructDef = [&](Element& elem, size_t typeIndex, bool nominal) {
     FieldList fields;
-    for (Index i = 1; i < elem.size(); i++) {
+    Index end = elem.size() - (nominal ? 1 : 0);
+    for (Index i = 1; i < end; i++) {
       Name name;
       fields.emplace_back(parseField(elem[i], name));
       if (name.is()) {
@@ -860,22 +863,43 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
   forEachType([&](Element& elem) {
     Element& def = elem[1]->dollared() ? *elem[2] : *elem[1];
     Element& kind = *def[0];
-    if (kind == FUNC) {
-      builder[index] = parseSignatureDef(def);
-    } else if (kind == STRUCT) {
-      builder[index] = parseStructDef(def, index);
-    } else if (kind == ARRAY) {
+    bool nominal =
+      kind == FUNC_SUBTYPE || kind == STRUCT_SUBTYPE || kind == ARRAY_SUBTYPE;
+    if (kind == FUNC || kind == FUNC_SUBTYPE) {
+      builder[index] = parseSignatureDef(def, nominal);
+    } else if (kind == STRUCT || kind == STRUCT_SUBTYPE) {
+      builder[index] = parseStructDef(def, index, nominal);
+    } else if (kind == ARRAY || kind == ARRAY_SUBTYPE) {
       builder[index] = parseArrayDef(def);
     } else {
       throw ParseException("unknown heaptype kind", kind.line, kind.col);
     }
-    if (elementStartsWith(elem[elem.size() - 1], EXTENDS)) {
+    Element* super = nullptr;
+    if (nominal) {
+      // TODO: Let the new nominal types coexist with equirecursive types
+      // builder[index].setNominal();
+      super = def[def.size() - 1];
+      if (super->dollared()) {
+        // OK
+      } else if (kind == FUNC_SUBTYPE && super->str() == FUNC) {
+        // OK; no supertype
+        super = nullptr;
+      } else if ((kind == STRUCT_SUBTYPE || kind == ARRAY_SUBTYPE) &&
+                 super->str() == DATA) {
+        // OK; no supertype
+        super = nullptr;
+      } else {
+        throw ParseException("unknown supertype", super->line, super->col);
+      }
+    } else if (elementStartsWith(elem[elem.size() - 1], EXTENDS)) {
       // '(' 'extends' $supertype ')'
       Element& extends = *elem[elem.size() - 1];
-      auto it = typeIndices.find(extends[1]->c_str());
+      super = extends[1];
+    }
+    if (super) {
+      auto it = typeIndices.find(super->c_str());
       if (it == typeIndices.end()) {
-        throw ParseException(
-          "unknown dollared function type", elem.line, elem.col);
+        throw ParseException("unknown supertype", super->line, super->col);
       }
       builder[index].subTypeOf(builder[it->second]);
     }
diff --git a/test/lit/parse-bad-nominal-types.wast b/test/lit/parse-bad-nominal-types.wast
new file mode 100644
index 000000000..e73e4e51b
--- /dev/null
+++ b/test/lit/parse-bad-nominal-types.wast
@@ -0,0 +1,63 @@
+;; Test that incorrect nominal types result in the expected parse errors
+
+;; RUN: foreach %s %t not wasm-opt -all 2>&1 | filecheck %s
+
+;; CHECK: [parse exception: unknown supertype (at 2:35)]
+(module
+  (type $bad-func (func) (extends $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:39)]
+(module
+  (type $bad-struct (struct) (extends $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:41)]
+(module
+  (type $bad-array (array i32) (extends $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:33)]
+(module
+  (type $bad-func (func_subtype $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:37)]
+(module
+  (type $bad-struct (struct_subtype $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:39)]
+(module
+  (type $bad-array (array_subtype i32 $bad))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:32)]
+(module
+  (type $bad-func (func_subtype any))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:36)]
+(module
+  (type $bad-struct (struct_subtype any))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:38)]
+(module
+  (type $bad-array (array_subtype i32 any))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:32)]
+(module
+  (type $bad-func (func_subtype data))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:36)]
+(module
+  (type $bad-struct (struct_subtype func))
+)
+
+;; CHECK: [parse exception: unknown supertype (at 2:38)]
+(module
+  (type $bad-array (array_subtype i32 func))
+)
diff --git a/test/lit/parse-nominal-types.wast b/test/lit/parse-nominal-types.wast
new file mode 100644
index 000000000..c3981478d
--- /dev/null
+++ b/test/lit/parse-nominal-types.wast
@@ -0,0 +1,67 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; Test that new-style nominal types are parsed correctly.
+;; TODO: Remove --nominal below once nominal types are parsed as nominal by default.
+
+;; RUN: foreach %s %t wasm-opt --nominal -all -S -o - | filecheck %s
+;; RUN: foreach %s %t wasm-opt --nominal -all --roundtrip -S -o - | filecheck %s
+
+;; void function type
+(module
+  ;; CHECK:      (type $sub (func) (extends $super))
+  (type $sub (func_subtype $super))
+
+  ;; CHECK:      (type $super (func))
+  (type $super (func_subtype func))
+
+  ;; CHECK:      (global $g (ref null $super) (ref.null $sub))
+  (global $g (ref null $super) (ref.null $sub))
+)
+
+;; function type with params and results
+(module
+  ;; CHECK:      (type $sub (func (param i32) (result i32)) (extends $super))
+  (type $sub (func_subtype (param i32) (result i32) $super))
+
+  ;; CHECK:      (type $super (func (param i32) (result i32)))
+  (type $super (func_subtype (param i32) (result i32) func))
+
+  ;; CHECK:      (global $g (ref null $super) (ref.null $sub))
+  (global $g (ref null $super) (ref.null $sub))
+)
+
+;; empty struct type
+(module
+  ;; CHECK:      (type $sub (struct ) (extends $super))
+  (type $sub (struct_subtype $super))
+
+  ;; CHECK:      (type $super (struct ))
+  (type $super (struct_subtype data))
+
+  ;; CHECK:      (global $g (ref null $super) (ref.null $sub))
+  (global $g (ref null $super) (ref.null $sub))
+)
+
+;; struct type with fields
+(module
+  ;; CHECK:      (type $sub (struct (field i32) (field i64)) (extends $super))
+  (type $sub (struct_subtype i32 (field i64) $super))
+
+  ;; CHECK:      (type $super (struct (field i32) (field i64)))
+  (type $super (struct_subtype (field i32) i64 data))
+
+  ;; CHECK:      (global $g (ref null $super) (ref.null $sub))
+  (global $g (ref null $super) (ref.null $sub))
+)
+
+;; array type
+(module
+  ;; CHECK:      (type $sub (array i8) (extends $super))
+  (type $sub (array_subtype i8 $super))
+
+  ;; CHECK:      (type $super (array i8))
+  (type $super (array_subtype i8 data))
+
+  ;; CHECK:      (global $g (ref null $super) (ref.null $sub))
+  (global $g (ref null $super) (ref.null $sub))
+)