//! WebAssembly codegen from monomorphised MIR.
//!
//! # Value representation
//!
//! | Gleam type | Wasm |
//! |------------|------|
//! | `Int`      | `i64` |
//! | `Bool`     | `i32` (`0` / `1`) |
//! | `Float`    | `f64` |
//! | `String`   | `i32` pointer to `{ len: u32, data: [u8; len] }` in linear memory |
//!
//! String literals are placed in the data segment. Concatenation allocates new
//! objects with a simple bump allocator (`$gleam_heap_ptr` global).
//!
//! # Running with wasmtime
//!
//! If the module defines a zero-argument `main`, the backend also emits a WASI
//! `_start` entry that calls `main` and prints the result to stdout via
//! `wasi_snapshot_preview1::fd_write`. Run with:
//!
//! ```text
//! wasmtime path/to/package.wasm
//! ```

use std::collections::HashMap;

use ecow::EcoString;
use num_bigint::BigInt;
use num_traits::ToPrimitive;
use wasm_encoder::{
    BlockType, CodeSection, ConstExpr, DataSection, EntityType, ExportKind, ExportSection,
    Function, FunctionSection, GlobalSection, GlobalType, Ieee64, ImportSection, MemArg,
    MemorySection, MemoryType, Module, TypeSection, ValType,
};

use crate::wasm::mir::ast::{self, CompleteType, Expression};

pub mod mir;
pub mod zed;

/// Bytes reserved at the start of linear memory for WASI iovecs and itoa.
/// Layout:
/// - `0..8`   — `ciovec { buf: i32, len: i32 }`
/// - `8..12`  — `nwritten: i32`
/// - `16..56` — decimal formatting buffer
const SCRATCH_SIZE: u32 = 64;
const SCRATCH_IOV: u32 = 0;
const SCRATCH_NWRITTEN: u32 = 8;
const SCRATCH_ITOA_END: u32 = 56;

/// Compile a monomorphised MIR module into a WebAssembly binary.
pub fn compile(module: ast::Module<CompleteType>) -> Vec<u8> {
    Compiler::new(&module).compile()
}

/// Merge monomorphised modules into a single package module.
///
/// Cross-module calls become same-module calls with mangled names
/// (`{module}__{function}`), so the backend can emit one linked Wasm artifact.
pub fn link_package(modules: Vec<ast::Module<CompleteType>>) -> ast::Module<CompleteType> {
    use ecow::eco_format;

    let package_name = modules
        .first()
        .map(|module| module.name.clone())
        .unwrap_or_else(|| "package".into());

    let mut linked = ast::Module {
        name: package_name,
        functions: Vec::new(),
    };

    for module in modules {
        for mut function in module.functions {
            function.name = eco_format!("{}__{}", module.name, function.name);
            if let Some(body) = &mut function.body {
                mangle_function_refs(body);
            }
            linked.functions.push(function);
        }
    }

    linked
}

fn mangle_function_refs(expression: &mut Expression<CompleteType>) {
    use ecow::eco_format;

    match expression {
        Expression::FunctionRef { module, name, .. } => {
            *name = eco_format!("{}__{}", module, name);
            *module = "".into();
        }
        Expression::Block(expressions) => {
            for expression in expressions {
                mangle_function_refs(expression);
            }
        }
        Expression::Set { value, .. }
        | Expression::TupleAccess { value, .. }
        | Expression::StructTag { value }
        | Expression::StructAccess { value, .. } => mangle_function_refs(value),
        Expression::Equals { lhs, rhs }
        | Expression::NotEquals { lhs, rhs }
        | Expression::IntGt { lhs, rhs }
        | Expression::IntGtEq { lhs, rhs }
        | Expression::IntLt { lhs, rhs }
        | Expression::IntLtEq { lhs, rhs }
        | Expression::IntAdd { lhs, rhs }
        | Expression::IntSub { lhs, rhs }
        | Expression::IntMul { lhs, rhs }
        | Expression::IntDiv { lhs, rhs }
        | Expression::IntRem { lhs, rhs }
        | Expression::FloatGt { lhs, rhs }
        | Expression::FloatGtEq { lhs, rhs }
        | Expression::FloatLt { lhs, rhs }
        | Expression::FloatLtEq { lhs, rhs }
        | Expression::FloatAdd { lhs, rhs }
        | Expression::FloatSub { lhs, rhs }
        | Expression::FloatMul { lhs, rhs }
        | Expression::FloatDiv { lhs, rhs }
        | Expression::StringConcat { lhs, rhs } => {
            mangle_function_refs(lhs);
            mangle_function_refs(rhs);
        }
        Expression::If { cond, then, else_ } => {
            mangle_function_refs(cond);
            mangle_function_refs(then);
            mangle_function_refs(else_);
        }
        Expression::Call { target, args, .. } => {
            mangle_function_refs(target);
            for arg in args {
                mangle_function_refs(arg);
            }
        }
        Expression::List { items, tail, .. } => {
            for item in items {
                mangle_function_refs(item);
            }
            if let Some(tail) = tail {
                mangle_function_refs(tail);
            }
        }
        Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
            for item in items {
                mangle_function_refs(item);
            }
        }
        Expression::Var(_)
        | Expression::Int { .. }
        | Expression::Float { .. }
        | Expression::Bool { .. }
        | Expression::String { .. }
        | Expression::Panic { .. } => {}
    }
}

/// Indices of synthesised runtime helpers (only present when strings are used).
struct StringRuntime {
    alloc: u32,
    concat: u32,
    eq: u32,
}

/// WASI command entry for modules that export a zero-arg `main`.
struct WasiEntry {
    /// Imported `fd_write` function index (always 0 when present).
    fd_write: u32,
    main_index: u32,
    main_return: CompleteType,
    print_string: u32,
    print_i64: u32,
    start: u32,
    newline_offset: u32,
}

struct Compiler<'a> {
    module: &'a ast::Module<CompleteType>,
    /// Function name → Wasm function index (including imports).
    function_indices: HashMap<EcoString, u32>,
    /// Unique string literal → data offset of its heap object.
    string_offsets: HashMap<EcoString, u32>,
    /// Raw bytes written into the active data segment (starting at address 0).
    static_data: Vec<u8>,
    /// First free heap address after static data (4-byte aligned).
    heap_start: u32,
    /// Offset of the interned empty string (valid pointer for dummies).
    empty_string_offset: u32,
    string_runtime: Option<StringRuntime>,
    wasi_entry: Option<WasiEntry>,
    /// Number of imported functions (shifts defined-function indices).
    import_func_count: u32,
}

