Compile and Run v5 (Capstone)

hard · compilers, bytecode, vm, capstone

Compile and Run v5 (Capstone)

Connect the full v5 compiler pipeline and execute the program.

Function signature

func CompileAndRun(src string) (Value, error)

Pipeline requirements

Your function must:

Lex source into tokens (Lex)
Parse tokens into a program AST (Parse)
Run semantic analysis (Analyze)
Compile modules to bytecode (CompileModules)
Link modules into a single program (Link)
Encode to BC2 text (Encode)
Decode back to bytecode (Decode)
Execute in the VM (Run on a new VM)

Return the final VM result.

Error handling

If lexing or parsing fails, return that error.
If semantic analysis returns errors, return the first error as error.
If linking, decoding, or execution fails, return that error.

Notes

The helper functions and types are provided in this file.
Keep the implementation readable.

Before implementation

Use the module’s worked reconstruction and independent debugging lab to predict an intermediate artifact first. Preserve one failing counterexample while implementing the stated API. The lesson’s transfer task uses a fresh case after the guided trace.

package solution

import (
	"bufio"
	"fmt"
	"strconv"
	"strings"
)

type TokenKind int

const (
	TokenEOF TokenKind = iota
	TokenIdent
	TokenNumber
	TokenString
	TokenLet
	TokenVar
	TokenConst
	TokenFn
	TokenIf
	TokenElse
	TokenWhile
	TokenFor
	TokenReturn
	TokenBreak
	TokenContinue
	TokenModule
	TokenImport
	TokenExport
	TokenAs
	TokenTrue
	TokenFalse
	TokenNil
	TokenPlus
	TokenMinus
	TokenStar
	TokenSlash
	TokenAssign
	TokenEqual
	TokenNotEqual
	TokenLess
	TokenLessEqual
	TokenGreater
	TokenGreaterEqual
	TokenBang
	TokenAndAnd
	TokenOrOr
	TokenDot
	TokenLParen
	TokenRParen
	TokenLBrace
	TokenRBrace
	TokenLBracket
	TokenRBracket
	TokenComma
	TokenSemicolon
	TokenColon
)

type Token struct {
	Kind   TokenKind
	Lexeme string
	Line   int
	Col    int
}

type VarKind int

const (
	VarLet VarKind = iota
	VarVar
	VarConst
)

type StmtKind int

const (
	StmtVar StmtKind = iota
	StmtAssign
	StmtExpr
	StmtIf
	StmtWhile
	StmtFor
	StmtBreak
	StmtContinue
	StmtReturn
	StmtBlock
	StmtFn
)

type Stmt struct {
	Kind     StmtKind
	Exported bool
	VarKind  VarKind
	Name     string
	Expr     *Expr
	Target   *Expr
	Body     []*Stmt
	Else     []*Stmt
	Params   []string
	Init     *Stmt
	Post     *Stmt
	Cond     *Expr
}

type Program struct {
	Modules []*Module
}

type Module struct {
	Name    string
	Imports []Import
	Stmts   []*Stmt
}

type Import struct {
	Name  string
	Alias string
}

type ExprKind int

const (
	ExprNumber ExprKind = iota
	ExprString
	ExprBool
	ExprNil
	ExprIdent
	ExprUnary
	ExprBinary
	ExprCall
	ExprArray
	ExprMap
	ExprIndex
	ExprMember
)

type MapPair struct {
	Key   *Expr
	Value *Expr
}

type Expr struct {
	Kind  ExprKind
	Value string
	Left  *Expr
	Right *Expr
	Args  []*Expr
	Elems []*Expr
	Pairs []MapPair
}

type OpCode int

const (
	OpPushNum OpCode = iota
	OpPushStr
	OpPushBool
	OpPushNil
	OpLoad
	OpStore
	OpDefineVar
	OpDefineConst
	OpAdd
	OpSub
	OpMul
	OpDiv
	OpNeg
	OpNot
	OpEq
	OpNeq
	OpLt
	OpLte
	OpGt
	OpGte
	OpJump
	OpJumpIfFalse
	OpCall
	OpReturn
	OpEnterScope
	OpExitScope
	OpPop
	OpMakeClosure
	OpMakeArray
	OpMakeMap
	OpGetIndex
	OpSetIndex
)

type Instr struct {
	Op  OpCode
	Int int
	Str string
}

type Function struct {
	ID     int
	Name   string
	Params []string
	Code   []Instr
}

type Bytecode struct {
	Functions []Function
	Main      []Instr
}

type ValueKind int

const (
	ValueNumber ValueKind = iota
	ValueString
	ValueBool
	ValueNil
	ValueArray
	ValueMap
	ValueClosure
)

type Value struct {
	Kind ValueKind
	Num  int
	Str  string
	Bool bool
	Obj  *Object
}

type ObjKind int

const (
	ObjArray ObjKind = iota
	ObjMap
	ObjClosure
)

type Object struct {
	Kind    ObjKind
	Marked  bool
	Array   []Value
	Map     map[hashKey]Value
	Closure *Closure
}

type Closure struct {
	FuncID int
	Env    *Env
}

type hashKey struct {
	kind ValueKind
	num  int
	str  string
	b    bool
}

// CompileAndRun connects the whole pipeline and executes the program.
func CompileAndRun(src string) (Value, error) {
	// TODO: implement the full pipeline.
	return Value{}, fmt.Errorf("not implemented")
}

