tsz_solver/evaluation/

evaluate.rs

//! Type evaluation for meta-types (conditional, mapped, index access).
//!
//! Meta-types are "type-level functions" that compute output types from input types.
//! This module provides evaluation logic for:
//! - Conditional types: T extends U ? X : Y
//! - Distributive conditional types: (A | B) extends U ? X : Y
//! - Index access types: T[K]
//!
//! Key design:
//! - Lazy evaluation: only evaluate when needed for subtype checking
//! - Handles deferred evaluation when type parameters are unknown
//! - Supports distributivity for naked type parameters in unions

use crate::TypeDatabase;
use crate::caches::db::QueryDatabase;
use crate::def::DefId;
use crate::instantiation::instantiate::instantiate_generic;
use crate::relations::subtype::{NoopResolver, TypeResolver};
#[cfg(test)]
use crate::types::*;
use crate::types::{
    ConditionalType, ConditionalTypeId, MappedType, MappedTypeId, StringIntrinsicKind,
    TemplateLiteralId, TemplateSpan, TypeApplicationId, TypeData, TypeId, TypeListId,
    TypeParamInfo,
};
use rustc_hash::{FxHashMap, FxHashSet};

/// Result of conditional type evaluation
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ConditionalResult {
    /// The condition was resolved to a definite type
    Resolved(TypeId),
    /// The condition could not be resolved (deferred)
    /// This happens when `check_type` is a type parameter that hasn't been substituted
    Deferred(TypeId),
}

/// Maximum number of unique types to track in the visiting set.
/// Prevents unbounded memory growth in pathological cases.
pub const MAX_VISITING_SET_SIZE: usize = 10_000;

/// Controls which subtype direction makes a member redundant when simplifying
/// a union or intersection.
enum SubtypeDirection {
    /// member[i] <: member[j] → member[i] is redundant (union semantics).
    SourceSubsumedByOther,
    /// member[j] <: member[i] → member[i] is redundant (intersection semantics).
    OtherSubsumedBySource,
}

/// Type evaluator for meta-types.
///
/// # Salsa Preparation
/// This struct uses `&mut self` methods instead of `RefCell` + `&self`.
/// This makes the evaluator thread-safe (Send) and prepares for future
/// Salsa integration where state is managed by the database runtime.
pub struct TypeEvaluator<'a, R: TypeResolver = NoopResolver> {
    interner: &'a dyn TypeDatabase,
    /// Optional query database for Salsa-backed memoization.
    query_db: Option<&'a dyn QueryDatabase>,
    resolver: &'a R,
    no_unchecked_indexed_access: bool,
    cache: FxHashMap<TypeId, TypeId>,
    /// Unified recursion guard for `TypeId` cycle detection, depth, and iteration limits.
    guard: crate::recursion::RecursionGuard<TypeId>,
    /// Per-DefId recursion depth counter.
    /// Allows recursive type aliases (like `TrimRight`) to expand up to `MAX_DEF_DEPTH`
    /// times before stopping, matching tsc's TS2589 "Type instantiation is excessively
    /// deep and possibly infinite" behavior. Unlike a set-based cycle detector, this
    /// permits legitimate bounded recursion where each expansion converges.
    def_depth: FxHashMap<DefId, u32>,
}

/// Array methods that return any (used for apparent type computation).
pub const ARRAY_METHODS_RETURN_ANY: &[&str] = &[
    "concat",
    "filter",
    "flat",
    "flatMap",
    "map",
    "reverse",
    "slice",
    "sort",
    "splice",
    "toReversed",
    "toSorted",
    "toSpliced",
    "with",
    "at",
    "find",
    "findLast",
    "pop",
    "shift",
    "entries",
    "keys",
    "values",
    "reduce",
    "reduceRight",
];
/// Array methods that return boolean.
pub const ARRAY_METHODS_RETURN_BOOLEAN: &[&str] = &["every", "includes", "some"];
/// Array methods that return number.
pub const ARRAY_METHODS_RETURN_NUMBER: &[&str] = &[
    "findIndex",
    "findLastIndex",
    "indexOf",
    "lastIndexOf",
    "push",
    "unshift",
];
/// Array methods that return void.
pub const ARRAY_METHODS_RETURN_VOID: &[&str] = &["forEach", "copyWithin", "fill"];
/// Array methods that return string.
pub const ARRAY_METHODS_RETURN_STRING: &[&str] = &["join", "toLocaleString", "toString"];

impl<'a> TypeEvaluator<'a, NoopResolver> {
    /// Create a new evaluator without a resolver.
    pub fn new(interner: &'a dyn TypeDatabase) -> Self {
        static NOOP: NoopResolver = NoopResolver;
        TypeEvaluator {
            interner,
            query_db: None,
            resolver: &NOOP,
            no_unchecked_indexed_access: false,
            cache: FxHashMap::default(),
            guard: crate::recursion::RecursionGuard::with_profile(
                crate::recursion::RecursionProfile::TypeEvaluation,
            ),
            def_depth: FxHashMap::default(),
        }
    }
}

