summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/type-updating.cpp3
-rw-r--r--src/tools/wasm-fuzz-types.cpp7
-rw-r--r--src/wasm-type.h27
-rw-r--r--src/wasm/wasm-binary.cpp6
-rw-r--r--src/wasm/wasm-s-parser.cpp6
-rw-r--r--src/wasm/wasm-type.cpp63
6 files changed, 85 insertions, 27 deletions
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 3516a10a9..10b8f1bb8 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -74,7 +74,8 @@ void GlobalTypeRewriter::update() {
}
}
- auto newTypes = typeBuilder.build();
+ auto buildResults = typeBuilder.build();
+ auto& newTypes = *buildResults;
// Map the old types to the new ones. This uses the fact that type indices
// are the same in the old and new types, that is, we have not added or
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index d0baec748..e736c8977 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -51,7 +51,12 @@ struct Fuzzer {
// TODO: Options to control the size or set it randomly.
HeapTypeGenerator generator =
HeapTypeGenerator::create(rand, FeatureSet::All, 20);
- std::vector<HeapType> types = generator.builder.build();
+ auto result = generator.builder.build();
+ if (auto* err = result.getError()) {
+ Fatal() << "Failed to build types: " << err->reason << " at index "
+ << err->index;
+ }
+ auto types = *result;
if (verbose) {
printTypes(types);
diff --git a/src/wasm-type.h b/src/wasm-type.h
index fa5650a31..4c050ed35 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -22,6 +22,7 @@
#include "wasm-features.h"
#include <optional>
#include <ostream>
+#include <variant>
#include <vector>
// TODO: At various code locations we were assuming that single types are basic
@@ -588,12 +589,35 @@ struct TypeBuilder {
// not overlap or go out of bounds.
void createRecGroup(size_t i, size_t length);
+ enum class ErrorReason {
+ // There is a cycle in the supertype relation.
+ SelfSupertype,
+ // The declared supertype of a type is invalid.
+ InvalidSupertype,
+ };
+
+ struct Error {
+ // The index of the type causing the failure.
+ size_t index;
+ ErrorReason reason;
+ };
+
+ struct BuildResult : std::variant<std::vector<HeapType>, Error> {
+ operator bool() const {
+ return bool(std::get_if<std::vector<HeapType>>(this));
+ }
+ const std::vector<HeapType>& operator*() const {
+ return std::get<std::vector<HeapType>>(*this);
+ }
+ const Error* getError() const { return std::get_if<Error>(this); }
+ };
+
// Returns all of the newly constructed heap types. May only be called once
// all of the heap types have been initialized with `setHeapType`. In nominal
// mode, all of the constructed HeapTypes will be fresh and distinct. In
// nominal mode, will also produce a fatal error if the declared subtype
// relationships are not valid.
- std::vector<HeapType> build();
+ BuildResult build();
// Utility for ergonomically using operator[] instead of explicit setHeapType
// and getTempHeapType methods.
@@ -639,6 +663,7 @@ std::ostream& operator<<(std::ostream&, Field);
std::ostream& operator<<(std::ostream&, Struct);
std::ostream& operator<<(std::ostream&, Array);
std::ostream& operator<<(std::ostream&, Rtt);
+std::ostream& operator<<(std::ostream&, TypeBuilder::ErrorReason);
} // namespace wasm
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index b20269f9b..13bcc5110 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1989,7 +1989,11 @@ void WasmBinaryBuilder::readTypes() {
}
}
- types = builder.build();
+ auto result = builder.build();
+ if (auto* err = result.getError()) {
+ Fatal() << "Invalid type: " << err->reason << " at index " << err->index;
+ }
+ types = *result;
}
Name WasmBinaryBuilder::getFunctionName(Index index) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 01e1789cd..0cb58746c 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -934,7 +934,11 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
++index;
});
- types = builder.build();
+ auto result = builder.build();
+ if (auto* err = result.getError()) {
+ Fatal() << "Invalid type: " << err->reason << " at index " << err->index;
+ }
+ types = *result;
for (auto& [name, index] : typeIndices) {
auto type = types[index];
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 4c2922c73..b69977426 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1317,6 +1317,15 @@ std::ostream& operator<<(std::ostream& os, Array array) {
std::ostream& operator<<(std::ostream& os, Rtt rtt) {
return TypePrinter(os).print(rtt);
}
+std::ostream& operator<<(std::ostream& os, TypeBuilder::ErrorReason reason) {
+ switch (reason) {
+ case TypeBuilder::ErrorReason::SelfSupertype:
+ return os << "Heap type is a supertype of itself";
+ case TypeBuilder::ErrorReason::InvalidSupertype:
+ return os << "Heap type has an invalid supertype";
+ }
+ WASM_UNREACHABLE("Unexpected error reason");
+}
unsigned Field::getByteSize() const {
if (type != Type::i32) {
@@ -1482,7 +1491,7 @@ Type TypeBounder::getLeastUpperBound(Type a, Type b) {
// Array is arbitrary; it might as well have been a Struct.
builder.grow(1);
builder[builder.size() - 1] = Array(Field(*tempLUB, Mutable));
- std::vector<HeapType> built = builder.build();
+ std::vector<HeapType> built = *builder.build();
return built.back().getArray().element.type;
}
@@ -1498,7 +1507,7 @@ HeapType TypeBounder::getLeastUpperBound(HeapType a, HeapType b) {
++index;
}
// Canonicalize and return the LUB.
- return builder.build()[index];
+ return (*builder.build())[index];
}
std::optional<Type> TypeBounder::lub(Type a, Type b) {
@@ -1847,7 +1856,6 @@ std::ostream& TypePrinter::print(HeapType heapType) {
}
#if TRACE_CANONICALIZATION
os << "[" << ((heapType.getID() >> 4) % 1000) << "]";
- HeapType super;
if (auto super = heapType.getSuperType()) {
os << "[super " << ((super->getID() >> 4) % 1000) << "]";
}
@@ -3104,7 +3112,8 @@ void canonicalizeEquirecursive(CanonicalizationState& state) {
#endif
}
-void canonicalizeNominal(CanonicalizationState& state) {
+std::optional<TypeBuilder::Error>
+canonicalizeNominal(CanonicalizationState& state) {
// TODO: clear recursion groups once we are no longer piggybacking the
// isorecursive system on the nominal system.
// if (typeSystem != TypeSystem::Isorecursive) {
@@ -3123,24 +3132,27 @@ void canonicalizeNominal(CanonicalizationState& state) {
// Ensure there are no cycles in the subtype graph. This is the classic DFA
// algorithm for detecting cycles, but in the form of a simple loop because
// each node (type) has at most one child (supertype).
- std::unordered_set<HeapTypeInfo*> seen;
- for (auto type : state.results) {
+ std::unordered_set<HeapTypeInfo*> checked;
+ for (size_t i = 0; i < state.results.size(); ++i) {
+ HeapType type = state.results[i];
if (type.isBasic()) {
continue;
}
std::unordered_set<HeapTypeInfo*> path;
for (auto* curr = getHeapTypeInfo(type);
- seen.insert(curr).second && curr->supertype != nullptr;
+ curr != nullptr && !checked.count(curr);
curr = curr->supertype) {
if (!path.insert(curr).second) {
- Fatal() << HeapType(uintptr_t(curr))
- << " cannot be a subtype of itself";
+ return TypeBuilder::Error{i, TypeBuilder::ErrorReason::SelfSupertype};
}
}
+ // None of the types in `path` reach themselves.
+ checked.insert(path.begin(), path.end());
}
// Ensure that all the subtype relations are valid.
- for (HeapType type : state.results) {
+ for (size_t i = 0; i < state.results.size(); ++i) {
+ HeapType type = state.results[i];
if (type.isBasic()) {
continue;
}
@@ -3151,12 +3163,11 @@ void canonicalizeNominal(CanonicalizationState& state) {
}
auto fail = [&]() {
- Fatal() << type << " cannot be a subtype of "
- << HeapType(uintptr_t(super));
+ return TypeBuilder::Error{i, TypeBuilder::ErrorReason::InvalidSupertype};
};
if (sub->kind != super->kind) {
- fail();
+ return fail();
}
SubTyper typer;
switch (sub->kind) {
@@ -3164,17 +3175,17 @@ void canonicalizeNominal(CanonicalizationState& state) {
WASM_UNREACHABLE("unexpected kind");
case HeapTypeInfo::SignatureKind:
if (!typer.isSubType(sub->signature, super->signature)) {
- fail();
+ return fail();
}
break;
case HeapTypeInfo::StructKind:
if (!typer.isSubType(sub->struct_, super->struct_)) {
- fail();
+ return fail();
}
break;
case HeapTypeInfo::ArrayKind:
if (!typer.isSubType(sub->array, super->array)) {
- fail();
+ return fail();
}
break;
}
@@ -3188,9 +3199,10 @@ void canonicalizeNominal(CanonicalizationState& state) {
.count()
<< " ms\n";
#endif
+ return {};
}
-void canonicalizeIsorecursive(
+std::optional<TypeBuilder::Error> canonicalizeIsorecursive(
CanonicalizationState& state,
std::vector<std::unique_ptr<RecGroupInfo>>& recGroupInfos) {
// Fill out the recursion groups.
@@ -3202,7 +3214,9 @@ void canonicalizeIsorecursive(
// TODO: proper isorecursive validation and canonicalization. For now just
// piggyback on the nominal system.
- canonicalizeNominal(state);
+ if (auto err = canonicalizeNominal(state)) {
+ return err;
+ }
// Move the recursion groups into the global store. TODO: after proper
// isorecursive canonicalization, some groups may no longer be used, so they
@@ -3211,6 +3225,7 @@ void canonicalizeIsorecursive(
for (auto& info : recGroupInfos) {
recGroups.emplace_back(std::move(info));
}
+ return {};
}
void canonicalizeBasicHeapTypes(CanonicalizationState& state) {
@@ -3233,7 +3248,7 @@ void canonicalizeBasicHeapTypes(CanonicalizationState& state) {
} // anonymous namespace
-std::vector<HeapType> TypeBuilder::build() {
+TypeBuilder::BuildResult TypeBuilder::build() {
size_t entryCount = impl->entries.size();
// Initialize the canonicalization state using the HeapTypeInfos from the
@@ -3269,10 +3284,14 @@ std::vector<HeapType> TypeBuilder::build() {
canonicalizeEquirecursive(state);
break;
case TypeSystem::Nominal:
- canonicalizeNominal(state);
+ if (auto error = canonicalizeNominal(state)) {
+ return {*error};
+ }
break;
case TypeSystem::Isorecursive:
- canonicalizeIsorecursive(state, impl->recGroups);
+ if (auto error = canonicalizeIsorecursive(state, impl->recGroups)) {
+ return {*error};
+ }
break;
}
@@ -3298,7 +3317,7 @@ std::vector<HeapType> TypeBuilder::build() {
}
}
- return state.results;
+ return {state.results};
}
} // namespace wasm
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 00:24:22 +0000