// Lex converts source text into tokens.
func Lex(src string) ([]Token, error) {
	var tokens []Token
	line := 1
	col := 1
	i := 0

for i < len(src) {
		ch := src[i]

switch ch {
		case ' ', '\t', '\r':
			i++
			col++
			continue
		case '\n':
			i++
			line++
			col = 1
			continue
		case '/':
			if i+1 < len(src) && src[i+1] == '/' {
				i += 2
				col += 2
				for i < len(src) && src[i] != '\n' {
					i++
					col++
				}
				continue
			}
		}

startLine := line
		startCol := col

if isAlpha(ch) || ch == '_' {
			start := i
			i++
			col++
			for i < len(src) && (isAlphaNum(src[i]) || src[i] == '_') {
				i++
				col++
			}
			lex := src[start:i]
			kind := identKind(lex)
			tokens = append(tokens, Token{Kind: kind, Lexeme: lex, Line: startLine, Col: startCol})
			continue
		}

if isDigit(ch) {
			start := i
			i++
			col++
			for i < len(src) && isDigit(src[i]) {
				i++
				col++
			}
			lex := src[start:i]
			tokens = append(tokens, Token{Kind: TokenNumber, Lexeme: lex, Line: startLine, Col: startCol})
			continue
		}

switch ch {
		case '"':
			lex, next, nextCol, err := readString(src, i, line, col)
			if err != nil {
				return nil, err
			}
			tokens = append(tokens, Token{Kind: TokenString, Lexeme: lex, Line: startLine, Col: startCol})
			i = next
			col = nextCol
		case '+':
			tokens = append(tokens, Token{Kind: TokenPlus, Lexeme: "+", Line: startLine, Col: startCol})
			i++
			col++
		case '-':
			tokens = append(tokens, Token{Kind: TokenMinus, Lexeme: "-", Line: startLine, Col: startCol})
			i++
			col++
		case '*':
			tokens = append(tokens, Token{Kind: TokenStar, Lexeme: "*", Line: startLine, Col: startCol})
			i++
			col++
		case '/':
			tokens = append(tokens, Token{Kind: TokenSlash, Lexeme: "/", Line: startLine, Col: startCol})
			i++
			col++
		case '=':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenEqual, Lexeme: "==", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenAssign, Lexeme: "=", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '!':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenNotEqual, Lexeme: "!=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenBang, Lexeme: "!", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '<':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenLessEqual, Lexeme: "<=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenLess, Lexeme: "<", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '>':
			if i+1 < len(src) && src[i+1] == '=' {
				tokens = append(tokens, Token{Kind: TokenGreaterEqual, Lexeme: ">=", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				tokens = append(tokens, Token{Kind: TokenGreater, Lexeme: ">", Line: startLine, Col: startCol})
				i++
				col++
			}
		case '&':
			if i+1 < len(src) && src[i+1] == '&' {
				tokens = append(tokens, Token{Kind: TokenAndAnd, Lexeme: "&&", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				return nil, fmt.Errorf("line %d col %d: unexpected character %q", line, col, ch)
			}
		case '|':
			if i+1 < len(src) && src[i+1] == '|' {
				tokens = append(tokens, Token{Kind: TokenOrOr, Lexeme: "||", Line: startLine, Col: startCol})
				i += 2
				col += 2
			} else {
				return nil, fmt.Errorf("line %d col %d: unexpected character %q", line, col, ch)
			}
		case '.':
			tokens = append(tokens, Token{Kind: TokenDot, Lexeme: ".", Line: startLine, Col: startCol})
			i++
			col++
		case '(':
			tokens = append(tokens, Token{Kind: TokenLParen, Lexeme: "(", Line: startLine, Col: startCol})
			i++
			col++
		case ')':
			tokens = append(tokens, Token{Kind: TokenRParen, Lexeme: ")", Line: startLine, Col: startCol})
			i++
			col++
		case '{':
			tokens = append(tokens, Token{Kind: TokenLBrace, Lexeme: "{", Line: startLine, Col: startCol})
			i++
			col++
		case '}':
			tokens = append(tokens, Token{Kind: TokenRBrace, Lexeme: "}", Line: startLine, Col: startCol})
			i++
			col++
		case '[':
			tokens = append(tokens, Token{Kind: TokenLBracket, Lexeme: "[", Line: startLine, Col: startCol})
			i++
			col++
		case ']':
			tokens = append(tokens, Token{Kind: TokenRBracket, Lexeme: "]", Line: startLine, Col: startCol})
			i++
			col++
		case ',':
			tokens = append(tokens, Token{Kind: TokenComma, Lexeme: ",", Line: startLine, Col: startCol})
			i++
			col++
		case ';':
			tokens = append(tokens, Token{Kind: TokenSemicolon, Lexeme: ";", Line: startLine, Col: startCol})
			i++
			col++
		case ':':
			tokens = append(tokens, Token{Kind: TokenColon, Lexeme: ":", Line: startLine, Col: startCol})
			i++
			col++
		default:
			return nil, fmt.Errorf("line %d col %d: unexpected character %q", line, col, ch)
		}
	}

tokens = append(tokens, Token{Kind: TokenEOF, Lexeme: "", Line: line, Col: col})
	return tokens, nil
}

func readString(src string, start int, line int, col int) (string, int, int, error) {
	var out []byte
	i := start + 1
	c := col + 1
	for i < len(src) {
		ch := src[i]
		if ch == '"' {
			return string(out), i + 1, c + 1, nil
		}
		if ch == '\n' {
			return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
		}
		if ch == '\\' {
			if i+1 >= len(src) {
				return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
			}
			i++
			c++
			esc := src[i]
			switch esc {
			case '"':
				out = append(out, '"')
			case '\\':
				out = append(out, '\\')
			case 'n':
				out = append(out, '\n')
			case 't':
				out = append(out, '\t')
			default:
				return "", 0, 0, fmt.Errorf("line %d col %d: invalid escape \\%c", line, col, esc)
			}
			i++
			c++
			continue
		}
		out = append(out, ch)
		i++
		c++
	}
	return "", 0, 0, fmt.Errorf("line %d col %d: unterminated string", line, col)
}

func isAlpha(ch byte) bool {
	return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
}

func isDigit(ch byte) bool {
	return ch >= '0' && ch <= '9'
}

func isAlphaNum(ch byte) bool {
	return isAlpha(ch) || isDigit(ch)
}

func identKind(lex string) TokenKind {
	switch lex {
	case "let":
		return TokenLet
	case "var":
		return TokenVar
	case "const":
		return TokenConst
	case "fn":
		return TokenFn
	case "if":
		return TokenIf
	case "else":
		return TokenElse
	case "while":
		return TokenWhile
	case "for":
		return TokenFor
	case "return":
		return TokenReturn
	case "break":
		return TokenBreak
	case "continue":
		return TokenContinue
	case "module":
		return TokenModule
	case "import":
		return TokenImport
	case "export":
		return TokenExport
	case "as":
		return TokenAs
	case "true":
		return TokenTrue
	case "false":
		return TokenFalse
	case "nil":
		return TokenNil
	default:
		return TokenIdent
	}
}

// Parse turns tokens into a program AST.
func Parse(tokens []Token) (*Program, error) {
	p := &parser{tokens: tokens}
	if p.peek().Kind == TokenModule {
		var modules []*Module
		for p.peek().Kind != TokenEOF {
			mod, err := p.parseModule()
			if err != nil {
				return nil, err
			}
			modules = append(modules, mod)
		}
		return &Program{Modules: modules}, nil
	}

var stmts []*Stmt
	for p.peek().Kind != TokenEOF {
		stmt, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		stmts = append(stmts, stmt)
	}
	return &Program{Modules: []*Module{{Name: "main", Stmts: stmts}}}, nil
}

type parser struct {
	tokens []Token
	pos    int
}

func (p *parser) parseModule() (*Module, error) {
	if !p.match(TokenModule) {
		return nil, fmt.Errorf("expected module")
	}
	nameTok := p.consume(TokenIdent, "expected module name")
	if nameTok == nil {
		return nil, fmt.Errorf("expected module name")
	}
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{' after module name")
	}
	var imports []Import
	var stmts []*Stmt
	for p.peek().Kind != TokenRBrace && p.peek().Kind != TokenEOF {
		switch p.peek().Kind {
		case TokenImport:
			imp, err := p.parseImport()
			if err != nil {
				return nil, err
			}
			imports = append(imports, imp)
		case TokenExport:
			stmt, err := p.parseExport()
			if err != nil {
				return nil, err
			}
			stmts = append(stmts, stmt)
		default:
			stmt, err := p.parseStmt()
			if err != nil {
				return nil, err
			}
			stmts = append(stmts, stmt)
		}
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}' after module body")
	}
	return &Module{Name: nameTok.Lexeme, Imports: imports, Stmts: stmts}, nil
}

func (p *parser) parseImport() (Import, error) {
	p.advance()
	nameTok := p.consume(TokenIdent, "expected module name")
	if nameTok == nil {
		return Import{}, fmt.Errorf("expected module name")
	}
	alias := nameTok.Lexeme
	if p.match(TokenAs) {
		aliasTok := p.consume(TokenIdent, "expected alias name")
		if aliasTok == nil {
			return Import{}, fmt.Errorf("expected alias name")
		}
		alias = aliasTok.Lexeme
	}
	if !p.match(TokenSemicolon) {
		return Import{}, fmt.Errorf("expected ';' after import")
	}
	return Import{Name: nameTok.Lexeme, Alias: alias}, nil
}

func (p *parser) parseExport() (*Stmt, error) {
	p.advance()
	switch p.peek().Kind {
	case TokenFn:
		stmt, err := p.parseFnDecl()
		if err != nil {
			return nil, err
		}
		stmt.Exported = true
		return stmt, nil
	case TokenLet, TokenVar, TokenConst:
		stmt, err := p.parseVarDecl()
		if err != nil {
			return nil, err
		}
		stmt.Exported = true
		return stmt, nil
	default:
		return nil, fmt.Errorf("expected declaration after export")
	}
}

func (p *parser) parseStmt() (*Stmt, error) {
	switch p.peek().Kind {
	case TokenLet, TokenVar, TokenConst:
		return p.parseVarDecl()
	case TokenIf:
		return p.parseIf()
	case TokenWhile:
		return p.parseWhile()
	case TokenFor:
		return p.parseFor()
	case TokenBreak:
		return p.parseBreak()
	case TokenContinue:
		return p.parseContinue()
	case TokenReturn:
		return p.parseReturn()
	case TokenLBrace:
		body, err := p.parseBlock()
		if err != nil {
			return nil, err
		}
		return &Stmt{Kind: StmtBlock, Body: body}, nil
	case TokenFn:
		return p.parseFnDecl()
	default:
		return p.parseAssignOrExpr()
	}
}

func (p *parser) parseFnDecl() (*Stmt, error) {
	if !p.match(TokenFn) {
		return nil, fmt.Errorf("expected fn")
	}
	nameTok := p.consume(TokenIdent, "expected function name")
	if nameTok == nil {
		return nil, fmt.Errorf("expected function name")
	}
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after function name")
	}
	params, err := p.parseParams()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after parameters")
	}
	body, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	return &Stmt{Kind: StmtFn, Name: nameTok.Lexeme, Params: params, Body: body}, nil
}

func (p *parser) parseParams() ([]string, error) {
	if p.peek().Kind == TokenRParen {
		return nil, nil
	}
	var params []string
	for {
		nameTok := p.consume(TokenIdent, "expected parameter name")
		if nameTok == nil {
			return nil, fmt.Errorf("expected parameter name")
		}
		params = append(params, nameTok.Lexeme)
		if !p.match(TokenComma) {
			break
		}
	}
	return params, nil
}

func (p *parser) parseVarDecl() (*Stmt, error) {
	kindTok := p.advance()
	var kind VarKind
	switch kindTok.Kind {
	case TokenLet:
		kind = VarLet
	case TokenVar:
		kind = VarVar
	case TokenConst:
		kind = VarConst
	default:
		return nil, fmt.Errorf("expected variable declaration")
	}
	nameTok := p.consume(TokenIdent, "expected variable name")
	if nameTok == nil {
		return nil, fmt.Errorf("expected variable name")
	}
	var init *Expr
	if p.match(TokenAssign) {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		init = expr
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after variable declaration")
	}
	return &Stmt{Kind: StmtVar, VarKind: kind, Name: nameTok.Lexeme, Expr: init}, nil
}

func (p *parser) parseVarDeclNoSemi() (*Stmt, error) {
	kindTok := p.advance()
	var kind VarKind
	switch kindTok.Kind {
	case TokenLet:
		kind = VarLet
	case TokenVar:
		kind = VarVar
	case TokenConst:
		kind = VarConst
	default:
		return nil, fmt.Errorf("expected variable declaration")
	}
	nameTok := p.consume(TokenIdent, "expected variable name")
	if nameTok == nil {
		return nil, fmt.Errorf("expected variable name")
	}
	var init *Expr
	if p.match(TokenAssign) {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		init = expr
	}
	return &Stmt{Kind: StmtVar, VarKind: kind, Name: nameTok.Lexeme, Expr: init}, nil
}

func (p *parser) parseAssignOrExpr() (*Stmt, error) {
	left, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if p.match(TokenAssign) {
		if !isLValue(left) {
			return nil, fmt.Errorf("invalid assignment target")
		}
		right, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenSemicolon) {
			return nil, fmt.Errorf("expected ';' after assignment")
		}
		return &Stmt{Kind: StmtAssign, Target: left, Expr: right}, nil
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after expression")
	}
	return &Stmt{Kind: StmtExpr, Expr: left}, nil
}

