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.

1 files changed, 88 insertions, 0 deletions

diff --git a/src/wasm-type-printing.h b/src/wasm-type-printing.h
new file mode 100644
index 000000000..fcf05db17
--- /dev/null
+++ b/src/wasm-type-printing.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright 2022 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_wasm_type_printing_h
+#define wasm_wasm_type_printing_h
+
+#include <cstddef>
+#include <iostream>
+#include <unordered_map>
+
+#include "support/name.h"
+#include "support/utilities.h"
+#include "wasm-type.h"
+
+namespace wasm {
+
+// CRTP base that all other type name generators should subclass. Provides the
+// ability to use the generator as a function to print Types and HeapTypes to
+// streams.
+template<typename Subclass> struct TypeNameGeneratorBase {
+  TypeNames getNames(HeapType type) {
+    static_assert(&TypeNameGeneratorBase<Subclass>::getNames !=
+                    &Subclass::getNames,
+                  "Derived class must implement getNames");
+    WASM_UNREACHABLE("Derived class must implement getNames");
+  }
+  HeapType::Printed operator()(HeapType type) {
+    return type.print(
+      [&](HeapType ht) { return static_cast<Subclass*>(this)->getNames(ht); });
+  }
+  Type::Printed operator()(Type type) {
+    return type.print(
+      [&](HeapType ht) { return static_cast<Subclass*>(this)->getNames(ht); });
+  }
+};
+
+// Generates names like "func.0", "struct.1", "array.2", etc. Struct fields are
+// not given names.
+struct DefaultTypeNameGenerator
+  : TypeNameGeneratorBase<DefaultTypeNameGenerator> {
+  size_t funcCount = 0;
+  size_t structCount = 0;
+  size_t arrayCount = 0;
+
+  // Cached names for types that have already been seen.
+  std::unordered_map<HeapType, TypeNames> nameCache;
+
+  TypeNames getNames(HeapType type);
+};
+
+// Generates names based on the indices of types in some collection, falling
+// back to the given FallbackGenerator when encountering a type not in the
+// collection. Struct fields are not given names.
+template<typename FallbackGenerator = DefaultTypeNameGenerator>
+struct IndexedTypeNameGenerator
+  : TypeNameGeneratorBase<IndexedTypeNameGenerator<FallbackGenerator>> {
+  FallbackGenerator fallback;
+  std::unordered_map<HeapType, TypeNames> names;
+  template<typename T> IndexedTypeNameGenerator(T& types) {
+    for (size_t i = 0; i < types.size(); ++i) {
+      names.insert({types[i], {std::to_string(i), {}}});
+    }
+  }
+  TypeNames getNames(HeapType type) {
+    if (auto it = names.find(type); it != names.end()) {
+      return it->second;
+    } else {
+      return fallback.getNames(type);
+    }
+  }
+};
+
+} // namespace wasm
+
+#endif // wasm_wasm_type_printing_h