summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/support/index.h29
-rw-r--r--src/tools/wasm-fuzz-types.cpp23
-rw-r--r--src/wasm-type-printing.h88
-rw-r--r--src/wasm-type.h55
-rw-r--r--src/wasm.h9
-rw-r--r--src/wasm/wasm-type.cpp229
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 << ')';
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-05 11:23:45 +0000