func (p *parser) parseAssignOrExprNoSemi() (*Stmt, error) {
	left, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if p.match(TokenAssign) {
		if !isLValue(left) {
			return nil, fmt.Errorf("invalid assignment target")
		}
		right, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		return &Stmt{Kind: StmtAssign, Target: left, Expr: right}, nil
	}
	return &Stmt{Kind: StmtExpr, Expr: left}, nil
}

func (p *parser) parseIf() (*Stmt, error) {
	p.advance()
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after if")
	}
	cond, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after if condition")
	}
	thenBody, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	var elseBody []*Stmt
	if p.match(TokenElse) {
		elseBody, err = p.parseBlock()
		if err != nil {
			return nil, err
		}
	}
	return &Stmt{Kind: StmtIf, Expr: cond, Body: thenBody, Else: elseBody}, nil
}

func (p *parser) parseWhile() (*Stmt, error) {
	p.advance()
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after while")
	}
	cond, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after while condition")
	}
	body, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	return &Stmt{Kind: StmtWhile, Expr: cond, Body: body}, nil
}

func (p *parser) parseFor() (*Stmt, error) {
	p.advance()
	if !p.match(TokenLParen) {
		return nil, fmt.Errorf("expected '(' after for")
	}
	var init *Stmt
	if p.peek().Kind != TokenSemicolon {
		var err error
		if p.peek().Kind == TokenLet || p.peek().Kind == TokenVar || p.peek().Kind == TokenConst {
			init, err = p.parseVarDeclNoSemi()
		} else {
			init, err = p.parseAssignOrExprNoSemi()
		}
		if err != nil {
			return nil, err
		}
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after for init")
	}
	var cond *Expr
	if p.peek().Kind != TokenSemicolon {
		var err error
		cond, err = p.parseExpr()
		if err != nil {
			return nil, err
		}
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after for condition")
	}
	var post *Stmt
	if p.peek().Kind != TokenRParen {
		var err error
		post, err = p.parseAssignOrExprNoSemi()
		if err != nil {
			return nil, err
		}
	}
	if !p.match(TokenRParen) {
		return nil, fmt.Errorf("expected ')' after for clauses")
	}
	body, err := p.parseBlock()
	if err != nil {
		return nil, err
	}
	return &Stmt{Kind: StmtFor, Init: init, Cond: cond, Post: post, Body: body}, nil
}

func (p *parser) parseBreak() (*Stmt, error) {
	p.advance()
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after break")
	}
	return &Stmt{Kind: StmtBreak}, nil
}

func (p *parser) parseContinue() (*Stmt, error) {
	p.advance()
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after continue")
	}
	return &Stmt{Kind: StmtContinue}, nil
}

func (p *parser) parseReturn() (*Stmt, error) {
	p.advance()
	if p.match(TokenSemicolon) {
		return &Stmt{Kind: StmtReturn}, nil
	}
	expr, err := p.parseExpr()
	if err != nil {
		return nil, err
	}
	if !p.match(TokenSemicolon) {
		return nil, fmt.Errorf("expected ';' after return")
	}
	return &Stmt{Kind: StmtReturn, Expr: expr}, nil
}

func (p *parser) parseBlock() ([]*Stmt, error) {
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{'")
	}
	var body []*Stmt
	for p.peek().Kind != TokenRBrace && p.peek().Kind != TokenEOF {
		stmt, err := p.parseStmt()
		if err != nil {
			return nil, err
		}
		body = append(body, stmt)
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}'")
	}
	return body, nil
}

func (p *parser) parseExpr() (*Expr, error) {
	return p.parseOr()
}

func (p *parser) parseOr() (*Expr, error) {
	expr, err := p.parseAnd()
	if err != nil {
		return nil, err
	}
	for p.match(TokenOrOr) {
		right, err := p.parseAnd()
		if err != nil {
			return nil, err
		}
		expr = &Expr{Kind: ExprBinary, Value: "||", Left: expr, Right: right}
	}
	return expr, nil
}

func (p *parser) parseAnd() (*Expr, error) {
	expr, err := p.parseEquality()
	if err != nil {
		return nil, err
	}
	for p.match(TokenAndAnd) {
		right, err := p.parseEquality()
		if err != nil {
			return nil, err
		}
		expr = &Expr{Kind: ExprBinary, Value: "&&", Left: expr, Right: right}
	}
	return expr, nil
}

func (p *parser) parseEquality() (*Expr, error) {
	expr, err := p.parseComparison()
	if err != nil {
		return nil, err
	}
	for {
		if p.match(TokenEqual) {
			right, err := p.parseComparison()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "==", Left: expr, Right: right}
			continue
		}
		if p.match(TokenNotEqual) {
			right, err := p.parseComparison()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "!=", Left: expr, Right: right}
			continue
		}
		break
	}
	return expr, nil
}

func (p *parser) parseComparison() (*Expr, error) {
	expr, err := p.parseTerm()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenLess:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "<", Left: expr, Right: right}
		case TokenLessEqual:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "<=", Left: expr, Right: right}
		case TokenGreater:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: ">", Left: expr, Right: right}
		case TokenGreaterEqual:
			p.advance()
			right, err := p.parseTerm()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: ">=", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

func (p *parser) parseTerm() (*Expr, error) {
	expr, err := p.parseFactor()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenPlus:
			p.advance()
			right, err := p.parseFactor()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "+", Left: expr, Right: right}
		case TokenMinus:
			p.advance()
			right, err := p.parseFactor()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "-", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

func (p *parser) parseFactor() (*Expr, error) {
	expr, err := p.parseUnary()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek().Kind {
		case TokenStar:
			p.advance()
			right, err := p.parseUnary()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "*", Left: expr, Right: right}
		case TokenSlash:
			p.advance()
			right, err := p.parseUnary()
			if err != nil {
				return nil, err
			}
			expr = &Expr{Kind: ExprBinary, Value: "/", Left: expr, Right: right}
		default:
			return expr, nil
		}
	}
}

func (p *parser) parseUnary() (*Expr, error) {
	if p.match(TokenBang) {
		right, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &Expr{Kind: ExprUnary, Value: "!", Left: right}, nil
	}
	if p.match(TokenMinus) {
		right, err := p.parseUnary()
		if err != nil {
			return nil, err
		}
		return &Expr{Kind: ExprUnary, Value: "-", Left: right}, nil
	}
	return p.parsePostfix()
}

func (p *parser) parsePostfix() (*Expr, error) {
	expr, err := p.parsePrimary()
	if err != nil {
		return nil, err
	}
	for {
		if p.match(TokenLParen) {
			args, err := p.parseArgs()
			if err != nil {
				return nil, err
			}
			if !p.match(TokenRParen) {
				return nil, fmt.Errorf("expected ')' after arguments")
			}
			expr = &Expr{Kind: ExprCall, Left: expr, Args: args}
			continue
		}
		if p.match(TokenLBracket) {
			idx, err := p.parseExpr()
			if err != nil {
				return nil, err
			}
			if !p.match(TokenRBracket) {
				return nil, fmt.Errorf("expected ']' after index")
			}
			expr = &Expr{Kind: ExprIndex, Left: expr, Right: idx}
			continue
		}
		if p.match(TokenDot) {
			nameTok := p.consume(TokenIdent, "expected member name")
			if nameTok == nil {
				return nil, fmt.Errorf("expected member name")
			}
			expr = &Expr{Kind: ExprMember, Left: expr, Value: nameTok.Lexeme}
			continue
		}
		break
	}
	return expr, nil
}

func (p *parser) parseArgs() ([]*Expr, error) {
	if p.peek().Kind == TokenRParen {
		return nil, nil
	}
	var args []*Expr
	for {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		args = append(args, expr)
		if !p.match(TokenComma) {
			break
		}
	}
	return args, nil
}

func (p *parser) parsePrimary() (*Expr, error) {
	switch p.peek().Kind {
	case TokenNumber:
		return &Expr{Kind: ExprNumber, Value: p.advance().Lexeme}, nil
	case TokenString:
		return &Expr{Kind: ExprString, Value: p.advance().Lexeme}, nil
	case TokenTrue:
		p.advance()
		return &Expr{Kind: ExprBool, Value: "true"}, nil
	case TokenFalse:
		p.advance()
		return &Expr{Kind: ExprBool, Value: "false"}, nil
	case TokenNil:
		p.advance()
		return &Expr{Kind: ExprNil}, nil
	case TokenIdent:
		return &Expr{Kind: ExprIdent, Value: p.advance().Lexeme}, nil
	case TokenLParen:
		p.advance()
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenRParen) {
			return nil, fmt.Errorf("expected ')' after expression")
		}
		return expr, nil
	case TokenLBracket:
		return p.parseArray()
	case TokenLBrace:
		return p.parseMap()
	default:
		return nil, fmt.Errorf("unexpected token: %v", p.peek().Kind)
	}
}

func (p *parser) parseArray() (*Expr, error) {
	if !p.match(TokenLBracket) {
		return nil, fmt.Errorf("expected '['")
	}
	if p.match(TokenRBracket) {
		return &Expr{Kind: ExprArray}, nil
	}
	var elems []*Expr
	for {
		expr, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		elems = append(elems, expr)
		if !p.match(TokenComma) {
			break
		}
	}
	if !p.match(TokenRBracket) {
		return nil, fmt.Errorf("expected ']' after array")
	}
	return &Expr{Kind: ExprArray, Elems: elems}, nil
}

