rukalang/

semantic.rs

//! Pre-expansion semantic analysis scaffolding for frontend programs.

use std::collections::BTreeMap;

use cranelift_entity::SecondaryMap;
use ruka_frontend::{
    Expr, ExprId, FrontendNodeIndex, MetaExpr, MetaExprId, MetaMatchPattern, MetaStmtId, Program,
    Stmt, TypeExpr,
};

use crate::meta_builtins::{builtin_result_type, builtin_spec_by_name};
use crate::meta_types::{format_type_expr, meta_types_compatible};

/// Runtime binding visible inside a typed expression builder.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BuilderBindingInfo {
    /// Binding name visible from the surrounding runtime scope.
    pub name: String,
    /// Best-known type for the binding before expansion.
    pub ty: Option<TypeExpr>,
}

/// Resolved meaning of an identifier before expansion.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ResolvedName {
    /// Lexically scoped runtime binding.
    RuntimeLocal,
    /// Lexically scoped meta binding.
    MetaLocal,
    /// Runtime function declaration.
    RuntimeFunction,
    /// Meta function declaration.
    MetaFunction,
    /// Struct declaration.
    Struct,
    /// Extern module declaration.
    ExternModule,
    /// Known type name.
    Type,
}

/// Compile-time type/category associated with a meta expression.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MetaType {
    /// Compile-time integer.
    Int,
    /// Compile-time boolean.
    Bool,
    /// Compile-time string.
    String,
    /// Compile-time type object.
    Type,
    /// Generated runtime expression with known runtime type.
    Expr(TypeExpr),
}

/// Pre-expansion semantic issue discovered before meta expansion.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SemanticIssue {
    /// Runtime binding used directly in meta evaluation.
    RuntimeBindingUnavailable {
        /// Binding name referenced from meta code.
        name: String,
    },
    /// Known non-meta symbol used as if it were a meta value.
    KnownNameNotMetaValue {
        /// Symbol name referenced from meta code.
        name: String,
        /// Resolved symbol category.
        kind: ResolvedName,
    },
    /// Statically known meta-type mismatch.
    MetaTypeMismatch {
        /// Expected meta-visible type.
        expected: String,
        /// Best-known actual meta-visible type.
        actual: String,
    },
}

/// Staged semantic facts for a meta call expression.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MetaCallInfo {
    /// Callee name resolved from the call site.
    pub callee: String,
    /// Whether the callee is a known builtin meta function.
    pub builtin: Option<BuiltinMetaCallKind>,
    /// Staged argument kinds at the call site.
    pub arg_types: Vec<Option<MetaType>>,
    /// Expected argument kinds for known builtin calls.
    pub expected_arg_kinds: Option<Vec<MetaArgKind>>,
    /// Best-known staged result type for the call.
    pub result_type: Option<MetaType>,
}

/// Known builtin meta call categories.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BuiltinMetaCallKind {
    /// `std::string::concat`.
    StringConcat,
    /// `std::string::starts_with`.
    StringStartsWith,
    /// `std::string::drop`.
    StringDrop,
    /// `std::string::take`.
    StringTake,
    /// `std::tuple::is_empty`.
    TupleIsEmpty,
    /// `std::tuple::head`.
    TupleHead,
    /// `std::tuple::tail`.
    TupleTail,
    /// `std::tuple::type_head`.
    TupleTypeHead,
    /// `std::tuple::type_tail`.
    TupleTypeTail,
}

/// Broad meta-value kind used for staged builtin argument expectations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MetaArgKind {
    /// Integer meta value.
    Int,
    /// Boolean meta value.
    Bool,
    /// String meta value.
    String,
    /// Type meta value.
    Type,
    /// Typed expression meta value.
    Expr,
}

/// Broad pattern category used by staged meta-match facts.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MetaPatternKind {
    /// Wildcard pattern.
    Wildcard,
    /// Integer literal pattern.
    Int,
    /// Boolean literal pattern.
    Bool,
    /// String literal pattern.
    String,
    /// Quoted code pattern.
    Quote,
    /// Quoted type pattern.
    Type,
}

/// Staged semantic facts for a meta match statement.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MetaMatchInfo {
    /// Best-known type of the matched value.
    pub matched_type: Option<MetaType>,
    /// Best-known converged type across all match arms.
    pub converged_arm_type: Option<MetaType>,
    /// Broad categories of the arm patterns.
    pub pattern_kinds: Vec<MetaPatternKind>,
}

