diff options
-rw-r--r-- | src/ir/type-updating.cpp | 3 | ||||
-rw-r--r-- | src/tools/wasm-fuzz-types.cpp | 7 | ||||
-rw-r--r-- | src/wasm-type.h | 27 | ||||
-rw-r--r-- | src/wasm/wasm-binary.cpp | 6 | ||||
-rw-r--r-- | src/wasm/wasm-s-parser.cpp | 6 | ||||
-rw-r--r-- | src/wasm/wasm-type.cpp | 63 | ||||
-rw-r--r-- | test/example/type-builder-nominal.cpp | 32 | ||||
-rw-r--r-- | test/example/type-builder.cpp | 20 | ||||
-rw-r--r-- | test/gtest/type-builder.cpp | 62 |
9 files changed, 172 insertions, 54 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 diff --git a/test/example/type-builder-nominal.cpp b/test/example/type-builder-nominal.cpp index 5d3bcc17c..470415fa6 100644 --- a/test/example/type-builder-nominal.cpp +++ b/test/example/type-builder-nominal.cpp @@ -47,7 +47,7 @@ void test_builder() { std::cout << "(ref null $array) => " << refNullArray << "\n"; std::cout << "(rtt 0 $array) => " << rttArray << "\n\n"; - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); Type newRefSig = Type(built[0], NonNullable); Type newRefStruct = Type(built[1], NonNullable); @@ -89,7 +89,7 @@ void test_canonicalization() { builder[2] = Signature(Type::none, Type::none); builder[3] = Signature(Type::none, Type::none); - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); assert(built[0] != struct_); assert(built[1] != struct_); @@ -115,7 +115,7 @@ void test_basic() { builder[4] = HeapType::any; builder[5] = HeapType::i31; - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); assert(built[0].getSignature() == Signature(Type::anyref, Type::i31ref)); assert(built[1].getSignature() == built[0].getSignature()); @@ -134,7 +134,7 @@ void test_signatures(bool warm) { Type tempRef = builder.getTempRefType(builder[0], Nullable); builder[0] = Signature(Type::i31ref, Type::anyref); builder[1] = Signature(tempRef, tempRef); - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); HeapType small = Signature(Type::i31ref, Type::anyref); HeapType big = @@ -159,7 +159,7 @@ void test_recursive() { TypeBuilder builder(1); Type temp = builder.getTempRefType(builder[0], Nullable); builder[0] = Signature(Type::none, temp); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n\n"; assert(built[0] == built[0].getSignature().results.getHeapType()); @@ -175,7 +175,7 @@ void test_recursive() { Type temp1 = builder.getTempRefType(builder[1], Nullable); builder[0] = Signature(Type::none, temp1); builder[1] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n\n"; @@ -199,7 +199,7 @@ void test_recursive() { builder[2] = Signature(Type::none, temp3); builder[3] = Signature(Type::none, temp4); builder[4] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n"; @@ -241,7 +241,7 @@ void test_recursive() { builder[3] = Signature(); builder[4] = Signature(Type::none, temp0); builder[5] = Signature(Type::none, temp1); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n"; @@ -268,7 +268,7 @@ void test_recursive() { Type temp0 = builder.getTempRefType(builder[0], Nullable); builder[0] = Signature(Type::none, temp0); builder[1] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n\n"; @@ -322,7 +322,7 @@ void test_subtypes() { builder[0] = Signature(Type::none, Type::none); builder[1] = Struct{}; builder[2] = Array(Field(Type::i32, Mutable)); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[0], built[0]) == built[0]); assert(LUB(built[1], built[1]) == built[1]); @@ -341,7 +341,7 @@ void test_subtypes() { builder[2] = Signature(Type::none, Type::anyref); builder[3] = Signature(Type::none, structRef0); builder[4] = Signature(Type::none, structRef1); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[0], built[1]) == HeapType::data); assert(LUB(built[2], built[3]) == HeapType::func); @@ -357,7 +357,7 @@ void test_subtypes() { builder[0] = Struct{}; builder[1] = Struct{}; builder[2] = Struct{}; - built = builder.build(); + built = *builder.build(); } assert(LUB(built[0], built[2]) == HeapType::data); } @@ -378,7 +378,7 @@ void test_subtypes() { builder[3] = Signature(Type::i32, Type::anyref); builder[4] = Array(Field(Type::i32, Mutable)); builder[5] = Array(Field(Type::i32, Mutable)); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[0], built[1]) == built[1]); assert(LUB(built[2], built[3]) == built[3]); @@ -394,7 +394,7 @@ void test_subtypes() { builder[1] = Struct({Field(Type::i32, Immutable), Field(Type::i32, Immutable)}); builder[1].subTypeOf(builder[0]); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[1], built[0]) == built[0]); } @@ -407,7 +407,7 @@ void test_subtypes() { builder[0] = Struct({Field(Type::anyref, Immutable)}); builder[1] = Struct({Field(Type::funcref, Immutable)}); builder[1].subTypeOf(builder[0]); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[1], built[0]) == built[0]); } @@ -427,7 +427,7 @@ void test_subtypes() { builder[1] = Struct({Field(d, Immutable)}); builder[2] = Struct({Field(a, Immutable)}); builder[3] = Struct({Field(b, Immutable)}); - built = builder.build(); + built = *builder.build(); } assert(LUB(built[0], built[1]) == built[0]); assert(LUB(built[2], built[3]) == built[2]); diff --git a/test/example/type-builder.cpp b/test/example/type-builder.cpp index 0fba565f1..3c6c8eeda 100644 --- a/test/example/type-builder.cpp +++ b/test/example/type-builder.cpp @@ -31,7 +31,7 @@ void test_canonicalization() { builder[2] = Signature(Type::none, Type::none); builder[3] = Signature(Type::none, Type::none); - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); assert(built[0] == struct_); assert(built[1] == struct_); @@ -55,7 +55,7 @@ void test_basic() { builder[4] = HeapType::any; builder[5] = HeapType::i31; - std::vector<HeapType> built = builder.build(); + std::vector<HeapType> built = *builder.build(); assert(built[0] == Signature(Type::anyref, Type::i31ref)); assert(built[1] == built[0]); @@ -75,7 +75,7 @@ void test_recursive() { TypeBuilder builder(1); Type temp = builder.getTempRefType(builder[0], Nullable); builder[0] = Signature(Type::none, temp); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n\n"; assert(built[0] == built[0].getSignature().results.getHeapType()); @@ -91,7 +91,7 @@ void test_recursive() { Type temp1 = builder.getTempRefType(builder[1], Nullable); builder[0] = Signature(Type::none, temp1); builder[1] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n\n"; @@ -115,7 +115,7 @@ void test_recursive() { builder[2] = Signature(Type::none, temp3); builder[3] = Signature(Type::none, temp4); builder[4] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n"; @@ -151,7 +151,7 @@ void test_recursive() { builder[3] = Signature(); builder[4] = Signature(Type::none, temp0); builder[5] = Signature(Type::none, temp1); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n"; @@ -178,7 +178,7 @@ void test_recursive() { Type temp0 = builder.getTempRefType(builder[0], Nullable); builder[0] = Signature(Type::none, temp0); builder[1] = Signature(Type::none, temp0); - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n\n"; @@ -197,7 +197,7 @@ void test_recursive() { builder[0] = Signature(anyref, temp0); builder[1] = Signature(anyref, temp0); builder[2] = HeapType::any; - built = builder.build(); + built = *builder.build(); } std::cout << built[0] << "\n"; std::cout << built[1] << "\n\n"; @@ -379,7 +379,7 @@ void test_lub() { Struct({Field(tempB, Immutable), Field(Type::eqref, Immutable)}); builder[1] = Struct({Field(tempA, Immutable), Field(Type::funcref, Immutable)}); - auto built = builder.build(); + auto built = *builder.build(); Type a(built[0], Nullable); Type b(built[1], Nullable); @@ -387,7 +387,7 @@ void test_lub() { Type tempLub = builder.getTempRefType(lubBuilder[0], Nullable); lubBuilder[0] = Struct({Field(tempLub, Immutable), Field(Type::anyref, Immutable)}); - built = lubBuilder.build(); + built = *lubBuilder.build(); Type lub(built[0], Nullable); assert(LUB(a, b) == lub); diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp index 1030dc9d4..9f1a99c5d 100644 --- a/test/gtest/type-builder.cpp +++ b/test/gtest/type-builder.cpp @@ -112,7 +112,9 @@ TEST_F(EquirecursiveTest, Basics) { builder[1] = struct_; builder[2] = array; - std::vector<HeapType> built = builder.build(); + auto result = builder.build(); + ASSERT_TRUE(result); + std::vector<HeapType> built = *result; ASSERT_EQ(built.size(), size_t{3}); // The built types should have the correct kinds. @@ -141,3 +143,61 @@ TEST_F(EquirecursiveTest, Basics) { EXPECT_NE(newRefNullArray, refNullArray); EXPECT_NE(newRttArray, rttArray); } + +static void testDirectSelfSupertype() { + // Type is directly a supertype of itself. + TypeBuilder builder(1); + builder[0] = Struct{}; + builder[0].subTypeOf(builder[0]); + + auto result = builder.build(); + EXPECT_FALSE(result); + + const auto* error = result.getError(); + ASSERT_TRUE(error); + EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype); + EXPECT_EQ(error->index, 0u); +} + +TEST_F(NominalTest, DirectSelfSupertype) { testDirectSelfSupertype(); } +TEST_F(IsorecursiveTest, DirectSelfSupertype) { testDirectSelfSupertype(); } + +static void testIndirectSelfSupertype() { + // Type is indirectly a supertype of itself. + TypeBuilder builder(2); + builder.createRecGroup(0, 2); + builder[0] = Struct{}; + builder[1] = Struct{}; + builder[0].subTypeOf(builder[1]); + builder[1].subTypeOf(builder[0]); + + auto result = builder.build(); + EXPECT_FALSE(result); + + const auto* error = result.getError(); + ASSERT_TRUE(error); + EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype); + EXPECT_EQ(error->index, 0u); +} + +TEST_F(NominalTest, IndirectSelfSupertype) { testIndirectSelfSupertype(); } +TEST_F(IsorecursiveTest, IndirectSelfSupertype) { testIndirectSelfSupertype(); } + +static void testInvalidSupertype() { + TypeBuilder builder(2); + builder.createRecGroup(0, 2); + builder[0] = Struct{}; + builder[1] = Struct({Field(Type::i32, Immutable)}); + builder[0].subTypeOf(builder[1]); + + auto result = builder.build(); + EXPECT_FALSE(result); + + const auto* error = result.getError(); + ASSERT_TRUE(error); + EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::InvalidSupertype); + EXPECT_EQ(error->index, 0u); +} + +TEST_F(NominalTest, InvalidSupertype) { testInvalidSupertype(); } +TEST_F(IsorecursiveTest, InvalidSupertype) { testInvalidSupertype(); } |