func (p *parser) parseMap() (*Expr, error) {
	if !p.match(TokenLBrace) {
		return nil, fmt.Errorf("expected '{'")
	}
	if p.match(TokenRBrace) {
		return &Expr{Kind: ExprMap}, nil
	}
	var pairs []MapPair
	for {
		key, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		if !p.match(TokenColon) {
			return nil, fmt.Errorf("expected ':' after map key")
		}
		value, err := p.parseExpr()
		if err != nil {
			return nil, err
		}
		pairs = append(pairs, MapPair{Key: key, Value: value})
		if !p.match(TokenComma) {
			break
		}
	}
	if !p.match(TokenRBrace) {
		return nil, fmt.Errorf("expected '}' after map")
	}
	return &Expr{Kind: ExprMap, Pairs: pairs}, nil
}

func isLValue(expr *Expr) bool {
	if expr == nil {
		return false
	}
	switch expr.Kind {
	case ExprIdent, ExprIndex:
		return true
	default:
		return false
	}
}

func (p *parser) peek() Token {
	if p.pos >= len(p.tokens) {
		return Token{Kind: TokenEOF}
	}
	return p.tokens[p.pos]
}

func (p *parser) advance() Token {
	if p.pos < len(p.tokens) {
		p.pos++
		return p.tokens[p.pos-1]
	}
	return Token{Kind: TokenEOF}
}

func (p *parser) match(kind TokenKind) bool {
	if p.peek().Kind == kind {
		p.pos++
		return true
	}
	return false
}

func (p *parser) consume(kind TokenKind, msg string) *Token {
	if p.peek().Kind == kind {
		tok := p.advance()
		return &tok
	}
	return nil
}

type symbolKind int

const (
	symVar symbolKind = iota
	symConst
	symFunc
	symModule
)

type symbol struct {
	kind  symbolKind
	arity int
}

type moduleInfo struct {
	name    string
	exports map[string]struct{}
	aliases map[string]string
}

// Analyze checks semantic rules and returns error messages.
func Analyze(prog *Program) []string {
	if prog == nil || len(prog.Modules) == 0 {
		return nil
	}

a := &analyzer{modules: map[string]*moduleInfo{}}
	index := map[string]int{}
	for i, mod := range prog.Modules {
		if _, ok := index[mod.Name]; ok {
			a.errors = append(a.errors, "duplicate module: "+mod.Name)
			continue
		}
		index[mod.Name] = i
		info := &moduleInfo{name: mod.Name, exports: map[string]struct{}{}, aliases: map[string]string{}}
		a.modules[mod.Name] = info
		for _, stmt := range mod.Stmts {
			if stmt == nil || !stmt.Exported {
				continue
			}
			if stmt.Kind != StmtVar && stmt.Kind != StmtFn {
				continue
			}
			if _, ok := info.exports[stmt.Name]; ok {
				continue
			}
			info.exports[stmt.Name] = struct{}{}
		}
	}

mainIndex, ok := index["main"]
	if !ok || mainIndex != len(prog.Modules)-1 {
		a.errors = append(a.errors, "main module must be last")
	}

for i, mod := range prog.Modules {
		info := a.modules[mod.Name]
		if info == nil {
			continue
		}
		a.scopes = []map[string]symbol{{}}
		a.inFunction = 0
		a.loopDepth = 0
		a.current = info

for _, imp := range mod.Imports {
			alias := imp.Alias
			if alias == "" {
				alias = imp.Name
			}
			targetIndex, ok := index[imp.Name]
			if !ok {
				a.errors = append(a.errors, "unknown module: "+imp.Name)
				continue
			}
			if targetIndex >= i {
				a.errors = append(a.errors, "import of future module: "+imp.Name)
				continue
			}
			if a.inCurrentScope(alias) {
				a.errors = append(a.errors, "redeclare in same scope: "+alias)
				continue
			}
			a.scopes[len(a.scopes)-1][alias] = symbol{kind: symModule}
			info.aliases[alias] = imp.Name
		}

for _, stmt := range mod.Stmts {
			a.analyzeStmt(stmt)
		}
	}
	return a.errors
}

type analyzer struct {
	modules    map[string]*moduleInfo
	current    *moduleInfo
	scopes     []map[string]symbol
	inFunction int
	loopDepth  int
	errors     []string
}

func (a *analyzer) analyzeStmt(stmt *Stmt) {
	if stmt == nil {
		return
	}
	switch stmt.Kind {
	case StmtVar:
		a.analyzeVarDecl(stmt)
	case StmtAssign:
		a.analyzeAssign(stmt)
	case StmtExpr:
		a.analyzeExpr(stmt.Expr)
	case StmtIf:
		a.analyzeExpr(stmt.Expr)
		a.analyzeBlock(stmt.Body)
		if len(stmt.Else) > 0 {
			a.analyzeBlock(stmt.Else)
		}
	case StmtWhile:
		a.analyzeExpr(stmt.Expr)
		a.loopDepth++
		a.analyzeBlock(stmt.Body)
		a.loopDepth--
	case StmtFor:
		a.analyzeFor(stmt)
	case StmtBreak:
		if a.loopDepth == 0 {
			a.errors = append(a.errors, "break outside loop")
		}
	case StmtContinue:
		if a.loopDepth == 0 {
			a.errors = append(a.errors, "continue outside loop")
		}
	case StmtReturn:
		if a.inFunction == 0 {
			a.errors = append(a.errors, "return outside function")
		}
		a.analyzeExpr(stmt.Expr)
	case StmtBlock:
		a.analyzeBlock(stmt.Body)
	case StmtFn:
		a.analyzeFn(stmt)
	}
}

func (a *analyzer) analyzeFor(stmt *Stmt) {
	a.pushScope()
	if stmt.Init != nil {
		a.analyzeStmt(stmt.Init)
	}
	a.analyzeExpr(stmt.Cond)
	if stmt.Post != nil {
		a.analyzeStmt(stmt.Post)
	}
	a.loopDepth++
	// The body is a block nested inside the initializer scope.
	a.analyzeBlock(stmt.Body)
	a.loopDepth--
	a.popScope()
}

func (a *analyzer) analyzeVarDecl(stmt *Stmt) {
	name := stmt.Name
	if a.inCurrentScope(name) {
		a.errors = append(a.errors, "redeclare in same scope: "+name)
		return
	}
	if stmt.VarKind == VarConst && stmt.Expr == nil {
		a.errors = append(a.errors, "const requires initializer: "+name)
	}
	a.analyzeExpr(stmt.Expr)

kind := symVar
	if stmt.VarKind == VarConst {
		kind = symConst
	}
	a.scopes[len(a.scopes)-1][name] = symbol{kind: kind}
}

func (a *analyzer) analyzeAssign(stmt *Stmt) {
	if stmt.Target == nil {
		return
	}
	if stmt.Target.Kind == ExprIdent {
		name := stmt.Target.Value
		sym, ok := a.resolve(name)
		if !ok {
			a.errors = append(a.errors, "undefined name: "+name)
		} else if sym.kind != symVar {
			a.errors = append(a.errors, "cannot assign to const: "+name)
		}
	} else {
		a.analyzeExpr(stmt.Target)
	}
	a.analyzeExpr(stmt.Expr)
}

func (a *analyzer) analyzeFn(stmt *Stmt) {
	name := stmt.Name
	if a.inCurrentScope(name) {
		a.errors = append(a.errors, "redeclare in same scope: "+name)
		return
	}
	a.scopes[len(a.scopes)-1][name] = symbol{kind: symFunc, arity: len(stmt.Params)}

a.pushScope()
	for _, param := range stmt.Params {
		if a.inCurrentScope(param) {
			a.errors = append(a.errors, "redeclare in same scope: "+param)
			continue
		}
		a.scopes[len(a.scopes)-1][param] = symbol{kind: symVar}
	}
	// A function cannot break or continue a loop in its defining function.
	previousLoopDepth := a.loopDepth
	a.loopDepth = 0
	a.inFunction++
	for _, s := range stmt.Body {
		a.analyzeStmt(s)
	}
	a.inFunction--
	a.loopDepth = previousLoopDepth
	a.popScope()
}

func (a *analyzer) analyzeBlock(stmts []*Stmt) {
	a.pushScope()
	for _, s := range stmts {
		a.analyzeStmt(s)
	}
	a.popScope()
}

func (a *analyzer) analyzeExpr(expr *Expr) {
	if expr == nil {
		return
	}
	switch expr.Kind {
	case ExprIdent:
		if _, ok := a.resolve(expr.Value); !ok {
			a.errors = append(a.errors, "undefined name: "+expr.Value)
		}
	case ExprMember:
		if expr.Left == nil || expr.Left.Kind != ExprIdent {
			a.errors = append(a.errors, "invalid module access")
			return
		}
		modAlias := expr.Left.Value
		modName, ok := a.current.aliases[modAlias]
		if !ok {
			a.errors = append(a.errors, "unknown module: "+modAlias)
			return
		}
		modInfo := a.modules[modName]
		if modInfo == nil {
			a.errors = append(a.errors, "unknown module: "+modName)
			return
		}
		if _, ok := modInfo.exports[expr.Value]; !ok {
			a.errors = append(a.errors, "unknown export: "+modName+"."+expr.Value)
		}
	case ExprCall:
		if expr.Left != nil && expr.Left.Kind == ExprIdent {
			sym, ok := a.resolve(expr.Left.Value)
			if !ok {
				a.errors = append(a.errors, "undefined name: "+expr.Left.Value)
			} else if sym.kind == symFunc && sym.arity != len(expr.Args) {
				a.errors = append(a.errors, "arity mismatch: "+expr.Left.Value+" expects "+itoa(sym.arity))
			}
		} else {
			a.analyzeExpr(expr.Left)
		}
		for _, arg := range expr.Args {
			a.analyzeExpr(arg)
		}
	case ExprUnary:
		a.analyzeExpr(expr.Left)
	case ExprBinary:
		a.analyzeExpr(expr.Left)
		a.analyzeExpr(expr.Right)
	case ExprArray:
		for _, elem := range expr.Elems {
			a.analyzeExpr(elem)
		}
	case ExprMap:
		for _, pair := range expr.Pairs {
			a.analyzeExpr(pair.Key)
			a.analyzeExpr(pair.Value)
		}
	case ExprIndex:
		a.analyzeExpr(expr.Left)
		a.analyzeExpr(expr.Right)
	default:
		for _, arg := range expr.Args {
			a.analyzeExpr(arg)
		}
	}
}

