mir-analyzer 0.80.0

//! Codebase-aware subtype check.
//!
//! `mir_types::Type::is_subtype_structural` is structural only — it never walks
//! `extends` / `implements`. Within `mir-analyzer`, whenever a `db` is in
//! scope, prefer [`is_subtype`] here. It falls back to the structural check
//! for scalars and exact matches, then resolves class hierarchies through the
//! Salsa database for named-object pairs and named-object/intersection pairs.
//!
//! Callers that already combine `is_subtype_structural` with their own
//! ad-hoc inheritance check (`named_object_subtype`, `named_object_return_compatible`)
//! don't need to switch — but new call sites should reach for this function
//! first.
use rustc_hash::FxHashMap;

use mir_types::{Atomic, Name, Type, Variance};

use crate::db::{
    class_template_params, extends_or_implements, inherited_template_bindings, MirDatabase,
};

/// A supertype type-parameter that's effectively wildcarded — an unbound
/// template var or `mixed`. When the supertype's params are all free, we
/// treat the supertype as "any instantiation" for subtype matching.
pub(crate) fn sup_param_is_free(ty: &Type) -> bool {
    ty.is_mixed()
        || ty
            .types
            .iter()
            .all(|a| matches!(a, Atomic::TTemplateParam { .. }))
}

/// Per-position variance check for two parameterizations of the SAME class
/// (`Box<Dog>` vs `Box<Animal>`): a `@template-covariant`/`-contravariant`
/// param may differ in the declared direction; invariant params must match
/// exactly (the `sub_params == sup_params` fast path in `is_subtype` already
/// covers the all-invariant case, so a mismatch here only survives when at
/// least one param is variant).
pub(crate) fn variance_compatible(
    db: &dyn MirDatabase,
    fqcn: &str,
    sub_params: &[Type],
    sup_params: &[Type],
) -> bool {
    if sub_params.len() != sup_params.len() {
        return false;
    }
    // A bare subclass that doesn't redeclare `@template` (`class IntBox
    // extends Box {}`) still carries its type args positioned against the
    // nearest ancestor that actually declares them — walk up to that
    // ancestor via `class_template_params` instead of finding zero
    // templates on `fqcn` itself. An empty result here (no template-declaring
    // ancestor at all) can't vacuously pass a caller-supplied non-empty
    // `sub_params`/`sup_params` pair (already known to differ, since the
    // `sub_params == sup_params` fast path in `is_subtype` would have short-
    // circuited otherwise) — there's no variance info to justify treating
    // them as compatible, so this must return false, not the previous
    // `tps.iter().zip(..)` vacuous-empty-iterator `true`.
    let tps = class_template_params(db, fqcn).unwrap_or_default();
    if tps.len() != sub_params.len() {
        return false;
    }
    tps.iter()
        .zip(sub_params)
        .zip(sup_params)
        .all(|((tp, sub_p), sup_p)| match tp.variance {
            Variance::Covariant => is_subtype(db, sub_p, sup_p),
            Variance::Contravariant => is_subtype(db, sup_p, sub_p),
            Variance::Invariant => sub_p == sup_p,
        })
}

