pub fn compile_program(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    program: &Program,

) -> Result<()> {

    if program.exprs.is_empty() {

        compile_nil(emit);

        return Ok(());

    }

    for expr in &program.exprs[..program.exprs.len() - 1] {

        compile_for_effect(ctx, emit, symbols, expr)?;

    compile_expr(ctx, emit, symbols, program.exprs.last().unwrap())

}

pub(super) fn compile_expr(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    expr: &Expr,

) -> Result<()> {

    match expr {

            debug!("compiling nil");

            compile_nil(emit);

            Ok(())

        Expr::Bool(b) => {

            debug!(value = b, "compiling bool");

            compile_bool(emit, *b);

            Ok(())

        Expr::Number(n) => {

            debug!(numer = *n.numer(), denom = *n.denom(), "compiling number");

            compile_number(emit, *n.numer(), *n.denom());

            Ok(())

        Expr::String(s) => {

            debug!(len = s.len(), "compiling string");

            compile_string(ctx, emit, s);

            Ok(())

        Expr::Symbol(name) => {

            debug!(symbol = %name, "resolving symbol");

            let resolved = resolve_arg(symbols, expr)?;

            compile_expr(ctx, emit, symbols, &resolved)

        Expr::Quote(inner) => {

            debug!("compiling quote");

            compile_quoted_expr(ctx, emit, inner)

        Expr::List(elems) if elems.is_empty() => {

            debug!("compiling empty list as nil");

            compile_nil(emit);

            Ok(())

        Expr::List(elems) => compile_call(ctx, emit, symbols, elems),

        Expr::Quasiquote(inner) => {

            let expanded = expand_quasiquote(symbols, inner)?;

            compile_expr(ctx, emit, symbols, &expanded)

            Err(Error::Compile("unquote outside of quasiquote".to_string()))

            if let Expr::RuntimeValue(Value::Struct { name, fields }) = expr

                && name == "TAG"

                let name_val = fields.first().cloned().unwrap_or(Value::Nil);

                let value_val = fields.get(1).cloned().unwrap_or(Value::Nil);

                let name_str = match name_val {

                    Value::String(s) => s,

                let value_str = match value_val {

                    Value::String(s) => s,

                if name_str.len() > u16::MAX as usize || value_str.len() > u16::MAX as usize {

                }

                let name_data_idx = ctx.add_data(name_str.as_bytes());

                let value_data_idx = ctx.add_data(value_str.as_bytes());

                let gc = GcLocals {

                    type_idx: ctx.type_idx("i8_array"),

                    arr: LOCAL_GC_ARR,

                    idx: LOCAL_IDX,

                };

                let mut serializer = OutputSerializer::new(LOCAL_OUTPUT_BASE);

                serializer.begin_output(emit);

                serializer.write_tag_gc(

                    emit,

                    name_data_idx,

                    name_str.len() as u32,

                    value_data_idx,

                    value_str.len() as u32,

                    &gc,

                return Ok(());

}

pub(super) fn compile_quoted_expr(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    inner: &Expr,

) -> Result<()> {

    match inner {

        Expr::Number(n) => {

            compile_number(emit, *n.numer(), *n.denom());

            Ok(())

        Expr::String(s) => {

            compile_string(ctx, emit, s);

            Ok(())

        Expr::Symbol(s) => {

            compile_symbol(ctx, emit, s);

            Ok(())

        Expr::List(elems) => {

            let s = format!(

                elems.iter().map(format_expr).collect::<Vec<_>>().join(" ")

            compile_string(ctx, emit, &s);

            Ok(())

}

pub(super) fn compile_nil(emit: &mut FunctionEmitter) {

    let mut serializer = OutputSerializer::new(LOCAL_OUTPUT_BASE);

    serializer.begin_output(emit);

    serializer.write_debug_nil(emit);

}

pub(super) fn compile_bool(emit: &mut FunctionEmitter, value: bool) {

    let mut serializer = OutputSerializer::new(LOCAL_OUTPUT_BASE);

    serializer.begin_output(emit);

    serializer.write_debug_bool(emit, value);

}

pub(super) fn compile_number(emit: &mut FunctionEmitter, numer: i64, denom: i64) {

    let mut serializer = OutputSerializer::new(LOCAL_OUTPUT_BASE);

    serializer.begin_output(emit);

    serializer.write_debug_number(emit, numer, denom);

}

fn compile_text(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    value_type: ValueType,

    s: &str,

) {

    let data_idx = ctx.add_data(s.as_bytes());

    let gc = GcLocals {

        type_idx: ctx.type_idx("i8_array"),

        arr: LOCAL_GC_ARR,

        idx: LOCAL_IDX,

    };

    let mut serializer = OutputSerializer::new(LOCAL_OUTPUT_BASE);

    serializer.begin_output(emit);

    serializer.write_debug_string_gc(emit, value_type, data_idx, s.len() as u32, &gc);

}

pub(super) fn compile_string(ctx: &mut CompileContext, emit: &mut FunctionEmitter, s: &str) {

    compile_text(ctx, emit, ValueType::String, s);

}

pub(super) fn compile_symbol(ctx: &mut CompileContext, emit: &mut FunctionEmitter, s: &str) {

    compile_text(ctx, emit, ValueType::Symbol, s);

}

pub(crate) fn call(symbols: &mut SymbolTable, elems: &[Expr]) -> Result<Expr> {

    let (head, args) = elems

        .split_first()

        .ok_or_else(|| Error::Compile("empty function call".to_string()))?;

    match head {

        Expr::Symbol(name) => dispatch_symbol(symbols, name, args),

        Expr::Quote(inner) => match inner.as_ref() {

            Expr::Symbol(name) => dispatch_symbol(symbols, name, args),

        Expr::Lambda(params, body) => call_lambda(symbols, params, body, args),

        Expr::List(inner) => {

            let resolved = call(symbols, inner)?;

            match resolved {

                Expr::Lambda(params, body) => call_lambda(symbols, &params, &body, args),

}

pub(crate) fn eval_value(symbols: &mut SymbolTable, expr: &Expr) -> Result<Expr> {

    match expr {

        Expr::List(elems) if !elems.is_empty() => call(symbols, elems),

        _ => resolve_arg(symbols, expr),

}

fn dispatch_symbol(symbols: &mut SymbolTable, name: &str, args: &[Expr]) -> Result<Expr> {

    let (func, kind) = {

        let sym = symbols

            .lookup(name)

            .ok_or_else(|| Error::UndefinedSymbol(name.to_string()))?;

        (sym.function().cloned(), sym.kind())

    if kind == SymbolKind::Macro

        && let Some(Expr::Lambda(params, body)) = func

        let expansion = expand_macro(symbols, &params, &body, args)?;

        let code = match expansion {

            Expr::Quote(inner) => *inner,

            other => other,

        return eval_value(symbols, &code);

    }

    if let Some(Expr::Lambda(params, body)) = func {

        return call_lambda(symbols, &params, &body, args);

    }

    match kind {

        SymbolKind::Native | SymbolKind::Operator => super::native::call(symbols, name, args),

        SymbolKind::SpecialForm => super::special::call(symbols, name, args),

}

pub(crate) fn expand_macro(

    symbols: &mut SymbolTable,

    params: &LambdaParams,

    body: &Expr,

    args: &[Expr],

) -> Result<Expr> {

    if !params.aux.is_empty() {

    }

    let min_args = params.required.len();

    let max_args = if params.rest.is_some() || !params.key.is_empty() {

        None

        Some(min_args + params.optional.len())

    if args.len() < min_args || max_args.is_some_and(|max| args.len() > max) {

        return Err(Error::Arity {

            name: "macro".to_string(),

            expected: min_args,

            actual: args.len(),

        });

    }

    let mut local_symbols = symbols.clone();

    let mut arg_idx = 0;

    for param in &params.required {

        local_symbols

            .define(Symbol::new(param, SymbolKind::Variable).with_value(args[arg_idx].clone()));

        arg_idx += 1;

    }

    for (param, default) in &params.optional {

    if let Some(rest_param) = &params.rest {

        let rest = Expr::Quote(Box::new(Expr::List(args[arg_idx..].to_vec())));

        local_symbols.define(Symbol::new(rest_param, SymbolKind::Variable).with_value(rest));

    }

    if !params.key.is_empty() {

        let remaining_args = &args[arg_idx..];

        for (param, default) in &params.key {

            let keyword = Expr::Keyword(param.to_uppercase());

            let mut found_value = None;

            for i in (0..remaining_args.len() - 1).step_by(2) {

                if remaining_args[i] == keyword {

                    found_value = Some(remaining_args[i + 1].clone());

                    break;

            let value = if let Some(val) = found_value {

                val

            local_symbols.define(Symbol::new(param, SymbolKind::Variable).with_value(value));

    }

    eval_value(&mut local_symbols, body)

}

fn call_lambda(

    symbols: &mut SymbolTable,

    params: &LambdaParams,

    body: &Expr,

    args: &[Expr],

) -> Result<Expr> {

    let min_args = params.required.len();

    let max_args = if params.rest.is_some() || !params.key.is_empty() {

        None

        Some(min_args + params.optional.len())

    if args.len() < min_args {

    }

    if let Some(max) = max_args

        && args.len() > max

    }

    let mut local_symbols = symbols.clone();

    let mut arg_idx = 0;

    for param in &params.required {

        let resolved = eval_value(symbols, &args[arg_idx])?;

        local_symbols.define(Symbol::new(param, SymbolKind::Variable).with_value(resolved));

        arg_idx += 1;

    for (param, default) in &params.optional {

        let value = if arg_idx < args.len() {

            eval_value(symbols, &args[arg_idx])?

        } else if let Some(default_expr) = default {

            eval_value(symbols, default_expr)?

            Expr::Nil

        local_symbols.define(Symbol::new(param, SymbolKind::Variable).with_value(value));

        if arg_idx < args.len() {

            arg_idx += 1;

        }

    if let Some(rest_param) = &params.rest {

        let rest_args: Vec<Expr> = args[arg_idx..]

            .iter()

            .map(|arg| eval_value(symbols, arg))

            .collect::<Result<_>>()?;

        let rest_list = if rest_args.is_empty() {

            Expr::Nil

            Expr::List(rest_args)

        local_symbols.define(Symbol::new(rest_param, SymbolKind::Variable).with_value(rest_list));

    }

    if !params.key.is_empty() {

        let remaining_args = &args[arg_idx..];

        for (param, default) in &params.key {

            let keyword = Expr::Keyword(param.to_uppercase());

            let mut found_value = None;

            if remaining_args.len() >= 2 {

                for i in (0..remaining_args.len() - 1).step_by(2) {

                    if remaining_args[i] == keyword {

                        found_value = Some(eval_value(symbols, &remaining_args[i + 1])?);

                        break;

                    }

            }

            let value = if let Some(val) = found_value {

                val

            } else if let Some(default_expr) = default {

                Expr::Nil

            local_symbols.define(Symbol::new(param, SymbolKind::Variable).with_value(value));

    }

    for (param, init) in &params.aux {

        let value = if let Some(init_expr) = init {

            eval_value(&mut local_symbols, init_expr)?

        local_symbols.define(Symbol::new(param, SymbolKind::Variable).with_value(value));

    eval_value(&mut local_symbols, body)

}

pub(super) fn compile_body(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    body: &[Expr],

) -> Result<()> {

    for expr in &body[..body.len() - 1] {

        compile_for_effect(ctx, emit, symbols, expr)?;

    compile_expr(ctx, emit, symbols, body.last().unwrap())

}

pub(super) fn compile_for_effect(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    expr: &Expr,

) -> Result<()> {

    match expr {

        Expr::List(elems) if matches!(elems.first(), Some(Expr::Symbol(s)) if s == "DEBUG") => {

            super::native::compile_debug_effect(ctx, emit, symbols, &elems[1..])

            let _ = (ctx, emit);

            eval_value(symbols, expr)?;

            Ok(())

}

pub(super) fn compile_call(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    elems: &[Expr],

) -> Result<()> {

    let (head, args) = elems

        .split_first()

        .ok_or_else(|| Error::Compile("empty function call".to_string()))?;

    match head {

        Expr::Symbol(name) => compile_symbol_call(ctx, emit, symbols, name, args),

        Expr::Quote(inner) => match inner.as_ref() {

            Expr::Symbol(name) => compile_symbol_call(ctx, emit, symbols, name, args),

        Expr::List(inner) => {

            let resolved = call(symbols, inner)?;

            match resolved {

                Expr::Lambda(params, body) => {

                    compile_lambda_call(ctx, emit, symbols, &params, &body, args)

}

fn compile_symbol_call(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    name: &str,

    args: &[Expr],

) -> Result<()> {

    let (func, kind) = {

        let sym = symbols

            .lookup(name)

            .ok_or_else(|| Error::UndefinedSymbol(name.to_string()))?;

        (sym.function().cloned(), sym.kind())

    if kind == SymbolKind::Macro

        && let Some(Expr::Lambda(params, body)) = func

        let expansion = expand_macro(symbols, &params, &body, args)?;

        let code = match expansion {

            Expr::Quote(inner) => *inner,

            other => other,

        return compile_expr(ctx, emit, symbols, &code);

    }

    if let Some(Expr::Lambda(params, body)) = func {

        return compile_lambda_call(ctx, emit, symbols, &params, &body, args);

    }

    match kind {

            super::native::compile(ctx, emit, symbols, name, args)

        SymbolKind::SpecialForm => super::special::compile(ctx, emit, symbols, name, args),

}

fn compile_lambda_call(

    ctx: &mut CompileContext,

    emit: &mut FunctionEmitter,

    symbols: &mut SymbolTable,

    params: &LambdaParams,

    body: &Expr,

    args: &[Expr],

) -> Result<()> {

    let min_args = params.required.len();

    let max_args = if params.rest.is_some() || !params.key.is_empty() {

        None

        Some(min_args + params.optional.len())

    if args.len() < min_args {

        return Err(Error::Arity {

            name: "lambda".to_string(),

            expected: min_args,

            actual: args.len(),

        });

    }

    if let Some(max) = max_args

        && args.len() > max

    }

    let mut local = symbols.clone();

    let mut arg_idx = 0;

    for param in &params.required {

        let resolved = eval_value(symbols, &args[arg_idx])?;

        local.define(Symbol::new(param, SymbolKind::Variable).with_value(resolved));

        arg_idx += 1;

    for (param, default) in &params.optional {

    if let Some(rest_param) = &params.rest {

    }

    if !params.key.is_empty() {

        let remaining_args = &args[arg_idx..];

        for (param, default) in &params.key {

            let keyword = Expr::Keyword(param.to_uppercase());

            let mut found_value = None;

            if remaining_args.len() >= 2 {

                for i in (0..remaining_args.len() - 1).step_by(2) {

                    if remaining_args[i] == keyword {

                        found_value = Some(eval_value(symbols, &remaining_args[i + 1])?);

                        break;

                    }

            let value = if let Some(val) = found_value {

                val

            local.define(Symbol::new(param, SymbolKind::Variable).with_value(value));

    }

    for (param, init) in &params.aux {

    compile_expr(ctx, emit, &mut local, body)

}

fn expand_quasiquote(symbols: &mut SymbolTable, expr: &Expr) -> Result<Expr> {

    fn splice_elements(resolved: Expr) -> Result<Vec<Expr>> {

        match resolved {

            Expr::Quote(inner) => match *inner {

                Expr::List(elems) => Ok(elems),

    }

    fn quasiquote_data(symbols: &mut SymbolTable, expr: &Expr) -> Result<Expr> {

        match expr {

            Expr::Unquote(inner) => resolve_arg(symbols, inner),

            Expr::List(elems) => {

                let mut resolved: Vec<Expr> = Vec::new();

                for elem in elems {

                    match elem {

                        Expr::UnquoteSplicing(inner) => {

                            let spliced = resolve_arg(symbols, inner)?;

                            resolved.extend(splice_elements(spliced)?);

                        _ => resolved.push(quasiquote_data(symbols, elem)?),

                Ok(Expr::List(resolved))

            _ => Ok(expr.clone()),

    }

    Ok(Expr::Quote(Box::new(quasiquote_data(symbols, expr)?)))

}

pub(crate) fn resolve_arg(symbols: &mut SymbolTable, expr: &Expr) -> Result<Expr> {

    match expr {

        | Expr::RuntimeValue(_) => Ok(expr.clone()),

        Expr::Cons(_, _) | Expr::List(_) => Ok(expr.clone()),

        Expr::Quasiquote(inner) => expand_quasiquote(symbols, inner),

        Expr::Symbol(name) => {

            let (value, kind, has_fn) = {

                let sym = symbols

                    .lookup(name)

                    .ok_or_else(|| Error::UndefinedSymbol(name.clone()))?;

                (sym.value().cloned(), sym.kind(), sym.function().is_some())

            if let Some(value) = value {

                return resolve_arg(symbols, &value);

            }

                SymbolKind::Native | SymbolKind::Operator => Err(Error::Compile(format!(

                    "'{name}' is a function and cannot be used as a value"

                ))),

                SymbolKind::SpecialForm => Err(Error::Compile(format!(

                    "'{name}' is a special form and cannot be used as a value"

                ))),

                SymbolKind::Macro => Err(Error::Compile(format!(

                    "'{name}' is a macro and cannot be used as a value"

                ))),

}

pub(crate) fn format_expr(expr: &Expr) -> String {

    match expr {

        Expr::Bool(true) => "#T".to_string(),

        Expr::Number(n) if *n.denom() == 1 => n.numer().to_string(),

        Expr::String(s) => s.clone(),

        Expr::Symbol(s) => s.clone(),

        Expr::List(elems) => {

            let inner: Vec<_> = elems.iter().map(format_expr).collect();

            format!("({})", inner.join(" "))

        Expr::Quote(e) => format!("'{}", format_expr(e)),

        Expr::Lambda(params, body) => {

            format!(

                format_lambda_params(params),

                format_expr(body)

        Expr::RuntimeValue(val) => format_runtime_value(val),

}

fn format_runtime_value(val: &Value) -> String {

    match val {

        Value::Nil => "NIL".to_string(),

        Value::Bool(false) => "NIL".to_string(),

        Value::Number(n) if *n.denom() == 1 => n.numer().to_string(),

        Value::String(s) => format!("\"{s}\""),

        Value::Struct { name, fields } => {

            let field_strs: Vec<_> = fields.iter().map(format_runtime_value).collect();

            format!("#S({name} {})", field_strs.join(" "))

}

fn format_lambda_params(params: &LambdaParams) -> String {

    let mut parts = Vec::new();

    parts.extend(params.required.iter().cloned());

    if !params.optional.is_empty() {

    }

    if let Some(rest) = &params.rest {

    }

    if !params.key.is_empty() {

    }

    if !params.aux.is_empty() {

    }

    parts.join(" ")

}