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, 330 insertions, 103 deletions

diff --git a/src/support/index.h b/src/support/index.h
new file mode 100644
index 000000000..c4177286a
--- /dev/null
+++ b/src/support/index.h
@@ -0,0 +1,29 @@
+/*
+ * 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_support_index_h
+#define wasm_support_index_h
+
+#include <cstdint>
+
+namespace wasm {
+
+// An index in a wasm module
+using Index = uint32_t;
+
+} // namespace wasm
+
+#endif // wasm_support_index_h
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index 983d949d0..4b1f2800e 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -21,6 +21,7 @@
 #include "support/command-line.h"
 #include "tools/fuzzing/heap-types.h"
 #include "tools/fuzzing/random.h"
+#include "wasm-type-printing.h"
 
 namespace wasm {
 
@@ -79,8 +80,28 @@ void Fuzzer::run(uint64_t seed) {
 
 void Fuzzer::printTypes(const std::vector<HeapType>& types) {
   std::cout << "Built " << types.size() << " types:\n";
+  struct FatalTypeNameGenerator
+    : TypeNameGeneratorBase<FatalTypeNameGenerator> {
+    TypeNames getNames(HeapType type) {
+      Fatal() << "trying to print unknown heap type";
+    }
+  };
+  IndexedTypeNameGenerator<FatalTypeNameGenerator> print(types);
+  std::unordered_map<HeapType, size_t> seen;
   for (size_t i = 0; i < types.size(); ++i) {
-    std::cout << i << ": " << types[i] << "\n";
+    auto type = types[i];
+    std::cout << "(type $" << i << ' ';
+    if (type.isBasic()) {
+      std::cout << print(type) << ")\n";
+      continue;
+    }
+    auto [it, inserted] = seen.insert({type, i});
+    if (inserted) {
+      std::cout << print(type);
+    } else {
+      std::cout << "identical to $" << it->second;
+    }
+    std::cout << ")\n";
   }
 }
 
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
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 8c8d85ebf..29e5114b7 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -17,14 +17,18 @@
 #ifndef wasm_wasm_type_h
 #define wasm_wasm_type_h
 
-#include "support/name.h"
-#include "support/parent_index_iterator.h"
-#include "wasm-features.h"
+#include <functional>
 #include <optional>
 #include <ostream>
+#include <string>
 #include <variant>
 #include <vector>
 
+#include "support/index.h"
+#include "support/name.h"
+#include "support/parent_index_iterator.h"
+#include "wasm-features.h"
+
 // TODO: At various code locations we were assuming that single types are basic
 // types, but this is going to change with the introduction of the compound
 // Signature, Struct and Array types that will be single but not basic. To
@@ -68,6 +72,17 @@ struct Rtt;
 enum Nullability { NonNullable, Nullable };
 enum Mutability { Immutable, Mutable };
 
+// HeapType name information used for printing.
+struct TypeNames {
+  // The name of the type.
+  Name name;
+  // For a Struct, names of fields.
+  std::unordered_map<Index, Name> fieldNames;
+};
+
+// Used to generate HeapType names.
+using HeapTypeNameGenerator = std::function<TypeNames(HeapType)>;
+
 // The type used for interning IDs in the public interfaces of Type and
 // HeapType.
 using TypeID = uint64_t;
@@ -271,6 +286,22 @@ public:
     return lub;
   }
 
+  // Helper allowing the value of `print(...)` to be sent to an ostream. Stores
+  // a `TypeID` because `Type` is incomplete at this point and using a reference
+  // makes it less convenient to use.
+  struct Printed {
+    TypeID typeID;
+    HeapTypeNameGenerator generateName;
+  };
+
+  // Given a function for generating non-basic HeapType names, print this Type
+  // to `os`.`generateName` should return the same name each time it is called
+  // with the same HeapType and it should return different names for different
+  // types.
+  Printed print(HeapTypeNameGenerator generateName) {
+    return Printed{getID(), generateName};
+  }
+
   std::string toString() const;
 
   size_t size() const;
@@ -385,6 +416,22 @@ public:
   // Return the LUB of two HeapTypes. The LUB always exists.
   static HeapType getLeastUpperBound(HeapType a, HeapType b);
 
+  // Helper allowing the value of `print(...)` to be sent to an ostream. Stores
+  // a `TypeID` because `Type` is incomplete at this point and using a reference
+  // makes it less convenient to use.
+  struct Printed {
+    TypeID typeID;
+    HeapTypeNameGenerator generateName;
+  };
+
+  // Given a function for generating HeapType names, print the definition of
+  // this HeapType to `os`. `generateName` should return the same
+  // name each time it is called with the same HeapType and it should return
+  // different names for different types.
+  Printed print(HeapTypeNameGenerator generateName) {
+    return Printed{getID(), generateName};
+  }
+
   std::string toString() const;
 };
 
@@ -667,7 +714,9 @@ struct TypeBuilder {
 };
 
 std::ostream& operator<<(std::ostream&, Type);
+std::ostream& operator<<(std::ostream&, Type::Printed);
 std::ostream& operator<<(std::ostream&, HeapType);
+std::ostream& operator<<(std::ostream&, HeapType::Printed);
 std::ostream& operator<<(std::ostream&, Tuple);
 std::ostream& operator<<(std::ostream&, Signature);
 std::ostream& operator<<(std::ostream&, Field);
diff --git a/src/wasm.h b/src/wasm.h
index 18662ad8e..153cb4764 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -34,6 +34,7 @@
 
 #include "literal.h"
 #include "mixed_arena.h"
+#include "support/index.h"
 #include "support/name.h"
 #include "wasm-features.h"
 #include "wasm-type.h"
@@ -1971,14 +1972,6 @@ public:
   // Module name, if specified. Serves a documentary role only.
   Name name;
 
-  // Optional type name information, used in printing only. Note that Types are
-  // globally interned, but type names are specific to a module.
-  struct TypeNames {
-    // The name of the type.
-    Name name;
-    // For a Struct, names of fields.
-    std::unordered_map<Index, Name> fieldNames;
-  };
   std::unordered_map<HeapType, TypeNames> typeNames;
 
   MixedArena allocator;
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 27480ce68..04b1122b6 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -28,6 +28,7 @@
 #include "support/hash.h"
 #include "support/insert_ordered.h"
 #include "wasm-features.h"
+#include "wasm-type-printing.h"
 #include "wasm-type.h"
 
 #define TRACE_CANONICALIZATION 0
@@ -196,42 +197,43 @@ private:
   std::optional<Rtt> lub(const Rtt& a, const Rtt& b);
 };
 
-// Helper for printing types without infinitely recursing on recursive types.
+// Helper for printing types.
 struct TypePrinter {
-  size_t currDepth = 0;
-  std::unordered_map<TypeID, size_t> depths;
+  // Whether to print explicit supertypes.
+  bool printSupertypes;
 
   // The stream we are printing to.
   std::ostream& os;
 
-  TypePrinter(std::ostream& os) : os(os) {}
+  // The default generator state if no other generator is provided.
+  std::optional<DefaultTypeNameGenerator> defaultGenerator;
+
+  // The function we call to get HeapType names.
+  HeapTypeNameGenerator generator;
+
+  TypePrinter(std::ostream& os, HeapTypeNameGenerator generator)
+    : printSupertypes(getTypeSystem() != TypeSystem::Equirecursive), os(os),
+      defaultGenerator(), generator(generator) {}
+  TypePrinter(std::ostream& os)
+    : TypePrinter(
+        os, [&](HeapType type) { return defaultGenerator->getNames(type); }) {
+    defaultGenerator = DefaultTypeNameGenerator{};
+  }
+
+  void printHeapTypeName(HeapType type);
+  void printSupertypeOr(std::optional<HeapType> super, std::string other);
 
   std::ostream& print(Type type);
-  std::ostream& print(HeapType heapType);
+  std::ostream& print(HeapType type);
   std::ostream& print(const Tuple& tuple);
   std::ostream& print(const Field& field);
-  std::ostream& print(const Signature& sig);
-  std::ostream& print(const Struct& struct_);
-  std::ostream& print(const Array& array);
+  std::ostream& print(const Signature& sig,
+                      std::optional<HeapType> super = std::nullopt);
+  std::ostream& print(const Struct& struct_,
+                      std::optional<HeapType> super = std::nullopt);
+  std::ostream& print(const Array& array,
+                      std::optional<HeapType> super = std::nullopt);
   std::ostream& print(const Rtt& rtt);
-
-private:
-  template<typename T, typename F> std::ostream& printChild(T curr, F printer);
-
-  // FIXME: This hard limit on how many times we call print() avoids extremely
-  //        large outputs, which can be inconveniently large in some cases, but
-  //        we should have a better mechanism for this.
-  static const size_t MaxPrints = 100;
-
-  size_t prints = 0;
-
-  bool exceededLimit() {
-    if (prints >= MaxPrints) {
-      return true;
-    }
-    prints++;
-    return false;
-  }
 };
 
 // Helper for hashing the shapes of TypeInfos and HeapTypeInfos. Keeps track of
@@ -1461,6 +1463,25 @@ size_t RecGroup::size() const {
   }
 }
 
+TypeNames DefaultTypeNameGenerator::getNames(HeapType type) {
+  auto [it, inserted] = nameCache.insert({type, {}});
+  if (inserted) {
+    // Generate a new name for this type we have not previously seen.
+    std::stringstream stream;
+    if (type.isSignature()) {
+      stream << "func." << funcCount++;
+    } else if (type.isStruct()) {
+      stream << "struct." << structCount++;
+    } else if (type.isArray()) {
+      stream << "array." << arrayCount++;
+    } else {
+      WASM_UNREACHABLE("unexpected kind");
+    }
+    it->second = {stream.str(), {}};
+  }
+  return it->second;
+}
+
 template<typename T> static std::string genericToString(const T& t) {
   std::ostringstream ss;
   ss << t;
@@ -1473,11 +1494,18 @@ std::string Signature::toString() const { return genericToString(*this); }
 std::string Struct::toString() const { return genericToString(*this); }
 std::string Array::toString() const { return genericToString(*this); }
 std::string Rtt::toString() const { return genericToString(*this); }
+
 std::ostream& operator<<(std::ostream& os, Type type) {
   return TypePrinter(os).print(type);
 }
-std::ostream& operator<<(std::ostream& os, HeapType heapType) {
-  return TypePrinter(os).print(heapType);
+std::ostream& operator<<(std::ostream& os, Type::Printed printed) {
+  return TypePrinter(os, printed.generateName).print(Type(printed.typeID));
+}
+std::ostream& operator<<(std::ostream& os, HeapType type) {
+  return TypePrinter(os).print(type);
+}
+std::ostream& operator<<(std::ostream& os, HeapType::Printed printed) {
+  return TypePrinter(os, printed.generateName).print(HeapType(printed.typeID));
 }
 std::ostream& operator<<(std::ostream& os, Tuple tuple) {
   return TypePrinter(os).print(tuple);
@@ -1944,22 +1972,21 @@ std::optional<Rtt> TypeBounder::lub(const Rtt& a, const Rtt& b) {
   return Rtt(depth, a.heapType);
 }
 
-template<typename T, typename F>
-std::ostream& TypePrinter::printChild(T curr, F printer) {
-  if (exceededLimit()) {
-    return os << "..!";
+void TypePrinter::printHeapTypeName(HeapType type) {
+  if (type.isBasic()) {
+    print(type);
+    return;
   }
-  auto it = depths.find(curr.getID());
-  if (it != depths.end()) {
-    assert(it->second <= currDepth);
-    size_t relativeDepth = currDepth - it->second;
-    return os << "..." << relativeDepth;
+  os << '$' << generator(type).name;
+}
+
+void TypePrinter::printSupertypeOr(std::optional<HeapType> super,
+                                   std::string other) {
+  if (super) {
+    printHeapTypeName(*super);
+  } else {
+    os << other;
   }
-  depths[curr.getID()] = ++currDepth;
-  printer();
-  depths.erase(curr.getID());
-  --currDepth;
-  return os;
 }
 
 std::ostream& TypePrinter::print(Type type) {
@@ -1994,33 +2021,32 @@ std::ostream& TypePrinter::print(Type type) {
     }
   }
 
-  return printChild(type, [&]() {
-    if (isTemp(type)) {
-      os << "[T]";
-    }
+  if (isTemp(type)) {
+    os << "(; temp ;) ";
+  }
 #if TRACE_CANONICALIZATION
-    os << "[" << ((type.getID() >> 4) % 1000) << "]";
+  os << "(;" << ((type.getID() >> 4) % 1000) << ";) ";
 #endif
-    if (type.isTuple()) {
-      print(type.getTuple());
-    } else if (type.isRef()) {
-      os << "(ref ";
-      if (type.isNullable()) {
-        os << "null ";
-      }
-      print(type.getHeapType());
-      os << ')';
-    } else if (type.isRtt()) {
-      print(type.getRtt());
-    } else {
-      WASM_UNREACHABLE("unexpected type");
-    }
-  });
+  if (type.isTuple()) {
+    print(type.getTuple());
+  } else if (type.isRef()) {
+    os << "(ref ";
+    if (type.isNullable()) {
+      os << "null ";
+    }
+    printHeapTypeName(type.getHeapType());
+    os << ')';
+  } else if (type.isRtt()) {
+    print(type.getRtt());
+  } else {
+    WASM_UNREACHABLE("unexpected type");
+  }
+  return os;
 }
 
-std::ostream& TypePrinter::print(HeapType heapType) {
-  if (heapType.isBasic()) {
-    switch (heapType.getBasic()) {
+std::ostream& TypePrinter::print(HeapType type) {
+  if (type.isBasic()) {
+    switch (type.getBasic()) {
       case HeapType::func:
         return os << "func";
       case HeapType::ext:
@@ -2036,29 +2062,25 @@ std::ostream& TypePrinter::print(HeapType heapType) {
     }
   }
 
-  return printChild(heapType, [&]() {
-    if (isTemp(heapType)) {
-      os << "[T]";
-    }
+  if (isTemp(type)) {
+    os << "(; temp ;) ";
+  }
 #if TRACE_CANONICALIZATION
-    os << "[" << ((heapType.getID() >> 4) % 1000) << "]";
-    if (auto super = heapType.getSuperType()) {
-      os << "[super " << ((super->getID() >> 4) % 1000) << "]";
-    }
+  os << "(;" << ((type.getID() >> 4) % 1000) << ";)";
 #endif
-    if (getHeapTypeInfo(heapType)->kind == HeapTypeInfo::BasicKind) {
-      os << '*';
-      print(getHeapTypeInfo(heapType)->basic);
-    } else if (heapType.isSignature()) {
-      print(heapType.getSignature());
-    } else if (heapType.isStruct()) {
-      print(heapType.getStruct());
-    } else if (heapType.isArray()) {
-      print(heapType.getArray());
-    } else {
-      WASM_UNREACHABLE("unexpected type");
-    }
-  });
+  if (getHeapTypeInfo(type)->kind == HeapTypeInfo::BasicKind) {
+    os << "(; noncanonical ;) ";
+    print(getHeapTypeInfo(type)->basic);
+  } else if (type.isSignature()) {
+    print(type.getSignature(), type.getSuperType());
+  } else if (type.isStruct()) {
+    print(type.getStruct(), type.getSuperType());
+  } else if (type.isArray()) {
+    print(type.getArray(), type.getSuperType());
+  } else {
+    WASM_UNREACHABLE("unexpected type");
+  }
+  return os;
 }
 
 std::ostream& TypePrinter::print(const Tuple& tuple) {
@@ -2094,7 +2116,8 @@ std::ostream& TypePrinter::print(const Field& field) {
   return os;
 }
 
-std::ostream& TypePrinter::print(const Signature& sig) {
+std::ostream& TypePrinter::print(const Signature& sig,
+                                 std::optional<HeapType> super) {
   auto printPrefixed = [&](const char* prefix, Type type) {
     os << '(' << prefix;
     for (Type t : type) {
@@ -2105,6 +2128,9 @@ std::ostream& TypePrinter::print(const Signature& sig) {
   };
 
   os << "(func";
+  if (printSupertypes) {
+    os << "_subtype";
+  }
   if (sig.params.getID() != Type::none) {
     os << ' ';
     printPrefixed("param", sig.params);
@@ -2113,11 +2139,19 @@ std::ostream& TypePrinter::print(const Signature& sig) {
     os << ' ';
     printPrefixed("result", sig.results);
   }
+  if (printSupertypes) {
+    os << ' ';
+    printSupertypeOr(super, "func");
+  }
   return os << ')';
 }
 
-std::ostream& TypePrinter::print(const Struct& struct_) {
+std::ostream& TypePrinter::print(const Struct& struct_,
+                                 std::optional<HeapType> super) {
   os << "(struct";
+  if (printSupertypes) {
+    os << "_subtype";
+  }
   if (struct_.fields.size()) {
     os << " (field";
   }
@@ -2128,12 +2162,25 @@ std::ostream& TypePrinter::print(const Struct& struct_) {
   if (struct_.fields.size()) {
     os << ')';
   }
+  if (printSupertypes) {
+    os << ' ';
+    printSupertypeOr(super, "data");
+  }
   return os << ')';
 }
 
-std::ostream& TypePrinter::print(const Array& array) {
-  os << "(array ";
+std::ostream& TypePrinter::print(const Array& array,
+                                 std::optional<HeapType> super) {
+  os << "(array";
+  if (printSupertypes) {
+    os << "_subtype";
+  }
+  os << ' ';
   print(array.element);
+  if (printSupertypes) {
+    os << ' ';
+    printSupertypeOr(super, "data");
+  }
   return os << ')';
 }
 
@@ -2142,7 +2189,7 @@ std::ostream& TypePrinter::print(const Rtt& rtt) {
   if (rtt.hasDepth()) {
     os << rtt.depth << ' ';
   }
-  print(rtt.heapType);
+  printHeapTypeName(rtt.heapType);
   return os << ')';
 }