/// Pre-expansion semantic information keyed by stable frontend node ids.
#[derive(Debug, Clone)]
pub struct StagedSemanticInfo {
    /// Deterministic frontend node index for the source program.
    pub nodes: FrontendNodeIndex,
    /// Runtime bindings visible at each `expr { ... }` builder site.
    pub builder_envs: SecondaryMap<MetaExprId, Option<Vec<BuilderBindingInfo>>>,
    /// Name-resolution result for runtime expressions.
    pub runtime_name_resolution: SecondaryMap<ExprId, Option<ResolvedName>>,
    /// Name-resolution result for meta expressions.
    pub meta_name_resolution: SecondaryMap<MetaExprId, Option<ResolvedName>>,
    /// Best-known pre-expansion runtime expression type.
    pub runtime_expr_types: SecondaryMap<ExprId, Option<TypeExpr>>,
    /// Best-known pre-expansion meta expression kind.
    pub meta_expr_types: SecondaryMap<MetaExprId, Option<MetaType>>,
    /// Known semantic facts for meta call expressions.
    pub meta_call_info: SecondaryMap<MetaExprId, Option<MetaCallInfo>>,
    /// Known semantic facts for meta match statements.
    pub meta_match_info: SecondaryMap<MetaStmtId, Option<MetaMatchInfo>>,
    /// Pre-expansion semantic issues found during analysis.
    pub issues: Vec<(MetaExprId, SemanticIssue)>,
    /// Obvious return-type issues for meta functions.
    pub meta_function_issues: BTreeMap<String, SemanticIssue>,
}

/// Analyze a parsed frontend program and collect reusable pre-expansion metadata.
pub fn analyze_program(program: &Program) -> StagedSemanticInfo {
    let nodes = FrontendNodeIndex::build(program);
    let mut analyzer = SemanticAnalyzer {
        runtime_expr_ids: nodes.expressions.keys().collect(),
        meta_expr_ids: nodes.meta_expressions.keys().collect(),
        builder_ids: nodes
            .meta_expressions
            .iter()
            .filter_map(|(id, kind)| {
                matches!(kind, ruka_frontend::MetaExprKind::BuildExpr).then_some(id)
            })
            .collect(),
        meta_stmt_ids: nodes.meta_statements.keys().collect(),
        runtime_function_names: program
            .functions
            .iter()
            .map(|function| function.name.clone())
            .collect(),
        meta_function_signatures: program
            .meta_functions
            .iter()
            .map(|function| {
                (
                    function.name.clone(),
                    function
                        .params
                        .iter()
                        .map(|param| param.ty.clone())
                        .collect(),
                )
            })
            .collect(),
        meta_function_return_types: program
            .meta_functions
            .iter()
            .map(|function| (function.name.clone(), function.return_type.clone()))
            .collect(),
        meta_function_inferred_returns: BTreeMap::new(),
        meta_function_names: program
            .meta_functions
            .iter()
            .map(|function| function.name.clone())
            .collect(),
        struct_names: program
            .structs
            .iter()
            .map(|decl| decl.name.clone())
            .collect(),
        extern_module_names: program
            .extern_modules
            .iter()
            .map(|module| module.name.clone())
            .collect(),
        next_runtime_expr: 0,
        next_meta_expr: 0,
        next_meta_stmt: 0,
        next_builder: 0,
        builder_envs: SecondaryMap::new(),
        runtime_name_resolution: SecondaryMap::new(),
        meta_name_resolution: SecondaryMap::new(),
        runtime_expr_types: SecondaryMap::new(),
        meta_expr_types: SecondaryMap::new(),
        meta_call_info: SecondaryMap::new(),
        meta_match_info: SecondaryMap::new(),
        issues: Vec::new(),
        meta_function_issues: BTreeMap::new(),
    };
    analyzer.visit_program(program);
    StagedSemanticInfo {
        nodes,
        builder_envs: analyzer.builder_envs,
        runtime_name_resolution: analyzer.runtime_name_resolution,
        meta_name_resolution: analyzer.meta_name_resolution,
        runtime_expr_types: analyzer.runtime_expr_types,
        meta_expr_types: analyzer.meta_expr_types,
        meta_call_info: analyzer.meta_call_info,
        meta_match_info: analyzer.meta_match_info,
        issues: analyzer.issues,
        meta_function_issues: analyzer.meta_function_issues,
    }
}