func (a *analyzer) resolve(name string) (symbol, bool) {
	for i := len(a.scopes) - 1; i >= 0; i-- {
		if sym, ok := a.scopes[i][name]; ok {
			return sym, true
		}
	}
	return symbol{}, false
}

func (a *analyzer) inCurrentScope(name string) bool {
	_, ok := a.scopes[len(a.scopes)-1][name]
	return ok
}

func (a *analyzer) pushScope() {
	a.scopes = append(a.scopes, map[string]symbol{})
}

func (a *analyzer) popScope() {
	if len(a.scopes) > 1 {
		a.scopes = a.scopes[:len(a.scopes)-1]
	}
}

func itoa(n int) string {
	if n == 0 {
		return "0"
	}
	var out [20]byte
	i := len(out)
	for n > 0 {
		i--
		out[i] = byte('0' + n%10)
		n /= 10
	}
	return string(out[i:])
}

type funcState struct {
	functions []Function
	nextID    int
}

type loopContext struct {
	breaks    []int
	continues []int
	depth     int
}

type ModuleBytecode struct {
	Name     string
	Imports  []Import
	Exports  []string
	Bytecode Bytecode
}

// CompileModules lowers a program AST into module bytecode.
func CompileModules(prog *Program) []ModuleBytecode {
	if prog == nil {
		return nil
	}
	var out []ModuleBytecode
	for _, mod := range prog.Modules {
		state := &funcState{}
		c := &compiler{funcs: state}
		c.emit(Instr{Op: OpEnterScope})
		for _, imp := range mod.Imports {
			alias := imp.Alias
			if alias == "" {
				alias = imp.Name
			}
			c.emit(Instr{Op: OpLoad, Str: imp.Name})
			c.emit(Instr{Op: OpDefineConst, Str: alias})
		}
		var exports []string
		for _, stmt := range mod.Stmts {
			if stmt != nil && stmt.Exported {
				exports = append(exports, stmt.Name)
			}
			c.compileStmt(stmt)
		}
		for _, name := range exports {
			c.emit(Instr{Op: OpPushStr, Str: name})
			c.emit(Instr{Op: OpLoad, Str: name})
		}
		c.emit(Instr{Op: OpMakeMap, Int: len(exports)})
		c.emit(Instr{Op: OpExitScope})
		c.emit(Instr{Op: OpDefineConst, Str: mod.Name})
		out = append(out, ModuleBytecode{
			Name:     mod.Name,
			Imports:  append([]Import(nil), mod.Imports...),
			Exports:  append([]string(nil), exports...),
			Bytecode: Bytecode{Functions: state.functions, Main: c.code},
		})
	}
	return out
}

type compiler struct {
	code       []Instr
	funcs      *funcState
	loops      []loopContext
	scopeDepth int
}

func (c *compiler) compileFunction(stmt *Stmt) int {
	id := c.funcs.nextID
	c.funcs.nextID++
	fc := &compiler{funcs: c.funcs}
	for _, s := range stmt.Body {
		fc.compileStmt(s)
	}
	fc.ensureReturn()
	c.funcs.functions = append(c.funcs.functions, Function{ID: id, Name: stmt.Name, Params: stmt.Params, Code: fc.code})
	return id
}

func (c *compiler) ensureReturn() {
	if len(c.code) == 0 || c.code[len(c.code)-1].Op != OpReturn {
		c.emit(Instr{Op: OpPushNil})
		c.emit(Instr{Op: OpReturn})
	}
}

func (c *compiler) compileStmt(stmt *Stmt) {
	switch stmt.Kind {
	case StmtVar:
		if stmt.Expr != nil {
			c.compileExpr(stmt.Expr)
		} else {
			c.emit(Instr{Op: OpPushNil})
		}
		if stmt.VarKind == VarConst {
			c.emit(Instr{Op: OpDefineConst, Str: stmt.Name})
		} else {
			c.emit(Instr{Op: OpDefineVar, Str: stmt.Name})
		}
	case StmtAssign:
		if stmt.Target != nil && stmt.Target.Kind == ExprIdent {
			c.compileExpr(stmt.Expr)
			c.emit(Instr{Op: OpStore, Str: stmt.Target.Value})
			return
		}
		if stmt.Target != nil && stmt.Target.Kind == ExprIndex {
			c.compileExpr(stmt.Target.Left)
			c.compileExpr(stmt.Target.Right)
			c.compileExpr(stmt.Expr)
			c.emit(Instr{Op: OpSetIndex})
			return
		}
	case StmtExpr:
		c.compileExpr(stmt.Expr)
		c.emit(Instr{Op: OpPop})
	case StmtIf:
		c.compileExpr(stmt.Expr)
		jumpIf := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
		c.compileBlock(stmt.Body)
		jumpEnd := c.emit(Instr{Op: OpJump, Int: -1})
		c.patch(jumpIf, len(c.code))
		if len(stmt.Else) > 0 {
			c.compileBlock(stmt.Else)
		}
		c.patch(jumpEnd, len(c.code))
	case StmtWhile:
		c.compileWhile(stmt)
	case StmtFor:
		c.compileFor(stmt)
	case StmtBreak:
		c.emitLoopJump(true)
	case StmtContinue:
		c.emitLoopJump(false)
	case StmtReturn:
		if stmt.Expr != nil {
			c.compileExpr(stmt.Expr)
		} else {
			c.emit(Instr{Op: OpPushNil})
		}
		c.emit(Instr{Op: OpReturn})
	case StmtBlock:
		c.compileBlock(stmt.Body)
	case StmtFn:
		id := c.compileFunction(stmt)
		c.emit(Instr{Op: OpMakeClosure, Int: id})
		c.emit(Instr{Op: OpDefineConst, Str: stmt.Name})
	}
}

func (c *compiler) compileWhile(stmt *Stmt) {
	loopDepth := c.scopeDepth
	start := len(c.code)
	c.compileExpr(stmt.Expr)
	jumpIf := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.pushLoop(loopDepth)
	c.compileBlock(stmt.Body)
	c.emit(Instr{Op: OpJump, Int: start})
	end := len(c.code)
	c.patch(jumpIf, end)
	ctx := c.popLoop()
	c.patchList(ctx.breaks, end)
	c.patchList(ctx.continues, start)
}

func (c *compiler) compileFor(stmt *Stmt) {
	c.enterScope()
	if stmt.Init != nil {
		c.compileStmt(stmt.Init)
	}
	loopDepth := c.scopeDepth
	start := len(c.code)
	if stmt.Cond != nil {
		c.compileExpr(stmt.Cond)
	} else {
		c.emit(Instr{Op: OpPushBool, Int: 1})
	}
	jumpIf := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.pushLoop(loopDepth)
	c.compileBlock(stmt.Body)
	postStart := len(c.code)
	if stmt.Post != nil {
		c.compileStmt(stmt.Post)
	}
	c.emit(Instr{Op: OpJump, Int: start})
	end := len(c.code)
	c.patch(jumpIf, end)
	ctx := c.popLoop()
	c.patchList(ctx.breaks, end)
	continueTarget := start
	if stmt.Post != nil {
		continueTarget = postStart
	}
	c.patchList(ctx.continues, continueTarget)
	c.exitScope()
}

func (c *compiler) emitLoopJump(isBreak bool) {
	if len(c.loops) == 0 {
		return
	}
	ctx := &c.loops[len(c.loops)-1]
	c.emitScopeExits(c.scopeDepth - ctx.depth)
	pos := c.emit(Instr{Op: OpJump, Int: -1})
	if isBreak {
		ctx.breaks = append(ctx.breaks, pos)
	} else {
		ctx.continues = append(ctx.continues, pos)
	}
}

func (c *compiler) compileBlock(stmts []*Stmt) {
	c.enterScope()
	for _, s := range stmts {
		c.compileStmt(s)
	}
	c.exitScope()
}