impl<'a, R: TypeResolver> TypeEvaluator<'a, R> {
    /// Maximum recursive expansion depth for a single `DefId`.
    /// Matches TypeScript's instantiation depth limit that triggers TS2589.
    const MAX_DEF_DEPTH: u32 = 50;

    /// Create a new evaluator with a custom resolver.
    pub fn with_resolver(interner: &'a dyn TypeDatabase, resolver: &'a R) -> Self {
        TypeEvaluator {
            interner,
            query_db: None,
            resolver,
            no_unchecked_indexed_access: false,
            cache: FxHashMap::default(),
            guard: crate::recursion::RecursionGuard::with_profile(
                crate::recursion::RecursionProfile::TypeEvaluation,
            ),
            def_depth: FxHashMap::default(),
        }
    }

    /// Set the query database for Salsa-backed memoization.
    pub fn with_query_db(mut self, db: &'a dyn QueryDatabase) -> Self {
        self.query_db = Some(db);
        self
    }

    pub fn set_no_unchecked_indexed_access(&mut self, enabled: bool) {
        if self.no_unchecked_indexed_access != enabled {
            self.cache.clear();
        }
        self.no_unchecked_indexed_access = enabled;
    }

    /// Reset per-evaluation state so this evaluator can be reused.
    ///
    /// Clears the cache, cycle detection sets, and counters while preserving
    /// configuration and borrowed references. Uses `.clear()` to reuse memory.
    #[inline]
    pub fn reset(&mut self) {
        self.cache.clear();
        self.guard.reset();
        self.def_depth.clear();
    }

    // =========================================================================
    // Accessor methods for evaluate_rules modules
    // =========================================================================