impl<'a> Compiler<'a> {
    fn new(module: &'a ast::Module<CompleteType>) -> Self {
        let main = module.functions.iter().find(|function| {
            is_main_function(&function.name)
                && function.parameters.is_empty()
                && function.external_wasm.is_none()
                && function.body.is_some()
        });
        let emit_wasi = main.is_some();
        let needs_heap = module_needs_heap(module) || module_uses_strings(module) || emit_wasi;
        let uses_strings = module_uses_strings(module) || emit_wasi;

        // Import order: optional WASI fd_write, then `@external(wasm, …)` functions.
        let external_functions: Vec<_> = module
            .functions
            .iter()
            .filter(|function| function.external_wasm.is_some())
            .collect();
        let defined_functions: Vec<_> = module
            .functions
            .iter()
            .filter(|function| function.external_wasm.is_none())
            .collect();

        let import_func_count = u32::from(emit_wasi) + external_functions.len() as u32;

        let mut function_indices = HashMap::new();
        let mut next_index = u32::from(emit_wasi);
        for function in &external_functions {
            _ = function_indices.insert(function.name.clone(), next_index);
            next_index += 1;
        }
        for function in &defined_functions {
            _ = function_indices.insert(function.name.clone(), next_index);
            next_index += 1;
        }

        let mut compiler = Self {
            module,
            function_indices,
            string_offsets: HashMap::new(),
            static_data: Vec::new(),
            heap_start: 0,
            empty_string_offset: 0,
            string_runtime: None,
            wasi_entry: None,
            import_func_count,
        };

        if needs_heap {
            // Reserve scratch so string objects never overlap WASI temp space.
            compiler.static_data.resize(SCRATCH_SIZE as usize, 0);
        }

        // Intern every static string *before* freezing `heap_start`, including
        // the WASI newline, so bump-allocation cannot overwrite them.
        let mut newline_offset = 0u32;
        if uses_strings {
            compiler.empty_string_offset = compiler.intern_string("");
            for function in &module.functions {
                if let Some(body) = &function.body {
                    collect_strings_from_expression(body, &mut |value| {
                        let _ = compiler.intern_string(value);
                    });
                }
            }
        }
        if emit_wasi {
            newline_offset = compiler.intern_string("\n");
        }

        if needs_heap {
            compiler.heap_start = align4(compiler.static_data.len() as u32);
        }

        if needs_heap {
            let base = import_func_count + defined_functions.len() as u32;
            compiler.string_runtime = Some(StringRuntime {
                alloc: base,
                concat: base + 1,
                eq: base + 2,
            });
        }

        if emit_wasi {
            let main = main.expect("main checked above");
            let mut next = import_func_count + defined_functions.len() as u32;
            if compiler.string_runtime.is_some() {
                next += 3;
            }
            let print_string = next;
            let print_i64 = next + 1;
            let start = next + 2;
            compiler.wasi_entry = Some(WasiEntry {
                fd_write: 0,
                main_index: *compiler
                    .function_indices
                    .get(&main.name)
                    .expect("main index"),
                main_return: main.return_type.clone(),
                print_string,
                print_i64,
                start,
                newline_offset,
            });
        }

        compiler
    }

    fn intern_string(&mut self, value: &str) -> u32 {
        if let Some(&offset) = self.string_offsets.get(value) {
            return offset;
        }

        let offset = align4(self.static_data.len() as u32);
        self.static_data.resize(offset as usize, 0);

        let bytes = value.as_bytes();
        let len = bytes.len() as u32;
        self.static_data.extend_from_slice(&len.to_le_bytes());
        self.static_data.extend_from_slice(bytes);

        _ = self.string_offsets.insert(value.into(), offset);
        offset
    }

    fn compile(self) -> Vec<u8> {
        let mut wasm = Module::new();

        let mut types = TypeSection::new();
        let mut imports = ImportSection::new();
        let mut functions = FunctionSection::new();
        let mut exports = ExportSection::new();
        let mut codes = CodeSection::new();

        // Predeclare the fd_write type if we need WASI (type index 0).
        let fd_write_type = if self.wasi_entry.is_some() {
            let _ = types.ty().function(
                vec![ValType::I32, ValType::I32, ValType::I32, ValType::I32],
                vec![ValType::I32],
            );
            Some(0u32)
        } else {
            None
        };

        if let Some(fd_type) = fd_write_type {
            let _ = imports.import(
                "wasi_snapshot_preview1",
                "fd_write",
                EntityType::Function(fd_type),
            );
        }

        // External Wasm imports (function types, then import entries).
        for function in self
            .module
            .functions
            .iter()
            .filter(|function| function.external_wasm.is_some())
        {
            let params: Vec<ValType> = function
                .parameters
                .iter()
                .map(|parameter| val_type(&parameter.type_))
                .collect();
            let results = vec![val_type(&function.return_type)];
            let type_index = types.len();
            let _ = types.ty().function(params, results);
            let (module_name, func_name) = function
                .external_wasm
                .as_ref()
                .expect("filtered to external");
            let _ = imports.import(
                module_name.as_str(),
                func_name.as_str(),
                EntityType::Function(type_index),
            );
        }

        // Defined user functions.
        for function in self
            .module
            .functions
            .iter()
            .filter(|function| function.external_wasm.is_none())
        {
            let params: Vec<ValType> = function
                .parameters
                .iter()
                .map(|parameter| val_type(&parameter.type_))
                .collect();
            let results = vec![val_type(&function.return_type)];
            let type_index = types.len();
            let _ = types.ty().function(params, results);
            let _ = functions.function(type_index);
            let wasm_index = *self
                .function_indices
                .get(&function.name)
                .expect("defined function index");
            let _ = exports.export(&function.name, ExportKind::Func, wasm_index);
            let _ = codes.function(&self.compile_function(function));
        }

        // String / heap runtime helpers.
        if let Some(runtime) = &self.string_runtime {
            let alloc_ty = types.len();
            let _ = types.ty().function(vec![ValType::I32], vec![ValType::I32]);
            let _ = functions.function(alloc_ty);

            let concat_ty = types.len();
            let _ = types
                .ty()
                .function(vec![ValType::I32, ValType::I32], vec![ValType::I32]);
            let _ = functions.function(concat_ty);

            let eq_ty = types.len();
            let _ = types
                .ty()
                .function(vec![ValType::I32, ValType::I32], vec![ValType::I32]);
            let _ = functions.function(eq_ty);

            let _ = codes.function(&compile_alloc());
            let _ = codes.function(&compile_string_concat(runtime.alloc));
            let _ = codes.function(&compile_string_eq());
        }

        // WASI print helpers + _start.
        if let Some(entry) = &self.wasi_entry {
            let print_string_ty = types.len();
            let _ = types.ty().function(vec![ValType::I32], vec![]);
            let _ = functions.function(print_string_ty);

            let print_i64_ty = types.len();
            let _ = types.ty().function(vec![ValType::I64], vec![]);
            let _ = functions.function(print_i64_ty);

            let start_ty = types.len();
            let _ = types.ty().function(vec![], vec![]);
            let _ = functions.function(start_ty);

            let _ = codes.function(&compile_print_string(entry.fd_write));
            let _ = codes.function(&compile_print_i64(entry.fd_write));
            let _ = codes.function(&compile_start(entry));
            let _ = exports.export("_start", ExportKind::Func, entry.start);
        }

        let needs_memory = self.string_runtime.is_some() || self.wasi_entry.is_some();

        let _ = wasm.section(&types);
        if !imports.is_empty() {
            let _ = wasm.section(&imports);
        }
        let _ = wasm.section(&functions);

        if needs_memory {
            let mut memories = MemorySection::new();
            let _ = memories.memory(MemoryType {
                minimum: 1,
                maximum: None,
                memory64: false,
                shared: false,
                page_size_log2: None,
            });
            let _ = wasm.section(&memories);

            if self.string_runtime.is_some() {
                let mut globals = GlobalSection::new();
                let _ = globals.global(
                    GlobalType {
                        val_type: ValType::I32,
                        mutable: true,
                        shared: false,
                    },
                    &ConstExpr::i32_const(self.heap_start as i32),
                );
                let _ = wasm.section(&globals);
            }

            let _ = exports.export("memory", ExportKind::Memory, 0);
        }

        let _ = wasm.section(&exports);
        let _ = wasm.section(&codes);

        if needs_memory && !self.static_data.is_empty() {
            let mut data = DataSection::new();
            let _ = data.active(
                0,
                &ConstExpr::i32_const(0),
                self.static_data.iter().copied(),
            );
            let _ = wasm.section(&data);
        }

        wasm.finish()
    }

