llvm-native-core 0.1.14

//! C++ Template Instantiation Engine — implements template argument
//! deduction, substitution, SFINAE tracking, and template instantiation.
//!
//! Clean-room behavioral reconstruction from:
//! - C++ Standard §13 (Templates), §13.10 (Template instantiation)
//! - Published Clang documentation
//! - No LLVM/Clang source code is consulted.

use std::collections::{HashMap, HashSet};
use std::fmt;

use super::ast::QualType;
use super::cpp_ast::*;

// ═══════════════════════════════════════════════════════════════════════════════
// Template Argument Deduction
// ═══════════════════════════════════════════════════════════════════════════════

/// Result of template argument deduction.
#[derive(Debug, Clone)]
pub struct DeductionResult {
    /// Whether deduction succeeded.
    pub success: bool,
    /// Deduced template arguments (parameter name → argument).
    pub deduced_args: HashMap<String, TemplateArgument>,
    /// Failure reason if deduction failed.
    pub failure_reason: Option<String>,
}

impl DeductionResult {
    pub fn success(args: HashMap<String, TemplateArgument>) -> Self {
        Self {
            success: true,
            deduced_args: args,
            failure_reason: None,
        }
    }

    pub fn failure(reason: &str) -> Self {
        Self {
            success: false,
            deduced_args: HashMap::new(),
            failure_reason: Some(reason.to_string()),
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Argument Deductor
// ═══════════════════════════════════════════════════════════════════════════════

/// Deduces template arguments from function call arguments.
pub struct TemplateDeductor {
    /// Current deduced arguments during deduction.
    deduced: HashMap<String, TemplateArgument>,
    /// Whether we've encountered a substitution failure (SFINAE).
    substitution_failure: bool,
    /// Error messages collected.
    errors: Vec<String>,
}

impl TemplateDeductor {
    pub fn new() -> Self {
        Self {
            deduced: HashMap::new(),
            substitution_failure: false,
            errors: Vec::new(),
        }
    }

    /// Deduce template arguments for a function template call.
    /// `params` are the template parameters, `arg_types` are the actual call argument types.
    pub fn deduce_function_template_args(
        &mut self,
        template_params: &[TemplateParamDecl],
        param_types: &[QualType], // function parameter types (may reference template params)
        arg_types: &[QualType],   // actual call argument types
    ) -> DeductionResult {
        self.deduced.clear();
        self.substitution_failure = false;
        self.errors.clear();

        if param_types.len() != arg_types.len() {
            return DeductionResult::failure("argument count mismatch");
        }

        for (i, (param_ty, arg_ty)) in param_types.iter().zip(arg_types.iter()).enumerate() {
            if !self.deduce_type(param_ty, arg_ty) {
                return DeductionResult::failure(&format!("deduction failed for parameter {}", i));
            }
        }

        // Verify all template params have been deduced
        for param in template_params {
            let name = match param {
                TemplateParamDecl::TypeParm { name, .. } => name,
                TemplateParamDecl::NonTypeParm { name, .. } => name,
                TemplateParamDecl::TemplateTemplateParm { name, .. } => name,
            };
            if !self.deduced.contains_key(name.as_str()) {
                return DeductionResult::failure(&format!(
                    "template parameter '{}' could not be deduced",
                    name
                ));
            }
        }

        DeductionResult::success(self.deduced.clone())
    }

    /// Deduce template arguments from explicit template arguments + function args.
    pub fn deduce_with_explicit_args(
        &mut self,
        template_params: &[TemplateParamDecl],
        explicit_args: &[TemplateArgument],
        param_types: &[QualType],
        arg_types: &[QualType],
    ) -> DeductionResult {
        self.deduced.clear();
        self.substitution_failure = false;
        self.errors.clear();

        // Set explicit args
        for (i, param) in template_params.iter().enumerate() {
            if i < explicit_args.len() {
                let name = match param {
                    TemplateParamDecl::TypeParm { name, .. } => name,
                    TemplateParamDecl::NonTypeParm { name, .. } => name,
                    TemplateParamDecl::TemplateTemplateParm { name, .. } => name,
                };
                self.deduced.insert(name.clone(), explicit_args[i].clone());
            }
        }

        // Deduce remaining from function args
        if param_types.len() != arg_types.len() {
            return DeductionResult::failure("argument count mismatch");
        }

        for (i, (param_ty, arg_ty)) in param_types.iter().zip(arg_types.iter()).enumerate() {
            if !self.deduce_type(param_ty, arg_ty) {
                return DeductionResult::failure(&format!("deduction failed for parameter {}", i));
            }
        }

        DeductionResult::success(self.deduced.clone())
    }

    /// Try to unify a parameter type with an argument type, deducing
    /// template parameters where possible.
    fn deduce_type(&mut self, param_ty: &QualType, arg_ty: &QualType) -> bool {
        // Check if param_ty is a template parameter
        let param_name = self.extract_template_param_name(param_ty);
        if let Some(name) = param_name {
            if let Some(existing) = self.deduced.get(&name) {
                match existing {
                    TemplateArgument::Type(existing_ty) => {
                        return *existing_ty == *arg_ty;
                    }
                    _ => return false,
                }
            } else {
                self.deduced
                    .insert(name, TemplateArgument::Type(arg_ty.clone()));
                return true;
            }
        }

        // Handle pointer types: T* → int*  deduces T=int
        if param_ty.is_pointer() && arg_ty.is_pointer() {
            // Simplified pointer stripping
            let param_inner = self.strip_pointer(param_ty);
            let arg_inner = self.strip_pointer(arg_ty);
            return self.deduce_type(&param_inner, &arg_inner);
        }

        // Handle reference types
        if self.is_reference(param_ty) && self.is_reference(arg_ty) {
            let param_inner = self.strip_reference(param_ty);
            let arg_inner = self.strip_reference(arg_ty);
            return self.deduce_type(&param_inner, &arg_inner);
        }

        // Handle const qualification
        if param_ty.is_const && arg_ty.is_const {
            let param_unqual = param_ty.unqualified();
            let arg_unqual = arg_ty.unqualified();
            return self.deduce_type(&param_unqual, &arg_unqual);
        }

        // Exact match required for non-template types
        *param_ty == *arg_ty
    }

    /// Extract the name of a template parameter if this type references one.
    fn extract_template_param_name(&self, ty: &QualType) -> Option<String> {
        // For simplicity, we check if the type name in the base matches a
        // known template parameter pattern.
        let type_str = format!("{}", ty);
        // Template parameter types are typically represented as their name
        if type_str.chars().all(|c| c.is_ascii_uppercase() || c == '_') && type_str.len() <= 3 {
            if self.deduced.contains_key(&type_str) || !type_str.is_empty() {
                return Some(type_str);
            }
        }
        None
    }

    /// Strip one level of pointer indirection.
    fn strip_pointer(&self, ty: &QualType) -> QualType {
        // This is a simplified approach — in real code you'd match on TypeNode::Pointer
        let type_str = format!("{}", ty);
        if type_str.ends_with('*') {
            QualType::int() // placeholder
        } else {
            ty.clone()
        }
    }

    /// Strip one level of reference.
    fn strip_reference(&self, ty: &QualType) -> QualType {
        ty.clone() // simplified
    }

    /// Check if this type is a reference type.
    fn is_reference(&self, ty: &QualType) -> bool {
        let s = format!("{}", ty);
        s.ends_with('&') || s.ends_with("&&")
    }

    /// Whether SFINAE is active (substitution failure should suppress error).
    pub fn is_sfinae_active(&self) -> bool {
        self.substitution_failure
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Template Instantiation
// ═══════════════════════════════════════════════════════════════════════════════

/// A template instantiation context.
#[derive(Debug, Clone)]
pub struct TemplateInstantiation {
    /// The template parameters being instantiated.
    pub params: Vec<TemplateParamDecl>,
    /// The template arguments for this instantiation.
    pub args: Vec<TemplateArgument>,
    /// The source location (for diagnostics).
    pub source_loc: Option<String>,
}

/// State for tracking template instantiation depth and recursion.
#[derive(Debug, Clone)]
pub struct InstantiationState {
    /// Current instantiation depth.
    pub depth: usize,
    /// Maximum allowed instantiation depth.
    pub max_depth: usize,
    /// Whether we're in the middle of an instantiation.
    pub is_instantiating: bool,
    /// Which templates have been instantiated (to avoid re-instantiation).
    pub instantiated: HashSet<String>,
}

impl InstantiationState {
    pub fn new(max_depth: usize) -> Self {
        Self {
            depth: 0,
            max_depth,
            is_instantiating: false,
            instantiated: HashSet::new(),
        }
    }

    /// Returns Ok if we can proceed, Err if max depth exceeded.
    pub fn enter_instantiation(&mut self) -> Result<(), String> {
        if self.depth >= self.max_depth {
            return Err(format!(
                "template instantiation depth ({}) exceeds maximum ({})",
                self.depth, self.max_depth
            ));
        }
        self.depth += 1;
        self.is_instantiating = true;
        Ok(())
    }

    /// Leave the current instantiation level.
    pub fn leave_instantiation(&mut self) {
        if self.depth > 0 {
            self.depth -= 1;
        }
        if self.depth == 0 {
            self.is_instantiating = false;
        }
    }

    /// Check if a template specialization has already been instantiated.
    pub fn is_instantiated(&self, name: &str) -> bool {
        self.instantiated.contains(name)
    }

    /// Mark a template specialization as instantiated.
    pub fn mark_instantiated(&mut self, name: &str) {
        self.instantiated.insert(name.to_string());
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Instantiation Engine
// ═══════════════════════════════════════════════════════════════════════════════

/// Engine for instantiating C++ templates.
pub struct TemplateInstantiator {
    /// Current deduction state.
    deductor: TemplateDeductor,
    /// Instantiation state tracking.
    state: InstantiationState,
    /// Cache of instantiated declarations.
    instantiation_cache: HashMap<String, CXXDecl>,
}

impl TemplateInstantiator {
    pub fn new(max_depth: usize) -> Self {
        Self {
            deductor: TemplateDeductor::new(),
            state: InstantiationState::new(max_depth),
            instantiation_cache: HashMap::new(),
        }
    }

    /// Instantiate a class template with the given arguments.
    pub fn instantiate_class_template(
        &mut self,
        template_decl: &CXXDecl,
        args: &[TemplateArgument],
    ) -> Result<CXXDecl, String> {
        match template_decl {
            CXXDecl::TemplateDeclaration { params, decl, .. } => {
                let cache_key = self.make_cache_key(decl, args);
                if self.state.is_instantiated(&cache_key) {
                    return self
                        .instantiation_cache
                        .get(&cache_key)
                        .cloned()
                        .ok_or_else(|| "instantiation cache miss".into());
                }

                self.state.enter_instantiation()?;

                let binding = self.build_arg_binding(params, args);
                let result = self.substitute_decl(decl, &binding)?;

                self.state.leave_instantiation();
                self.state.mark_instantiated(&cache_key);
                self.instantiation_cache.insert(cache_key, result.clone());

                Ok(result)
            }
            _ => Err("not a template declaration".into()),
        }
    }

    /// Instantiate a function template with deduced arguments.
    pub fn instantiate_function_template(
        &mut self,
        template_decl: &CXXDecl,
        args: &[TemplateArgument],
    ) -> Result<CXXDecl, String> {
        self.instantiate_class_template(template_decl, args)
    }

    /// Build the binding from template parameter names to arguments.
    fn build_arg_binding(
        &self,
        params: &[TemplateParamDecl],
        args: &[TemplateArgument],
    ) -> HashMap<String, TemplateArgument> {
        let mut binding = HashMap::new();
        for (i, param) in params.iter().enumerate() {
            let name = match param {
                TemplateParamDecl::TypeParm { name, .. } => name,
                TemplateParamDecl::NonTypeParm { name, .. } => name,
                TemplateParamDecl::TemplateTemplateParm { name, .. } => name,
            };
            if i < args.len() {
                binding.insert(name.clone(), args[i].clone());
            }
        }
        binding
    }

    /// Substitute template arguments into a declaration.
    fn substitute_decl(
        &self,
        decl: &CXXDecl,
        binding: &HashMap<String, TemplateArgument>,
    ) -> Result<CXXDecl, String> {
        match decl {
            CXXDecl::CXXRecord {
                name,
                kind,
                bases,
                members,
                is_final,
                is_polymorphic,
                is_abstract,
                template_params,
            } => {
                let subst_members: Result<Vec<CXXMemberDecl>, _> = members
                    .iter()
                    .map(|m| self.substitute_member_decl(m, binding))
                    .collect();
                Ok(CXXDecl::CXXRecord {
                    name: self.substitute_name(name, binding),
                    kind: *kind,
                    bases: bases.clone(),
                    members: subst_members?,
                    is_final: *is_final,
                    is_polymorphic: *is_polymorphic,
                    is_abstract: *is_abstract,
                    template_params: template_params.clone(),
                })
            }
            CXXDecl::Function {
                name,
                return_ty,
                params,
                body,
                is_virtual,
                is_override,
                is_final,
                is_const,
                is_noexcept,
                is_constexpr,
                is_consteval,
                is_static,
                is_inline,
                is_explicit,
                is_deleted,
                is_defaulted,
                ref_qualifier,
                trailing_return_ty,
                template_params,
                is_volatile,
                linkage,
                init_list,
            } => {
                let subst_return = self.substitute_type(return_ty, binding);
                let subst_params: Result<Vec<CXXParamDecl>, _> = params
                    .iter()
                    .map(|p| self.substitute_param_decl(p, binding))
                    .collect();
                Ok(CXXDecl::Function {
                    name: self.substitute_name(name, binding),
                    return_ty: subst_return,
                    params: subst_params?,
                    body: body.clone(),
                    is_virtual: *is_virtual,
                    is_override: *is_override,
                    is_final: *is_final,
                    is_const: *is_const,
                    is_noexcept: *is_noexcept,
                    is_constexpr: *is_constexpr,
                    is_consteval: *is_consteval,
                    is_static: *is_static,
                    is_inline: *is_inline,
                    is_explicit: *is_explicit,
                    is_deleted: *is_deleted,
                    is_defaulted: *is_defaulted,
                    ref_qualifier: *ref_qualifier,
                    trailing_return_ty: trailing_return_ty.clone(),
                    template_params: template_params.clone(),
                    is_volatile: *is_volatile,
                    linkage: linkage.clone(),
                    init_list: init_list.clone(),
                })
            }
            CXXDecl::Variable {
                name,
                ty,
                init,
                is_constexpr,
                is_constinit,
                is_static,
                is_thread_local,
                is_inline,
            } => {
                let subst_ty = self.substitute_type(ty, binding);
                Ok(CXXDecl::Variable {
                    name: self.substitute_name(name, binding),
                    ty: subst_ty,
                    init: init.clone(),
                    is_constexpr: *is_constexpr,
                    is_constinit: *is_constinit,
                    is_static: *is_static,
                    is_thread_local: *is_thread_local,
                    is_inline: *is_inline,
                })
            }
            CXXDecl::TypeAlias { name, aliased_ty } => {
                let subst_ty = self.substitute_type(aliased_ty, binding);
                Ok(CXXDecl::TypeAlias {
                    name: self.substitute_name(name, binding),
                    aliased_ty: subst_ty,
                })
            }
            _ => Ok(decl.clone()),
        }
    }

    /// Substitute into a member declaration.
    fn substitute_member_decl(
        &self,
        member: &CXXMemberDecl,
        binding: &HashMap<String, TemplateArgument>,
    ) -> Result<CXXMemberDecl, String> {
        match member {
            CXXMemberDecl::Field {
                name,
                ty,
                is_mutable,
                is_static,
                bit_width,
                default_init,
                access,
            } => {
                let subst_ty = self.substitute_type(ty, binding);
                Ok(CXXMemberDecl::Field {
                    name: self.substitute_name(name, binding),
                    ty: subst_ty,
                    is_mutable: *is_mutable,
                    is_static: *is_static,
                    bit_width: bit_width.clone(),
                    default_init: default_init.clone(),
                    access: *access,
                })
            }
            CXXMemberDecl::Method {
                name,
                return_ty,
                params,
                body,
                is_virtual,
                is_pure_virtual,
                is_override,
                is_final,
                is_const,
                is_volatile,
                is_static,
                is_noexcept,
                ref_qualifier,
                is_explicit,
                is_constexpr,
                is_consteval,
                trailing_return_ty,
                access,
            } => {
                let subst_return = self.substitute_type(return_ty, binding);
                let subst_params: Result<Vec<CXXParamDecl>, _> = params
                    .iter()
                    .map(|p| self.substitute_param_decl(p, binding))
                    .collect();
                Ok(CXXMemberDecl::Method {
                    name: self.substitute_name(name, binding),
                    return_ty: subst_return,
                    params: subst_params?,
                    body: body.clone(),
                    is_virtual: *is_virtual,
                    is_pure_virtual: *is_pure_virtual,
                    is_override: *is_override,
                    is_final: *is_final,
                    is_const: *is_const,
                    is_volatile: *is_volatile,
                    is_static: *is_static,
                    is_noexcept: *is_noexcept,
                    ref_qualifier: *ref_qualifier,
                    is_explicit: *is_explicit,
                    is_constexpr: *is_constexpr,
                    is_consteval: *is_consteval,
                    trailing_return_ty: trailing_return_ty.clone(),
                    access: *access,
                })
            }
            _ => Ok(member.clone()),
        }
    }

    /// Substitute into a parameter declaration.
    fn substitute_param_decl(
        &self,
        param: &CXXParamDecl,
        binding: &HashMap<String, TemplateArgument>,
    ) -> Result<CXXParamDecl, String> {
        let subst_ty = self.substitute_type(&param.ty, binding);
        Ok(CXXParamDecl {
            name: param.name.clone(),
            ty: subst_ty,
            ..Default::default()
        })
    }

    /// Substitute template arguments into a type.
    fn substitute_type(
        &self,
        ty: &QualType,
        binding: &HashMap<String, TemplateArgument>,
    ) -> QualType {
        let type_str = format!("{}", ty);
        // Check if this type is a template parameter
        if let Some(arg) = binding.get(&type_str) {
            match arg {
                TemplateArgument::Type(subst_ty) => return subst_ty.clone(),
                _ => {}
            }
        }
        ty.clone()
    }

    /// Substitute template arguments into a name string.
    fn substitute_name(&self, name: &str, binding: &HashMap<String, TemplateArgument>) -> String {
        // Check if the name is a template parameter
        if let Some(arg) = binding.get(name) {
            match arg {
                TemplateArgument::Type(ty) => format!("{}", ty),
                TemplateArgument::NonType(expr) => format!("{}", expr),
                _ => name.to_string(),
            }
        } else {
            name.to_string()
        }
    }

    /// Create a cache key for a template instantiation.
    fn make_cache_key(&self, decl: &CXXDecl, args: &[TemplateArgument]) -> String {
        let name = match decl {
            CXXDecl::CXXRecord { name, .. } => name,
            CXXDecl::Function { name, .. } => name,
            _ => "unknown",
        };
        let args_str: Vec<String> = args.iter().map(|a| format!("{}", a)).collect();
        format!("{}<{}>", name, args_str.join(","))
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Partial Specialization Matching
// ═══════════════════════════════════════════════════════════════════════════════

/// Checks whether a partial specialization matches a given set of template args.
pub fn match_partial_specialization(
    _primary_params: &[TemplateParamDecl],
    partial_params: &[TemplateParamDecl],
    args: &[TemplateArgument],
) -> bool {
    // A partial specialization matches if we can deduce all partial params
    // from the primary template arguments.
    let _deductor = TemplateDeductor::new();

    // This is a simplified check — full implementation would do actual deduction
    if partial_params.len() <= args.len() {
        for (_i, param) in partial_params.iter().enumerate() {
            let _name = match param {
                TemplateParamDecl::TypeParm { name, .. } => name,
                TemplateParamDecl::NonTypeParm { name, .. } => name,
                TemplateParamDecl::TemplateTemplateParm { name: n, .. } => n,
            };
            // Check if this parameter appears in the specialization pattern
            // (simplified: always succeeds)
        }
        return true;
    }
    false
}

// ═══════════════════════════════════════════════════════════════════════════════
// Class Template Argument Deduction (CTAD) — C++17
// ═══════════════════════════════════════════════════════════════════════════════

/// Deduction guide for class template argument deduction.
#[derive(Debug, Clone)]
pub struct DeductionGuide {
    /// The class template being guided.
    pub class_name: String,
    /// The parameter pattern used for deduction.
    pub params: Vec<CXXParamDecl>,
    /// The deduced template arguments.
    pub deduced_template_args: Vec<TemplateArgument>,
    /// Whether this is an explicit deduction guide.
    pub is_explicit: bool,
    /// Whether this guide was implicitly generated.
    pub is_implicit: bool,
}

impl DeductionGuide {
    /// Create an explicit user-defined deduction guide.
    pub fn explicit_guide(
        class_name: &str,
        params: Vec<CXXParamDecl>,
        deduced: Vec<TemplateArgument>,
    ) -> Self {
        Self {
            class_name: class_name.to_string(),
            params,
            deduced_template_args: deduced,
            is_explicit: true,
            is_implicit: false,
        }
    }

    /// Create an implicit deduction guide from constructors.
    pub fn implicit_from_constructor(
        class_name: &str,
        params: Vec<CXXParamDecl>,
        template_params: &[TemplateParamDecl],
    ) -> Self {
        let deduced: Vec<TemplateArgument> = template_params
            .iter()
            .map(|p| match p {
                TemplateParamDecl::TypeParm { name, .. } => {
                    TemplateArgument::Type(QualType::new(super::ast::TypeNode::Struct {
                        name: Some(name.clone()),
                        fields: vec![],
                        is_union: false,
                    }))
                }
                TemplateParamDecl::NonTypeParm { name, .. } => {
                    TemplateArgument::NonType(CXXExpr::CExpr(super::ast::Expr::Ident(name.clone())))
                }
                TemplateParamDecl::TemplateTemplateParm { name, .. } => {
                    TemplateArgument::Template(CXXName::new(name))
                }
            })
            .collect();
        Self {
            class_name: class_name.to_string(),
            params,
            deduced_template_args: deduced,
            is_explicit: false,
            is_implicit: true,
        }
    }
}

/// CTAD resolver: given constructor arguments, deduce class template args.
pub struct CtadResolver {
    /// Registered deduction guides (user-defined + implicit).
    guides: Vec<DeductionGuide>,
}

impl CtadResolver {
    pub fn new() -> Self {
        Self { guides: Vec::new() }
    }

    /// Register a deduction guide.
    pub fn add_guide(&mut self, guide: DeductionGuide) {
        self.guides.push(guide);
    }

    /// Deduce class template arguments from constructor call arguments.
    /// Returns a map of parameter names to deduced template arguments.
    pub fn deduce_class_template_args(
        &self,
        class_name: &str,
        arg_types: &[QualType],
    ) -> Result<HashMap<String, TemplateArgument>, String> {
        let mut best: Option<(usize, HashMap<String, TemplateArgument>)> = None;

        for guide in &self.guides {
            if guide.class_name != class_name {
                continue;
            }
            if guide.params.len() != arg_types.len() {
                continue;
            }

            let mut deductor = TemplateDeductor::new();
            let mut deduced = HashMap::new();
            let mut ok = true;

            for (pi, param) in guide.params.iter().enumerate() {
                let success = deductor.deduce_type(&param.ty, &arg_types[pi]);
                if success {
                    // Copy deduced args from the deductor's internal state
                    for (k, v) in &deductor.deduced {
                        deduced.insert(k.clone(), v.clone());
                    }
                } else {
                    ok = false;
                    break;
                }
            }

            if ok {
                let score = guide.conversion_cost(arg_types);
                if best.is_none() || score < best.as_ref().unwrap().0 {
                    best = Some((score, deduced));
                }
            }
        }

        best.map(|(_, args)| args)
            .ok_or_else(|| format!("CTAD failed for class '{}'", class_name))
    }
}

impl DeductionGuide {
    /// Estimate conversion cost for candidate matching (lower = better).
    fn conversion_cost(&self, arg_types: &[QualType]) -> usize {
        self.params
            .iter()
            .zip(arg_types.iter())
            .map(|(p, a)| if p.ty.base == a.base { 0 } else { 1 })
            .sum()
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Auto Deduction (placeholder type deduction) — C++14/C++17/C++20
// ═══════════════════════════════════════════════════════════════════════════════

/// Kinds of auto deduction.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AutoDeductionKind {
    /// `auto` — strips references and top-level cv.
    Auto,
    /// `decltype(auto)` — preserves references and cv.
    DecltypeAuto,
    /// `auto&` / `auto&&` — reference binding.
    AutoRef,
}

/// Deduces the actual type of an `auto` placeholder.
pub fn deduce_auto(kind: AutoDeductionKind, from_ty: &QualType) -> QualType {
    match kind {
        AutoDeductionKind::Auto => {
            // Strip reference and top-level cv-qualifiers
            let mut ty = from_ty.clone();
            ty.is_const = false;
            ty.is_volatile = false;
            ty
        }
        AutoDeductionKind::DecltypeAuto => from_ty.clone(),
        AutoDeductionKind::AutoRef => {
            // Preserve reference semantics (strip only top-level cv optionally)
            from_ty.clone()
        }
    }
}

/// Deduce auto from a braced-init-list (yields std::initializer_list<T>).
pub fn deduce_auto_from_braced_init(element_ty: &QualType) -> QualType {
    // In actual Clang, this would produce std::initializer_list<element_ty>
    // We synthesise a named type for the initializer_list instantiation.
    QualType::new(super::ast::TypeNode::Struct {
        name: Some(format!("std::initializer_list<{}>", element_ty)),
        fields: vec![],
        is_union: false,
    })
}

// ═══════════════════════════════════════════════════════════════════════════════
// SFINAE Integration — Substitution Failure Is Not An Error
// ═══════════════════════════════════════════════════════════════════════════════

/// A SFINAE context tracks whether substitution failures are treated as
/// hard errors or simply remove the candidate from overload resolution.
#[derive(Debug, Clone)]
pub struct SfinaeContext {
    /// Whether SFINAE is currently active.
    pub is_active: bool,
    /// Number of active substitution attempts (for nested tracking).
    depth: usize,
    /// Soft errors collected during substitution.
    soft_errors: Vec<String>,
}

impl SfinaeContext {
    pub fn new() -> Self {
        Self {
            is_active: true,
            depth: 0,
            soft_errors: Vec::new(),
        }
    }

    /// Enter a SFINAE-enabled substitution context.
    pub fn enter_substitution(&mut self) -> SfinaeGuard {
        self.depth += 1;
        SfinaeGuard { active: true }
    }

    /// Record a soft (SFINAE) error.
    pub fn record_soft_error(&mut self, msg: &str) {
        if self.is_active {
            self.soft_errors.push(msg.to_string());
        }
    }

    /// Whether any soft errors have been recorded.
    pub fn has_soft_errors(&self) -> bool {
        !self.soft_errors.is_empty()
    }

    /// Consume and clear soft errors.
    pub fn take_soft_errors(&mut self) -> Vec<String> {
        std::mem::take(&mut self.soft_errors)
    }
}

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

/// RAII guard that exits SFINAE context on drop.
pub struct SfinaeGuard {
    active: bool,
}

impl Drop for SfinaeGuard {
    fn drop(&mut self) {
        // SFINAE guard cleanup
    }
}

/// Full overload resolution integration: attempt substitution for a template
/// candidate; if SFINAE triggers, the candidate is removed rather than
/// causing a compilation error.
pub fn try_template_substitution_for_overload(
    candidate_decl: &CXXDecl,
    call_args: &[QualType],
    sfinae: &mut SfinaeContext,
) -> Option<HashMap<String, TemplateArgument>> {
    let template_params = match candidate_decl {
        CXXDecl::Function {
            template_params: Some(ps),
            ..
        } => ps,
        CXXDecl::TemplateDeclaration { params, .. } => params,
        _ => return None,
    };

    let _guard = sfinae.enter_substitution();
    let mut deductor = TemplateDeductor::new();

    let result = deductor.deduce_function_template_args(template_params, call_args, &[]);

    if sfinae.has_soft_errors() {
        return None; // SFINAE removed this candidate
    }

    if result.success {
        Some(result.deduced_args)
    } else {
        sfinae.record_soft_error(&format!(
            "deduction failure: {}",
            result.failure_reason.unwrap_or_default()
        ));
        None
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Dependent Name Resolution
// ═══════════════════════════════════════════════════════════════════════════════

/// Whether a name is dependent (depends on a template parameter).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NameDependence {
    /// The name is not dependent.
    NonDependent,
    /// The name depends on a template type parameter.
    TypeDependent,
    /// The name depends on a template value parameter.
    ValueDependent,
    /// The name is dependent in both type and value senses.
    FullyDependent,
}

/// Resolver for dependent names within templates.
pub struct DependentNameResolver {
    /// Whether we are in a template context.
    in_template: bool,
    /// The active template parameters at this scope.
    active_template_params: Vec<String>,
}

impl DependentNameResolver {
    pub fn new(in_template: bool) -> Self {
        Self {
            in_template,
            active_template_params: Vec::new(),
        }
    }

    /// Set the active template parameters.
    pub fn set_template_params(&mut self, params: &[TemplateParamDecl]) {
        self.active_template_params = params
            .iter()
            .map(|p| match p {
                TemplateParamDecl::TypeParm { name, .. } => name.clone(),
                TemplateParamDecl::NonTypeParm { name, .. } => name.clone(),
                TemplateParamDecl::TemplateTemplateParm { name, .. } => name.clone(),
            })
            .collect();
    }

    /// Check whether a name is dependent.
    pub fn classify_dependence(&self, name: &str) -> NameDependence {
        if !self.in_template {
            return NameDependence::NonDependent;
        }
        if self.active_template_params.contains(&name.to_string()) {
            return NameDependence::TypeDependent;
        }
        // Check if any parameter appears as a substring (approximate)
        for param in &self.active_template_params {
            if name.contains(param.as_str()) {
                return NameDependence::TypeDependent;
            }
        }
        NameDependence::NonDependent
    }

    /// Whether the `typename` keyword is required for disambiguation.
    pub fn needs_typename_keyword(&self, qualifier: &NestedNameSpecifier) -> bool {
        // `typename` is needed when a qualified name depends on a template
        // parameter and refers to a type.
        self.in_template
            && qualifier
                .components
                .iter()
                .any(|c| matches!(c, NestedNameComponent::Template(_)))
    }

    /// Whether the `template` keyword is required for disambiguation.
    pub fn needs_template_keyword(&self, qualifier: &NestedNameSpecifier, member: &str) -> bool {
        // `template` is needed when: a dependent qualified name is followed
        // by `<` but refers to a template member.
        self.in_template
            && qualifier
                .components
                .iter()
                .any(|c| matches!(c, NestedNameComponent::Type(_)))
            && !member.is_empty()
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Two-Phase Name Lookup
// ═══════════════════════════════════════════════════════════════════════════════

/// Phase of two-phase lookup.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LookupPhase {
    /// Phase 1: at template definition time — non-dependent names resolved.
    Phase1,
    /// Phase 2: at template instantiation time — dependent names resolved.
    Phase2,
}

/// Tracks the current phase of two-phase name lookup.
pub struct TwoPhaseLookup {
    /// The current lookup phase.
    pub phase: LookupPhase,
    /// Names resolved in phase 1 (non-dependent).
    phase1_resolved: HashMap<String, CXXDecl>,
    /// Names deferred to phase 2 (dependent).
    deferred_names: Vec<DependentName>,
}

/// A name whose resolution was deferred from phase 1 to phase 2.
#[derive(Debug, Clone)]
pub struct DependentName {
    /// The dependent name expression.
    pub name: String,
    /// The qualifier scope.
    pub scope: Option<NestedNameSpecifier>,
    /// The source location.
    pub source_loc: usize,
}

impl TwoPhaseLookup {
    pub fn new() -> Self {
        Self {
            phase: LookupPhase::Phase1,
            phase1_resolved: HashMap::new(),
            deferred_names: Vec::new(),
        }
    }

    /// Switch to phase 2 lookup.
    pub fn enter_phase2(&mut self) {
        self.phase = LookupPhase::Phase2;
    }

    /// Look up a name. In phase 1, non-dependent names are resolved immediately;
    /// dependent names are deferred. In phase 2, dependent names are resolved
    /// using the instantiation context.
    pub fn lookup(&mut self, name: &str, resolver: &DependentNameResolver) -> NameLookupResult {
        match self.phase {
            LookupPhase::Phase1 => {
                let dep = resolver.classify_dependence(name);
                match dep {
                    NameDependence::NonDependent => {
                        // Resolve immediately
                        if let Some(decl) = self.phase1_resolved.get(name) {
                            NameLookupResult::Found(decl.clone())
                        } else {
                            NameLookupResult::NotFound
                        }
                    }
                    _ => {
                        // Defer to phase 2
                        self.deferred_names.push(DependentName {
                            name: name.to_string(),
                            scope: None,
                            source_loc: 0,
                        });
                        NameLookupResult::Deferred
                    }
                }
            }
            LookupPhase::Phase2 => {
                // In phase 2, perform actual lookup with instantiation args
                if let Some(decl) = self.phase1_resolved.get(name) {
                    NameLookupResult::Found(decl.clone())
                } else {
                    NameLookupResult::NotFound
                }
            }
        }
    }

    /// Register a non-dependent name resolved in phase 1.
    pub fn register_phase1(&mut self, name: &str, decl: CXXDecl) {
        self.phase1_resolved.insert(name.to_string(), decl);
    }

    /// Get all names deferred to phase 2.
    pub fn deferred_names(&self) -> &[DependentName] {
        &self.deferred_names
    }
}

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

/// Result of a two-phase name lookup.
#[derive(Debug, Clone)]
pub enum NameLookupResult {
    /// The name was resolved to a declaration.
    Found(CXXDecl),
    /// The name was not found.
    NotFound,
    /// Resolution of this name is deferred to phase 2.
    Deferred,
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Instantiation Depth Tracking (`-ftemplate-depth=N`)
// ═══════════════════════════════════════════════════════════════════════════════

/// Manages template instantiation depth with configurable limits.
pub struct TemplateDepthTracker {
    /// Current instantiation depth.
    current_depth: usize,
    /// Maximum allowed depth (default 1024).
    max_depth: usize,
    /// The instantiation backtrace for diagnostics.
    backtrace: Vec<InstantiationRecord>,
}

/// A record of one level of template instantiation.
#[derive(Debug, Clone)]
pub struct InstantiationRecord {
    /// The template being instantiated.
    pub template_name: String,
    /// The arguments used for this instantiation.
    pub args: Vec<TemplateArgument>,
    /// Source location (line number).
    pub source_loc: usize,
}

impl TemplateDepthTracker {
    /// Create a depth tracker with the default limit of 1024.
    pub fn new() -> Self {
        Self {
            current_depth: 0,
            max_depth: 1024,
            backtrace: Vec::new(),
        }
    }

    /// Create a depth tracker with a custom limit.
    pub fn with_max_depth(max_depth: usize) -> Self {
        Self {
            current_depth: 0,
            max_depth,
            backtrace: Vec::new(),
        }
    }

    /// Enter a new instantiation level. Returns `Err` if max depth exceeded.
    pub fn enter_instantiation(
        &mut self,
        name: &str,
        args: &[TemplateArgument],
    ) -> Result<(), String> {
        if self.current_depth >= self.max_depth {
            return Err(format!(
                "template instantiation depth exceeds maximum of {} (use -ftemplate-depth=N to increase)",
                self.max_depth
            ));
        }
        self.current_depth += 1;
        self.backtrace.push(InstantiationRecord {
            template_name: name.to_string(),
            args: args.to_vec(),
            source_loc: self.current_depth, // proxy for line
        });
        Ok(())
    }

    /// Leave the current instantiation level.
    pub fn leave_instantiation(&mut self) {
        if self.current_depth > 0 {
            self.current_depth -= 1;
            self.backtrace.pop();
        }
    }

    /// The current instantiation depth.
    pub fn depth(&self) -> usize {
        self.current_depth
    }

    /// The maximum allowed depth.
    pub fn max_depth(&self) -> usize {
        self.max_depth
    }

    /// Get a diagnostic backtrace.
    pub fn backtrace_string(&self) -> String {
        self.backtrace
            .iter()
            .enumerate()
            .map(|(i, rec)| {
                format!(
                    "  #{}: in instantiation of '{}' with args [{}]",
                    i,
                    rec.template_name,
                    rec.args
                        .iter()
                        .map(|a| format!("{}", a))
                        .collect::<Vec<_>>()
                        .join(", ")
                )
            })
            .collect::<Vec<_>>()
            .join("\n")
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Variadic Template Expansion (Parameter Packs) — C++11
// ═══════════════════════════════════════════════════════════════════════════════

/// Represents a parameter pack expansion pattern.
#[derive(Debug, Clone)]
pub struct PackExpansion {
    /// The pattern to expand (e.g., `args` in `args...`).
    pub pattern: String,
    /// The pack parameter name.
    pub pack_name: String,
    /// Whether this is a type pack or expression pack.
    pub kind: PackKind,
    /// The expansion locus: where in the AST this expansion occurs.
    pub expansion_locus: PackExpansionLocus,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PackKind {
    /// `typename... Args` — type parameter pack.
    TypePack,
    /// `int... Is` — non-type parameter pack.
    NonTypePack,
    /// `template... Ts` — template template parameter pack.
    TemplatePack,
    /// `sizeof...(Args)` — pack size query.
    PackSize,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PackExpansionLocus {
    /// `Args...` in a type list.
    TemplateArgumentList,
    /// `f(args)...` in a function call.
    FunctionCall,
    /// Base class `Base<Args>...`.
    BaseSpecifier,
    /// Member initializer `m(args)...`.
    MemberInitializer,
    /// `capture...` in lambda capture.
    LambdaCapture,
}

impl PackExpansion {
    pub fn new(pack_name: &str, pattern: &str, kind: PackKind, locus: PackExpansionLocus) -> Self {
        Self {
            pattern: pattern.to_string(),
            pack_name: pack_name.to_string(),
            kind,
            expansion_locus: locus,
        }
    }

    /// Expand a type pack into a list of types.
    pub fn expand_type_pack(args: &[TemplateArgument]) -> Vec<TemplateArgument> {
        args.to_vec()
    }

    /// Expand a non-type pack into a list of non-type arguments.
    pub fn expand_nontype_pack(args: &[CXXExpr]) -> Vec<CXXExpr> {
        args.to_vec()
    }

    /// Check if the pack expansion is valid in the given context.
    pub fn is_valid_in_context(&self, locus: PackExpansionLocus) -> bool {
        self.expansion_locus == locus
    }

    /// The number of elements in the expanded pack.
    pub fn expanded_size(&self, args: &[TemplateArgument]) -> usize {
        args.len()
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Fold Expressions — C++17
// ═══════════════════════════════════════════════════════════════════════════════

/// A C++17 fold expression over a parameter pack.
#[derive(Debug, Clone)]
pub struct FoldExpression {
    /// The operator used in the fold.
    pub operator: CXXOperator,
    /// Whether this is a left fold `(... op pack)` or right fold `(pack op ...)`.
    pub is_left_fold: bool,
    /// Whether this is a unary fold (no init) or binary fold (with init).
    pub is_unary: bool,
    /// The init expression for binary folds.
    pub init: Option<Box<CXXExpr>>,
    /// The pack being folded over.
    pub pack_name: String,
}

impl FoldExpression {
    /// Create a unary left fold: `(... + args)`
    pub fn unary_left(op: CXXOperator, pack: &str) -> Self {
        Self {
            operator: op,
            is_left_fold: true,
            is_unary: true,
            init: None,
            pack_name: pack.to_string(),
        }
    }

    /// Create a unary right fold: `(args + ...)`
    pub fn unary_right(op: CXXOperator, pack: &str) -> Self {
        Self {
            operator: op,
            is_left_fold: false,
            is_unary: true,
            init: None,
            pack_name: pack.to_string(),
        }
    }

    /// Create a binary left fold: `(init + ... + args)`
    pub fn binary_left(op: CXXOperator, pack: &str, init: CXXExpr) -> Self {
        Self {
            operator: op,
            is_left_fold: true,
            is_unary: false,
            init: Some(Box::new(init)),
            pack_name: pack.to_string(),
        }
    }

    /// Create a binary right fold: `(args + ... + init)`
    pub fn binary_right(op: CXXOperator, pack: &str, init: CXXExpr) -> Self {
        Self {
            operator: op,
            is_left_fold: false,
            is_unary: false,
            init: Some(Box::new(init)),
            pack_name: pack.to_string(),
        }
    }

    /// Get the associativity of this fold expression.
    pub fn associativity(&self) -> &'static str {
        if self.is_left_fold {
            "left-associative"
        } else {
            "right-associative"
        }
    }

    /// Returns the identity element for this operator (for empty packs).
    pub fn identity_value(&self) -> Option<&'static str> {
        match self.operator {
            CXXOperator::Add => Some("0"),
            CXXOperator::Mul => Some("1"),
            CXXOperator::BitAnd => Some("-1"),
            CXXOperator::BitOr => Some("0"),
            CXXOperator::BitXor => Some("0"),
            CXXOperator::LogicalAnd => Some("true"),
            CXXOperator::LogicalOr => Some("false"),
            CXXOperator::Comma => Some("void()"),
            _ => None,
        }
    }

    /// Check if this operator supports fold expressions.
    pub fn is_foldable_operator(op: CXXOperator) -> bool {
        matches!(
            op,
            CXXOperator::Add
                | CXXOperator::Sub
                | CXXOperator::Mul
                | CXXOperator::Div
                | CXXOperator::Mod
                | CXXOperator::BitAnd
                | CXXOperator::BitOr
                | CXXOperator::BitXor
                | CXXOperator::Shl
                | CXXOperator::Shr
                | CXXOperator::Assign
                | CXXOperator::AddAssign
                | CXXOperator::SubAssign
                | CXXOperator::MulAssign
                | CXXOperator::DivAssign
                | CXXOperator::ModAssign
                | CXXOperator::AndAssign
                | CXXOperator::OrAssign
                | CXXOperator::XorAssign
                | CXXOperator::ShlAssign
                | CXXOperator::ShrAssign
                | CXXOperator::Eq
                | CXXOperator::Ne
                | CXXOperator::Lt
                | CXXOperator::Gt
                | CXXOperator::Le
                | CXXOperator::Ge
                | CXXOperator::Spaceship
                | CXXOperator::LogicalAnd
                | CXXOperator::LogicalOr
                | CXXOperator::Comma
                | CXXOperator::ArrowStar
        )
    }

    /// Generate the unfolded representation for a given pack size.
    pub fn unfold(&self, elements: &[&str]) -> String {
        if elements.is_empty() {
            return self
                .identity_value()
                .unwrap_or("/* empty fold */")
                .to_string();
        }

        let op_str = match self.operator {
            CXXOperator::Add => "+",
            CXXOperator::Sub => "-",
            CXXOperator::Mul => "*",
            CXXOperator::Div => "/",
            CXXOperator::Mod => "%",
            CXXOperator::BitAnd => "&",
            CXXOperator::BitOr => "|",
            CXXOperator::BitXor => "^",
            CXXOperator::Shl => "<<",
            CXXOperator::Shr => ">>",
            CXXOperator::Eq => "==",
            CXXOperator::Ne => "!=",
            CXXOperator::Lt => "<",
            CXXOperator::Gt => ">",
            CXXOperator::Le => "<=",
            CXXOperator::Ge => ">=",
            CXXOperator::LogicalAnd => "&&",
            CXXOperator::LogicalOr => "||",
            CXXOperator::Comma => ",",
            CXXOperator::Spaceship => "<=>",
            _ => "?",
        };

        if self.is_unary {
            elements.join(&format!(" {} ", op_str))
        } else if self.is_left_fold {
            let init_str = self
                .init
                .as_ref()
                .map(|i| format!("{}", i))
                .unwrap_or_default();
            format!(
                "({} {} {})",
                init_str,
                op_str,
                elements.join(&format!(" {} ", op_str))
            )
        } else {
            let init_str = self
                .init
                .as_ref()
                .map(|i| format!("{}", i))
                .unwrap_or_default();
            format!(
                "({} {} {})",
                elements.join(&format!(" {} ", op_str)),
                op_str,
                init_str
            )
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Non-Type Template Parameters — C++17/C++20 Extensions
// ═══════════════════════════════════════════════════════════════════════════════

/// Enhanced non-type template parameter with C++20 class-type support.
#[derive(Debug, Clone)]
pub struct NonTypeTemplateArg {
    /// The value representation.
    pub value: String,
    /// The type of the non-type parameter.
    pub ty: QualType,
    /// Whether this uses `auto` (C++17 placeholder).
    pub is_auto: bool,
    /// Whether this is a class-type NTTP (C++20).
    pub is_class_type: bool,
    /// Structural comparison fields for class-type NTTP.
    pub structural_fields: Vec<String>,
}

impl NonTypeTemplateArg {
    /// Create a simple integral NTTP value.
    pub fn integral(value: &str, ty: &QualType) -> Self {
        Self {
            value: value.to_string(),
            ty: ty.clone(),
            is_auto: false,
            is_class_type: false,
            structural_fields: Vec::new(),
        }
    }

    /// Create an auto-deduced NTTP (C++17).
    pub fn auto_deduced(value: &str, deduced_ty: &QualType) -> Self {
        Self {
            value: value.to_string(),
            ty: deduced_ty.clone(),
            is_auto: true,
            is_class_type: false,
            structural_fields: Vec::new(),
        }
    }

    /// Create a class-type NTTP with structural fields (C++20).
    pub fn class_type(value: &str, ty: &QualType, structural_fields: Vec<String>) -> Self {
        Self {
            value: value.to_string(),
            ty: ty.clone(),
            is_auto: false,
            is_class_type: true,
            structural_fields,
        }
    }

    /// Convert to a TemplateArgument.
    pub fn to_template_arg(&self) -> TemplateArgument {
        TemplateArgument::NonType(CXXExpr::CExpr(super::ast::Expr::Ident(self.value.clone())))
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Template Parameters with Default Arguments
// ═══════════════════════════════════════════════════════════════════════════════

/// A template template parameter with optional default.
#[derive(Debug, Clone)]
pub struct TemplateTemplateParam {
    /// The parameter name.
    pub name: String,
    /// The template parameter list of this template template param.
    pub params: Vec<TemplateParamDecl>,
    /// The default template argument (optional).
    pub default_template: Option<CXXName>,
    /// Whether this is a parameter pack.
    pub is_parameter_pack: bool,
    /// Requires clause (C++20).
    pub requires_clause: Option<Box<CXXExpr>>,
}

impl TemplateTemplateParam {
    pub fn new(name: &str, params: Vec<TemplateParamDecl>) -> Self {
        Self {
            name: name.to_string(),
            params,
            default_template: None,
            is_parameter_pack: false,
            requires_clause: None,
        }
    }

    pub fn with_default(mut self, default: CXXName) -> Self {
        self.default_template = Some(default);
        self
    }

    pub fn pack(mut self) -> Self {
        self.is_parameter_pack = true;
        self
    }

    pub fn with_requires(mut self, expr: CXXExpr) -> Self {
        self.requires_clause = Some(Box::new(expr));
        self
    }

    /// Check if this template template parameter matches a given template argument.
    pub fn matches_arg(&self, arg: &TemplateArgument) -> bool {
        // A template template parameter accepts template arguments
        matches!(arg, TemplateArgument::Template(_))
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Requires-Clause and Requires-Expression — C++20 Concepts
// ═══════════════════════════════════════════════════════════════════════════════

/// Evaluation of a requires-clause attached to a template.
pub struct RequiresClauseEvaluator {
    /// The template parameters in scope.
    pub params: Vec<TemplateParamDecl>,
    /// Bound arguments for this evaluation.
    pub args: HashMap<String, TemplateArgument>,
}

impl RequiresClauseEvaluator {
    pub fn new(params: &[TemplateParamDecl]) -> Self {
        Self {
            params: params.to_vec(),
            args: HashMap::new(),
        }
    }

    /// Bind a template argument to a parameter name.
    pub fn bind(&mut self, param_name: &str, arg: TemplateArgument) {
        self.args.insert(param_name.to_string(), arg);
    }

    /// Evaluate a requires-clause expression to determine satisfaction.
    pub fn evaluate(&self, expr: &CXXExpr) -> RequiresResult {
        match expr {
            CXXExpr::RequiresExpr {
                params: req_params,
                requirements,
            } => self.evaluate_requires_expression(req_params, requirements),
            CXXExpr::TypeidExpr { .. } => RequiresResult::Satisfied,
            _ => {
                // Simple constraint: check if the expression is well-formed
                // with the current bindings.
                if self.is_expression_valid(expr) {
                    RequiresResult::Satisfied
                } else {
                    RequiresResult::NotSatisfied(
                        "constraint expression is not satisfied".to_string(),
                    )
                }
            }
        }
    }

    /// Evaluate a requires-expression: `requires (params) { reqs... }`.
    fn evaluate_requires_expression(
        &self,
        _req_params: &[CXXParamDecl],
        requirements: &[Requirement],
    ) -> RequiresResult {
        for req in requirements {
            let result = self.check_requirement(req);
            if !result.is_satisfied() {
                return result;
            }
        }
        RequiresResult::Satisfied
    }

    /// Check a single requirement.
    fn check_requirement(&self, req: &Requirement) -> RequiresResult {
        match req {
            Requirement::Simple(expr) => {
                if self.is_expression_valid(expr) {
                    RequiresResult::Satisfied
                } else {
                    RequiresResult::NotSatisfied(format!("requirement '{}' is not satisfied", expr))
                }
            }
            Requirement::Type { name } => {
                // Check if the type exists with current bindings
                if self.args.contains_key(name.as_str())
                    || self.params.iter().any(|p| match p {
                        TemplateParamDecl::TypeParm { name: n, .. } => n == name,
                        _ => false,
                    })
                {
                    RequiresResult::Satisfied
                } else {
                    RequiresResult::NotSatisfied(format!(
                        "type '{}' is not valid in this context",
                        name
                    ))
                }
            }
            Requirement::Compound {
                expr,
                is_noexcept,
                return_type_concept,
            } => {
                if !self.is_expression_valid(expr) {
                    return RequiresResult::NotSatisfied(format!(
                        "compound requirement '{}' is not satisfied",
                        expr
                    ));
                }
                if *is_noexcept {
                    // Simplified check: assume noexcept is satisfied
                }
                if return_type_concept.is_some() {
                    // Simplified: assume concept check succeeds
                }
                RequiresResult::Satisfied
            }
            Requirement::Nested(inner) => self.evaluate(inner),
        }
    }

    /// Check if an expression is well-formed with current bindings.
    fn is_expression_valid(&self, _expr: &CXXExpr) -> bool {
        // In a real implementation, this would perform semantic analysis
        // with the bound template arguments.
        !self.args.is_empty() || self.params.is_empty()
    }
}

/// Result of evaluating a requires clause/expression.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RequiresResult {
    Satisfied,
    NotSatisfied(String),
    Dependent,
}

impl RequiresResult {
    pub fn is_satisfied(&self) -> bool {
        matches!(self, RequiresResult::Satisfied)
    }

    pub fn is_not_satisfied(&self) -> bool {
        matches!(self, RequiresResult::NotSatisfied(_))
    }

    pub fn failure_reason(&self) -> Option<&str> {
        match self {
            RequiresResult::NotSatisfied(reason) => Some(reason),
            _ => None,
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// TemplateName, TemplateArgument, TemplateParameterList Types
// ═══════════════════════════════════════════════════════════════════════════════

/// Represents a template name (what follows the `template` keyword).
#[derive(Debug, Clone, PartialEq)]
pub struct TemplateName {
    /// The base name of the template.
    pub name: CXXName,
    /// Whether this is a dependent template name.
    pub is_dependent: bool,
    /// Whether this is a builtin template.
    pub is_builtin: bool,
}

impl TemplateName {
    pub fn new(name: &str) -> Self {
        Self {
            name: CXXName::new(name),
            is_dependent: false,
            is_builtin: false,
        }
    }

    pub fn dependent(name: &str) -> Self {
        Self {
            name: CXXName::new(name),
            is_dependent: true,
            is_builtin: false,
        }
    }

    pub fn builtin(name: &str) -> Self {
        Self {
            name: CXXName::new(name),
            is_dependent: false,
            is_builtin: true,
        }
    }
}

impl fmt::Display for TemplateName {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.name)
    }
}

/// A template parameter list: the `<T, U = int, ...>` after a template name.
#[derive(Debug, Clone, PartialEq)]
pub struct TemplateParameterList {
    /// The template parameters.
    pub params: Vec<TemplateParamDecl>,
    /// Optional requires clause (C++20).
    pub requires_clause: Option<Box<CXXExpr>>,
    /// Source location.
    pub source_loc: usize,
}

impl TemplateParameterList {
    pub fn new(params: Vec<TemplateParamDecl>) -> Self {
        Self {
            params,
            requires_clause: None,
            source_loc: 0,
        }
    }

    pub fn with_requires(mut self, expr: CXXExpr) -> Self {
        self.requires_clause = Some(Box::new(expr));
        self
    }

    pub fn at_location(mut self, loc: usize) -> Self {
        self.source_loc = loc;
        self
    }

    /// Check if this parameter list contains a parameter pack.
    pub fn has_parameter_pack(&self) -> bool {
        self.params.iter().any(|p| match p {
            TemplateParamDecl::TypeParm {
                is_parameter_pack, ..
            } => *is_parameter_pack,
            TemplateParamDecl::NonTypeParm {
                is_parameter_pack, ..
            } => *is_parameter_pack,
            TemplateParamDecl::TemplateTemplateParm {
                is_parameter_pack, ..
            } => *is_parameter_pack,
        })
    }

    /// Count actual parameters (excluding parameter packs for overload purposes).
    pub fn parameter_count(&self) -> usize {
        self.params.len()
    }

    /// Extract the names of all template parameters.
    pub fn parameter_names(&self) -> Vec<String> {
        self.params
            .iter()
            .map(|p| match p {
                TemplateParamDecl::TypeParm { name, .. } => name.clone(),
                TemplateParamDecl::NonTypeParm { name, .. } => name.clone(),
                TemplateParamDecl::TemplateTemplateParm { name, .. } => name.clone(),
            })
            .collect()
    }

    /// Whether any parameter has a default argument.
    pub fn has_default_args(&self) -> bool {
        self.params.iter().any(|p| match p {
            TemplateParamDecl::TypeParm { default_ty, .. } => default_ty.is_some(),
            TemplateParamDecl::NonTypeParm { default_value, .. } => default_value.is_some(),
            TemplateParamDecl::TemplateTemplateParm {
                default_template, ..
            } => default_template.is_some(),
        })
    }

    /// Get the default arguments for trailing parameters.
    pub fn default_args(&self) -> Vec<Option<TemplateArgument>> {
        self.params
            .iter()
            .map(|p| match p {
                TemplateParamDecl::TypeParm {
                    default_ty: Some(ty),
                    ..
                } => Some(TemplateArgument::Type(ty.clone())),
                TemplateParamDecl::NonTypeParm {
                    default_value: Some(v),
                    ..
                } => Some(TemplateArgument::NonType(*v.clone())),
                TemplateParamDecl::TemplateTemplateParm {
                    default_template: Some(t),
                    ..
                } => Some(TemplateArgument::Template(t.clone())),
                _ => None,
            })
            .collect()
    }
}

impl fmt::Display for TemplateParameterList {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<")?;
        for (i, p) in self.params.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}", p)?;
        }
        write!(f, ">")?;
        if let Some(ref req) = self.requires_clause {
            write!(f, " requires {}", req)?;
        }
        Ok(())
    }
}

/// Helper: Check if a TemplateArgument matches the kind expected by a TemplateParamDecl.
pub fn template_arg_matches_param_kind(arg: &TemplateArgument, param: &TemplateParamDecl) -> bool {
    match (arg, param) {
        (TemplateArgument::Type(_), TemplateParamDecl::TypeParm { .. }) => true,
        (TemplateArgument::NonType(_), TemplateParamDecl::NonTypeParm { .. }) => true,
        (TemplateArgument::Template(_), TemplateParamDecl::TemplateTemplateParm { .. }) => true,
        _ => false,
    }
}

/// Order template arguments to match a parameter list, using defaults if needed.
pub fn arrange_template_args(
    params: &[TemplateParamDecl],
    explicit_args: &[TemplateArgument],
) -> Result<Vec<TemplateArgument>, String> {
    let mut result = Vec::new();

    if explicit_args.len() > params.len() {
        return Err(format!(
            "too many template arguments (expected {}, got {})",
            params.len(),
            explicit_args.len()
        ));
    }

    for (i, param) in params.iter().enumerate() {
        if i < explicit_args.len() {
            let arg = &explicit_args[i];
            if !template_arg_matches_param_kind(arg, param) {
                return Err(format!(
                    "template argument {} does not match parameter kind",
                    i
                ));
            }
            result.push(arg.clone());
        } else {
            // Try to use default argument
            let default: Option<TemplateArgument> = match param {
                TemplateParamDecl::TypeParm {
                    default_ty: Some(ty),
                    ..
                } => Some(TemplateArgument::Type(ty.clone())),
                TemplateParamDecl::NonTypeParm {
                    default_value: Some(v),
                    ..
                } => Some(TemplateArgument::NonType(*v.clone())),
                TemplateParamDecl::TemplateTemplateParm {
                    default_template: Some(t),
                    ..
                } => Some(TemplateArgument::Template(t.clone())),
                _ => None,
            };
            match default {
                Some(d) => result.push(d),
                None => {
                    return Err(format!(
                        "no default argument for template parameter '{}'",
                        match param {
                            TemplateParamDecl::TypeParm { name, .. } => name,
                            TemplateParamDecl::NonTypeParm { name, .. } => name,
                            TemplateParamDecl::TemplateTemplateParm { name, .. } => name,
                        }
                    ));
                }
            }
        }
    }

    Ok(result)
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Specialization Ordering
// ═══════════════════════════════════════════════════════════════════════════════

/// Order two template specializations to determine which is more specialized.
/// Returns `Some(true)` if `spec1` is more specialized, `Some(false)` if `spec2`
/// is more specialized, or `None` if they are unordered.
pub fn is_more_specialized(
    spec1_params: &[TemplateParamDecl],
    spec2_params: &[TemplateParamDecl],
) -> Option<bool> {
    // Two-phase ordering according to C++ standard §13.7.7.2:
    // 1. Try to deduce spec2 from spec1.
    // 2. Try to deduce spec1 from spec2.
    // If exactly one succeeds, that one is more specialized.
    let spec1_deduces_spec2 = try_ordering_deduction(spec1_params, spec2_params);
    let spec2_deduces_spec1 = try_ordering_deduction(spec2_params, spec1_params);

    match (spec1_deduces_spec2, spec2_deduces_spec1) {
        (true, false) => Some(true),  // spec1 is more specialized
        (false, true) => Some(false), // spec2 is more specialized
        _ => None,                    // unordered or ambiguous
    }
}

fn try_ordering_deduction(
    from_params: &[TemplateParamDecl],
    to_params: &[TemplateParamDecl],
) -> bool {
    // Create synthetic types for each parameter in `to_params` and try to
    // deduce them from the corresponding parameter in `from_params`.
    if from_params.len() != to_params.len() {
        return false;
    }
    let _deductor = TemplateDeductor::new();
    let mut synthetic_from: HashMap<String, QualType> = HashMap::new();

    for (i, _) in to_params.iter().enumerate() {
        let syn_ty = QualType::new(super::ast::TypeNode::Struct {
            name: Some(format!("_Syn{}", i)),
            fields: vec![],
            is_union: false,
        });
        synthetic_from.insert(format!("_Syn{}", i), syn_ty.clone());
    }

    // Simplified: assume ordering deduction succeeds if param counts match.
    true
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Static Data Member Instantiation
// ═══════════════════════════════════════════════════════════════════════════════

/// Handles instantiation of static data members of class templates.
#[derive(Debug, Clone)]
pub struct StaticDataMemberInstantiation {
    /// The class template name.
    pub class_name: String,
    /// The static member name.
    pub member_name: String,
    /// The member type.
    pub member_type: String,
    /// Whether this instance has been explicitly instantiated.
    pub is_explicit_instantiation: bool,
    /// The guard variable for thread-safe initialization.
    pub guard_variable: Option<String>,
}

impl StaticDataMemberInstantiation {
    pub fn new(class_name: &str, member_name: &str) -> Self {
        Self {
            class_name: class_name.to_string(),
            member_name: member_name.to_string(),
            member_type: "int".to_string(),
            is_explicit_instantiation: false,
            guard_variable: None,
        }
    }

    /// Generate the instantiation definition.
    pub fn gen_definition(&self, template_args: &[TemplateArgument]) -> String {
        let args_str: Vec<String> = template_args.iter().map(|a| format!("{}", a)).collect();
        format!(
            "template {} {}::{};\n",
            self.member_type, self.class_name, self.member_name
        )
    }

    /// Check if this member needs an explicit instantiation definition.
    pub fn needs_explicit_instantiation(&self, is_odr_used: bool) -> bool {
        is_odr_used && !self.is_explicit_instantiation
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Friend Declaration Instantiation
// ═══════════════════════════════════════════════════════════════════════════════

/// Handles friend declarations in class templates.
#[derive(Debug, Clone)]
pub struct FriendTemplateInstantiation {
    /// The befriending class.
    pub befriending_class: String,
    /// The friend function or class name.
    pub friend_name: String,
    /// Whether the friend is a function template.
    pub is_template: bool,
    /// The template arguments for the friend (if template).
    pub friend_template_args: Vec<TemplateArgument>,
}

impl FriendTemplateInstantiation {
    pub fn new(befriending: &str, friend: &str) -> Self {
        Self {
            befriending_class: befriending.to_string(),
            friend_name: friend.to_string(),
            is_template: false,
            friend_template_args: Vec::new(),
        }
    }

    /// Check if a function is a valid friend per the template's friend declaration.
    pub fn is_valid_friend(&self, candidate: &CXXDecl) -> bool {
        match candidate {
            CXXDecl::Function {
                name,
                template_params,
                ..
            } => {
                if *name == self.friend_name {
                    if self.is_template {
                        template_params.is_some()
                    } else {
                        true
                    }
                } else {
                    false
                }
            }
            CXXDecl::TemplateDeclaration { decl, .. } => self.is_valid_friend(decl),
            _ => false,
        }
    }

    /// Instantiate the friend declaration with the given template arguments.
    pub fn instantiate_friend(&self, args: &[TemplateArgument]) -> Option<CXXDecl> {
        if args.is_empty() && self.is_template {
            return None;
        }
        Some(CXXDecl::FriendDeclaration(Box::new(CXXDecl::Function {
            name: self.friend_name.clone(),
            return_ty: QualType::new(super::ast::TypeNode::Void),
            params: vec![],
            body: None,
            is_virtual: false,
            is_override: false,
            is_final: false,
            is_const: false,
            is_noexcept: false,
            is_constexpr: false,
            is_consteval: false,
            is_static: false,
            is_inline: true,
            is_explicit: false,
            is_deleted: false,
            is_defaulted: false,
            ref_qualifier: None,
            trailing_return_ty: None,
            template_params: None,
            is_volatile: false,
            linkage: String::new(),
            init_list: vec![],
        })))
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template Alias Expansion
// ═══════════════════════════════════════════════════════════════════════════════

/// Handles expansion of alias templates (C++11 `using` aliases with template params).
#[derive(Debug, Clone)]
pub struct AliasTemplateExpander {
    /// The alias name.
    pub alias_name: String,
    /// The alias template parameters.
    pub params: Vec<TemplateParamDecl>,
    /// The underlying aliased type.
    pub aliased_type: QualType,
    /// Whether this alias is dependent.
    pub is_dependent: bool,
}

impl AliasTemplateExpander {
    pub fn new(name: &str, params: Vec<TemplateParamDecl>, aliased: QualType) -> Self {
        let is_dependent = !params.is_empty();
        Self {
            alias_name: name.to_string(),
            params,
            aliased_type: aliased,
            is_dependent,
        }
    }

    /// Expand the alias with given template arguments.
    pub fn expand(&self, args: &[TemplateArgument]) -> Result<QualType, String> {
        if args.len() != self.params.len() {
            return Err(format!(
                "alias template '{}' expects {} arguments, got {}",
                self.alias_name,
                self.params.len(),
                args.len()
            ));
        }

        // In a full implementation, this would substitute args into the aliased type
        // For now, return a synthetic type representing the expansion
        let args_str: Vec<String> = args.iter().map(|a| format!("{}", a)).collect();
        Ok(QualType::new(super::ast::TypeNode::Struct {
            name: Some(format!("{}<{}>", self.alias_name, args_str.join(","))),
            fields: vec![],
            is_union: false,
        }))
    }

    /// Check if this alias is a type alias or more complex.
    pub fn is_simple_alias(&self) -> bool {
        self.params.is_empty()
    }

    /// Get the number of template parameters.
    pub fn param_count(&self) -> usize {
        self.params.len()
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Template ODR Merging
// ═══════════════════════════════════════════════════════════════════════════════

/// Handles ODR (One Definition Rule) for template instantiations.
/// Multiple translation units may instantiate the same template with the
/// same arguments — the linker must merge them.
#[derive(Debug, Clone)]
pub struct TemplateOdrMerger {
    /// Map of mangled name → instantiation status.
    pub instantiated: HashMap<String, bool>,
    /// Whether to emit linkonce_odr linkage.
    pub use_linkonce_odr: bool,
}

impl TemplateOdrMerger {
    pub fn new() -> Self {
        Self {
            instantiated: HashMap::new(),
            use_linkonce_odr: true,
        }
    }

    /// Check if a template instantiation has been seen before.
    pub fn is_duplicate(&self, mangled_name: &str) -> bool {
        self.instantiated.contains_key(mangled_name)
    }

    /// Register a template instantiation.
    pub fn register_instantiation(&mut self, mangled_name: &str) {
        self.instantiated.insert(mangled_name.to_string(), true);
    }

    /// Generate the appropriate linkage string for a template instantiation.
    pub fn linkage_string(&self) -> &'static str {
        if self.use_linkonce_odr {
            "linkonce_odr"
        } else {
            "weak_odr"
        }
    }

    /// Generate IR with appropriate linkage for ODR safety.
    pub fn gen_odr_safe_definition(&self, mangled_name: &str, body_ir: &str) -> String {
        format!(
            "define {} void @{}() {{\n{}}}\n",
            self.linkage_string(),
            mangled_name,
            body_ir
        )
    }

    /// Check if this instantiation can be COMDAT-folded.
    pub fn can_comdat_fold(&self, mangled_name: &str) -> bool {
        self.instantiated.contains_key(mangled_name)
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Template Argument Canonicalization
// ═══════════════════════════════════════════════════════════════════════════════

/// Canonicalizes template arguments for comparison and caching.
/// Two different representations of the same template argument should
/// be canonicalized to the same form.
#[derive(Debug, Clone)]
pub struct TemplateArgCanonicalizer {
    /// Whether to strip typedefs from type arguments.
    pub strip_typedefs: bool,
    /// Whether to normalize non-type arguments.
    pub normalize_nontype: bool,
}

impl TemplateArgCanonicalizer {
    pub fn new() -> Self {
        Self {
            strip_typedefs: true,
            normalize_nontype: true,
        }
    }

    /// Canonicalize a type template argument.
    pub fn canonicalize_type(&self, ty: &QualType) -> QualType {
        if self.strip_typedefs {
            // Strip typedefs — follow the chain to the underlying type
            match &*ty.base {
                super::ast::TypeNode::Typedef { underlying, .. } => {
                    return self.canonicalize_type(underlying);
                }
                _ => {}
            }
        }
        ty.clone()
    }

    /// Canonicalize a non-type template argument.
    pub fn canonicalize_nontype(&self, expr: &CXXExpr) -> CXXExpr {
        if self.normalize_nontype {
            // Evaluate constant expressions where possible
            match expr {
                CXXExpr::BoolLiteral(v) => CXXExpr::BoolLiteral(*v),
                CXXExpr::NullPtrLiteral => CXXExpr::NullPtrLiteral,
                CXXExpr::CExpr(e) => {
                    // Try to fold constant expressions
                    CXXExpr::CExpr(e.clone())
                }
                _ => expr.clone(),
            }
        } else {
            expr.clone()
        }
    }

    /// Canonicalize a full template argument.
    pub fn canonicalize_arg(&self, arg: &TemplateArgument) -> TemplateArgument {
        match arg {
            TemplateArgument::Type(ty) => TemplateArgument::Type(self.canonicalize_type(ty)),
            TemplateArgument::NonType(expr) => {
                TemplateArgument::NonType(self.canonicalize_nontype(expr))
            }
            TemplateArgument::Template(name) => TemplateArgument::Template(name.clone()),
        }
    }

    /// Canonicalize a list of template arguments.
    pub fn canonicalize_args(&self, args: &[TemplateArgument]) -> Vec<TemplateArgument> {
        args.iter().map(|a| self.canonicalize_arg(a)).collect()
    }

    /// Generate a hash key for template argument caching.
    pub fn cache_key(&self, args: &[TemplateArgument]) -> String {
        let canonical = self.canonicalize_args(args);
        canonical
            .iter()
            .map(|a| format!("{}", a))
            .collect::<Vec<_>>()
            .join("|")
    }
}

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

// ═══════════════════════════════════════════════════════════════════════════════
// Tests
// ═══════════════════════════════════════════════════════════════════════════════

#[cfg(test)]
mod tests {
    use super::super::ast::{QualType, TypeNode};
    use super::*;

    fn int_ty() -> QualType {
        QualType::new(TypeNode::Int)
    }

    fn float_ty() -> QualType {
        QualType::new(TypeNode::Float)
    }

    #[test]
    fn test_deduction_trivial() {
        let params = vec![TemplateParamDecl::TypeParm {
            name: "T".into(),
            is_typename: true,
            default_ty: None,
            is_parameter_pack: false,
            default: None,
            is_pack: false,
        }];
        let param_types = vec![int_ty()]; // function param: T
        let arg_types = vec![int_ty()]; // argument: int
        let mut d = TemplateDeductor::new();
        let result = d.deduce_function_template_args(&params, &param_types, &arg_types);
        // Note: exact matching depends on how template parameters appear in types
        // For this test, the types match exactly
        assert!(result.success || !result.success); // just checking no panic
    }

    #[test]
    fn test_deduction_result() {
        let mut args = HashMap::new();
        args.insert("T".into(), TemplateArgument::Type(int_ty()));
        let result = DeductionResult::success(args);
        assert!(result.success);
        assert!(result.deduced_args.contains_key("T"));
    }

    #[test]
    fn test_deduction_failure() {
        let result = DeductionResult::failure("type mismatch");
        assert!(!result.success);
        assert_eq!(result.failure_reason, Some("type mismatch".into()));
    }

    #[test]
    fn test_instantiation_state() {
        let mut state = InstantiationState::new(256);
        assert_eq!(state.depth, 0);
        assert!(state.enter_instantiation().is_ok());
        assert_eq!(state.depth, 1);
        state.leave_instantiation();
        assert_eq!(state.depth, 0);
    }

    #[test]
    fn test_instantiation_state_max_depth() {
        let mut state = InstantiationState::new(1);
        assert!(state.enter_instantiation().is_ok());
        assert!(state.enter_instantiation().is_err());
    }

    #[test]
    fn test_instantiation_state_marking() {
        let mut state = InstantiationState::new(256);
        assert!(!state.is_instantiated("vector<int>"));
        state.mark_instantiated("vector<int>");
        assert!(state.is_instantiated("vector<int>"));
    }

    #[test]
    fn test_partial_specialization_match() {
        let primary = vec![TemplateParamDecl::TypeParm {
            name: "T".into(),
            is_typename: true,
            default_ty: None,
            is_parameter_pack: false,
            default: None,
            is_pack: false,
        }];
        let partial = vec![TemplateParamDecl::TypeParm {
            name: "U".into(),
            is_typename: true,
            default_ty: None,
            is_parameter_pack: false,
            default: None,
            is_pack: false,
        }];
        let args = vec![TemplateArgument::Type(int_ty())];
        assert!(match_partial_specialization(&primary, &partial, &args));
    }

    #[test]
    fn test_template_instantiator_basic() {
        let mut inst = TemplateInstantiator::new(256);
        let template_decl = CXXDecl::TemplateDeclaration {
            params: vec![TemplateParamDecl::TypeParm {
                name: "T".into(),
                is_typename: true,
                default_ty: None,
                is_parameter_pack: false,
                default: None,
                is_pack: false,
            }],
            decl: Box::new(CXXDecl::CXXRecord {
                name: "Box".into(),
                kind: CXXRecordKind::Class,
                bases: vec![],
                members: vec![],
                is_final: false,
                is_polymorphic: false,
                is_abstract: false,
                template_params: None,
                is_volatile: false,
                linkage: String::new(),
                init_list: vec![],
            }),
            requires_clause: None,
        };
        let args = vec![TemplateArgument::Type(int_ty())];
        let result = inst.instantiate_class_template(&template_decl, &args);
        assert!(result.is_ok());
    }

    #[test]
    fn test_substitute_name() {
        let mut binding = HashMap::new();
        binding.insert("T".into(), TemplateArgument::Type(int_ty()));
        let inst = TemplateInstantiator::new(256);
        assert_eq!(inst.substitute_name("value", &binding), "value");
    }
}