mir-analyzer 0.65.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_tps.len() != sub_params.len() {
        return false;
    }
    let own_bindings: FxHashMap<Name, Type> = 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();
    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()))
        || (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())
                }
                (
                    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,
                        })
                    })
                }
                // 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())
                }
                _ => false,
            }
        })
    })
}

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