mir_types/

union.rs

use rustc_hash::FxHashMap;
use serde::{Deserialize, Serialize};
use smallvec::SmallVec;
use std::sync::{Arc, OnceLock};

use crate::atomic::Atomic;
use crate::symbol::Name;

/// Returns a cached empty `Arc<[Type]>` for `type_params` / `parts` fields.
/// Re-uses a single Arc allocation so all empty parameter lists share one
/// control block instead of allocating one per TNamedObject construction.
pub fn empty_type_params() -> Arc<[Type]> {
    static EMPTY: OnceLock<Arc<[Type]>> = OnceLock::new();
    EMPTY.get_or_init(|| Arc::from([] as [Type; 0])).clone()
}

/// Convert a `Vec<Type>` to `Arc<[Type]>`, using the cached empty Arc when
/// the vec is empty to avoid an allocation for the common no-generic case.
pub fn vec_to_type_params(v: Vec<Type>) -> Arc<[Type]> {
    if v.is_empty() {
        empty_type_params()
    } else {
        Arc::from(v)
    }
}

// Most unions contain 1-2 atomics (e.g. `string|null`), so we inline two.
pub type AtomicVec = SmallVec<[Atomic; 2]>;

/// Result of classifying a type for `clone` validity (see [`Type::clone_validity`]).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CloneValidity {
    /// Every member is (or may be) an object — cloning is fine.
    Cloneable,
    /// Every member is definitely a non-object — cloning is an error.
    Invalid,
    /// Some members are non-objects, some are objects — cloning may be an error.
    PossiblyInvalid,
    /// Empty/unknown type — no diagnostic.
    Unknown,
}

// ---------------------------------------------------------------------------
// Type — the primary type carrier
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Type {
    pub types: AtomicVec,
    /// The variable holding this type may not be initialized at this point.
    pub possibly_undefined: bool,
    /// This type originated from a docblock annotation rather than inference.
    pub from_docblock: bool,
    /// A `false`/`null` failure variant was deliberately stripped from this type
    /// (e.g. `preg_split`'s regex-error `false`) because real code overwhelmingly
    /// never checks for it. A defensive `=== false`/`=== null` check or a
    /// `(string)`/`(array)` cast guarding against that exact stripped variant is
    /// still legitimate, so the impossibility/redundancy checks (`ImpossibleIdenticalComparison`,
    /// `RedundantCast`, the `=== null` narrowing divergence) exempt it instead of
    /// flagging the caller's own defensive code.
    pub falsy_stripped: bool,
}

impl Type {
    // --- Constructors -------------------------------------------------------

    pub fn empty() -> Self {
        Self {
            types: SmallVec::new(),
            possibly_undefined: false,
            from_docblock: false,
            falsy_stripped: false,
        }
    }

    pub fn single(atomic: Atomic) -> Self {
        let mut types = SmallVec::new();
        types.push(atomic);
        Self {
            types,
            possibly_undefined: false,
            from_docblock: false,
            falsy_stripped: false,
        }
    }

    pub fn mixed() -> Self {
        Self::single(Atomic::TMixed)
    }

    pub fn void() -> Self {
        Self::single(Atomic::TVoid)
    }

    pub fn never() -> Self {
        Self::single(Atomic::TNever)
    }

    pub fn null() -> Self {
        Self::single(Atomic::TNull)
    }

    pub fn bool() -> Self {
        Self::single(Atomic::TBool)
    }

    pub fn int() -> Self {
        Self::single(Atomic::TInt)
    }

    pub fn float() -> Self {
        Self::single(Atomic::TFloat)
    }

    pub fn string() -> Self {
        Self::single(Atomic::TString)
    }

    /// `int|string` — the canonical PHP array-key type, used as the default
    /// key type when a docblock/inferred array has no more specific key.
    pub fn array_key() -> Self {
        let mut u = Self::single(Atomic::TInt);
        u.add_type(Atomic::TString);
        u
    }

    /// `T|null`
    pub fn nullable(atomic: Atomic) -> Self {
        // `mixed|null` = `mixed` — null is already included in mixed.
        if matches!(atomic, Atomic::TMixed) {
            return Self::mixed();
        }
        let mut types = SmallVec::new();
        types.push(atomic);
        types.push(Atomic::TNull);
        Self {
            types,
            possibly_undefined: false,
            from_docblock: false,
            falsy_stripped: false,
        }
    }

    /// Build a union from multiple atomics, de-duplicating on the fly.
    pub fn from_vec(atomics: Vec<Atomic>) -> Self {
        let mut u = Self::empty();
        for a in atomics {
            u.add_type(a);
        }
        u
    }

    // --- Introspection -------------------------------------------------------

    pub fn is_empty(&self) -> bool {
        self.types.is_empty()
    }

    pub fn is_single(&self) -> bool {
        self.types.len() == 1
    }

    pub fn is_nullable(&self) -> bool {
        self.types.iter().any(|t| matches!(t, Atomic::TNull))
    }

    /// True when this is exactly `int|string` — the array-key domain, which
    /// is already the maximal set of legal PHP array keys and so should be
    /// treated like a "default"/unconstrained key, same as `mixed` would be
    /// for a non-key type parameter.
    pub fn is_array_key(&self) -> bool {
        self.types.len() == 2
            && self.types.iter().any(|t| matches!(t, Atomic::TInt))
            && self.types.iter().any(|t| matches!(t, Atomic::TString))
    }

    pub fn is_mixed(&self) -> bool {
        self.types.iter().any(|t| match t {
            Atomic::TMixed => true,
            Atomic::TTemplateParam { as_type, .. } => as_type.is_mixed(),
            _ => false,
        })
    }

    /// True only when the type contains `TMixed` atoms and no `TTemplateParam` atoms.
    /// Unlike [`is_mixed`], this does not treat an unconstrained template parameter as
    /// "mixed" — a `T` placeholder is an intentionally parameterised type that will be
    /// instantiated at the call site, so it must not trigger `MixedAssignment` warnings.
    pub fn is_mixed_not_template(&self) -> bool {
        self.is_mixed()
            && !self
                .types
                .iter()
                .any(|t| matches!(t, Atomic::TTemplateParam { .. }))
    }

    pub fn is_never(&self) -> bool {
        self.types.iter().all(|t| matches!(t, Atomic::TNever)) && !self.types.is_empty()
    }

    /// Classify this type for `clone` validity. Recurses into template-param
    /// bounds (like [`Type::is_mixed`]). Callers handle `mixed` separately.
    pub fn clone_validity(&self) -> CloneValidity {
        if self.types.is_empty() {
            return CloneValidity::Unknown;
        }
        let mut has_non_object = false;
        let mut has_other = false; // object or ambiguous (callable, mixed, conditional, …)
        for t in &self.types {
            match t {
                Atomic::TTemplateParam { as_type, .. } => match as_type.clone_validity() {
                    CloneValidity::Invalid => has_non_object = true,
                    CloneValidity::PossiblyInvalid => {
                        has_non_object = true;
                        has_other = true;
                    }
                    CloneValidity::Cloneable | CloneValidity::Unknown => has_other = true,
                },
                other if other.is_definitely_non_object() => has_non_object = true,
                _ => has_other = true,
            }
        }
        match (has_non_object, has_other) {
            (true, false) => CloneValidity::Invalid,
            (true, true) => CloneValidity::PossiblyInvalid,
            _ => CloneValidity::Cloneable,
        }
    }

    pub fn is_void(&self) -> bool {
        self.is_single() && matches!(self.types[0], Atomic::TVoid)
    }

    pub fn can_be_falsy(&self) -> bool {
        self.types.iter().any(|t| t.can_be_falsy())
    }

    pub fn can_be_truthy(&self) -> bool {
        self.types.iter().any(|t| t.can_be_truthy())
    }

    pub fn contains<F: Fn(&Atomic) -> bool>(&self, f: F) -> bool {
        self.types.iter().any(f)
    }

    pub fn has_named_object(&self, fqcn: &str) -> bool {
        self.types.iter().any(|t| match t {
            Atomic::TNamedObject { fqcn: f, .. } => f.as_ref() == fqcn,
            _ => false,
        })
    }

    // --- Mutation ------------------------------------------------------------

    /// Add an atomic to this union, skipping duplicates.
    /// Subsumption rules: anything ⊆ TMixed; TLiteralInt ⊆ TInt; etc.
    pub fn add_type(&mut self, atomic: Atomic) {
        // If we already have TMixed, nothing to add.
        if self.types.iter().any(|t| matches!(t, Atomic::TMixed)) {
            return;
        }

        // Adding TMixed subsumes everything.
        if matches!(atomic, Atomic::TMixed) {
            self.types.clear();
            self.types.push(Atomic::TMixed);
            return;
        }

        // Simplify trivial conditional types: (X is ? T : T) → T
        // Recursively simplify branches first so nested trivial conditionals collapse.
        let atomic = if let Atomic::TConditional { data } = &atomic {
            let (if_true, if_false) = (&data.if_true, &data.if_false);
            let mut simplified_true = Type::empty();
            for t in &if_true.types {
                simplified_true.add_type(t.clone());
            }
            let mut simplified_false = Type::empty();
            for t in &if_false.types {
                simplified_false.add_type(t.clone());
            }
            if simplified_true == simplified_false {
                for t in simplified_true.types {
                    self.add_type(t);
                }
                return;
            }
            atomic
        } else {
            atomic
        };

        // Avoid exact duplicates.
        if self.types.contains(&atomic) {
            return;
        }

        // TLiteralInt(n) is subsumed by TInt.
        if let Atomic::TLiteralInt(_) = &atomic {
            if self.types.iter().any(|t| matches!(t, Atomic::TInt)) {
                return;
            }
        }
        // TLiteralString(s) is subsumed by TString.
        if let Atomic::TLiteralString(_) = &atomic {
            if self.types.iter().any(|t| matches!(t, Atomic::TString)) {
                return;
            }
        }
        // TTrue / TFalse are subsumed by TBool.
        if matches!(atomic, Atomic::TTrue | Atomic::TFalse)
            && self.types.iter().any(|t| matches!(t, Atomic::TBool))
        {
            return;
        }
        // TTrue and TFalse together are exactly TBool — merge rather than
        // keeping both literals once both are present.
        if matches!(atomic, Atomic::TTrue) && self.types.iter().any(|t| matches!(t, Atomic::TFalse))
        {
            self.types.retain(|t| !matches!(t, Atomic::TFalse));
            self.types.push(Atomic::TBool);
            return;
        }
        if matches!(atomic, Atomic::TFalse) && self.types.iter().any(|t| matches!(t, Atomic::TTrue))
        {
            self.types.retain(|t| !matches!(t, Atomic::TTrue));
            self.types.push(Atomic::TBool);
            return;
        }
        // Adding TInt widens away all TLiteralInt variants.
        if matches!(atomic, Atomic::TInt) {
            self.types.retain(|t| !matches!(t, Atomic::TLiteralInt(_)));
        }
        // Adding TString widens away all TLiteralString variants.
        if matches!(atomic, Atomic::TString) {
            self.types
                .retain(|t| !matches!(t, Atomic::TLiteralString(_)));
        }
        // Adding TBool widens away TTrue/TFalse.
        if matches!(atomic, Atomic::TBool) {
            self.types
                .retain(|t| !matches!(t, Atomic::TTrue | Atomic::TFalse));
        }

        // TNever is the bottom type: T | never = T.
        if matches!(atomic, Atomic::TNever) {
            if !self.types.is_empty() {
                return;
            }
        } else {
            self.types.retain(|t| !matches!(t, Atomic::TNever));
        }

        // Closed empty keyed array (array{}) is a subtype of any generic array or
        // list. Remove it if we already have a generic array<K,V> or list<V>. An
        // OPEN empty shape (array{...}) carries real information — it may hold
        // unknown, possibly non-list, extra keys at runtime — so it's not
        // subsumed and must not be dropped.
        if let Atomic::TKeyedArray {
            properties,
            is_open,
            ..
        } = &atomic
        {
            if properties.is_empty() && !is_open {
                for existing in &self.types {
                    match existing {
                        Atomic::TArray { .. }
                        | Atomic::TNonEmptyArray { .. }
                        | Atomic::TList { .. }
                        | Atomic::TNonEmptyList { .. } => {
                            return; // Don't add empty array, it's subsumed
                        }
                        _ => {}
                    }
                }
            }
        }

        // When adding a generic array or list, remove any CLOSED empty keyed
        // arrays since they're subtypes (same reasoning as above, mirrored).
        let is_generic_array_or_list = matches!(
            &atomic,
            Atomic::TArray { .. }
                | Atomic::TNonEmptyArray { .. }
                | Atomic::TList { .. }
                | Atomic::TNonEmptyList { .. }
        );
        if is_generic_array_or_list {
            self.types.retain(|t| {
                if let Atomic::TKeyedArray {
                    properties,
                    is_open,
                    ..
                } = t
                {
                    !properties.is_empty() || *is_open
                } else {
                    true
                }
            });
        }

        self.types.push(atomic);
    }