    fn compile_function(&self, function: &ast::Function<CompleteType>) -> Function {
        let body_expr = function
            .body
            .as_ref()
            .expect("defined function has a body");
        let mut locals = LocalAllocator::new(function);
        locals.collect_from_expression(body_expr);
        locals.reserve_tmps();

        let mut body = Function::new_with_locals_types(locals.extra_locals.iter().copied());
        self.emit_expression(&mut body, &mut locals, body_expr);
        let _ = body.instructions().end();
        body
    }

    fn emit_expression(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        expression: &Expression<CompleteType>,
    ) {
        match expression {
            Expression::Block(expressions) => {
                assert!(
                    !expressions.is_empty(),
                    "MIR blocks must contain at least one expression"
                );
                let last = expressions.len() - 1;
                for (index, expression) in expressions.iter().enumerate() {
                    match expression {
                        Expression::Set { name, value } => {
                            self.emit_expression(body, locals, value);
                            let local = locals.index(&name.name);
                            if index == last {
                                let _ = body.instructions().local_tee(local);
                            } else {
                                let _ = body.instructions().local_set(local);
                            }
                        }
                        other => {
                            self.emit_expression(body, locals, other);
                            if index != last {
                                let _ = body.instructions().drop();
                            }
                        }
                    }
                }
            }

            Expression::FunctionRef { .. } => {
                panic!("bare function references are not supported in Wasm yet")
            }

            Expression::Var(var) => {
                let local = locals.index(&var.name);
                let _ = body.instructions().local_get(local);
            }

            Expression::Int { value } => {
                let _ = body.instructions().i64_const(bigint_to_i64(value));
            }

            Expression::Float { value } => {
                let float: f64 = value
                    .parse()
                    .unwrap_or_else(|_| panic!("invalid float literal: {value}"));
                let _ = body.instructions().f64_const(Ieee64::from(float));
            }

            Expression::Bool { value } => {
                let _ = body.instructions().i32_const(i32::from(*value));
            }

            Expression::String { value } => {
                let offset = self
                    .string_offsets
                    .get(value)
                    .unwrap_or_else(|| panic!("string literal was not interned: {value:?}"));
                let _ = body.instructions().i32_const(*offset as i32);
            }

            Expression::Equals { lhs, rhs } => {
                self.emit_eq(body, locals, lhs, rhs, true);
            }

            Expression::NotEquals { lhs, rhs } => {
                self.emit_eq(body, locals, lhs, rhs, false);
            }

            Expression::IntGt { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_gt_s();
                });
            }
            Expression::IntGtEq { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_ge_s();
                });
            }
            Expression::IntLt { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_lt_s();
                });
            }
            Expression::IntLtEq { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_le_s();
                });
            }
            Expression::IntAdd { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_add();
                });
            }
            Expression::IntSub { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_sub();
                });
            }
            Expression::IntMul { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_mul();
                });
            }
            Expression::IntDiv { lhs, rhs } => {
                // Gleam integer division truncates toward zero.
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_div_s();
                });
            }
            Expression::IntRem { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().i64_rem_s();
                });
            }

            Expression::FloatGt { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_gt();
                });
            }
            Expression::FloatGtEq { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_ge();
                });
            }
            Expression::FloatLt { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_lt();
                });
            }
            Expression::FloatLtEq { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_le();
                });
            }
            Expression::FloatAdd { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_add();
                });
            }
            Expression::FloatSub { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_sub();
                });
            }
            Expression::FloatMul { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_mul();
                });
            }
            Expression::FloatDiv { lhs, rhs } => {
                self.emit_binary(body, locals, lhs, rhs, |b| {
                    let _ = b.instructions().f64_div();
                });
            }

            Expression::StringConcat { lhs, rhs } => {
                let runtime = self
                    .string_runtime
                    .as_ref()
                    .expect("string runtime required for concatenation");
                self.emit_expression(body, locals, lhs);
                self.emit_expression(body, locals, rhs);
                let _ = body.instructions().call(runtime.concat);
            }

            Expression::List { items, tail, type_ } => {
                self.emit_list(body, locals, items, tail.as_deref(), type_);
            }

            Expression::Tuple { items, type_ } => {
                // Tuples share the struct layout with tag 0.
                self.emit_struct(body, locals, 0, items, type_);
            }

            Expression::TupleAccess { value, index, type_ } => {
                self.emit_expression(body, locals, value);
                // Tuple fields start at offset 4 (after tag).
                let offset = 4 + *index * 4;
                self.emit_field_load(body, locals, type_, offset);
            }

            Expression::Struct { tag, items, type_ } => {
                self.emit_struct(body, locals, *tag, items, type_);
            }

            Expression::StructTag { value } => {
                // Lists use the null pointer as empty; treat pointer 0 as tag 0
                // is wrong for tag load — StructTag is only used on records.
                // For lists empty-check we compare pointers, not tags.
                // Loading tag at offset 0:
                self.emit_expression(body, locals, value);
                // Convert to i64 so Equals with Int tags type-checks on the stack
                // as the MIR type of StructTag is Int.
                let tmp = locals.alloc_tmp(ValType::I32);
                let _ = body.instructions().local_tee(tmp);
                let _ = body.instructions().i32_load(mem_arg(0, 2));
                let _ = body.instructions().i64_extend_i32_u();
                let _ = tmp; // keep tmp live for tee side-effect only
            }

            Expression::StructAccess {
                value,
                index,
                type_,
            } => {
                self.emit_expression(body, locals, value);
                match value.type_() {
                    CompleteType::List(_) => {
                        // Cons cell: head @0, tail @4 (no tag).
                        let offset = *index * 4;
                        self.emit_field_load(body, locals, type_, offset);
                    }
                    _ => {
                        // Record/tuple: tag @0, fields @4 + i*4 (i32 slots).
                        let offset = 4 + *index * 4;
                        self.emit_field_load(body, locals, type_, offset);
                    }
                }
            }

            Expression::Set { name, value } => {
                // Standalone set used as an expression value.
                self.emit_expression(body, locals, value);
                let local = locals.index(&name.name);
                let _ = body.instructions().local_tee(local);
            }

            Expression::If { cond, then, else_ } => {
                self.emit_expression(body, locals, cond);
                let result_type = block_type(&then.type_());
                let _ = body.instructions().if_(result_type);
                self.emit_expression(body, locals, then);
                let _ = body.instructions().else_();
                self.emit_expression(body, locals, else_);
                let _ = body.instructions().end();
            }

            Expression::Call {
                target,
                args,
                type_: _,
            } => {
                for arg in args {
                    self.emit_expression(body, locals, arg);
                }

                match target.as_ref() {
                    Expression::FunctionRef {
                        module: _,
                        name,
                        arity: _,
                        type_: _,
                    } => {
                        let index = self.function_indices.get(name).unwrap_or_else(|| {
                            panic!("unknown function `{name}` in module `{}`", self.module.name)
                        });
                        let _ = body.instructions().call(*index);
                    }
                    _ => panic!("indirect calls are not supported in Wasm yet"),
                }
            }

            Expression::Panic { type_ } => {
                let _ = body.instructions().unreachable();
                // Keep the stack typed for surrounding expressions.
                push_dummy_value(body, type_);
            }
        }
    }

    fn emit_binary(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        lhs: &Expression<CompleteType>,
        rhs: &Expression<CompleteType>,
        op: impl FnOnce(&mut Function),
    ) {
        self.emit_expression(body, locals, lhs);
        self.emit_expression(body, locals, rhs);
        op(body);
    }

    fn emit_eq(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        lhs: &Expression<CompleteType>,
        rhs: &Expression<CompleteType>,
        equal: bool,
    ) {
        self.emit_expression(body, locals, lhs);
        self.emit_expression(body, locals, rhs);
        match lhs.type_() {
            CompleteType::Int => {
                if equal {
                    let _ = body.instructions().i64_eq();
                } else {
                    let _ = body.instructions().i64_ne();
                }
            }
            CompleteType::Bool => {
                if equal {
                    let _ = body.instructions().i32_eq();
                } else {
                    let _ = body.instructions().i32_ne();
                }
            }
            CompleteType::Float => {
                if equal {
                    let _ = body.instructions().f64_eq();
                } else {
                    let _ = body.instructions().f64_ne();
                }
            }
            CompleteType::String => {
                let runtime = self
                    .string_runtime
                    .as_ref()
                    .expect("string runtime required for string equality");
                let _ = body.instructions().call(runtime.eq);
                if !equal {
                    let _ = body.instructions().i32_eqz();
                }
            }
            CompleteType::List(_)
            | CompleteType::Struct { .. }
            | CompleteType::Tuple { .. }
            | CompleteType::Func { .. } => {
                if equal {
                    let _ = body.instructions().i32_eq();
                } else {
                    let _ = body.instructions().i32_ne();
                }
            }
        }
    }

    fn emit_struct(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        tag: u32,
        items: &[Expression<CompleteType>],
        type_: &CompleteType,
    ) {
        let runtime = self
            .string_runtime
            .as_ref()
            .expect("heap runtime required for struct allocation");

        // size = 4 (tag) + 4 * nfields (i32 slots). Int/Float fields are
        // currently stored truncated/reinterpreated as i32 for the zed surface.
        let size = 4 + items.len() as i32 * 4;
        let _ = body.instructions().i32_const(size);
        let _ = body.instructions().call(runtime.alloc);
        let ptr = locals.alloc_tmp(ValType::I32);
        let _ = body.instructions().local_set(ptr);

        // Store tag.
        let _ = body.instructions().local_get(ptr);
        let _ = body.instructions().i32_const(tag as i32);
        let _ = body.instructions().i32_store(mem_arg(0, 2));

        for (index, item) in items.iter().enumerate() {
            let _ = body.instructions().local_get(ptr);
            self.emit_expression(body, locals, item);
            self.emit_field_store(body, locals, &item.type_(), 4 + index as u64 * 4);
        }

        let _ = body.instructions().local_get(ptr);
        let _ = type_;
    }

    fn emit_list(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        items: &[Expression<CompleteType>],
        tail: Option<&Expression<CompleteType>>,
        type_: &CompleteType,
    ) {
        // Start from tail (or null for empty).
        if let Some(tail) = tail {
            self.emit_expression(body, locals, tail);
        } else {
            let _ = body.instructions().i32_const(0);
        }
        let acc = locals.alloc_tmp(ValType::I32);
        let _ = body.instructions().local_set(acc);

        if items.is_empty() {
            let _ = body.instructions().local_get(acc);
            let _ = type_;
            return;
        }

        let runtime = self
            .string_runtime
            .as_ref()
            .expect("heap runtime required for list allocation");

        // Build right-to-left so the first item ends up at the head.
        for item in items.iter().rev() {
            // cons = alloc(8); store head; store tail; acc = cons
            let _ = body.instructions().i32_const(8);
            let _ = body.instructions().call(runtime.alloc);
            let cell = locals.alloc_tmp(ValType::I32);
            let _ = body.instructions().local_set(cell);

            let _ = body.instructions().local_get(cell);
            self.emit_expression(body, locals, item);
            self.emit_field_store(body, locals, &item.type_(), 0);

            let _ = body.instructions().local_get(cell);
            let _ = body.instructions().local_get(acc);
            let _ = body.instructions().i32_store(mem_arg(4, 2));

            let _ = body.instructions().local_get(cell);
            let _ = body.instructions().local_set(acc);
        }

        let _ = body.instructions().local_get(acc);
        let _ = type_;
    }

    fn emit_field_load(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        field_type: &CompleteType,
        offset: u64,
    ) {
        // Pointer to object is on the stack.
        match field_type {
            CompleteType::Int => {
                let _ = body.instructions().i32_load(mem_arg(offset, 2));
                let _ = body.instructions().i64_extend_i32_s();
            }
            CompleteType::Float => {
                let _ = body.instructions().f64_load(mem_arg(offset, 3));
            }
            CompleteType::Bool
            | CompleteType::String
            | CompleteType::List(_)
            | CompleteType::Struct { .. }
            | CompleteType::Tuple { .. }
            | CompleteType::Func { .. } => {
                let _ = body.instructions().i32_load(mem_arg(offset, 2));
            }
        }
        let _ = locals;
    }

    fn emit_field_store(
        &self,
        body: &mut Function,
        locals: &mut LocalAllocator,
        field_type: &CompleteType,
        offset: u64,
    ) {
        // Stack: base_ptr, field_value
        match field_type {
            CompleteType::Int => {
                let _ = body.instructions().i32_wrap_i64();
                let _ = body.instructions().i32_store(mem_arg(offset, 2));
            }
            CompleteType::Float => {
                let _ = body.instructions().f64_store(mem_arg(offset, 3));
            }
            CompleteType::Bool
            | CompleteType::String
            | CompleteType::List(_)
            | CompleteType::Struct { .. }
            | CompleteType::Tuple { .. }
            | CompleteType::Func { .. } => {
                let _ = body.instructions().i32_store(mem_arg(offset, 2));
            }
        }
        let _ = locals;
    }
}

