mir_types/

union.rs

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

use crate::atomic::{ArrayKey, Atomic, KeyedProperty};
use crate::symbol::Name;
use indexmap::IndexMap;

/// 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,
    /// This type was read from a generic array/list offset (`$arr[$key]`)
    /// whose key presence isn't statically provable — PHP returns `null`
    /// (with a warning) for a missing offset, so a defensive `=== null`/
    /// `!== null` check against it is legitimate even though the inferred
    /// value type itself doesn't literally include `null` (adding `null`
    /// unconditionally to every generic-array read would drown real code in
    /// `PossiblyNull*` noise for the overwhelmingly common case where the key
    /// really is present). The impossibility/redundancy checks
    /// (`ImpossibleIdenticalComparison`, the `=== null` narrowing divergence)
    /// exempt it, mirroring `falsy_stripped`.
    pub possibly_absent_offset: bool,
}

type IntBounds = (Option<i64>, Option<i64>);

/// Inclusive `(min, max)` bounds of an int atomic; `None` bound is unbounded.
fn int_bounds(a: &Atomic) -> Option<IntBounds> {
    match a {
        Atomic::TInt => Some((None, None)),
        Atomic::TLiteralInt(n) => Some((Some(*n), Some(*n))),
        Atomic::TPositiveInt => Some((Some(1), None)),
        Atomic::TNonNegativeInt => Some((Some(0), None)),
        Atomic::TNegativeInt => Some((None, Some(-1))),
        Atomic::TIntRange { min, max } => Some((*min, *max)),
        _ => None,
    }
}

fn bounds_contain(outer: IntBounds, inner: IntBounds) -> bool {
    let lo_ok = match (outer.0, inner.0) {
        (None, _) => true,
        (Some(o), Some(i)) => o <= i,
        (Some(_), None) => false,
    };
    let hi_ok = match (outer.1, inner.1) {
        (None, _) => true,
        (Some(o), Some(i)) => o >= i,
        (Some(_), None) => false,
    };
    lo_ok && hi_ok
}

/// Shapes a union keeps apart before [`Type::add_type`] starts folding them.
/// Each `if` that optionally sets a key doubles the shapes in a union, and
/// flow merges compare every pair, so a long run of such branches went
/// exponential (Symfony's `MandrillApiTransport::getPayload` took 17s).
/// Below the limit shapes stay apart: `count($a) === N` narrowing picks among
/// them, and a key set on only some paths reads without `null`.
const MAX_KEYED_SHAPES: usize = 8;