    // --- Narrowing -----------------------------------------------------------

    /// Remove `null` from the union (e.g. after a null check).
    pub fn remove_null(&self) -> Type {
        self.filter(|t| !matches!(t, Atomic::TNull))
    }

    /// Remove `false` from the union.
    /// `TFalse` is dropped; `TBool` becomes `TTrue` since `bool - false = true`.
    pub fn remove_false(&self) -> Type {
        let mut result = self.filter(|t| !matches!(t, Atomic::TFalse | Atomic::TBool));
        if self.types.iter().any(|t| matches!(t, Atomic::TBool)) {
            result.add_type(Atomic::TTrue);
        }
        result
    }

    /// Remove `true` from the union.
    /// `TTrue` is dropped; `TBool` becomes `TFalse` since `bool - true = false`.
    pub fn remove_true(&self) -> Type {
        let mut result = self.filter(|t| !matches!(t, Atomic::TTrue | Atomic::TBool));
        if self.types.iter().any(|t| matches!(t, Atomic::TBool)) {
            result.add_type(Atomic::TFalse);
        }
        result
    }

    /// Remove both `null` and `false` from the union (core type without nullable/falsy variants).
    pub fn core_type(&self) -> Type {
        self.remove_null().remove_false()
    }

    /// Keep only truthy atomics (e.g. after `if ($x)`).
    pub fn narrow_to_truthy(&self) -> Type {
        if self.is_mixed_not_template() {
            return Type::mixed();
        }
        let mut result = Type::empty();
        result.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                // An unconstrained/bounded template could resolve to anything at
                // runtime, truthy or falsy — preserve it rather than dropping or
                // widening it, the same way narrow_to_string/_int/etc. already do.
                Atomic::TTemplateParam { .. } => result.add_type(t.clone()),
                // Always-falsy — exclude entirely.
                Atomic::TLiteralInt(0)
                | Atomic::TLiteralFloat(0, 0)
                | Atomic::TNull
                | Atomic::TFalse => {}
                Atomic::TLiteralString(s) if s.as_ref() == "" || s.as_ref() == "0" => {}
                // bool contains both true (truthy) and false (falsy); truthy branch is true.
                Atomic::TBool => result.add_type(Atomic::TTrue),
                // array/list: empty ↔ falsy; truthy branch is non-empty-array/list.
                Atomic::TArray { key, value } => result.add_type(Atomic::TNonEmptyArray {
                    key: key.clone(),
                    value: value.clone(),
                }),
                Atomic::TList { value } => result.add_type(Atomic::TNonEmptyList {
                    value: value.clone(),
                }),
                // string: only "" and "0" are falsy; truthy branch is non-empty-string.
                // non-empty-string still includes "0" (which is falsy) but that is the
                // standard approximation used by Psalm and other analyzers.
                Atomic::TString => result.add_type(Atomic::TNonEmptyString),
                // numeric-string: "0" is the only falsy value; non-zero numerics are truthy.
                // No named "non-zero numeric-string" type exists; keep as-is conservatively.
                // int<0, max> only has 0 as its falsy value; truthy branch is int<1, max>.
                // (int<0, 0> is handled by the can_be_truthy() false guard below.)
                Atomic::TNonNegativeInt => result.add_type(Atomic::TPositiveInt),
                Atomic::TIntRange { min: Some(0), max } if max.is_none_or(|m| m >= 1) => {
                    let atom = if max.is_none() {
                        Atomic::TPositiveInt
                    } else {
                        Atomic::TIntRange {
                            min: Some(1),
                            max: *max,
                        }
                    };
                    result.add_type(atom);
                }
                // int<min, 0>: 0 is the only falsy value; truthy branch excludes it → int<min, -1>.
                Atomic::TIntRange { min, max: Some(0) } => {
                    let atom = match min {
                        None => Atomic::TNegativeInt,
                        Some(n) if *n <= -1 => Atomic::TIntRange {
                            min: *min,
                            max: Some(-1),
                        },
                        _ => continue, // min >= 0 with max == 0 → range is {0} — can_be_truthy() handles this
                    };
                    result.add_type(atom);
                }
                // Anything else that can never be truthy — drop.
                t if !t.can_be_truthy() => {}
                _ => result.add_type(t.clone()),
            }
        }
        result
    }

    /// Keep only falsy atomics (e.g. after `if (!$x)`).
    pub fn narrow_to_falsy(&self) -> Type {
        if self.is_mixed_not_template() {
            return Type::from_vec(vec![
                Atomic::TNull,
                Atomic::TFalse,
                Atomic::TLiteralInt(0),
                Atomic::TLiteralString("".into()),
            ]);
        }
        let mut result = Type::empty();
        result.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                // An unconstrained/bounded template could resolve to anything at
                // runtime, truthy or falsy — preserve it rather than dropping it
                // (its own `can_be_falsy()` conservatively defaults to `false`,
                // which would otherwise wrongly exclude it here).
                Atomic::TTemplateParam { .. } => result.add_type(t.clone()),
                // bool: only false is falsy; falsy branch is false.
                Atomic::TBool => result.add_type(Atomic::TFalse),
                // int: only 0 is falsy.
                Atomic::TInt => result.add_type(Atomic::TLiteralInt(0)),
                // float: only 0.0 is falsy.
                Atomic::TFloat => result.add_type(Atomic::TLiteralFloat(0, 0)),
                // string: only "" and "0" are falsy.
                Atomic::TString => {
                    result.add_type(Atomic::TLiteralString("".into()));
                    result.add_type(Atomic::TLiteralString("0".into()));
                }
                // numeric-string: only "0" is a falsy numeric string.
                Atomic::TNumericString => result.add_type(Atomic::TLiteralString("0".into())),
                // non-negative-int: only 0 is falsy.
                Atomic::TNonNegativeInt => result.add_type(Atomic::TLiteralInt(0)),
                // int<0, hi>: only 0 is falsy.
                Atomic::TIntRange {
                    min: Some(0),
                    max: Some(_) | None,
                } => result.add_type(Atomic::TLiteralInt(0)),
                // int<min, 0>: only 0 is falsy.
                Atomic::TIntRange { max: Some(0), .. } => result.add_type(Atomic::TLiteralInt(0)),
                t if !t.can_be_falsy() => {} // always truthy — exclude
                _ => result.add_type(t.clone()),
            }
        }
        result
    }

    /// Narrow this type as if `$x instanceof ClassName` is true.
    ///
    /// The instanceof check guarantees the value IS an instance of `class`, so we
    /// replace any object / mixed constituents with the specific named object.  Scalar
    /// constituents are dropped (they can never satisfy instanceof).
    pub fn narrow_instanceof(&self, class: &str) -> Type {
        let narrowed_ty = Atomic::TNamedObject {
            fqcn: class.into(),
            type_params: empty_type_params(),
        };
        // If any constituent is an object-like type, the result is the specific class.
        let has_object = self.types.iter().any(|t| {
            matches!(
                t,
                Atomic::TObject | Atomic::TNamedObject { .. } | Atomic::TMixed | Atomic::TNull // null fails instanceof, but mixed/object may include null
            )
        });
        if has_object || self.is_empty() {
            Type::single(narrowed_ty)
        } else {
            // Pure scalars — instanceof is always false here, but return the class
            // defensively so callers don't see an empty union.
            Type::single(narrowed_ty)
        }
    }

    /// Narrow as if `is_string($x)` is true. `mixed`/`scalar` become a concrete
    /// `string` (rather than staying `mixed`) so downstream string-only
    /// operations see a usable type instead of reporting `Mixed*`.
    pub fn narrow_to_string(&self) -> Type {
        self.filter_replacing(
            |t| t.is_string() || matches!(t, Atomic::TTemplateParam { .. }),
            |t| matches!(t, Atomic::TMixed | Atomic::TScalar),
            Atomic::TString,
        )
    }

    /// Narrow as if `is_int($x)` is true.
    pub fn narrow_to_int(&self) -> Type {
        self.filter_replacing(
            |t| t.is_int() || matches!(t, Atomic::TTemplateParam { .. }),
            |t| matches!(t, Atomic::TMixed | Atomic::TScalar | Atomic::TNumeric),
            Atomic::TInt,
        )
    }

    /// Narrow as if `is_float($x)` is true.
    pub fn narrow_to_float(&self) -> Type {
        self.filter_replacing(
            |t| {
                matches!(
                    t,
                    Atomic::TFloat
                        | Atomic::TIntegralFloat
                        | Atomic::TLiteralFloat(..)
                        | Atomic::TTemplateParam { .. }
                )
            },
            |t| matches!(t, Atomic::TMixed | Atomic::TScalar | Atomic::TNumeric),
            Atomic::TFloat,
        )
    }

    /// Narrow as if `is_bool($x)` is true.
    pub fn narrow_to_bool(&self) -> Type {
        self.filter_replacing(
            |t| {
                matches!(
                    t,
                    Atomic::TBool | Atomic::TTrue | Atomic::TFalse | Atomic::TTemplateParam { .. }
                )
            },
            |t| matches!(t, Atomic::TMixed | Atomic::TScalar),
            Atomic::TBool,
        )
    }

    /// Narrow as if `is_null($x)` is true.
    pub fn narrow_to_null(&self) -> Type {
        self.filter_replacing(
            |t| matches!(t, Atomic::TNull | Atomic::TTemplateParam { .. }),
            |t| matches!(t, Atomic::TMixed),
            Atomic::TNull,
        )
    }

    /// Narrow as if `is_array($x)` is true.
    pub fn narrow_to_array(&self) -> Type {
        self.filter_replacing(
            |t| t.is_array() || matches!(t, Atomic::TTemplateParam { .. }),
            |t| matches!(t, Atomic::TMixed),
            Atomic::TArray {
                key: Box::new(Type::mixed()),
                value: Box::new(Type::mixed()),
            },
        )
    }

    /// Narrow array/list types to their non-empty variants (for `count() > 0` etc.).
    pub fn narrow_to_non_empty_collection(&self) -> Type {
        let mut out = Type::empty();
        out.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                Atomic::TArray { key, value } => out.add_type(Atomic::TNonEmptyArray {
                    key: key.clone(),
                    value: value.clone(),
                }),
                Atomic::TList { value } => out.add_type(Atomic::TNonEmptyList {
                    value: value.clone(),
                }),
                _ => out.add_type(t.clone()),
            }
        }
        out
    }

    /// Narrow array/list types when proven empty (e.g. `array_key_first($x) === null`,
    /// `$arr === []`). Drops the non-empty variants outright — they can never
    /// be empty — and narrows a plain `array`/`list` down to the same closed,
    /// zero-property `TKeyedArray` an empty `[]` literal itself types as, so
    /// e.g. `$values[0]` on a proven-empty branch is flagged as a
    /// `NonExistentArrayOffset` instead of silently keeping the pre-narrow
    /// element type. `TKeyedArray` atoms are left unchanged — narrowing an
    /// already-shaped array to "empty" when it may declare required
    /// properties is a separate, more nuanced case.
    pub fn narrow_to_empty_collection(&self) -> Type {
        let mut out = Type::empty();
        out.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                Atomic::TNonEmptyArray { .. } | Atomic::TNonEmptyList { .. } => {}
                Atomic::TArray { .. } | Atomic::TList { .. } => {
                    out.add_type(Atomic::TKeyedArray {
                        properties: Box::default(),
                        is_open: false,
                        is_list: true,
                    });
                }
                _ => out.add_type(t.clone()),
            }
        }
        out
    }

    /// Narrow as if `array_is_list($x)` is true.
    /// Lists have sequential integer keys starting from 0, so:
    /// - `list<T>` / `non-empty-list<T>` are kept unchanged.
    /// - `array<int, T>` is narrowed to `list<T>` (could be sequential).
    /// - `non-empty-array<int, T>` is narrowed to `non-empty-list<T>`.
    /// - `TKeyedArray` (shape) is kept only when its own `is_list` flag is
    ///   already true — that flag is precise (set from the actual literal's
    ///   keys, or an explicit `list{...}` docblock), not a hint, so a
    ///   string-keyed or non-contiguous shape is correctly excluded.
    /// - `mixed` becomes `list<mixed>` (array_is_list implies array).
    /// - All other types (string-keyed arrays, non-arrays) are dropped.
    pub fn narrow_to_list(&self) -> Type {
        let mut out = Type::empty();
        out.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                Atomic::TList { .. } | Atomic::TNonEmptyList { .. } => out.add_type(t.clone()),
                // Guard on "key admits int" rather than "key is exactly TInt" —
                // `is_array($mixed)` narrows an unknown key to `Type::mixed()`,
                // which is a list candidate (the runtime shape is still unknown),
                // unlike a key statically known to exclude int entirely (e.g. a
                // docblock-declared `array<string, T>`), which must stay excluded.
                Atomic::TArray { key, value } if !key.narrow_to_int().is_empty() => {
                    out.add_type(Atomic::TList {
                        value: value.clone(),
                    });
                }
                Atomic::TNonEmptyArray { key, value } if !key.narrow_to_int().is_empty() => {
                    out.add_type(Atomic::TNonEmptyList {
                        value: value.clone(),
                    });
                }
                Atomic::TKeyedArray { is_list: true, .. } => out.add_type(t.clone()),
                Atomic::TMixed => out.add_type(Atomic::TList {
                    value: Box::new(Type::mixed()),
                }),
                _ => {}
            }
        }
        if out.is_empty() {
            self.filter(|t| matches!(t, Atomic::TList { .. } | Atomic::TNonEmptyList { .. }))
        } else {
            out
        }
    }

    /// Narrow as if `is_object($x)` is true. A `mixed` becomes a concrete bare
    /// `object` (rather than staying `mixed`) so downstream object-only
    /// operations — `clone`, `instanceof`, method calls — see an object type
    /// instead of reporting `Mixed*`.
    pub fn narrow_to_object(&self) -> Type {
        let mut out = Type::empty();
        for t in &self.types {
            if matches!(t, Atomic::TMixed) {
                out.add_type(Atomic::TObject);
            } else if t.is_object() || matches!(t, Atomic::TTemplateParam { .. }) {
                out.add_type(t.clone());
            }
        }
        if out.types.is_empty() {
            self.filter(|t| t.is_object())
        } else {
            out
        }
    }

    /// Narrow as if `is_callable($x)` is true.
    ///
    /// PHP accepts closures, TCallable, strings (function names), arrays
    /// (['Class', 'method'] or [$obj, 'method']), and objects with __invoke.
    /// Keep all of these; only drop atoms that are definitely not callable
    /// (scalars, null, bool, etc.).
    pub fn narrow_to_callable(&self) -> Type {
        let narrowed = self.filter(|t| {
            t.is_callable()
                || t.is_string()
                || t.is_array()
                || t.is_object()
                || matches!(t, Atomic::TMixed | Atomic::TTemplateParam { .. })
        });
        // A bare `object` carries no known `__invoke` signature to compare
        // against a `callable`-typed target, so it stayed an object rather
        // than satisfying one — represent it as a generic callable instead,
        // matching what `is_callable()` actually proved. A `TNamedObject`
        // keeps its own class (its real `__invoke`, if any, is more precise
        // than a generic callable).
        let mut result = Type::empty();
        result.possibly_undefined = narrowed.possibly_undefined;
        result.from_docblock = narrowed.from_docblock;
        for atomic in narrowed.types {
            if matches!(atomic, Atomic::TObject) {
                result.add_type(Atomic::TCallable {
                    params: None,
                    return_type: None,
                });
            } else {
                result.add_type(atomic);
            }
        }
        result
    }

    /// Narrow as if `is_scalar($x)` is true (int | string | float | bool).
    pub fn narrow_to_scalar(&self) -> Type {
        self.filter_replacing(
            |t| {
                t.is_string()
                    || t.is_int()
                    || matches!(
                        t,
                        Atomic::TFloat
                            | Atomic::TIntegralFloat
                            | Atomic::TLiteralFloat(..)
                            | Atomic::TBool
                            | Atomic::TTrue
                            | Atomic::TFalse
                            | Atomic::TScalar
                            | Atomic::TNumeric
                            | Atomic::TNumericString
                            | Atomic::TTemplateParam { .. }
                    )
            },
            |t| matches!(t, Atomic::TMixed),
            Atomic::TScalar,
        )
    }

    /// Narrow as if `is_iterable($x)` is true (array | Traversable).
    /// For simplicity, this narrows to arrays or objects (can't easily verify interfaces).
    pub fn narrow_to_iterable(&self) -> Type {
        self.filter(|t| {
            t.is_array()
                || t.is_object()
                || matches!(t, Atomic::TMixed | Atomic::TTemplateParam { .. })
        })
    }

    /// Narrow as if `is_countable($x)` is true (array | Countable).
    /// For simplicity, this narrows to arrays or objects (can't easily verify Countable interface).
    pub fn narrow_to_countable(&self) -> Type {
        self.filter(|t| {
            t.is_array()
                || t.is_object()
                || matches!(t, Atomic::TMixed | Atomic::TTemplateParam { .. })
        })
    }

    /// Narrow as if `is_resource($x)` is true.
    /// Note: No TResource atomic type exists in the type system; this is a no-op.
    /// Resources are declining in modern PHP and not actively tracked.
    pub fn narrow_to_resource(&self) -> Type {
        // No resource type in the system; just return mixed (allows any type)
        self.filter(|t| matches!(t, Atomic::TMixed))
    }

    /// Narrow as if `class_exists($x)` returned true for a string variable.
    /// String atoms become `class-string`; existing class-string atoms pass through;
    /// mixed/scalar becomes `class-string`. Non-string atoms are dropped (returning
    /// empty so the caller can mark the branch as diverging).
    pub fn narrow_to_class_string(&self) -> Type {
        let mut out = Type::empty();
        out.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                Atomic::TClassString(_) => out.add_type(t.clone()),
                _ if t.is_string() || matches!(t, Atomic::TMixed | Atomic::TScalar) => {
                    out.add_type(Atomic::TClassString(None));
                }
                _ => {}
            }
        }
        out
    }

    /// Narrow as if `interface_exists($x)` returned true for a string variable.
    /// String atoms become `interface-string`; existing interface-string atoms pass
    /// through; mixed/scalar becomes `interface-string`. Non-string atoms are dropped
    /// (returning empty so the caller can mark the branch as diverging).
    pub fn narrow_to_interface_string(&self) -> Type {
        let mut out = Type::empty();
        out.from_docblock = self.from_docblock;
        for t in &self.types {
            match t {
                Atomic::TInterfaceString(_) => out.add_type(t.clone()),
                // A known class-string keeps its name — every interface-string is
                // also a valid class-string, so `interface_exists()` returning true
                // narrows the atom without losing which class it names.
                Atomic::TClassString(name) => {
                    out.add_type(Atomic::TInterfaceString(*name));
                }
                _ if t.is_string() || matches!(t, Atomic::TMixed | Atomic::TScalar) => {
                    out.add_type(Atomic::TInterfaceString(None));
                }
                _ => {}
            }
        }
        out
    }

    // --- Merge (branch join) ------------------------------------------------

    /// Merge two unions at a branch join point (e.g. after if/else).
    /// The result is the union of all types in both.
    pub fn merge(a: &Type, b: &Type) -> Type {
        // Fast path: b is empty — nothing to add.
        if b.types.is_empty() {
            let mut result = a.clone();
            result.possibly_undefined = a.possibly_undefined || b.possibly_undefined;
            return result;
        }
        // Fast path: a is empty — clone b.
        if a.types.is_empty() {
            let mut result = b.clone();
            result.possibly_undefined = a.possibly_undefined || b.possibly_undefined;
            return result;
        }
        // Fast path: a is already mixed — b cannot widen it further.
        if a.types.len() == 1 && matches!(a.types[0], Atomic::TMixed) {
            let mut result = a.clone();
            result.possibly_undefined = a.possibly_undefined || b.possibly_undefined;
            return result;
        }
        // Fast path: b contains mixed — result collapses to mixed.
        if b.types.iter().any(|t| matches!(t, Atomic::TMixed)) {
            return Type {
                types: smallvec::smallvec![Atomic::TMixed],
                possibly_undefined: a.possibly_undefined || b.possibly_undefined,
                from_docblock: a.from_docblock || b.from_docblock,
                falsy_stripped: false,
            };
        }
        let mut result = a.clone();
        result.merge_with(b);
        result
    }

    /// Merge `other` into `self` in-place (avoids cloning `self`).
    pub fn merge_with(&mut self, other: &Type) {
        if self.types.iter().any(|t| matches!(t, Atomic::TMixed)) {
            self.possibly_undefined |= other.possibly_undefined;
            return;
        }
        if other.types.iter().any(|t| matches!(t, Atomic::TMixed)) {
            self.types.clear();
            self.types.push(Atomic::TMixed);
            self.possibly_undefined |= other.possibly_undefined;
            return;
        }
        for atomic in &other.types {
            self.add_type(atomic.clone());
        }
        self.possibly_undefined |= other.possibly_undefined;
    }

    /// Intersect with another union: keep only types present in `other`, widening
    /// where `self` contains `mixed` (which is compatible with everything).
    /// Used for match-arm subject narrowing.
    pub fn intersect_with(&self, other: &Type) -> Type {
        if self.is_mixed() {
            return other.clone();
        }
        if other.is_mixed() {
            return self.clone();
        }
        // Keep the more specific of each overlapping (self, other) atomic
        // pair — e.g. intersecting `int` with `1|2` must keep `1|2` (the
        // narrower side), not `int` (self's own, wider atomic): the whole
        // point of narrowing a variable against a match/switch arm's
        // literal conditions is to end up with the literal, not the bare
        // declared type it already had. Every matching pair is kept (not
        // just the first), so `int ∩ (1|2)` keeps both `1` and `2`.
        let mut result = Type::empty();
        for a in &self.types {
            for b in &other.types {
                if a == b {
                    result.add_type(a.clone());
                } else if atomic_subtype(b, a) {
                    result.add_type(b.clone());
                } else if atomic_subtype(a, b) {
                    result.add_type(a.clone());
                }
            }
        }
        if result.is_empty() {
            Type::never()
        } else {
            result
        }
    }

    // --- Template substitution ----------------------------------------------

    /// Replace template param references with their resolved types.
    pub fn substitute_templates(&self, bindings: &FxHashMap<Name, Type>) -> Type {
        if bindings.is_empty() {
            return self.clone();
        }
        // Most argument/return types are plain scalars or resolved objects
        // with nothing to substitute — skip the rebuild entirely.
        if !self.types.iter().any(atomic_may_contain_templates) {
            return self.clone();
        }
        let mut result = Type::empty();
        result.possibly_undefined = self.possibly_undefined;
        result.from_docblock = self.from_docblock;
        for atomic in &self.types {
            match atomic {
                Atomic::TTemplateParam { name, .. } => {
                    if let Some(resolved) = bindings.get(name) {
                        for t in &resolved.types {
                            result.add_type(t.clone());
                        }
                    } else {
                        result.add_type(atomic.clone());
                    }
                }
                Atomic::TArray { key, value } => {
                    result.add_type(Atomic::TArray {
                        key: Box::new(key.substitute_templates(bindings)),
                        value: Box::new(value.substitute_templates(bindings)),
                    });
                }
                Atomic::TList { value } => {
                    result.add_type(Atomic::TList {
                        value: Box::new(value.substitute_templates(bindings)),
                    });
                }
                Atomic::TNonEmptyArray { key, value } => {
                    result.add_type(Atomic::TNonEmptyArray {
                        key: Box::new(key.substitute_templates(bindings)),
                        value: Box::new(value.substitute_templates(bindings)),
                    });
                }
                Atomic::TNonEmptyList { value } => {
                    result.add_type(Atomic::TNonEmptyList {
                        value: Box::new(value.substitute_templates(bindings)),
                    });
                }
                Atomic::TKeyedArray {
                    properties,
                    is_open,
                    is_list,
                } => {
                    use crate::atomic::KeyedProperty;
                    let new_props = properties
                        .iter()
                        .map(|(k, prop)| {
                            (
                                k.clone(),
                                KeyedProperty {
                                    ty: prop.ty.substitute_templates(bindings),
                                    optional: prop.optional,
                                },
                            )
                        })
                        .collect();
                    result.add_type(Atomic::TKeyedArray {
                        properties: Box::new(new_props),
                        is_open: *is_open,
                        is_list: *is_list,
                    });
                }
                Atomic::TCallable {
                    params,
                    return_type,
                } => {
                    result.add_type(Atomic::TCallable {
                        params: params.as_ref().map(|ps| {
                            ps.iter()
                                .map(|p| substitute_in_fn_param(p, bindings))
                                .collect()
                        }),
                        return_type: return_type
                            .as_ref()
                            .map(|r| Box::new(r.substitute_templates(bindings))),
                    });
                }
                Atomic::TClosure { data } => {
                    result.add_type(Atomic::TClosure {
                        data: Box::new(crate::atomic::ClosureData {
                            params: data
                                .params
                                .iter()
                                .map(|p| substitute_in_fn_param(p, bindings))
                                .collect(),
                            return_type: data.return_type.substitute_templates(bindings),
                            this_type: data
                                .this_type
                                .as_ref()
                                .map(|t| t.substitute_templates(bindings)),
                        }),
                    });
                }
                Atomic::TConditional { data } => {
                    let param_name = &data.param_name;
                    let new_subject = data.subject.substitute_templates(bindings);
                    let new_if_true = data.if_true.substitute_templates(bindings);
                    let new_if_false = data.if_false.substitute_templates(bindings);

                    // If param_name names a template that is bound in this substitution,
                    // resolve the conditional immediately using the same predicate logic as
                    // `resolve_conditional_returns` for the $param form.
                    let resolved = if let Some(name) = param_name {
                        if let Some(bound) = bindings.get(name) {
                            if new_subject.types.len() == 1 {
                                resolve_conditional_branch(
                                    &new_subject.types[0],
                                    bound,
                                    &new_if_true,
                                    &new_if_false,
                                )
                            } else {
                                None
                            }
                        } else {
                            None
                        }
                    } else {
                        None
                    };

                    if let Some(branch) = resolved {
                        for t in branch.types {
                            result.add_type(t);
                        }
                    } else {
                        result.add_type(Atomic::TConditional {
                            data: Box::new(crate::atomic::ConditionalData {
                                param_name: *param_name,
                                subject: new_subject,
                                if_true: new_if_true,
                                if_false: new_if_false,
                            }),
                        });
                    }
                }
                Atomic::TIntersection { parts } => {
                    result.add_type(Atomic::TIntersection {
                        parts: vec_to_type_params(
                            parts
                                .iter()
                                .map(|p| p.substitute_templates(bindings))
                                .collect(),
                        ),
                    });
                }
                Atomic::TNamedObject { fqcn, type_params } => {
                    // TODO: the docblock parser emits TNamedObject { fqcn: "T" } for bare @return T
                    // annotations instead of TTemplateParam, because it lacks template context at
                    // parse time. This block works around that by treating bare unqualified names
                    // as template param references when they appear in the binding map. Proper fix:
                    // make the docblock parser template-aware so it emits TTemplateParam directly.
                    // See issue #26 for context.
                    if type_params.is_empty() && !fqcn.contains('\\') {
                        if let Some(resolved) = bindings.get(fqcn) {
                            for t in &resolved.types {
                                result.add_type(t.clone());
                            }
                            continue;
                        }
                    }
                    let new_params: Vec<Type> = type_params
                        .iter()
                        .map(|p| p.substitute_templates(bindings))
                        .collect();
                    result.add_type(Atomic::TNamedObject {
                        fqcn: *fqcn,
                        type_params: vec_to_type_params(new_params),
                    });
                }
                // class-string<T> → substitute T from bindings
                Atomic::TClassString(Some(param_name)) => {
                    if let Some(resolved) = bindings.get(param_name) {
                        for r_atomic in &resolved.types {
                            let cls_name = if let Atomic::TNamedObject { fqcn, .. } = r_atomic {
                                Some(*fqcn)
                            } else {
                                None
                            };
                            result.add_type(Atomic::TClassString(cls_name));
                        }
                    } else {
                        result.add_type(atomic.clone());
                    }
                }
                // interface-string<T> → substitute T from bindings
                Atomic::TInterfaceString(Some(param_name)) => {
                    if let Some(resolved) = bindings.get(param_name) {
                        for r_atomic in &resolved.types {
                            let iface_name = if let Atomic::TNamedObject { fqcn, .. } = r_atomic {
                                Some(*fqcn)
                            } else {
                                None
                            };
                            result.add_type(Atomic::TInterfaceString(iface_name));
                        }
                    } else {
                        result.add_type(atomic.clone());
                    }
                }
                _ => {
                    result.add_type(atomic.clone());
                }
            }
        }
        result
    }

    /// Resolves `TConditional` atoms whose discriminator is known at the call site.
    ///
    /// `lookup(param_name)` returns the call-site argument type for the named parameter,
    /// or `None` if the argument is not available. Handles `is null`, `is string`, and
    /// `is array` conditions; other condition types pass through unchanged.
    pub fn resolve_conditional_returns<F>(self, lookup: F) -> Type
    where
        F: Fn(&str) -> Option<Type>,
    {
        self.resolve_conditional_inner(&lookup)
    }

    fn resolve_conditional_inner<F>(self, lookup: &F) -> Type
    where
        F: Fn(&str) -> Option<Type>,
    {
        let mut result = Type::empty();
        for atomic in self.types {
            match atomic {
                Atomic::TConditional { ref data } => {
                    let (param_name, subject, if_true, if_false) = (
                        &data.param_name,
                        &data.subject,
                        &data.if_true,
                        &data.if_false,
                    );
                    let resolved = if subject.types.len() == 1 {
                        if let Some(name) = param_name {
                            if let Some(arg_ty) = lookup(name.as_ref()) {
                                resolve_conditional_branch(
                                    &subject.types[0],
                                    &arg_ty,
                                    if_true,
                                    if_false,
                                )
                            } else {
                                None
                            }
                        } else {
                            None
                        }
                    } else {
                        None
                    };

                    if let Some(branch) = resolved {
                        // Recursively resolve nested conditionals in the selected branch.
                        for t in branch.resolve_conditional_inner(lookup).types {
                            result.add_type(t);
                        }
                    } else {
                        // Cannot resolve at this call site: widen to the union of both branches.
                        // Recursively resolve nested conditionals in each branch.
                        for t in if_true.clone().resolve_conditional_inner(lookup).types {
                            result.add_type(t);
                        }
                        for t in if_false.clone().resolve_conditional_inner(lookup).types {
                            result.add_type(t);
                        }
                    }
                }
                other => result.add_type(other),
            }
        }
        result
    }

    // --- Subtype check -------------------------------------------------------

    /// Returns true if every atomic in `self` is a subtype of some atomic in `other`,
    /// using **only structural rules** — no `extends` / `implements` walk.
    ///
    /// Two distinct user-defined classes are never related here, even when one
    /// extends the other. Within `mir-analyzer`, when a `db` is in scope,
    /// prefer `crate::subtype::is_subtype(db, sub, sup)` which layers
    /// inheritance resolution on top of this check.
    pub fn is_subtype_structural(&self, other: &Type) -> bool {
        if other.is_mixed() {
            return true;
        }
        if self.is_never() {
            return true; // never <: everything
        }
        self.types
            .iter()
            .all(|a| other.types.iter().any(|b| atomic_subtype(a, b)))
    }

    /// `sub <: self`, structurally, for a single atomic — equivalent to
    /// `Type::single(sub.clone()).is_subtype_structural(self)` without the
    /// clone and the temporary single-atomic union.
    pub fn accepts_atomic_structural(&self, sub: &Atomic) -> bool {
        if self.is_mixed() {
            return true;
        }
        matches!(sub, Atomic::TNever) || self.types.iter().any(|b| atomic_subtype(sub, b))
    }

    // --- Utilities ----------------------------------------------------------

    fn filter<F: Fn(&Atomic) -> bool>(&self, f: F) -> Type {
        let mut result = Type::empty();
        result.possibly_undefined = self.possibly_undefined;
        result.from_docblock = self.from_docblock;
        for atomic in &self.types {
            if f(atomic) {
                result.types.push(atomic.clone());
            }
        }
        result
    }

    /// Like `filter`, but atoms matching `placeholder` are substituted with
    /// `replacement` instead of passing through unchanged. Used so narrowing
    /// an unrefined `mixed`/`scalar`/`numeric` value (e.g. via `is_int($x)`)
    /// yields the concrete narrowed type instead of staying `mixed`.
    fn filter_replacing<K: Fn(&Atomic) -> bool, P: Fn(&Atomic) -> bool>(
        &self,
        keep: K,
        placeholder: P,
        replacement: Atomic,
    ) -> Type {
        let mut result = Type::empty();
        result.possibly_undefined = self.possibly_undefined;
        result.from_docblock = self.from_docblock;
        for atomic in &self.types {
            if keep(atomic) {
                result.add_type(atomic.clone());
            } else if placeholder(atomic) {
                result.add_type(replacement.clone());
            }
        }
        result
    }

    /// Mark this union as possibly-undefined and return it.
    pub fn possibly_undefined(mut self) -> Self {
        self.possibly_undefined = true;
        self
    }

    /// Mark this union as coming from a docblock annotation.
    pub fn from_docblock(mut self) -> Self {
        self.from_docblock = true;
        self
    }

    /// Mark this union as having had a `false`/`null` failure variant stripped
    /// for flow purposes (see the field doc on [`Type::falsy_stripped`]).
    pub fn falsy_stripped(mut self) -> Self {
        self.falsy_stripped = true;
        self
    }
}

