xqvm 0.2.0

X-Quadratic Virtual Machine — bytecode interpreter for the XQuad Toolchain
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

// Copyright (C) 2026 Postquant Labs Incorporated
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Pre-execution bytecode verifier for XQVM programs.
//!
//! Verification is structured as composable [`Phase`]s. Each phase performs
//! one focused check over a [`Program`] and maps failures to [`VerifierError`]
//! via its `type Error: Into<VerifierError>`. A [`Verifier`] runs phases
//! sequentially, stopping at the first failure.
//!
//! The low-level `scan` function is the shared kernel: it makes one linear
//! pass over the instruction bytes, builds the [`crate::JumpTable`], and returns the
//! first Phase 1 violation. [`Program::new`] calls it to obtain the jump
//! table (ignoring any error); [`Verifier::default`] calls it once per
//! invocation rather than running three separate stream passes.
//!
//! # Phases
//!
//! | Phase | What it checks | Errors emitted |
//! |---|---|---|
//! | [`StructuralPhase`] | Truncated bytes, unknown opcodes | [`VerifierError::TruncatedInstruction`], [`VerifierError::BadOpcode`] |
//! | [`JumpTargetPhase`] | Jump label ≥ target count | [`VerifierError::UndefinedJumpTarget`] |
//! | [`LoopNestingPhase`] | Loop open/close balance, loop-context reads | [`VerifierError::NoActiveLoop`], [`VerifierError::UnmatchedLoop`] |
//! | [`RegisterTypePhase`] | CFG-based read-before-write; type-state mismatches | [`VerifierError::ReadUnsetRegister`], [`VerifierError::RegisterTypeMismatch`] |
//! | [`UninitRegisterPhase`] | CFG AND-meet: registers uninit on at least one path | [`VerifierError::ReadUnsetRegister`] |
//! | [`StackDepthPhase`] | CFG-based stack depth: underflow/overflow, loop balance, join-point mismatch | [`VerifierError::StackUnderflow`], [`VerifierError::StackOverflowRisk`], [`VerifierError::LoopStackImbalance`], [`VerifierError::StackDepthMismatch`] |
//!
//! Phase 1 (structural, jump, loop) runs as a single combined pass via
//! `scan`. Phases 2–4 each build a control-flow graph and run a forward
//! worklist analysis:
//!
//! * [`RegisterTypePhase`] -- permissive Any-meet at join points; catches
//!   read-before-write and type mismatches on all CFG paths.
//! * [`UninitRegisterPhase`] -- AND-meet at join points; flags registers that
//!   are definitely unset on at least one incoming path.
//! * [`StackDepthPhase`] -- min-meet for underflow detection, plus a strict-
//!   equality pass over join-point predecessors for [`VerifierError::StackDepthMismatch`].
//!
//! # Quick start
//!
//! ```rust
//! use xqvm::{verifier, InstructionBuilder};
//!
//! let mut b = InstructionBuilder::new();
//! b.emit_push(1).emit_push(2).emit_add().emit_halt();
//! let program = b.build().unwrap();
//! assert!(verifier::verify(&program).is_ok());
//! ```
//!
//! # Custom composition
//!
//! ```rust
//! use xqvm::verifier::{Phase, Verifier, JumpTargetPhase, LoopNestingPhase};
//! use xqvm::InstructionBuilder;
//!
//! let mut b = InstructionBuilder::new();
//! b.emit_halt();
//! let program = b.build().unwrap();
//!
//! // Run only the jump and loop checks, skip the structural pass.
//! let result = Verifier::new()
//!     .with_phase(JumpTargetPhase)
//!     .with_phase(LoopNestingPhase)
//!     .run(&program);
//! assert!(result.is_ok());
//! ```

mod error;
mod jump_target;
mod loop_nesting;
mod phase;
pub(crate) mod reg_type;
mod register_type;
mod scan;
mod stack_depth;
mod structural;
mod uninit_register;

#[cfg(test)]
mod tests;

// ---------------------------------------------------------------------------
// Public re-exports
// ---------------------------------------------------------------------------

pub use error::VerifierError;
pub use jump_target::JumpTargetPhase;
pub use loop_nesting::LoopNestingPhase;
pub use phase::{Phase, Verifier};
pub use reg_type::RegType;
pub use register_type::RegisterTypePhase;
pub use stack_depth::StackDepthPhase;
pub use structural::StructuralPhase;
pub use uninit_register::UninitRegisterPhase;

pub(crate) use scan::scan;

use crate::Program;

/// Run the full four-phase verifier over `program`.
///
/// Equivalent to `Verifier::default().run(program)`. Runs `CombinedPhase`
/// (structural, jump-target, loop-nesting) followed by [`RegisterTypePhase`]
/// (CFG-based read-before-write and type-state checks) followed by
/// [`UninitRegisterPhase`] (CFG AND-meet must-init analysis) followed by
/// [`StackDepthPhase`] (CFG-based stack depth, loop balance, and join-point
/// depth consistency). Returns the first [`VerifierError`] found, or
/// `Ok(())` if all checks pass.
///
/// # Errors
///
/// Returns a [`VerifierError`] on the first violation detected.
///
/// # Examples
///
/// ```rust
/// use xqvm::{verifier, InstructionBuilder};
///
/// let mut b = InstructionBuilder::new();
/// b.emit_push(42).emit_halt();
/// assert!(verifier::verify(&b.build().unwrap()).is_ok());
/// ```
pub fn verify(program: &Program) -> Result<(), VerifierError> {
    Verifier::default().run(program)
}