struct SemanticAnalyzer {
    runtime_expr_ids: Vec<ExprId>,
    meta_expr_ids: Vec<MetaExprId>,
    meta_stmt_ids: Vec<MetaStmtId>,
    builder_ids: Vec<MetaExprId>,
    runtime_function_names: Vec<String>,
    meta_function_signatures: BTreeMap<String, Vec<TypeExpr>>,
    meta_function_return_types: BTreeMap<String, TypeExpr>,
    meta_function_inferred_returns: BTreeMap<String, MetaType>,
    meta_function_names: Vec<String>,
    struct_names: Vec<String>,
    extern_module_names: Vec<String>,
    next_runtime_expr: usize,
    next_meta_expr: usize,
    next_meta_stmt: usize,
    next_builder: usize,
    builder_envs: SecondaryMap<MetaExprId, Option<Vec<BuilderBindingInfo>>>,
    runtime_name_resolution: SecondaryMap<ExprId, Option<ResolvedName>>,
    meta_name_resolution: SecondaryMap<MetaExprId, Option<ResolvedName>>,
    runtime_expr_types: SecondaryMap<ExprId, Option<TypeExpr>>,
    meta_expr_types: SecondaryMap<MetaExprId, Option<MetaType>>,
    meta_call_info: SecondaryMap<MetaExprId, Option<MetaCallInfo>>,
    meta_match_info: SecondaryMap<MetaStmtId, Option<MetaMatchInfo>>,
    issues: Vec<(MetaExprId, SemanticIssue)>,
    meta_function_issues: BTreeMap<String, SemanticIssue>,
}

impl SemanticAnalyzer {
    fn visit_program(&mut self, program: &Program) {
        self.infer_meta_function_returns(&program.meta_functions);
        for function in &program.functions {
            let mut runtime_env = function
                .params
                .iter()
                .map(|param| (param.name.clone(), Some(param.ty.ty.clone())))
                .collect::<Vec<_>>();
            let mut meta_env = Vec::new();
            self.visit_block(&function.body, &mut runtime_env, &mut meta_env);
        }
        for function in &program.meta_functions {
            let mut runtime_env = Vec::new();
            let mut meta_env = function
                .params
                .iter()
                .map(|param| {
                    (
                        param.name.clone(),
                        infer_meta_type_from_type_expr(&param.ty),
                    )
                })
                .collect::<Vec<_>>();
            self.visit_meta_block(&function.body, &mut runtime_env, &mut meta_env);
        }
    }

    fn infer_meta_function_returns(&mut self, functions: &[ruka_frontend::MetaFunctionDecl]) {
        loop {
            let mut changed = false;
            for function in functions {
                let mut meta_env = function
                    .params
                    .iter()
                    .map(|param| {
                        (
                            param.name.clone(),
                            infer_meta_type_from_type_expr(&param.ty),
                        )
                    })
                    .collect::<Vec<_>>();
                let Some(actual_return) =
                    self.infer_meta_block_result_type(&function.body, &mut meta_env)
                else {
                    continue;
                };
                let prev = self
                    .meta_function_inferred_returns
                    .insert(function.name.clone(), actual_return.clone());
                if prev.as_ref() != Some(&actual_return) {
                    changed = true;
                }
            }
            if !changed {
                break;
            }
        }

        for function in functions {
            let Some(actual_return) = self.meta_function_inferred_returns.get(&function.name)
            else {
                continue;
            };
            if meta_value_fits_type(&function.return_type, actual_return) {
                continue;
            }
            self.meta_function_issues.insert(
                function.name.clone(),
                SemanticIssue::MetaTypeMismatch {
                    expected: format_type_expr(&function.return_type),
                    actual: format_meta_type(actual_return),
                },
            );
        }
    }

    fn infer_meta_block_result_type(
        &self,
        block: &ruka_frontend::MetaBlock,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) -> Option<MetaType> {
        let mut last_value = None;
        for stmt in &block.statements {
            match stmt {
                ruka_frontend::MetaStmt::Let { name, value } => {
                    meta_env.push((
                        name.clone(),
                        self.infer_meta_expr_type_with_env(value, meta_env),
                    ));
                }
                ruka_frontend::MetaStmt::Expr { expr } => {
                    if let Some(value) = self.infer_meta_expr_type_with_env(expr, meta_env) {
                        last_value = Some(value);
                    }
                }
                ruka_frontend::MetaStmt::Match { arms, .. } => {
                    let arm_types = arms
                        .iter()
                        .map(|arm| self.infer_meta_expr_type_with_env(&arm.result, meta_env))
                        .collect::<Vec<_>>();
                    last_value = converge_meta_types(&arm_types).or(last_value);
                }
                ruka_frontend::MetaStmt::Meta { body } => {
                    if let Some(value) = self.infer_meta_block_result_type(body, meta_env) {
                        last_value = Some(value);
                    }
                }
            }
        }
        last_value
    }

    fn visit_block(
        &mut self,
        block: &ruka_frontend::Block,
        runtime_env: &mut Vec<(String, Option<TypeExpr>)>,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) {
        for stmt in &block.statements {
            self.visit_stmt(stmt, runtime_env, meta_env);
        }
    }