// ---------------------------------------------------------------------------
// Conditional return resolution helpers
// ---------------------------------------------------------------------------

fn is_string_atomic(a: &Atomic) -> bool {
    matches!(
        a,
        Atomic::TString
            | Atomic::TNonEmptyString
            | Atomic::TLiteralString(_)
            | Atomic::TNumericString
            | Atomic::TClassString(_)
            | Atomic::TInterfaceString(_)
            | Atomic::TCallableString
    )
}

fn is_array_atomic(a: &Atomic) -> bool {
    matches!(
        a,
        Atomic::TArray { .. }
            | Atomic::TNonEmptyArray { .. }
            | Atomic::TKeyedArray { .. }
            | Atomic::TList { .. }
            | Atomic::TNonEmptyList { .. }
    )
}

fn is_list_atomic(a: &Atomic) -> bool {
    match a {
        Atomic::TList { .. } | Atomic::TNonEmptyList { .. } => true,
        Atomic::TKeyedArray { is_list, .. } => *is_list,
        _ => false,
    }
}

fn is_float_atomic(a: &Atomic) -> bool {
    matches!(
        a,
        Atomic::TFloat | Atomic::TIntegralFloat | Atomic::TLiteralFloat(..)
    )
}

fn is_bool_atomic(a: &Atomic) -> bool {
    matches!(a, Atomic::TBool | Atomic::TTrue | Atomic::TFalse)
}

