6 files changed, 77 insertions, 2 deletions
diff --git a/test/heap-types.wast.fromBinary.noDebugInfo b/test/heap-types.wast.fromBinary.noDebugInfo
index e0b465bed..dbfcb9cdd 100644
--- a/test/heap-types.wast.fromBinary.noDebugInfo
+++ b/test/heap-types.wast.fromBinary.noDebugInfo
@@ -7,8 +7,8 @@
  (type ${} (struct ))
  (type ${mut:f32} (struct (field (mut f32))))
  (type $none_=>_none (func))
- (type $rtt_1_${}_=>_none (func (param (rtt 1 ${}))))
- (type $rtt_${}_=>_none (func (param (rtt ${}))))
+ (type $rtt_1_{}_=>_none (func (param (rtt 1 ${}))))
+ (type $rtt_{}_=>_none (func (param (rtt ${}))))
  (type $ref?|{i32_f32_f64}|_=>_ref?|{i8_mut:i16_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}| (func (param (ref null ${i32_f32_f64})) (result (ref null ${i8_mut:i16_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))))
  (type $ref?|[mut:f64]|_=>_ref?|[ref?|[mut:f64]|]| (func (param (ref null $[mut:f64])) (result (ref null $[ref?|[mut:f64]|]))))
  (type ${i32} (struct (field i32)))
diff --git a/test/lit/recursive-types.wast b/test/lit/recursive-types.wast
new file mode 100644
index 000000000..c825c9cad
--- /dev/null
+++ b/test/lit/recursive-types.wast
@@ -0,0 +1,36 @@
+;; Test a trivial recursive type works properly
+
+;; RUN: wasm-opt %s -all -S -o - | filecheck %s
+
+;; TODO: Fix the bug where self-referential function signatures are emitted
+;; twice. This happens because collectHeapTypes has to reconstruct a HeapType
+;; from each function's signature, but self-referential HeapTypes aren't
+;; canonicalized when they are parsed so collectHeapTypes ends up with a
+;; separate, unfolded version of the type.
+
+;; TODO: Fix the bug where structurally identical types are given the same
+;; generated name, making the wast invalid due to duplicate names.
+
+;; CHECK:      (module
+;; CHECK-NEXT:   (type $ref?|...0|_=>_ref?|...0| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
+;; CHECK-NEXT:   (type $ref?|...0|_=>_ref?|...0| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
+;; CHECK-NEXT:   (type $ref?|ref?|...0|_->_ref?|...0||_=>_ref?|ref?|...0|_->_ref?|...0|| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
+;; CHECK-NEXT:   (type $ref?|ref?|...0|_->_ref?|...0||_=>_ref?|ref?|...0|_->_ref?|...0|| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
+;; CHECK-NEXT:   (func $foo (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
+;; CHECK-NEXT:     (unreachable)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (func $bar (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
+;; CHECK-NEXT:     (unreachable)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT: )
+
+(module
+  (type (func (param (ref null 0)) (result (ref null 0))))
+  (type (func (param (ref null 1)) (result (ref null 1))))
+  (func $foo (type 0)
+    (unreachable)
+  )
+  (func $bar (type 1)
+    (unreachable)
+  )
+)
diff --git a/test/subtypes.wast b/test/subtypes.wast
index d37735777..06f85a273 100644
--- a/test/subtypes.wast
+++ b/test/subtypes.wast
@@ -18,6 +18,15 @@
     (field (ref any))
   ))
 
+  ;; Recursive structs
+  (type $struct-rec-one (struct
+    (field (ref $struct-rec-one))
+  ))
+  (type $struct-rec-two (struct
+    (field (ref $struct-rec-two))
+    (field (ref $struct-rec-two))
+  ))
+
   (func $foo (param $no-null (ref $vector-i32))
              (param $yes-null (ref null $vector-i32))
     ;; ok to set a non-nullable reference to a nullable target
@@ -41,4 +50,10 @@
     ;; also ok to have extra fields
     (local.set $s-i31 (local.get $s-i31_any))
   )
+
+  (func $coinductive (param $rec-one (ref $struct-rec-one))
+                     (param $rec-two (ref $struct-rec-two))
+    ;; Do not infinitely recurse when determining this subtype relation!
+    (local.set $rec-one (local.get $rec-two))
+  )
 )
diff --git a/test/subtypes.wast.from-wast b/test/subtypes.wast.from-wast
index db4d69f6d..3e811109a 100644
--- a/test/subtypes.wast.from-wast
+++ b/test/subtypes.wast.from-wast
@@ -1,8 +1,11 @@
 (module
+ (type $struct-rec-two (struct (field (ref null $struct-rec-two)) (field (ref null $struct-rec-two))))
  (type $struct-i31 (struct (field (ref null i31))))
+ (type $struct-rec-one (struct (field (ref null $struct-rec-one))))
  (type $vector-i32 (array i32))
  (type $ref?|$struct-i31|_ref?|$struct-any|_=>_none (func (param (ref null $struct-i31) (ref null $struct-any))))
  (type $ref?|$struct-i31|_ref?|$struct-i31_any|_=>_none (func (param (ref null $struct-i31) (ref null $struct-i31_any))))
+ (type $ref?|$struct-rec-one|_ref?|$struct-rec-two|_=>_none (func (param (ref null $struct-rec-one) (ref null $struct-rec-two))))
  (type $ref?|$vector-i32|_ref?|$vector-i32|_=>_none (func (param (ref null $vector-i32) (ref null $vector-i32))))
  (type $ref?|$vector-i31|_ref?|$vector-any|_=>_none (func (param (ref null $vector-i31) (ref null $vector-any))))
  (type $struct-any (struct (field anyref)))
@@ -29,4 +32,9 @@
    (local.get $s-i31_any)
   )
  )
+ (func $coinductive (param $rec-one (ref null $struct-rec-one)) (param $rec-two (ref null $struct-rec-two))
+  (local.set $rec-one
+   (local.get $rec-two)
+  )
+ )
 )
diff --git a/test/subtypes.wast.fromBinary b/test/subtypes.wast.fromBinary
index d169a4086..c2fcb0e3d 100644
--- a/test/subtypes.wast.fromBinary
+++ b/test/subtypes.wast.fromBinary
@@ -1,8 +1,11 @@
 (module
+ (type $struct-rec-two (struct (field (ref null $struct-rec-two)) (field (ref null $struct-rec-two))))
  (type $struct-i31 (struct (field (ref null i31))))
+ (type $struct-rec-one (struct (field (ref null $struct-rec-one))))
  (type $vector-i32 (array i32))
  (type $ref?|$struct-i31|_ref?|$struct-any|_=>_none (func (param (ref null $struct-i31) (ref null $struct-any))))
  (type $ref?|$struct-i31|_ref?|$struct-i31_any|_=>_none (func (param (ref null $struct-i31) (ref null $struct-i31_any))))
+ (type $ref?|$struct-rec-one|_ref?|$struct-rec-two|_=>_none (func (param (ref null $struct-rec-one) (ref null $struct-rec-two))))
  (type $ref?|$vector-i32|_ref?|$vector-i32|_=>_none (func (param (ref null $vector-i32) (ref null $vector-i32))))
  (type $ref?|$vector-i31|_ref?|$vector-any|_=>_none (func (param (ref null $vector-i31) (ref null $vector-any))))
  (type $struct-any (struct (field anyref)))
@@ -29,5 +32,10 @@
    (local.get $s-i31_any)
   )
  )
+ (func $coinductive (param $rec-one (ref null $struct-rec-one)) (param $rec-two (ref null $struct-rec-two))
+  (local.set $rec-one
+   (local.get $rec-two)
+  )
+ )
 )
 
diff --git a/test/subtypes.wast.fromBinary.noDebugInfo b/test/subtypes.wast.fromBinary.noDebugInfo
index d80e5afd0..a108cf151 100644
--- a/test/subtypes.wast.fromBinary.noDebugInfo
+++ b/test/subtypes.wast.fromBinary.noDebugInfo
@@ -1,8 +1,11 @@
 (module
+ (type ${ref?|...0|_ref?|...0|} (struct (field (ref null ${ref?|...0|_ref?|...0|})) (field (ref null ${ref?|...0|_ref?|...0|}))))
  (type ${ref?|i31|} (struct (field (ref null i31))))
+ (type ${ref?|...0|} (struct (field (ref null ${ref?|...0|}))))
  (type $[i32] (array i32))
  (type $ref?|{ref?|i31|}|_ref?|{anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${anyref}))))
  (type $ref?|{ref?|i31|}|_ref?|{ref?|i31|_anyref}|_=>_none (func (param (ref null ${ref?|i31|}) (ref null ${ref?|i31|_anyref}))))
+ (type $ref?|{ref?|...0|}|_ref?|{ref?|...0|_ref?|...0|}|_=>_none (func (param (ref null ${ref?|...0|}) (ref null ${ref?|...0|_ref?|...0|}))))
  (type $ref?|[i32]|_ref?|[i32]|_=>_none (func (param (ref null $[i32]) (ref null $[i32]))))
  (type $ref?|[ref?|i31|]|_ref?|[anyref]|_=>_none (func (param (ref null $[ref?|i31|]) (ref null $[anyref]))))
  (type ${anyref} (struct (field anyref)))
@@ -29,5 +32,10 @@
    (local.get $1)
   )
  )
+ (func $4 (param $0 (ref null ${ref?|...0|})) (param $1 (ref null ${ref?|...0|_ref?|...0|}))
+  (local.set $0
+   (local.get $1)
+  )
+ )
 )