    fn visit_stmt(
        &mut self,
        stmt: &Stmt,
        runtime_env: &mut Vec<(String, Option<TypeExpr>)>,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) {
        match stmt {
            Stmt::Let { name, value, .. } => {
                self.visit_expr(value, runtime_env, meta_env);
                runtime_env.push((name.clone(), infer_runtime_expr_type(value)));
            }
            Stmt::Assign { value, .. } => self.visit_expr(value, runtime_env, meta_env),
            Stmt::If {
                condition,
                then_block,
                else_block,
                ..
            } => {
                self.visit_expr(condition, runtime_env, meta_env);
                let mut then_env = runtime_env.clone();
                let mut then_meta_env = meta_env.clone();
                self.visit_block(then_block, &mut then_env, &mut then_meta_env);
                if let Some(block) = else_block {
                    let mut else_env = runtime_env.clone();
                    let mut else_meta_env = meta_env.clone();
                    self.visit_block(block, &mut else_env, &mut else_meta_env);
                }
            }
            Stmt::For {
                iterable,
                body,
                binding,
            } => {
                self.visit_expr(iterable, runtime_env, meta_env);
                let mut loop_env = runtime_env.clone();
                let mut loop_meta_env = meta_env.clone();
                loop_env.push((binding.name.clone(), None));
                self.visit_block(body, &mut loop_env, &mut loop_meta_env);
            }
            Stmt::While { condition, body } => {
                self.visit_expr(condition, runtime_env, meta_env);
                let mut loop_env = runtime_env.clone();
                let mut loop_meta_env = meta_env.clone();
                self.visit_block(body, &mut loop_env, &mut loop_meta_env);
            }
            Stmt::Match { value, arms } => {
                self.visit_expr(value, runtime_env, meta_env);
                for arm in arms {
                    let mut arm_env = runtime_env.clone();
                    let mut arm_meta_env = meta_env.clone();
                    for binder in match &arm.pattern {
                        ruka_frontend::MatchPattern::Wildcard => Vec::new(),
                        ruka_frontend::MatchPattern::Variant { binders, .. } => {
                            binders.iter().filter_map(|binder| binder.clone()).collect()
                        }
                    } {
                        arm_env.push((binder.name, None));
                    }
                    self.visit_block(&arm.body, &mut arm_env, &mut arm_meta_env);
                }
            }
            Stmt::Meta { body } => self.visit_meta_block(body, runtime_env, meta_env),
            Stmt::Expr { expr, .. } => self.visit_expr(expr, runtime_env, meta_env),
        }
    }

    fn visit_expr(
        &mut self,
        expr: &Expr,
        runtime_env: &mut Vec<(String, Option<TypeExpr>)>,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) {
        let id = self.runtime_expr_ids[self.next_runtime_expr];
        self.next_runtime_expr += 1;
        self.runtime_expr_types[id] = infer_runtime_expr_type(expr);
        self.runtime_name_resolution[id] = resolve_runtime_name(
            expr,
            runtime_env,
            &self.runtime_function_names,
            &self.struct_names,
            &self.extern_module_names,
        );

        match expr {
            Expr::Array { items, .. } | Expr::Tuple { items, .. } => {
                for item in items {
                    self.visit_expr(item, runtime_env, meta_env);
                }
            }
            Expr::StructLit { fields, .. } => {
                for field in fields {
                    self.visit_expr(&field.value, runtime_env, meta_env);
                }
            }
            Expr::Call { callee, args, .. } => {
                self.visit_expr(callee, runtime_env, meta_env);
                for arg in args {
                    match arg {
                        ruka_frontend::CallArg::Expr(expr)
                        | ruka_frontend::CallArg::Spread(expr) => {
                            self.visit_expr(expr, runtime_env, meta_env)
                        }
                        ruka_frontend::CallArg::Type(_) => {}
                    }
                }
            }
            Expr::IntrinsicCall { args, .. } => {
                for arg in args {
                    match arg {
                        ruka_frontend::CallArg::Expr(expr)
                        | ruka_frontend::CallArg::Spread(expr) => {
                            self.visit_expr(expr, runtime_env, meta_env)
                        }
                        ruka_frontend::CallArg::Type(_) => {}
                    }
                }
            }
            Expr::Field { base, .. } => self.visit_expr(base, runtime_env, meta_env),
            Expr::Index { base, index } => {
                self.visit_expr(base, runtime_env, meta_env);
                self.visit_expr(index, runtime_env, meta_env);
            }
            Expr::SliceRange { base, start, end } => {
                self.visit_expr(base, runtime_env, meta_env);
                if let Some(start) = start {
                    self.visit_expr(start, runtime_env, meta_env);
                }
                if let Some(end) = end {
                    self.visit_expr(end, runtime_env, meta_env);
                }
            }
            Expr::Prefix { value, .. } => self.visit_expr(value, runtime_env, meta_env),
            Expr::Binary { lhs, rhs, .. } | Expr::Relational { lhs, rhs, .. } => {
                self.visit_expr(lhs, runtime_env, meta_env);
                self.visit_expr(rhs, runtime_env, meta_env);
            }
            Expr::Block(block) => {
                let mut block_env = runtime_env.clone();
                let mut block_meta_env = meta_env.clone();
                self.visit_block(block, &mut block_env, &mut block_meta_env);
            }
            Expr::Splice(meta_expr) => self.visit_meta_expr(meta_expr, runtime_env, meta_env),
            Expr::Ident { .. }
            | Expr::Int(_)
            | Expr::Number(_)
            | Expr::String(_)
            | Expr::Bool(_) => {}
        }
    }