    /// Get the type interner.
    #[inline]
    pub(crate) fn interner(&self) -> &'a dyn TypeDatabase {
        self.interner
    }

    /// Get the type resolver.
    #[inline]
    pub(crate) const fn resolver(&self) -> &'a R {
        self.resolver
    }

    /// Check if `no_unchecked_indexed_access` is enabled.
    #[inline]
    pub(crate) const fn no_unchecked_indexed_access(&self) -> bool {
        self.no_unchecked_indexed_access
    }

    /// Check if depth limit was exceeded.
    #[inline]
    pub const fn is_depth_exceeded(&self) -> bool {
        self.guard.is_exceeded()
    }

    /// Mark the guard as exceeded, causing subsequent evaluations to bail out.
    ///
    /// Used when an external condition (e.g. mapped key count or distribution
    /// size exceeds its limit) means further recursive evaluation should stop.
    #[inline]
    pub(crate) const fn mark_depth_exceeded(&mut self) {
        self.guard.mark_exceeded();
    }

    /// Evaluate a type, resolving any meta-types if possible.
    /// Returns the evaluated type (may be the same if no evaluation needed).
    pub fn evaluate(&mut self, type_id: TypeId) -> TypeId {
        use crate::recursion::RecursionResult;

        // Fast path for intrinsics
        if type_id.is_intrinsic() {
            return type_id;
        }

        // Check if depth was already exceeded in a previous call
        if self.guard.is_exceeded() {
            return TypeId::ERROR;
        }

        if let Some(&cached) = self.cache.get(&type_id) {
            return cached;
        }

        // Unified enter: checks iterations, depth, cycle detection, and visiting set size
        match self.guard.enter(type_id) {
            RecursionResult::Entered => {}
            RecursionResult::Cycle => {
                // Recursion guard for self-referential mapped/application types.
                // Per TypeScript behavior, recursive mapped types evaluate to empty objects.
                let key = self.interner.lookup(type_id);
                if matches!(key, Some(TypeData::Mapped(_))) {
                    let empty = self.interner.object(vec![]);
                    self.cache.insert(type_id, empty);
                    return empty;
                }
                return type_id;
            }
            RecursionResult::DepthExceeded => {
                self.cache.insert(type_id, TypeId::ERROR);
                return TypeId::ERROR;
            }
            RecursionResult::IterationExceeded => {
                self.cache.insert(type_id, type_id);
                return type_id;
            }
        }

        let key = match self.interner.lookup(type_id) {
            Some(k) => k,
            None => {
                self.guard.leave(type_id);
                return type_id;
            }
        };

        // Visitor pattern: dispatch to appropriate visit_* method
        let result = self.visit_type_key(type_id, &key);

        // Symmetric cleanup: leave guard and cache result
        self.guard.leave(type_id);
        self.cache.insert(type_id, result);

        result
    }

    /// Evaluate a generic type application: Base<Args>
    ///
    /// Algorithm:
    /// 1. Look up the base type - if it's a Ref, resolve it
    /// 2. Get the type parameters for the base symbol
    /// 3. If we have type params, instantiate the resolved type with args
    /// 4. Recursively evaluate the result
    fn evaluate_application(&mut self, app_id: TypeApplicationId) -> TypeId {
        let app = self.interner.type_application(app_id);

        // Look up the base type
        let base_key = match self.interner.lookup(app.base) {
            Some(k) => k,
            None => return self.interner.application(app.base, app.args.clone()),
        };

        // Task B: Resolve TypeQuery bases to DefId for expansion
        // This fixes the "Ref(5)<error>" diagnostic issue where generic types
        // aren't expanded to their underlying function/object types
        // Note: Ref(SymbolRef) was migrated to Lazy(DefId)
        let def_id = match base_key {
            TypeData::Lazy(def_id) => Some(def_id),
            TypeData::TypeQuery(sym_ref) => self.resolver.symbol_to_def_id(sym_ref),
            _ => None,
        };

        tracing::trace!(
            base = app.base.0,
            base_key = ?base_key,
            def_id = ?def_id,
            args = ?app.args.iter().map(|a| a.0).collect::<Vec<_>>(),
            "evaluate_application"
        );

        // If the base is a DefId (Lazy, Ref, or TypeQuery), try to resolve and instantiate
        if let Some(def_id) = def_id {
            // =======================================================================
            // PER-DEFID DEPTH LIMITING
            // =======================================================================
            // This catches expansive recursion in type aliases like `type T<X> = T<Box<X>>`
            // that produce new TypeIds on each evaluation, bypassing the `visiting` set.
            //
            // Unlike a set-based cycle detector (which blocks ANY re-entry), we use a
            // per-DefId counter that allows up to MAX_DEF_DEPTH recursive expansions.
            // This correctly handles legitimate recursive types like:
            //   type TrimRight<S> = S extends `${infer R} ` ? TrimRight<R> : S;
            // which need multiple re-entries of the same DefId to converge.
            // =======================================================================
            let depth = self.def_depth.entry(def_id).or_insert(0);
            if *depth >= Self::MAX_DEF_DEPTH {
                self.guard.mark_exceeded();
                return TypeId::ERROR;
            }
            *depth += 1;

            // Try to get the type parameters for this DefId
            let type_params = self.resolver.get_lazy_type_params(def_id);
            let resolved = self.resolver.resolve_lazy(def_id, self.interner);

            tracing::trace!(
                ?def_id,
                has_type_params = type_params.is_some(),
                type_params_count = type_params.as_ref().map(std::vec::Vec::len),
                has_resolved = resolved.is_some(),
                resolved_key = ?resolved.and_then(|r| self.interner.lookup(r)),
                "evaluate_application resolve"
            );

            let result = if let Some(type_params) = type_params {
                // Resolve the base type to get the body
                if let Some(resolved) = resolved {
                    // Pre-expand type arguments that are TypeQuery or Application.
                    // For conditional type bodies with Application extends containing infer,
                    // preserve Application args so the conditional evaluator can match
                    // at the Application level (e.g., Promise<string> vs Promise<infer U>).
                    let body_is_conditional_with_app_infer =
                        self.is_conditional_with_application_infer(resolved);
                    let expanded_args = if body_is_conditional_with_app_infer {
                        self.expand_type_args_preserve_applications(&app.args)
                    } else {
                        self.expand_type_args(&app.args)
                    };
                    let no_unchecked_indexed_access = self.no_unchecked_indexed_access;

                    if let Some(db) = self.query_db
                        && let Some(cached) = db.lookup_application_eval_cache(
                            def_id,
                            &expanded_args,
                            no_unchecked_indexed_access,
                        )
                    {
                        if let Some(d) = self.def_depth.get_mut(&def_id) {
                            *d = d.saturating_sub(1);
                        }
                        return cached;
                    }

                    // Instantiate the resolved type with the type arguments
                    let instantiated =
                        instantiate_generic(self.interner, resolved, &type_params, &expanded_args);
                    // Recursively evaluate the result
                    let evaluated = self.evaluate(instantiated);
                    if let Some(db) = self.query_db {
                        db.insert_application_eval_cache(
                            def_id,
                            &expanded_args,
                            no_unchecked_indexed_access,
                            evaluated,
                        );
                    }
                    evaluated
                } else {
                    self.interner.application(app.base, app.args.clone())
                }
            } else if let Some(resolved) = resolved {
                // Fallback: try to extract type params from the resolved type's properties
                let extracted_params = self.extract_type_params_from_type(resolved);
                if !extracted_params.is_empty() && extracted_params.len() == app.args.len() {
                    // Pre-expand type arguments
                    let expanded_args = self.expand_type_args(&app.args);
                    let no_unchecked_indexed_access = self.no_unchecked_indexed_access;

                    if let Some(db) = self.query_db
                        && let Some(cached) = db.lookup_application_eval_cache(
                            def_id,
                            &expanded_args,
                            no_unchecked_indexed_access,
                        )
                    {
                        if let Some(d) = self.def_depth.get_mut(&def_id) {
                            *d = d.saturating_sub(1);
                        }
                        return cached;
                    }

                    let instantiated = instantiate_generic(
                        self.interner,
                        resolved,
                        &extracted_params,
                        &expanded_args,
                    );
                    let evaluated = self.evaluate(instantiated);
                    if let Some(db) = self.query_db {
                        db.insert_application_eval_cache(
                            def_id,
                            &expanded_args,
                            no_unchecked_indexed_access,
                            evaluated,
                        );
                    }
                    evaluated
                } else {
                    self.interner.application(app.base, app.args.clone())
                }
            } else {
                self.interner.application(app.base, app.args.clone())
            };

            // Decrement per-DefId depth after evaluation
            if let Some(d) = self.def_depth.get_mut(&def_id) {
                *d = d.saturating_sub(1);
            }

            result
        } else {
            // If we can't expand, return the original application
            self.interner.application(app.base, app.args.clone())
        }
    }

    /// Check if a type is a Conditional whose `extends_type` is an Application containing infer.
    /// This detects patterns like `T extends Promise<infer U> ? U : T`.
    fn is_conditional_with_application_infer(&self, type_id: TypeId) -> bool {
        let Some(TypeData::Conditional(cond_id)) = self.interner.lookup(type_id) else {
            return false;
        };
        let cond = self.interner.conditional_type(cond_id);
        matches!(
            self.interner.lookup(cond.extends_type),
            Some(TypeData::Application(_))
        )
    }

    /// Like `expand_type_args` but preserves Application types without evaluating them.
    /// Used for conditional type bodies so the conditional evaluator can match
    /// at the Application level for infer pattern matching.
    fn expand_type_args_preserve_applications(&mut self, args: &[TypeId]) -> Vec<TypeId> {
        let mut expanded = Vec::with_capacity(args.len());
        for &arg in args {
            let Some(key) = self.interner.lookup(arg) else {
                expanded.push(arg);
                continue;
            };
            match key {
                TypeData::Application(_) => {
                    // Preserve Application form for conditional infer matching
                    expanded.push(arg);
                }
                _ => expanded.push(self.try_expand_type_arg(arg)),
            }
        }
        expanded
    }

    /// Expand type arguments by evaluating any that are `TypeQuery` or Application.
    /// Uses a loop instead of closure to allow mutable self access.
    fn expand_type_args(&mut self, args: &[TypeId]) -> Vec<TypeId> {
        let mut expanded = Vec::with_capacity(args.len());
        for &arg in args {
            expanded.push(self.try_expand_type_arg(arg));
        }
        expanded
    }

    /// Extract type parameter infos from a type by scanning for `TypeParameter` types.
    fn extract_type_params_from_type(&self, type_id: TypeId) -> Vec<TypeParamInfo> {
        let mut seen = FxHashSet::default();
        let mut params = Vec::new();
        self.collect_type_params(type_id, &mut seen, &mut params);
        params
    }

    /// Recursively collect `TypeParameter` types from a type.
    fn collect_type_params(
        &self,
        type_id: TypeId,
        seen: &mut FxHashSet<tsz_common::interner::Atom>,
        params: &mut Vec<TypeParamInfo>,
    ) {
        if type_id.is_intrinsic() {
            return;
        }

        let Some(key) = self.interner.lookup(type_id) else {
            return;
        };

        match key {
            TypeData::TypeParameter(ref info) => {
                if !seen.contains(&info.name) {
                    seen.insert(info.name);
                    params.push(info.clone());
                }
            }
            TypeData::Object(shape_id) | TypeData::ObjectWithIndex(shape_id) => {
                let shape = self.interner.object_shape(shape_id);
                for prop in &shape.properties {
                    self.collect_type_params(prop.type_id, seen, params);
                }
            }
            TypeData::Function(shape_id) => {
                let shape = self.interner.function_shape(shape_id);
                for param in &shape.params {
                    self.collect_type_params(param.type_id, seen, params);
                }
                self.collect_type_params(shape.return_type, seen, params);
            }
            TypeData::Union(members) | TypeData::Intersection(members) => {
                let members = self.interner.type_list(members);
                for &member in members.iter() {
                    self.collect_type_params(member, seen, params);
                }
            }
            TypeData::Array(elem) => {
                self.collect_type_params(elem, seen, params);
            }
            TypeData::Conditional(cond_id) => {
                let cond = self.interner.conditional_type(cond_id);
                self.collect_type_params(cond.check_type, seen, params);
                self.collect_type_params(cond.extends_type, seen, params);
                self.collect_type_params(cond.true_type, seen, params);
                self.collect_type_params(cond.false_type, seen, params);
            }
            TypeData::Application(app_id) => {
                let app = self.interner.type_application(app_id);
                self.collect_type_params(app.base, seen, params);
                for &arg in &app.args {
                    self.collect_type_params(arg, seen, params);
                }
            }
            TypeData::Mapped(mapped_id) => {
                let mapped = self.interner.mapped_type(mapped_id);
                // Note: mapped.type_param is the iteration variable (e.g., K in "K in keyof T")
                // We should NOT add it directly - the outer type param (T) is found in the constraint.
                // For DeepPartial<T> = { [K in keyof T]?: DeepPartial<T[K]> }:
                //   - type_param is K (iteration var, NOT the outer param)
                //   - constraint is "keyof T" (contains T, the actual param to extract)
                //   - template is DeepPartial<T[K]> (also contains T)
                self.collect_type_params(mapped.constraint, seen, params);
                self.collect_type_params(mapped.template, seen, params);
                if let Some(name_type) = mapped.name_type {
                    self.collect_type_params(name_type, seen, params);
                }
            }
            TypeData::KeyOf(operand) => {
                // Extract type params from the operand of keyof
                // e.g., keyof T -> extract T
                self.collect_type_params(operand, seen, params);
            }
            TypeData::IndexAccess(obj, idx) => {
                // Extract type params from both object and index
                // e.g., T[K] -> extract T and K
                self.collect_type_params(obj, seen, params);
                self.collect_type_params(idx, seen, params);
            }
            TypeData::TemplateLiteral(spans) => {
                // Extract type params from template literal interpolations
                let spans = self.interner.template_list(spans);
                for span in spans.iter() {
                    if let TemplateSpan::Type(inner) = span {
                        self.collect_type_params(*inner, seen, params);
                    }
                }
            }
            _ => {}
        }
    }

    /// Try to expand a type argument that may be a `TypeQuery` or Application.
    /// Returns the expanded type, or the original if it can't be expanded.
    /// This ensures type arguments are resolved before instantiation.
    ///
    /// NOTE: This method uses `self.evaluate()` for Application, Conditional, Mapped,
    /// and `TemplateLiteral` types to ensure recursion depth limits are enforced.
    fn try_expand_type_arg(&mut self, arg: TypeId) -> TypeId {
        let Some(key) = self.interner.lookup(arg) else {
            return arg;
        };
        match key {
            TypeData::TypeQuery(sym_ref) => {
                // Resolve the TypeQuery to get the VALUE type (constructor for classes).
                // Use resolve_ref, not resolve_symbol_ref, to avoid the resolve_lazy path
                // which returns instance types for classes.
                if let Some(resolved) = self.resolver.resolve_ref(sym_ref, self.interner) {
                    resolved
                } else if let Some(def_id) = self.resolver.symbol_to_def_id(sym_ref) {
                    self.resolver
                        .resolve_lazy(def_id, self.interner)
                        .unwrap_or(arg)
                } else {
                    arg
                }
            }
            TypeData::Application(_)
            | TypeData::Conditional(_)
            | TypeData::Mapped(_)
            | TypeData::TemplateLiteral(_) => {
                // Use evaluate() to ensure depth limits are enforced
                self.evaluate(arg)
            }
            TypeData::Lazy(def_id) => {
                // Resolve Lazy types in type arguments
                // This helps with generic instantiation accuracy
                self.resolver
                    .resolve_lazy(def_id, self.interner)
                    .unwrap_or(arg)
            }
            _ => arg,
        }
    }

    /// Check if a type is "complex" and requires full evaluation for identity.
    ///
    /// Complex types are those whose structural identity depends on evaluation context:
    /// - `TypeParameter`: Opaque until instantiation
    /// - Lazy: Requires resolution
    /// - Conditional: Requires evaluation of extends clause
    /// - Mapped: Requires evaluation of mapped type
    /// - `IndexAccess`: Requires evaluation of T[K]
    /// - `KeyOf`: Requires evaluation of keyof
    /// - Application: Requires expansion of Base<Args>
    /// - `TypeQuery`: Requires resolution of typeof
    /// - `TemplateLiteral`: Requires evaluation of template parts
    /// - `ReadonlyType`: Wraps another type
    /// - `StringIntrinsic`: Uppercase, Lowercase, Capitalize, Uncapitalize
    ///
    /// These types are NOT safe for simplification because bypassing evaluation
    /// would produce incorrect results (e.g., treating T[K] as a distinct type from
    /// the value it evaluates to).
    ///
    /// ## Task #37: Deep Structural Simplification
    ///
    /// After implementing the Canonicalizer (Task #32), we can now safely handle
    /// `Lazy` (type aliases) and `Application` (generics) structurally. These types
    /// are now "unlocked" for simplification because:
    /// - `Lazy` types are canonicalized using De Bruijn indices
    /// - `Application` types are recursively canonicalized
    /// - The `SubtypeChecker`'s fast-path (Task #36) uses O(1) structural identity
    ///
    /// Types that remain "complex" are those that are **inherently deferred**:
    /// - `TypeParameter`, `Infer`: Waiting for generic substitution
    /// - `Conditional`, `Mapped`, `IndexAccess`, `KeyOf`: Require type-level computation
    /// - These cannot be compared structurally until they are fully evaluated
    fn is_complex_type(&self, type_id: TypeId) -> bool {
        let Some(key) = self.interner.lookup(type_id) else {
            return false;
        };

        matches!(
            key,
            TypeData::TypeParameter(_)
                | TypeData::Infer(_) // Type parameter for conditional types
                | TypeData::Conditional(_)
                | TypeData::Mapped(_)
                | TypeData::IndexAccess(_, _)
                | TypeData::KeyOf(_)
                | TypeData::TypeQuery(_)
                | TypeData::TemplateLiteral(_)
                | TypeData::ReadonlyType(_)
                | TypeData::StringIntrinsic { .. }
                | TypeData::ThisType // Context-dependent polymorphic type
                                     // Note: Lazy and Application are REMOVED (Task #37)
                                     // They are now handled by the Canonicalizer (Task #32)
        )
    }

    /// Evaluate an intersection type by recursively evaluating members and re-interning.
    /// This enables "deferred reduction" where intersections containing meta-types
    /// (e.g., `string & T[K]`) are reduced after the meta-types are evaluated.
    ///
    /// Example: `string & T[K]` where `T[K]` evaluates to `number` will become
    /// `string & number`, which then reduces to `never` via the interner's normalization.
    fn evaluate_intersection(&mut self, list_id: TypeListId) -> TypeId {
        let members = self.interner.type_list(list_id);
        let mut evaluated_members = Vec::with_capacity(members.len());

        for &member in members.iter() {
            evaluated_members.push(self.evaluate(member));
        }

        // Deep structural simplification using SubtypeChecker
        self.simplify_intersection_members(&mut evaluated_members);

        self.interner.intersection(evaluated_members)
    }

    /// Evaluate a union type by recursively evaluating members and re-interning.
    /// This enables "deferred reduction" where unions containing meta-types
    /// (e.g., `string | T[K]`) are reduced after the meta-types are evaluated.
    ///
    /// Example: `string | T[K]` where `T[K]` evaluates to `string` will become
    /// `string | string`, which then reduces to `string` via the interner's normalization.
    fn evaluate_union(&mut self, list_id: TypeListId) -> TypeId {
        let members = self.interner.type_list(list_id);
        let mut evaluated_members = Vec::with_capacity(members.len());

        for &member in members.iter() {
            evaluated_members.push(self.evaluate(member));
        }

        // Deep structural simplification using SubtypeChecker
        self.simplify_union_members(&mut evaluated_members);

        self.interner.union(evaluated_members)
    }

    /// Simplify union members by removing redundant types using deep subtype checks.
    /// If A <: B, then A | B = B (A is redundant in the union).
    ///
    /// This uses `SubtypeChecker` with `bypass_evaluation=true` to prevent infinite
    /// recursion, since `TypeEvaluator` has already evaluated all members.
    ///
    /// Performance: O(N²) where N is the number of members. We skip simplification
    /// if the union has more than 25 members to avoid excessive computation.
    ///
    /// ## Strategy
    ///
    /// 1. **Early exit for large unions** (>25 members) to avoid O(N²) explosion
    /// 2. **Skip complex types** that require full resolution:
    ///    - `TypeParameter`, Infer, Conditional, Mapped, `IndexAccess`, `KeyOf`, `TypeQuery`
    ///    - `TemplateLiteral`, `ReadonlyType`, String manipulation types
    ///    - Note: Lazy and Application are NOW safe (Task #37: handled by Canonicalizer)
    /// 3. **Fast-path for any/unknown**: If any member is any, entire union becomes any
    /// 4. **Identity check**: O(1) structural identity via `SubtypeChecker` (Task #36 fast-path)
    /// 5. **Depth limit**: `MAX_SUBTYPE_DEPTH` enables deep recursive type simplification (Task #37)
    ///
    /// ## Example Reductions
    ///
    /// - `"a" | string` → `string` (literal absorbed by primitive)
    /// - `number | 1 | 2` → `number` (literals absorbed by primitive)
    /// - `{ a: string } | { a: string; b: number }` → `{ a: string; b: number }`
    fn simplify_union_members(&mut self, members: &mut Vec<TypeId>) {
        // Union-specific early exits
        if members.iter().any(|&id| id.is_unknown()) {
            return;
        }
        // Skip if all members are identity-comparable — they're disjoint, so the O(n²) loop
        // would find nothing. The interner's reduce_union_subtypes handles shallow cases.
        if members
            .iter()
            .all(|&id| self.interner.is_identity_comparable_type(id))
        {
            return;
        }
        // In a union, A <: B means A is redundant (B subsumes it).
        // E.g. `"a" | string` => "a" is redundant, result: `string`
        self.remove_redundant_members(members, SubtypeDirection::SourceSubsumedByOther);
    }

    /// Simplify intersection members by removing redundant types using deep subtype checks.
    /// If A <: B, then A & B = A (B is redundant in the intersection).
    ///
    /// ## Example Reductions
    ///
    /// - `{ a: string } & { a: string; b: number }` → `{ a: string; b: number }`
    /// - `{ readonly a: string } & { a: string }` → `{ readonly a: string }`
    /// - `number & 1` → `1` (literal is more specific)
    fn simplify_intersection_members(&mut self, members: &mut Vec<TypeId>) {
        // In an intersection, A <: B means B is redundant (A is more specific).
        // We check if other members are subtypes of the candidate to remove the supertype.
        self.remove_redundant_members(members, SubtypeDirection::OtherSubsumedBySource);
    }

    /// Remove redundant members from a type list using subtype checks.
    ///
    /// This is the shared O(n²) core for both union and intersection simplification.
    /// The `direction` parameter controls which subtype relationship makes a member
    /// redundant:
    /// - `SourceSubsumedByOther`: member[i] <: member[j] → i is redundant (union semantics)
    /// - `OtherSubsumedBySource`: member[j] <: member[i] → i is redundant (intersection semantics)
    ///
    /// Common early exits (size guards, `any` check, complex-type check) are applied here.
    fn remove_redundant_members(&mut self, members: &mut Vec<TypeId>, direction: SubtypeDirection) {
        // Performance guard: skip small or very large type lists
        const MAX_SIMPLIFICATION_SIZE: usize = 25;
        if members.len() < 2 || members.len() > MAX_SIMPLIFICATION_SIZE {
            return;
        }

        if members.iter().any(|&id| id.is_any()) {
            return;
        }

        if members.iter().any(|&id| self.is_complex_type(id)) {
            return;
        }

        use crate::relations::subtype::{MAX_SUBTYPE_DEPTH, SubtypeChecker};
        let mut checker = SubtypeChecker::with_resolver(self.interner, self.resolver);
        checker.bypass_evaluation = true;
        checker.max_depth = MAX_SUBTYPE_DEPTH;
        checker.no_unchecked_indexed_access = self.no_unchecked_indexed_access;

        let mut i = 0;
        while i < members.len() {
            let mut redundant = false;
            for j in 0..members.len() {
                if i == j {
                    continue;
                }
                if members[i] == members[j] {
                    continue;
                }

                let is_subtype = match direction {
                    SubtypeDirection::SourceSubsumedByOther => {
                        checker.is_subtype_of(members[i], members[j])
                    }
                    SubtypeDirection::OtherSubsumedBySource => {
                        checker.is_subtype_of(members[j], members[i])
                    }
                };
                if is_subtype {
                    redundant = true;
                    break;
                }
            }
            if redundant {
                members.remove(i);
            } else {
                i += 1;
            }
        }
    }

    // =========================================================================
    // Visitor Pattern Implementation (North Star Rule 2)
    // =========================================================================

    /// Visit a `TypeData` and return its evaluated form.
    ///
    /// This is the visitor dispatch method that routes to specific visit_* methods.
    /// The `visiting.remove()` and `cache.insert()` are handled in `evaluate()` for symmetry.
    fn visit_type_key(&mut self, type_id: TypeId, key: &TypeData) -> TypeId {
        match key {
            TypeData::Conditional(cond_id) => self.visit_conditional(*cond_id),
            TypeData::IndexAccess(obj, idx) => self.visit_index_access(*obj, *idx),
            TypeData::Mapped(mapped_id) => self.visit_mapped(*mapped_id),
            TypeData::KeyOf(operand) => self.visit_keyof(*operand),
            TypeData::TypeQuery(symbol) => self.visit_type_query(symbol.0, type_id),
            TypeData::Application(app_id) => self.visit_application(*app_id),
            TypeData::TemplateLiteral(spans) => self.visit_template_literal(*spans),
            TypeData::Lazy(def_id) => self.visit_lazy(*def_id, type_id),
            TypeData::StringIntrinsic { kind, type_arg } => {
                self.visit_string_intrinsic(*kind, *type_arg)
            }
            TypeData::Intersection(list_id) => self.visit_intersection(*list_id),
            TypeData::Union(list_id) => self.visit_union(*list_id),
            TypeData::NoInfer(inner) => {
                // NoInfer<T> evaluates to T (strip wrapper, evaluate inner)
                self.evaluate(*inner)
            }
            // All other types pass through unchanged (default behavior)
            _ => type_id,
        }
    }

    /// Visit a conditional type: T extends U ? X : Y
    fn visit_conditional(&mut self, cond_id: ConditionalTypeId) -> TypeId {
        let cond = self.interner.conditional_type(cond_id);
        self.evaluate_conditional(cond.as_ref())
    }

    /// Visit an index access type: T[K]
    fn visit_index_access(&mut self, object_type: TypeId, index_type: TypeId) -> TypeId {
        self.evaluate_index_access(object_type, index_type)
    }

    /// Visit a mapped type: { [K in Keys]: V }
    fn visit_mapped(&mut self, mapped_id: MappedTypeId) -> TypeId {
        let mapped = self.interner.mapped_type(mapped_id);
        self.evaluate_mapped(mapped.as_ref())
    }

    /// Visit a keyof type: keyof T
    fn visit_keyof(&mut self, operand: TypeId) -> TypeId {
        self.evaluate_keyof(operand)
    }

    /// Visit a type query: typeof expr
    ///
    /// `TypeQuery` represents `typeof X` which must resolve to the VALUE-space type
    /// (constructor type for classes). We use `resolve_ref` which returns the
    /// constructor type stored under `SymbolRef`, NOT `resolve_lazy` which returns
    /// the instance type for classes. This distinction is critical: `typeof A`
    /// for a class A should give the constructor type (with static members and
    /// construct signatures), not the instance type.
    fn visit_type_query(&mut self, symbol_ref: u32, original_type_id: TypeId) -> TypeId {
        use crate::types::SymbolRef;
        let symbol = SymbolRef(symbol_ref);

        // Prefer resolve_ref which returns the VALUE type (constructor for classes).
        // This is correct for TypeQuery (typeof) which is a value-space query.
        if let Some(resolved) = self.resolver.resolve_ref(symbol, self.interner) {
            return resolved;
        }

        // Fallback: try DefId-based resolution if no SymbolRef mapping exists
        if let Some(def_id) = self.resolver.symbol_to_def_id(symbol)
            && let Some(resolved) = self.resolver.resolve_lazy(def_id, self.interner)
        {
            return resolved;
        }

        original_type_id
    }

    /// Visit a generic type application: Base<Args>
    fn visit_application(&mut self, app_id: TypeApplicationId) -> TypeId {
        self.evaluate_application(app_id)
    }

    /// Visit a template literal type: `hello${T}world`
    fn visit_template_literal(&mut self, spans: TemplateLiteralId) -> TypeId {
        self.evaluate_template_literal(spans)
    }

    /// Visit a lazy type reference: Lazy(DefId)
    fn visit_lazy(&mut self, def_id: DefId, original_type_id: TypeId) -> TypeId {
        if let Some(resolved) = self.resolver.resolve_lazy(def_id, self.interner) {
            // Re-evaluate the resolved type in case it needs further evaluation
            self.evaluate(resolved)
        } else {
            original_type_id
        }
    }

    /// Visit a string manipulation intrinsic type: Uppercase<T>, Lowercase<T>, etc.
    fn visit_string_intrinsic(&mut self, kind: StringIntrinsicKind, type_arg: TypeId) -> TypeId {
        self.evaluate_string_intrinsic(kind, type_arg)
    }

    /// Visit an intersection type: A & B & C
    fn visit_intersection(&mut self, list_id: TypeListId) -> TypeId {
        self.evaluate_intersection(list_id)
    }

    /// Visit a union type: A | B | C
    fn visit_union(&mut self, list_id: TypeListId) -> TypeId {
        self.evaluate_union(list_id)
    }
}