// ---------------------------------------------------------------------------
// Runtime helpers
// ---------------------------------------------------------------------------

const HEAP_GLOBAL: u32 = 0;

fn mem_arg(offset: u64, align: u32) -> MemArg {
    MemArg {
        offset,
        align,
        memory_index: 0,
    }
}

/// `print_string(s)` — write a Gleam string to stdout via WASI `fd_write`.
fn compile_print_string(fd_write: u32) -> Function {
    // param: s=0
    let mut f = Function::new([]);
    // iov.buf = s + 4
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i32_const(4);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_store(mem_arg(0, 2));
    // iov.len = *s
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i32_load(mem_arg(0, 2));
    let _ = f.instructions().i32_store(mem_arg(4, 2));
    // fd_write(1, iov, 1, &nwritten)
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_const(SCRATCH_NWRITTEN as i32);
    let _ = f.instructions().call(fd_write);
    let _ = f.instructions().drop();
    let _ = f.instructions().end();
    f
}

/// `print_i64(n)` — write a signed decimal integer to stdout.
fn compile_print_i64(fd_write: u32) -> Function {
    // param: n=0 (i64)
    // locals: i=1 (i32 cursor), neg=2 (i32), tmp=3 (i64)
    let mut f = Function::new_with_locals_types([ValType::I32, ValType::I32, ValType::I64]);

    // i = ITOA_END
    let _ = f.instructions().i32_const(SCRATCH_ITOA_END as i32);
    let _ = f.instructions().local_set(1);
    // neg = 0; tmp = n
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().local_set(2);
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().local_set(3);

    // if n < 0: neg = 1; tmp = -n
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i64_const(0);
    let _ = f.instructions().i64_lt_s();
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().local_set(2);
    let _ = f.instructions().i64_const(0);
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i64_sub();
    let _ = f.instructions().local_set(3);
    let _ = f.instructions().end();

    // do { write digit; tmp /= 10 } while tmp != 0
    let _ = f.instructions().loop_(BlockType::Empty);
    // i -= 1
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_sub();
    let _ = f.instructions().local_set(1);
    // *i = '0' + (tmp % 10)
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i64_const(10);
    let _ = f.instructions().i64_rem_u();
    let _ = f.instructions().i32_wrap_i64();
    let _ = f.instructions().i32_const(b'0' as i32);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_store8(mem_arg(0, 0));
    // tmp /= 10
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i64_const(10);
    let _ = f.instructions().i64_div_u();
    let _ = f.instructions().local_set(3);
    // continue while tmp != 0
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i64_const(0);
    let _ = f.instructions().i64_ne();
    let _ = f.instructions().br_if(0);
    let _ = f.instructions().end(); // loop

    // if neg: prepend '-'
    let _ = f.instructions().local_get(2);
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_sub();
    let _ = f.instructions().local_tee(1);
    let _ = f.instructions().i32_const(b'-' as i32);
    let _ = f.instructions().i32_store8(mem_arg(0, 0));
    let _ = f.instructions().end();

    // iov.buf = i; iov.len = ITOA_END - i
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_store(mem_arg(0, 2));
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().i32_const(SCRATCH_ITOA_END as i32);
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_sub();
    let _ = f.instructions().i32_store(mem_arg(4, 2));
    // fd_write(1, ...)
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_const(SCRATCH_IOV as i32);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_const(SCRATCH_NWRITTEN as i32);
    let _ = f.instructions().call(fd_write);
    let _ = f.instructions().drop();
    let _ = f.instructions().end();
    f
}

