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.

3 files changed, 97 insertions, 0 deletions

diff --git a/test/lit/nominal-bad.wast b/test/lit/nominal-bad.wast
new file mode 100644
index 000000000..43a1eea95
--- /dev/null
+++ b/test/lit/nominal-bad.wast
@@ -0,0 +1,29 @@
+;; RUN: not wasm-opt %s -all --nominal -S -o - 2>&1 | filecheck %s
+
+;; CHECK: [wasm-validator error in function make-super-struct] function body type must match
+;; CHECK: [wasm-validator error in function make-super-array] function body type must match
+
+(module
+
+  (type $sub-struct (struct i32 i64))
+  (type $super-struct (struct i32))
+
+  (type $sub-array (array (ref $sub-struct)))
+  (type $super-array (array (ref $super-struct)))
+
+  (func $make-sub-struct (result (ref $sub-struct))
+    (unreachable)
+  )
+
+  (func $make-super-struct (result (ref $super-struct))
+    (call $make-sub-struct)
+  )
+
+  (func $make-sub-array (result (ref $sub-array))
+    (unreachable)
+  )
+
+  (func $make-super-array (result (ref $super-array))
+    (call $make-sub-array)
+  )
+)
diff --git a/test/lit/nominal-chain.wast b/test/lit/nominal-chain.wast
new file mode 100644
index 000000000..b6b48a191
--- /dev/null
+++ b/test/lit/nominal-chain.wast
@@ -0,0 +1,26 @@
+;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s
+;; RUN: wasm-opt %s -all --nominal --roundtrip -S -o - | filecheck %s
+
+;; Check that intermediate types in subtype chains are also included in the
+;; output module, even if there are no other references to those intermediate
+;; types.
+
+(module
+
+  ;; CHECK:      (type $root (struct ))
+  ;; CHECK-NEXT: (type $none_=>_ref?|$root| (func (result (ref null $root))))
+  ;; CHECK-NEXT: (type $leaf (struct (field i32) (field i64) (field f32) (field f64)) (extends $twig))
+  ;; CHECK-NEXT: (type $twig (struct (field i32) (field i64) (field f32)) (extends $branch))
+  ;; CHECK-NEXT: (type $branch (struct (field i32) (field i64)) (extends $trunk))
+  ;; CHECK-NEXT: (type $trunk (struct (field i32)) (extends $root))
+
+  (type $leaf (struct i32 i64 f32 f64) (extends $twig))
+  (type $twig (struct i32 i64 f32) (extends $branch))
+  (type $branch (struct i32 i64) (extends $trunk))
+  (type $trunk (struct i32) (extends $root))
+  (type $root (struct))
+
+  (func $make-root (result (ref null $root))
+    (ref.null $leaf)
+  )
+)
diff --git a/test/lit/nominal-good.wast b/test/lit/nominal-good.wast
new file mode 100644
index 000000000..d63b0506a
--- /dev/null
+++ b/test/lit/nominal-good.wast
@@ -0,0 +1,42 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s
+;; RUN: wasm-opt %s -all --nominal --roundtrip -S -o - | filecheck %s
+
+(module
+
+  (type $sub-struct (struct i32 i64) (extends $super-struct))
+  (type $super-struct (struct i32))
+
+  (type $sub-array (array (ref $sub-struct)) (extends $super-array))
+  (type $super-array (array (ref $super-struct)))
+
+  ;; TODO: signature types as well, once functions store their HeapTypes.
+
+  ;; CHECK:      (func $make-sub-struct (result (ref $sub-struct))
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $make-sub-struct (result (ref $sub-struct))
+    (unreachable)
+  )
+
+  ;; CHECK:      (func $make-super-struct (result (ref $super-struct))
+  ;; CHECK-NEXT:  (call $make-sub-struct)
+  ;; CHECK-NEXT: )
+  (func $make-super-struct (result (ref $super-struct))
+    (call $make-sub-struct)
+  )
+
+  ;; CHECK:      (func $make-sub-array (result (ref $sub-array))
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $make-sub-array (result (ref $sub-array))
+    (unreachable)
+  )
+
+  ;; CHECK:      (func $make-super-array (result (ref $super-array))
+  ;; CHECK-NEXT:  (call $make-sub-array)
+  ;; CHECK-NEXT: )
+  (func $make-super-array (result (ref $super-array))
+    (call $make-sub-array)
+  )
+)