tsz-solver 0.1.8

//! Generic type subtype checking.
//!
//! This module handles subtyping for TypeScript's generic and reference types:
//! - Ref types (nominal references to type aliases, classes, interfaces)
//! - `TypeQuery` (typeof expressions)
//! - Type applications (Generic<T, U>)
//! - Mapped types ({ [K in keyof T]: T[K] })
//! - Type expansion and instantiation

use crate::def::DefId;
use crate::types::{MappedModifier, Visibility};
use crate::types::{MappedTypeId, SymbolRef, TypeApplicationId, TypeId};
use crate::visitor::{
    application_id, index_access_parts, keyof_inner_type, lazy_def_id, literal_value,
    mapped_type_id, object_shape_id, object_with_index_shape_id, ref_symbol, type_param_info,
    union_list_id,
};
use tsz_binder::SymbolId;

use super::super::{SubtypeChecker, SubtypeResult, TypeResolver};

impl<'a, R: TypeResolver> SubtypeChecker<'a, R> {
    /// Helper for resolving two Ref/TypeQuery symbols and checking subtype.
    ///
    /// Handles the common pattern of:
    /// - Both resolved: check `s_type` <: `t_type`
    /// - Only source resolved: check `s_type` <: target
    /// - Only target resolved: check source <: `t_type`
    /// - Neither resolved: False
    pub(crate) fn check_resolved_pair_subtype(
        &mut self,
        source: TypeId,
        target: TypeId,
        s_resolved: Option<TypeId>,
        t_resolved: Option<TypeId>,
    ) -> SubtypeResult {
        match (s_resolved, t_resolved) {
            (Some(s_type), Some(t_type)) => self.check_subtype(s_type, t_type),
            (Some(s_type), None) => self.check_subtype(s_type, target),
            (None, Some(t_type)) => self.check_subtype(source, t_type),
            (None, None) => SubtypeResult::False,
        }
    }

    /// Check Ref to Ref subtype with optional identity shortcut.
    ///
    /// For class-to-class checks, uses `InheritanceGraph` for O(1) nominal subtyping
    /// before falling back to structural checking. This is critical for:
    /// - Performance: Avoids expensive member-by-member comparison
    /// - Correctness: Properly handles private/protected members (nominal, not structural)
    /// - Recursive types: Breaks cycles in class inheritance (e.g., `class Box { next: Box }`)
    ///
    /// # DefId-Level Cycle Detection
    ///
    /// This function implements cycle detection at the `SymbolRef` level (analogous to `DefId`)
    /// to catch recursive types before resolution. This prevents infinite expansion of
    /// types like:
    /// - `type List<T> = { head: T; tail: List<T> }`
    /// - `interface Recursive { self: Recursive }`
    ///
    /// When we detect that we're comparing the same (`source_sym`, `target_sym`) pair that
    /// we're already checking, we return `CycleDetected` (coinductive semantics) which
    /// implements coinductive subtype checking for recursive types.
    pub(crate) fn check_ref_ref_subtype(
        &mut self,
        source: TypeId,
        target: TypeId,
        s_sym: SymbolRef,
        t_sym: SymbolRef,
    ) -> SubtypeResult {
        // Identity check: same symbol is always a subtype of itself
        if s_sym == t_sym {
            return SubtypeResult::True;
        }

        // =======================================================================
        // DefId-level cycle detection (before resolution!)
        //
        // This catches cycles in recursive type aliases and interfaces at the
        // symbol level, preventing infinite expansion. We check this BEFORE
        // resolving the symbols to their structural forms.
        // =======================================================================
        let ref_pair = (s_sym, t_sym);
        if self.seen_refs.contains(&ref_pair) {
            // We're in a cycle at the symbol level - return CycleDetected
            // This implements coinductive semantics for recursive types
            return SubtypeResult::CycleDetected;
        }

        // Also check the reversed pair for bivariant cross-recursion
        let reversed_ref_pair = (t_sym, s_sym);
        if self.seen_refs.contains(&reversed_ref_pair) {
            return SubtypeResult::CycleDetected;
        }

        // Mark this pair as being checked
        self.seen_refs.insert(ref_pair);

        // O(1) nominal class subtype checking using InheritanceGraph
        // This short-circuits expensive structural checks for class inheritance
        if let (Some(graph), Some(is_class)) = (self.inheritance_graph, self.is_class_symbol) {
            // Check if both symbols are classes (not interfaces or type aliases)
            let s_is_class = is_class(s_sym);
            let t_is_class = is_class(t_sym);

            if s_is_class && t_is_class {
                // Both are classes - use nominal inheritance check
                // Convert SymbolRef to SymbolId for InheritanceGraph
                let s_sid = SymbolId(s_sym.0);
                let t_sid = SymbolId(t_sym.0);

                if graph.is_derived_from(s_sid, t_sid) {
                    // O(1) bitset check: source is a subclass of target
                    self.seen_refs.remove(&ref_pair);
                    return SubtypeResult::True;
                }

                // Not a subclass - fall through to structural check below
                // This handles the case where a class is structurally compatible
                // even though it doesn't inherit from the target
            }
        }

        let s_resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(s_sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(s_sym, self.interner)
        };
        let t_resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(t_sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(t_sym, self.interner)
        };
        let result = self.check_resolved_pair_subtype(source, target, s_resolved, t_resolved);

        // Remove from seen set after checking
        self.seen_refs.remove(&ref_pair);

        result
    }

