Generate heap type names when printing types (#4503)

The previous printing system in the Types API would print the full recursive
structure of a Type or HeapType with special markers using de Bruijn indices to
avoid infinite recursion and a separate special marker for when the size
exceeded an arbitrary upper limit. In practice, the types printed by that system
were not human readable, so all that complexity was not useful.

Replace that system with a new system that always emits a HeapType name rather
than recursing into the structure of inner HeapTypes. Add methods for printing
Types and HeapTypes with custom HeapType name generators. Also add a new
wasm-type-printing.h header with off-the-shelf type name generators that
implement simple naming schemes sufficient for tests and the type fuzzer.

Note that these new printing methods and the old printing methods they augment
are not used for emitting text modules. Printing types as part of expressions
and modules is handled by separate code in Print.cpp and the printing API
modified in this PR is mostly used for debugging. However, the new printing
methods are general enough that Print.cpp should be able to use them as well, so
update the format used to print types in the modified printing system to match
the text format in anticipation of making that change in a follow-up PR.

6 files changed, 238 insertions, 195 deletions

diff --git a/test/example/type-builder-nominal.cpp b/test/example/type-builder-nominal.cpp
index 470415fa6..f83648b74 100644
--- a/test/example/type-builder-nominal.cpp
+++ b/test/example/type-builder-nominal.cpp
@@ -1,6 +1,7 @@
 #include <cassert>
 #include <iostream>
 
+#include "wasm-type-printing.h"
 #include "wasm-type.h"
 
 using namespace wasm;
@@ -29,23 +30,31 @@ void test_builder() {
   Struct struct_({Field(refNullArray, Immutable), Field(rttArray, Mutable)});
   Array array(Field(refNullExt, Mutable));
 
+  IndexedTypeNameGenerator print(builder);
+
   std::cout << "Before setting heap types:\n";
-  std::cout << "(ref $sig) => " << refSig << "\n";
-  std::cout << "(ref $struct) => " << refStruct << "\n";
-  std::cout << "(ref $array) => " << refArray << "\n";
-  std::cout << "(ref null $array) => " << refNullArray << "\n";
-  std::cout << "(rtt 0 $array) => " << rttArray << "\n\n";
+  std::cout << "$sig => " << print(builder[0]) << "\n";
+  std::cout << "$struct => " << print(builder[1]) << "\n";
+  std::cout << "$array => " << print(builder[2]) << "\n";
+  std::cout << "(ref $sig) => " << print(refSig) << "\n";
+  std::cout << "(ref $struct) => " << print(refStruct) << "\n";
+  std::cout << "(ref $array) => " << print(refArray) << "\n";
+  std::cout << "(ref null $array) => " << print(refNullArray) << "\n";
+  std::cout << "(rtt 0 $array) => " << print(rttArray) << "\n\n";
 
   builder[0] = sig;
   builder[1] = struct_;
   builder[2] = array;
 
   std::cout << "After setting heap types:\n";
-  std::cout << "(ref $sig) => " << refSig << "\n";
-  std::cout << "(ref $struct) => " << refStruct << "\n";
-  std::cout << "(ref $array) => " << refArray << "\n";
-  std::cout << "(ref null $array) => " << refNullArray << "\n";
-  std::cout << "(rtt 0 $array) => " << rttArray << "\n\n";
+  std::cout << "$sig => " << print(builder[0]) << "\n";
+  std::cout << "$struct => " << print(builder[1]) << "\n";
+  std::cout << "$array => " << print(builder[2]) << "\n";
+  std::cout << "(ref $sig) => " << print(refSig) << "\n";
+  std::cout << "(ref $struct) => " << print(refStruct) << "\n";
+  std::cout << "(ref $array) => " << print(refArray) << "\n";
+  std::cout << "(ref null $array) => " << print(refNullArray) << "\n";
+  std::cout << "(rtt 0 $array) => " << print(rttArray) << "\n\n";
 
   std::vector<HeapType> built = *builder.build();
 
@@ -55,12 +64,17 @@ void test_builder() {
   Type newRefNullArray = Type(built[2], Nullable);
   Type newRttArray = Type(Rtt(0, built[2]));
 
+  print = IndexedTypeNameGenerator(built);
+
   std::cout << "After building types:\n";
-  std::cout << "(ref $sig) => " << newRefSig << "\n";
-  std::cout << "(ref $struct) => " << newRefStruct << "\n";
-  std::cout << "(ref $array) => " << newRefArray << "\n";
-  std::cout << "(ref null $array) => " << newRefNullArray << "\n";
-  std::cout << "(rtt 0 $array) => " << newRttArray << "\n\n";
+  std::cout << "$sig => " << print(built[0]) << "\n";
+  std::cout << "$struct => " << print(built[1]) << "\n";
+  std::cout << "$array => " << print(built[2]) << "\n";
+  std::cout << "(ref $sig) => " << print(newRefSig) << "\n";
+  std::cout << "(ref $struct) => " << print(newRefStruct) << "\n";
+  std::cout << "(ref $array) => " << print(newRefArray) << "\n";
+  std::cout << "(ref null $array) => " << print(newRefNullArray) << "\n";
+  std::cout << "(rtt 0 $array) => " << print(newRttArray) << "\n\n";
 }
 
 // Check that the builder works when there are duplicate definitions
@@ -161,7 +175,8 @@ void test_recursive() {
       builder[0] = Signature(Type::none, temp);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n\n";
     assert(built[0] == built[0].getSignature().results.getHeapType());
     assert(Type(built[0], Nullable) == built[0].getSignature().results);
   }
@@ -177,8 +192,9 @@ void test_recursive() {
       builder[1] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[1]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
     assert(built[0] != built[1]);
@@ -201,11 +217,12 @@ void test_recursive() {
       builder[4] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n";
-    std::cout << built[2] << "\n";
-    std::cout << built[3] << "\n";
-    std::cout << built[4] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n";
+    std::cout << print(built[2]) << "\n";
+    std::cout << print(built[3]) << "\n";
+    std::cout << print(built[4]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[1]);
     assert(built[1].getSignature().results.getHeapType() == built[2]);
     assert(built[2].getSignature().results.getHeapType() == built[3]);
@@ -243,12 +260,13 @@ void test_recursive() {
       builder[5] = Signature(Type::none, temp1);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n";
-    std::cout << built[2] << "\n";
-    std::cout << built[3] << "\n";
-    std::cout << built[4] << "\n";
-    std::cout << built[5] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n";
+    std::cout << print(built[2]) << "\n";
+    std::cout << print(built[3]) << "\n";
+    std::cout << print(built[4]) << "\n";
+    std::cout << print(built[5]) << "\n\n";
     assert(built[0] != built[1]);
     assert(built[2] != built[3]);
     assert(built[4] != built[5]);
@@ -270,8 +288,9 @@ void test_recursive() {
       builder[1] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[0]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
     assert(built[0] != built[1]);
diff --git a/test/example/type-builder-nominal.txt b/test/example/type-builder-nominal.txt
index ff3e1c5fe..8d1fe67e4 100644
--- a/test/example/type-builder-nominal.txt
+++ b/test/example/type-builder-nominal.txt
@@ -1,96 +1,114 @@
 ;; Test TypeBuilder
 Before setting heap types:
-(ref $sig) => [T](ref [T](func))
-(ref $struct) => [T](ref [T](func))
-(ref $array) => [T](ref [T](func))
-(ref null $array) => [T](ref null [T](func))
-(rtt 0 $array) => [T](rtt 0 [T](func))
+$sig => (; temp ;) (func_subtype func)
+$struct => (; temp ;) (func_subtype func)
+$array => (; temp ;) (func_subtype func)
+(ref $sig) => (; temp ;) (ref $0)
+(ref $struct) => (; temp ;) (ref $1)
+(ref $array) => (; temp ;) (ref $2)
+(ref null $array) => (; temp ;) (ref null $2)
+(rtt 0 $array) => (; temp ;) (rtt 0 $2)
 
 After setting heap types:
-(ref $sig) => [T](ref [T](func (param [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))) (result [T](ref [T](array (mut externref))) i32)))
-(ref $struct) => [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))
-(ref $array) => [T](ref [T](array (mut externref)))
-(ref null $array) => [T](ref null [T](array (mut externref)))
-(rtt 0 $array) => [T](rtt 0 [T](array (mut externref)))
+$sig => (; temp ;) (func_subtype (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32) func)
+$struct => (; temp ;) (struct_subtype (field (; temp ;) (ref null $2) (mut (; temp ;) (rtt 0 $2))) data)
+$array => (; temp ;) (array_subtype (mut externref) data)
+(ref $sig) => (; temp ;) (ref $0)
+(ref $struct) => (; temp ;) (ref $1)
+(ref $array) => (; temp ;) (ref $2)
+(ref null $array) => (; temp ;) (ref null $2)
+(rtt 0 $array) => (; temp ;) (rtt 0 $2)
 
 After building types:
-(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
-(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))
-(ref $array) => (ref (array (mut externref)))
-(ref null $array) => (ref null (array (mut externref)))
-(rtt 0 $array) => (rtt 0 (array (mut externref)))
+$sig => (func_subtype (param (ref $1)) (result (ref $2) i32) func)
+$struct => (struct_subtype (field (ref null $2) (mut (rtt 0 $2))) data)
+$array => (array_subtype (mut externref) data)
+(ref $sig) => (ref $0)
+(ref $struct) => (ref $1)
+(ref $array) => (ref $2)
+(ref null $array) => (ref null $2)
+(rtt 0 $array) => (rtt 0 $2)
 
 ;; Test canonicalization
 ;; Test basic
 ;; Test canonical signatures
 ;; Test recursive types
-(func (result (ref null ...1)))
+(func_subtype (result (ref null $0)) func)
 
-(func (result (ref null (func (result (ref null ...3))))))
-(func (result (ref null (func (result (ref null ...3))))))
+(func_subtype (result (ref null $1)) func)
+(func_subtype (result (ref null $0)) func)
 
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func_subtype (result (ref null $1)) func)
+(func_subtype (result (ref null $2)) func)
+(func_subtype (result (ref null $3)) func)
+(func_subtype (result (ref null $4)) func)
+(func_subtype (result (ref null $0)) func)
 
-(func (result (ref null ...1) (ref null (func))))
-(func (result (ref null ...1) (ref null (func))))
-(func)
-(func)
-(func (result (ref null (func (result ...1 (ref null (func)))))))
-(func (result (ref null (func (result ...1 (ref null (func)))))))
+(func_subtype (result (ref null $0) (ref null $2)) func)
+(func_subtype (result (ref null $1) (ref null $3)) func)
+(func_subtype func)
+(func_subtype func)
+(func_subtype (result (ref null $0)) func)
+(func_subtype (result (ref null $1)) func)
 
-(func (result (ref null ...1)))
-(func (result (ref null (func (result ...1)))))
+(func_subtype (result (ref null $0)) func)
+(func_subtype (result (ref null $0)) func)
 
 ;; Test subtyping
 ;; Test TypeBuilder
 Before setting heap types:
-(ref $sig) => [T](ref [T](func))
-(ref $struct) => [T](ref [T](func))
-(ref $array) => [T](ref [T](func))
-(ref null $array) => [T](ref null [T](func))
-(rtt 0 $array) => [T](rtt 0 [T](func))
+$sig => (; temp ;) (func_subtype func)
+$struct => (; temp ;) (func_subtype func)
+$array => (; temp ;) (func_subtype func)
+(ref $sig) => (; temp ;) (ref $0)
+(ref $struct) => (; temp ;) (ref $1)
+(ref $array) => (; temp ;) (ref $2)
+(ref null $array) => (; temp ;) (ref null $2)
+(rtt 0 $array) => (; temp ;) (rtt 0 $2)
 
 After setting heap types:
-(ref $sig) => [T](ref [T](func (param [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))) (result [T](ref [T](array (mut externref))) i32)))
-(ref $struct) => [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))
-(ref $array) => [T](ref [T](array (mut externref)))
-(ref null $array) => [T](ref null [T](array (mut externref)))
-(rtt 0 $array) => [T](rtt 0 [T](array (mut externref)))
+$sig => (; temp ;) (func_subtype (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32) func)
+$struct => (; temp ;) (struct_subtype (field (; temp ;) (ref null $2) (mut (; temp ;) (rtt 0 $2))) data)
+$array => (; temp ;) (array_subtype (mut externref) data)
+(ref $sig) => (; temp ;) (ref $0)
+(ref $struct) => (; temp ;) (ref $1)
+(ref $array) => (; temp ;) (ref $2)
+(ref null $array) => (; temp ;) (ref null $2)
+(rtt 0 $array) => (; temp ;) (rtt 0 $2)
 
 After building types:
-(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
-(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))
-(ref $array) => (ref (array (mut externref)))
-(ref null $array) => (ref null (array (mut externref)))
-(rtt 0 $array) => (rtt 0 (array (mut externref)))
+$sig => (func_subtype (param (ref $1)) (result (ref $2) i32) func)
+$struct => (struct_subtype (field (ref null $2) (mut (rtt 0 $2))) data)
+$array => (array_subtype (mut externref) data)
+(ref $sig) => (ref $0)
+(ref $struct) => (ref $1)
+(ref $array) => (ref $2)
+(ref null $array) => (ref null $2)
+(rtt 0 $array) => (rtt 0 $2)
 
 ;; Test canonicalization
 ;; Test basic
 ;; Test canonical signatures
 ;; Test recursive types
-(func (result (ref null ...1)))
-
-(func (result (ref null (func (result (ref null ...3))))))
-(func (result (ref null (func (result (ref null ...3))))))
-
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-
-(func (result (ref null ...1) (ref null (func))))
-(func (result (ref null ...1) (ref null (func))))
-(func)
-(func)
-(func (result (ref null (func (result ...1 (ref null (func)))))))
-(func (result (ref null (func (result ...1 (ref null (func)))))))
-
-(func (result (ref null ...1)))
-(func (result (ref null (func (result ...1)))))
+(func_subtype (result (ref null $0)) func)
+
+(func_subtype (result (ref null $1)) func)
+(func_subtype (result (ref null $0)) func)
+
+(func_subtype (result (ref null $1)) func)
+(func_subtype (result (ref null $2)) func)
+(func_subtype (result (ref null $3)) func)
+(func_subtype (result (ref null $4)) func)
+(func_subtype (result (ref null $0)) func)
+
+(func_subtype (result (ref null $0) (ref null $2)) func)
+(func_subtype (result (ref null $1) (ref null $3)) func)
+(func_subtype func)
+(func_subtype func)
+(func_subtype (result (ref null $0)) func)
+(func_subtype (result (ref null $1)) func)
+
+(func_subtype (result (ref null $0)) func)
+(func_subtype (result (ref null $0)) func)
 
 ;; Test subtyping
diff --git a/test/example/type-builder.cpp b/test/example/type-builder.cpp
index 3c6c8eeda..318e48f2e 100644
--- a/test/example/type-builder.cpp
+++ b/test/example/type-builder.cpp
@@ -1,6 +1,7 @@
 #include <cassert>
 #include <iostream>
 
+#include "wasm-type-printing.h"
 #include "wasm-type.h"
 
 using namespace wasm;
@@ -77,7 +78,8 @@ void test_recursive() {
       builder[0] = Signature(Type::none, temp);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n\n";
     assert(built[0] == built[0].getSignature().results.getHeapType());
     assert(Type(built[0], Nullable) == built[0].getSignature().results);
   }
@@ -93,8 +95,9 @@ void test_recursive() {
       builder[1] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[1]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
     assert(built[0] == built[1]);
@@ -117,11 +120,12 @@ void test_recursive() {
       builder[4] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n";
-    std::cout << built[2] << "\n";
-    std::cout << built[3] << "\n";
-    std::cout << built[4] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n";
+    std::cout << print(built[2]) << "\n";
+    std::cout << print(built[3]) << "\n";
+    std::cout << print(built[4]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[1]);
     assert(built[1].getSignature().results.getHeapType() == built[2]);
     assert(built[2].getSignature().results.getHeapType() == built[3]);
@@ -153,12 +157,13 @@ void test_recursive() {
       builder[5] = Signature(Type::none, temp1);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n";
-    std::cout << built[2] << "\n";
-    std::cout << built[3] << "\n";
-    std::cout << built[4] << "\n";
-    std::cout << built[5] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n";
+    std::cout << print(built[2]) << "\n";
+    std::cout << print(built[3]) << "\n";
+    std::cout << print(built[4]) << "\n";
+    std::cout << print(built[5]) << "\n\n";
     assert(built[0] == built[1]);
     assert(built[2] == built[3]);
     assert(built[4] == built[5]);
@@ -180,8 +185,9 @@ void test_recursive() {
       builder[1] = Signature(Type::none, temp0);
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[0]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
     assert(built[0] == built[1]);
@@ -199,8 +205,9 @@ void test_recursive() {
       builder[2] = HeapType::any;
       built = *builder.build();
     }
-    std::cout << built[0] << "\n";
-    std::cout << built[1] << "\n\n";
+    IndexedTypeNameGenerator print(built);
+    std::cout << print(built[0]) << "\n";
+    std::cout << print(built[1]) << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[0]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
     assert(built[0].getSignature().params == Type::anyref);
diff --git a/test/example/type-builder.txt b/test/example/type-builder.txt
index df67b599d..372e531a1 100644
--- a/test/example/type-builder.txt
+++ b/test/example/type-builder.txt
@@ -1,56 +1,56 @@
 ;; Test canonicalization
 ;; Test basic
 ;; Test recursive types
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1) (ref null (func))))
-(func (result (ref null ...1) (ref null (func))))
+(func (result (ref null $0) (ref null $2)))
+(func (result (ref null $0) (ref null $2)))
 (func)
 (func)
-(func (result (ref null (func (result ...1 (ref null (func)))))))
-(func (result (ref null (func (result ...1 (ref null (func)))))))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (param anyref) (result (ref null ...1)))
-(func (param anyref) (result (ref null ...1)))
+(func (param anyref) (result (ref null $0)))
+(func (param anyref) (result (ref null $0)))
 
 ;; Test LUBs
 ;; Test canonicalization
 ;; Test basic
 ;; Test recursive types
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1) (ref null (func))))
-(func (result (ref null ...1) (ref null (func))))
+(func (result (ref null $0) (ref null $2)))
+(func (result (ref null $0) (ref null $2)))
 (func)
 (func)