    fn visit_meta_block(
        &mut self,
        block: &ruka_frontend::MetaBlock,
        runtime_env: &mut Vec<(String, Option<TypeExpr>)>,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) {
        for stmt in &block.statements {
            self.visit_meta_stmt(stmt, runtime_env, meta_env);
        }
    }

    fn visit_meta_stmt(
        &mut self,
        stmt: &ruka_frontend::MetaStmt,
        runtime_env: &mut Vec<(String, Option<TypeExpr>)>,
        meta_env: &mut Vec<(String, Option<MetaType>)>,
    ) {
        let stmt_id = self.meta_stmt_ids[self.next_meta_stmt];
        self.next_meta_stmt += 1;
        match stmt {
            ruka_frontend::MetaStmt::Let { name, value } => {
                self.meta_match_info[stmt_id] = None;
                self.visit_meta_expr(value, runtime_env, meta_env);
                meta_env.push((
                    name.clone(),
                    self.infer_meta_expr_type_with_env(value, meta_env),
                ));
            }
            ruka_frontend::MetaStmt::Match { value, arms } => {
                let matched_type = self.infer_meta_expr_type_with_env(value, meta_env);
                let arm_types = arms
                    .iter()
                    .map(|arm| self.infer_meta_expr_type_with_env(&arm.result, meta_env))
                    .collect::<Vec<_>>();
                self.meta_match_info[stmt_id] = Some(MetaMatchInfo {
                    matched_type,
                    converged_arm_type: converge_meta_types(&arm_types),
                    pattern_kinds: arms
                        .iter()
                        .map(|arm| meta_pattern_kind(&arm.pattern))
                        .collect(),
                });
                self.visit_meta_expr(value, runtime_env, meta_env);
                for arm in arms {
                    self.visit_meta_expr(&arm.result, runtime_env, meta_env);
                }
            }
            ruka_frontend::MetaStmt::Meta { body } => {
                self.meta_match_info[stmt_id] = None;
                self.visit_meta_block(body, runtime_env, meta_env)
            }
            ruka_frontend::MetaStmt::Expr { expr } => {
                self.meta_match_info[stmt_id] = None;
                self.visit_meta_expr(expr, runtime_env, meta_env)
            }
        }
    }

    fn visit_meta_expr(
        &mut self,
        expr: &MetaExpr,
        runtime_env: &[(String, Option<TypeExpr>)],
        meta_env: &[(String, Option<MetaType>)],
    ) {
        let id = self.meta_expr_ids[self.next_meta_expr];
        self.next_meta_expr += 1;
        self.meta_name_resolution[id] = resolve_meta_name(
            expr,
            meta_env,
            &self.runtime_function_names,
            &self.meta_function_names,
            &self.struct_names,
            &self.extern_module_names,
        );
        self.meta_expr_types[id] = self.infer_meta_expr_type_with_env(expr, meta_env);
        self.meta_call_info[id] = meta_call_info(expr, self.meta_expr_types[id].clone(), meta_env);
        let resolved_name = self.meta_name_resolution[id].clone();
        self.record_meta_issue(id, expr, runtime_env, resolved_name.as_ref());

        match expr {
            MetaExpr::Call { args, .. } => {
                self.record_meta_call_issues(id, expr, meta_env);
                for arg in args {
                    self.visit_meta_expr(arg, runtime_env, meta_env);
                }
            }
            MetaExpr::BuildExpr(runtime_expr) => {
                let builder_id = self.builder_ids[self.next_builder];
                self.next_builder += 1;
                self.builder_envs[builder_id] = Some(
                    runtime_env
                        .iter()
                        .map(|(name, ty)| BuilderBindingInfo {
                            name: name.clone(),
                            ty: ty.clone(),
                        })
                        .collect(),
                );
                let mut nested_env = runtime_env.to_vec();
                let mut nested_meta_env = meta_env.to_vec();
                self.visit_expr(runtime_expr, &mut nested_env, &mut nested_meta_env);
            }
            MetaExpr::Quote(quoted) => match quoted.as_ref() {
                ruka_frontend::QuotedCode::Expr(expr) => {
                    let mut nested_env = runtime_env.to_vec();
                    let mut nested_meta_env = meta_env.to_vec();
                    self.visit_expr(expr, &mut nested_env, &mut nested_meta_env);
                }
                ruka_frontend::QuotedCode::Type(_) => {}
            },
            MetaExpr::Splice(expr) => self.visit_meta_expr(expr, runtime_env, meta_env),
            MetaExpr::Ident(_)
            | MetaExpr::Int(_)
            | MetaExpr::Bool(_)
            | MetaExpr::String(_)
            | MetaExpr::Type(_) => {}
        }
    }