    /// Check Lazy(DefId) to Lazy(DefId) subtype with optional identity shortcut.
    ///
    /// Handles cycles in Lazy(DefId) types and uses the `InheritanceGraph` bridge
    /// for O(1) nominal class subtype checking.
    pub(crate) fn check_lazy_lazy_subtype(
        &mut self,
        source: TypeId,
        target: TypeId,
        s_def: DefId,
        t_def: DefId,
    ) -> SubtypeResult {
        // =======================================================================
        // IDENTITY CHECK: O(1) DefId equality
        // =======================================================================
        // If both DefIds are the same, we're checking the same type against itself.
        // This implements coinductive semantics: a recursive type is a subtype of itself.
        if s_def == t_def {
            return SubtypeResult::True;
        }

        // =======================================================================
        // CYCLE DETECTION: DefId-level tracking
        // =======================================================================
        // This catches cycles in recursive type aliases at the DefId level,
        // preventing infinite expansion. We check this BEFORE resolving the DefIds
        // to their structural forms.
        // =======================================================================
        let def_pair = (s_def, t_def);

        // Check reversed pair for bivariant cross-recursion
        if self.def_guard.is_visiting(&(t_def, s_def)) {
            return SubtypeResult::CycleDetected;
        }

        use crate::recursion::RecursionResult;
        match self.def_guard.enter(def_pair) {
            RecursionResult::Cycle => return SubtypeResult::CycleDetected,
            RecursionResult::DepthExceeded | RecursionResult::IterationExceeded => {
                return SubtypeResult::DepthExceeded;
            }
            RecursionResult::Entered => {}
        }

        // =======================================================================
        // O(1) NOMINAL CLASS SUBTYPE CHECKING (InheritanceGraph Bridge)
        // =======================================================================
        // This short-circuits expensive structural checks for class inheritance.
        // We use the def_to_symbol bridge to map DefIds back to SymbolIds, then
        // use the existing InheritanceGraph for O(1) nominal subtype checking.
        // =======================================================================
        if let Some(graph) = self.inheritance_graph
            && let (Some(s_sym), Some(t_sym)) = (
                self.resolver.def_to_symbol_id(s_def),
                self.resolver.def_to_symbol_id(t_def),
            )
            && let Some(is_class) = self.is_class_symbol
        {
            // Check if both symbols are classes (not interfaces or type aliases)
            let s_is_class = is_class(SymbolRef(s_sym.0));
            let t_is_class = is_class(SymbolRef(t_sym.0));

            if s_is_class && t_is_class {
                // Both are classes - use nominal inheritance check
                if graph.is_derived_from(s_sym, t_sym) {
                    // O(1) bitset check: source is a subclass of target
                    self.def_guard.leave(def_pair);
                    return SubtypeResult::True;
                }
                // Not a subclass - fall through to structural check below
            }
        }

        // Resolve DefIds to their structural forms
        let s_resolved = self.resolver.resolve_lazy(s_def, self.interner);
        let t_resolved = self.resolver.resolve_lazy(t_def, self.interner);
        let result = self.check_resolved_pair_subtype(source, target, s_resolved, t_resolved);

        // Leave def_guard after checking
        self.def_guard.leave(def_pair);

        result
    }

    /// Check `TypeQuery` to `TypeQuery` subtype with optional identity shortcut.
    pub(crate) fn check_typequery_typequery_subtype(
        &mut self,
        source: TypeId,
        target: TypeId,
        s_sym: SymbolRef,
        t_sym: SymbolRef,
    ) -> SubtypeResult {
        if s_sym == t_sym {
            return SubtypeResult::True;
        }

        let s_resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(s_sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(s_sym, self.interner)
        };
        let t_resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(t_sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(t_sym, self.interner)
        };
        self.check_resolved_pair_subtype(source, target, s_resolved, t_resolved)
    }