/// Per-position variance check across an inheritance/`@implements` chain:
/// `sub_fqcn<sub_params>` may satisfy `sup_fqcn<sup_params>` — a DIFFERENT
/// class/interface — when `sup_fqcn`'s own template params are declared
/// covariant/contravariant and the type args `sub_fqcn` actually supplies for
/// `sup_fqcn` (resolved through its `@extends`/`@implements` chain) satisfy
/// them in the declared direction. Without this, `variance_compatible`'s
/// `sub_fqcn == sup_fqcn` gate only ever matches two instantiations of the
/// SAME class, so e.g. `TypedList<Dog> implements Collection<T>` could never
/// satisfy a `Collection<Animal>` parameter even though `Collection`'s `T` is
/// `@template-covariant`.
pub(crate) fn variance_compatible_across_hierarchy(
    db: &dyn MirDatabase,
    sub_fqcn: &str,
    sub_params: &[Type],
    sup_fqcn: &str,
    sup_params: &[Type],
) -> bool {
    if sub_fqcn == sup_fqcn {
        return false;
    }
    // A bare subclass that doesn't redeclare `@template` (`class IntBox
    // extends Box {}`) still carries its type args positioned against the
    // nearest ancestor that actually declares them — walk up to that
    // ancestor instead of finding zero templates on `sub_fqcn` itself and
    // discarding every bound type param (see `variance_compatible` above for
    // the same fix, and `call/method.rs`/`call/static_call.rs`/
    // `expr/objects.rs` for the established pattern elsewhere). `None`/empty
    // (no template-declaring ancestor at all — a genuinely concrete,
    // non-generic class) has no OWN bindings to contribute, but it can still
    // fix an ancestor's template argument via `@implements Collection<int>` —
    // `inherited_template_bindings` below resolves that directly from the
    // `@implements` clause, so an empty `own_bindings` is fine. Only bail
    // when the sub class DOES declare templates but the caller supplied a
    // mismatched arity — a malformed receiver, not "nothing to check".
    let sub_tps = class_template_params(db, sub_fqcn).unwrap_or_default();
    if !sub_tps.is_empty() && !sub_params.is_empty() && sub_tps.len() != sub_params.len() {
        return false;
    }
    // A bare instantiation leaves its own templates unbound, i.e. `mixed`.
    let own_bindings: FxHashMap<Name, Type> = if sub_params.is_empty() {
        sub_tps.iter().map(|tp| (tp.name, Type::mixed())).collect()
    } else {
        sub_tps
            .iter()
            .zip(sub_params)
            .map(|(tp, ty)| (tp.name, ty.clone()))
            .collect()
    };
    let ancestor_bindings = inherited_template_bindings(db, sub_fqcn, &own_bindings);
    let sup_tps = class_template_params(db, sup_fqcn).unwrap_or_default();
    let resolved_sup_params: Vec<Type> = sup_tps
        .iter()
        .map(|tp| {
            ancestor_bindings
                .get(&tp.name)
                .cloned()
                .unwrap_or_else(Type::mixed)
        })
        .collect();
    if sub_params.is_empty() && resolved_sup_params.iter().all(Type::is_mixed) {
        return true;
    }
    variance_compatible(db, sup_fqcn, &resolved_sup_params, sup_params)
}

/// Whether `sub_fqcn<sub_params>`'s type arguments are compatible with a
/// required `sup_fqcn<sup_params>` — shared by the `(TNamedObject,
/// TNamedObject)` and `(TNamedObject, TIntersection)` arms of `is_subtype`
/// (an intersection part is itself just a named-object requirement). Does
/// NOT check `sub_fqcn`/`sup_fqcn`'s class-hierarchy relationship — callers
/// combine this with their own `extends_or_implements` check.
pub(crate) fn named_object_type_params_ok(
    db: &dyn MirDatabase,
    sub_fqcn: &Name,
    sub_params: &[Type],
    sup_fqcn: &Name,
    sup_params: &[Type],
) -> bool {
    // For parameterized classes we can only reason about the hierarchy when
    // the supertype is bare (no `<...>`), the supertype's params are all
    // unbound template vars (e.g. `Base<K, V>` where `K`/`V` are free), both
    // sides match exactly, or the sub's params are free:
    // - `mixed` explicitly opts out of type-param checking (mirrors
    //   Psalm/PHPStan behaviour for `mixed` args)
    // - `never` is the bottom type and a subtype of every type
    sup_params.is_empty()
        || sub_params == sup_params
        || sup_params.iter().all(sup_param_is_free)
        || (!sub_params.is_empty() && sub_params.iter().all(|p| p.is_mixed() || p.is_never()))
        // A bare instantiation (`new Gen()` with nothing to infer from) leaves
        // every template unbound, i.e. `Gen<mixed, ...>`.
        || (sub_params.is_empty() && sub_fqcn == sup_fqcn)
        || (sub_fqcn == sup_fqcn
            && variance_compatible(db, sub_fqcn.as_ref(), sub_params, sup_params))
        || variance_compatible_across_hierarchy(
            db,
            sub_fqcn.as_ref(),
            sub_params,
            sup_fqcn.as_ref(),
            sup_params,
        )
}

