TypeBuilder (#3418)

Introduce TypeBuilder, a utility for constructing heap types in terms of other
heap types that may have not yet been defined. Internally, it works by creating
HeapTypes backed by mutable HeapTypeInfos owned by the TypeBuilder. That lets
the TypeBuilder create temporary Types that can refer to the TypeBuilder-managed
HeapTypes. Those temporary Types can in turn be used to initialize the very
HeapTypes they refer to. Since the TypeBuilder-managed HeapTypes are only valid
for the lifetime of their TypeBuilder, there is a canonicalization step that
converts them into globally interned canonical HeapTypes.

This PR allows HeapTypes to be built in terms of as of yet undefined HeapTypes,
but it currently errors out in the presence of recursive types. Supporting
recursive types will require further work to canonicalize them into finite,
acyclic representations. Currently any attempt to compare, print, or otherwise
manipulate recursive types would infinitely recurse.

2 files changed, 166 insertions, 0 deletions

diff --git a/test/example/type-builder.cpp b/test/example/type-builder.cpp
new file mode 100644
index 000000000..145ec4787
--- /dev/null
+++ b/test/example/type-builder.cpp
@@ -0,0 +1,142 @@
+#include <cassert>
+#include <iostream>
+
+#include "wasm-type.h"
+
+using namespace wasm;
+
+// Construct Signature, Struct, and Array heap types using undefined types.
+void test_builder() {
+  std::cout << ";; Test TypeBuilder\n";
+
+  // (type $sig (func (param (ref $struct)) (result (ref $array) i32)))
+  // (type $struct (struct (field (ref null $array) (mut rtt 0 $array))))
+  // (type $array (array (mut externref)))
+
+  TypeBuilder builder(3);
+
+  Type refSig = builder.getTempRefType(0, false);
+  Type refStruct = builder.getTempRefType(1, false);
+  Type refArray = builder.getTempRefType(2, false);
+  Type refNullArray = builder.getTempRefType(2, true);
+  Type rttArray = builder.getTempRttType(2, 0);
+  Type refNullExt(HeapType::ext, true);
+
+  Signature sig(refStruct, builder.getTempTupleType({refArray, Type::i32}));
+  Struct struct_({Field(refNullArray, false), Field(rttArray, true)});
+  Array array(Field(refNullExt, true));
+
+  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";
+
+  builder.setHeapType(0, sig);
+  builder.setHeapType(1, struct_);
+  builder.setHeapType(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::vector<HeapType> built = builder.build();
+
+  Type newRefSig = Type(built[0], false);
+  Type newRefStruct = Type(built[1], false);
+  Type newRefArray = Type(built[2], false);
+  Type newRefNullArray = Type(built[2], true);
+  Type newRttArray = Type(Rtt(0, built[2]));
+
+  assert(refSig != newRefSig);
+  assert(refStruct != newRefStruct);
+  assert(refArray != newRefArray);
+  assert(refNullArray != newRefNullArray);
+  assert(rttArray != newRttArray);
+
+  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";
+}
+
+// Check that the builder works when there are duplicate definitions
+void test_canonicalization() {
+  std::cout << ";; Test canonicalization\n";
+
+  // (type $struct (struct (field (ref null $sig))))
+  // (type $sig (func))
+  HeapType sig = Signature(Type::none, Type::none);
+  HeapType struct_ = Struct({Field(Type(sig, true), false)});
+
+  TypeBuilder builder(4);
+
+  Type tempSigRef1 = builder.getTempRefType(2, true);
+  Type tempSigRef2 = builder.getTempRefType(3, true);
+
+  assert(tempSigRef1 != tempSigRef2);
+  assert(tempSigRef1 != Type(sig, true));
+  assert(tempSigRef2 != Type(sig, true));
+
+  builder.setHeapType(0, Struct({Field(tempSigRef1, false)}));
+  builder.setHeapType(1, Struct({Field(tempSigRef2, false)}));
+  builder.setHeapType(2, Signature(Type::none, Type::none));
+  builder.setHeapType(3, Signature(Type::none, Type::none));
+
+  std::vector<HeapType> built = builder.build();
+
+  assert(built[0] == struct_);
+  assert(built[1] == struct_);
+  assert(built[2] == sig);
+  assert(built[3] == sig);
+}
+
+void test_recursive() {
+  std::cout << ";; Test recursive types\n";
+
+  {
+    // Trivial recursion
+    TypeBuilder builder(1);
+    Type temp = builder.getTempRefType(0, true);
+    builder.setHeapType(0, Signature(Type::none, temp));
+    // std::vector<HeapType> built = builder.build();
+  }
+
+  {
+    // Mutual recursion
+    TypeBuilder builder(2);
+    Type temp0 = builder.getTempRefType(0, true);
+    Type temp1 = builder.getTempRefType(1, true);
+    builder.setHeapType(0, Signature(Type::none, temp1));
+    builder.setHeapType(1, Signature(Type::none, temp0));
+    // std::vector<HeapType> built = builder.build();
+  }
+
+  {
+    // A longer chain of recursion
+    TypeBuilder builder(5);
+    Type temp0 = builder.getTempRefType(0, true);
+    Type temp1 = builder.getTempRefType(1, true);
+    Type temp2 = builder.getTempRefType(2, true);
+    Type temp3 = builder.getTempRefType(3, true);
+    Type temp4 = builder.getTempRefType(4, true);
+    builder.setHeapType(0, Signature(Type::none, temp1));
+    builder.setHeapType(1, Signature(Type::none, temp2));
+    builder.setHeapType(2, Signature(Type::none, temp3));
+    builder.setHeapType(3, Signature(Type::none, temp4));
+    builder.setHeapType(4, Signature(Type::none, temp0));
+    // std::vector<HeapType> built = builder.build();
+  }
+}
+
+int main() {
+  test_builder();
+  test_canonicalization();
+  test_recursive();
+}
diff --git a/test/example/type-builder.txt b/test/example/type-builder.txt
new file mode 100644
index 000000000..0cb414be1
--- /dev/null
+++ b/test/example/type-builder.txt
@@ -0,0 +1,24 @@
+;; Test TypeBuilder
+Before setting heap types:
+(ref $sig) => (ref (func))
+(ref $struct) => (ref (func))
+(ref $array) => (ref (func))
+(ref null $array) => (ref null (func))
+(rtt 0 $array) => (rtt 0 (func))
+
+After setting heap 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)))
+
+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)))
+
+;; Test canonicalization
+;; Test recursive types