Parse, create, and print isorecursive recursion groups (#4464)

In `--hybrid` isorecursive mode, associate each defined type with a recursion
group, represented as a `(rec ...)` wrapping the type definitions in the text
format. Parse that text format, create the rec groups using a new TypeBuilder
method, and print the rec groups in the printer.

The only semantic difference rec groups currently make is that if one type in a
rec group will be included in the output, all the types in that rec group will
be included. This is because changing a rec group in any way (for example by
removing a type) changes the identity of the types in that group in the
isorecursive type system. Notably, rec groups do not yet participate in
validation, so `--hybrid` is largely equivalent to `--nominal` for now.

3 files changed, 93 insertions, 0 deletions

diff --git a/test/lit/isorecursive-good.wast b/test/lit/isorecursive-good.wast
new file mode 100644
index 000000000..353905c4f
--- /dev/null
+++ b/test/lit/isorecursive-good.wast
@@ -0,0 +1,53 @@
+;; TODO: Autogenerate these checks! The current script cannot handle `rec`.
+
+;; RUN: wasm-opt %s -all --hybrid -S -o - | filecheck %s --check-prefix HYBRID
+;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s --check-prefix NOMINAL
+
+;; TDOO: test with --roundtrip as well
+
+(module
+
+;; HYBRID:      (rec
+;; HYBRID-NEXT:  (type $super-struct (struct_subtype (field i32) data))
+;; HYBRID-NEXT:  (type $sub-struct (struct_subtype (field i32) (field i64) $super-struct))
+;; HYBRID-NEXT: )
+
+;; HYBRID:      (rec
+;; HYBRID-NEXT:   (type $super-array (array_subtype (ref $super-struct) data))
+;; HYBRID-NEXT:   (type $sub-array (array_subtype (ref $sub-struct) $super-array))
+;; HYBRID-NEXT: )
+
+;; NOMINAL-NOT: rec
+
+;; NOMINAL:      (type $super-struct (struct_subtype (field i32) data))
+;; NOMINAL-NEXT: (type $sub-struct (struct_subtype (field i32) (field i64) $super-struct))
+
+;; NOMINAL:      (type $super-array (array_subtype (ref $super-struct) data))
+;; NOMINAL-NEXT: (type $sub-array (array_subtype (ref $sub-struct) $super-array))
+
+  (rec
+    (type $super-struct (struct i32))
+    (type $sub-struct (struct_subtype i32 i64 $super-struct))
+  )
+
+  (rec
+    (type $super-array (array (ref $super-struct)))
+    (type $sub-array (array_subtype (ref $sub-struct) $super-array))
+  )
+
+  (func $make-super-struct (result (ref $super-struct))
+    (call $make-sub-struct)
+  )
+
+  (func $make-sub-struct (result (ref $sub-struct))
+    (unreachable)
+  )
+
+  (func $make-super-array (result (ref $super-array))
+    (call $make-sub-array)
+  )
+
+  (func $make-sub-array (result (ref $sub-array))
+    (unreachable)
+  )
+)
diff --git a/test/lit/isorecursive-singleton-group.wast b/test/lit/isorecursive-singleton-group.wast
new file mode 100644
index 000000000..adb40b141
--- /dev/null
+++ b/test/lit/isorecursive-singleton-group.wast
@@ -0,0 +1,19 @@
+;; TODO: Autogenerate these checks! The current script cannot handle `rec`.
+
+;; RUN: wasm-opt %s -all --hybrid -S -o - | filecheck %s
+
+;; Check that everything works correctly when a recursion group has only a
+;; single member. The rec group is implicit, so does not need to be printed.
+
+(module
+
+;; CHECK-NOT: rec
+;; CHECK: (type $singleton (struct_subtype data))
+
+ (rec
+  (type $singleton (struct_subtype data))
+ )
+
+ ;; Use the type so it appears in the output.
+ (global $g (ref null $singleton) (ref.null $singleton))
+)
diff --git a/test/lit/isorecursive-whole-group.wast b/test/lit/isorecursive-whole-group.wast
new file mode 100644
index 000000000..625025b23
--- /dev/null
+++ b/test/lit/isorecursive-whole-group.wast
@@ -0,0 +1,21 @@
+;; TODO: Autogenerate these checks! The current script cannot handle `rec`.
+
+;; RUN: wasm-opt %s -all --hybrid -S -o - | filecheck %s
+
+;; Check that unused types are still included in the output when they are part
+;; of a recursion group with used types.
+
+(module
+
+;; CHECK:      (rec
+;; CHECK-NEXT:  (type $used (struct_subtype data))
+;; CHECK-NEXT:  (type $unused (struct_subtype data))
+;; CHECK-NEXT: )
+
+ (rec
+  (type $used (struct_subtype data))
+  (type $unused (struct_subtype data))
+ )
+
+ (global $g (ref null $used) (ref.null $used))
+)