/// Resolve one branch of a conditional return type given the subject discriminant
/// atomic and the actual argument type at the call site.
///
/// Returns `Some(branch)` when the branch can be determined statically, or `None`
/// to signal that the caller should widen to the union of both branches.
fn resolve_conditional_branch(
    subject: &Atomic,
    arg_ty: &Type,
    if_true: &Type,
    if_false: &Type,
) -> Option<Type> {
    let predicate: fn(&Atomic) -> bool = match subject {
        Atomic::TNull => |a| matches!(a, Atomic::TNull),
        Atomic::TTrue => |a| matches!(a, Atomic::TTrue),
        Atomic::TFalse => |a| matches!(a, Atomic::TFalse),
        Atomic::TString => is_string_atomic,
        Atomic::TList { .. } => is_list_atomic,
        Atomic::TArray { .. } => is_array_atomic,
        Atomic::TInt => Atomic::is_int,
        Atomic::TFloat => is_float_atomic,
        Atomic::TBool => is_bool_atomic,
        _ => return None,
    };

    if arg_ty.types.is_empty() {
        return None;
    }
    let all_match = arg_ty.types.iter().all(&predicate);
    let none_match = !arg_ty.types.iter().any(predicate);
    if all_match {
        Some(if_true.clone())
    } else if none_match {
        Some(if_false.clone())
    } else {
        None
    }
}