/// `_start` — call `main`, print the result, print a newline.
fn compile_start(entry: &WasiEntry) -> Function {
    let mut f = Function::new([]);
    let _ = f.instructions().call(entry.main_index);
    match entry.main_return {
        CompleteType::String => {
            let _ = f.instructions().call(entry.print_string);
        }
        CompleteType::Int => {
            let _ = f.instructions().call(entry.print_i64);
        }
        CompleteType::Bool => {
            // Print 0 / 1 as decimal.
            let _ = f.instructions().i64_extend_i32_u();
            let _ = f.instructions().call(entry.print_i64);
        }
        CompleteType::Float => {
            // Drop the float; print a placeholder.
            let _ = f.instructions().drop();
            // Fall through to newline only.
        }
        _ => {
            // Unsupported return: drop if needed is already on stack as value.
            let _ = f.instructions().drop();
        }
    }
    // print newline
    let _ = f.instructions().i32_const(entry.newline_offset as i32);
    let _ = f.instructions().call(entry.print_string);
    let _ = f.instructions().end();
    f
}

/// `alloc(size) -> ptr` — bump-allocate `size` bytes, 4-byte aligned.
fn compile_alloc() -> Function {
    // locals: $ptr
    let mut f = Function::new_with_locals_types([ValType::I32]);
    // ptr = heap
    let _ = f.instructions().global_get(HEAP_GLOBAL);
    let _ = f.instructions().local_set(1);
    // heap = (heap + size + 3) & !3
    let _ = f.instructions().global_get(HEAP_GLOBAL);
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_const(3);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_const(-4);
    let _ = f.instructions().i32_and();
    let _ = f.instructions().global_set(HEAP_GLOBAL);
    // return ptr
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().end();
    f
}

/// `string_concat(a, b) -> ptr`
fn compile_string_concat(alloc_index: u32) -> Function {
    // params: a=0, b=1
    // locals: la=2, lb=3, result=4, i=5
    let mut f = Function::new_with_locals_types([
        ValType::I32,
        ValType::I32,
        ValType::I32,
        ValType::I32,
    ]);

    // la = *a
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i32_load(mem_arg(0, 2));
    let _ = f.instructions().local_set(2);
    // lb = *b
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_load(mem_arg(0, 2));
    let _ = f.instructions().local_set(3);
    // result = alloc(4 + la + lb)
    let _ = f.instructions().local_get(2);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_const(4);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().call(alloc_index);
    let _ = f.instructions().local_set(4);
    // *result = la + lb
    let _ = f.instructions().local_get(4);
    let _ = f.instructions().local_get(2);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_store(mem_arg(0, 2));

    // copy a → result+4
    emit_memcpy(&mut f, /*dest_base*/ 4, /*src_param*/ 0, /*len_local*/ 2, /*i*/ 5);
    // copy b → result+4+la
    // i = 0
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().local_set(5);
    // loop
    let _ = f.instructions().loop_(BlockType::Empty);
    // if i >= lb: break via br to outer... use if
    let _ = f.instructions().local_get(5);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_lt_u();
    let _ = f.instructions().if_(BlockType::Empty);
    // dest = result + 4 + la + i
    let _ = f.instructions().local_get(4);
    let _ = f.instructions().local_get(2);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().local_get(5);
    let _ = f.instructions().i32_add();
    // src byte = *(b + 4 + i)
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().local_get(5);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
    let _ = f.instructions().i32_store8(mem_arg(4, 0));
    // i += 1
    let _ = f.instructions().local_get(5);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().local_set(5);
    let _ = f.instructions().br(1); // continue loop
    let _ = f.instructions().end(); // if
    let _ = f.instructions().end(); // loop

    let _ = f.instructions().local_get(4);
    let _ = f.instructions().end();
    f
}

