//! Implementation of matching (structural subtyping) for core Wasm types. //! //! We only ever do structural matching for one link at a time in a subtype //! chain. That is, we never recurse on new `SubType`s. This is because //! subtyping relations are required to be declared, so the earlier links in the //! chain were already checked when we processed those declarations. //! //! Note that while we don't recursively *match* on each sub- and supertype field //! when checking whether a struct type matches another struct type, we do check //! that either `field_type_a == field_type b` or that it was previously //! declared that `field_type a <: field_type b`. The latter case means that we //! previously checked that they matched when we saw the declaration, and we //! don't need to match again; we just look at the declarations from now on. use crate::{ types::{CoreTypeId, RecGroupId, TypeList}, ArrayType, CompositeInnerType, CompositeType, ContType, FieldType, FuncType, RefType, StorageType, StructType, SubType, ValType, }; /// Wasm type matching. pub trait Matches { /// Does `a` structurally match `b`? /// /// Both `a` and `b` must be canonicalized already. /// /// This is expected to recursively break down and inspect the *parts* of /// `Self` but should always bottom out in subtype checks, rather than /// looping back to new match calls on a *whole* new `Self`. This is what /// maintains the "single-link-in-the-chain" property mentioned in the /// module comment above. fn matches(types: &TypeList, a: Self, b: Self) -> bool; } /// A `T` with its containing `RecGroupId`. /// /// The `RecGroupId` can be used to resolve canonicalized type references that /// are indices into the local rec group. #[derive(Debug, Copy, Clone)] pub(crate) struct WithRecGroup { inner: T, rec_group_id: RecGroupId, } impl WithRecGroup { #[inline] fn rec_group(x: Self) -> RecGroupId { x.rec_group_id } } impl core::ops::Deref for WithRecGroup { type Target = T; #[inline] fn deref(&self) -> &T { &self.inner } } impl core::ops::DerefMut for WithRecGroup { #[inline] fn deref_mut(&mut self) -> &mut Self::Target { &mut self.inner } } impl WithRecGroup { /// Construct a new `WithRecGroup` by looking up the /// `CoreTypeId`'s rec group id in the `TypeList`. pub(crate) fn new(types: &TypeList, id: CoreTypeId) -> Self { let rec_group_id = types.rec_group_id_of(id); WithRecGroup { inner: id, rec_group_id, } } } impl WithRecGroup { /// Project into a field of the inner value, while maintaining the /// `RecGroupId` context. pub(crate) fn map(x: Self, f: impl FnOnce(T) -> U) -> WithRecGroup { WithRecGroup { inner: f(x.inner), rec_group_id: x.rec_group_id, } } } impl<'a> Matches for WithRecGroup<&'a SubType> { fn matches(types: &TypeList, a: Self, b: Self) -> bool { // NB: matching does not check finality and supertypes. That is checked // once when we define types, not repeatedly every time we check // matches. Matches::matches( types, WithRecGroup::map(a, |a| &a.composite_type), WithRecGroup::map(b, |b| &b.composite_type), ) } } impl<'a> Matches for WithRecGroup<&'a CompositeType> { fn matches(types: &TypeList, a: Self, b: Self) -> bool { use CompositeInnerType::*; if (*a).shared != (*b).shared { return false; } match (&(*a).inner, &(*b).inner) { (Func(fa), Func(fb)) => Matches::matches( types, WithRecGroup::map(a, |_| fa), WithRecGroup::map(b, |_| fb), ), (Func(_), _) => false, (Array(aa), Array(ab)) => Matches::matches( types, WithRecGroup::map(a, |_| *aa), WithRecGroup::map(b, |_| *ab), ), (Array(_), _) => false, (Struct(sa), Struct(sb)) => Matches::matches( types, WithRecGroup::map(a, |_| sa), WithRecGroup::map(b, |_| sb), ), (Struct(_), _) => false, (Cont(ca), Cont(cb)) => Matches::matches( types, WithRecGroup::map(a, |_| ca), WithRecGroup::map(b, |_| cb), ), (Cont(_), _) => false, } } } impl<'a> Matches for WithRecGroup<&'a FuncType> { fn matches(types: &TypeList, a: Self, b: Self) -> bool { if a.params().len() != b.params().len() || a.results().len() != b.results().len() { return false; } // A quick recap of covariance, contravariance, and how it applies to // subtyping function types, because I (and almost everyone else, it // seems) always need a reminder: // // *Covariance* is when `a <: b` and `a' <: b'`. That is, the subtyping // checks on the nested things (`a'` and `b'`) goes the same way as the // outer things (`a` and `b`). // // *Contravariance* is when `a <: b` and `b' <: a'`. That is, the // subtyping on the nested things is reversed compared to the outer // things. // // Now, when we are checking subtyping for function types, we have the // following variance: // // * Parameters are contravariant: `(a -> c) <: (b -> c)` when `b <: a`. // // For example, we can substitute a `Cat -> Cat` function with a // `Animal -> Cat` function because `Cat <: Animal` and so all // arguments that could be given to the function are still valid. // // We can't do the opposite and replace an `Animal -> Cat` function // with a `Cat -> Cat` function. What would the `Cat -> Cat` function // do when given a `Dog`? It is unsound. // // * Results are covariant: `(a -> b) <: (a -> c)` when `b <: c`. // // For example, we can substitute a `Cat -> Animal` function with a // `Cat -> Cat` function because callers expect to be returned an // `Animal` and all `Cat`s are `Animal`s. (Also: all `Cat`s are // `Beautiful`!) // // We cannot do the opposite and substitute a `Cat -> Cat` function // with a `Cat -> Animal` function, since callers expect a `Cat` but // the new function could return a `Pig`. // // As always, Wikipedia is also helpful: // https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) let params_match = a.params().iter().zip(b.params()).all(|(pa, pb)| { // Parameters are contravariant. Matches::matches( types, WithRecGroup::map(b, |_| *pb), WithRecGroup::map(a, |_| *pa), ) }); if !params_match { return false; } a.results().iter().zip(b.results()).all(|(ra, rb)| { // Results are covariant. Matches::matches( types, WithRecGroup::map(a, |_| *ra), WithRecGroup::map(b, |_| *rb), ) }) } } impl Matches for WithRecGroup { fn matches(types: &TypeList, a: Self, b: Self) -> bool { Matches::matches( types, WithRecGroup::map(a, |a| a.0), WithRecGroup::map(b, |b| b.0), ) } } impl<'a> Matches for WithRecGroup<&'a StructType> { fn matches(types: &TypeList, a: Self, b: Self) -> bool { // Note: Struct types support width and depth subtyping. a.fields.len() >= b.fields.len() && a.fields.iter().zip(b.fields.iter()).all(|(fa, fb)| { Matches::matches( types, WithRecGroup::map(a, |_| *fa), WithRecGroup::map(b, |_| *fb), ) }) } } impl Matches for WithRecGroup { fn matches(types: &TypeList, a: Self, b: Self) -> bool { // `a`'s storage type must match `b`'s storage type. if !Matches::matches( types, WithRecGroup::map(a, |a| a.element_type), WithRecGroup::map(b, |b| b.element_type), ) { return false; } // And either both fields are immutable... if !a.mutable && !b.mutable { return true; } // Or both fields are mutable and `b`'s storage type must match `a`'s // storage type, a.k.a. they must be the exact same storage type. a.mutable && b.mutable && Matches::matches( types, WithRecGroup::map(b, |b| b.element_type), WithRecGroup::map(a, |a| a.element_type), ) } } impl Matches for WithRecGroup { fn matches(types: &TypeList, a: Self, b: Self) -> bool { use StorageType as ST; match (*a, *b) { (ST::I8, ST::I8) | (ST::I16, ST::I16) => true, (ST::I8 | ST::I16, _) => false, (ST::Val(va), ST::Val(vb)) => Matches::matches( types, WithRecGroup::map(a, |_| va), WithRecGroup::map(b, |_| vb), ), (ST::Val(_), _) => false, } } } impl<'a> Matches for WithRecGroup<&'a ContType> { fn matches(types: &TypeList, a: Self, b: Self) -> bool { match (*a, *b) { (ContType(ca), ContType(cb)) => { ca == cb || types.reftype_is_subtype_impl( RefType::concrete(false, *ca), Some(WithRecGroup::rec_group(a)), RefType::concrete(false, *cb), Some(WithRecGroup::rec_group(b)), ) } } } } impl Matches for WithRecGroup { fn matches(types: &TypeList, a: Self, b: Self) -> bool { match (*a, *b) { (ValType::Ref(ra), ValType::Ref(rb)) => Matches::matches( types, WithRecGroup::map(a, |_| ra), WithRecGroup::map(b, |_| rb), ), (ValType::Ref(_), _) => false, (ValType::I32 | ValType::I64 | ValType::F32 | ValType::F64 | ValType::V128, _) => { *a == *b } } } } impl Matches for WithRecGroup { fn matches(types: &TypeList, a: Self, b: Self) -> bool { types.reftype_is_subtype_impl( *a, Some(WithRecGroup::rec_group(a)), *b, Some(WithRecGroup::rec_group(b)), ) } }