sema_vm/
compiler.rs

1use sema_core::{intern, resolve as resolve_spur, SemaError, Spur, Value};
2
3use crate::chunk::{Chunk, ExceptionEntry, Function, UpvalueDesc};
4use crate::core_expr::{
5    ResolvedDoLoop, ResolvedExpr, ResolvedLambda, ResolvedPromptEntry, VarRef, VarResolution,
6};
7use crate::emit::Emitter;
8use crate::opcodes::Op;
9
10/// Result of compiling a top-level expression.
11pub struct CompileResult {
12    /// The top-level chunk to execute.
13    pub chunk: Chunk,
14    /// All compiled function templates (referenced by MakeClosure func_id).
15    pub functions: Vec<Function>,
16}
17
18/// Maximum recursion depth for the compiler.
19/// This prevents native stack overflow from deeply nested expressions.
20const MAX_COMPILE_DEPTH: usize = 256;
21
22/// Compile a resolved expression tree into bytecode.
23pub fn compile(expr: &ResolvedExpr) -> Result<CompileResult, SemaError> {
24    compile_with_locals(expr, 0)
25}
26
27/// Compile a resolved expression tree into bytecode with a known top-level local count.
28pub fn compile_with_locals(expr: &ResolvedExpr, n_locals: u16) -> Result<CompileResult, SemaError> {
29    let mut compiler = Compiler::new();
30    compiler.n_locals = n_locals;
31    compiler.compile_expr(expr)?;
32    compiler.emit.emit_op(Op::Return);
33    let (chunk, functions) = compiler.finish();
34    Ok(CompileResult { chunk, functions })
35}
36
37/// Compile multiple top-level expressions into a single chunk.
38pub fn compile_many(exprs: &[ResolvedExpr]) -> Result<CompileResult, SemaError> {
39    compile_many_with_locals(exprs, 0)
40}
41
42/// Compile multiple top-level expressions with a known top-level local count.
43pub fn compile_many_with_locals(
44    exprs: &[ResolvedExpr],
45    n_locals: u16,
46) -> Result<CompileResult, SemaError> {
47    let mut compiler = Compiler::new();
48    compiler.n_locals = n_locals;
49    for (i, expr) in exprs.iter().enumerate() {
50        compiler.compile_expr(expr)?;
51        if i < exprs.len() - 1 {
52            compiler.emit.emit_op(Op::Pop);
53        }
54    }
55    if exprs.is_empty() {
56        compiler.emit.emit_op(Op::Nil);
57    }
58    compiler.emit.emit_op(Op::Return);
59    let (chunk, functions) = compiler.finish();
60    Ok(CompileResult { chunk, functions })
61}
62
63/// Walk bytecode and add `offset` to all MakeClosure func_id operands.
64fn patch_closure_func_ids(chunk: &mut Chunk, offset: u16) {
65    let code = &mut chunk.code;
66    let mut pc = 0;
67    while pc < code.len() {
68        let Some(op) = Op::from_u8(code[pc]) else {
69            break;
70        };
71        match op {
72            Op::MakeClosure => {
73                // func_id is at pc+1..pc+3 (u16 LE)
74                let old = u16::from_le_bytes([code[pc + 1], code[pc + 2]]);
75                let new = old + offset;
76                let bytes = new.to_le_bytes();
77                code[pc + 1] = bytes[0];
78                code[pc + 2] = bytes[1];
79                // n_upvalues at pc+3..pc+5
80                let n_upvalues = u16::from_le_bytes([code[pc + 3], code[pc + 4]]) as usize;
81                // Skip: op(1) + func_id(2) + n_upvalues(2) + n_upvalues * (is_local(2) + idx(2))
82                pc += 1 + 2 + 2 + n_upvalues * 4;
83            }
84            // Variable-length instructions: skip op + operands
85            Op::Const
86            | Op::LoadLocal
87            | Op::StoreLocal
88            | Op::LoadUpvalue
89            | Op::StoreUpvalue
90            | Op::Call
91            | Op::TailCall
92            | Op::MakeList
93            | Op::MakeVector
94            | Op::MakeMap
95            | Op::MakeHashMap => {
96                pc += 1 + 2; // op + u16
97            }
98            Op::CallNative => {
99                pc += 1 + 2 + 2; // op + u16 native_id + u16 argc
100            }
101            Op::LoadGlobal | Op::StoreGlobal | Op::DefineGlobal => {
102                pc += 1 + 4; // op + u32
103            }
104            Op::CallGlobal => {
105                pc += 1 + 4 + 2; // op + u32 spur + u16 argc
106            }
107            Op::Jump | Op::JumpIfFalse | Op::JumpIfTrue => {
108                pc += 1 + 4; // op + i32
109            }
110            // Single-byte instructions
111            _ => {
112                pc += 1;
113            }
114        }
115    }
116}
117
118struct Compiler {
119    emit: Emitter,
120    functions: Vec<Function>,
121    exception_entries: Vec<ExceptionEntry>,
122    n_locals: u16,
123    /// Current operand stack depth above locals (for exception handler stack restore).
124    stack_height: u16,
125    depth: usize,
126}
127
128impl Compiler {
129    fn new() -> Self {
130        Compiler {
131            emit: Emitter::new(),
132            functions: Vec::new(),
133            exception_entries: Vec::new(),
134            n_locals: 0,
135            stack_height: 0,
136            depth: 0,
137        }
138    }
139
140    fn finish(self) -> (Chunk, Vec<Function>) {
141        let mut chunk = self.emit.into_chunk();
142        chunk.n_locals = self.n_locals;
143        chunk.exception_table = self.exception_entries;
144        (chunk, self.functions)
145    }
146
147    fn compile_expr(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
148        self.depth += 1;
149        if self.depth > MAX_COMPILE_DEPTH {
150            self.depth -= 1;
151            return Err(SemaError::eval("maximum compilation depth exceeded"));
152        }
153        // Track operand stack: every expression has a net effect of +1
154        // (pushes exactly one result value). We save before and restore
155        // the +1 after, so inner recursive calls accumulate correctly
156        // for compile_try's stack_depth calculation.
157        let result = self.compile_expr_inner(expr);
158        self.depth -= 1;
159        result
160    }
161
162    fn compile_expr_inner(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
163        match expr {
164            ResolvedExpr::Const(val) => self.compile_const(val),
165            ResolvedExpr::Var(vr) => self.compile_var_load(vr),
166            ResolvedExpr::If { test, then, else_ } => self.compile_if(test, then, else_),
167            ResolvedExpr::Begin(exprs) => self.compile_begin(exprs),
168            ResolvedExpr::Set(vr, val) => self.compile_set(vr, val),
169            ResolvedExpr::Lambda(def) => self.compile_lambda(def),
170            ResolvedExpr::Call { func, args, tail } => self.compile_call(func, args, *tail),
171            ResolvedExpr::Define(spur, val) => self.compile_define(*spur, val),
172            ResolvedExpr::Let { bindings, body } => self.compile_let(bindings, body),
173            ResolvedExpr::LetStar { bindings, body } => self.compile_let_star(bindings, body),
174            ResolvedExpr::Letrec { bindings, body } => self.compile_letrec(bindings, body),
175            ResolvedExpr::NamedLet {
176                name,
177                bindings,
178                body,
179            } => self.compile_named_let(name, bindings, body),
180            ResolvedExpr::Do(do_loop) => self.compile_do(do_loop),
181            ResolvedExpr::Try {
182                body,
183                catch_var,
184                handler,
185            } => self.compile_try(body, catch_var, handler),
186            ResolvedExpr::Throw(val) => self.compile_throw(val),
187            ResolvedExpr::And(exprs) => self.compile_and(exprs),
188            ResolvedExpr::Or(exprs) => self.compile_or(exprs),
189            ResolvedExpr::Quote(val) => self.compile_const(val),
190            ResolvedExpr::MakeList(exprs) => self.compile_make_list(exprs),
191            ResolvedExpr::MakeVector(exprs) => self.compile_make_vector(exprs),
192            ResolvedExpr::MakeMap(pairs) => self.compile_make_map(pairs),
193            ResolvedExpr::Defmacro {
194                name,
195                params,
196                rest,
197                body,
198            } => self.compile_defmacro(*name, params, rest, body),
199            ResolvedExpr::DefineRecordType {
200                type_name,
201                ctor_name,
202                pred_name,
203                field_names,
204                field_specs,
205            } => self.compile_define_record_type(
206                *type_name,
207                *ctor_name,
208                *pred_name,
209                field_names,
210                field_specs,
211            ),
212            ResolvedExpr::Module {
213                name,
214                exports,
215                body,
216            } => self.compile_module(*name, exports, body),
217            ResolvedExpr::Import { path, selective } => self.compile_import(path, selective),
218            ResolvedExpr::Load(path) => self.compile_load(path),
219            ResolvedExpr::Eval(expr) => self.compile_eval(expr),
220            ResolvedExpr::Prompt(entries) => self.compile_prompt(entries),
221            ResolvedExpr::Message { role, parts } => self.compile_message(role, parts),
222            ResolvedExpr::Deftool {
223                name,
224                description,
225                parameters,
226                handler,
227            } => self.compile_deftool(*name, description, parameters, handler),
228            ResolvedExpr::Defagent { name, options } => self.compile_defagent(*name, options),
229            ResolvedExpr::Delay(expr) => self.compile_delay(expr),
230            ResolvedExpr::Force(expr) => self.compile_force(expr),
231            ResolvedExpr::Macroexpand(expr) => self.compile_macroexpand(expr),
232        }
233    }
234
235    // --- Constants ---
236
237    fn compile_const(&mut self, val: &Value) -> Result<(), SemaError> {
238        if val.is_nil() {
239            self.emit.emit_op(Op::Nil);
240        } else if val.as_bool() == Some(true) {
241            self.emit.emit_op(Op::True);
242        } else if val.as_bool() == Some(false) {
243            self.emit.emit_op(Op::False);
244        } else {
245            self.emit.emit_const(val.clone());
246        }
247        Ok(())
248    }
249
250    // --- Variable access ---
251
252    fn compile_var_load(&mut self, vr: &VarRef) -> Result<(), SemaError> {
253        match vr.resolution {
254            VarResolution::Local { slot } => match slot {
255                0 => self.emit.emit_op(Op::LoadLocal0),
256                1 => self.emit.emit_op(Op::LoadLocal1),
257                2 => self.emit.emit_op(Op::LoadLocal2),
258                3 => self.emit.emit_op(Op::LoadLocal3),
259                _ => {
260                    self.emit.emit_op(Op::LoadLocal);
261                    self.emit.emit_u16(slot);
262                }
263            },
264            VarResolution::Upvalue { index } => {
265                self.emit.emit_op(Op::LoadUpvalue);
266                self.emit.emit_u16(index);
267            }
268            VarResolution::Global { spur } => {
269                self.emit.emit_op(Op::LoadGlobal);
270                self.emit.emit_u32(spur_to_u32(spur));
271            }
272        }
273        Ok(())
274    }
275
276    fn compile_var_store(&mut self, vr: &VarRef) {
277        match vr.resolution {
278            VarResolution::Local { slot } => match slot {
279                0 => self.emit.emit_op(Op::StoreLocal0),
280                1 => self.emit.emit_op(Op::StoreLocal1),
281                2 => self.emit.emit_op(Op::StoreLocal2),
282                3 => self.emit.emit_op(Op::StoreLocal3),
283                _ => {
284                    self.emit.emit_op(Op::StoreLocal);
285                    self.emit.emit_u16(slot);
286                }
287            },
288            VarResolution::Upvalue { index } => {
289                self.emit.emit_op(Op::StoreUpvalue);
290                self.emit.emit_u16(index);
291            }
292            VarResolution::Global { spur } => {
293                self.emit.emit_op(Op::StoreGlobal);
294                self.emit.emit_u32(spur_to_u32(spur));
295            }
296        }
297    }
298
299    // --- Control flow ---
300
301    fn compile_if(
302        &mut self,
303        test: &ResolvedExpr,
304        then: &ResolvedExpr,
305        else_: &ResolvedExpr,
306    ) -> Result<(), SemaError> {
307        // Peephole: (if (not X) then else) → compile X, JumpIfTrue to else
308        // Avoids emitting NOT + JumpIfFalse, saving one opcode dispatch.
309        if let ResolvedExpr::Call { func, args, .. } = test {
310            if args.len() == 1 {
311                if let ResolvedExpr::Var(vr) = func.as_ref() {
312                    if let VarResolution::Global { spur } = vr.resolution {
313                        if resolve_spur(spur) == "not" {
314                            self.compile_expr(&args[0])?;
315                            let else_jump = self.emit.emit_jump(Op::JumpIfTrue);
316                            self.compile_expr(then)?;
317                            let end_jump = self.emit.emit_jump(Op::Jump);
318                            self.emit.patch_jump(else_jump);
319                            self.compile_expr(else_)?;
320                            self.emit.patch_jump(end_jump);
321                            return Ok(());
322                        }
323                    }
324                }
325            }
326        }
327
328        self.compile_expr(test)?;
329        let else_jump = self.emit.emit_jump(Op::JumpIfFalse);
330        self.compile_expr(then)?;
331        let end_jump = self.emit.emit_jump(Op::Jump);
332        self.emit.patch_jump(else_jump);
333        self.compile_expr(else_)?;
334        self.emit.patch_jump(end_jump);
335        Ok(())
336    }
337
338    fn compile_begin(&mut self, exprs: &[ResolvedExpr]) -> Result<(), SemaError> {
339        if exprs.is_empty() {
340            self.emit.emit_op(Op::Nil);
341            return Ok(());
342        }
343        for (i, expr) in exprs.iter().enumerate() {
344            self.compile_expr(expr)?;
345            if i < exprs.len() - 1 {
346                self.emit.emit_op(Op::Pop);
347                // compile_expr pushed +1, Pop removes it
348            }
349            // Last expr's value stays on stack (net +1 for the whole begin)
350        }
351        Ok(())
352    }
353
354    // --- Assignment ---
355
356    fn compile_set(&mut self, vr: &VarRef, val: &ResolvedExpr) -> Result<(), SemaError> {
357        self.compile_expr(val)?;
358        self.emit.emit_op(Op::Dup); // set! returns the value
359        self.compile_var_store(vr);
360        Ok(())
361    }
362
363    fn compile_define(&mut self, spur: Spur, val: &ResolvedExpr) -> Result<(), SemaError> {
364        self.compile_expr(val)?;
365        self.emit.emit_op(Op::DefineGlobal);
366        self.emit.emit_u32(spur_to_u32(spur));
367        self.emit.emit_op(Op::Nil); // define returns nil
368        Ok(())
369    }
370
371    // --- Lambda ---
372
373    fn compile_lambda(&mut self, def: &ResolvedLambda) -> Result<(), SemaError> {
374        // Compile the lambda body into a separate function
375        let mut inner = Compiler::new();
376        inner.n_locals = def.n_locals;
377
378        // Compile body
379        if def.body.is_empty() {
380            inner.emit.emit_op(Op::Nil);
381        } else {
382            for (i, expr) in def.body.iter().enumerate() {
383                inner.compile_expr(expr)?;
384                if i < def.body.len() - 1 {
385                    inner.emit.emit_op(Op::Pop);
386                }
387            }
388        }
389        inner.emit.emit_op(Op::Return);
390
391        let func_id = self.functions.len() as u16;
392        let (mut chunk, mut child_functions) = inner.finish();
393
394        // The inner compiler assigned func_ids starting from 0, but child functions
395        // will be placed starting at func_id + 1 in our functions vec.
396        // Patch all MakeClosure func_id operands in the inner chunk and child functions.
397        let offset = func_id + 1;
398        if offset > 0 && !child_functions.is_empty() {
399            patch_closure_func_ids(&mut chunk, offset);
400            for f in &mut child_functions {
401                patch_closure_func_ids(&mut f.chunk, offset);
402            }
403        }
404
405        let func = Function {
406            name: def.name,
407            chunk,
408            upvalue_descs: def.upvalues.clone(),
409            arity: def.params.len() as u16,
410            has_rest: def.rest.is_some(),
411            local_names: Vec::new(),
412        };
413        self.functions.push(func);
414        self.functions.extend(child_functions);
415
416        // Emit MakeClosure instruction
417        let n_upvalues = def.upvalues.len() as u16;
418        self.emit.emit_op(Op::MakeClosure);
419        self.emit.emit_u16(func_id);
420        self.emit.emit_u16(n_upvalues);
421
422        // Emit upvalue descriptors inline
423        for uv in &def.upvalues {
424            match uv {
425                UpvalueDesc::ParentLocal(slot) => {
426                    self.emit.emit_u16(1); // is_local = true (using u16 for alignment)
427                    self.emit.emit_u16(*slot);
428                }
429                UpvalueDesc::ParentUpvalue(idx) => {
430                    self.emit.emit_u16(0); // is_local = false
431                    self.emit.emit_u16(*idx);
432                }
433            }
434        }
435
436        Ok(())
437    }
438
439    // --- Function calls ---
440
441    /// Try to compile a call to a known global as an inline opcode.
442    /// Returns `true` if the intrinsic was emitted, `false` if not recognized.
443    fn try_compile_intrinsic(
444        &mut self,
445        spur: Spur,
446        args: &[ResolvedExpr],
447    ) -> Result<bool, SemaError> {
448        let name = resolve_spur(spur);
449        let argc = args.len();
450
451        let op = match (name.as_str(), argc) {
452            // Unary
453            ("not", 1) => Op::Not,
454            ("-", 1) => Op::Negate,
455            // Binary arithmetic
456            ("+", 2) => Op::AddInt,
457            ("-", 2) => Op::SubInt,
458            ("*", 2) => Op::MulInt,
459            ("/", 2) => Op::Div,
460            // Binary comparison
461            ("<", 2) => Op::LtInt,
462            (">", 2) => Op::Gt,
463            ("<=", 2) => Op::Le,
464            (">=", 2) => Op::Ge,
465            ("=", 2) => Op::EqInt,
466            _ => return Ok(false),
467        };
468
469        // Compile all arguments, tracking stack height for exception handlers.
470        for arg in args {
471            self.compile_expr(arg)?;
472            self.stack_height += 1;
473        }
474        self.emit.emit_op(op);
475        // Opcode consumes all args and produces 1 result.
476        // stack_height tracks intermediate operands (for exception handler restore),
477        // not including the final result — same convention as compile_call.
478        self.stack_height -= argc as u16;
479        Ok(true)
480    }
481
482    fn compile_call(
483        &mut self,
484        func: &ResolvedExpr,
485        args: &[ResolvedExpr],
486        tail: bool,
487    ) -> Result<(), SemaError> {
488        // Intrinsic recognition: emit inline opcodes for known builtins.
489        // This applies regardless of tail position since intrinsics don't create frames.
490        if let ResolvedExpr::Var(vr) = func {
491            if let VarResolution::Global { spur } = vr.resolution {
492                if self.try_compile_intrinsic(spur, args)? {
493                    return Ok(());
494                }
495            }
496        }
497
498        // Fused CALL_GLOBAL for non-tail calls to global functions.
499        // Tail calls can't use this because CALL_GLOBAL pushes a new frame
500        // (tail calls need to reuse the current frame).
501        if !tail {
502            if let ResolvedExpr::Var(vr) = func {
503                if let VarResolution::Global { spur } = vr.resolution {
504                    // Compile arguments (each pushes 1 value)
505                    for arg in args {
506                        self.compile_expr(arg)?;
507                        self.stack_height += 1;
508                    }
509                    let argc = args.len() as u16;
510                    self.emit.emit_op(Op::CallGlobal);
511                    self.emit.emit_u32(spur_to_u32(spur));
512                    self.emit.emit_u16(argc);
513                    // CALL_GLOBAL pops argc args, pushes 1 result
514                    self.stack_height -= argc;
515                    return Ok(());
516                }
517            }
518        }
519
520        // General path: compile function expression (pushes 1 value onto operand stack)
521        self.compile_expr(func)?;
522        self.stack_height += 1;
523        // Compile arguments (each pushes 1 value)
524        for arg in args {
525            self.compile_expr(arg)?;
526            self.stack_height += 1;
527        }
528        let argc = args.len() as u16;
529        if tail {
530            self.emit.emit_op(Op::TailCall);
531        } else {
532            self.emit.emit_op(Op::Call);
533        }
534        self.emit.emit_u16(argc);
535        // CALL pops func + args, pushes 1 result. Net from our perspective:
536        // we pushed (1 + argc) above, result is handled by our caller.
537        self.stack_height -= 1 + argc;
538        Ok(())
539    }
540
541    // --- Let forms ---
542
543    fn compile_let(
544        &mut self,
545        bindings: &[(VarRef, ResolvedExpr)],
546        body: &[ResolvedExpr],
547    ) -> Result<(), SemaError> {
548        // Compile all init expressions first
549        for (_, init) in bindings {
550            self.compile_expr(init)?;
551        }
552        // Store into local slots (in reverse to match stack order)
553        for (vr, _) in bindings.iter().rev() {
554            self.compile_var_store(vr);
555        }
556        // Compile body
557        self.compile_begin(body)
558    }
559
560    fn compile_let_star(
561        &mut self,
562        bindings: &[(VarRef, ResolvedExpr)],
563        body: &[ResolvedExpr],
564    ) -> Result<(), SemaError> {
565        // Sequential: compile init, store, next binding
566        for (vr, init) in bindings {
567            self.compile_expr(init)?;
568            self.compile_var_store(vr);
569        }
570        self.compile_begin(body)
571    }
572
573    fn compile_letrec(
574        &mut self,
575        bindings: &[(VarRef, ResolvedExpr)],
576        body: &[ResolvedExpr],
577    ) -> Result<(), SemaError> {
578        // Initialize all slots to nil first
579        for (vr, _) in bindings {
580            self.emit.emit_op(Op::Nil);
581            self.compile_var_store(vr);
582        }
583        // Then compile and assign each init
584        for (vr, init) in bindings {
585            self.compile_expr(init)?;
586            self.compile_var_store(vr);
587        }
588        self.compile_begin(body)
589    }
590
591    fn compile_named_let(
592        &mut self,
593        name: &VarRef,
594        bindings: &[(VarRef, ResolvedExpr)],
595        body: &[ResolvedExpr],
596    ) -> Result<(), SemaError> {
597        // Named let is compiled as a local recursive function.
598        // The loop variable `name` is bound to a lambda that takes the binding params.
599        // 1. Create the lambda for the loop body
600        // 2. Bind it to `name`
601        // 3. Call it with initial values
602
603        // Build a synthetic ResolvedLambda for the loop body
604        let params: Vec<Spur> = bindings.iter().map(|(vr, _)| vr.name).collect();
605
606        // Compile the lambda body into a separate function
607        let mut inner = Compiler::new();
608        // The lambda needs locals for its params + the loop name
609        // The resolver has already set up the slots
610        let max_slot = bindings
611            .iter()
612            .map(|(vr, _)| match vr.resolution {
613                VarResolution::Local { slot } => slot + 1,
614                _ => 0,
615            })
616            .max()
617            .unwrap_or(0);
618        let name_slot = match name.resolution {
619            VarResolution::Local { slot } => slot + 1,
620            _ => 0,
621        };
622        inner.n_locals = max_slot.max(name_slot);
623
624        // Compile body
625        if body.is_empty() {
626            inner.emit.emit_op(Op::Nil);
627        } else {
628            for (i, expr) in body.iter().enumerate() {
629                inner.compile_expr(expr)?;
630                if i < body.len() - 1 {
631                    inner.emit.emit_op(Op::Pop);
632                }
633            }
634        }
635        inner.emit.emit_op(Op::Return);
636
637        let func_id = self.functions.len() as u16;
638        let (chunk, child_functions) = inner.finish();
639
640        let func = Function {
641            name: Some(name.name),
642            chunk,
643            upvalue_descs: Vec::new(),
644            arity: params.len() as u16,
645            has_rest: false,
646            local_names: Vec::new(),
647        };
648        self.functions.push(func);
649        self.functions.extend(child_functions);
650
651        // Emit MakeClosure for the loop function
652        self.emit.emit_op(Op::MakeClosure);
653        self.emit.emit_u16(func_id);
654        // TODO: named-let doesn't support capturing outer variables yet
655        self.emit.emit_u16(0);
656
657        // Store the closure in the loop name's slot
658        self.compile_var_store(name);
659
660        // Now call it with the initial binding values
661        self.compile_var_load(name)?;
662        for (_, init) in bindings {
663            self.compile_expr(init)?;
664        }
665        let argc = bindings.len() as u16;
666        self.emit.emit_op(Op::Call);
667        self.emit.emit_u16(argc);
668
669        Ok(())
670    }
671
672    // --- Do loop ---
673
674    fn compile_do(&mut self, do_loop: &ResolvedDoLoop) -> Result<(), SemaError> {
675        // 1. Compile init expressions and store to vars
676        for var in &do_loop.vars {
677            self.compile_expr(&var.init)?;
678            self.compile_var_store(&var.name);
679        }
680
681        // 2. Loop top
682        let loop_top = self.emit.current_pc();
683
684        // 3. Compile test
685        self.compile_expr(&do_loop.test)?;
686        let exit_jump = self.emit.emit_jump(Op::JumpIfTrue);
687
688        // 4. Compile loop body
689        for expr in &do_loop.body {
690            self.compile_expr(expr)?;
691            self.emit.emit_op(Op::Pop);
692        }
693
694        // 5. Compile step expressions and update vars
695        // First compile all step values, then store (to avoid using partially-updated vars)
696        let mut step_vars = Vec::new();
697        for var in &do_loop.vars {
698            if let Some(step) = &var.step {
699                self.compile_expr(step)?;
700                step_vars.push(&var.name);
701            }
702        }
703        // Store in reverse order (stack is LIFO)
704        for vr in step_vars.iter().rev() {
705            self.compile_var_store(vr);
706        }
707
708        // 6. Jump back to loop top
709        self.emit.emit_op(Op::Jump);
710        let jump_end_pc = self.emit.current_pc();
711        let offset = loop_top as i32 - (jump_end_pc as i32 + 4);
712        self.emit.emit_i32(offset);
713
714        // 7. Exit: compile result expressions
715        self.emit.patch_jump(exit_jump);
716        if do_loop.result.is_empty() {
717            self.emit.emit_op(Op::Nil);
718        } else {
719            for (i, expr) in do_loop.result.iter().enumerate() {
720                self.compile_expr(expr)?;
721                if i < do_loop.result.len() - 1 {
722                    self.emit.emit_op(Op::Pop);
723                }
724            }
725        }
726
727        Ok(())
728    }
729
730    // --- Exception handling ---
731
732    fn compile_try(
733        &mut self,
734        body: &[ResolvedExpr],
735        catch_var: &VarRef,
736        handler: &[ResolvedExpr],
737    ) -> Result<(), SemaError> {
738        let try_start = self.emit.current_pc();
739
740        // Compile body
741        self.compile_begin(body)?;
742        let try_end = self.emit.current_pc();
743
744        // Jump over handler on success
745        let success_jump = self.emit.emit_jump(Op::Jump);
746
747        let handler_pc = self.emit.current_pc();
748
749        // The VM will push the caught error value onto the stack
750        // Store it in the catch variable slot
751        let catch_slot = match catch_var.resolution {
752            VarResolution::Local { slot } => slot,
753            _ => 0,
754        };
755        self.emit.emit_op(Op::StoreLocal);
756        self.emit.emit_u16(catch_slot);
757
758        // Compile handler body
759        self.compile_begin(handler)?;
760
761        self.emit.patch_jump(success_jump);
762
763        // Add exception table entry
764        // We need to modify the emitter's chunk directly — use a deferred approach
765        // Store the exception entry data and apply after finish
766        // Actually, the Emitter gives us into_chunk which we can modify.
767        // Let's store exception entries separately and merge at finish.
768        // For now, store in the compiler and merge.
769        // We'll need to access the chunk... let's extend Emitter slightly or use a side vec.
770        self.add_exception_entry(ExceptionEntry {
771            try_start,
772            try_end,
773            handler_pc,
774            // Restore stack to locals + any operand values pushed before the try.
775            // Without this, unwinding from a callee frame would discard operand
776            // values belonging to a surrounding expression (e.g., a function being
777            // called with the try result as an argument).
778            stack_depth: self.n_locals + self.stack_height,
779            catch_slot,
780        });
781
782        Ok(())
783    }
784
785    fn add_exception_entry(&mut self, entry: ExceptionEntry) {
786        // We'll store these and apply when finishing the chunk
787        // For now, emit directly into the emitter's chunk
788        // Since Emitter doesn't expose this, we use a workaround:
789        // Store entries in Compiler and merge in finish_chunk
790        self.exception_entries.push(entry);
791    }
792
793    fn compile_throw(&mut self, val: &ResolvedExpr) -> Result<(), SemaError> {
794        self.compile_expr(val)?;
795        self.emit.emit_op(Op::Throw);
796        Ok(())
797    }
798
799    // --- Short-circuit boolean ---
800
801    fn compile_and(&mut self, exprs: &[ResolvedExpr]) -> Result<(), SemaError> {
802        if exprs.is_empty() {
803            self.emit.emit_op(Op::True);
804            return Ok(());
805        }
806
807        let mut jumps = Vec::new();
808        for (i, expr) in exprs.iter().enumerate() {
809            self.compile_expr(expr)?;
810            if i < exprs.len() - 1 {
811                // Dup so the value is preserved if we short-circuit
812                self.emit.emit_op(Op::Dup);
813                let jump = self.emit.emit_jump(Op::JumpIfFalse);
814                jumps.push(jump);
815                self.emit.emit_op(Op::Pop); // discard the dup'd value (continuing)
816            }
817        }
818        let end_jump = self.emit.emit_jump(Op::Jump);
819        // Short-circuit target: the dup'd falsy value is on the stack
820        for jump in jumps {
821            self.emit.patch_jump(jump);
822        }
823        self.emit.patch_jump(end_jump);
824        Ok(())
825    }
826
827    fn compile_or(&mut self, exprs: &[ResolvedExpr]) -> Result<(), SemaError> {
828        if exprs.is_empty() {
829            self.emit.emit_op(Op::False);
830            return Ok(());
831        }
832
833        let mut jumps = Vec::new();
834        for (i, expr) in exprs.iter().enumerate() {
835            self.compile_expr(expr)?;
836            if i < exprs.len() - 1 {
837                self.emit.emit_op(Op::Dup);
838                let jump = self.emit.emit_jump(Op::JumpIfTrue);
839                jumps.push(jump);
840                self.emit.emit_op(Op::Pop);
841            }
842        }
843        let end_jump = self.emit.emit_jump(Op::Jump);
844        for jump in jumps {
845            self.emit.patch_jump(jump);
846        }
847        self.emit.patch_jump(end_jump);
848        Ok(())
849    }
850
851    // --- Data constructors ---
852
853    fn compile_make_list(&mut self, exprs: &[ResolvedExpr]) -> Result<(), SemaError> {
854        for expr in exprs {
855            self.compile_expr(expr)?;
856        }
857        self.emit.emit_op(Op::MakeList);
858        self.emit.emit_u16(exprs.len() as u16);
859        Ok(())
860    }
861
862    fn compile_make_vector(&mut self, exprs: &[ResolvedExpr]) -> Result<(), SemaError> {
863        for expr in exprs {
864            self.compile_expr(expr)?;
865        }
866        self.emit.emit_op(Op::MakeVector);
867        self.emit.emit_u16(exprs.len() as u16);
868        Ok(())
869    }
870
871    fn compile_make_map(
872        &mut self,
873        pairs: &[(ResolvedExpr, ResolvedExpr)],
874    ) -> Result<(), SemaError> {
875        for (key, val) in pairs {
876            self.compile_expr(key)?;
877            self.compile_expr(val)?;
878        }
879        self.emit.emit_op(Op::MakeMap);
880        self.emit.emit_u16(pairs.len() as u16);
881        Ok(())
882    }
883
884    // --- Forms that delegate to runtime native calls ---
885    // These forms cannot be fully compiled to bytecode because they need
886    // access to the tree-walker (eval, macros, modules) or have complex
887    // runtime semantics. They are compiled as calls to well-known global
888    // functions that the VM/interpreter provides.
889
890    fn compile_eval(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
891        self.emit_runtime_call("__vm-eval", &[expr])
892    }
893
894    fn compile_load(&mut self, path: &ResolvedExpr) -> Result<(), SemaError> {
895        self.emit_runtime_call("__vm-load", &[path])
896    }
897
898    fn compile_import(&mut self, path: &ResolvedExpr, selective: &[Spur]) -> Result<(), SemaError> {
899        let sel_list: Vec<Value> = selective
900            .iter()
901            .map(|s| Value::symbol_from_spur(*s))
902            .collect();
903        self.emit_runtime_call_with_const("__vm-import", path, &Value::list(sel_list))
904    }
905
906    fn compile_module(
907        &mut self,
908        _name: Spur,
909        _exports: &[Spur],
910        body: &[ResolvedExpr],
911    ) -> Result<(), SemaError> {
912        // Compile module body sequentially
913        for (i, expr) in body.iter().enumerate() {
914            self.compile_expr(expr)?;
915            if i < body.len() - 1 {
916                self.emit.emit_op(Op::Pop);
917            }
918        }
919        if body.is_empty() {
920            self.emit.emit_op(Op::Nil);
921        }
922        // Module result is the last body expression
923        // Module registration is handled by the VM when it sees this was a module
924        Ok(())
925    }
926
927    fn compile_defmacro(
928        &mut self,
929        name: Spur,
930        params: &[Spur],
931        rest: &Option<Spur>,
932        body: &[ResolvedExpr],
933    ) -> Result<(), SemaError> {
934        // Defmacro at compile time — emit as a call to __vm-defmacro
935        // For now, compile the body as a lambda and register it
936        let param_vals: Vec<Value> = params.iter().map(|s| Value::symbol_from_spur(*s)).collect();
937        self.emit.emit_op(Op::LoadGlobal);
938        self.emit.emit_u32(spur_to_u32(intern("__vm-defmacro")));
939        self.emit.emit_const(Value::symbol_from_spur(name));
940        self.emit.emit_const(Value::list(param_vals));
941        if let Some(r) = rest {
942            self.emit.emit_const(Value::symbol_from_spur(*r));
943        } else {
944            self.emit.emit_op(Op::Nil);
945        }
946        // Compile body as a begin
947        self.compile_begin(body)?;
948        self.emit.emit_op(Op::Call);
949        self.emit.emit_u16(4);
950        Ok(())
951    }
952
953    fn compile_define_record_type(
954        &mut self,
955        type_name: Spur,
956        ctor_name: Spur,
957        pred_name: Spur,
958        field_names: &[Spur],
959        field_specs: &[(Spur, Spur)],
960    ) -> Result<(), SemaError> {
961        // Emit as a call to __vm-define-record-type with all info as constants
962        // Function must be pushed first (before args) to match VM calling convention
963        self.emit.emit_op(Op::LoadGlobal);
964        self.emit
965            .emit_u32(spur_to_u32(intern("__vm-define-record-type")));
966        self.emit.emit_const(Value::symbol_from_spur(type_name));
967        self.emit.emit_const(Value::symbol_from_spur(ctor_name));
968        self.emit.emit_const(Value::symbol_from_spur(pred_name));
969        let fields: Vec<Value> = field_names
970            .iter()
971            .map(|s| Value::symbol_from_spur(*s))
972            .collect();
973        self.emit.emit_const(Value::list(fields));
974        let specs: Vec<Value> = field_specs
975            .iter()
976            .map(|(f, a)| {
977                Value::list(vec![
978                    Value::symbol_from_spur(*f),
979                    Value::symbol_from_spur(*a),
980                ])
981            })
982            .collect();
983        self.emit.emit_const(Value::list(specs));
984        self.emit.emit_op(Op::Call);
985        self.emit.emit_u16(5);
986        Ok(())
987    }
988
989    fn compile_prompt(&mut self, entries: &[ResolvedPromptEntry]) -> Result<(), SemaError> {
990        // Function must be pushed first (before args) to match VM calling convention
991        self.emit.emit_op(Op::LoadGlobal);
992        self.emit.emit_u32(spur_to_u32(intern("__vm-prompt")));
993        // Compile each prompt entry and build a list
994        for entry in entries {
995            match entry {
996                ResolvedPromptEntry::RoleContent { role, parts } => {
997                    self.emit.emit_const(Value::string(role));
998                    for part in parts {
999                        self.compile_expr(part)?;
1000                    }
1001                    self.emit.emit_op(Op::MakeList);
1002                    self.emit.emit_u16(parts.len() as u16);
1003                    // Make a (role parts-list) pair
1004                    self.emit.emit_op(Op::MakeList);
1005                    self.emit.emit_u16(2);
1006                }
1007                ResolvedPromptEntry::Expr(expr) => {
1008                    self.compile_expr(expr)?;
1009                }
1010            }
1011        }
1012        self.emit.emit_op(Op::MakeList);
1013        self.emit.emit_u16(entries.len() as u16);
1014        self.emit.emit_op(Op::Call);
1015        self.emit.emit_u16(1);
1016        Ok(())
1017    }
1018
1019    fn compile_message(
1020        &mut self,
1021        role: &ResolvedExpr,
1022        parts: &[ResolvedExpr],
1023    ) -> Result<(), SemaError> {
1024        self.emit.emit_op(Op::LoadGlobal);
1025        self.emit.emit_u32(spur_to_u32(intern("__vm-message")));
1026        self.compile_expr(role)?;
1027        for part in parts {
1028            self.compile_expr(part)?;
1029        }
1030        self.emit.emit_op(Op::MakeList);
1031        self.emit.emit_u16(parts.len() as u16);
1032        self.emit.emit_op(Op::Call);
1033        self.emit.emit_u16(2);
1034        Ok(())
1035    }
1036
1037    fn compile_deftool(
1038        &mut self,
1039        name: Spur,
1040        description: &ResolvedExpr,
1041        parameters: &ResolvedExpr,
1042        handler: &ResolvedExpr,
1043    ) -> Result<(), SemaError> {
1044        self.emit.emit_op(Op::LoadGlobal);
1045        self.emit.emit_u32(spur_to_u32(intern("__vm-deftool")));
1046        self.emit.emit_const(Value::symbol_from_spur(name));
1047        self.compile_expr(description)?;
1048        self.compile_expr(parameters)?;
1049        self.compile_expr(handler)?;
1050        self.emit.emit_op(Op::Call);
1051        self.emit.emit_u16(4);
1052        Ok(())
1053    }
1054
1055    fn compile_defagent(&mut self, name: Spur, options: &ResolvedExpr) -> Result<(), SemaError> {
1056        self.emit.emit_op(Op::LoadGlobal);
1057        self.emit.emit_u32(spur_to_u32(intern("__vm-defagent")));
1058        self.emit.emit_const(Value::symbol_from_spur(name));
1059        self.compile_expr(options)?;
1060        self.emit.emit_op(Op::Call);
1061        self.emit.emit_u16(2);
1062        Ok(())
1063    }
1064
1065    fn compile_delay(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
1066        // Delay wraps expr in a zero-arg lambda (thunk)
1067        // The resolver already handles this if lowered as a lambda,
1068        // but if it comes through as Delay, compile as a call to __vm-delay
1069        self.emit.emit_op(Op::LoadGlobal);
1070        self.emit.emit_u32(spur_to_u32(intern("__vm-delay")));
1071        self.compile_expr(expr)?;
1072        self.emit.emit_op(Op::Call);
1073        self.emit.emit_u16(1);
1074        Ok(())
1075    }
1076
1077    fn compile_force(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
1078        self.emit.emit_op(Op::LoadGlobal);
1079        self.emit.emit_u32(spur_to_u32(intern("__vm-force")));
1080        self.compile_expr(expr)?;
1081        self.emit.emit_op(Op::Call);
1082        self.emit.emit_u16(1);
1083        Ok(())
1084    }
1085
1086    fn compile_macroexpand(&mut self, expr: &ResolvedExpr) -> Result<(), SemaError> {
1087        self.emit.emit_op(Op::LoadGlobal);
1088        self.emit.emit_u32(spur_to_u32(intern("__vm-macroexpand")));
1089        self.compile_expr(expr)?;
1090        self.emit.emit_op(Op::Call);
1091        self.emit.emit_u16(1);
1092        Ok(())
1093    }
1094
1095    // --- Helper: emit a call to a well-known runtime function ---
1096
1097    fn emit_runtime_call(&mut self, name: &str, args: &[&ResolvedExpr]) -> Result<(), SemaError> {
1098        self.emit.emit_op(Op::LoadGlobal);
1099        self.emit.emit_u32(spur_to_u32(intern(name)));
1100        for arg in args {
1101            self.compile_expr(arg)?;
1102        }
1103        self.emit.emit_op(Op::Call);
1104        self.emit.emit_u16(args.len() as u16);
1105        Ok(())
1106    }
1107
1108    fn emit_runtime_call_with_const(
1109        &mut self,
1110        name: &str,
1111        arg1: &ResolvedExpr,
1112        arg2: &Value,
1113    ) -> Result<(), SemaError> {
1114        self.emit.emit_op(Op::LoadGlobal);
1115        self.emit.emit_u32(spur_to_u32(intern(name)));
1116        self.compile_expr(arg1)?;
1117        self.emit.emit_const(arg2.clone());
1118        self.emit.emit_op(Op::Call);
1119        self.emit.emit_u16(2);
1120        Ok(())
1121    }
1122}
1123
1124fn spur_to_u32(spur: Spur) -> u32 {
1125    spur.into_inner().get()
1126}
1127
1128#[cfg(test)]
1129mod tests {
1130    use super::*;
1131    use crate::lower::lower;
1132    use crate::resolve::resolve;
1133
1134    fn compile_str(input: &str) -> CompileResult {
1135        let val = sema_reader::read(input).unwrap();
1136        let core = lower(&val).unwrap();
1137        let resolved = resolve(&core).unwrap();
1138        compile(&resolved).unwrap()
1139    }
1140
1141    fn compile_many_str(input: &str) -> CompileResult {
1142        let vals = sema_reader::read_many(input).unwrap();
1143        let mut resolved = Vec::new();
1144        for val in &vals {
1145            let core = lower(val).unwrap();
1146            resolved.push(resolve(&core).unwrap());
1147        }
1148        compile_many(&resolved).unwrap()
1149    }
1150
1151    /// Extract just the opcode bytes from a chunk, skipping operands.
1152    fn extract_ops(chunk: &Chunk) -> Vec<Op> {
1153        let code = &chunk.code;
1154        let mut ops = Vec::new();
1155        let mut pc = 0;
1156        while pc < code.len() {
1157            let op = unsafe { std::mem::transmute::<u8, Op>(code[pc]) };
1158            ops.push(op);
1159            pc += 1;
1160            // Skip operands based on opcode
1161            match op {
1162                Op::Const
1163                | Op::LoadLocal
1164                | Op::StoreLocal
1165                | Op::LoadUpvalue
1166                | Op::StoreUpvalue
1167                | Op::Call
1168                | Op::TailCall
1169                | Op::MakeList
1170                | Op::MakeVector
1171                | Op::MakeMap
1172                | Op::MakeHashMap => pc += 2,
1173                Op::LoadGlobal | Op::StoreGlobal | Op::DefineGlobal => pc += 4,
1174                Op::CallGlobal => pc += 6, // u32 spur + u16 argc
1175                Op::Jump | Op::JumpIfFalse | Op::JumpIfTrue => pc += 4,
1176                Op::CallNative => pc += 4,
1177                Op::MakeClosure => {
1178                    let func_id = u16::from_le_bytes([code[pc], code[pc + 1]]);
1179                    let n_upvalues = u16::from_le_bytes([code[pc + 2], code[pc + 3]]);
1180                    pc += 4;
1181                    pc += n_upvalues as usize * 4; // each upvalue is u16 + u16
1182                    let _ = func_id;
1183                }
1184                _ => {} // zero-operand opcodes
1185            }
1186        }
1187        ops
1188    }
1189
1190    /// Read the i32 operand of a Jump/JumpIfFalse/JumpIfTrue at the given opcode PC.
1191    fn read_jump_offset(chunk: &Chunk, op_pc: usize) -> i32 {
1192        i32::from_le_bytes([
1193            chunk.code[op_pc + 1],
1194            chunk.code[op_pc + 2],
1195            chunk.code[op_pc + 3],
1196            chunk.code[op_pc + 4],
1197        ])
1198    }
1199
1200    // --- Literal compilation ---
1201
1202    #[test]
1203    fn test_compile_int_literal() {
1204        let result = compile_str("42");
1205        let ops = extract_ops(&result.chunk);
1206        assert_eq!(ops, vec![Op::Const, Op::Return]);
1207        assert_eq!(result.chunk.consts[0], Value::int(42));
1208    }
1209
1210    #[test]
1211    fn test_compile_nil() {
1212        let result = compile_str("()");
1213        let ops = extract_ops(&result.chunk);
1214        assert_eq!(ops, vec![Op::Nil, Op::Return]);
1215    }
1216
1217    #[test]
1218    fn test_compile_true_false() {
1219        let t = compile_str("#t");
1220        assert_eq!(extract_ops(&t.chunk), vec![Op::True, Op::Return]);
1221
1222        let f = compile_str("#f");
1223        assert_eq!(extract_ops(&f.chunk), vec![Op::False, Op::Return]);
1224    }
1225
1226    #[test]
1227    fn test_compile_string_literal() {
1228        let result = compile_str("\"hello\"");
1229        let ops = extract_ops(&result.chunk);
1230        assert_eq!(ops, vec![Op::Const, Op::Return]);
1231        assert_eq!(result.chunk.consts[0].as_str(), Some("hello"));
1232    }
1233
1234    // --- Variable access ---
1235
1236    #[test]
1237    fn test_compile_global_var() {
1238        let result = compile_str("x");
1239        let ops = extract_ops(&result.chunk);
1240        assert_eq!(ops, vec![Op::LoadGlobal, Op::Return]);
1241    }
1242
1243    // --- Control flow ---
1244
1245    #[test]
1246    fn test_compile_if() {
1247        let result = compile_str("(if #t 1 2)");
1248        let ops = extract_ops(&result.chunk);
1249        // TRUE, JumpIfFalse, CONST(1), Jump, CONST(2), RETURN
1250        assert_eq!(
1251            ops,
1252            vec![
1253                Op::True,
1254                Op::JumpIfFalse,
1255                Op::Const,
1256                Op::Jump,
1257                Op::Const,
1258                Op::Return
1259            ]
1260        );
1261    }
1262
1263    #[test]
1264    fn test_compile_nested_if() {
1265        let result = compile_str("(if #t (if #f 1 2) 3)");
1266        let ops = extract_ops(&result.chunk);
1267        let jif_count = ops.iter().filter(|&&op| op == Op::JumpIfFalse).count();
1268        assert_eq!(jif_count, 2);
1269    }
1270
1271    #[test]
1272    fn test_compile_begin() {
1273        let result = compile_str("(begin 1 2 3)");
1274        let ops = extract_ops(&result.chunk);
1275        // CONST(1), POP, CONST(2), POP, CONST(3), RETURN
1276        assert_eq!(
1277            ops,
1278            vec![
1279                Op::Const,
1280                Op::Pop,
1281                Op::Const,
1282                Op::Pop,
1283                Op::Const,
1284                Op::Return
1285            ]
1286        );
1287    }
1288
1289    // --- Define ---
1290
1291    #[test]
1292    fn test_compile_define() {
1293        let result = compile_str("(define x 42)");
1294        let ops = extract_ops(&result.chunk);
1295        // CONST(42), DefineGlobal, Nil, Return
1296        assert_eq!(ops, vec![Op::Const, Op::DefineGlobal, Op::Nil, Op::Return]);
1297    }
1298
1299    // --- Lambda ---
1300
1301    #[test]
1302    fn test_compile_lambda() {
1303        let result = compile_str("(lambda (x) x)");
1304        assert_eq!(result.functions.len(), 1);
1305        let func = &result.functions[0];
1306        assert_eq!(func.arity, 1);
1307        assert!(!func.has_rest);
1308
1309        // Inner function: LoadLocal0, Return
1310        let inner_ops = extract_ops(&func.chunk);
1311        assert_eq!(inner_ops, vec![Op::LoadLocal0, Op::Return]);
1312
1313        // Top-level: MakeClosure, Return
1314        let top_ops = extract_ops(&result.chunk);
1315        assert_eq!(top_ops, vec![Op::MakeClosure, Op::Return]);
1316    }
1317
1318    #[test]
1319    fn test_compile_lambda_rest_param() {
1320        let result = compile_str("(lambda (x . rest) x)");
1321        assert_eq!(result.functions.len(), 1);
1322        let func = &result.functions[0];
1323        assert_eq!(func.arity, 1);
1324        assert!(func.has_rest);
1325    }
1326
1327    // --- Calls: non-tail vs tail ---
1328
1329    #[test]
1330    fn test_compile_non_tail_call() {
1331        // Top-level call is NOT in tail position of a lambda
1332        // Intrinsic builtins like + compile to inline opcodes
1333        let result = compile_str("(+ 1 2)");
1334        let ops = extract_ops(&result.chunk);
1335        // Const(1), Const(2), AddInt, Return
1336        assert_eq!(ops, vec![Op::Const, Op::Const, Op::AddInt, Op::Return]);
1337    }
1338
1339    #[test]
1340    fn test_compile_tail_call() {
1341        let result = compile_str("(lambda () (f 1))");
1342        assert_eq!(result.functions.len(), 1);
1343        let inner_ops = extract_ops(&result.functions[0].chunk);
1344        // LoadGlobal(f), Const(1), TailCall(1), Return
1345        assert_eq!(
1346            inner_ops,
1347            vec![Op::LoadGlobal, Op::Const, Op::TailCall, Op::Return]
1348        );
1349        // Verify it's TailCall, NOT Call
1350        assert!(!inner_ops.contains(&Op::Call));
1351    }
1352
1353    #[test]
1354    fn test_compile_non_tail_in_begin() {
1355        // (lambda () (f 1) (g 2)) — first call is NOT tail, second IS tail
1356        let result = compile_str("(lambda () (f 1) (g 2))");
1357        let inner_ops = extract_ops(&result.functions[0].chunk);
1358        // f call: Const, CallGlobal(f, 1), Pop  (non-tail uses fused CallGlobal)
1359        // g call: LoadGlobal, Const, TailCall, Return  (tail call can't use CallGlobal)
1360        assert_eq!(
1361            inner_ops,
1362            vec![
1363                Op::Const,
1364                Op::CallGlobal,
1365                Op::Pop,
1366                Op::LoadGlobal,
1367                Op::Const,
1368                Op::TailCall,
1369                Op::Return
1370            ]
1371        );
1372    }
1373
1374    // --- Intrinsic recognition ---
1375
1376    #[test]
1377    fn test_compile_intrinsic_sub() {
1378        let result = compile_str("(- 5 3)");
1379        let ops = extract_ops(&result.chunk);
1380        assert_eq!(ops, vec![Op::Const, Op::Const, Op::SubInt, Op::Return]);
1381    }
1382
1383    #[test]
1384    fn test_compile_intrinsic_lt() {
1385        let result = compile_str("(< 1 2)");
1386        let ops = extract_ops(&result.chunk);
1387        assert_eq!(ops, vec![Op::Const, Op::Const, Op::LtInt, Op::Return]);
1388    }
1389
1390    #[test]
1391    fn test_compile_intrinsic_not() {
1392        let result = compile_str("(not #t)");
1393        let ops = extract_ops(&result.chunk);
1394        assert_eq!(ops, vec![Op::True, Op::Not, Op::Return]);
1395    }
1396
1397    #[test]
1398    fn test_compile_intrinsic_negate() {
1399        let result = compile_str("(- 5)");
1400        let ops = extract_ops(&result.chunk);
1401        assert_eq!(ops, vec![Op::Const, Op::Negate, Op::Return]);
1402    }
1403
1404    #[test]
1405    fn test_compile_intrinsic_in_tail_position() {
1406        // Intrinsics work in tail position too (they don't create frames)
1407        let result = compile_str("(lambda (x y) (+ x y))");
1408        let inner_ops = extract_ops(&result.functions[0].chunk);
1409        assert_eq!(
1410            inner_ops,
1411            vec![Op::LoadLocal0, Op::LoadLocal1, Op::AddInt, Op::Return]
1412        );
1413    }
1414
1415    #[test]
1416    fn test_compile_non_intrinsic_still_uses_call_global() {
1417        // Non-intrinsic globals still use CallGlobal
1418        let result = compile_str("(foo 1 2)");
1419        let ops = extract_ops(&result.chunk);
1420        assert_eq!(ops, vec![Op::Const, Op::Const, Op::CallGlobal, Op::Return]);
1421    }
1422
1423    #[test]
1424    fn test_compile_if_not_peephole() {
1425        // (if (not x) then else) → compile x, JumpIfTrue
1426        let result = compile_str("(lambda (x) (if (not x) 1 2))");
1427        let inner_ops = extract_ops(&result.functions[0].chunk);
1428        // LoadLocal0(x), JumpIfTrue, Const(1), Jump, Const(2), Return
1429        assert_eq!(
1430            inner_ops,
1431            vec![
1432                Op::LoadLocal0,
1433                Op::JumpIfTrue,
1434                Op::Const,
1435                Op::Jump,
1436                Op::Const,
1437                Op::Return
1438            ]
1439        );
1440        // Should NOT contain Not opcode
1441        assert!(!inner_ops.contains(&Op::Not));
1442    }
1443
1444    // --- Let forms ---
1445
1446    #[test]
1447    fn test_compile_let() {
1448        let result = compile_str("(lambda () (let ((x 1) (y 2)) x))");
1449        let inner_ops = extract_ops(&result.functions[0].chunk);
1450        // CONST(1), CONST(2), StoreLocal1(y=1), StoreLocal0(x=0), LoadLocal0(x=0), Return
1451        assert_eq!(
1452            inner_ops,
1453            vec![
1454                Op::Const,
1455                Op::Const,
1456                Op::StoreLocal1,
1457                Op::StoreLocal0,
1458                Op::LoadLocal0,
1459                Op::Return
1460            ]
1461        );
1462    }
1463
1464    #[test]
1465    fn test_compile_let_star() {
1466        // let* stores sequentially so later bindings see earlier ones
1467        let result = compile_str("(lambda () (let* ((x 1) (y x)) y))");
1468        let inner_ops = extract_ops(&result.functions[0].chunk);
1469        // CONST(1), StoreLocal0(x), LoadLocal0(x), StoreLocal1(y), LoadLocal1(y), Return
1470        assert_eq!(
1471            inner_ops,
1472            vec![
1473                Op::Const,
1474                Op::StoreLocal0,
1475                Op::LoadLocal0,
1476                Op::StoreLocal1,
1477                Op::LoadLocal1,
1478                Op::Return
1479            ]
1480        );
1481    }
1482
1483    #[test]
1484    fn test_compile_letrec() {
1485        let result = compile_str("(lambda () (letrec ((x 1)) x))");
1486        let inner_ops = extract_ops(&result.functions[0].chunk);
1487        // Nil, StoreLocal0(x), CONST(1), StoreLocal0(x), LoadLocal0(x), Return
1488        assert_eq!(
1489            inner_ops,
1490            vec![
1491                Op::Nil,
1492                Op::StoreLocal0,
1493                Op::Const,
1494                Op::StoreLocal0,
1495                Op::LoadLocal0,
1496                Op::Return
1497            ]
1498        );
1499    }
1500
1501    // --- Set! ---
1502
1503    #[test]
1504    fn test_compile_set_local() {
1505        let result = compile_str("(lambda (x) (set! x 42))");
1506        let inner_ops = extract_ops(&result.functions[0].chunk);
1507        // CONST(42), Dup, StoreLocal0(0), Return
1508        assert_eq!(
1509            inner_ops,
1510            vec![Op::Const, Op::Dup, Op::StoreLocal0, Op::Return]
1511        );
1512    }
1513
1514    #[test]
1515    fn test_compile_set_global() {
1516        let result = compile_str("(set! x 42)");
1517        let ops = extract_ops(&result.chunk);
1518        // CONST(42), Dup, StoreGlobal, Return
1519        assert_eq!(ops, vec![Op::Const, Op::Dup, Op::StoreGlobal, Op::Return]);
1520    }
1521
1522    #[test]
1523    fn test_compile_set_upvalue() {
1524        // Inner lambda sets outer variable
1525        let result = compile_str("(lambda (x) (lambda () (set! x 1)))");
1526        assert_eq!(result.functions.len(), 2);
1527        let inner_ops = extract_ops(&result.functions[1].chunk);
1528        // CONST(1), Dup, StoreUpvalue(0), Return
1529        assert_eq!(
1530            inner_ops,
1531            vec![Op::Const, Op::Dup, Op::StoreUpvalue, Op::Return]
1532        );
1533    }
1534
1535    // --- Short-circuit boolean ---
1536
1537    #[test]
1538    fn test_compile_and_empty() {
1539        let result = compile_str("(and)");
1540        let ops = extract_ops(&result.chunk);
1541        assert_eq!(ops, vec![Op::True, Op::Return]);
1542    }
1543
1544    #[test]
1545    fn test_compile_or_empty() {
1546        let result = compile_str("(or)");
1547        let ops = extract_ops(&result.chunk);
1548        assert_eq!(ops, vec![Op::False, Op::Return]);
1549    }
1550
1551    #[test]
1552    fn test_compile_and_short_circuit() {
1553        let result = compile_str("(and 1 2)");
1554        let ops = extract_ops(&result.chunk);
1555        // CONST(1), Dup, JumpIfFalse, Pop, CONST(2), Jump, Return
1556        assert_eq!(
1557            ops,
1558            vec![
1559                Op::Const,
1560                Op::Dup,
1561                Op::JumpIfFalse,
1562                Op::Pop,
1563                Op::Const,
1564                Op::Jump,
1565                Op::Return
1566            ]
1567        );
1568    }
1569
1570    #[test]
1571    fn test_compile_or_short_circuit() {
1572        let result = compile_str("(or 1 2)");
1573        let ops = extract_ops(&result.chunk);
1574        // CONST(1), Dup, JumpIfTrue, Pop, CONST(2), Jump, Return
1575        assert_eq!(
1576            ops,
1577            vec![
1578                Op::Const,
1579                Op::Dup,
1580                Op::JumpIfTrue,
1581                Op::Pop,
1582                Op::Const,
1583                Op::Jump,
1584                Op::Return
1585            ]
1586        );
1587    }
1588
1589    // --- Data constructors ---
1590
1591    #[test]
1592    fn test_compile_vector_literal() {
1593        let result = compile_str("[1 2 3]");
1594        let ops = extract_ops(&result.chunk);
1595        assert_eq!(
1596            ops,
1597            vec![Op::Const, Op::Const, Op::Const, Op::MakeVector, Op::Return]
1598        );
1599    }
1600
1601    #[test]
1602    fn test_compile_quote() {
1603        let result = compile_str("'(1 2 3)");
1604        let ops = extract_ops(&result.chunk);
1605        assert_eq!(ops, vec![Op::Const, Op::Return]);
1606    }
1607
1608    // --- Exception handling ---
1609
1610    #[test]
1611    fn test_compile_throw() {
1612        let result = compile_str("(throw 42)");
1613        let ops = extract_ops(&result.chunk);
1614        assert_eq!(ops, vec![Op::Const, Op::Throw, Op::Return]);
1615    }
1616
1617    #[test]
1618    fn test_compile_try_catch() {
1619        let result = compile_str("(lambda () (try (/ 1 0) (catch e e)))");
1620        let func = &result.functions[0];
1621        // Verify exception table
1622        assert_eq!(func.chunk.exception_table.len(), 1);
1623        let entry = &func.chunk.exception_table[0];
1624        assert!(entry.try_start < entry.try_end);
1625        assert!(entry.handler_pc > entry.try_end);
1626        assert!((entry.handler_pc as usize) < func.chunk.code.len());
1627        // Handler should store to catch slot then load it
1628        let ops = extract_ops(&func.chunk);
1629        assert!(ops.contains(&Op::StoreLocal)); // store caught error
1630                                                // The jump-over-handler should be present
1631        assert!(ops.contains(&Op::Jump));
1632    }
1633
1634    // --- Closures ---
1635
1636    #[test]
1637    fn test_compile_closure_with_upvalue() {
1638        let result = compile_str("(lambda (x) (lambda () x))");
1639        assert_eq!(result.functions.len(), 2);
1640        // Outer function: MakeClosure for inner, Return
1641        let outer = &result.functions[0];
1642        let outer_ops = extract_ops(&outer.chunk);
1643        assert!(outer_ops.contains(&Op::MakeClosure));
1644        // Inner function: LoadUpvalue(0), Return
1645        let inner = &result.functions[1];
1646        let inner_ops = extract_ops(&inner.chunk);
1647        assert_eq!(inner_ops, vec![Op::LoadUpvalue, Op::Return]);
1648        // Inner function's upvalue_descs should match
1649        assert_eq!(inner.upvalue_descs.len(), 1);
1650        assert!(matches!(
1651            inner.upvalue_descs[0],
1652            UpvalueDesc::ParentLocal(0)
1653        ));
1654    }
1655
1656    #[test]
1657    fn test_compile_nested_lambda_func_ids() {
1658        // (lambda () (lambda () 1) (lambda () 2))
1659        // Outer is func 0, inner lambdas are func 1 and func 2
1660        let result = compile_str("(lambda () (lambda () 1) (lambda () 2))");
1661        assert_eq!(result.functions.len(), 3);
1662        // Verify each inner function compiles correctly
1663        let f1 = &result.functions[1];
1664        let f1_ops = extract_ops(&f1.chunk);
1665        assert_eq!(f1_ops, vec![Op::Const, Op::Return]);
1666        assert_eq!(f1.chunk.consts[0], Value::int(1));
1667
1668        let f2 = &result.functions[2];
1669        let f2_ops = extract_ops(&f2.chunk);
1670        assert_eq!(f2_ops, vec![Op::Const, Op::Return]);
1671        assert_eq!(f2.chunk.consts[0], Value::int(2));
1672
1673        // Verify the outer function has two MakeClosure instructions
1674        // with func_ids 1 and 2 (checking the raw bytes)
1675        let outer = &result.functions[0];
1676        let outer_ops = extract_ops(&outer.chunk);
1677        let mc_count = outer_ops
1678            .iter()
1679            .filter(|&&op| op == Op::MakeClosure)
1680            .count();
1681        assert_eq!(mc_count, 2);
1682    }
1683
1684    // --- Do loop ---
1685
1686    #[test]
1687    fn test_compile_do_loop() {
1688        let result = compile_str("(lambda () (do ((i 0 (+ i 1))) ((= i 10) i) (display i)))");
1689        let func = &result.functions[0];
1690        let ops = extract_ops(&func.chunk);
1691        // Must contain a backward Jump (negative offset) for the loop back-edge
1692        let jump_pcs: Vec<usize> = (0..func.chunk.code.len())
1693            .filter(|&pc| func.chunk.code[pc] == Op::Jump as u8)
1694            .collect();
1695        // Find the back-edge jump (should have a negative offset)
1696        let has_back_edge = jump_pcs
1697            .iter()
1698            .any(|&pc| read_jump_offset(&func.chunk, pc) < 0);
1699        assert!(has_back_edge, "do loop must have a backward jump");
1700        // Must have JumpIfTrue for the exit condition
1701        assert!(ops.contains(&Op::JumpIfTrue));
1702    }
1703
1704    // --- Named let ---
1705
1706    #[test]
1707    fn test_compile_named_let() {
1708        // Named let desugars to letrec+lambda, compiled as letrec with a closure
1709        let result = compile_str("(lambda () (let loop ((n 10)) (if (= n 0) n (loop (- n 1)))))");
1710        // Should have at least 2 functions: outer lambda + loop lambda
1711        assert!(result.functions.len() >= 2);
1712        // The outer function should contain MakeClosure (for the loop) + TailCall (initial invocation in tail position)
1713        let outer = &result.functions[0];
1714        let outer_ops = extract_ops(&outer.chunk);
1715        assert!(outer_ops.contains(&Op::MakeClosure));
1716        assert!(outer_ops.contains(&Op::TailCall) || outer_ops.contains(&Op::Call));
1717    }
1718
1719    // --- compile_many ---
1720
1721    #[test]
1722    fn test_compile_many_empty() {
1723        let result = compile_many(&[]).unwrap();
1724        let ops = extract_ops(&result.chunk);
1725        assert_eq!(ops, vec![Op::Nil, Op::Return]);
1726    }
1727
1728    #[test]
1729    fn test_compile_many_multiple() {
1730        let result = compile_many_str("1 2 3");
1731        let ops = extract_ops(&result.chunk);
1732        // CONST(1), Pop, CONST(2), Pop, CONST(3), Return
1733        assert_eq!(
1734            ops,
1735            vec![
1736                Op::Const,
1737                Op::Pop,
1738                Op::Const,
1739                Op::Pop,
1740                Op::Const,
1741                Op::Return
1742            ]
1743        );
1744    }
1745
1746    #[test]
1747    fn test_compile_many_single() {
1748        let result = compile_many_str("42");
1749        let ops = extract_ops(&result.chunk);
1750        // CONST(42), Return (no Pop)
1751        assert_eq!(ops, vec![Op::Const, Op::Return]);
1752    }
1753
1754    // --- Calling convention: function must be below args ---
1755
1756    #[test]
1757    fn test_calling_convention_runtime_call() {
1758        // (eval 42) compiles as: LoadGlobal(__vm-eval), CONST(42), Call(1)
1759        let result = compile_str("(eval 42)");
1760        let ops = extract_ops(&result.chunk);
1761        assert_eq!(ops, vec![Op::LoadGlobal, Op::Const, Op::Call, Op::Return]);
1762        // The first op must be LoadGlobal (function loaded first)
1763        assert_eq!(ops[0], Op::LoadGlobal);
1764    }
1765
1766    // --- Map literal ---
1767
1768    #[test]
1769    fn test_compile_map_literal() {
1770        let result = compile_str("{:a 1 :b 2}");
1771        let ops = extract_ops(&result.chunk);
1772        // key, val, key, val, MakeMap, Return
1773        assert_eq!(
1774            ops,
1775            vec![
1776                Op::Const,
1777                Op::Const,
1778                Op::Const,
1779                Op::Const,
1780                Op::MakeMap,
1781                Op::Return
1782            ]
1783        );
1784    }
1785
1786    #[test]
1787    fn test_compile_depth_limit() {
1788        // Build deeply nested Begin(Begin(Begin(...Const(1)...))) bypassing lowering
1789        let mut expr = ResolvedExpr::Const(Value::int(1));
1790        for _ in 0..300 {
1791            expr = ResolvedExpr::Begin(vec![expr]);
1792        }
1793        let result = compile(&expr);
1794        let err = result.err().expect("expected compilation to fail");
1795        let msg = err.to_string();
1796        assert!(
1797            msg.contains("compilation depth"),
1798            "expected compilation depth error, got: {msg}"
1799        );
1800    }
1801}
sema_vm/compiler.rs

sema_vm/
compiler.rs