/// Copy `len` bytes from `src_param+4` to `result_local+4`.
/// Uses locals: i for index.
fn emit_memcpy(f: &mut Function, result_local: u32, src_param: u32, len_local: u32, i_local: u32) {
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().local_set(i_local);
    let _ = f.instructions().loop_(BlockType::Empty);
    let _ = f.instructions().local_get(i_local);
    let _ = f.instructions().local_get(len_local);
    let _ = f.instructions().i32_lt_u();
    let _ = f.instructions().if_(BlockType::Empty);
    // dest address = result + i  (store8 uses offset 4)
    let _ = f.instructions().local_get(result_local);
    let _ = f.instructions().local_get(i_local);
    let _ = f.instructions().i32_add();
    // src byte
    let _ = f.instructions().local_get(src_param);
    let _ = f.instructions().local_get(i_local);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
    let _ = f.instructions().i32_store8(mem_arg(4, 0));
    // i += 1
    let _ = f.instructions().local_get(i_local);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().local_set(i_local);
    let _ = f.instructions().br(1);
    let _ = f.instructions().end(); // if
    let _ = f.instructions().end(); // loop
}

/// `string_eq(a, b) -> i32` (1 if equal, 0 otherwise).
fn compile_string_eq() -> Function {
    // params: a=0, b=1
    // locals: la=2, i=3
    let mut f = Function::new_with_locals_types([ValType::I32, ValType::I32]);

    // block $ret (result i32)
    let _ = f.instructions().block(BlockType::Result(ValType::I32));

    // if a == b: return 1
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_eq();
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().br(1); // br $ret
    let _ = f.instructions().end();

    // la = *a
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().i32_load(mem_arg(0, 2));
    let _ = f.instructions().local_tee(2);
    // if la != *b: return 0
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().i32_load(mem_arg(0, 2));
    let _ = f.instructions().i32_ne();
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().br(1);
    let _ = f.instructions().end();

    // i = 0
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().local_set(3);
    let _ = f.instructions().loop_(BlockType::Empty);
    // if i >= la: return 1
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().local_get(2);
    let _ = f.instructions().i32_ge_u();
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().br(2); // br $ret
    let _ = f.instructions().end();
    // if bytes differ: return 0
    let _ = f.instructions().local_get(0);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
    let _ = f.instructions().local_get(1);
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().i32_load8_u(mem_arg(4, 0));
    let _ = f.instructions().i32_ne();
    let _ = f.instructions().if_(BlockType::Empty);
    let _ = f.instructions().i32_const(0);
    let _ = f.instructions().br(2); // br $ret
    let _ = f.instructions().end();
    // i += 1; continue
    let _ = f.instructions().local_get(3);
    let _ = f.instructions().i32_const(1);
    let _ = f.instructions().i32_add();
    let _ = f.instructions().local_set(3);
    let _ = f.instructions().br(0);
    let _ = f.instructions().end(); // loop

    let _ = f.instructions().unreachable();
    let _ = f.instructions().end(); // block $ret
    let _ = f.instructions().end();
    f
}

// ---------------------------------------------------------------------------
// Locals
// ---------------------------------------------------------------------------

struct LocalAllocator {
    /// Parameter + local name → local index.
    names: HashMap<EcoString, u32>,
    /// Types of non-parameter locals, in declaration order.
    extra_locals: Vec<ValType>,
    next_index: u32,
    /// Scratch i32 locals reserved for expression lowering (allocated up front
    /// so `Function::new_with_locals_types` sees them before emit).
    tmp_base: u32,
    tmp_count: u32,
    tmp_next: u32,
}

impl LocalAllocator {
    const TMP_SLOTS: u32 = 64;

    fn new(function: &ast::Function<CompleteType>) -> Self {
        let mut names = HashMap::new();
        let mut next_index = 0;

        for parameter in &function.parameters {
            if let Some(name) = &parameter.name {
                _ = names.insert(name.clone(), next_index);
            }
            next_index += 1;
        }

        Self {
            names,
            extra_locals: Vec::new(),
            next_index,
            tmp_base: 0,
            tmp_count: 0,
            tmp_next: 0,
        }
    }

    /// Reserve a pool of i32 scratch locals. Call after named locals are known.
    fn reserve_tmps(&mut self) {
        self.tmp_base = self.next_index;
        self.tmp_count = Self::TMP_SLOTS;
        self.tmp_next = 0;
        for _ in 0..Self::TMP_SLOTS {
            self.extra_locals.push(ValType::I32);
            self.next_index += 1;
        }
    }

    fn collect_from_expression(&mut self, expression: &Expression<CompleteType>) {
        match expression {
            Expression::Block(expressions) => {
                for expression in expressions {
                    self.collect_from_expression(expression);
                }
            }
            Expression::Set { name, value } => {
                self.ensure_local(&name.name, &name.type_);
                self.collect_from_expression(value);
            }
            Expression::Equals { lhs, rhs }
            | Expression::NotEquals { lhs, rhs }
            | Expression::IntGt { lhs, rhs }
            | Expression::IntGtEq { lhs, rhs }
            | Expression::IntLt { lhs, rhs }
            | Expression::IntLtEq { lhs, rhs }
            | Expression::IntAdd { lhs, rhs }
            | Expression::IntSub { lhs, rhs }
            | Expression::IntMul { lhs, rhs }
            | Expression::IntDiv { lhs, rhs }
            | Expression::IntRem { lhs, rhs }
            | Expression::FloatGt { lhs, rhs }
            | Expression::FloatGtEq { lhs, rhs }
            | Expression::FloatLt { lhs, rhs }
            | Expression::FloatLtEq { lhs, rhs }
            | Expression::FloatAdd { lhs, rhs }
            | Expression::FloatSub { lhs, rhs }
            | Expression::FloatMul { lhs, rhs }
            | Expression::FloatDiv { lhs, rhs }
            | Expression::StringConcat { lhs, rhs } => {
                self.collect_from_expression(lhs);
                self.collect_from_expression(rhs);
            }
            Expression::If { cond, then, else_ } => {
                self.collect_from_expression(cond);
                self.collect_from_expression(then);
                self.collect_from_expression(else_);
            }
            Expression::Call { target, args, .. } => {
                self.collect_from_expression(target);
                for arg in args {
                    self.collect_from_expression(arg);
                }
            }
            Expression::List { items, tail, .. } => {
                for item in items {
                    self.collect_from_expression(item);
                }
                if let Some(tail) = tail {
                    self.collect_from_expression(tail);
                }
            }
            Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
                for item in items {
                    self.collect_from_expression(item);
                }
            }
            Expression::TupleAccess { value, .. }
            | Expression::StructTag { value }
            | Expression::StructAccess { value, .. } => {
                self.collect_from_expression(value);
            }
            Expression::FunctionRef { .. }
            | Expression::Var(_)
            | Expression::Int { .. }
            | Expression::Float { .. }
            | Expression::Bool { .. }
            | Expression::String { .. }
            | Expression::Panic { .. } => {}
        }
    }

    fn ensure_local(&mut self, name: &EcoString, type_: &CompleteType) {
        if self.names.contains_key(name) {
            return;
        }
        _ = self.names.insert(name.clone(), self.next_index);
        self.extra_locals.push(val_type(type_));
        self.next_index += 1;
    }

    fn index(&self, name: &EcoString) -> u32 {
        *self
            .names
            .get(name)
            .unwrap_or_else(|| panic!("unknown local `{name}`"))
    }

    fn alloc_tmp(&mut self, _type_: ValType) -> u32 {
        if self.tmp_count == 0 {
            panic!("temporary locals were not reserved before emit");
        }
        if self.tmp_next >= self.tmp_count {
            // Wrap around — nested expressions that hold multiple live tmps
            // beyond TMP_SLOTS will clobber; raise the pool if that happens.
            self.tmp_next = 0;
        }
        let index = self.tmp_base + self.tmp_next;
        self.tmp_next += 1;
        index
    }
}

// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------

fn val_type(type_: &CompleteType) -> ValType {
    match type_ {
        CompleteType::Int => ValType::I64,
        CompleteType::Float => ValType::F64,
        CompleteType::Bool
        | CompleteType::String
        | CompleteType::Tuple { .. }
        | CompleteType::Struct { .. }
        | CompleteType::List(_)
        | CompleteType::Func { .. } => ValType::I32,
    }
}

fn block_type(type_: &CompleteType) -> BlockType {
    BlockType::Result(val_type(type_))
}

fn bigint_to_i64(value: &BigInt) -> i64 {
    value
        .to_i64()
        .unwrap_or_else(|| panic!("integer literal does not fit in i64: {value}"))
}

fn push_dummy_value(body: &mut Function, type_: &CompleteType) {
    match type_ {
        CompleteType::Int => {
            let _ = body.instructions().i64_const(0);
        }
        CompleteType::Bool
        | CompleteType::String
        | CompleteType::Tuple { .. }
        | CompleteType::Struct { .. }
        | CompleteType::List(_)
        | CompleteType::Func { .. } => {
            let _ = body.instructions().i32_const(0);
        }
        CompleteType::Float => {
            let _ = body.instructions().f64_const(Ieee64::from(0.0));
        }
    }
}

fn align4(value: u32) -> u32 {
    (value + 3) & !3
}

fn is_main_function(name: &str) -> bool {
    name == "main" || name.ends_with("__main")
}

fn module_uses_strings(module: &ast::Module<CompleteType>) -> bool {
    module.functions.iter().any(|function| {
        type_is_stringy(&function.return_type)
            || function
                .parameters
                .iter()
                .any(|parameter| type_is_stringy(&parameter.type_))
            || function
                .body
                .as_ref()
                .is_some_and(expression_uses_strings)
    })
}

fn module_needs_heap(module: &ast::Module<CompleteType>) -> bool {
    module.functions.iter().any(|function| {
        type_needs_heap(&function.return_type)
            || function
                .parameters
                .iter()
                .any(|parameter| type_needs_heap(&parameter.type_))
            || function.body.as_ref().is_some_and(expression_needs_heap)
    })
}

fn expression_needs_heap(expression: &Expression<CompleteType>) -> bool {
    match expression {
        Expression::String { .. }
        | Expression::StringConcat { .. }
        | Expression::List { .. }
        | Expression::Tuple { .. }
        | Expression::Struct { .. } => true,
        Expression::Block(expressions) => expressions.iter().any(expression_needs_heap),
        Expression::Set { value, .. }
        | Expression::TupleAccess { value, .. }
        | Expression::StructTag { value }
        | Expression::StructAccess { value, .. } => expression_needs_heap(value),
        Expression::Equals { lhs, rhs }
        | Expression::NotEquals { lhs, rhs }
        | Expression::IntGt { lhs, rhs }
        | Expression::IntGtEq { lhs, rhs }
        | Expression::IntLt { lhs, rhs }
        | Expression::IntLtEq { lhs, rhs }
        | Expression::IntAdd { lhs, rhs }
        | Expression::IntSub { lhs, rhs }
        | Expression::IntMul { lhs, rhs }
        | Expression::IntDiv { lhs, rhs }
        | Expression::IntRem { lhs, rhs }
        | Expression::FloatGt { lhs, rhs }
        | Expression::FloatGtEq { lhs, rhs }
        | Expression::FloatLt { lhs, rhs }
        | Expression::FloatLtEq { lhs, rhs }
        | Expression::FloatAdd { lhs, rhs }
        | Expression::FloatSub { lhs, rhs }
        | Expression::FloatMul { lhs, rhs }
        | Expression::FloatDiv { lhs, rhs } => {
            expression_needs_heap(lhs) || expression_needs_heap(rhs)
        }
        Expression::If { cond, then, else_ } => {
            expression_needs_heap(cond)
                || expression_needs_heap(then)
                || expression_needs_heap(else_)
        }
        Expression::Call { target, args, .. } => {
            expression_needs_heap(target) || args.iter().any(expression_needs_heap)
        }
        Expression::FunctionRef { .. }
        | Expression::Var(_)
        | Expression::Int { .. }
        | Expression::Float { .. }
        | Expression::Bool { .. }
        | Expression::Panic { .. } => false,
    }
}

fn type_is_stringy(type_: &CompleteType) -> bool {
    match type_ {
        CompleteType::String => true,
        CompleteType::List(inner) => type_is_stringy(inner),
        CompleteType::Tuple { elements } | CompleteType::Struct { elements } => {
            elements.iter().any(type_is_stringy)
        }
        CompleteType::Func { arguments, returns } => {
            arguments.iter().any(type_is_stringy) || type_is_stringy(returns)
        }
        _ => false,
    }
}

fn type_needs_heap(type_: &CompleteType) -> bool {
    match type_ {
        CompleteType::String
        | CompleteType::List(_)
        | CompleteType::Tuple { .. }
        | CompleteType::Struct { .. } => true,
        CompleteType::Func { arguments, returns } => {
            arguments.iter().any(type_needs_heap) || type_needs_heap(returns)
        }
        _ => false,
    }
}