/// One shape covering `a | b`: keys of both, with those set on one side only
/// made optional and value types unioned. `None` when the shapes disagree on
/// openness, list-ness or emptiness — folding `array{} | array{0: X}` to
/// `array{0?: X}` would stop `if ($arr)` narrowing.
fn combine_keyed_arrays(a: &Atomic, b: &Atomic) -> Option<Atomic> {
    let (
        Atomic::TKeyedArray {
            properties: pa,
            is_open: oa,
            is_list: la,
        },
        Atomic::TKeyedArray {
            properties: pb,
            is_open: ob,
            is_list: lb,
        },
    ) = (a, b)
    else {
        return None;
    };
    let non_empty = |p: &IndexMap<ArrayKey, KeyedProperty>| p.values().any(|v| !v.optional);
    if oa != ob || la != lb || non_empty(pa) != non_empty(pb) {
        return None;
    }
    let mut properties = IndexMap::with_capacity(pa.len().max(pb.len()));
    for (key, x) in pa.iter() {
        let prop = match pb.get(key) {
            Some(y) => {
                let mut ty = x.ty.clone();
                ty.merge_with(&y.ty);
                KeyedProperty {
                    ty,
                    optional: x.optional || y.optional,
                }
            }
            // An open shape already admits the missing key with any value,
            // so keeping the other side's type for it would be unsound.
            None if *oa => continue,
            None => KeyedProperty {
                ty: x.ty.clone(),
                optional: true,
            },
        };
        properties.insert(key.clone(), prop);
    }
    if !*oa {
        for (key, y) in pb.iter() {
            if !pa.contains_key(key) {
                properties.insert(
                    key.clone(),
                    KeyedProperty {
                        ty: y.ty.clone(),
                        optional: true,
                    },
                );
            }
        }
    }
    Some(Atomic::TKeyedArray {
        properties: Box::new(properties),
        is_open: *oa,
        is_list: *la,
    })
}

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

    pub fn empty() -> Self {
        Self {
            types: SmallVec::new(),
            possibly_undefined: false,
            from_docblock: false,
            falsy_stripped: false,
            possibly_absent_offset: 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,
            possibly_absent_offset: 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,
            possibly_absent_offset: 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 [`Self::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
        };

        // Past the limit, fold a new shape into a compatible existing one
        // rather than growing the union (see `MAX_KEYED_SHAPES`).
        let mut atomic = atomic;
        if matches!(atomic, Atomic::TKeyedArray { .. })
            && !self.types.contains(&atomic)
            && self
                .types
                .iter()
                .filter(|t| matches!(t, Atomic::TKeyedArray { .. }))
                .count()
                >= MAX_KEYED_SHAPES
        {
            if let Some((idx, combined)) = self
                .types
                .iter()
                .enumerate()
                .find_map(|(i, t)| combine_keyed_arrays(t, &atomic).map(|c| (i, c)))
            {
                self.types.remove(idx);
                atomic = combined;
            }
        }

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

        // Int atomics absorb each other by bound containment (`5 | int<0, max>`
        // → `int<0, max>`, `non-negative-int | int` → `int`).
        if let Some(new_bounds) = int_bounds(&atomic) {
            if self
                .types
                .iter()
                .any(|t| int_bounds(t).is_some_and(|b| bounds_contain(b, new_bounds)))
            {
                return;
            }
            self.types
                .retain(|t| !int_bounds(t).is_some_and(|b| bounds_contain(new_bounds, b)));
        }
        // TLiteralString(s) is subsumed by TString.
        if let Atomic::TLiteralString(_) = &atomic {
            if self.types.iter().any(|t| matches!(t, Atomic::TString)) {
                return;
            }
        }
        // TNonEmptyString is subsumed by TString.
        if matches!(atomic, Atomic::TNonEmptyString)
            && 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 TString widens away all TLiteralString and TNonEmptyString variants.
        if matches!(atomic, Atomic::TString) {
            self.types
                .retain(|t| !matches!(t, Atomic::TLiteralString(_) | Atomic::TNonEmptyString));
        }
        // 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,
        )
        .with_callable_form(self, Atomic::TCallableString)
    }

    /// 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()),
            },
        )
        .with_callable_form(self, callable_array())
    }

    /// Keeps the outer collection kind but turns every nested `non-empty-list`/`non-empty-array`
    /// into `list`/`array`, for comparisons that ignore element emptiness.
    pub fn widen_nested_non_empty(&self) -> Type {
        fn relax_all(ty: &Type) -> Type {
            map_atoms(ty, |a| match a {
                Atomic::TNonEmptyList { value } => Atomic::TList {
                    value: Box::new(relax_all(value)),
                },
                Atomic::TNonEmptyArray { key, value } => Atomic::TArray {
                    key: key.clone(),
                    value: Box::new(relax_all(value)),
                },
                other => map_values(other, relax_all),
            })
        }
        fn map_values(atomic: &Atomic, f: fn(&Type) -> Type) -> Atomic {
            match atomic {
                Atomic::TArray { key, value } => Atomic::TArray {
                    key: key.clone(),
                    value: Box::new(f(value)),
                },
                Atomic::TList { value } => Atomic::TList {
                    value: Box::new(f(value)),
                },
                Atomic::TNonEmptyArray { key, value } => Atomic::TNonEmptyArray {
                    key: key.clone(),
                    value: Box::new(f(value)),
                },
                Atomic::TNonEmptyList { value } => Atomic::TNonEmptyList {
                    value: Box::new(f(value)),
                },
                Atomic::TKeyedArray {
                    properties,
                    is_open,
                    is_list,
                } => Atomic::TKeyedArray {
                    properties: Box::new(
                        properties
                            .iter()
                            .map(|(k, p)| {
                                (
                                    k.clone(),
                                    crate::atomic::KeyedProperty {
                                        ty: f(&p.ty),
                                        optional: p.optional,
                                    },
                                )
                            })
                            .collect(),
                    ),
                    is_open: *is_open,
                    is_list: *is_list,
                },
                other => other.clone(),
            }
        }
        fn map_atoms(ty: &Type, f: impl Fn(&Atomic) -> Atomic) -> Type {
            let mut result = Type::empty();
            result.possibly_undefined = ty.possibly_undefined;
            result.from_docblock = ty.from_docblock;
            for atomic in &ty.types {
                result.add_type(f(atomic));
            }
            result
        }
        map_atoms(self, |a| map_values(a, relax_all))
    }

    /// Narrow array/list types to their non-empty variants (for `count() > 0` etc.),
    /// dropping the closed empty shape `array{}`.
    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(),
                }),
                Atomic::TKeyedArray {
                    properties,
                    is_open: false,
                    ..
                } if properties.is_empty() => {}
                _ => 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())
                .with_callable_form(self, Atomic::TObject)
        } else {
            out.with_callable_form(self, Atomic::TObject)
        }
    }

    /// Adds `form` when `source` has a plain `callable`, which may be a function-name string,
    /// a `[class, method]` array or an invokable object.
    fn with_callable_form(mut self, source: &Type, form: Atomic) -> Type {
        if source
            .types
            .iter()
            .any(|t| matches!(t, Atomic::TCallable { .. }))
        {
            self.add_type(form);
        }
        self
    }

    /// Narrow as if `is_callable($x)` is false: the `[class, method]` array a
    /// `callable` was narrowed to by `is_array()` is callable too.
    pub fn narrow_to_not_callable(&self) -> Type {
        let callable_array = callable_array();
        self.filter(|t| !t.is_callable() && *t != callable_array)
    }

    /// 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,
                    is_pure: false,
                });
            } 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,
                possibly_absent_offset: 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,
                    is_pure,
                } => {
                    result.add_type(Atomic::TCallable {
                        params: params.as_ref().map(|ps| {
                            Box::new(
                                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))),
                        is_pure: *is_pure,
                    });
                }
                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)),
                            is_pure: data.is_pure,
                            is_static: data.is_static,
                            rejects_surplus_args: data.rejects_surplus_args,
                        }),
                    });
                }
                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::TKeyOf { target } => {
                    let new_target = target.substitute_templates(bindings);
                    if let Some(resolved) = eval_key_of_type(&new_target) {
                        result.merge_with(&resolved);
                    } else {
                        result.add_type(Atomic::TKeyOf {
                            target: Box::new(new_target),
                        });
                    }
                }
                Atomic::TValueOf { target } => {
                    let new_target = target.substitute_templates(bindings);
                    if let Some(resolved) = eval_value_of_type(&new_target) {
                        result.merge_with(&resolved);
                    } else {
                        result.add_type(Atomic::TValueOf {
                            target: Box::new(new_target),
                        });
                    }
                }
                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 } => {
                    // 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| {
            let fits = |a: &Atomic| other.types.iter().any(|b| atomic_subtype(a, b));
            fits(a) || composite_parts(a).is_some_and(|parts| parts.iter().all(fits))
        })
    }

    /// Like `is_subtype_structural`, but a template atom is judged by its bound
    /// (an unbound one is `mixed` and fits anything).
    pub fn is_subtype_by_template_bounds(&self, other: &Type) -> bool {
        self.is_subtype_structural(other)
            || self.types.iter().all(|a| match a {
                Atomic::TTemplateParam { as_type, .. } => {
                    as_type.is_subtype_by_template_bounds(other)
                }
                _ => other.accepts_atomic_structural(a),
            })
    }

    /// `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
    }

    /// Mark this union as read from a generic array/list offset whose key
    /// presence isn't statically provable (see the field doc on
    /// [`Type::possibly_absent_offset`]).
    pub fn possibly_absent_offset(mut self) -> Self {
        self.possibly_absent_offset = true;
        self
    }
}

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

/// Coarse value class of a runtime value.
///
/// One atom may hold several classes (a `bool` may hold `true` *or*
/// `false`; a `scalar` argument is one of the five scalar classes).
/// Literal refinements stay precise only where they matter: `int`/`float`
/// literals get their own class so that `int` and `float` literals decide
/// against each other's subjects; string literals collapse to
/// [`ValueClass::String`] (refined string kinds never feed a conditional
/// subject and would only cost match precision).
#[derive(Clone, PartialEq, Eq, Debug)]
enum ValueClass {
    Int,
    Float,
    True,
    False,
    String,
    Array,
    /// `list`-shaped arrays (sequential integer keys) — a refinement of [`Array`].
    List,
    Object,
    Null,
    /// `mixed`/`void` — a value of every class; it overlaps every other
    /// class, so a `mixed` argument rules out no branch.
    Top,
    /// Literal `int` — precise against `int`/`float` subjects: an `int`
    /// literal is not a float, a float literal is not an int.
    LitInt(i64),
    /// Literal `float` — the bit decomposition mirrors [`Atomic::TLiteralFloat`].
    LitFloat(i64, i64),
    /// A specific `string` literal.
    LitString(Arc<str>),
}

impl ValueClass {
    /// Whether a value of class `b` is necessarily a value of class `a`, i.e.
    /// whether the class lattice (`int` literal <: `int` <: `scalar`;
    /// `list` <: `array`; `true`/`false` <: `bool`; `mixed` <: everything)
    /// places `b` beneath `a`.
    fn includes(&self, b: &Self) -> bool {
        self == b
            || matches!(
                (self, b),
                (Self::Top, _)
                    | (Self::Int, Self::LitInt(_))
                    | (Self::Float, Self::LitFloat(..))
                    | (Self::String, Self::LitString(_))
                    | (Self::Array, Self::List)
            )
    }
}

/// The value classes an atom may hold.
///
/// Meta-types map to every class they may hold (`TBool` holds `true` *and*
/// `false`); opaque/deferred atoms (`TTemplateParam`, `TKeyOf`, …) map to
/// none — an argument of such a type rules out no branch.
fn value_classes(a: &Atomic) -> Vec<ValueClass> {
    use ValueClass::*;
    match a {
        // Integers (range bounds are not modeled: a subject `int` is a
        // family question).
        Atomic::TInt
        | Atomic::TIntRange { .. }
        | Atomic::TPositiveInt
        | Atomic::TNegativeInt
        | Atomic::TNonNegativeInt => vec![Int],
        Atomic::TLiteralInt(v) => vec![LitInt(*v)],
        // Floats.
        Atomic::TFloat | Atomic::TIntegralFloat => vec![Float],
        Atomic::TLiteralFloat(int_bits, frac_bits) => {
            vec![LitFloat(*int_bits, *frac_bits)]
        }
        // Bools.
        Atomic::TBool => vec![True, False],
        Atomic::TTrue => vec![True],
        Atomic::TFalse => vec![False],
        // Strings — every refined string kind maps to one class.
        Atomic::TString
        | Atomic::TNonEmptyString
        | Atomic::TNumericString
        | Atomic::TClassString(_)
        | Atomic::TInterfaceString(_)
        | Atomic::TEnumString
        | Atomic::TTraitString
        | Atomic::TCallableString => vec![String],
        Atomic::TLiteralString(s) => vec![LitString(s.clone())],
        // Arrays — `list` is a refinement of `array`.
        Atomic::TArray { .. }
        | Atomic::TNonEmptyArray { .. }
        | Atomic::TKeyedArray { is_list: false, .. } => vec![Array],
        Atomic::TList { .. }
        | Atomic::TNonEmptyList { .. }
        | Atomic::TKeyedArray { is_list: true, .. } => vec![List],
        // Objects — a specific class instance is an object at runtime.
        Atomic::TObject
        | Atomic::TNamedObject { .. }
        | Atomic::TStaticObject { .. }
        | Atomic::TSelf { .. }
        | Atomic::TParent { .. }
        | Atomic::TClosure { .. }
        | Atomic::TLiteralEnumCase { .. } => vec![Object],
        // Null. `void` maps to `Top` (a `void`-typed value is unknown; treating
        // it as "everything" keeps any branch it feeds undecidable).
        Atomic::TNull => vec![Null],
        Atomic::TVoid => vec![Top],
        // Everything / scalars.
        Atomic::TMixed => vec![Top],
        Atomic::TScalar => vec![Int, Float, True, False, String],
        // `numeric` may hold `int` or `float` values (a numeric *string*
        // can never be the discriminant of an `is numeric` subject).
        Atomic::TNumeric => vec![Int, Float],
        // Opaque / deferred — rules out no branch.
        Atomic::TCallable { .. }
        | Atomic::TNever
        | Atomic::TTemplateParam { .. }
        | Atomic::TKeyOf { .. }
        | Atomic::TValueOf { .. }
        | Atomic::TConditional { .. }
        | Atomic::TIntersection { .. } => Vec::new(),
    }
}

/// Whether a conditional discriminant subject can be decided by value class.
///
/// Only the bare family kinds and scalar literals qualify. A refined subject (a named object, a
/// shape, a non-empty list, an enum case, …) carries value-level constraints
/// the class lattice cannot express — an argument that is *some* object is
/// not necessarily *that* class — so refined subjects stay undecidable, the
/// same behavior as the pre-class predicate (which had no arm for them).
fn subject_is_decidable(subject: &Atomic) -> bool {
    matches!(
        subject,
        Atomic::TNull
            | Atomic::TTrue
            | Atomic::TFalse
            | Atomic::TBool
            | Atomic::TString
            | Atomic::TInt
            | Atomic::TFloat
            | Atomic::TLiteralString(_)
            | Atomic::TLiteralInt(_)
            | Atomic::TLiteralFloat(..)
            | Atomic::TArray { .. }
            | Atomic::TList { .. }
            | Atomic::TObject
            | Atomic::TMixed
            | Atomic::TScalar
    )
}

/// Resolve one branch of a conditional return type given the subject
/// discriminant 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.
///
/// Decision rule (value-class semantics): the discriminant and the argument
/// are compared *only on value classes* — the value sets the runtime type
/// system uses for narrowing. Class containment is the same lattice the
/// subtype relation uses for these kinds (`true` ⊆ `bool` ⊆ `scalar`,
/// `list` ⊆ `array`, `int`/`float` literals distinct, `mixed` ⊆ everything),
/// so a subject kind and an argument kind are related iff some contained
/// class relates them.
///
/// The true branch commits when every argument class is contained in some
/// subject class (every value the argument can hold is a subject value); the
/// false branch commits when every argument class is disjoint from every
/// subject class (no value the argument can hold is a subject value).
/// Otherwise the branch is undecidable and the caller widens to the union of
/// both branches.
fn resolve_conditional_branch(
    subject: &Atomic,
    arg_ty: &Type,
    if_true: &Type,
    if_false: &Type,
) -> Option<Type> {
    if !subject_is_decidable(subject) {
        return None;
    }
    if arg_ty.types.is_empty() {
        return None;
    }
    let subject_classes = value_classes(subject);
    let arg_classes: Vec<ValueClass> = arg_ty.types.iter().flat_map(value_classes).collect();
    if arg_classes.is_empty() {
        // Opaque argument (template, `key-of`, …) — no branch is ruled out.
        return None;
    }
    let all_match = arg_classes
        .iter()
        .all(|c| subject_classes.iter().any(|s| s.includes(c)));
    let any_overlap = arg_classes.iter().any(|c| {
        subject_classes
            .iter()
            .any(|s| s.includes(c) || c.includes(s))
    });
    if all_match {
        Some(if_true.clone())
    } else if !any_overlap {
        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::TKeyOf { .. }
        | Atomic::TValueOf { .. }
        | 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,
    }
}

pub fn eval_key_of_type(t: &Type) -> Option<Type> {
    let mut result = Type::empty();
    for atomic in &t.types {
        match atomic {
            Atomic::TArray { key, .. } | Atomic::TNonEmptyArray { key, .. } => {
                for k in &key.types {
                    result.add_type(k.clone());
                }
            }
            Atomic::TList { .. } | Atomic::TNonEmptyList { .. } => {
                result.add_type(Atomic::TInt);
            }
            Atomic::TKeyedArray { properties, .. } => {
                for key in properties.keys() {
                    match key {
                        crate::atomic::ArrayKey::Int(n) => result.add_type(Atomic::TLiteralInt(*n)),
                        crate::atomic::ArrayKey::String(s) => {
                            result.add_type(Atomic::TLiteralString(s.clone()))
                        }
                    }
                }
            }
            _ => return None,
        }
    }
    (!result.types.is_empty()).then_some(result)
}

pub fn eval_value_of_type(t: &Type) -> Option<Type> {
    let mut result = Type::empty();
    for atomic in &t.types {
        match atomic {
            Atomic::TArray { value, .. }
            | Atomic::TNonEmptyArray { value, .. }
            | Atomic::TList { value }
            | Atomic::TNonEmptyList { value } => {
                result.merge_with(value);
            }
            Atomic::TKeyedArray { properties, .. } => {
                for prop in properties.values() {
                    result.merge_with(&prop.ty);
                }
            }
            _ => return None,
        }
    }
    (!result.types.is_empty()).then_some(result)
}

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)
// ---------------------------------------------------------------------------