    fn record_meta_issue(
        &mut self,
        id: MetaExprId,
        expr: &MetaExpr,
        runtime_env: &[(String, Option<TypeExpr>)],
        resolved_name: Option<&ResolvedName>,
    ) {
        let MetaExpr::Ident(name) = expr else {
            return;
        };
        if runtime_env.iter().rev().any(|(binding, _)| binding == name) {
            self.issues.push((
                id,
                SemanticIssue::RuntimeBindingUnavailable { name: name.clone() },
            ));
            return;
        }
        match resolved_name {
            Some(ResolvedName::RuntimeFunction)
            | Some(ResolvedName::MetaFunction)
            | Some(ResolvedName::Struct)
            | Some(ResolvedName::ExternModule)
            | Some(ResolvedName::Type) => {
                self.issues.push((
                    id,
                    SemanticIssue::KnownNameNotMetaValue {
                        name: name.clone(),
                        kind: resolved_name.cloned().expect("resolved name should exist"),
                    },
                ));
            }
            Some(ResolvedName::RuntimeLocal) | Some(ResolvedName::MetaLocal) | None => {}
        }
    }

    fn record_meta_call_issues(
        &mut self,
        id: MetaExprId,
        expr: &MetaExpr,
        meta_env: &[(String, Option<MetaType>)],
    ) {
        let MetaExpr::Call { callee, args } = expr else {
            return;
        };
        let Some(param_types) = self.meta_function_signatures.get(callee) else {
            return;
        };
        for (arg, expected_ty) in args.iter().zip(param_types.iter()) {
            let Some(actual_ty) = self.infer_meta_expr_type_with_env(arg, meta_env) else {
                continue;
            };
            if meta_value_fits_type(expected_ty, &actual_ty) {
                continue;
            }
            self.issues.push((
                id,
                SemanticIssue::MetaTypeMismatch {
                    expected: format_type_expr(expected_ty),
                    actual: format_meta_type(&actual_ty),
                },
            ));
        }
    }

    fn infer_meta_expr_type_with_env(
        &self,
        expr: &MetaExpr,
        meta_env: &[(String, Option<MetaType>)],
    ) -> Option<MetaType> {
        match expr {
            MetaExpr::Ident(name) => meta_env
                .iter()
                .rev()
                .find(|(binding, _)| binding == name)
                .and_then(|(_, ty)| ty.clone()),
            MetaExpr::Call { callee, .. } => self
                .meta_function_inferred_returns
                .get(callee)
                .cloned()
                .or_else(|| {
                    self.meta_function_return_types
                        .get(callee)
                        .and_then(infer_meta_type_from_type_expr)
                }),
            _ => infer_meta_expr_type(expr),
        }
    }
}

fn resolve_runtime_name(
    expr: &Expr,
    runtime_env: &[(String, Option<TypeExpr>)],
    runtime_functions: &[String],
    structs: &[String],
    extern_modules: &[String],
) -> Option<ResolvedName> {
    let Expr::Ident { name, .. } = expr else {
        return None;
    };
    if runtime_env.iter().rev().any(|(binding, _)| binding == name) {
        Some(ResolvedName::RuntimeLocal)
    } else if runtime_functions.iter().any(|binding| binding == name) {
        Some(ResolvedName::RuntimeFunction)
    } else if structs.iter().any(|binding| binding == name) {
        Some(ResolvedName::Struct)
    } else if extern_modules.iter().any(|binding| binding == name) {
        Some(ResolvedName::ExternModule)
    } else if looks_like_type_name(name) {
        Some(ResolvedName::Type)
    } else {
        None
    }
}

