Add a fuzzer utility for ensuring types are inhabitable (#5541)

Some valid GC types, such as non-nullable references to bottom heap types and
types that contain non-nullable references to themselves, are uninhabitable,
meaning it is not possible to construct values of those types. This can cause
problems for the fuzzer, which generally needs to be able to construct values of
arbitrary types.

To simplify things for the fuzzer, introduce a utility for transforming type
graphs such that all their types are inhabitable. The utility performs a DFS to
find cycles of non-nullable references and breaks those cycles by introducing
nullability.

The new utility is itself fuzzed in the type fuzzer.

2 files changed, 58 insertions, 0 deletions

diff --git a/test/lit/fuzz-types/isorecursive.test b/test/lit/fuzz-types/isorecursive.test
index 4ba564193..92f604215 100644
--- a/test/lit/fuzz-types/isorecursive.test
+++ b/test/lit/fuzz-types/isorecursive.test
@@ -30,3 +30,37 @@
 ;; CHECK-NEXT:  (type $18 none)
 ;; CHECK-NEXT: )
 ;; CHECK-NEXT: (type $19 (func_subtype (param (ref any) i32 i64 f64 f64 anyref v128) (result i64) $9))
+;; CHECK-NEXT:
+;; CHECK-NEXT: Inhabitable types:
+;; CHECK-NEXT:
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: (type $0 (type $0 (struct)))
+;; CHECK-NEXT: (rec
+;; CHECK-NEXT:  (type $1 (type $1 (struct)))
+;; CHECK-NEXT:  (type $2 (type $2 (array i16)))
+;; CHECK-NEXT:  (type $3 (type $3 (func)))
+;; CHECK-NEXT:  (type $4 (type $4 (func (param (ref $5) i32 i64 f64 f64 (ref eq) v128) (result i64))))
+;; CHECK-NEXT:  (type $5 (type $5 (array (mut i32))))
+;; CHECK-NEXT: )
+;; CHECK-NEXT: (rec
+;; CHECK-NEXT:  (type $6 (type $6 (array (mut funcref))))
+;; CHECK-NEXT:  (type $7 (type $7 (func (param f64) (result i64))))
+;; CHECK-NEXT: )
+;; CHECK-NEXT: (rec
+;; CHECK-NEXT:  (type $8 (type $8 (struct_subtype (field f64 (ref $2) f64 (mut (ref null $9))) $1)))
+;; CHECK-NEXT:  (type $9 (type $9 (func_subtype (param (ref array) i32 i64 f64 f64 anyref v128) (result i64) $4)))
+;; CHECK-NEXT: )
+;; CHECK-NEXT: (rec
+;; CHECK-NEXT:  (type $10 (type $10 (func_subtype (param (ref eq) i32 i64 f64 f64 anyref v128) (result i64) $9)))
+;; CHECK-NEXT:  (type $11 (type $11 (array_subtype (mut funcref) $6)))
+;; CHECK-NEXT:  (type $12 (type $12 (array nullref)))
+;; CHECK-NEXT:  (type $13 none)
+;; CHECK-NEXT:  (type $14 (type $14 (array (ref $6))))
+;; CHECK-NEXT:  (type $15 (type $15 (array i32)))
+;; CHECK-NEXT: )
+;; CHECK-NEXT: (rec
+;; CHECK-NEXT:  (type $16 (type $16 (array_subtype nullref $12)))
+;; CHECK-NEXT:  (type $17 (type $17 (func (param (ref null $9)) (result f32 structref))))
+;; CHECK-NEXT:  (type $18 none)
+;; CHECK-NEXT: )
+;; CHECK-NEXT: (type $19 (type $19 (func_subtype (param (ref any) i32 i64 f64 f64 anyref v128) (result i64) $9)))
diff --git a/test/lit/fuzz-types/nominal.test b/test/lit/fuzz-types/nominal.test
index 27d6a969c..613e73b52 100644
--- a/test/lit/fuzz-types/nominal.test
+++ b/test/lit/fuzz-types/nominal.test
@@ -20,3 +20,27 @@
 ;; CHECK-NEXT: (type $17 (array (mut (ref $2))))
 ;; CHECK-NEXT: (type $18 (array (ref $10)))
 ;; CHECK-NEXT: (type $19 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64 (mut f32)) $0))
+;; CHECK-NEXT:
+;; CHECK-NEXT: Inhabitable types:
+;; CHECK-NEXT:
+;; CHECK-NEXT: Built 20 types:
+;; CHECK-NEXT: (type $0 (type $0 (struct (field (mut i16) i31ref f32 f32 f64))))
+;; CHECK-NEXT: (type $1 (type $1 (func (param f64 v128))))
+;; CHECK-NEXT: (type $2 (type $2 (struct (field (mut (ref null $19)) f64 arrayref))))
+;; CHECK-NEXT: (type $3 (type $3 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64) $0)))
+;; CHECK-NEXT: (type $4 (type $4 (struct)))
+;; CHECK-NEXT: (type $5 none)
+;; CHECK-NEXT: (type $6 (type $6 (array (mut eqref))))
+;; CHECK-NEXT: (type $7 (type $7 (func_subtype (param f64 v128) $1)))
+;; CHECK-NEXT: (type $8 (type $8 (array anyref)))
+;; CHECK-NEXT: (type $9 (type $9 (array f32)))
+;; CHECK-NEXT: (type $10 (type $10 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64) $0)))
+;; CHECK-NEXT: (type $11 (type $11 (func (result f64))))
+;; CHECK-NEXT: (type $12 (type $12 (func_subtype (param f64 v128) $1)))
+;; CHECK-NEXT: (type $13 (type $13 (func_subtype (param f64 v128) $12)))
+;; CHECK-NEXT: (type $14 (type $14 (func_subtype (result f64) $11)))
+;; CHECK-NEXT: (type $15 (type $15 (func_subtype (result f64) $14)))
+;; CHECK-NEXT: (type $16 (type $16 (func (param (ref struct)) (result structref))))
+;; CHECK-NEXT: (type $17 (type $17 (array (mut (ref $2)))))
+;; CHECK-NEXT: (type $18 (type $18 (array (ref $10))))
+;; CHECK-NEXT: (type $19 (type $19 (struct_subtype (field (mut i16) (ref i31) f32 f32 f64 (mut f32)) $0)))