/// Atomics that are exactly a union of other atomics, so a union spelling out
/// every part (e.g. `string|int|float|bool`) accepts them.
fn composite_parts(atomic: &Atomic) -> Option<&'static [Atomic]> {
    match atomic {
        Atomic::TScalar => Some(&[Atomic::TInt, Atomic::TFloat, Atomic::TString, Atomic::TBool]),
        Atomic::TNumeric => Some(&[Atomic::TInt, Atomic::TFloat, Atomic::TNumericString]),
        _ => None,
    }
}

/// 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,
        // A class/interface/callable/enum/trait name can never be the empty
        // string in real PHP — every one of these string-subtype atoms is
        // always non-empty, same reasoning as numeric-string above.
        (Atomic::TClassString(_), Atomic::TNonEmptyString) => true,
        (Atomic::TInterfaceString(_), Atomic::TNonEmptyString) => true,
        (Atomic::TCallableString, Atomic::TNonEmptyString) => true,
        (Atomic::TEnumString, Atomic::TNonEmptyString) => true,
        (Atomic::TTraitString, Atomic::TNonEmptyString) => 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::TClassString(Some(_)), 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,
        // An enum-case literal is, at runtime, an object.
        (Atomic::TLiteralEnumCase { .. }, 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
        }
        (Atomic::TLiteralEnumCase { enum_fqcn, .. }, Atomic::TSelf { fqcn })
        | (Atomic::TLiteralEnumCase { enum_fqcn, .. }, Atomic::TStaticObject { 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::TCallableString, 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()
                        // A void callback discards its return value, so any
                        // return type satisfies it — PHP places no
                        // constraint on what an implementation returns here.
                        || sup.return_type.is_void()
                        || 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))
        }),
        (Atomic::TIntersection { parts }, Atomic::TObject) => parts
            .iter()
            .any(|part| part.is_subtype_structural(&Type::single(Atomic::TObject))),

        // 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)
        }
        (Atomic::TNonEmptyList { value: v1 }, Atomic::TNonEmptyList { value: v2 }) => {
            v1.is_subtype_structural(v2)
        }
        // 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_by_template_bounds(&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
        }
        // TKeyedArray (array shape) satisfies TIntersection iff it satisfies every
        // intersection part. This handles the Psalm idiom of using intersection types
        // for "shape plus extra keys allowed" patterns like:
        // @psalm-type Context = array<string,mixed> & array{actor:...,target?:...,outcome:...}
        (
            Atomic::TKeyedArray {
                properties,
                is_open,
                ..
            },
            Atomic::TIntersection { parts },
        ) => parts.iter().all(|part| {
            part.types.iter().any(|part_atomic| match part_atomic {
                Atomic::TKeyedArray {
                    properties: sup_props,
                    is_open: sup_open,
                    ..
                } => {
                    let keys_satisfied =
                        sup_props
                            .iter()
                            .all(|(key, sup_prop)| match properties.get(key) {
                                Some(sub_prop) => {
                                    if !sup_prop.optional && sub_prop.optional {
                                        return false;
                                    }
                                    let has_named_obj = sup_prop.ty.types.iter().any(|a| {
                                        matches!(
                                            a,
                                            Atomic::TNamedObject { .. }
                                                | Atomic::TSelf { .. }
                                                | Atomic::TStaticObject { .. }
                                                | Atomic::TClosure { .. }
                                                | Atomic::TTemplateParam { .. }
                                        )
                                    });
                                    has_named_obj
                                        || sub_prop.ty.is_subtype_by_template_bounds(&sup_prop.ty)
                                        || bare_array_may_fit(&sub_prop.ty, &sup_prop.ty)
                                }
                                None => *is_open || sup_prop.optional,
                            });
                    let has_array_part = parts.iter().any(|part| {
                        part.types
                            .iter()
                            .any(|t| matches!(t, Atomic::TArray { .. }))
                    });
                    let has_keyed_array_part = parts.iter().any(|part| {
                        part.types
                            .iter()
                            .any(|t| matches!(t, Atomic::TKeyedArray { .. }))
                    });
                    let keys_allowed_by_some_part = if has_array_part {
                        true
                    } else if has_keyed_array_part {
                        properties.keys().all(|k| {
                            parts.iter().any(|part| {
                                part.types.iter().any(|t| {
                                    if let Atomic::TKeyedArray {
                                        properties: part_props,
                                        ..
                                    } = t
                                    {
                                        part_props.contains_key(k)
                                    } else {
                                        false
                                    }
                                })
                            })
                        })
                    } else {
                        true
                    };
                    let no_undeclared_extras = *sup_open || keys_allowed_by_some_part;
                    keys_satisfied && no_undeclared_extras
                }
                Atomic::TArray { key, value } => properties.iter().all(|(prop_key, prop)| {
                    let key_atomic = match prop_key {
                        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)
                }),
                Atomic::TNamedObject { .. }
                | Atomic::TSelf { .. }
                | Atomic::TStaticObject { .. }
                | Atomic::TClosure { .. }
                | Atomic::TTemplateParam { .. } => true,
                _ => false,
            })
        }),

        _ => false,
    }
}