fn resolve_meta_name(
    expr: &MetaExpr,
    meta_env: &[(String, Option<MetaType>)],
    runtime_functions: &[String],
    meta_functions: &[String],
    structs: &[String],
    extern_modules: &[String],
) -> Option<ResolvedName> {
    let MetaExpr::Ident(name) = expr else {
        return None;
    };
    if meta_env.iter().rev().any(|(binding, _)| binding == name) {
        Some(ResolvedName::MetaLocal)
    } else if runtime_functions.iter().any(|binding| binding == name) {
        Some(ResolvedName::RuntimeFunction)
    } else if meta_functions.iter().any(|binding| binding == name) {
        Some(ResolvedName::MetaFunction)
    } else if structs.iter().any(|binding| binding == name) {
        Some(ResolvedName::Struct)
    } else if extern_modules.iter().any(|binding| binding == name) {
        Some(ResolvedName::ExternModule)
    } else if looks_like_type_name(name) {
        Some(ResolvedName::Type)
    } else {
        None
    }
}

fn looks_like_type_name(name: &str) -> bool {
    name.chars()
        .next()
        .is_some_and(|ch| ch.is_ascii_uppercase())
}

fn infer_meta_type_from_type_expr(ty: &TypeExpr) -> Option<MetaType> {
    match ty {
        TypeExpr::Named(name) if name == "i64" => Some(MetaType::Int),
        TypeExpr::Named(name) if name == "Bool" => Some(MetaType::Bool),
        TypeExpr::Named(name) if name == "String" => Some(MetaType::String),
        TypeExpr::TypeKind => Some(MetaType::Type),
        TypeExpr::Apply { callee, args } if callee == "Expr" && args.len() == 1 => {
            Some(MetaType::Expr(args[0].clone()))
        }
        _ => None,
    }
}

fn infer_meta_expr_type(expr: &MetaExpr) -> Option<MetaType> {
    match expr {
        MetaExpr::Int(_) => Some(MetaType::Int),
        MetaExpr::Bool(_) => Some(MetaType::Bool),
        MetaExpr::String(_) => Some(MetaType::String),
        MetaExpr::Type(_) => Some(MetaType::Type),
        MetaExpr::BuildExpr(expr) => infer_runtime_expr_type(expr).map(MetaType::Expr),
        MetaExpr::Ident(_) | MetaExpr::Call { .. } | MetaExpr::Quote(_) | MetaExpr::Splice(_) => {
            None
        }
    }
}

fn meta_value_fits_type(expected_ty: &TypeExpr, actual_ty: &MetaType) -> bool {
    match actual_ty {
        MetaType::Int => {
            matches!(expected_ty, TypeExpr::Named(name) if name == "i64" || name == "any")
        }
        MetaType::Bool => {
            matches!(expected_ty, TypeExpr::Named(name) if name == "Bool" || name == "any")
        }
        MetaType::String => {
            matches!(expected_ty, TypeExpr::Named(name) if name == "String" || name == "any")
        }
        MetaType::Type => match expected_ty {
            TypeExpr::TypeKind => true,
            TypeExpr::Named(name) if name == "any" => true,
            _ => false,
        },
        MetaType::Expr(actual_expr_ty) => match expected_ty {
            TypeExpr::Named(name) if name == "any" => true,
            TypeExpr::Apply { callee, args } if callee == "Expr" && args.len() == 1 => {
                meta_types_compatible(&args[0], actual_expr_ty)
            }
            _ => false,
        },
    }
}

fn format_meta_type(ty: &MetaType) -> String {
    match ty {
        MetaType::Int => "i64".to_owned(),
        MetaType::Bool => "Bool".to_owned(),
        MetaType::String => "String".to_owned(),
        MetaType::Type => "type".to_owned(),
        MetaType::Expr(item) => format!("Expr[{}]", format_type_expr(item)),
    }
}

fn meta_call_info(
    expr: &MetaExpr,
    result_type: Option<MetaType>,
    meta_env: &[(String, Option<MetaType>)],
) -> Option<MetaCallInfo> {
    let MetaExpr::Call { callee, args } = expr else {
        return None;
    };
    let builtin_spec = builtin_spec_by_name(callee);
    let builtin = builtin_spec.map(|spec| spec.kind);
    Some(MetaCallInfo {
        callee: callee.clone(),
        builtin,
        arg_types: args
            .iter()
            .map(|arg| infer_meta_expr_type_with_env_shallow(arg, meta_env))
            .collect(),
        expected_arg_kinds: builtin_spec.map(|spec| spec.arg_kinds.to_vec()),
        result_type: result_type.or_else(|| {
            builtin.and_then(|kind| {
                builtin_result_type(
                    kind,
                    &args
                        .iter()
                        .map(|arg| infer_meta_expr_type_with_env_shallow(arg, meta_env))
                        .collect::<Vec<_>>(),
                )
            })
        }),
    })
}

