Cabbage

A stack-based virtual machine with generational mark and sweep garbage collection, written in Rust.

Building

Requires Rust toolchain (1.70+). Build with:

cargo build --release

Running

Execute an assembly file:

cargo run -- <file.asm>

Example:

cargo run -- examples/example.asm

Architecture

src/
├── main.rs           # CLI entry point
├── lib.rs            # Public API exports
├── asm/
│   ├── mod.rs        # Assembly module
│   └── parser.rs     # Two-pass assembler (labels + bytecode generation)
└── vm/
    ├── mod.rs        # VM module
    ├── vm.rs         # Virtual machine (fetch-decode-execute loop)
    ├── gc.rs         # Generational garbage collector
    ├── value.rs      # Value types (Int, Object) and heap objects
    ├── opcode.rs     # Instruction opcodes
    └── error.rs      # VM error types

How It Works

Virtual Machine

The VM is stack-based with a program counter that iterates through bytecode instructions. Values on the stack are either immediate integers or references to heap-allocated objects.

Supported instructions:

Opcode	Hex	Description
HALT	0x00	Stop execution
ICONST n	0x01	Push 32-bit integer n onto the stack
IADD	0x02	Pop two integers, push their sum
ISUB	0x03	Pop two integers, push their difference
IMUL	0x04	Pop two integers, push their product
LOADCONST i	0x05	Load constant at index i, allocate on heap
PRINT	0x06	Pop and print top of stack
JUMP label	0x07	Unconditional jump to label
JUMPIFZERO label	0x08	Pop integer; jump if zero
DUP	0x09	Duplicate top of stack

Garbage Collector

The GC uses a generational mark-and-sweep algorithm with two generations:

• Young generation: Newly allocated objects start here
• Old generation: Objects that survive multiple GC cycles are promoted

Collection process:

1. Minor GC (young generation only):

   • Mark objects reachable from the stack
   • Increment age of surviving objects
   • Promote objects exceeding the age threshold to old generation
   • Sweep unmarked objects

2. Major GC (both generations):

   • Mark all reachable objects across both generations
   • Sweep unmarked objects from both generations

GC is triggered automatically when generation limits are reached during allocation.

Assembly Parser

The parser performs two passes:

1. First pass: Collect label addresses and parse instructions
2. Second pass: Generate bytecode with resolved label references

Assembly syntax supports:

• Comments: ; comment
• Labels: label_name:
• String literals: LOADCONST "hello"
• Case-insensitive instructions

Examples

Arithmetic (examples/example.asm):

ICONST 10
ICONST 20
IADD          ; 30
PRINT
HALT

Loop (examples/loop.asm):

    ICONST 5
loop:
    DUP
    PRINT
    ICONST -1
    IADD
    DUP
    JUMPIFZERO done
    JUMP loop
done:
    HALT