/// A bare `array` carries no key/value info, so it may hold any array-shaped `sup`.
fn bare_array_may_fit(sub: &Type, sup: &Type) -> bool {
    fn array_like(t: &Atomic) -> bool {
        match t {
            Atomic::TArray { .. }
            | Atomic::TNonEmptyArray { .. }
            | Atomic::TList { .. }
            | Atomic::TNonEmptyList { .. }
            | Atomic::TKeyedArray { .. } => true,
            Atomic::TIntersection { parts } => parts.iter().all(|p| p.types.iter().all(array_like)),
            _ => false,
        }
    }
    matches!(
        sub.types.as_slice(),
        [Atomic::TArray { key, value }]
            if value.is_mixed()
                && (key.is_mixed()
                    || matches!(key.types.as_slice(), [Atomic::TInt, Atomic::TString] | [Atomic::TString, Atomic::TInt]))
    ) && sup.types.iter().all(array_like)
}

/// 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
// ---------------------------------------------------------------------------

/// Accumulates a union with hash-based dedup of literal strings/ints, so large
/// literal sets build in linear time. Equivalent to repeated [`Type::add_type`].
pub struct UnionBuilder {
    ty: Type,
    strings: std::collections::HashSet<std::sync::Arc<str>>,
    ints: std::collections::HashSet<i64>,
    // No atom present can subsume a new literal (`mixed`, `string`, int ranges).
    literals_independent: bool,
}