fn infer_meta_expr_type_with_env_shallow(
    expr: &MetaExpr,
    meta_env: &[(String, Option<MetaType>)],
) -> Option<MetaType> {
    match expr {
        MetaExpr::Ident(name) => meta_env
            .iter()
            .rev()
            .find(|(binding, _)| binding == name)
            .and_then(|(_, ty)| ty.clone()),
        _ => infer_meta_expr_type(expr),
    }
}

fn meta_pattern_kind(pattern: &MetaMatchPattern) -> MetaPatternKind {
    match pattern {
        MetaMatchPattern::Wildcard => MetaPatternKind::Wildcard,
        MetaMatchPattern::Int(_) => MetaPatternKind::Int,
        MetaMatchPattern::Bool(_) => MetaPatternKind::Bool,
        MetaMatchPattern::String(_) => MetaPatternKind::String,
        MetaMatchPattern::Quote(_) => MetaPatternKind::Quote,
        MetaMatchPattern::Type(_) => MetaPatternKind::Type,
    }
}

fn converge_meta_types(types: &[Option<MetaType>]) -> Option<MetaType> {
    let mut iter = types.iter();
    let first = iter.next().and_then(Clone::clone)?;
    if iter.all(|ty| ty.as_ref() == Some(&first)) {
        return Some(first);
    }
    match first {
        MetaType::Expr(first_ty) => {
            if iter_all_expr_types(types, &first_ty) {
                Some(MetaType::Expr(first_ty))
            } else {
                None
            }
        }
        _ => None,
    }
}

fn iter_all_expr_types(types: &[Option<MetaType>], first_ty: &TypeExpr) -> bool {
    types.iter().all(|ty| match ty {
        Some(MetaType::Expr(item_ty)) => meta_types_compatible(first_ty, item_ty),
        _ => false,
    })
}

fn infer_runtime_expr_type(expr: &Expr) -> Option<TypeExpr> {
    match expr {
        Expr::Int(_) => Some(TypeExpr::Named("i64".to_owned())),
        Expr::Number(value) => {
            let raw = value.raw.as_str();
            let inferred = if raw.ends_with("u8") {
                "u8"
            } else if raw.ends_with("u16") {
                "u16"
            } else if raw.ends_with("u32") {
                "u32"
            } else if raw.ends_with("u64") {
                "u64"
            } else if raw.ends_with("i8") {
                "i8"
            } else if raw.ends_with("i16") {
                "i16"
            } else if raw.ends_with("i32") {
                "i32"
            } else if raw.ends_with("i64") {
                "i64"
            } else if raw.ends_with("f32") {
                "f32"
            } else if raw.ends_with("f64") || raw.contains('.') {
                "f64"
            } else {
                "i64"
            };
            Some(TypeExpr::Named(inferred.to_owned()))
        }
        Expr::Bool(_) => Some(TypeExpr::Named("Bool".to_owned())),
        Expr::String(_) => Some(TypeExpr::Named("String".to_owned())),
        Expr::Tuple { items, .. } => Some(TypeExpr::Tuple(
            items
                .iter()
                .map(infer_runtime_expr_type)
                .collect::<Option<Vec<_>>>()?,
        )),
        Expr::Array { items, .. } => {
            let item_ty = items.first().and_then(infer_runtime_expr_type)?;
            if items
                .iter()
                .all(|item| infer_runtime_expr_type(item).as_ref() == Some(&item_ty))
            {
                Some(TypeExpr::Array {
                    item: Box::new(item_ty),
                    len: items.len(),
                })
            } else {
                None
            }
        }
        Expr::Block(block) => block.statements.last().and_then(|stmt| match stmt {
            Stmt::Expr {
                expr,
                has_semi: false,
            } => infer_runtime_expr_type(expr),
            _ => None,
        }),
        Expr::Ident { .. }
        | Expr::StructLit { .. }
        | Expr::Call { .. }
        | Expr::IntrinsicCall { .. }
        | Expr::Field { .. }
        | Expr::Index { .. }
        | Expr::SliceRange { .. }
        | Expr::Prefix { .. }
        | Expr::Binary { .. }
        | Expr::Relational { .. }
        | Expr::Splice(_) => None,
    }
}

#[cfg(test)]
mod tests;