func (c *compiler) compileExpr(expr *Expr) {
	switch expr.Kind {
	case ExprNumber:
		v, _ := strconv.Atoi(expr.Value)
		c.emit(Instr{Op: OpPushNum, Int: v})
	case ExprString:
		c.emit(Instr{Op: OpPushStr, Str: expr.Value})
	case ExprBool:
		if expr.Value == "true" {
			c.emit(Instr{Op: OpPushBool, Int: 1})
		} else {
			c.emit(Instr{Op: OpPushBool, Int: 0})
		}
	case ExprNil:
		c.emit(Instr{Op: OpPushNil})
	case ExprIdent:
		c.emit(Instr{Op: OpLoad, Str: expr.Value})
	case ExprUnary:
		c.compileExpr(expr.Left)
		switch expr.Value {
		case "-":
			c.emit(Instr{Op: OpNeg})
		case "!":
			c.emit(Instr{Op: OpNot})
		}
	case ExprBinary:
		if expr.Value == "&&" {
			c.compileAnd(expr.Left, expr.Right)
			return
		}
		if expr.Value == "||" {
			c.compileOr(expr.Left, expr.Right)
			return
		}
		c.compileExpr(expr.Left)
		c.compileExpr(expr.Right)
		switch expr.Value {
		case "+":
			c.emit(Instr{Op: OpAdd})
		case "-":
			c.emit(Instr{Op: OpSub})
		case "*":
			c.emit(Instr{Op: OpMul})
		case "/":
			c.emit(Instr{Op: OpDiv})
		case "==":
			c.emit(Instr{Op: OpEq})
		case "!=":
			c.emit(Instr{Op: OpNeq})
		case "<":
			c.emit(Instr{Op: OpLt})
		case "<=":
			c.emit(Instr{Op: OpLte})
		case ">":
			c.emit(Instr{Op: OpGt})
		case ">=":
			c.emit(Instr{Op: OpGte})
		}
	case ExprCall:
		c.compileExpr(expr.Left)
		for _, arg := range expr.Args {
			c.compileExpr(arg)
		}
		c.emit(Instr{Op: OpCall, Int: len(expr.Args)})
	case ExprArray:
		for _, elem := range expr.Elems {
			c.compileExpr(elem)
		}
		c.emit(Instr{Op: OpMakeArray, Int: len(expr.Elems)})
	case ExprMap:
		for _, pair := range expr.Pairs {
			c.compileExpr(pair.Key)
			c.compileExpr(pair.Value)
		}
		c.emit(Instr{Op: OpMakeMap, Int: len(expr.Pairs)})
	case ExprIndex:
		c.compileExpr(expr.Left)
		c.compileExpr(expr.Right)
		c.emit(Instr{Op: OpGetIndex})
	case ExprMember:
		c.compileExpr(expr.Left)
		c.emit(Instr{Op: OpPushStr, Str: expr.Value})
		c.emit(Instr{Op: OpGetIndex})
	}
}

func (c *compiler) compileAnd(left, right *Expr) {
	c.compileExpr(left)
	jumpFalse := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.compileExpr(right)
	jumpFalse2 := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.emit(Instr{Op: OpPushBool, Int: 1})
	jumpEnd := c.emit(Instr{Op: OpJump, Int: -1})
	falseLabel := len(c.code)
	c.emit(Instr{Op: OpPushBool, Int: 0})
	end := len(c.code)
	c.patch(jumpFalse, falseLabel)
	c.patch(jumpFalse2, falseLabel)
	c.patch(jumpEnd, end)
}

func (c *compiler) compileOr(left, right *Expr) {
	c.compileExpr(left)
	jumpCheck := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.emit(Instr{Op: OpPushBool, Int: 1})
	jumpEnd := c.emit(Instr{Op: OpJump, Int: -1})
	checkLabel := len(c.code)
	c.compileExpr(right)
	jumpFalse := c.emit(Instr{Op: OpJumpIfFalse, Int: -1})
	c.emit(Instr{Op: OpPushBool, Int: 1})
	jumpEnd2 := c.emit(Instr{Op: OpJump, Int: -1})
	falseLabel := len(c.code)
	c.emit(Instr{Op: OpPushBool, Int: 0})
	end := len(c.code)
	c.patch(jumpCheck, checkLabel)
	c.patch(jumpFalse, falseLabel)
	c.patch(jumpEnd, end)
	c.patch(jumpEnd2, end)
}

func (c *compiler) pushLoop(depth int) {
	c.loops = append(c.loops, loopContext{depth: depth})
}

func (c *compiler) popLoop() loopContext {
	ctx := c.loops[len(c.loops)-1]
	c.loops = c.loops[:len(c.loops)-1]
	return ctx
}

func (c *compiler) enterScope() {
	c.emit(Instr{Op: OpEnterScope})
	c.scopeDepth++
}

func (c *compiler) exitScope() {
	c.emit(Instr{Op: OpExitScope})
	if c.scopeDepth > 0 {
		c.scopeDepth--
	}
}

func (c *compiler) emitScopeExits(n int) {
	for i := 0; i < n; i++ {
		c.emit(Instr{Op: OpExitScope})
	}
}

func (c *compiler) emit(instr Instr) int {
	c.code = append(c.code, instr)
	return len(c.code) - 1
}

func (c *compiler) patch(pos int, target int) {
	c.code[pos].Int = target
}

func (c *compiler) patchList(list []int, target int) {
	for _, pos := range list {
		c.patch(pos, target)
	}
}

// Link merges module bytecode into a single program.
func Link(mods []ModuleBytecode) (Bytecode, error) {
	if len(mods) == 0 {
		return Bytecode{}, fmt.Errorf("main module must be last")
	}
	index := map[string]int{}
	for i, mod := range mods {
		if _, ok := index[mod.Name]; ok {
			return Bytecode{}, fmt.Errorf("duplicate module: %s", mod.Name)
		}
		index[mod.Name] = i
	}
	mainIndex, ok := index["main"]
	if !ok || mainIndex != len(mods)-1 {
		return Bytecode{}, fmt.Errorf("main module must be last")
	}
	for i, mod := range mods {
		for _, imp := range mod.Imports {
			idx, ok := index[imp.Name]
			if !ok {
				return Bytecode{}, fmt.Errorf("unknown module: %s", imp.Name)
			}
			if idx >= i {
				return Bytecode{}, fmt.Errorf("import of future module: %s", imp.Name)
			}
		}
	}

var out Bytecode
	functionOffset := 0
	for _, mod := range mods {
		mainOffset := len(out.Main)
		for _, original := range mod.Bytecode.Functions {
			function := original
			function.ID += functionOffset
			function.Params = append([]string(nil), original.Params...)
			function.Code = append([]Instr(nil), original.Code...)
			// Function-local instruction indexes stay local to their code slice.
			rebaseInstrs(function.Code, functionOffset)
			out.Functions = append(out.Functions, function)
		}
		mainCode := append([]Instr(nil), mod.Bytecode.Main...)
		rebaseInstrs(mainCode, functionOffset)
		for i := range mainCode {
			if mainCode[i].Op == OpJump || mainCode[i].Op == OpJumpIfFalse {
				mainCode[i].Int += mainOffset
			}
		}
		out.Main = append(out.Main, mainCode...)
		functionOffset += len(mod.Bytecode.Functions)
	}

return out, nil
}

func rebaseInstrs(code []Instr, offset int) {
	if offset == 0 {
		return
	}
	for i := range code {
		if code[i].Op == OpMakeClosure {
			code[i].Int += offset
		}
	}
}

// Encode converts bytecode into a BC2 text format.
func Encode(bc Bytecode) string {
	var b strings.Builder
	writeLine(&b, "BC2")
	for _, fn := range bc.Functions {
		line := "FUNC " + strconv.Itoa(fn.ID) + " " + fn.Name
		for _, p := range fn.Params {
			line += " " + p
		}
		writeLine(&b, line)
		for _, ins := range fn.Code {
			writeLine(&b, encodeInstr(ins))
		}
		writeLine(&b, "END")
	}
	writeLine(&b, "MAIN")
	for _, ins := range bc.Main {
		writeLine(&b, encodeInstr(ins))
	}
	writeLine(&b, "END")
	return b.String()
}

// Decode parses BC2 text into bytecode.
func Decode(src string) (Bytecode, error) {
	scanner := bufio.NewScanner(strings.NewReader(src))
	var lines []string
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if line == "" || strings.HasPrefix(line, "#") {
			continue
		}
		lines = append(lines, line)
	}
	if err := scanner.Err(); err != nil {
		return Bytecode{}, err
	}
	if len(lines) == 0 || lines[0] != "BC2" {
		return Bytecode{}, fmt.Errorf("missing BC2 header")
	}

var bc Bytecode
	i := 1
	for i < len(lines) {
		line := lines[i]
		if line == "MAIN" {
			code, next, err := parseSection(lines, i+1)
			if err != nil {
				return Bytecode{}, err
			}
			bc.Main = code
			i = next
			continue
		}
		toks, err := splitTokens(line)
		if err != nil {
			return Bytecode{}, err
		}
		if len(toks) >= 3 && toks[0] == "FUNC" {
			id, err := strconv.Atoi(toks[1])
			if err != nil {
				return Bytecode{}, err
			}
			fn := Function{ID: id, Name: toks[2], Params: append([]string(nil), toks[3:]...)}
			code, next, err := parseSection(lines, i+1)
			if err != nil {
				return Bytecode{}, err
			}
			fn.Code = code
			bc.Functions = append(bc.Functions, fn)
			i = next
			continue
		}
		return Bytecode{}, fmt.Errorf("unexpected line: %s", line)
	}
	return bc, nil
}

func parseSection(lines []string, start int) ([]Instr, int, error) {
	var code []Instr
	for i := start; i < len(lines); i++ {
		line := lines[i]
		if line == "END" {
			return code, i + 1, nil
		}
		toks, err := splitTokens(line)
		if err != nil {
			return nil, 0, err
		}
		ins, err := parseInstr(toks)
		if err != nil {
			return nil, 0, err
		}
		code = append(code, ins)
	}
	return nil, 0, fmt.Errorf("missing END")
}