fn expression_uses_strings(expression: &Expression<CompleteType>) -> bool {
    match expression {
        Expression::String { .. } | Expression::StringConcat { .. } => true,
        Expression::Block(expressions) => expressions.iter().any(expression_uses_strings),
        Expression::Set { value, .. } => expression_uses_strings(value),
        Expression::Equals { lhs, rhs }
        | Expression::NotEquals { lhs, rhs }
        | Expression::IntGt { lhs, rhs }
        | Expression::IntGtEq { lhs, rhs }
        | Expression::IntLt { lhs, rhs }
        | Expression::IntLtEq { lhs, rhs }
        | Expression::IntAdd { lhs, rhs }
        | Expression::IntSub { lhs, rhs }
        | Expression::IntMul { lhs, rhs }
        | Expression::IntDiv { lhs, rhs }
        | Expression::IntRem { lhs, rhs }
        | Expression::FloatGt { lhs, rhs }
        | Expression::FloatGtEq { lhs, rhs }
        | Expression::FloatLt { lhs, rhs }
        | Expression::FloatLtEq { lhs, rhs }
        | Expression::FloatAdd { lhs, rhs }
        | Expression::FloatSub { lhs, rhs }
        | Expression::FloatMul { lhs, rhs }
        | Expression::FloatDiv { lhs, rhs } => {
            expression_uses_strings(lhs) || expression_uses_strings(rhs)
        }
        Expression::If { cond, then, else_ } => {
            expression_uses_strings(cond)
                || expression_uses_strings(then)
                || expression_uses_strings(else_)
        }
        Expression::Call { target, args, .. } => {
            expression_uses_strings(target) || args.iter().any(expression_uses_strings)
        }
        Expression::List { items, tail, type_ } => {
            type_is_stringy(type_)
                || items.iter().any(expression_uses_strings)
                || tail.as_ref().is_some_and(|t| expression_uses_strings(t))
        }
        Expression::Tuple { items, type_ } | Expression::Struct { items, type_, .. } => {
            type_is_stringy(type_) || items.iter().any(expression_uses_strings)
        }
        Expression::TupleAccess { value, type_, .. }
        | Expression::StructAccess { value, type_, .. } => {
            type_is_stringy(type_) || expression_uses_strings(value)
        }
        Expression::StructTag { value } => expression_uses_strings(value),
        Expression::FunctionRef { type_, .. } => type_is_stringy(type_),
        Expression::Var(var) => type_is_stringy(&var.type_),
        Expression::Panic { type_ } => type_is_stringy(type_),
        Expression::Int { .. }
        | Expression::Float { .. }
        | Expression::Bool { .. } => false,
    }
}

fn collect_strings_from_expression(expression: &Expression<CompleteType>, f: &mut dyn FnMut(&str)) {
    match expression {
        Expression::String { value } => f(value),
        Expression::Block(expressions) => {
            for expression in expressions {
                collect_strings_from_expression(expression, f);
            }
        }
        Expression::Set { value, .. }
        | Expression::StructTag { value }
        | Expression::TupleAccess { value, .. }
        | Expression::StructAccess { value, .. } => {
            collect_strings_from_expression(value, f);
        }
        Expression::Equals { lhs, rhs }
        | Expression::NotEquals { lhs, rhs }
        | Expression::IntGt { lhs, rhs }
        | Expression::IntGtEq { lhs, rhs }
        | Expression::IntLt { lhs, rhs }
        | Expression::IntLtEq { lhs, rhs }
        | Expression::IntAdd { lhs, rhs }
        | Expression::IntSub { lhs, rhs }
        | Expression::IntMul { lhs, rhs }
        | Expression::IntDiv { lhs, rhs }
        | Expression::IntRem { lhs, rhs }
        | Expression::FloatGt { lhs, rhs }
        | Expression::FloatGtEq { lhs, rhs }
        | Expression::FloatLt { lhs, rhs }
        | Expression::FloatLtEq { lhs, rhs }
        | Expression::FloatAdd { lhs, rhs }
        | Expression::FloatSub { lhs, rhs }
        | Expression::FloatMul { lhs, rhs }
        | Expression::FloatDiv { lhs, rhs }
        | Expression::StringConcat { lhs, rhs } => {
            collect_strings_from_expression(lhs, f);
            collect_strings_from_expression(rhs, f);
        }
        Expression::If { cond, then, else_ } => {
            collect_strings_from_expression(cond, f);
            collect_strings_from_expression(then, f);
            collect_strings_from_expression(else_, f);
        }
        Expression::Call { target, args, .. } => {
            collect_strings_from_expression(target, f);
            for arg in args {
                collect_strings_from_expression(arg, f);
            }
        }
        Expression::List { items, tail, .. } => {
            for item in items {
                collect_strings_from_expression(item, f);
            }
            if let Some(tail) = tail {
                collect_strings_from_expression(tail, f);
            }
        }
        Expression::Tuple { items, .. } | Expression::Struct { items, .. } => {
            for item in items {
                collect_strings_from_expression(item, f);
            }
        }
        Expression::FunctionRef { .. }
        | Expression::Var(_)
        | Expression::Int { .. }
        | Expression::Float { .. }
        | Expression::Bool { .. }
        | Expression::Panic { .. } => {}
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::wasm::mir::ast::{Function, FunctionParameter, Module};

    #[test]
    fn compiles_constant_int_main() {
        let module = Module {
            name: "project_wasm".into(),
            functions: vec![Function {
                name: "main".into(),
                return_type: CompleteType::Int,
                parameters: vec![],
                body: Some(Expression::Int {
                    value: BigInt::from(0),
                }),
                external_wasm: None,
            }],
        };

        let bytes = compile(module);
        assert_eq!(&bytes[..4], b"\0asm");
        // version 1
        assert_eq!(&bytes[4..8], &[1, 0, 0, 0]);
    }

    #[test]
    fn compiles_add() {
        let module = Module {
            name: "maths".into(),
            functions: vec![Function {
                name: "add".into(),
                return_type: CompleteType::Int,
                parameters: vec![
                    FunctionParameter {
                        type_: CompleteType::Int,
                        name: Some("lhs".into()),
                    },
                    FunctionParameter {
                        type_: CompleteType::Int,
                        name: Some("rhs".into()),
                    },
                ],
                body: Some(Expression::IntAdd {
                    lhs: Box::new(Expression::Var(ast::Var {
                        name: "lhs".into(),
                        type_: CompleteType::Int,
                    })),
                    rhs: Box::new(Expression::Var(ast::Var {
                        name: "rhs".into(),
                        type_: CompleteType::Int,
                    })),
                }),
                external_wasm: None,
            }],
        };

        let bytes = compile(module);
        assert_eq!(&bytes[..4], b"\0asm");
    }

    #[test]
    fn compiles_string_literal_and_concat() {
        let module = Module {
            name: "strings".into(),
            functions: vec![Function {
                name: "greet".into(),
                return_type: CompleteType::String,
                parameters: vec![],
                body: Some(Expression::StringConcat {
                    lhs: Box::new(Expression::String {
                        value: "hello, ".into(),
                    }),
                    rhs: Box::new(Expression::String {
                        value: "world!".into(),
                    }),
                }),
                external_wasm: None,
            }],
        };

        let bytes = compile(module);
        assert_eq!(&bytes[..4], b"\0asm");
        // Must include a memory section / export for host access.
        assert!(bytes.len() > 40);
    }
}