// ---------------------------------------------------------------------------
// Template substitution helpers
// ---------------------------------------------------------------------------

/// Whether `substitute_templates` could change this atomic: it is either a
/// template reference itself or a container/callable that may hold one.
/// Mirrors the substituting arms of that function's match — keep in sync.
fn atomic_may_contain_templates(atomic: &Atomic) -> bool {
    match atomic {
        // Bare unqualified names double as template refs (docblock parser
        // workaround, see substitute_templates); qualified names only matter
        // when they carry generic params.
        Atomic::TNamedObject { fqcn, type_params } => {
            !type_params.is_empty() || !fqcn.contains('\\')
        }
        Atomic::TTemplateParam { .. }
        | Atomic::TArray { .. }
        | Atomic::TList { .. }
        | Atomic::TNonEmptyArray { .. }
        | Atomic::TNonEmptyList { .. }
        | Atomic::TKeyedArray { .. }
        | Atomic::TCallable { .. }
        | Atomic::TClosure { .. }
        | Atomic::TConditional { .. }
        | Atomic::TIntersection { .. }
        | Atomic::TClassString(Some(_))
        | Atomic::TInterfaceString(Some(_)) => true,
        _ => false,
    }
}

fn substitute_in_fn_param(
    p: &crate::atomic::FnParam,
    bindings: &FxHashMap<Name, Type>,
) -> crate::atomic::FnParam {
    crate::atomic::FnParam {
        name: p.name,
        ty: p.ty.as_ref().map(|t| {
            let u = t.to_union();
            let substituted = u.substitute_templates(bindings);
            crate::compact::SimpleType::from_union(substituted)
        }),
        out_ty: p.out_ty.as_ref().map(|t| {
            let u = t.to_union();
            let substituted = u.substitute_templates(bindings);
            crate::compact::SimpleType::from_union(substituted)
        }),
        default: p.default.as_ref().map(|d| {
            let u = d.to_union();
            let substituted = u.substitute_templates(bindings);
            crate::compact::SimpleType::from_union(substituted)
        }),
        is_variadic: p.is_variadic,
        is_byref: p.is_byref,
        is_optional: p.is_optional,
    }
}

// ---------------------------------------------------------------------------
// Atomic subtype (no codebase — structural check only)
// ---------------------------------------------------------------------------