func encodeInstr(ins Instr) string {
	switch ins.Op {
	case OpPushNum:
		return "PUSH_NUM " + strconv.Itoa(ins.Int)
	case OpPushStr:
		return "PUSH_STR \"" + escapeString(ins.Str) + "\""
	case OpPushBool:
		return "PUSH_BOOL " + strconv.Itoa(ins.Int)
	case OpPushNil:
		return "PUSH_NIL"
	case OpLoad:
		return "LOAD " + ins.Str
	case OpStore:
		return "STORE " + ins.Str
	case OpDefineVar:
		return "DEFINE_VAR " + ins.Str
	case OpDefineConst:
		return "DEFINE_CONST " + ins.Str
	case OpAdd:
		return "ADD"
	case OpSub:
		return "SUB"
	case OpMul:
		return "MUL"
	case OpDiv:
		return "DIV"
	case OpNeg:
		return "NEG"
	case OpNot:
		return "NOT"
	case OpEq:
		return "EQ"
	case OpNeq:
		return "NEQ"
	case OpLt:
		return "LT"
	case OpLte:
		return "LTE"
	case OpGt:
		return "GT"
	case OpGte:
		return "GTE"
	case OpJump:
		return "JUMP " + strconv.Itoa(ins.Int)
	case OpJumpIfFalse:
		return "JUMP_IF_FALSE " + strconv.Itoa(ins.Int)
	case OpCall:
		return "CALL " + strconv.Itoa(ins.Int)
	case OpReturn:
		return "RETURN"
	case OpEnterScope:
		return "ENTER_SCOPE"
	case OpExitScope:
		return "EXIT_SCOPE"
	case OpPop:
		return "POP"
	case OpMakeClosure:
		return "MAKE_CLOSURE " + strconv.Itoa(ins.Int)
	case OpMakeArray:
		return "MAKE_ARRAY " + strconv.Itoa(ins.Int)
	case OpMakeMap:
		return "MAKE_MAP " + strconv.Itoa(ins.Int)
	case OpGetIndex:
		return "GET_INDEX"
	case OpSetIndex:
		return "SET_INDEX"
	default:
		return ""
	}
}

func parseInstr(toks []string) (Instr, error) {
	if len(toks) == 0 {
		return Instr{}, fmt.Errorf("empty instruction")
	}
	op := toks[0]
	switch op {
	case "PUSH_NUM":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_NUM expects 1 arg")
		}
		v, err := strconv.Atoi(toks[1])
		if err != nil {
			return Instr{}, err
		}
		return Instr{Op: OpPushNum, Int: v}, nil
	case "PUSH_STR":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_STR expects 1 arg")
		}
		return Instr{Op: OpPushStr, Str: toks[1]}, nil
	case "PUSH_BOOL":
		if len(toks) != 2 {
			return Instr{}, fmt.Errorf("PUSH_BOOL expects 1 arg")
		}
		v, err := strconv.Atoi(toks[1])
		if err != nil {
			return Instr{}, err
		}
		return Instr{Op: OpPushBool, Int: v}, nil
	case "PUSH_NIL":
		return Instr{Op: OpPushNil}, nil
	case "LOAD":
		return parseNameInstr(toks, OpLoad)
	case "STORE":
		return parseNameInstr(toks, OpStore)
	case "DEFINE_VAR":
		return parseNameInstr(toks, OpDefineVar)
	case "DEFINE_CONST":
		return parseNameInstr(toks, OpDefineConst)
	case "ADD":
		return Instr{Op: OpAdd}, nil
	case "SUB":
		return Instr{Op: OpSub}, nil
	case "MUL":
		return Instr{Op: OpMul}, nil
	case "DIV":
		return Instr{Op: OpDiv}, nil
	case "NEG":
		return Instr{Op: OpNeg}, nil
	case "NOT":
		return Instr{Op: OpNot}, nil
	case "EQ":
		return Instr{Op: OpEq}, nil
	case "NEQ":
		return Instr{Op: OpNeq}, nil
	case "LT":
		return Instr{Op: OpLt}, nil
	case "LTE":
		return Instr{Op: OpLte}, nil
	case "GT":
		return Instr{Op: OpGt}, nil
	case "GTE":
		return Instr{Op: OpGte}, nil
	case "JUMP":
		return parseIntInstr(toks, OpJump)
	case "JUMP_IF_FALSE":
		return parseIntInstr(toks, OpJumpIfFalse)
	case "CALL":
		return parseIntInstr(toks, OpCall)
	case "RETURN":
		return Instr{Op: OpReturn}, nil
	case "ENTER_SCOPE":
		return Instr{Op: OpEnterScope}, nil
	case "EXIT_SCOPE":
		return Instr{Op: OpExitScope}, nil
	case "POP":
		return Instr{Op: OpPop}, nil
	case "MAKE_CLOSURE":
		return parseIntInstr(toks, OpMakeClosure)
	case "MAKE_ARRAY":
		return parseIntInstr(toks, OpMakeArray)
	case "MAKE_MAP":
		return parseIntInstr(toks, OpMakeMap)
	case "GET_INDEX":
		return Instr{Op: OpGetIndex}, nil
	case "SET_INDEX":
		return Instr{Op: OpSetIndex}, nil
	default:
		return Instr{}, fmt.Errorf("unknown opcode: %s", op)
	}
}

func parseNameInstr(toks []string, op OpCode) (Instr, error) {
	if len(toks) != 2 {
		return Instr{}, fmt.Errorf("name opcode expects 1 arg")
	}
	return Instr{Op: op, Str: toks[1]}, nil
}

func parseIntInstr(toks []string, op OpCode) (Instr, error) {
	if len(toks) != 2 {
		return Instr{}, fmt.Errorf("int opcode expects 1 arg")
	}
	v, err := strconv.Atoi(toks[1])
	if err != nil {
		return Instr{}, err
	}
	return Instr{Op: op, Int: v}, nil
}

func splitTokens(line string) ([]string, error) {
	var toks []string
	i := 0
	for i < len(line) {
		for i < len(line) && line[i] == ' ' {
			i++
		}
		if i >= len(line) {
			break
		}
		if line[i] == '"' {
			i++
			var out []byte
			closed := false
			for i < len(line) {
				ch := line[i]
				if ch == '"' {
					i++
					closed = true
					break
				}
				if ch == '\\' {
					if i+1 >= len(line) {
						return nil, fmt.Errorf("invalid escape")
					}
					i++
					esc := line[i]
					switch esc {
					case '"':
						out = append(out, '"')
					case '\\':
						out = append(out, '\\')
					case 'n':
						out = append(out, '\n')
					case 't':
						out = append(out, '\t')
					default:
						return nil, fmt.Errorf("invalid escape")
					}
					i++
					continue
				}
				out = append(out, ch)
				i++
			}
			if !closed {
				return nil, fmt.Errorf("unterminated string")
			}
			toks = append(toks, string(out))
			continue
		}
		start := i
		for i < len(line) && line[i] != ' ' {
			i++
		}
		toks = append(toks, line[start:i])
	}
	return toks, nil
}

func escapeString(s string) string {
	var b strings.Builder
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case '\\':
			b.WriteString("\\\\")
		case '"':
			b.WriteString("\\\"")
		case '\n':
			b.WriteString("\\n")
		case '\t':
			b.WriteString("\\t")
		default:
			b.WriteByte(s[i])
		}
	}
	return b.String()
}

func writeLine(b *strings.Builder, line string) {
	b.WriteString(line)
	b.WriteString("\n")
}

type binding struct {
	val     Value
	isConst bool
}

type Env struct {
	vars   map[string]*binding
	parent *Env
}

type frame struct {
	code []Instr
	ip   int
	env  *Env
}

type Heap struct {
	objects []*Object
}

func (h *Heap) alloc(obj *Object) *Object {
	h.objects = append(h.objects, obj)
	return obj
}

func (h *Heap) sweep() {
	live := h.objects[:0]
	for _, obj := range h.objects {
		if obj.Marked {
			obj.Marked = false
			live = append(live, obj)
		}
	}
	h.objects = live
}

func (h *Heap) count() int {
	return len(h.objects)
}

type VM struct {
	stack  []Value
	frames []frame
	funcs  map[int]Function
	heap   *Heap
	global *Env
}

func NewVM() *VM {
	return &VM{heap: &Heap{}}
}

