diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/wasm-type.h | 4 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 145 |
2 files changed, 106 insertions, 43 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 |