    /// Check Ref to structural type subtype.
    ///
    /// When the source type is a nominal reference (Ref), we must resolve it to
    /// its structural type and then check subtyping against the target.
    pub(crate) fn check_ref_subtype(
        &mut self,
        _source: TypeId,
        target: TypeId,
        sym: SymbolRef,
    ) -> SubtypeResult {
        let resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(sym, self.interner)
        };
        match resolved {
            Some(s_resolved) => self.check_subtype(s_resolved, target),
            None => SubtypeResult::False,
        }
    }

    /// Check structural type to Ref subtype.
    ///
    /// When the target type is a nominal reference (Ref), we must resolve it to
    /// its structural type and then check if the source is a subtype of that.
    pub(crate) fn check_to_ref_subtype(
        &mut self,
        source: TypeId,
        _target: TypeId,
        sym: SymbolRef,
    ) -> SubtypeResult {
        let resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(sym, self.interner)
        };
        match resolved {
            Some(t_resolved) => self.check_subtype(source, t_resolved),
            None => SubtypeResult::False,
        }
    }

    /// Check `TypeQuery` (typeof) to structural type subtype.
    pub(crate) fn check_typequery_subtype(
        &mut self,
        _source: TypeId,
        target: TypeId,
        sym: SymbolRef,
    ) -> SubtypeResult {
        let resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(sym, self.interner)
        };
        match resolved {
            Some(s_resolved) => self.check_subtype(s_resolved, target),
            None => SubtypeResult::False,
        }
    }

    /// Check structural type to `TypeQuery` (typeof) subtype.
    pub(crate) fn check_to_typequery_subtype(
        &mut self,
        source: TypeId,
        _target: TypeId,
        sym: SymbolRef,
    ) -> SubtypeResult {
        let resolved = if let Some(def_id) = self.resolver.symbol_to_def_id(sym) {
            self.resolver.resolve_lazy(def_id, self.interner)
        } else {
            self.resolver.resolve_symbol_ref(sym, self.interner)
        };
        match resolved {
            Some(t_resolved) => self.check_subtype(source, t_resolved),
            None => SubtypeResult::False,
        }
    }

    /// Check if a generic type application is a subtype of another application.
    ///
    /// Variance-aware generic assignability checking.
    ///
    /// This function implements O(1) generic type assignability by using variance
    /// annotations to avoid expensive structural expansion. When both applications
    /// have the same base type, we use the variance mask to check each type argument:
    /// - Covariant: check `s_arg` <: `t_arg`
    /// - Contravariant: check `t_arg` <: `s_arg` (reversed)
    /// - Invariant: check both directions (mutual subtyping)
    /// - Independent: skip (no constraint needed)
    ///
    /// If variance is unavailable or bases differ, fall back to structural expansion.
    pub(crate) fn check_application_to_application_subtype(
        &mut self,
        s_app_id: TypeApplicationId,
        t_app_id: TypeApplicationId,
    ) -> SubtypeResult {
        let s_app = self.interner.type_application(s_app_id);
        let t_app = self.interner.type_application(t_app_id);

        // =======================================================================
        // VARIANCE-AWARE FAST PATH: Same base type with variance checking
        // =======================================================================
        // When both applications have the same base (e.g., Array<T>), we can use
        // variance annotations to check type arguments without expanding the
        // entire structure. This is critical for O(1) performance.
        // =======================================================================
        if s_app.base == t_app.base && s_app.args.len() == t_app.args.len() {
            // Try to resolve DefId from the base to query variance
            let def_id = if let Some(id) = lazy_def_id(self.interner, s_app.base) {
                // Base is Lazy(DefId) - use DefId directly
                Some(id)
            } else if let Some(sym) = ref_symbol(self.interner, s_app.base) {
                // Base is Ref(SymbolRef) - convert to DefId
                self.resolver.symbol_to_def_id(sym)
            } else {
                // Base is neither Lazy nor Ref - can't get variance
                None
            };

            if let Some(def_id) = def_id {
                // Try to get variance from query_db (if available)
                // This enables O(1) variance-based generic assignability checking
                // Use fully qualified syntax to disambiguate QueryDatabase vs TypeResolver
                use crate::db::QueryDatabase;
                let variances = self
                    .query_db
                    .and_then(|db| QueryDatabase::get_type_param_variance(db, def_id));

                if let Some(variances) = variances {
                    // Ensure variance count matches arg count (may differ with defaults)
                    if variances.len() == s_app.args.len() {
                        let mut all_ok = true;
                        for (i, variance) in variances.iter().enumerate() {
                            let s_arg = s_app.args[i];
                            let t_arg = t_app.args[i];

                            // Apply variance rules for each type argument
                            if variance.is_invariant() {
                                // Invariant: Must be mutually assignable (effectively equal)
                                // Both directions must hold for soundness
                                if !self.check_subtype(s_arg, t_arg).is_true()
                                    || !self.check_subtype(t_arg, s_arg).is_true()
                                {
                                    all_ok = false;
                                    break;
                                }
                            } else if variance.is_covariant() {
                                // Covariant: source <: target (normal direction)
                                if !self.check_subtype(s_arg, t_arg).is_true() {
                                    all_ok = false;
                                    break;
                                }
                            } else if variance.is_contravariant() {
                                // Contravariant: target <: source (reversed direction)
                                // Function parameters are the classic example
                                if !self.check_subtype(t_arg, s_arg).is_true() {
                                    all_ok = false;
                                    break;
                                }
                            }
                            // Independent: No check needed (type parameter not used)
                        }

                        if all_ok {
                            return SubtypeResult::True;
                        }

                        // If variance check failed, return False immediately
                        // because for the SAME base, structural expansion won't help
                        // (the variance check is semantically equivalent to expansion)
                        return SubtypeResult::False;
                    }
                }
            }
        }

        // =======================================================================
        // CYCLE DETECTION: DefId-level tracking for Application base pairs
        // =======================================================================
        // When checking App(List, args1) <: App(Seq, args2), structural expansion
        // can produce recursive applications (e.g., List<Pair<T,S>> <: Seq<Pair<T,S>>
        // expanding to members that return List<Pair<Pair<T,S>,S2>> <: Seq<Pair<...>>).
        // Without cycle detection at the base-type level, this infinite expansion
        // leads to false negatives. We detect cycles by tracking (source_base_DefId,
        // target_base_DefId) pairs — coinductive semantics assume the relation holds.
        // =======================================================================
        let s_base_def = lazy_def_id(self.interner, s_app.base).or_else(|| {
            ref_symbol(self.interner, s_app.base)
                .and_then(|sym| self.resolver.symbol_to_def_id(sym))
        });
        let t_base_def = lazy_def_id(self.interner, t_app.base).or_else(|| {
            ref_symbol(self.interner, t_app.base)
                .and_then(|sym| self.resolver.symbol_to_def_id(sym))
        });

        let app_def_pair = match (s_base_def, t_base_def) {
            (Some(s_def), Some(t_def)) if s_def != t_def => Some((s_def, t_def)),
            _ => None,
        };

        if let Some(def_pair) = app_def_pair {
            // Check for cycles before expansion
            if self.def_guard.is_visiting(&def_pair)
                || self.def_guard.is_visiting(&(def_pair.1, def_pair.0))
            {
                return SubtypeResult::CycleDetected;
            }
            use crate::recursion::RecursionResult;
            match self.def_guard.enter(def_pair) {
                RecursionResult::Cycle => return SubtypeResult::CycleDetected,
                RecursionResult::DepthExceeded | RecursionResult::IterationExceeded => {
                    return SubtypeResult::DepthExceeded;
                }
                RecursionResult::Entered => {}
            }
        }

        // =======================================================================
        // SLOW PATH: Structural expansion for mismatched bases or unknown variance
        // =======================================================================
        // When bases differ or variance is unavailable, we expand both applications
        // to their structural forms and compare. This handles cases like:
        // - interface Child<T> extends Parent<T>
        // - Generic types without variance annotations
        // - Type aliases with complex transformations
        // =======================================================================
        let s_expanded = self.try_expand_application(s_app_id);
        let t_expanded = self.try_expand_application(t_app_id);
        let result = match (s_expanded, t_expanded) {
            (Some(s_struct), Some(t_struct)) => self.check_subtype(s_struct, t_struct),
            (Some(s_struct), None) => {
                // Re-intern the target application for comparison
                let t_app = self.interner.type_application(t_app_id);
                let target = self.interner.application(t_app.base, t_app.args.clone());
                self.check_subtype(s_struct, target)
            }
            (None, Some(t_struct)) => {
                let s_app = self.interner.type_application(s_app_id);
                let source = self.interner.application(s_app.base, s_app.args.clone());
                self.check_subtype(source, t_struct)
            }
            (None, None) => {
                // Compatibility fallback: when both applications share the same base and
                // cannot be structurally expanded (e.g. lib/interface generic applications),
                // apply a covariant argument check before failing hard.
                //
                // This mirrors common TS behavior for readonly/out-position generic uses and
                // avoids broad false-positive assignability failures from an expansion miss.
                if s_app.base == t_app.base && s_app.args.len() == t_app.args.len() {
                    let mut all_ok = true;
                    for (s_arg, t_arg) in s_app.args.iter().zip(t_app.args.iter()) {
                        if !self.check_subtype(*s_arg, *t_arg).is_true() {
                            all_ok = false;
                            break;
                        }
                    }
                    if all_ok {
                        SubtypeResult::True
                    } else {
                        SubtypeResult::False
                    }
                } else {
                    SubtypeResult::False
                }
            }
        };

        // Clean up cycle detection guard
        if let Some(def_pair) = app_def_pair {
            self.def_guard.leave(def_pair);
        }

        result
    }

    /// Check application-to-application structural comparison.
    ///
    /// When both source and target are type applications that resolve to mapped types
    /// over the same type parameter (e.g., `Readonly<T>` vs `Partial<T>`), compare
    /// the mapped type structure directly rather than trying to expand.
    pub(crate) fn check_application_to_application(
        &mut self,
        source: TypeId,
        target: TypeId,
        s_app_id: TypeApplicationId,
        t_app_id: TypeApplicationId,
    ) -> SubtypeResult {
        // Try to resolve both applications to see if they are mapped types
        let s_resolved = self.try_resolve_application_body(s_app_id);
        let t_resolved = self.try_resolve_application_body(t_app_id);

        // If both resolve to mapped types, try direct mapped-to-mapped comparison
        if let (Some(s_body), Some(t_body)) = (s_resolved, t_resolved)
            && let (Some(s_mapped_id), Some(t_mapped_id)) = (
                mapped_type_id(self.interner, s_body),
                mapped_type_id(self.interner, t_body),
            )
        {
            return self.check_mapped_to_mapped(source, target, s_mapped_id, t_mapped_id);
        }

        SubtypeResult::False
    }

    /// Try to resolve the body of a type application (instantiated with its args),
    /// without requiring concrete expansion. This resolves the base type alias/interface
    /// body and instantiates it with the provided type arguments.
    fn try_resolve_application_body(&mut self, app_id: TypeApplicationId) -> Option<TypeId> {
        use crate::{TypeSubstitution, instantiate_type};

        let app = self.interner.type_application(app_id);

        let (type_params, resolved_body) =
            if let Some(def_id) = lazy_def_id(self.interner, app.base) {
                let params = self.resolver.get_lazy_type_params(def_id)?;
                let body = self.resolver.resolve_lazy(def_id, self.interner)?;
                (params, body)
            } else if let Some(symbol) = ref_symbol(self.interner, app.base) {
                let params = self.resolver.get_type_params(symbol)?;
                let body = if let Some(def_id) = self.resolver.symbol_to_def_id(symbol) {
                    self.resolver.resolve_lazy(def_id, self.interner)?
                } else {
                    self.resolver.resolve_symbol_ref(symbol, self.interner)?
                };
                (params, body)
            } else {
                return None;
            };

        // Skip if self-referential
        if let Some(resolved_app_id) = application_id(self.interner, resolved_body)
            && resolved_app_id == app_id
        {
            return None;
        }

        let substitution = TypeSubstitution::from_args(self.interner, &type_params, &app.args);
        Some(instantiate_type(
            self.interner,
            resolved_body,
            &substitution,
        ))
    }

    /// Check Application expansion to target (one-sided Application case).
    ///
    /// When the target is an Application type that can be expanded (e.g., conditional
    /// types, mapped types), we first expand it and then check subtyping.
    pub(crate) fn check_application_expansion_target(
        &mut self,
        _source: TypeId,
        target: TypeId,
        app_id: TypeApplicationId,
    ) -> SubtypeResult {
        match self.try_expand_application(app_id) {
            Some(expanded) => self.check_subtype(expanded, target),
            None => SubtypeResult::False,
        }
    }

    /// Check source to Application expansion (one-sided Application case).
    ///
    /// When the source is an Application type that can be expanded (e.g., conditional
    /// types, mapped types), we first expand it and then check subtyping.
    pub(crate) fn check_source_to_application_expansion(
        &mut self,
        source: TypeId,
        _target: TypeId,
        app_id: TypeApplicationId,
    ) -> SubtypeResult {
        match self.try_expand_application(app_id) {
            Some(expanded) => self.check_subtype(source, expanded),
            None => SubtypeResult::False,
        }
    }

    /// Check mapped-to-mapped structural comparison.
    ///
    /// When both source and target are mapped types, compare their structure directly
    /// rather than trying to expand (which fails for generic type parameters).
    ///
    /// This handles cases like:
    /// - `Readonly<T>` assignable to `Partial<T>` (template `T[K]` is same, target adds `?`)
    /// - `Partial<Readonly<T>>` assignable to `Readonly<Partial<T>>` (equivalent)
    /// - `T` wrapped in nested homomorphic mapped types
    ///
    /// The rule from tsc: when both mapped types have the same constraint, compare
    /// the template types. If the target adds optional (`?`), the source template
    /// must be assignable to `target_template | undefined`.
    pub(crate) fn check_mapped_to_mapped(
        &mut self,
        _source: TypeId,
        _target: TypeId,
        source_mapped_id: MappedTypeId,
        target_mapped_id: MappedTypeId,
    ) -> SubtypeResult {
        let source_mapped = self.interner.mapped_type(source_mapped_id);
        let target_mapped = self.interner.mapped_type(target_mapped_id);

        // Both must have the same constraint for this optimization to apply.
        // This handles cases like both being `keyof T` for the same T.
        if source_mapped.constraint != target_mapped.constraint {
            return SubtypeResult::False;
        }

        // Check template types.
        // For homomorphic mapped types with the same constraint, the templates
        // can be compared directly: source_template <: target_template.
        let source_template = source_mapped.template;
        let mut target_template = target_mapped.template;

        // If the target adds optional modifier, the target template is effectively
        // `template | undefined`, since optional properties accept undefined.
        let target_adds_optional = target_mapped.optional_modifier == Some(MappedModifier::Add);
        let source_adds_optional = source_mapped.optional_modifier == Some(MappedModifier::Add);

        if target_adds_optional && !source_adds_optional {
            // Target is `{ [K in ...]?: template }` — target template effectively
            // becomes `template | undefined`, so source template just needs to be
            // assignable to `template | undefined`.
            target_template = self.interner.union2(target_template, TypeId::UNDEFINED);
        }

        // If the source removes optional but the target doesn't, that's fine
        // (Required<T> to Partial<T> should work).

        // If the target removes optional (Required) but source doesn't, source
        // properties may be optional while target requires them — we can't
        // automatically approve this, so fall through to expansion.
        let target_removes_optional =
            target_mapped.optional_modifier == Some(MappedModifier::Remove);
        let source_removes_optional =
            source_mapped.optional_modifier == Some(MappedModifier::Remove);
        if target_removes_optional && !source_removes_optional {
            // Can't easily determine if source properties include undefined,
            // fall through to expansion.
            return SubtypeResult::False;
        }

        // Handle nested mapped types in templates.
        // For example, Partial<Readonly<T>> has template that is itself a mapped type.
        // Recursively compare if both templates are mapped types.
        if let (Some(s_inner_mapped), Some(t_inner_mapped)) = (
            mapped_type_id(self.interner, source_template),
            mapped_type_id(self.interner, target_template),
        ) {
            return self.check_mapped_to_mapped(
                source_template,
                target_template,
                s_inner_mapped,
                t_inner_mapped,
            );
        }

        // Compare templates directly
        self.check_subtype(source_template, target_template)
    }

    /// Check Mapped expansion to target (one-sided Mapped case).
    ///
    /// When the target is a Mapped type that can be expanded (e.g., `{ [K in keyof T]: T[K] }`),
    /// we first expand it and then check subtyping.
    pub(crate) fn check_mapped_expansion_target(
        &mut self,
        _source: TypeId,
        target: TypeId,
        mapped_id: MappedTypeId,
    ) -> SubtypeResult {
        match self.try_expand_mapped(mapped_id) {
            Some(expanded) => self.check_subtype(expanded, target),
            None => {
                if let Some(expanded) = self.try_expand_mapped_with_constraint(mapped_id) {
                    self.check_subtype(expanded, target)
                } else {
                    SubtypeResult::False
                }
            }
        }
    }

    /// Check source to Mapped expansion (one-sided Mapped case).
    ///
    /// When the source is a Mapped type that can be expanded, we first expand it
    /// and then check subtyping.
    pub(crate) fn check_source_to_mapped_expansion(
        &mut self,
        source: TypeId,
        _target: TypeId,
        mapped_id: MappedTypeId,
    ) -> SubtypeResult {
        match self.try_expand_mapped(mapped_id) {
            Some(expanded) => self.check_subtype(source, expanded),
            None => {
                if let Some(expanded) = self.try_expand_mapped_with_constraint(mapped_id) {
                    self.check_subtype(source, expanded)
                } else {
                    SubtypeResult::False
                }
            }
        }
    }

    fn try_expand_mapped_with_constraint(&mut self, mapped_id: MappedTypeId) -> Option<TypeId> {
        use crate::{MappedType, TypeData, TypeSubstitution, instantiate_type};
        let mapped = self.interner.mapped_type(mapped_id);
        if let Some(TypeData::KeyOf(source)) = self.interner.lookup(mapped.constraint)
            && let Some(TypeData::TypeParameter(param)) = self.interner.lookup(source)
            && let Some(constraint) = param.constraint
        {
            let mut subst = TypeSubstitution::new();
            subst.insert(param.name, constraint);
            // Use keyof(constraint) directly to prevent eager evaluation
            // which would break array/tuple preservation in evaluate_mapped.
            let inst_constraint = self.interner.keyof(constraint);
            let inst_template = instantiate_type(self.interner, mapped.template, &subst);
            let inst_name = mapped
                .name_type
                .map(|n| instantiate_type(self.interner, n, &subst));
            let new_mapped_id = self.interner.mapped(MappedType {
                type_param: mapped.type_param.clone(),
                constraint: inst_constraint,
                name_type: inst_name,
                template: inst_template,
                optional_modifier: mapped.optional_modifier,
                readonly_modifier: mapped.readonly_modifier,
            });
            if let Some(TypeData::Mapped(m_id)) = self.interner.lookup(new_mapped_id) {
                let new_mapped = self.interner.mapped_type(m_id);
                let res = crate::evaluate::evaluate_mapped(self.interner, &new_mapped);
                if res != TypeId::ERROR && res != new_mapped_id {
                    return Some(res);
                }
            }
        }
        None
    }

    /// Try to expand an Application type to its structural form.
    /// Returns None if the application cannot be expanded (missing type params or body).
    ///
    /// Supports both Ref(SymbolRef) and Lazy(DefId) bases for unified generic type expansion.
    pub(crate) fn try_expand_application(&mut self, app_id: TypeApplicationId) -> Option<TypeId> {
        use crate::{TypeSubstitution, instantiate_type};

        let app = self.interner.type_application(app_id);

        // Try to get type params and resolved body from either Ref or Lazy base
        let (type_params, resolved_body) = if let Some(symbol) = ref_symbol(self.interner, app.base)
        {
            let params = self.resolver.get_type_params(symbol)?;
            let body = if let Some(def_id) = self.resolver.symbol_to_def_id(symbol) {
                self.resolver.resolve_lazy(def_id, self.interner)?
            } else {
                self.resolver.resolve_symbol_ref(symbol, self.interner)?
            };
            (params, body)
        } else if let Some(def_id) = lazy_def_id(self.interner, app.base) {
            let params = self.resolver.get_lazy_type_params(def_id)?;
            let body = self.resolver.resolve_lazy(def_id, self.interner)?;
            (params, body)
        } else {
            return None;
        };

        // Skip expansion if the resolved type is just this Application
        // (prevents infinite recursion on self-referential types)
        if let Some(resolved_app_id) = application_id(self.interner, resolved_body)
            && resolved_app_id == app_id
        {
            return None;
        }

        // Create substitution and instantiate
        let substitution = TypeSubstitution::from_args(self.interner, &type_params, &app.args);
        let instantiated = instantiate_type(self.interner, resolved_body, &substitution);

        // Return the instantiated type for recursive checking
        Some(instantiated)
    }

    /// Try to expand a Mapped type to its structural form.
    /// Returns None if the mapped type cannot be expanded (unresolvable constraint).
    pub(crate) fn try_expand_mapped(&mut self, mapped_id: MappedTypeId) -> Option<TypeId> {
        use crate::{MappedModifier, PropertyInfo, TypeSubstitution, instantiate_type};

        let mapped = self.interner.mapped_type(mapped_id);

        // Get concrete keys from the constraint
        let keys = self.try_evaluate_mapped_constraint(mapped.constraint)?;
        if keys.is_empty() {
            return None;
        }

        let (source_object, is_homomorphic) =
            match index_access_parts(self.interner, mapped.template) {
                Some((obj, idx)) => {
                    let is_homomorphic = type_param_info(self.interner, idx)
                        .is_some_and(|param| param.name == mapped.type_param.name);
                    let source_object = is_homomorphic.then_some(obj);
                    (source_object, is_homomorphic)
                }
                None => (None, false),
            };

        // Helper to get original property modifiers
        let get_original_modifiers = |key_name: tsz_common::interner::Atom| -> (bool, bool) {
            if let Some(source_obj) = source_object {
                let shape_id = object_shape_id(self.interner, source_obj)
                    .or_else(|| object_with_index_shape_id(self.interner, source_obj));
                if let Some(shape_id) = shape_id {
                    let shape = self.interner.object_shape(shape_id);
                    for prop in &shape.properties {
                        if prop.name == key_name {
                            return (prop.optional, prop.readonly);
                        }
                    }
                }
            }
            (false, false)
        };

        // Build properties by instantiating template for each key
        let mut properties = Vec::new();
        for key_name in keys {
            let key_literal = self.interner.literal_string_atom(key_name);

            let mut subst = TypeSubstitution::new();
            subst.insert(mapped.type_param.name, key_literal);

            let instantiated_type = instantiate_type(self.interner, mapped.template, &subst);
            let property_type = self.evaluate_type(instantiated_type);

            // Determine modifiers based on mapped type configuration
            let (original_optional, original_readonly) = get_original_modifiers(key_name);
            let optional = match mapped.optional_modifier {
                Some(MappedModifier::Add) => true,
                Some(MappedModifier::Remove) => false,
                None => {
                    if is_homomorphic {
                        original_optional
                    } else {
                        false
                    }
                }
            };
            let readonly = match mapped.readonly_modifier {
                Some(MappedModifier::Add) => true,
                Some(MappedModifier::Remove) => false,
                None => {
                    if is_homomorphic {
                        original_readonly
                    } else {
                        false
                    }
                }
            };

            properties.push(PropertyInfo {
                name: key_name,
                type_id: property_type,
                write_type: property_type,
                optional,
                readonly,
                is_method: false,
                visibility: Visibility::Public,
                parent_id: None,
            });
        }

        Some(self.interner.object(properties))
    }

    /// Try to evaluate a mapped type constraint to get concrete string keys.
    /// Returns None if the constraint can't be resolved to concrete keys.
    pub(crate) fn try_evaluate_mapped_constraint(
        &self,
        constraint: TypeId,
    ) -> Option<Vec<tsz_common::interner::Atom>> {
        use crate::LiteralValue;

        if let Some(operand) = keyof_inner_type(self.interner, constraint) {
            // Try to resolve the operand to get concrete keys
            return self.try_get_keyof_keys(operand);
        }

        if let Some(LiteralValue::String(name)) = literal_value(self.interner, constraint) {
            return Some(vec![name]);
        }

        if let Some(list_id) = union_list_id(self.interner, constraint) {
            let members = self.interner.type_list(list_id);
            let mut keys = Vec::new();
            for &member in members.iter() {
                if let Some(LiteralValue::String(name)) = literal_value(self.interner, member) {
                    keys.push(name);
                }
            }
            return if keys.is_empty() { None } else { Some(keys) };
        }

        None
    }

    /// Try to get keys from keyof an operand type.
    pub(crate) fn try_get_keyof_keys(
        &self,
        operand: TypeId,
    ) -> Option<Vec<tsz_common::interner::Atom>> {
        let shape_id = object_shape_id(self.interner, operand)
            .or_else(|| object_with_index_shape_id(self.interner, operand));
        if let Some(shape_id) = shape_id {
            let shape = self.interner.object_shape(shape_id);
            if shape.properties.is_empty() {
                return None;
            }
            return Some(shape.properties.iter().map(|p| p.name).collect());
        }

        // Handle DefId-based Lazy types (new API)
        if let Some(def_id) = lazy_def_id(self.interner, operand) {
            let resolved = self.resolver.resolve_lazy(def_id, self.interner)?;
            if resolved == operand {
                return None; // Avoid infinite recursion
            }
            return self.try_get_keyof_keys(resolved);
        }

        // Handle legacy SymbolRef-based types (old API)
        if let Some(symbol) = ref_symbol(self.interner, operand) {
            // Try to resolve the ref and get keys from the resolved type
            let resolved = self.resolver.resolve_symbol_ref(symbol, self.interner)?;
            if resolved == operand {
                return None; // Avoid infinite recursion
            }
            return self.try_get_keyof_keys(resolved);
        }

        None
    }
}