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

// 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

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

use crate::bytecode::error::StreamError;
use crate::bytecode::{Instruction, InstructionStream, JumpTable};

use super::error::VerifierError;

/// Convert a [`StreamError`] into a [`VerifierError`].
///
/// `SeekOutOfBounds` cannot be triggered by sequential stream iteration,
/// so it is mapped defensively to `TruncatedInstruction`.
pub(super) fn stream_err(e: &StreamError) -> VerifierError {
    match e {
        StreamError::TruncatedInstruction { offset } => {
            VerifierError::TruncatedInstruction { offset: *offset }
        }
        StreamError::UnknownOpcode { offset, byte } => VerifierError::BadOpcode {
            offset: *offset,
            byte: *byte,
        },
        StreamError::SeekOutOfBounds { target, .. } => {
            VerifierError::TruncatedInstruction { offset: *target }
        }
    }
}

/// Build a [`JumpTable`], count slot instructions, and detect the first Phase 1
/// violation in one pass.
///
/// Walks the instruction bytes exactly once, collecting:
/// - byte positions of `TARGET` opcodes (for the jump table),
/// - counts of `INPUT` and `OUTPUT` instructions (clamped to `u8::MAX`),
/// - loop-opener positions (to check nesting balance),
/// - jump-instruction labels (for deferred target-count validation).
///
/// Structural errors (`BadOpcode`, `TruncatedInstruction`) abort the walk
/// immediately. Loop and jump-target errors are recorded after the walk.
///
/// Returns `(jump_table, (input_slots, output_slots), first_error)`.
pub(crate) fn scan(code: &[u8]) -> (JumpTable, (u8, u8), Option<VerifierError>) {
    let mut targets: Vec<usize> = Vec::new();
    let mut loop_offsets: Vec<usize> = Vec::new();
    let mut jump_refs: Vec<(usize, u16)> = Vec::new();
    let mut first_error: Option<VerifierError> = None;
    let mut input_slots: u8 = 0;
    let mut output_slots: u8 = 0;

    let mut stream = InstructionStream::new(code);
    'scan: while let Some(item) = stream.next_instruction() {
        let (pos, _label, instr) = match item {
            Ok(v) => v,
            Err(e) => {
                let _ = first_error.get_or_insert_with(|| stream_err(&e));
                break 'scan;
            }
        };

        match instr {
            Instruction::Target {} => targets.push(pos),
            Instruction::Input { .. } => input_slots = input_slots.saturating_add(1),
            Instruction::Output { .. } => output_slots = output_slots.saturating_add(1),
            Instruction::Range {} | Instruction::Iter { .. } => loop_offsets.push(pos),
            Instruction::Next {} if first_error.is_none() && loop_offsets.pop().is_none() => {
                first_error = Some(VerifierError::NoActiveLoop { offset: pos });
            }
            Instruction::Lidx { .. } | Instruction::LVal { .. } if loop_offsets.is_empty() => {
                let _ = first_error.get_or_insert(VerifierError::NoActiveLoop { offset: pos });
            }
            Instruction::Jump1 { label } | Instruction::JumpI1 { label } => {
                jump_refs.push((pos, u16::from(label)));
            }
            Instruction::Jump2 { label } | Instruction::JumpI2 { label } => {
                jump_refs.push((pos, label));
            }
            _ => {}
        }
    }

    // Unmatched loop openers: report the outermost (first-pushed) one.
    if first_error.is_none()
        && let Some(&outermost) = loop_offsets.first()
    {
        first_error = Some(VerifierError::UnmatchedLoop {
            offset: outermost,
            depth: loop_offsets.len(),
        });
    }

    let jump_table = JumpTable::new(targets);

    // Deferred jump-target check: needs the final TARGET count.
    if first_error.is_none() {
        let target_count = jump_table.len();
        for (offset, label) in jump_refs {
            if usize::from(label) >= target_count {
                first_error = Some(VerifierError::UndefinedJumpTarget {
                    offset,
                    label,
                    target_count,
                });
                break;
            }
        }
    }

    (jump_table, (input_slots, output_slots), first_error)
}