impl Default for UnionBuilder {
    fn default() -> Self {
        Self::new()
    }
}

impl UnionBuilder {
    pub fn new() -> Self {
        Self {
            ty: Type::empty(),
            strings: Default::default(),
            ints: Default::default(),
            literals_independent: true,
        }
    }

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

    pub fn merge(&mut self, other: &Type) {
        for a in &other.types {
            self.add(a.clone());
        }
        self.ty.possibly_undefined |= other.possibly_undefined;
    }

    pub fn add(&mut self, atomic: Atomic) {
        // A lone `never` is dropped by add_type once anything else arrives.
        let lone_never = matches!(self.ty.types.first(), Some(Atomic::TNever));
        if self.literals_independent && !lone_never {
            match &atomic {
                Atomic::TLiteralString(s) => {
                    if self.strings.insert(s.clone()) {
                        self.ty.types.push(atomic);
                    }
                    return;
                }
                Atomic::TLiteralInt(n) => {
                    if self.ints.insert(*n) {
                        self.ty.types.push(atomic);
                    }
                    return;
                }
                _ => {}
            }
        }
        let disturbs_literals = matches!(
            atomic,
            Atomic::TString | Atomic::TMixed | Atomic::TConditional { .. }
        ) || int_bounds(&atomic).is_some();
        self.ty.add_type(atomic);
        if disturbs_literals || lone_never {
            self.resync();
        }
    }