func (vm *VM) Run(bc Bytecode) (Value, error) {
	vm.stack = nil
	vm.frames = nil
	vm.funcs = map[int]Function{}
	vm.heap = &Heap{}
	for _, fn := range bc.Functions {
		vm.funcs[fn.ID] = fn
	}
	vm.global = &Env{vars: map[string]*binding{}}
	vm.pushFrame(bc.Main, vm.global)

for len(vm.frames) > 0 {
		fr := vm.currentFrame()
		if fr.ip >= len(fr.code) {
			if len(vm.frames) == 1 {
				if len(vm.stack) > 0 {
					return vm.stack[len(vm.stack)-1], nil
				}
				return Value{Kind: ValueNil}, nil
			}
			vm.popFrame()
			vm.push(Value{Kind: ValueNil})
			continue
		}

instr := fr.code[fr.ip]
		fr.ip++

switch instr.Op {
		case OpPushNum:
			vm.push(Value{Kind: ValueNumber, Num: instr.Int})
		case OpPushStr:
			vm.push(Value{Kind: ValueString, Str: instr.Str})
		case OpPushBool:
			vm.push(Value{Kind: ValueBool, Bool: instr.Int != 0})
		case OpPushNil:
			vm.push(Value{Kind: ValueNil})
		case OpLoad:
			b, ok := fr.env.lookup(instr.Str)
			if !ok {
				return Value{}, fmt.Errorf("undefined name: %s", instr.Str)
			}
			vm.push(b.val)
		case OpStore:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if err := fr.env.assign(instr.Str, v); err != nil {
				return Value{}, err
			}
		case OpDefineVar:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			fr.env.define(instr.Str, v, false)
		case OpDefineConst:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			fr.env.define(instr.Str, v, true)
		case OpAdd:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind == ValueNumber && b.Kind == ValueNumber {
				vm.push(Value{Kind: ValueNumber, Num: a.Num + b.Num})
				break
			}
			if a.Kind == ValueString && b.Kind == ValueString {
				vm.push(Value{Kind: ValueString, Str: a.Str + b.Str})
				break
			}
			return Value{}, fmt.Errorf("type error: add")
		case OpSub:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: sub")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num - b.Num})
		case OpMul:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: mul")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num * b.Num})
		case OpDiv:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: div")
			}
			if b.Num == 0 {
				return Value{}, fmt.Errorf("division by zero")
			}
			vm.push(Value{Kind: ValueNumber, Num: a.Num / b.Num})
		case OpNeg:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if v.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: neg")
			}
			vm.push(Value{Kind: ValueNumber, Num: -v.Num})
		case OpNot:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: !isTruthy(v)})
		case OpEq:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: valueEqual(a, b)})
		case OpNeq:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			vm.push(Value{Kind: ValueBool, Bool: !valueEqual(a, b)})
		case OpLt:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lt")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num < b.Num})
		case OpLte:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: lte")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num <= b.Num})
		case OpGt:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gt")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num > b.Num})
		case OpGte:
			b, a, err := vm.pop2()
			if err != nil {
				return Value{}, err
			}
			if a.Kind != ValueNumber || b.Kind != ValueNumber {
				return Value{}, fmt.Errorf("type error: gte")
			}
			vm.push(Value{Kind: ValueBool, Bool: a.Num >= b.Num})
		case OpJump:
			fr.ip = instr.Int
		case OpJumpIfFalse:
			v, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if !isTruthy(v) {
				fr.ip = instr.Int
			}
		case OpCall:
			args, err := vm.popArgs(instr.Int)
			if err != nil {
				return Value{}, err
			}
			callee, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if callee.Kind != ValueClosure || callee.Obj == nil || callee.Obj.Closure == nil {
				return Value{}, fmt.Errorf("call of non-function")
			}
			closure := callee.Obj.Closure
			fn, ok := vm.funcs[closure.FuncID]
			if !ok {
				return Value{}, fmt.Errorf("unknown function id %d", closure.FuncID)
			}
			if len(args) != len(fn.Params) {
				return Value{}, fmt.Errorf("arity mismatch")
			}
			callEnv := &Env{vars: map[string]*binding{}, parent: closure.Env}
			for i, name := range fn.Params {
				callEnv.define(name, args[i], false)
			}
			vm.pushFrame(fn.Code, callEnv)
		case OpReturn:
			ret, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			vm.popFrame()
			if len(vm.frames) == 0 {
				return ret, nil
			}
			vm.push(ret)
		case OpEnterScope:
			fr.env = &Env{vars: map[string]*binding{}, parent: fr.env}
		case OpExitScope:
			if fr.env.parent != nil {
				fr.env = fr.env.parent
			}
		case OpPop:
			if _, err := vm.pop(); err != nil {
				return Value{}, err
			}
		case OpMakeClosure:
			obj := vm.heap.alloc(&Object{Kind: ObjClosure, Closure: &Closure{FuncID: instr.Int, Env: fr.env}})
			vm.push(Value{Kind: ValueClosure, Obj: obj})
		case OpMakeArray:
			arr, err := vm.popList(instr.Int)
			if err != nil {
				return Value{}, err
			}
			obj := vm.heap.alloc(&Object{Kind: ObjArray, Array: arr})
			vm.push(Value{Kind: ValueArray, Obj: obj})
		case OpMakeMap:
			m := map[hashKey]Value{}
			for i := 0; i < instr.Int; i++ {
				val, err := vm.pop()
				if err != nil {
					return Value{}, err
				}
				keyVal, err := vm.pop()
				if err != nil {
					return Value{}, err
				}
				key, ok := toKey(keyVal)
				if !ok {
					return Value{}, fmt.Errorf("invalid map key")
				}
				// Pairs pop in reverse source order; retain the last source value.
				if _, exists := m[key]; !exists {
					m[key] = val
				}
			}
			obj := vm.heap.alloc(&Object{Kind: ObjMap, Map: m})
			vm.push(Value{Kind: ValueMap, Obj: obj})
		case OpGetIndex:
			idx, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			target, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			v, err := vm.getIndex(target, idx)
			if err != nil {
				return Value{}, err
			}
			vm.push(v)
		case OpSetIndex:
			val, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			idx, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			target, err := vm.pop()
			if err != nil {
				return Value{}, err
			}
			if err := vm.setIndex(target, idx, val); err != nil {
				return Value{}, err
			}
		default:
			return Value{}, fmt.Errorf("unknown opcode")
		}
	}
	return Value{Kind: ValueNil}, nil
}

func (vm *VM) currentFrame() *frame {
	return &vm.frames[len(vm.frames)-1]
}

func (vm *VM) pushFrame(code []Instr, env *Env) {
	vm.frames = append(vm.frames, frame{code: code, env: env})
}

func (vm *VM) popFrame() {
	if len(vm.frames) > 0 {
		vm.frames = vm.frames[:len(vm.frames)-1]
	}
}

func (vm *VM) push(v Value) {
	vm.stack = append(vm.stack, v)
}

func (vm *VM) pop() (Value, error) {
	if len(vm.stack) == 0 {
		return Value{}, fmt.Errorf("stack underflow")
	}
	v := vm.stack[len(vm.stack)-1]
	vm.stack = vm.stack[:len(vm.stack)-1]
	return v, nil
}

func (vm *VM) pop2() (Value, Value, error) {
	b, err := vm.pop()
	if err != nil {
		return Value{}, Value{}, err
	}
	a, err := vm.pop()
	if err != nil {
		return Value{}, Value{}, err
	}
	return b, a, nil
}

func (vm *VM) popArgs(n int) ([]Value, error) {
	if n == 0 {
		return nil, nil
	}
	args := make([]Value, n)
	for i := n - 1; i >= 0; i-- {
		v, err := vm.pop()
		if err != nil {
			return nil, err
		}
		args[i] = v
	}
	return args, nil
}

func (vm *VM) popList(n int) ([]Value, error) {
	if n == 0 {
		return nil, nil
	}
	out := make([]Value, n)
	for i := n - 1; i >= 0; i-- {
		v, err := vm.pop()
		if err != nil {
			return nil, err
		}
		out[i] = v
	}
	return out, nil
}

func (vm *VM) getIndex(target Value, idx Value) (Value, error) {
	switch target.Kind {
	case ValueArray:
		if idx.Kind != ValueNumber {
			return Value{}, fmt.Errorf("index must be number")
		}
		arr := target.Obj.Array
		if idx.Num < 0 || idx.Num >= len(arr) {
			return Value{}, fmt.Errorf("index out of range")
		}
		return arr[idx.Num], nil
	case ValueMap:
		key, ok := toKey(idx)
		if !ok {
			return Value{}, fmt.Errorf("invalid map key")
		}
		val, ok := target.Obj.Map[key]
		if !ok {
			return Value{Kind: ValueNil}, nil
		}
		return val, nil
	default:
		return Value{}, fmt.Errorf("indexing non-collection")
	}
}

func (vm *VM) setIndex(target Value, idx Value, val Value) error {
	switch target.Kind {
	case ValueArray:
		if idx.Kind != ValueNumber {
			return fmt.Errorf("index must be number")
		}
		arr := target.Obj.Array
		if idx.Num < 0 || idx.Num >= len(arr) {
			return fmt.Errorf("index out of range")
		}
		arr[idx.Num] = val
		target.Obj.Array = arr
		return nil
	case ValueMap:
		key, ok := toKey(idx)
		if !ok {
			return fmt.Errorf("invalid map key")
		}
		target.Obj.Map[key] = val
		return nil
	default:
		return fmt.Errorf("indexing non-collection")
	}
}

func isTruthy(v Value) bool {
	if v.Kind == ValueNil {
		return false
	}
	if v.Kind == ValueBool {
		return v.Bool
	}
	return true
}

func valueEqual(a Value, b Value) bool {
	if a.Kind != b.Kind {
		return false
	}
	switch a.Kind {
	case ValueNumber:
		return a.Num == b.Num
	case ValueString:
		return a.Str == b.Str
	case ValueBool:
		return a.Bool == b.Bool
	case ValueNil:
		return true
	case ValueArray, ValueMap, ValueClosure:
		return a.Obj == b.Obj
	default:
		return false
	}
}

func toKey(v Value) (hashKey, bool) {
	switch v.Kind {
	case ValueNumber:
		return hashKey{kind: v.Kind, num: v.Num}, true
	case ValueString:
		return hashKey{kind: v.Kind, str: v.Str}, true
	case ValueBool:
		return hashKey{kind: v.Kind, b: v.Bool}, true
	case ValueNil:
		return hashKey{kind: v.Kind}, true
	default:
		return hashKey{}, false
	}
}

func (e *Env) define(name string, v Value, isConst bool) {
	if e.vars == nil {
		e.vars = map[string]*binding{}
	}
	e.vars[name] = &binding{val: v, isConst: isConst}
}

func (e *Env) lookup(name string) (*binding, bool) {
	for cur := e; cur != nil; cur = cur.parent {
		if b, ok := cur.vars[name]; ok {
			return b, true
		}
	}
	return nil, false
}

func (e *Env) assign(name string, v Value) error {
	for cur := e; cur != nil; cur = cur.parent {
		if b, ok := cur.vars[name]; ok {
			if b.isConst {
				return fmt.Errorf("cannot assign to const: %s", name)
			}
			b.val = v
			return nil
		}
	}
	return fmt.Errorf("undefined name: %s", name)
}