summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/wasm-type.h4
-rw-r--r--src/wasm/wasm-type.cpp145
-rw-r--r--test/gtest/type-builder.cpp53
3 files changed, 153 insertions, 49 deletions
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 4c050ed35..7b63adf9d 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -594,6 +594,10 @@ struct TypeBuilder {
SelfSupertype,
// The declared supertype of a type is invalid.
InvalidSupertype,
+ // The declared supertype is an invalid forward reference.
+ ForwardSupertypeReference,
+ // A child of the type is an invalid forward reference.
+ ForwardChildReference,
};
struct Error {
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index b69977426..475e2e714 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -1323,6 +1323,10 @@ std::ostream& operator<<(std::ostream& os, TypeBuilder::ErrorReason reason) {
return os << "Heap type is a supertype of itself";
case TypeBuilder::ErrorReason::InvalidSupertype:
return os << "Heap type has an invalid supertype";
+ case TypeBuilder::ErrorReason::ForwardSupertypeReference:
+ return os << "Heap type has an undeclared supertype";
+ case TypeBuilder::ErrorReason::ForwardChildReference:
+ return os << "Heap type has an undeclared child";
}
WASM_UNREACHABLE("Unexpected error reason");
}
@@ -3113,6 +3117,50 @@ void canonicalizeEquirecursive(CanonicalizationState& state) {
}
std::optional<TypeBuilder::Error>
+validateStructuralSubtyping(const std::vector<HeapType>& types) {
+ for (size_t i = 0; i < types.size(); ++i) {
+ HeapType type = types[i];
+ if (type.isBasic()) {
+ continue;
+ }
+ auto* sub = getHeapTypeInfo(type);
+ auto* super = sub->supertype;
+ if (super == nullptr) {
+ continue;
+ }
+
+ auto fail = [&]() {
+ return TypeBuilder::Error{i, TypeBuilder::ErrorReason::InvalidSupertype};
+ };
+
+ if (sub->kind != super->kind) {
+ return fail();
+ }
+ SubTyper typer;
+ switch (sub->kind) {
+ case HeapTypeInfo::BasicKind:
+ WASM_UNREACHABLE("unexpected kind");
+ case HeapTypeInfo::SignatureKind:
+ if (!typer.isSubType(sub->signature, super->signature)) {
+ return fail();
+ }
+ break;
+ case HeapTypeInfo::StructKind:
+ if (!typer.isSubType(sub->struct_, super->struct_)) {
+ return fail();
+ }
+ break;
+ case HeapTypeInfo::ArrayKind:
+ if (!typer.isSubType(sub->array, super->array)) {
+ return fail();
+ }
+ break;
+ }
+ }
+ return {};
+}
+
+std::optional<TypeBuilder::Error>
canonicalizeNominal(CanonicalizationState& state) {
// TODO: clear recursion groups once we are no longer piggybacking the
// isorecursive system on the nominal system.
@@ -3150,45 +3198,9 @@ canonicalizeNominal(CanonicalizationState& state) {
checked.insert(path.begin(), path.end());
}
- // Ensure that all the subtype relations are valid.
- for (size_t i = 0; i < state.results.size(); ++i) {
- HeapType type = state.results[i];
- if (type.isBasic()) {
- continue;
- }
- auto* sub = getHeapTypeInfo(type);
- auto* super = sub->supertype;
- if (super == nullptr) {
- continue;
- }
-
- auto fail = [&]() {
- return TypeBuilder::Error{i, TypeBuilder::ErrorReason::InvalidSupertype};
- };
-
- if (sub->kind != super->kind) {
- return fail();
- }
- SubTyper typer;
- switch (sub->kind) {
- case HeapTypeInfo::BasicKind:
- WASM_UNREACHABLE("unexpected kind");
- case HeapTypeInfo::SignatureKind:
- if (!typer.isSubType(sub->signature, super->signature)) {
- return fail();
- }
- break;
- case HeapTypeInfo::StructKind:
- if (!typer.isSubType(sub->struct_, super->struct_)) {
- return fail();
- }
- break;
- case HeapTypeInfo::ArrayKind:
- if (!typer.isSubType(sub->array, super->array)) {
- return fail();
- }
- break;
- }
+ // Check that the declared supertypes are valid.
+ if (auto error = validateStructuralSubtyping(state.results)) {
+ return {*error};
}
#if TIME_CANONICALIZATION
@@ -3212,10 +3224,57 @@ std::optional<TypeBuilder::Error> canonicalizeIsorecursive(
}
}
- // TODO: proper isorecursive validation and canonicalization. For now just
- // piggyback on the nominal system.
- if (auto err = canonicalizeNominal(state)) {
- return err;
+ // Check that supertypes precede their subtypes and that other child types
+ // either precede their parents or appear later in the same recursion group.
+ // `indexOfType` both maps types to their indices and keeps track of which
+ // types we have seen so far.
+ std::unordered_map<HeapType, size_t> indexOfType;
+ std::optional<RecGroup> currGroup;
+ size_t groupStart = 0;
+
+ // Validate the children of all types in a recursion group after all the types
+ // have been registered in `indexOfType`.
+ auto finishGroup = [&](size_t groupEnd) -> std::optional<TypeBuilder::Error> {
+ for (size_t index = groupStart; index < groupEnd; ++index) {
+ HeapType type = state.results[index];
+ for (HeapType child : type.getHeapTypeChildren()) {
+ // Only basic children, globally canonical children, and children
+ // defined in this or previous recursion groups are allowed.
+ if (isTemp(child) && !indexOfType.count(child)) {
+ return {{index, TypeBuilder::ErrorReason::ForwardChildReference}};
+ }
+ }
+ }
+ groupStart = groupEnd;
+ return {};
+ };
+
+ for (size_t index = 0; index < state.results.size(); ++index) {
+ HeapType type = state.results[index];
+ // Validate the supertype. Supertypes must precede their subtypes.
+ if (auto super = type.getSuperType()) {
+ if (!indexOfType.count(*super)) {
+ return {{index, TypeBuilder::ErrorReason::ForwardSupertypeReference}};
+ }
+ }
+ // Check whether we have finished a rec group.
+ auto newGroup = type.getRecGroup();
+ if (currGroup && *currGroup != newGroup) {
+ if (auto error = finishGroup(index)) {
+ return *error;
+ }
+ }
+ currGroup = newGroup;
+ // Register this type as seen.
+ indexOfType.insert({type, index});
+ }
+ if (auto error = finishGroup(state.results.size())) {
+ return *error;
+ }
+
+ // Check that the declared supertypes are structurally valid.
+ if (auto error = validateStructuralSubtyping(state.results)) {
+ return {*error};
}
// Move the recursion groups into the global store. TODO: after proper
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 9f1a99c5d..78c8037a4 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -155,7 +155,12 @@ static void testDirectSelfSupertype() {
const auto* error = result.getError();
ASSERT_TRUE(error);
- EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype);
+ if (getTypeSystem() == TypeSystem::Nominal) {
+ EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype);
+ } else if (getTypeSystem() == TypeSystem::Isorecursive) {
+ EXPECT_EQ(error->reason,
+ TypeBuilder::ErrorReason::ForwardSupertypeReference);
+ }
EXPECT_EQ(error->index, 0u);
}
@@ -176,7 +181,14 @@ static void testIndirectSelfSupertype() {
const auto* error = result.getError();
ASSERT_TRUE(error);
- EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype);
+ if (getTypeSystem() == TypeSystem::Nominal) {
+ EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::SelfSupertype);
+ } else if (getTypeSystem() == TypeSystem::Isorecursive) {
+ EXPECT_EQ(error->reason,
+ TypeBuilder::ErrorReason::ForwardSupertypeReference);
+ } else {
+ WASM_UNREACHABLE("unexpected type system");
+ }
EXPECT_EQ(error->index, 0u);
}
@@ -186,9 +198,9 @@ 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]);
+ builder[0] = Struct({Field(Type::i32, Immutable)});
+ builder[1] = Struct{};
+ builder[1].subTypeOf(builder[0]);
auto result = builder.build();
EXPECT_FALSE(result);
@@ -196,8 +208,37 @@ static void testInvalidSupertype() {
const auto* error = result.getError();
ASSERT_TRUE(error);
EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::InvalidSupertype);
- EXPECT_EQ(error->index, 0u);
+ EXPECT_EQ(error->index, 1u);
}
TEST_F(NominalTest, InvalidSupertype) { testInvalidSupertype(); }
TEST_F(IsorecursiveTest, InvalidSupertype) { testInvalidSupertype(); }
+
+TEST_F(IsorecursiveTest, SelfReferencedChild) {
+ // A self-referential type should be ok even without an explicit rec group.
+ TypeBuilder builder(1);
+ Type selfRef = builder.getTempRefType(builder[0], Nullable);
+ builder[0] = Struct({Field(selfRef, Immutable)});
+ auto result = builder.build();
+ EXPECT_TRUE(result);
+}
+
+TEST_F(IsorecursiveTest, ForwardReferencedChild) {
+ TypeBuilder builder(3);
+ builder.createRecGroup(0, 2);
+ Type refA1 = builder.getTempRefType(builder[1], Nullable);
+ Type refB0 = builder.getTempRefType(builder[2], Nullable);
+ // Forward reference to same group is ok.
+ builder[0] = Struct({Field(refA1, Mutable)});
+ // Forward reference to different group is not ok.
+ builder[1] = Struct({Field(refB0, Mutable)});
+ builder[2] = Struct{};
+
+ auto result = builder.build();
+ EXPECT_FALSE(result);
+
+ const auto* error = result.getError();
+ ASSERT_TRUE(error);
+ EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::ForwardChildReference);
+ EXPECT_EQ(error->index, 1u);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-07 09:09:03 +0000