    fn resync(&mut self) {
        self.strings.clear();
        self.ints.clear();
        self.literals_independent = true;
        for t in &self.ty.types {
            match t {
                Atomic::TLiteralString(s) => {
                    self.strings.insert(s.clone());
                }
                Atomic::TLiteralInt(n) => {
                    self.ints.insert(*n);
                }
                Atomic::TMixed | Atomic::TString => self.literals_independent = false,
                other if int_bounds(other).is_some() => self.literals_independent = false,
                _ => {}
            }
        }
    }

    pub fn build(self) -> Type {
        self.ty
    }
}

/// `list{class-string|object, non-empty-string}`: the `[class, method]` form of a callable.
fn callable_array() -> Atomic {
    let mut properties = IndexMap::with_capacity(2);
    properties.insert(
        ArrayKey::Int(0),
        KeyedProperty {
            ty: Type::from_vec(vec![Atomic::TClassString(None), Atomic::TObject]),
            optional: false,
        },
    );
    properties.insert(
        ArrayKey::Int(1),
        KeyedProperty {
            ty: Type::single(Atomic::TNonEmptyString),
            optional: false,
        },
    );
    Atomic::TKeyedArray {
        properties: Box::new(properties),
        is_open: false,
        is_list: true,
    }
}

#[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 subtype_enum_case_under_own_self_and_static() {
        let case = |enum_fqcn: &str| {
            Type::single(Atomic::TLiteralEnumCase {
                enum_fqcn: Name::new(enum_fqcn),
                case_name: Name::new("A"),
            })
        };
        let own = Type::single(Atomic::TSelf {
            fqcn: Name::new("Suit"),
        });
        let own_static = Type::single(Atomic::TStaticObject {
            fqcn: Name::new("Suit"),
        });
        assert!(case("Suit").is_subtype_structural(&own));
        assert!(case("Suit").is_subtype_structural(&own_static));
        assert!(!case("Other").is_subtype_structural(&own));
    }

    #[test]
    fn subtype_enum_case_under_bare_object() {
        let sub = Type::single(Atomic::TLiteralEnumCase {
            enum_fqcn: Name::new("RoundingMode"),
            case_name: Name::new("Unnecessary"),
        });
        let sup = Type::single(Atomic::TObject);
        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(vec![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"))),
            is_pure: false,
        });
        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,
            is_pure: false,
        });
        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")),
                is_pure: false,
                is_static: false,
                rejects_surplus_args: false,
            }),
        });
        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 resolve_conditional_true_subject_bool_arg_widens() {
        // A `bool` argument carries the value classes `{true, false}`:
        // `false` is not contained in the `true` class, and `true`
        // overlaps it, so neither branch is ruled out.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TTrue),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TBool))
            } else {
                None
            }
        });
        assert_eq!(result.types.len(), 2);
        assert!(result.contains(|t| matches!(t, Atomic::TInt)));
        assert!(result.contains(|t| matches!(t, Atomic::TString)));
    }

    #[test]
    fn resolve_conditional_true_subject_mixed_arg_widens() {
        // `mixed` maps to the `Top` value class, which overlaps every
        // other class, so it can never rule a branch out.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TTrue),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::mixed())
            } else {
                None
            }
        });
        assert_eq!(result.types.len(), 2);
        assert!(result.contains(|t| matches!(t, Atomic::TInt)));
        assert!(result.contains(|t| matches!(t, Atomic::TString)));
    }

    #[test]
    fn resolve_conditional_true_subject_literal_args() {
        // Literals decide by value class: `false` is contained in
        // `{false}` and disjoint from `{true}`, and vice versa.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TTrue),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let false_arg = ty.clone().resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TFalse))
            } else {
                None
            }
        });
        assert_eq!(false_arg.types.len(), 1);
        assert!(matches!(false_arg.types[0], Atomic::TString));

        let true_arg = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TTrue))
            } else {
                None
            }
        });
        assert_eq!(true_arg.types.len(), 1);
        assert!(matches!(true_arg.types[0], Atomic::TInt));
    }

    #[test]
    fn resolve_conditional_bool_subject_scalar_arg_widens() {
        // `scalar` carries all five scalar classes: `true`/`false`
        // overlap the `bool` subject, but `int`/`float`/`string` are
        // not contained in `{true, false}`, so neither branch commits.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TBool),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TScalar))
            } else {
                None
            }
        });
        assert_eq!(result.types.len(), 2);
        assert!(result.contains(|t| matches!(t, Atomic::TInt)));
        assert!(result.contains(|t| matches!(t, Atomic::TString)));
    }

    #[test]
    fn resolve_conditional_string_subject_bool_arg_false_branch() {
        // Disjoint value classes still commit to the false branch: a
        // `bool` argument carries `{true, false}`, none of which is a
        // string, and strings are not bools.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TString),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TBool),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TBool))
            } else {
                None
            }
        });
        assert_eq!(result.types.len(), 1);
        assert!(matches!(result.types[0], Atomic::TBool));
    }

    #[test]
    fn resolve_conditional_list_subject_bare_array_arg_widens() {
        // A bare `array` is the supertype of `list`, so it may or may
        // not be a list: both branches stay live.
        let ty = Type::single(conditional(
            Some(Name::new("x")),
            Type::single(Atomic::TList {
                value: Box::new(Type::mixed()),
            }),
            Type::single(Atomic::TInt),
            Type::single(Atomic::TString),
        ));
        let result = ty.resolve_conditional_returns(|name| {
            if name == "x" {
                Some(Type::single(Atomic::TArray {
                    key: Box::new(Type::mixed()),
                    value: Box::new(Type::mixed()),
                }))
            } else {
                None
            }
        });
        assert_eq!(result.types.len(), 2);
        assert!(result.contains(|t| matches!(t, Atomic::TInt)));
        assert!(result.contains(|t| matches!(t, Atomic::TString)));
    }

    #[test]
    fn resolve_conditional_float_subject_int_literal_false_branch() {
        // A `float` subject is the `Float` class; an int literal is
        // `LitInt`, which is not a float, and floats are not ints.
        let ty = resolve_conditional_branch(
            &Atomic::TFloat,
            &Type::single(Atomic::TLiteralInt(42)),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_int_subject_float_literal_false_branch() {
        let ty = resolve_conditional_branch(
            &Atomic::TInt,
            &Type::single(Atomic::TLiteralFloat(1, 0)),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_float_subject_float_literal_then_branch() {
        let ty = resolve_conditional_branch(
            &Atomic::TFloat,
            &Type::single(Atomic::TLiteralFloat(1, 5)),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_int_subject_int_literal_then_branch() {
        let ty = resolve_conditional_branch(
            &Atomic::TInt,
            &Type::single(Atomic::TLiteralInt(7)),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_int_subject_float_arg_false_branch() {
        // A bare `float` argument is never an `int`: disjoint value
        // classes commit to the false branch.
        let ty = resolve_conditional_branch(
            &Atomic::TInt,
            &Type::single(Atomic::TFloat),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_array_subject_string_arg_false_branch() {
        let ty = resolve_conditional_branch(
            &Atomic::TArray {
                key: Box::new(Type::mixed()),
                value: Box::new(Type::mixed()),
            },
            &Type::single(Atomic::TString),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_array_subject_bool_arg_false_branch() {
        let ty = resolve_conditional_branch(
            &Atomic::TArray {
                key: Box::new(Type::mixed()),
                value: Box::new(Type::mixed()),
            },
            &Type::single(Atomic::TBool),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_array_subject_mixed_arg_widens() {
        // A `mixed` argument is `Top`: it overlaps `array`, so the then
        // branch is never ruled out, and it is not contained in `array`,
        // so the false branch is never ruled out either.
        let ty = resolve_conditional_branch(
            &Atomic::TArray {
                key: Box::new(Type::mixed()),
                value: Box::new(Type::mixed()),
            },
            &Type::mixed(),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_array_subject_list_arg_then_branch() {
        // A `list` argument is an `array` (`List` is contained in
        // `Array`), so every argument class is in the subject's class.
        let ty = resolve_conditional_branch(
            &Atomic::TArray {
                key: Box::new(Type::mixed()),
                value: Box::new(Type::mixed()),
            },
            &Type::single(Atomic::TList {
                value: Box::new(Type::mixed()),
            }),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_list_subject_keyed_list_arg_then_branch() {
        // A keyed array with `is_list` is a list at runtime.
        let ty = resolve_conditional_branch(
            &Atomic::TList {
                value: Box::new(Type::mixed()),
            },
            &Type::single(Atomic::TKeyedArray {
                properties: Box::default(),
                is_open: false,
                is_list: true,
            }),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_list_subject_list_string_union_widens() {
        // A `list|string` argument carries `{List, String}`: `List`
        // overlaps the `list` subject, `String` does not, so neither
        // branch is ruled out.
        let ty = resolve_conditional_branch(
            &Atomic::TList {
                value: Box::new(Type::mixed()),
            },
            &Type::from_vec(vec![
                Atomic::TList {
                    value: Box::new(Type::mixed()),
                },
                Atomic::TString,
            ]),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_numeric_subject_widens() {
        // `numeric` is a refined subject (it admits numeric strings such
        // as `"123"`), so the value-class lattice cannot reduce it: the
        // branch stays undecidable even for a literal string argument.
        let ty = resolve_conditional_branch(
            &Atomic::TNumeric,
            &Type::single(Atomic::TLiteralString("123".into())),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_non_empty_string_subject_widens() {
        // A `non-empty-string` subject is refined (`""` is a string but
        // not non-empty), so even a bare string argument is undecidable.
        let ty = resolve_conditional_branch(
            &Atomic::TNonEmptyString,
            &Type::single(Atomic::TString),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_template_arg_widens() {
        // A template parameter has no value classes at all (opaque), so
        // it is undecidable against any subject.
        let ty = resolve_conditional_branch(
            &Atomic::TString,
            &t_param("T"),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_mixed_subject_bool_arg_then_branch() {
        // `mixed` is a decidable subject: every value class is contained
        // in `Top`, so a bool argument is always `mixed`.
        let ty = resolve_conditional_branch(
            &Atomic::TMixed,
            &Type::single(Atomic::TBool),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_scalar_subject_null_arg_false_branch() {
        // `null` is not a scalar value class: the argument is disjoint
        // from the subject, so the false branch is taken.
        let ty = resolve_conditional_branch(
            &Atomic::TScalar,
            &Type::single(Atomic::TNull),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_object_subject_named_arg_then_branch() {
        // A named class instance is an object at runtime.
        let ty = resolve_conditional_branch(
            &Atomic::TObject,
            &Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Foo"),
                type_params: empty_type_params(),
            }),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[test]
    fn resolve_conditional_named_subject_other_class_widens() {
        // A named-object subject is refined (one specific class), so an
        // instance of another class is undecidable even though both are
        // objects.
        let ty = resolve_conditional_branch(
            &Atomic::TNamedObject {
                fqcn: Name::new("Foo"),
                type_params: empty_type_params(),
            },
            &Type::single(Atomic::TNamedObject {
                fqcn: Name::new("Bar"),
                type_params: empty_type_params(),
            }),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_enum_case_subject_widens() {
        // An enum-case subject is refined: the value-class lattice cannot
        // reduce a specific enum case, so an int argument is undecidable.
        let ty = resolve_conditional_branch(
            &Atomic::TLiteralEnumCase {
                enum_fqcn: Name::new("RoundingMode"),
                case_name: Name::new("Unnecessary"),
            },
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(ty.is_none());
    }

    #[test]
    fn resolve_conditional_null_subject_bool_arg_false_branch() {
        // `null` and bool are disjoint value classes.
        let ty = resolve_conditional_branch(
            &Atomic::TNull,
            &Type::single(Atomic::TBool),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TString)
        ));
    }

    #[test]
    fn resolve_conditional_bool_subject_true_arg_then_branch() {
        // `true` is contained in `bool`'s `{true, false}` classes, so
        // the then branch is taken.
        let ty = resolve_conditional_branch(
            &Atomic::TBool,
            &Type::single(Atomic::TTrue),
            &Type::single(Atomic::TInt),
            &Type::single(Atomic::TString),
        );
        assert!(matches!(
            ty.as_ref(),
            Some(t) if t.types.len() == 1 && matches!(t.types[0], Atomic::TInt)
        ));
    }

    #[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));
    }

    fn shape(props: &[(&str, Atomic, bool)], is_open: bool) -> Atomic {
        Atomic::TKeyedArray {
            properties: Box::new(
                props
                    .iter()
                    .map(|(k, ty, optional)| {
                        (
                            ArrayKey::String(Arc::from(*k)),
                            KeyedProperty {
                                ty: Type::single(ty.clone()),
                                optional: *optional,
                            },
                        )
                    })
                    .collect(),
            ),
            is_open,
            is_list: false,
        }
    }

    /// A closed shape `{a: int}` plus key `k{i}` for each bit set in `bits`.
    fn shape_with_bits(bits: u32, is_open: bool) -> Atomic {
        let names: Vec<String> = (0..5).map(|i| format!("k{i}")).collect();
        let mut props = vec![("a", Atomic::TInt, false)];
        props.extend(
            (0..5)
                .filter(|i| bits & (1 << i) != 0)
                .map(|i| (names[i].as_str(), Atomic::TString, false)),
        );
        shape(&props, is_open)
    }

    fn keyed_count(ty: &Type) -> usize {
        ty.types
            .iter()
            .filter(|t| matches!(t, Atomic::TKeyedArray { .. }))
            .count()
    }

    #[test]
    fn add_type_keeps_few_shapes_apart() {
        let mut ty = Type::empty();
        for bits in 0..MAX_KEYED_SHAPES as u32 {
            ty.add_type(shape_with_bits(bits, false));
        }
        assert_eq!(keyed_count(&ty), MAX_KEYED_SHAPES);
    }

    #[test]
    fn add_type_folds_shapes_past_the_limit() {
        let mut ty = Type::empty();
        for bits in 0..32 {
            ty.add_type(shape_with_bits(bits, false));
        }
        assert!(keyed_count(&ty) <= MAX_KEYED_SHAPES);
        // Every key stays reachable; `a` stays required everywhere.
        for t in &ty.types {
            let Atomic::TKeyedArray { properties, .. } = t else {
                continue;
            };
            assert!(!properties[&ArrayKey::String(Arc::from("a"))].optional);
        }
        for i in 0..5 {
            let key = ArrayKey::String(Arc::from(format!("k{i}").as_str()));
            assert!(ty.types.iter().any(|t| matches!(
                t,
                Atomic::TKeyedArray { properties, .. } if properties.contains_key(&key)
            )));
        }
    }

    #[test]
    fn combine_keeps_emptiness_and_open_shape_soundness() {
        // `array{}` and `array{a: int}` differ in emptiness.
        assert!(combine_keyed_arrays(
            &shape(&[], false),
            &shape(&[("a", Atomic::TInt, false)], false)
        )
        .is_none());
        // Open and closed shapes don't mix.
        assert!(combine_keyed_arrays(
            &shape(&[("a", Atomic::TInt, false)], true),
            &shape(&[("a", Atomic::TInt, false)], false)
        )
        .is_none());
        // An open shape missing `k` already admits any `k`: drop it.
        assert_eq!(
            combine_keyed_arrays(
                &shape(&[("a", Atomic::TInt, false)], true),
                &shape(
                    &[("a", Atomic::TInt, false), ("k", Atomic::TString, false)],
                    true
                )
            ),
            Some(shape(&[("a", Atomic::TInt, false)], true))
        );
    }

    #[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));
    }
}