/// Structural `sub <: sup` for a single atomic pair, without hierarchy resolution.
pub fn atomic_subtype(sub: &Atomic, sup: &Atomic) -> bool {
    if sub == sup {
        return true;
    }
    match (sub, sup) {
        // Bottom type
        (Atomic::TNever, _) => true,
        // Top types — anything goes in both directions for mixed
        (_, Atomic::TMixed) => true,
        (Atomic::TMixed, _) => true,
        // Template param in supertype position: any value satisfies an unconstrained
        // template (as_type = mixed), or a constrained one if it satisfies the bound.
        // This handles union bounds like `T of string|list<I>|array<K, V>` where
        // I/K/V are free template params — any type satisfies them structurally.
        (_, Atomic::TTemplateParam { as_type, .. }) => {
            as_type.is_mixed() || as_type.types.iter().any(|b| atomic_subtype(sub, b))
        }

        // Scalars
        (Atomic::TLiteralInt(_), Atomic::TInt) => true,
        (Atomic::TLiteralInt(_), Atomic::TNumeric) => true,
        (Atomic::TLiteralInt(_), Atomic::TScalar) => true,
        (Atomic::TLiteralInt(n), Atomic::TPositiveInt) => *n > 0,
        (Atomic::TLiteralInt(n), Atomic::TNonNegativeInt) => *n >= 0,
        (Atomic::TLiteralInt(n), Atomic::TNegativeInt) => *n < 0,
        (Atomic::TPositiveInt, Atomic::TInt) => true,
        (Atomic::TPositiveInt, Atomic::TNonNegativeInt) => true,
        (Atomic::TPositiveInt, Atomic::TNumeric) => true,
        (Atomic::TPositiveInt, Atomic::TScalar) => true,
        (Atomic::TNegativeInt, Atomic::TInt) => true,
        (Atomic::TNegativeInt, Atomic::TNumeric) => true,
        (Atomic::TNegativeInt, Atomic::TScalar) => true,
        (Atomic::TNonNegativeInt, Atomic::TInt) => true,
        (Atomic::TNonNegativeInt, Atomic::TNumeric) => true,
        (Atomic::TNonNegativeInt, Atomic::TScalar) => true,
        (Atomic::TIntRange { .. }, Atomic::TInt) => true,
        (Atomic::TIntRange { .. }, Atomic::TNumeric) => true,
        (Atomic::TIntRange { .. }, Atomic::TScalar) => true,
        // positive-int is int<1, ∞>: subtype of int<sup_min, ∞> when sup_min <= 1
        (Atomic::TPositiveInt, Atomic::TIntRange { min, max }) => {
            max.is_none() && min.is_none_or(|m| m <= 1)
        }
        // negative-int is int<-∞, -1>: subtype of int<-∞, sup_max> when sup_max >= -1
        (Atomic::TNegativeInt, Atomic::TIntRange { min, max }) => {
            min.is_none() && max.is_none_or(|m| m >= -1)
        }
        // non-negative-int is int<0, ∞>: subtype of int<sup_min, ∞> when sup_min <= 0
        (Atomic::TNonNegativeInt, Atomic::TIntRange { min, max }) => {
            max.is_none() && min.is_none_or(|m| m <= 0)
        }
        // A bounded int range is a subtype of a named int subtype when every value fits
        (Atomic::TIntRange { min: sub_min, .. }, Atomic::TPositiveInt) => {
            sub_min.is_some_and(|lo| lo >= 1)
        }
        (Atomic::TIntRange { min: sub_min, .. }, Atomic::TNonNegativeInt) => {
            sub_min.is_some_and(|lo| lo >= 0)
        }
        (Atomic::TIntRange { max: sub_max, .. }, Atomic::TNegativeInt) => {
            sub_max.is_some_and(|hi| hi <= -1)
        }
        // int<sub_min, sub_max> <: int<sup_min, sup_max> when ranges nest
        (
            Atomic::TIntRange {
                min: sub_min,
                max: sub_max,
            },
            Atomic::TIntRange {
                min: sup_min,
                max: sup_max,
            },
        ) => {
            let lower_ok = match (sub_min, sup_min) {
                (_, None) => true,
                (None, Some(_)) => false,
                (Some(sl), Some(su)) => sl >= su,
            };
            let upper_ok = match (sub_max, sup_max) {
                (None, None) | (Some(_), None) => true,
                (None, Some(_)) => false,
                (Some(sl), Some(su)) => sl <= su,
            };
            lower_ok && upper_ok
        }

        (Atomic::TLiteralFloat(..), Atomic::TFloat) => true,
        (Atomic::TLiteralFloat(..), Atomic::TNumeric) => true,
        (Atomic::TLiteralFloat(..), Atomic::TScalar) => true,

        (Atomic::TLiteralString(s), Atomic::TString) => {
            let _ = s;
            true
        }
        (Atomic::TLiteralString(s), Atomic::TCallableString) => {
            let _ = s;
            true
        }
        (Atomic::TLiteralString(s), Atomic::TNonEmptyString) => !s.is_empty(),
        (Atomic::TLiteralString(s), Atomic::TNumericString) => s.parse::<f64>().is_ok(),
        // A literal string is type-compatible with class-string; validate_class_string_argument
        // separately checks whether the string names a real class (UndefinedClass).
        (Atomic::TLiteralString(_), Atomic::TClassString(_)) => true,
        // Same, for interface-string; validate_interface_string_argument checks existence
        // and that the name actually resolves to an interface.
        (Atomic::TLiteralString(_), Atomic::TInterfaceString(_)) => true,
        (Atomic::TLiteralString(_), Atomic::TScalar) => true,
        (Atomic::TNonEmptyString, Atomic::TString) => true,
        (Atomic::TCallableString, Atomic::TString) => true,
        // numeric-string is always non-empty (e.g. "42", "-1", "0.5") — "" is not numeric.
        (Atomic::TNumericString, Atomic::TNonEmptyString) => true,
        (Atomic::TNumericString, Atomic::TString) => true,
        (Atomic::TClassString(_), Atomic::TString) => true,
        (Atomic::TInterfaceString(_), Atomic::TString) => true,
        // Every interface-string is a valid class-string: PHP doesn't distinguish
        // the two at runtime — both are just strings naming a class-like symbol.
        // Instantiability (`new $x()`) is guarded separately, since an interface
        // name can never be `new`-ed even though it satisfies class-string.
        (Atomic::TInterfaceString(_), Atomic::TClassString(None)) => true,
        (Atomic::TInterfaceString(Some(a)), Atomic::TClassString(Some(b))) => a == b,
        (Atomic::TEnumString, Atomic::TString) => true,
        (Atomic::TTraitString, Atomic::TString) => true,

        (Atomic::TTrue, Atomic::TBool) => true,
        (Atomic::TFalse, Atomic::TBool) => true,

        (Atomic::TInt, Atomic::TNumeric) => true,
        (Atomic::TFloat, Atomic::TNumeric) => true,
        (Atomic::TIntegralFloat, Atomic::TNumeric) => true,
        (Atomic::TNumericString, Atomic::TNumeric) => true,

        (Atomic::TInt, Atomic::TScalar) => true,
        (Atomic::TFloat, Atomic::TScalar) => true,
        (Atomic::TIntegralFloat, Atomic::TScalar) => true,
        (Atomic::TString, Atomic::TScalar) => true,
        (Atomic::TBool, Atomic::TScalar) => true,
        (Atomic::TNumeric, Atomic::TScalar) => true,
        (Atomic::TTrue, Atomic::TScalar) => true,
        (Atomic::TFalse, Atomic::TScalar) => true,
        // Every refined string atom is, at runtime, still just a `string` —
        // and therefore a `scalar` — same as the already-covered TLiteralString
        // and int-family refinements just above/below.
        (Atomic::TNonEmptyString, Atomic::TScalar) => true,
        (Atomic::TNumericString, Atomic::TScalar) => true,
        (Atomic::TCallableString, Atomic::TScalar) => true,
        (Atomic::TClassString(_), Atomic::TScalar) => true,
        (Atomic::TInterfaceString(_), Atomic::TScalar) => true,
        (Atomic::TEnumString, Atomic::TScalar) => true,
        (Atomic::TTraitString, Atomic::TScalar) => true,

        // Object hierarchy (structural, no codebase)
        (Atomic::TNamedObject { .. }, Atomic::TObject) => true,
        (Atomic::TStaticObject { .. }, Atomic::TObject) => true,
        (Atomic::TSelf { .. }, Atomic::TObject) => true,
        // self(X) and static(X) satisfy TNamedObject(X) with same FQCN
        (Atomic::TSelf { fqcn: a }, Atomic::TNamedObject { fqcn: b, .. }) => a == b,
        (Atomic::TStaticObject { fqcn: a }, Atomic::TNamedObject { fqcn: b, .. }) => a == b,
        // TNamedObject(X) satisfies self(X) / static(X) with same FQCN
        (Atomic::TNamedObject { fqcn: a, .. }, Atomic::TSelf { fqcn: b }) => a == b,
        (Atomic::TNamedObject { fqcn: a, .. }, Atomic::TStaticObject { fqcn: b }) => a == b,
        // An enum-case literal satisfies its own bare enum type (enums are
        // represented as TNamedObject).
        (Atomic::TLiteralEnumCase { enum_fqcn, .. }, Atomic::TNamedObject { fqcn, .. }) => {
            enum_fqcn == fqcn
        }
        // Bare generic property accepts parameterized value: Box accepts Box<string>.
        // The reverse is NOT true — bare Box value does not satisfy Box<string> property
        // (invariant check). Only sup being bare (empty type_params) is the wildcard.
        (
            Atomic::TNamedObject {
                fqcn: sub_fqcn,
                type_params: sub_params,
            },
            Atomic::TNamedObject {
                fqcn: sup_fqcn,
                type_params: sup_params,
            },
        ) => {
            sub_fqcn == sup_fqcn
                && (sup_params.is_empty() || type_params_compatible(sub_params, sup_params))
        }

        // TIntegralFloat is a subtype of float (all integral floats are floats)
        (Atomic::TIntegralFloat, Atomic::TFloat) => true,

        // Literal int widens to float in PHP
        (Atomic::TLiteralInt(_), Atomic::TFloat) => true,
        (Atomic::TPositiveInt, Atomic::TFloat) => true,
        (Atomic::TNegativeInt, Atomic::TFloat) => true,
        (Atomic::TNonNegativeInt, Atomic::TFloat) => true,
        (Atomic::TInt, Atomic::TFloat) => true,
        (Atomic::TIntRange { .. }, Atomic::TFloat) => true,

        // Literal int satisfies an int range only when the value is within bounds
        (Atomic::TLiteralInt(n), Atomic::TIntRange { min, max }) => {
            min.is_none_or(|lo| *n >= lo) && max.is_none_or(|hi| *n <= hi)
        }

        // PHP callables: string and array are valid callable values
        (Atomic::TString, Atomic::TCallable { .. }) => true,
        (Atomic::TNonEmptyString, Atomic::TCallable { .. }) => true,
        (Atomic::TLiteralString(_), Atomic::TCallable { .. }) => true,
        (Atomic::TArray { .. }, Atomic::TCallable { .. }) => true,
        (Atomic::TNonEmptyArray { .. }, Atomic::TCallable { .. }) => true,
        (Atomic::TKeyedArray { .. }, Atomic::TCallable { .. }) => true,

        // Closure <: callable, typed Closure <: Closure
        (Atomic::TClosure { .. }, Atomic::TCallable { .. }) => true,
        // callable <: Closure: callable is wider but not flagged at default error level
        (Atomic::TCallable { .. }, Atomic::TClosure { .. }) => true,
        // TClosure <: TClosure: check arity, per-parameter contravariance, and
        // return covariance for scalar/array-shaped types, where a purely
        // structural check is reliable. A named-class (or nested-callable)
        // param/return is skipped rather than checked — this checker has no
        // database access to walk `extends`/`implements`, so it can't safely
        // tell a real Liskov violation apart from a legitimate subclass/
        // superclass substitution; treating it as compatible avoids false
        // positives on that far more common case at the cost of missing the
        // narrower nominal-variance violation.
        (Atomic::TClosure { data: sub }, Atomic::TClosure { data: sup }) => {
            fn has_nominal_type(t: &Type) -> bool {
                t.types.iter().any(|a| {
                    matches!(
                        a,
                        Atomic::TNamedObject { .. }
                            | Atomic::TSelf { .. }
                            | Atomic::TStaticObject { .. }
                            | Atomic::TTemplateParam { .. }
                            | Atomic::TClosure { .. }
                            | Atomic::TCallable { .. }
                    )
                })
            }
            let sub_required = sub
                .params
                .iter()
                .filter(|p| !p.is_optional && !p.is_variadic)
                .count();
            if sub_required > sup.params.len() {
                false
            } else {
                let params_ok = sup.params.iter().enumerate().all(|(i, sup_param)| {
                    let Some(sub_param) = sub.params.get(i) else {
                        return true;
                    };
                    if sub_param.is_optional || sub_param.is_variadic {
                        return true;
                    }
                    let (Some(sub_ty), Some(sup_ty)) =
                        (sub_param.ty.as_ref(), sup_param.ty.as_ref())
                    else {
                        return true;
                    };
                    let (sub_u, sup_u) = (sub_ty.to_union(), sup_ty.to_union());
                    if has_nominal_type(&sub_u) || has_nominal_type(&sup_u) {
                        return true;
                    }
                    // Contravariance: whatever `sup` promises to pass must be
                    // acceptable to `sub`'s declared parameter type.
                    sup_u.is_subtype_structural(&sub_u)
                });
                params_ok
                    && (sub.return_type.is_mixed()
                        || sup.return_type.is_mixed()
                        || has_nominal_type(&sub.return_type)
                        || has_nominal_type(&sup.return_type)
                        || sub.return_type.is_subtype_structural(&sup.return_type))
            }
        }
        // callable <: callable (trivial)
        (Atomic::TCallable { .. }, Atomic::TCallable { .. }) => true,
        // TClosure satisfies `Closure` named object or `object`
        (Atomic::TClosure { .. }, Atomic::TNamedObject { fqcn, .. }) => {
            fqcn.as_ref().eq_ignore_ascii_case("closure")
        }
        (Atomic::TClosure { .. }, Atomic::TObject) => true,
        // bare `Closure` (named object without signature) satisfies any typed Closure(): T
        (Atomic::TNamedObject { fqcn, .. }, Atomic::TClosure { .. }) => {
            fqcn.as_ref().eq_ignore_ascii_case("closure")
        }
        // `Closure` named-object satisfies `callable`
        (Atomic::TNamedObject { fqcn, .. }, Atomic::TCallable { .. }) => {
            fqcn.as_ref().eq_ignore_ascii_case("closure")
        }

        // A&B&C <: D&E iff every part of the supertype is satisfied by some
        // part of the subtype — an intersection with MORE conjuncts is the
        // more specific (sub)type, so `Countable&ArrayAccess&Iterator` is a
        // subtype of `Countable&ArrayAccess`. Purely structural (each part's
        // own `is_subtype_structural` recurses, so e.g. two differently-named
        // interfaces only match when equal — same conservative stance as the
        // TClosure<:TClosure arm above for named types).
        (
            Atomic::TIntersection { parts: sub_parts },
            Atomic::TIntersection { parts: sup_parts },
        ) => sup_parts.iter().all(|sup_part| {
            sub_parts
                .iter()
                .any(|sub_part| sub_part.is_subtype_structural(sup_part))
        }),

        // List <: array  (list key is always int; int must satisfy the array's key type)
        (Atomic::TList { value }, Atomic::TArray { key, value: av }) => {
            Type::single(Atomic::TInt).is_subtype_structural(key) && value.is_subtype_structural(av)
        }
        (Atomic::TNonEmptyList { value }, Atomic::TArray { key, value: av }) => {
            Type::single(Atomic::TInt).is_subtype_structural(key) && value.is_subtype_structural(av)
        }
        (Atomic::TNonEmptyList { value }, Atomic::TNonEmptyArray { key, value: av }) => {
            Type::single(Atomic::TInt).is_subtype_structural(key) && value.is_subtype_structural(av)
        }
        (Atomic::TNonEmptyList { value }, Atomic::TList { value: lv }) => {
            value.is_subtype_structural(lv)
        }
        // array<int, X> is accepted where list<X> or non-empty-list<X> expected
        (Atomic::TArray { key, value: av }, Atomic::TList { value: lv }) => {
            matches!(key.types.as_slice(), [Atomic::TInt | Atomic::TMixed])
                && av.is_subtype_structural(lv)
        }
        (Atomic::TArray { key, value: av }, Atomic::TNonEmptyList { value: lv }) => {
            matches!(key.types.as_slice(), [Atomic::TInt | Atomic::TMixed])
                && av.is_subtype_structural(lv)
        }
        (Atomic::TNonEmptyArray { key, value: av }, Atomic::TList { value: lv }) => {
            matches!(key.types.as_slice(), [Atomic::TInt | Atomic::TMixed])
                && av.is_subtype_structural(lv)
        }
        (Atomic::TNonEmptyArray { key, value: av }, Atomic::TNonEmptyList { value: lv }) => {
            matches!(key.types.as_slice(), [Atomic::TInt | Atomic::TMixed])
                && av.is_subtype_structural(lv)
        }
        // TList <: TList value covariance
        (Atomic::TList { value: v1 }, Atomic::TList { value: v2 }) => v1.is_subtype_structural(v2),
        (Atomic::TNonEmptyArray { key: k1, value: v1 }, Atomic::TArray { key: k2, value: v2 }) => {
            k1.is_subtype_structural(k2) && v1.is_subtype_structural(v2)
        }

        // array<A, B> <: array<C, D>  iff  A <: C && B <: D
        (Atomic::TArray { key: k1, value: v1 }, Atomic::TArray { key: k2, value: v2 }) => {
            k1.is_subtype_structural(k2) && v1.is_subtype_structural(v2)
        }

        // A keyed/shape array is a subtype of array<K, V> / non-empty-array<K, V>
        // when all property KEYS are subtypes of K. Value compatibility is checked
        // structurally only for scalar types; named-object values are deferred to
        // class-hierarchy checks in return_arrays_compatible (mir-analyzer).
        // Open shapes (is_open=true) may have extra unknown keys beyond `properties`:
        // those stay unchecked (permissive), but every KNOWN property must still
        // satisfy K/V regardless of openness — an open shape isn't a license to skip
        // checking the keys it does declare.
        (Atomic::TKeyedArray { properties, .. }, Atomic::TArray { key, value }) => {
            properties.iter().all(|(prop_key, prop)| {
                let key_atomic = match prop_key {
                    crate::atomic::ArrayKey::String(s) => Atomic::TLiteralString(s.clone()),
                    crate::atomic::ArrayKey::Int(n) => Atomic::TLiteralInt(*n),
                };
                if !Type::single(key_atomic).is_subtype_structural(key) {
                    return false; // key mismatch — definitively incompatible
                }
                // Named-object values require class-hierarchy checks not available here.
                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 || prop.ty.is_subtype_structural(value)
            })
        }
        (
            Atomic::TKeyedArray {
                properties,
                is_open,
                ..
            },
            Atomic::TNonEmptyArray { key, value },
        ) => {
            (*is_open || properties.iter().any(|(_, p)| !p.optional))
                && properties.iter().all(|(prop_key, prop)| {
                    let key_atomic = match prop_key {
                        crate::atomic::ArrayKey::String(s) => Atomic::TLiteralString(s.clone()),
                        crate::atomic::ArrayKey::Int(n) => Atomic::TLiteralInt(*n),
                    };
                    if !Type::single(key_atomic).is_subtype_structural(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 || prop.ty.is_subtype_structural(value)
                })
        }

        // A list-shaped keyed array (is_list=true, all int keys) is a subtype of list<X>.
        (
            Atomic::TKeyedArray {
                properties,
                is_list,
                ..
            },
            Atomic::TList { value: lv },
        ) => *is_list && properties.values().all(|p| p.ty.is_subtype_structural(lv)),
        (
            Atomic::TKeyedArray {
                properties,
                is_list,
                ..
            },
            Atomic::TNonEmptyList { value: lv },
        ) => {
            *is_list
                && !properties.is_empty()
                && properties.values().all(|p| p.ty.is_subtype_structural(lv))
        }

        // Two shapes: every sup key must be satisfied (present+compatible, or
        // absent-but-optional/sub-open), and sub may not have keys sup doesn't
        // declare unless sup itself is open. Named-object values are deferred
        // to class-hierarchy checks, same as the TArray/TList sup arms above.
        (
            Atomic::TKeyedArray {
                properties: sub_props,
                is_open: sub_open,
                ..
            },
            Atomic::TKeyedArray {
                properties: sup_props,
                is_open: sup_open,
                ..
            },
        ) => {
            let keys_satisfied = sup_props
                .iter()
                .all(|(key, sup_prop)| match sub_props.get(key) {
                    Some(sub_prop) => {
                        // A key merely optional on the sub side may legally be
                        // absent at runtime, so it can't satisfy a sup key that
                        // requires it present.
                        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 || sub_prop.ty.is_subtype_structural(&sup_prop.ty)
                    }
                    None => sup_prop.optional || *sub_open,
                });
            let no_undeclared_extras =
                *sup_open || sub_props.keys().all(|k| sup_props.contains_key(k));
            keys_satisfied && no_undeclared_extras
        }

        _ => false,
    }
}

/// Whether each generic type-argument in `sub` is compatible with the
/// corresponding argument in `sup`. Arguments are invariant (require structural
/// equality) with one exception: an empty array literal (`array{}`) is accepted
/// against any array/list argument, so `new Box([])` — inferred as
/// `Box<array{}>` — satisfies a declared `Box<list<T>>` for any `T`.
fn type_params_compatible(sub: &[Type], sup: &[Type]) -> bool {
    if sub.len() != sup.len() {
        return false;
    }
    sub.iter()
        .zip(sup.iter())
        .all(|(a, b)| a == b || (is_empty_array_literal(a) && is_array_like(b)))
}

/// True for a non-empty union whose atoms are all empty keyed arrays (`array{}`),
/// i.e. the type of an empty array literal `[]`.
fn is_empty_array_literal(t: &Type) -> bool {
    !t.types.is_empty()
        && t.types.iter().all(
            |atom| matches!(atom, Atomic::TKeyedArray { properties, .. } if properties.is_empty()),
        )
}

/// True for a non-empty union whose atoms are all array/list types.
fn is_array_like(t: &Type) -> bool {
    !t.types.is_empty() && t.types.iter().all(|atom| atom.is_array())
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use std::sync::Arc;

    use super::*;

    fn conditional(
        param_name: Option<Name>,
        subject: Type,
        if_true: Type,
        if_false: Type,
    ) -> Atomic {
        Atomic::TConditional {
            data: Box::new(crate::atomic::ConditionalData {
                param_name,
                subject,
                if_true,
                if_false,
            }),
        }
    }

    #[test]
    fn single_is_single() {
        let u = Type::single(Atomic::TString);
        assert!(u.is_single());
        assert!(!u.is_nullable());
    }

    #[test]
    fn nullable_has_null() {
        let u = Type::nullable(Atomic::TString);
        assert!(u.is_nullable());
        assert_eq!(u.types.len(), 2);
    }

    #[test]
    fn add_type_deduplicates() {
        let mut u = Type::single(Atomic::TString);
        u.add_type(Atomic::TString);
        assert_eq!(u.types.len(), 1);
    }

    #[test]
    fn array_key_is_int_string() {
        let k = Type::array_key();
        assert!(k.is_array_key());
        assert_eq!(k.types.len(), 2);
    }

    #[test]
    fn is_array_key_false_for_plain_int() {
        assert!(!Type::int().is_array_key());
    }

    #[test]
    fn is_array_key_false_for_mixed() {
        assert!(!Type::mixed().is_array_key());
    }

    #[test]
    fn is_array_key_false_for_int_string_null() {
        let mut u = Type::array_key();
        u.add_type(Atomic::TNull);
        assert!(!u.is_array_key());
    }

    #[test]
    fn add_type_literal_subsumed_by_base() {
        let mut u = Type::single(Atomic::TInt);
        u.add_type(Atomic::TLiteralInt(42));
        assert_eq!(u.types.len(), 1);
        assert!(matches!(u.types[0], Atomic::TInt));
    }

    #[test]
    fn true_then_false_merges_to_bool() {
        let mut u = Type::single(Atomic::TTrue);
        u.add_type(Atomic::TFalse);
        assert_eq!(u.types.len(), 1);
        assert!(matches!(u.types[0], Atomic::TBool));
    }

    #[test]
    fn false_then_true_merges_to_bool() {
        let mut u = Type::single(Atomic::TFalse);
        u.add_type(Atomic::TTrue);
        assert_eq!(u.types.len(), 1);
        assert!(matches!(u.types[0], Atomic::TBool));
    }

    #[test]
    fn true_alone_stays_true() {
        let u = Type::single(Atomic::TTrue);
        assert_eq!(u.types.len(), 1);
        assert!(matches!(u.types[0], Atomic::TTrue));
    }

    #[test]
    fn true_false_merge_preserves_other_union_members() {
        let mut u = Type::single(Atomic::TTrue);
        u.add_type(Atomic::TNull);
        u.add_type(Atomic::TFalse);
        assert_eq!(u.types.len(), 2);
        assert!(u.contains(|t| matches!(t, Atomic::TBool)));
        assert!(u.contains(|t| matches!(t, Atomic::TNull)));
    }

    #[test]
    fn add_type_base_widens_literals() {
        let mut u = Type::single(Atomic::TLiteralInt(1));
        u.add_type(Atomic::TLiteralInt(2));
        u.add_type(Atomic::TInt);
        assert_eq!(u.types.len(), 1);
        assert!(matches!(u.types[0], Atomic::TInt));
    }

    #[test]
    fn mixed_subsumes_everything() {
        let mut u = Type::single(Atomic::TString);
        u.add_type(Atomic::TMixed);
        assert_eq!(u.types.len(), 1);
        assert!(u.is_mixed());
    }

    #[test]
    fn remove_null() {
        let u = Type::nullable(Atomic::TString);
        let narrowed = u.remove_null();
        assert!(!narrowed.is_nullable());
        assert_eq!(narrowed.types.len(), 1);
    }

    #[test]
    fn narrow_to_truthy_removes_null_false() {
        let mut u = Type::empty();
        u.add_type(Atomic::TString);
        u.add_type(Atomic::TNull);
        u.add_type(Atomic::TFalse);
        let truthy = u.narrow_to_truthy();
        assert!(!truthy.is_nullable());
        assert!(!truthy.contains(|t| matches!(t, Atomic::TFalse)));
    }

    #[test]
    fn merge_combines_types() {
        let a = Type::single(Atomic::TString);
        let b = Type::single(Atomic::TInt);
        let merged = Type::merge(&a, &b);
        assert_eq!(merged.types.len(), 2);
    }

    #[test]
    fn intersect_keeps_narrower_side_not_self() {
        // int ∩ (1|2) must keep the narrower `1|2`, not the wider `int` —
        // this is exactly what a `match ($x) { 1, 2 => ... }` arm relies on
        // to narrow $x inside its body.
        let int_ty = Type::single(Atomic::TInt);
        let mut literals = Type::empty();
        literals.add_type(Atomic::TLiteralInt(1));
        literals.add_type(Atomic::TLiteralInt(2));

        let narrowed = int_ty.intersect_with(&literals);
        assert_eq!(narrowed.types.len(), 2);
        assert!(narrowed.contains(|t| matches!(t, Atomic::TLiteralInt(1))));
        assert!(narrowed.contains(|t| matches!(t, Atomic::TLiteralInt(2))));
        assert!(!narrowed.contains(|t| matches!(t, Atomic::TInt)));
    }

    #[test]
    fn subtype_literal_int_under_int() {
        let sub = Type::single(Atomic::TLiteralInt(5));
        let sup = Type::single(Atomic::TInt);
        assert!(sub.is_subtype_structural(&sup));
    }

    #[test]
    fn subtype_never_is_bottom() {
        let never = Type::never();
        let string = Type::single(Atomic::TString);
        assert!(never.is_subtype_structural(&string));
    }

    #[test]
    fn subtype_everything_under_mixed() {
        let string = Type::single(Atomic::TString);
        let mixed = Type::mixed();
        assert!(string.is_subtype_structural(&mixed));
    }

    #[test]
    fn subtype_enum_case_under_own_enum() {
        let sub = Type::single(Atomic::TLiteralEnumCase {
            enum_fqcn: Name::new("RoundingMode"),
            case_name: Name::new("Unnecessary"),
        });
        let sup = Type::single(Atomic::TNamedObject {
            fqcn: Name::new("RoundingMode"),
            type_params: empty_type_params(),
        });
        assert!(sub.is_subtype_structural(&sup));
    }

    #[test]
    fn enum_case_not_subtype_of_unrelated_enum() {
        let sub = Type::single(Atomic::TLiteralEnumCase {
            enum_fqcn: Name::new("RoundingMode"),
            case_name: Name::new("Unnecessary"),
        });
        let sup = Type::single(Atomic::TNamedObject {
            fqcn: Name::new("Suit"),
            type_params: empty_type_params(),
        });
        assert!(!sub.is_subtype_structural(&sup));
    }

    #[test]
    fn template_substitution() {
        let mut bindings = FxHashMap::default();
        bindings.insert(Name::new("T"), Type::single(Atomic::TString));

        let tmpl = Type::single(Atomic::TTemplateParam {
            name: Name::new("T"),
            as_type: Box::new(Type::mixed()),
            defining_entity: Name::new("MyClass"),
        });

        let resolved = tmpl.substitute_templates(&bindings);
        assert_eq!(resolved.types.len(), 1);
        assert!(matches!(resolved.types[0], Atomic::TString));
    }

    #[test]
    fn intersection_is_object() {
        let parts = vec![
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Iterator"),
                type_params: empty_type_params(),
            }),
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Countable"),
                type_params: empty_type_params(),
            }),
        ];
        let atomic = Atomic::TIntersection {
            parts: vec_to_type_params(parts),
        };
        assert!(atomic.is_object());
        assert!(!atomic.can_be_falsy());
        assert!(atomic.can_be_truthy());
    }

    #[test]
    fn intersection_display_two_parts() {
        let parts = vec![
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Iterator"),
                type_params: empty_type_params(),
            }),
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Countable"),
                type_params: empty_type_params(),
            }),
        ];
        let u = Type::single(Atomic::TIntersection {
            parts: vec_to_type_params(parts),
        });
        assert_eq!(format!("{u}"), "Iterator&Countable");
    }

    #[test]
    fn intersection_display_three_parts() {
        let parts = vec![
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("A"),
                type_params: empty_type_params(),
            }),
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("B"),
                type_params: empty_type_params(),
            }),
            Type::single(Atomic::TNamedObject {
                fqcn: Name::new("C"),
                type_params: empty_type_params(),
            }),
        ];
        let u = Type::single(Atomic::TIntersection {
            parts: vec_to_type_params(parts),
        });
        assert_eq!(format!("{u}"), "A&B&C");
    }

    #[test]
    fn intersection_in_nullable_union_display() {
        let intersection = Atomic::TIntersection {
            parts: vec_to_type_params(vec![
                Type::single(Atomic::TNamedObject {
                    fqcn: Name::new("Iterator"),
                    type_params: empty_type_params(),
                }),
                Type::single(Atomic::TNamedObject {
                    fqcn: Name::new("Countable"),
                    type_params: empty_type_params(),
                }),
            ]),
        };
        let mut u = Type::single(intersection);
        u.add_type(Atomic::TNull);
        assert!(u.is_nullable());
        assert!(u.contains(|t| matches!(t, Atomic::TIntersection { .. })));
    }

    // --- substitute_templates coverage for previously-missing arms ----------

    fn t_param(name: &str) -> Type {
        Type::single(Atomic::TTemplateParam {
            name: Name::new(name),
            as_type: Box::new(Type::mixed()),
            defining_entity: Name::new("Fn"),
        })
    }

    fn bindings_t_string() -> FxHashMap<Name, Type> {
        let mut b = FxHashMap::default();
        b.insert(Name::new("T"), Type::single(Atomic::TString));
        b
    }

    #[test]
    fn substitute_non_empty_array_key_and_value() {
        let ty = Type::single(Atomic::TNonEmptyArray {
            key: Box::new(t_param("T")),
            value: Box::new(t_param("T")),
        });
        let result = ty.substitute_templates(&bindings_t_string());
        assert_eq!(result.types.len(), 1);
        let Atomic::TNonEmptyArray { key, value } = &result.types[0] else {
            panic!("expected TNonEmptyArray");
        };
        assert!(matches!(key.types[0], Atomic::TString));
        assert!(matches!(value.types[0], Atomic::TString));
    }

    #[test]
    fn substitute_non_empty_list_value() {
        let ty = Type::single(Atomic::TNonEmptyList {
            value: Box::new(t_param("T")),
        });
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TNonEmptyList { value } = &result.types[0] else {
            panic!("expected TNonEmptyList");
        };
        assert!(matches!(value.types[0], Atomic::TString));
    }

    #[test]
    fn substitute_keyed_array_property_types() {
        use crate::atomic::{ArrayKey, KeyedProperty};
        use indexmap::IndexMap;
        let mut props = IndexMap::new();
        props.insert(
            ArrayKey::String(Arc::from("name")),
            KeyedProperty {
                ty: t_param("T"),
                optional: false,
            },
        );
        props.insert(
            ArrayKey::String(Arc::from("tag")),
            KeyedProperty {
                ty: t_param("T"),
                optional: true,
            },
        );
        let ty = Type::single(Atomic::TKeyedArray {
            properties: Box::new(props),
            is_open: true,
            is_list: false,
        });
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TKeyedArray {
            properties,
            is_open,
            is_list,
        } = &result.types[0]
        else {
            panic!("expected TKeyedArray");
        };
        assert!(is_open);
        assert!(!is_list);
        assert!(matches!(
            properties[&ArrayKey::String(Arc::from("name"))].ty.types[0],
            Atomic::TString
        ));
        assert!(properties[&ArrayKey::String(Arc::from("tag"))].optional);
        assert!(matches!(
            properties[&ArrayKey::String(Arc::from("tag"))].ty.types[0],
            Atomic::TString
        ));
    }

    #[test]
    fn substitute_callable_params_and_return() {
        use crate::atomic::FnParam;
        let ty = Type::single(Atomic::TCallable {
            params: Some(Box::new([FnParam {
                name: Name::new("x"),
                ty: Some(crate::compact::SimpleType::from_union(t_param("T"))),
                out_ty: None,
                default: None,
                is_variadic: false,
                is_byref: false,
                is_optional: false,
            }])),
            return_type: Some(Box::new(t_param("T"))),
        });
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TCallable {
            params,
            return_type,
        } = &result.types[0]
        else {
            panic!("expected TCallable");
        };
        let param_ty = params.as_ref().unwrap()[0].ty.as_ref().unwrap();
        let param_union = param_ty.to_union();
        assert!(matches!(param_union.types[0], Atomic::TString));
        let ret = return_type.as_ref().unwrap();
        assert!(matches!(ret.types[0], Atomic::TString));
    }

    #[test]
    fn substitute_callable_bare_no_panic() {
        // callable with no params/return — must not panic and must pass through unchanged
        let ty = Type::single(Atomic::TCallable {
            params: None,
            return_type: None,
        });
        let result = ty.substitute_templates(&bindings_t_string());
        assert!(matches!(
            result.types[0],
            Atomic::TCallable {
                params: None,
                return_type: None
            }
        ));
    }

    #[test]
    fn substitute_closure_params_return_and_this() {
        use crate::atomic::FnParam;
        let ty = Type::single(Atomic::TClosure {
            data: Box::new(crate::atomic::ClosureData {
                params: Box::new([FnParam {
                    name: Name::new("a"),
                    ty: Some(crate::compact::SimpleType::from_union(t_param("T"))),
                    out_ty: None,
                    default: Some(crate::compact::SimpleType::from_union(t_param("T"))),
                    is_variadic: true,
                    is_byref: true,
                    is_optional: true,
                }]),
                return_type: t_param("T"),
                this_type: Some(t_param("T")),
            }),
        });
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TClosure { data } = &result.types[0] else {
            panic!("expected TClosure");
        };
        let (params, return_type, this_type) = (&data.params, &data.return_type, &data.this_type);
        let p = &params[0];
        let ty_union = p.ty.as_ref().unwrap().to_union();
        let default_union = p.default.as_ref().unwrap().to_union();
        assert!(matches!(ty_union.types[0], Atomic::TString));
        assert!(matches!(default_union.types[0], Atomic::TString));
        // flags preserved
        assert!(p.is_variadic);
        assert!(p.is_byref);
        assert!(p.is_optional);
        assert!(matches!(return_type.types[0], Atomic::TString));
        assert!(matches!(
            this_type.as_ref().unwrap().types[0],
            Atomic::TString
        ));
    }

    #[test]
    fn substitute_conditional_all_branches() {
        let ty = Type::single(conditional(
            None,
            t_param("T"),
            t_param("T"),
            Type::single(Atomic::TInt),
        ));
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TConditional { data } = &result.types[0] else {
            panic!("expected TConditional");
        };
        let (subject, if_true, if_false) = (&data.subject, &data.if_true, &data.if_false);
        assert!(matches!(subject.types[0], Atomic::TString));
        assert!(matches!(if_true.types[0], Atomic::TString));
        assert!(matches!(if_false.types[0], Atomic::TInt));
    }

    #[test]
    fn resolve_conditional_is_null_non_null_arg() {
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TNull),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TString)) // definitely not null
            } else {
                None
            }
        });
        assert!(result.types.len() == 1);
        assert!(matches!(result.types[0], Atomic::TString));
    }

    #[test]
    fn resolve_conditional_is_null_null_arg() {
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TNull),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TNull)) // definitely null
            } else {
                None
            }
        });
        assert!(result.types.len() == 1);
        assert!(matches!(result.types[0], Atomic::TInt));
    }

    #[test]
    fn resolve_conditional_is_null_nullable_arg_widens_to_branch_union() {
        let mut nullable_str = Type::single(Atomic::TString);
        nullable_str.add_type(Atomic::TNull);
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TNull),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(nullable_str.clone())
            } else {
                None
            }
        });
        // uncertain discriminator → widen to if_true | if_false
        assert_eq!(result.types.len(), 2);
        assert!(result.types.iter().any(|t| matches!(t, Atomic::TInt)));
        assert!(result.types.iter().any(|t| matches!(t, Atomic::TString)));
    }

    #[test]
    fn resolve_conditional_nested_widens_inner_branch() {
        // ($x is null ? int : ($x is string ? string : float))
        // When $x is unknown, should widen to int|string|float (no TConditional remaining).
        let inner = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TString),
            Type::single(Atomic::TString),
            Type::single(Atomic::TFloat),
        ));
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TNull),
            Type::single(Atomic::TInt),
            inner,
        ));
        // unknown arg → widen both outer branches, inner conditional must also be widened
        let result = ty.resolve_conditional_returns(|_| None);
        assert!(
            result
                .types
                .iter()
                .all(|t| !matches!(t, Atomic::TConditional { .. })),
            "no TConditional should survive: {:?}",
            result.types
        );
        assert!(result.types.iter().any(|t| matches!(t, Atomic::TInt)));
        assert!(result.types.iter().any(|t| matches!(t, Atomic::TString)));
        assert!(result.types.iter().any(|t| matches!(t, Atomic::TFloat)));
    }

    #[test]
    fn resolve_conditional_nested_resolves_inner_branch() {
        // ($x is null ? int : ($x is string ? string : float))
        // When $x is definitely not null but unknown string-or-not → resolves outer to inner,
        // then inner must also be resolved.
        let inner = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TString),
            Type::single(Atomic::TString),
            Type::single(Atomic::TFloat),
        ));
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TNull),
            Type::single(Atomic::TInt),
            inner,
        ));
        // $x = string → outer: not null → if_false (inner); inner: is string → if_true = string
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TString))
            } else {
                None
            }
        });
        assert!(
            result
                .types
                .iter()
                .all(|t| !matches!(t, Atomic::TConditional { .. })),
            "no TConditional should survive: {:?}",
            result.types
        );
        assert_eq!(result.types.len(), 1);
        assert!(matches!(result.types[0], Atomic::TString));
    }

    #[test]
    fn substitute_intersection_parts() {
        let ty = Type::single(Atomic::TIntersection {
            parts: vec_to_type_params(vec![
                Type::single(Atomic::TNamedObject {
                    fqcn: Name::new("Countable"),
                    type_params: empty_type_params(),
                }),
                t_param("T"),
            ]),
        });
        let result = ty.substitute_templates(&bindings_t_string());
        let Atomic::TIntersection { parts } = &result.types[0] else {
            panic!("expected TIntersection");
        };
        assert_eq!(parts.len(), 2);
        assert!(matches!(parts[0].types[0], Atomic::TNamedObject { .. }));
        assert!(matches!(parts[1].types[0], Atomic::TString));
    }

    #[test]
    fn substitute_no_template_params_identity() {
        let ty = Type::single(Atomic::TInt);
        let result = ty.substitute_templates(&bindings_t_string());
        assert!(matches!(result.types[0], Atomic::TInt));
    }
}