# Regorus Virtual Machine Architecture This document explains how Rego source becomes executable bytecode and how the runtime evaluates it. It is meant for three audiences: - **Engine developers** working on the RVM execution core and runtime subsystems. - **Policy front-end authors** targeting the VM from alternate policy languages. - **Operators/tools** wanting to reason about execution behaviour and troubleshooting output. The high-level pipeline looks like this: ``` ┌───────────┐ emit Program ┌────────────┐ load & run ┌─────────┐ │ Parser & │ ───────────────▶ │ Program │ ─────────────▶ │ Rego VM │ │ Compiler │ (bytecode) │ Artifact │ (instructions│ Runtime │ └───────────┘ │ │ + metadata) │ │ └────────────┘ └─────────┘ ``` Each step feeds the next via well-defined data structures described below. --- ## RVM in context The Rego VM uses a register-based architecture with the following traits: - **Register windows per frame**: Each rule or function call receives a compile-time-sized register window. Windows are pooled and reused to keep the runtime allocation profile predictable. - **Sequential bytecode stream**: Fixed-width 32-bit instructions execute from a linear program counter with optional jumps. Complex instructions reference shared tables (`InstructionData`) that carry literals, loop metadata and call parameters. - **Literal and builtin tables**: Literal pools and builtin dispatch tables are resolved at load time so bytecode stays compact and symbol lookups remain constant-time during execution. - **Extended control stacks**: Loop, rule-cache and comprehension stacks sit alongside the core call stack, enabling suspension, short-circuiting and deterministic rule caching without growing the register windows themselves. --- ## 1. Compilation Outputs A successful compilation produces a `Program` (`src/rvm/program/core.rs`). The layout is deliberately split: - **Stable artifact section**: Always serialised and treated as canonical. It captures the original policy sources, entry-points, compiler options, etc. - **Synthesised execution section**: It contains the compiled instruction stream, instruction parameter tables, literal tables, etc. It can be recreated from the stable artifact section if a future RVM version is note able to deserialize it. | Field | Purpose | Notes | | :---------------------------------------------- | :--------------------------------------------------------------- | :---- | | `instructions: Vec` | Ordered bytecode emitted by the compiler. | Each opcode is defined in `src/rvm/instructions/mod.rs` and executed by the dispatch tree. | | `literals: Vec` | Literal constants shared across instructions. | Skipped by serde but written in the binary format via `BinaryValueSlice`; avoids duplicating large value graphs. | | `instruction_data: InstructionData` | Parameter tables for complex opcodes. | Tables are indexed by `params_index` values stored in instructions. | | `builtin_info_table: Vec` | Metadata for builtin calls. | Enforced and resolved by `Program::initialize_resolved_builtins`. | | `entry_points: IndexMap` | Maps path names (e.g. `data.pkg.rule`) to starting PCs. | Preserves declaration order for tooling and serialized in the artifact section. | | `sources: Vec` | Captures original policy sources. | Stored in the stable artifact section alongside entry-points. | | `rule_infos: Vec` | Metadata for every rule. | Includes register windows, default values, destructuring blocks. | | `instruction_spans: Vec>` | Optional span info for diagnostics. | Lines/columns mapped back into the source table when present. | | `main_entry_point: usize` | Default bytecode entry point. | Used by loaders to jump into the top-level policy. | | `max_rule_window_size` / `dispatch_window_size` | Register window sizing hints. | The VM uses these to size register banks up-front. | | `metadata: ProgramMetadata` | Compilation metadata (`compiler_version`, etc.). | Helps operators verify provenance and tooling compatibility. | | `rule_tree: Value` | Map of rule labels for conflict detection and lookups. | Serialized via `BinaryValueRef`; rebuilt into a `Value::Object` during load. | | `resolved_builtins: Vec` | Resolved builtin function pointers. | Not serialized; repopulated by the host at load time. | | `needs_runtime_recursion_check: bool` | Flags when `VirtualDataDocumentLookup` requires runtime guards. | Ensures the VM short-circuits recursion before hitting the instruction budget ceiling. | | `needs_recompilation: bool` | Indicates partial deserialization of execution data. | Set when the extensible section fails; signals the loader to recompile. | | `rego_v0: bool` | Records whether the policy targeted Rego v0 semantics. | Ensures recompilation preserves language-version behaviour. | Additional helpers such as `Program::add_*`, `Program::update_*`, and `Program::display_instruction_with_params` are used by the compiler and inspection tooling to populate and render the program. ### Serialization layout The module `src/rvm/program/serialization` writes `Program` instances into a compact binary envelope that stays forward-compatible within a major format version: 1. **Header**: magic `REGO` bytes followed by `SERIALIZATION_VERSION` (currently `3`). 2. **Section manifest**: four little-endian `u32` lengths for entry points, sources, literals, and the rule tree, plus a single-byte `rego_v0` flag. 3. **Preamble payloads**: each section is encoded with `postcard` using helper wrappers (`BinaryValueSlice`, `BinaryValueRef`) to stream complex `Value` graphs without cloning. 4. **Program core**: the remaining `Program` struct is serialized once more via `postcard`; fields skipped by serde (entry points, literals, sources, rule_tree, resolved builtins) are re-inserted from the preamble when the program is reconstructed. During deserialization the loader sanity-checks the header, lengths, and version before decoding each preamble section. Any failure while decoding the core payload downgrades the result to `DeserializationResult::Partial`, preserving enough artifact data to trigger a recompilation. Successful loads call `Program::initialize_resolved_builtins` so host runtimes can plug in their builtin implementations. --- ## 2. Runtime Subsystems At evaluation time the `RegoVM` (`src/rvm/vm/machine.rs`) consumes a `Program` and exposes execution APIs. The VM separates concerns through specialised stacks and caches. ````text Runtime stacks (run-to-completion) ┌──────────────────────────── RegoVM ─────────────────────────────┐ │ Registers (active window) ─────┐ │ │ Program counter (pc) ───────┐ │ │ │ ▼ ▼ │ │ Control flow dispatcher ───────────────▶ Instruction stream │ │ ▲ ▲ │ │ Rule cache ────────┐ │ │ Loop stack (LoopContext) │ │ Evaluation cache │ │ └──▶ Comprehension stack │ │ Host await queue ──┴─▶ Return values / suspensions │ └─────────────────────────────────────────────────────────────────┘ Suspendable mode frame stack ┌───────────────────────────────────────────────────────────────────────┐ │ Frame stack │ │ │ │ ┌────────────────┐ ┌────────────────┐ ┌──────────────────────┐ │ │ │ RuleFrame │ → │ LoopFrame │ → │ ComprehensionFrame │ │ │ └────────────────┘ └────────────────┘ └──────────────────────┘ │ │ ▲ ▲ ▲ │ │ │ push frame │ push frame │ push frame│ │ ▼ ▼ ▼ │ │ allow { ... } │ │ some user in input.users │ │ [x | ... ] │ └─────────┴─────────────────────────────────────────────────────────────┘ Execution state machine (suspendable) ┌──────────────────────┐ │ Suspended │ └─────▲────────────┬───┘ │ │ | │ │ │ │ │ HostAwait/Breakpoint/Step │ | resume │ │ │ │ | ▼ ┌──────────┐ ┌───────────────────────────┐ Return ┌────────────┐ │ Ready ├─────────────▶│ Running │────────────▶│ Completed │ └──────────┘ └────────────┬──────────────┘ └────────────┘ │ VmError ▼ ┌──────────┐ │ Error │ └──────────┘ ```` Key state: - **Registers**: The active register window for the current frame. Windows are allocated per rule call using a register pool to minimise allocations. - **Program counter (`pc`)**: The bytecode index for run-to-completion mode. In suspendable mode, each frame tracks its own `pc`. - **Rule cache**: Stores results and completion flags per rule to avoid recomputation. - **Loop/comprehension stacks**: Track iteration state, completion criteria, and pending yields. - **Execution stack**: Present in suspendable mode. Stores `ExecutionFrame` objects (`FrameKind::Rule`, `Loop`, `Comprehension`) so that the VM can pause and resume evaluation cleanly. - **Host await responses**: For run-to-completion execution, pre-defined values keyed by identifier. Suspendable mode instead returns a `SuspendReason::HostAwait` to the caller. - **Evaluation cache**: Used by `VirtualDataDocumentLookup` to memoise path results. --- ## 3. Execution Modes The VM supports two execution styles selected via `set_execution_mode`. ### Run-to-completion - Entry point: `RegoVM::execute` or `execute_entry_point_by_{index,name}`. - Control loop: `execute_run_to_completion` → `jump_to` which iterates the instruction stream sequentially. - Suspension: Unsupported. Any instruction that would suspend emits a runtime error because the host cannot resume. - Traps: Instruction budget enforced via `max_instructions`; exceeding the limit returns `VmError::InstructionLimitExceeded`. ### Suspendable - Entry point: same as above, but the VM calls `run_stackless_from` which pushes a main `ExecutionFrame` and dispatches instructions through `run_stackless_loop`. - Frames: Each instruction can adjust the currently active frame or push/pop new frames (rule calls, loops, comprehensions). - Suspension: `InstructionOutcome::Suspend` transitions the VM into `ExecutionState::Suspended` with a `SuspendReason` (host await, breakpoint, single-step). The host must call `resume` with an optional value to continue. - Breakpoints & step mode: Configured via `set_step_mode` and breakpoint mutators on `ExecutionState`. Execution halts when a frame `pc` matches a registered breakpoint. In both modes the VM constantly validates safety conditions: parameter indices must resolve, register windows must exist, and results must stay inside the supported `Value` lattice. Errors are reported as `VmError` variants that include formatted state snapshots where possible. --- ## 4. Data-flow Walkthrough 1. **Rule entry**: The compiler emits a `CallRule` instruction referencing a rule index. The VM first consults `rule_cache[rule_index]`; non-function rules that have already executed within the current top-level run reuse the cached result. When the cache is cold, the VM pushes a new rule frame, allocates a register window and jumps to the rule entry point. Function rules always run afresh today—per-specialisation memoization is not yet implemented. 2. **Literal loads**: `Load` and `Load*` instructions fill registers from the literal table or other sources (`LoadData`, `LoadInput`). 3. **Loops**: `LoopStart` fetches `LoopStartParams` from `InstructionData`, initialises a `LoopContext`, and either pushes a new execution frame (for suspendable mode) or updates `loop_stack`. `LoopNext` consults loop mode (`Any`, `Every`, `ForEach`) to decide whether to continue or short-circuit. 4. **Comprehensions**: `ComprehensionBegin`/`Yield`/`End` manage collection builders stored in a `ComprehensionContext`. Nested comprehensions stack cleanly with loops. 5. **Assertions**: `AssertCondition` and `AssertNotUndefined` enforce Rego's truthiness semantics. Inside loops/comprehensions they flag the current iteration as failed (or short-circuit `every` loops to `false`); outside loop contexts they raise `VmError::AssertionFailed`, mirroring Rego's runtime errors for failed guards. 6. **Builtins & functions**: `BuiltinCall` reads `BuiltinCallParams`, resolves the host function via `get_resolved_builtin`, and writes the result. Function rules use `FunctionCallParams` to marshal arguments and run in the same pipeline; repeat invocations with the same arguments are recomputed until the VM grows specialisation-aware caching. 7. **Host await**: In run-to-completion mode, `HostAwait` consumes a response from `host_await_responses`. Suspendable mode yields control with a `SuspendReason::HostAwait { dest, argument, identifier }` that the host must service. 8. **Completion**: `Return` wraps the selected register value into `InstructionOutcome::Return`, unwinding frames until the entry frame is cleared. `RuleReturn` is a specialised variant used by rule execution helpers. Throughout execution, diagnostics (register snapshots, loop counters, cache hits) can be collected via `RegoVM` accessors. Integration tests in `tests/rvm/vm/suites` exercise the most complex combinations of loops, comprehensions and host calls; `complex.yaml` is a good starting point for understanding real-world instruction streams. --- ## 5. Related Documentation - [Instruction Set Reference](instruction-set.md) - [VM Runtime Walkthrough](vm-runtime.md)