/// Returns true if `sub` is a subtype of `sup`, considering the codebase's
/// class-hierarchy graph (`extends` / `implements`) on top of structural
/// matches.
pub(crate) fn is_subtype(db: &dyn MirDatabase, sub: &Type, sup: &Type) -> bool {
    if sub.is_subtype_structural(sup) {
        return true;
    }
    if sup.is_mixed() {
        return true;
    }
    if sub.is_never() {
        return true;
    }

    sub.types.iter().all(|a| {
        // A trait-typed value only arises as `$this` inside a trait body
        // (analyzed standalone). Its concrete runtime type is the unknown using
        // class, which may extend/implement anything — so treat it as a subtype
        // of any target rather than rejecting it against the trait's own (empty)
        // hierarchy.
        if let Atomic::TNamedObject { fqcn: sub_fqcn, .. } = a {
            if crate::db::class_kind(db, sub_fqcn.as_ref()).is_some_and(|k| k.is_trait) {
                return true;
            }
        }
        sup.types.iter().any(|b| {
            // Per-pair structural check: handles scalars (string, int, etc.) when
            // sub is a union — is_subtype_structural above failed because another
            // arm didn't match structurally, but this pair may still match.
            if mir_types::union::atomic_subtype(a, b) {
                return true;
            }
            match (a, b) {
                (
                    Atomic::TNamedObject {
                        fqcn: sub_fqcn,
                        type_params: sub_params,
                    },
                    Atomic::TNamedObject {
                        fqcn: sup_fqcn,
                        type_params: sup_params,
                    },
                ) => {
                    named_object_type_params_ok(db, sub_fqcn, sub_params, sup_fqcn, sup_params)
                        && extends_or_implements(db, sub_fqcn.as_ref(), sup_fqcn.as_ref())
                }
                // An invokable object (one with an __invoke() method) satisfies a
                // callable(...): R / Closure(...): R target — mirrors the same
                // leniency `call/args/types.rs::named_object_subtype` already
                // applies for callable-typed ARGUMENTS via `has_method_in_chain`,
                // just not signature-checked here either (matching that existing
                // precedent, not a stricter new bar).
                (
                    Atomic::TNamedObject { fqcn: sub_fqcn, .. },
                    Atomic::TCallable { .. } | Atomic::TClosure { .. },
                ) => crate::db::has_method_in_chain(db, sub_fqcn.as_ref(), "__invoke"),
                (
                    Atomic::TNamedObject {
                        fqcn: sub_fqcn,
                        type_params: sub_params,
                    },
                    Atomic::TIntersection { parts },
                ) => {
                    // sub satisfies intersection bound iff it satisfies every part —
                    // same type-param variance check as the plain (TNamedObject,
                    // TNamedObject) arm above, applied per intersection part instead
                    // of dropped: `Collection<int>&Countable` must reject a
                    // `Collection<string>&Countable` sub just as strictly as a bare
                    // `Collection<int>` supertype would.
                    parts.iter().all(|part| {
                        part.types.iter().any(|part_atomic| match part_atomic {
                            Atomic::TNamedObject {
                                fqcn: part_fqcn,
                                type_params: part_params,
                            } => {
                                named_object_type_params_ok(
                                    db,
                                    sub_fqcn,
                                    sub_params,
                                    part_fqcn,
                                    part_params,
                                ) && extends_or_implements(
                                    db,
                                    sub_fqcn.as_ref(),
                                    part_fqcn.as_ref(),
                                )
                            }
                            _ => false,
                        })
                    })
                }
                // TKeyedArray (array shape) satisfies TIntersection iff it satisfies every
                // intersection part. This mirrors the atomic_subtype fix and handles
                // the Psalm idiom of using intersection types for "shape plus extra keys
                // allowed" patterns like:
                // @psalm-type Context = array<string,mixed> & array{actor:...,target?:...,outcome:...}
                (
                    Atomic::TKeyedArray {
                        properties,
                        is_open,
                        ..
                    },
                    Atomic::TIntersection { parts },
                ) => parts.iter().all(|part| {
                    part.types.iter().any(|part_atomic| match part_atomic {
                        Atomic::TKeyedArray {
                            properties: sup_props,
                            is_open: sup_open,
                            ..
                        } => {
                            let keys_satisfied =
                                sup_props
                                    .iter()
                                    .all(|(key, sup_prop)| match properties.get(key) {
                                        Some(sub_prop) => {
                                            if !sup_prop.optional && sub_prop.optional {
                                                return false;
                                            }
                                            let has_named_obj = sup_prop.ty.types.iter().any(|a| {
                                                matches!(
                                                    a,
                                                    Atomic::TNamedObject { .. }
                                                        | Atomic::TSelf { .. }
                                                        | Atomic::TStaticObject { .. }
                                                        | Atomic::TClosure { .. }
                                                        | Atomic::TTemplateParam { .. }
                                                )
                                            });
                                            has_named_obj
                                                || is_subtype(db, &sub_prop.ty, &sup_prop.ty)
                                        }
                                        None => *is_open || sup_prop.optional,
                                    });
                            let has_array_part = parts.iter().any(|part| {
                                part.types
                                    .iter()
                                    .any(|t| matches!(t, Atomic::TArray { .. }))
                            });
                            let has_keyed_array_part = parts.iter().any(|part| {
                                part.types
                                    .iter()
                                    .any(|t| matches!(t, Atomic::TKeyedArray { .. }))
                            });
                            let keys_allowed_by_some_part = if has_array_part {
                                true
                            } else if has_keyed_array_part {
                                properties.keys().all(|k| {
                                    parts.iter().any(|part| {
                                        part.types.iter().any(|t| {
                                            if let Atomic::TKeyedArray {
                                                properties: part_props,
                                                ..
                                            } = t
                                            {
                                                part_props.contains_key(k)
                                            } else {
                                                false
                                            }
                                        })
                                    })
                                })
                            } else {
                                true
                            };
                            let no_undeclared_extras = *sup_open || keys_allowed_by_some_part;
                            keys_satisfied && no_undeclared_extras
                        }
                        Atomic::TArray { key, value } => {
                            properties.iter().all(|(prop_key, prop)| {
                                let key_atomic = match prop_key {
                                    mir_types::atomic::ArrayKey::String(s) => {
                                        Atomic::TLiteralString(s.clone())
                                    }
                                    mir_types::atomic::ArrayKey::Int(n) => Atomic::TLiteralInt(*n),
                                };
                                if !is_subtype(db, &Type::single(key_atomic), key) {
                                    return false;
                                }
                                let has_named_obj = prop.ty.types.iter().any(|a| {
                                    matches!(
                                        a,
                                        Atomic::TNamedObject { .. }
                                            | Atomic::TSelf { .. }
                                            | Atomic::TStaticObject { .. }
                                            | Atomic::TClosure { .. }
                                            | Atomic::TTemplateParam { .. }
                                    )
                                });
                                has_named_obj || is_subtype(db, &prop.ty, value)
                            })
                        }
                        Atomic::TNamedObject { .. }
                        | Atomic::TSelf { .. }
                        | Atomic::TStaticObject { .. }
                        | Atomic::TClosure { .. }
                        | Atomic::TTemplateParam { .. } => true,
                        _ => false,
                    })
                }),
                // A&B&C satisfies a required X&Y iff every required part is
                // covered by some part of sub — a value with MORE capabilities
                // than required still satisfies the narrower requirement.
                (
                    Atomic::TIntersection { parts: sub_parts },
                    Atomic::TIntersection { parts: sup_parts },
                ) => sup_parts.iter().all(|sup_part| {
                    sub_parts
                        .iter()
                        .any(|sub_part| is_subtype(db, sub_part, sup_part))
                }),
                // An intersection type is a subtype of C if any of its parts is a subtype of C
                // (a value satisfying A&B is also an A and also a B).
                (Atomic::TIntersection { parts }, b) => {
                    let sup_single = Type::single(b.clone());
                    parts.iter().any(|part| is_subtype(db, part, &sup_single))
                }
                // A list-shaped keyed array (array{0:A,1:B}) satisfies list<T> when every
                // element is a subtype of T — using the codebase-aware check so subclasses
                // (CommandArgument extends Argument) are accepted.
                (
                    Atomic::TKeyedArray {
                        properties,
                        is_list,
                        ..
                    },
                    Atomic::TList { value: lv },
                ) => *is_list && properties.values().all(|p| is_subtype(db, &p.ty, lv)),
                // array<K1,V1>/non-empty-array<K1,V1> satisfies array<K2,V2> when the key
                // and value types do (codebase-aware, so array<int,Cat> satisfies
                // array<int,Animal>) — mir_types::union::atomic_subtype's structural
                // check has no class-hierarchy awareness for these pairs at all.
                (
                    Atomic::TArray { key: sk, value: sv }
                    | Atomic::TNonEmptyArray { key: sk, value: sv },
                    Atomic::TArray { key: dk, value: dv },
                ) => is_subtype(db, sk, dk) && is_subtype(db, sv, dv),
                (
                    Atomic::TNonEmptyArray { key: sk, value: sv },
                    Atomic::TNonEmptyArray { key: dk, value: dv },
                ) => is_subtype(db, sk, dk) && is_subtype(db, sv, dv),
                // list<V1>/non-empty-list<V1> satisfies list<V2> the same way.
                (
                    Atomic::TList { value: sv } | Atomic::TNonEmptyList { value: sv },
                    Atomic::TList { value: dv },
                ) => is_subtype(db, sv, dv),
                (Atomic::TNonEmptyList { value: sv }, Atomic::TNonEmptyList { value: dv }) => {
                    is_subtype(db, sv, dv)
                }
                // PHP implicitly coerces int to float in all numeric contexts.
                (
                    Atomic::TInt
                    | Atomic::TLiteralInt(_)
                    | Atomic::TPositiveInt
                    | Atomic::TNegativeInt
                    | Atomic::TNonNegativeInt
                    | Atomic::TIntRange { .. },
                    Atomic::TFloat,
                ) => true,
                (Atomic::TIntegralFloat, Atomic::TFloat) => true,
                // class-string<X> is a subtype of class-string<Y> (or interface-string<Y>,
                // provided X actually names an interface) when X extends/implements Y —
                // structural equality alone (checked above) misses the inheritance case.
                (Atomic::TClassString(Some(sub_cls)), Atomic::TClassString(Some(sup_cls))) => {
                    sub_cls == sup_cls
                        || extends_or_implements(db, sub_cls.as_ref(), sup_cls.as_ref())
                }
                (Atomic::TClassString(Some(sub_cls)), Atomic::TInterfaceString(None)) => {
                    is_interface(db, sub_cls.as_ref())
                }
                (
                    Atomic::TClassString(Some(sub_cls)),
                    Atomic::TInterfaceString(Some(sup_iface)),
                ) => {
                    is_interface(db, sub_cls.as_ref())
                        && (sub_cls == sup_iface
                            || extends_or_implements(db, sub_cls.as_ref(), sup_iface.as_ref()))
                }
                // An unresolved class-string could name an interface — stay permissive
                // rather than definitely reject, matching the None-vs-Some convention above.
                (Atomic::TClassString(None), Atomic::TInterfaceString(_)) => true,
                (
                    Atomic::TInterfaceString(Some(sub_iface)),
                    Atomic::TInterfaceString(Some(sup_iface)),
                ) => {
                    sub_iface == sup_iface
                        || extends_or_implements(db, sub_iface.as_ref(), sup_iface.as_ref())
                }
                (
                    Atomic::TInterfaceString(Some(sub_iface)),
                    Atomic::TClassString(Some(sup_cls)),
                ) => {
                    sub_iface == sup_cls
                        || extends_or_implements(db, sub_iface.as_ref(), sup_cls.as_ref())
                }
                // An enum-case literal satisfies a supertype named by any interface
                // (or, since enums can't extend a class, any other named type) its
                // declaring enum implements — e.g. a `HasLabel`-typed param/property
                // accepting `Status::Active` when `Status implements HasLabel`.
                // Exact-fqcn equality is already covered by the structural check above.
                (
                    Atomic::TLiteralEnumCase { enum_fqcn, .. },
                    Atomic::TNamedObject { fqcn: sup_fqcn, .. },
                ) => extends_or_implements(db, enum_fqcn.as_ref(), sup_fqcn.as_ref()),
                _ => false,
            }
        })
    })
}

fn is_interface(db: &dyn MirDatabase, fqcn: &str) -> bool {
    crate::db::class_kind(db, fqcn).is_some_and(|k| k.is_interface)
}