/// Convenience function for evaluating conditional types
pub fn evaluate_conditional(interner: &dyn TypeDatabase, cond: &ConditionalType) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.evaluate_conditional(cond)
}

/// Convenience function for evaluating index access types
pub fn evaluate_index_access(
    interner: &dyn TypeDatabase,
    object_type: TypeId,
    index_type: TypeId,
) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.evaluate_index_access(object_type, index_type)
}

/// Convenience function for evaluating index access types with options.
pub fn evaluate_index_access_with_options(
    interner: &dyn TypeDatabase,
    object_type: TypeId,
    index_type: TypeId,
    no_unchecked_indexed_access: bool,
) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.set_no_unchecked_indexed_access(no_unchecked_indexed_access);
    evaluator.evaluate_index_access(object_type, index_type)
}

/// Convenience function for full type evaluation
pub fn evaluate_type(interner: &dyn TypeDatabase, type_id: TypeId) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.evaluate(type_id)
}

/// Convenience function for evaluating mapped types
pub fn evaluate_mapped(interner: &dyn TypeDatabase, mapped: &MappedType) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.evaluate_mapped(mapped)
}

/// Convenience function for evaluating keyof types
pub fn evaluate_keyof(interner: &dyn TypeDatabase, operand: TypeId) -> TypeId {
    let mut evaluator = TypeEvaluator::new(interner);
    evaluator.evaluate_keyof(operand)
}

// Re-enabled evaluate tests - verifying API compatibility
#[cfg(test)]
#[path = "../../tests/evaluate_tests.rs"]
mod tests;