-(func (result (ref null (func (result ...1 (ref null (func)))))))
-(func (result (ref null (func (result ...1 (ref null (func)))))))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (result (ref null ...1)))
-(func (result (ref null ...1)))
+(func (result (ref null $0)))
+(func (result (ref null $0)))
 
-(func (param anyref) (result (ref null ...1)))
-(func (param anyref) (result (ref null ...1)))
+(func (param anyref) (result (ref null $0)))
+(func (param anyref) (result (ref null $0)))
 
 ;; Test LUBs
diff --git a/test/example/typeinfo.cpp b/test/example/typeinfo.cpp
index ae40ad188..dd8e13d43 100644
--- a/test/example/typeinfo.cpp
+++ b/test/example/typeinfo.cpp
@@ -317,7 +317,6 @@ void test_printing() {
     std::cout << tuple << "\n";
     std::cout << Type(tuple) << "\n";
   }
-  // TODO: Think about recursive types. Currently impossible to construct.
   {
     std::cout << "\n;; Recursive (not really)\n";
     Signature signatureSignature(Type::none, Type::none);
diff --git a/test/example/typeinfo.txt b/test/example/typeinfo.txt
index c205ce431..552e59e58 100644
--- a/test/example/typeinfo.txt
+++ b/test/example/typeinfo.txt
@@ -20,27 +20,27 @@ i31ref
 
 ;; Signature
 (func)
-(ref (func))
-(ref null (func))
+(ref $func.0)
+(ref null $func.0)
 (func (param i32) (result f64))
-(ref (func (param i32) (result f64)))
-(ref null (func (param i32) (result f64)))
+(ref $func.0)
+(ref null $func.0)
 
 ;; Struct
 (struct)
-(ref (struct))
-(ref null (struct))
+(ref $struct.0)
+(ref null $struct.0)
 (struct (field i32 i64 (mut f32) (mut f64) externref))
-(ref (struct (field i32 i64 (mut f32) (mut f64) externref)))
-(ref null (struct (field i32 i64 (mut f32) (mut f64) externref)))
+(ref $struct.0)
+(ref null $struct.0)
 
 ;; Array
 (array i32)
-(ref (array i32))
-(ref null (array i32))
+(ref $array.0)
+(ref null $array.0)
 (array (mut externref))
-(ref (array (mut externref)))
-(ref null (array (mut externref)))
+(ref $array.0)
+(ref null $array.0)
 
 ;; Tuple
 ()
@@ -59,50 +59,50 @@ none
 (rtt 3 eq)
 (rtt 4 i31)
 (rtt 4 i31)
-(rtt 6 (func))
-(rtt 6 (func))
-(rtt 7 (struct))
-(rtt 7 (struct))
-(rtt 8 (array i32))
-(rtt 8 (array i32))
+(rtt 6 $func.0)
+(rtt 6 $func.0)
+(rtt 7 $struct.0)
+(rtt 7 $struct.0)
+(rtt 8 $array.0)
+(rtt 8 $array.0)
 
 ;; Signature of references (param/result)
-(func (param (ref null (struct))) (result (ref (array (mut i32)))))
+(func (param (ref null $struct.0)) (result (ref $array.0)))
 
 ;; Signature of references (params/results)
-(func (param (ref null (struct)) (ref (array (mut i32)))) (result (ref (struct)) (ref null (array i32))))
+(func (param (ref null $struct.0) (ref $array.0)) (result (ref $struct.0) (ref null $array.1)))
 
 ;; Struct of references
-(struct (field (ref (func)) (mut (ref (func))) (ref null (func)) (mut (ref null (func)))))
-(ref (struct (field (ref (func)) (mut (ref (func))) (ref null (func)) (mut (ref null (func))))))
-(ref null (struct (field (ref (func)) (mut (ref (func))) (ref null (func)) (mut (ref null (func))))))
-(struct (field (ref (struct)) (mut (ref (struct))) (ref null (struct)) (mut (ref null (struct)))))
-(ref (struct (field (ref (struct)) (mut (ref (struct))) (ref null (struct)) (mut (ref null (struct))))))
-(ref null (struct (field (ref (struct)) (mut (ref (struct))) (ref null (struct)) (mut (ref null (struct))))))
-(struct (field (ref (array i32)) (mut (ref (array i32))) (ref null (array i32)) (mut (ref null (array i32)))))
-(ref (struct (field (ref (array i32)) (mut (ref (array i32))) (ref null (array i32)) (mut (ref null (array i32))))))
-(ref null (struct (field (ref (array i32)) (mut (ref (array i32))) (ref null (array i32)) (mut (ref null (array i32))))))
-(struct (field (mut i32) (mut (ref null (func))) (mut (ref null (struct))) (mut (ref null (array (mut i32))))))
-(ref (struct (field (mut i32) (mut (ref null (func))) (mut (ref null (struct))) (mut (ref null (array (mut i32)))))))
-(ref null (struct (field (mut i32) (mut (ref null (func))) (mut (ref null (struct))) (mut (ref null (array (mut i32)))))))
+(struct (field (ref $func.0) (mut (ref $func.0)) (ref null $func.0) (mut (ref null $func.0))))
+(ref $struct.0)
+(ref null $struct.0)
+(struct (field (ref $struct.0) (mut (ref $struct.0)) (ref null $struct.0) (mut (ref null $struct.0))))
+(ref $struct.0)
+(ref null $struct.0)
+(struct (field (ref $array.0) (mut (ref $array.0)) (ref null $array.0) (mut (ref null $array.0))))
+(ref $struct.0)
+(ref null $struct.0)
+(struct (field (mut i32) (mut (ref null $func.0)) (mut (ref null $struct.0)) (mut (ref null $array.0))))
+(ref $struct.0)
+(ref null $struct.0)
 
 ;; Array of references
-(array (ref null (func)))
-(ref (array (ref null (func))))
-(ref null (array (ref null (func))))
-(array (mut (ref null (struct))))
-(ref (array (mut (ref null (struct)))))
-(ref null (array (mut (ref null (struct)))))
-(array (ref null (array i32)))
-(ref (array (ref null (array i32))))
-(ref null (array (ref null (array i32))))
+(array (ref null $func.0))
+(ref $array.0)
+(ref null $array.0)
+(array (mut (ref null $struct.0)))
+(ref $array.0)
+(ref null $array.0)
+(array (ref null $array.0))
+(ref $array.0)
+(ref null $array.0)
 
 ;; Tuple of references
-((ref (func)) (ref null (func)) (ref (struct)) (ref null (struct)) (ref (array i32)) (ref null (array i32)))
-((ref (func)) (ref null (func)) (ref (struct)) (ref null (struct)) (ref (array i32)) (ref null (array i32)))
+((ref $func.0) (ref null $func.0) (ref $struct.0) (ref null $struct.0) (ref $array.0) (ref null $array.0))
+((ref $func.0) (ref null $func.0) (ref $struct.0) (ref null $struct.0) (ref $array.0) (ref null $array.0))
 
 ;; Recursive (not really)
-(func (param (ref (func))))
-(ref (func (param (ref (func)))))
-(func (param (ref (array (ref (func))))))
-(ref (func (param (ref (array (ref (func)))))))
+(func (param (ref $func.0)))
+(ref $func.0)
+(func (param (ref $array.0)))
+(ref $func.0)