vm/
bytecode.rs

1use std::collections::{HashMap, hash_map};
2use std::fmt;
3use std::hash::{BuildHasherDefault, Hash, Hasher};
4use std::sync::{Arc, OnceLock};
5
6use crate::compiler::TypeSchema;
7
8pub const BYTECODE_ABI_VERSION: u16 = 10;
9
10pub type SharedString = Arc<String>;
11pub type SharedBytes = Arc<Vec<u8>>;
12pub type SharedArray = Arc<Vec<Value>>;
13pub type SharedMap = Arc<VmMap>;
14pub type SharedCallable = Arc<CallableValue>;
15pub type SharedCaptureCell = Arc<std::sync::Mutex<Value>>;
16
17#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
18pub enum CallableKind {
19    FunctionItem,
20    Closure,
21    HostFunction,
22}
23
24#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
25#[repr(u8)]
26pub enum CaptureBindingMode {
27    Copy = 0,
28    Borrow = 1,
29    BorrowMut = 2,
30    Move = 3,
31}
32
33#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
34pub enum CallableTarget {
35    ScriptFunction(u32),
36    HostImport(u16),
37}
38
39#[derive(Clone, Debug, PartialEq, Eq, Hash)]
40pub struct ScriptFunction {
41    pub entry_ip: u32,
42    pub end_ip: u32,
43}
44
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub struct CallablePrototype {
47    pub kind: CallableKind,
48    pub target: CallableTarget,
49    pub arity: u8,
50    pub frame_local_count: usize,
51    pub parameter_slots: Vec<u16>,
52    pub capture_source_slots: Vec<u16>,
53    pub capture_slots: Vec<u16>,
54    pub capture_modes: Vec<CaptureBindingMode>,
55    pub self_slot: Option<u16>,
56    pub schema: Option<TypeSchema>,
57}
58
59#[derive(Clone, Debug, PartialEq, Eq, Hash)]
60pub struct FunctionRegion {
61    pub start_ip: u32,
62    pub end_ip: u32,
63    pub prototype_id: Option<u32>,
64}
65
66#[derive(Clone, Debug, PartialEq, Eq, Hash)]
67pub struct RootCallableBinding {
68    pub local_slot: u16,
69    pub prototype_id: u32,
70}
71
72#[derive(Clone, Debug, PartialEq, Eq, Hash)]
73pub struct ExportedCallable {
74    pub name: String,
75    pub local_slot: u16,
76}
77
78#[derive(Debug)]
79pub struct CallableEnvironment {
80    pub(crate) cells: std::sync::Mutex<Vec<SharedCaptureCell>>,
81}
82
83#[derive(Clone, Debug)]
84pub struct CallableValue {
85    pub prototype_id: u32,
86    pub kind: CallableKind,
87    pub env: Option<Arc<CallableEnvironment>>,
88}
89
90type VmMapStorage = HashMap<MapKey, Value, BuildHasherDefault<StableHasher>>;
91
92/// Runtime map storage for VM values.
93///
94/// Keys and values may be any runtime [`Value`]. Key equality is hybrid:
95/// scalars, strings, and bytes compare by value, while arrays and maps compare by
96/// heap-object identity. Float keys use canonicalized IEEE bits: `0.0` /
97/// `-0.0` are treated as the same key, while `NaN` keys only compare equal
98/// when their bit patterns match. Duplicate inserts overwrite the prior value
99/// for the same key.
100///
101/// Heap-backed keys remain stable after insertion. Values are reference-counted
102/// and container writes detach before mutation, so later writes through an
103/// alias create a new heap object instead of mutating a key already stored in
104/// the map.
105#[derive(Clone, Default)]
106pub struct VmMap {
107    entries: VmMapStorage,
108    cached_len: usize,
109}
110
111#[derive(Clone, Debug)]
112struct MapKey(Value);
113
114pub struct VmMapIter<'a> {
115    inner: hash_map::Iter<'a, MapKey, Value>,
116}
117
118pub struct VmMapIntoIter {
119    inner: hash_map::IntoIter<MapKey, Value>,
120}
121
122#[derive(Default)]
123pub(crate) struct StableHasher(u64);
124
125impl Hasher for StableHasher {
126    fn finish(&self) -> u64 {
127        self.0
128    }
129
130    fn write(&mut self, bytes: &[u8]) {
131        const OFFSET_BASIS: u64 = 0xcbf29ce484222325;
132        const PRIME: u64 = 0x100000001b3;
133
134        if self.0 == 0 {
135            self.0 = OFFSET_BASIS;
136        }
137        for byte in bytes {
138            self.0 ^= u64::from(*byte);
139            self.0 = self.0.wrapping_mul(PRIME);
140        }
141    }
142}
143
144impl VmMap {
145    pub fn new() -> Self {
146        Self::default()
147    }
148
149    pub fn from_entries(entries: Vec<(Value, Value)>) -> Self {
150        let mut out = Self::new();
151        for (key, value) in entries {
152            out.insert(key, value);
153        }
154        out
155    }
156
157    pub fn len(&self) -> usize {
158        debug_assert_eq!(self.cached_len, self.entries.len());
159        self.cached_len
160    }
161
162    pub fn is_empty(&self) -> bool {
163        self.len() == 0
164    }
165
166    pub fn iter(&self) -> VmMapIter<'_> {
167        VmMapIter {
168            inner: self.entries.iter(),
169        }
170    }
171
172    pub fn get(&self, key: &Value) -> Option<&Value> {
173        self.entries.get(&MapKey::new(key.clone()))
174    }
175
176    pub fn insert(&mut self, key: Value, value: Value) -> Option<Value> {
177        let replaced = self.entries.insert(MapKey::new(key), value);
178        self.cached_len = self.entries.len();
179        replaced
180    }
181
182    pub fn remove(&mut self, key: &Value) -> Option<Value> {
183        let removed = self.entries.remove(&MapKey::new(key.clone()));
184        self.cached_len = self.entries.len();
185        removed
186    }
187}
188
189#[allow(dead_code)]
190pub(crate) fn vm_map_len_field_offset() -> usize {
191    std::mem::offset_of!(VmMap, cached_len)
192}
193
194impl From<Vec<(Value, Value)>> for VmMap {
195    fn from(value: Vec<(Value, Value)>) -> Self {
196        Self::from_entries(value)
197    }
198}
199
200impl IntoIterator for VmMap {
201    type Item = (Value, Value);
202    type IntoIter = VmMapIntoIter;
203
204    fn into_iter(self) -> Self::IntoIter {
205        VmMapIntoIter {
206            inner: self.entries.into_iter(),
207        }
208    }
209}
210
211impl<'a> IntoIterator for &'a VmMap {
212    type Item = (&'a Value, &'a Value);
213    type IntoIter = VmMapIter<'a>;
214
215    fn into_iter(self) -> Self::IntoIter {
216        self.iter()
217    }
218}
219
220impl fmt::Debug for VmMap {
221    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
222        f.debug_map().entries(self.iter()).finish()
223    }
224}
225
226impl PartialEq for VmMap {
227    fn eq(&self, other: &Self) -> bool {
228        self.entries == other.entries
229    }
230}
231
232impl Eq for VmMap {}
233
234impl MapKey {
235    fn new(value: Value) -> Self {
236        Self(value)
237    }
238
239    fn value(&self) -> &Value {
240        &self.0
241    }
242
243    fn into_value(self) -> Value {
244        self.0
245    }
246}
247
248impl PartialEq for MapKey {
249    fn eq(&self, other: &Self) -> bool {
250        map_key_eq(&self.0, &other.0)
251    }
252}
253
254impl Eq for MapKey {}
255
256impl Hash for MapKey {
257    fn hash<H: Hasher>(&self, state: &mut H) {
258        hash_map_key(&self.0, state);
259    }
260}
261
262impl<'a> Iterator for VmMapIter<'a> {
263    type Item = (&'a Value, &'a Value);
264
265    fn next(&mut self) -> Option<Self::Item> {
266        self.inner.next().map(|(key, value)| (key.value(), value))
267    }
268}
269
270impl Iterator for VmMapIntoIter {
271    type Item = (Value, Value);
272
273    fn next(&mut self) -> Option<Self::Item> {
274        self.inner
275            .next()
276            .map(|(key, value)| (key.into_value(), value))
277    }
278}
279
280fn hash_map_key(value: &Value, state: &mut impl Hasher) {
281    match value {
282        Value::Null => {
283            6u8.hash(state);
284        }
285        Value::Int(value) => {
286            0u8.hash(state);
287            value.hash(state);
288        }
289        Value::Float(value) => {
290            1u8.hash(state);
291            canonical_float_key_bits(*value).hash(state);
292        }
293        Value::Bool(value) => {
294            2u8.hash(state);
295            value.hash(state);
296        }
297        Value::String(value) => {
298            3u8.hash(state);
299            value.hash(state);
300        }
301        Value::Bytes(value) => {
302            4u8.hash(state);
303            value.hash(state);
304        }
305        Value::Array(values) => {
306            5u8.hash(state);
307            Arc::as_ptr(values).hash(state);
308        }
309        Value::Map(entries) => {
310            6u8.hash(state);
311            Arc::as_ptr(entries).hash(state);
312        }
313        Value::Callable(callable) => {
314            7u8.hash(state);
315            callable.prototype_id.hash(state);
316            callable.kind.hash(state);
317            callable.env.as_ref().map(Arc::as_ptr).hash(state);
318        }
319    }
320}
321
322fn map_key_eq(lhs: &Value, rhs: &Value) -> bool {
323    match (lhs, rhs) {
324        (Value::Null, Value::Null) => true,
325        (Value::Int(lhs), Value::Int(rhs)) => lhs == rhs,
326        (Value::Float(lhs), Value::Float(rhs)) => {
327            canonical_float_key_bits(*lhs) == canonical_float_key_bits(*rhs)
328        }
329        (Value::Bool(lhs), Value::Bool(rhs)) => lhs == rhs,
330        (Value::String(lhs), Value::String(rhs)) => lhs == rhs,
331        (Value::Bytes(lhs), Value::Bytes(rhs)) => lhs == rhs,
332        (Value::Array(lhs), Value::Array(rhs)) => Arc::ptr_eq(lhs, rhs),
333        (Value::Map(lhs), Value::Map(rhs)) => Arc::ptr_eq(lhs, rhs),
334        (Value::Callable(lhs), Value::Callable(rhs)) => callable_value_eq(lhs, rhs),
335        _ => false,
336    }
337}
338
339/// Hash a value structurally for VM-internal cache keys.
340///
341/// The hasher itself is a small deterministic 64-bit FNV-1a-style accumulator.
342/// Arrays hash recursively in order and maps hash recursively without caring
343/// about entry order, so the result is stable across allocations.
344#[allow(dead_code)]
345pub(crate) fn hash_value(value: &Value, state: &mut impl Hasher) {
346    match value {
347        Value::Null => {
348            6u8.hash(state);
349        }
350        Value::Int(value) => {
351            0u8.hash(state);
352            value.hash(state);
353        }
354        Value::Float(value) => {
355            1u8.hash(state);
356            canonical_float_key_bits(*value).hash(state);
357        }
358        Value::Bool(value) => {
359            2u8.hash(state);
360            value.hash(state);
361        }
362        Value::String(value) => {
363            3u8.hash(state);
364            value.hash(state);
365        }
366        Value::Bytes(value) => {
367            4u8.hash(state);
368            value.hash(state);
369        }
370        Value::Array(values) => {
371            5u8.hash(state);
372            values.len().hash(state);
373            for value in values.iter() {
374                hash_value(value, state);
375            }
376        }
377        Value::Map(entries) => {
378            6u8.hash(state);
379            entries.len().hash(state);
380            let mut entry_hashes = entries
381                .iter()
382                .map(|(key, value)| {
383                    let mut entry_hasher = StableHasher::default();
384                    hash_value(key, &mut entry_hasher);
385                    hash_value(value, &mut entry_hasher);
386                    entry_hasher.finish()
387                })
388                .collect::<Vec<_>>();
389            entry_hashes.sort_unstable();
390            for entry_hash in entry_hashes {
391                entry_hash.hash(state);
392            }
393        }
394        Value::Callable(callable) => {
395            7u8.hash(state);
396            callable.prototype_id.hash(state);
397            callable.kind.hash(state);
398            callable.env.as_ref().map(Arc::as_ptr).hash(state);
399        }
400    }
401}
402
403fn canonical_float_key_bits(value: f64) -> u64 {
404    if value == 0.0 {
405        0.0f64.to_bits()
406    } else {
407        value.to_bits()
408    }
409}
410
411#[derive(Clone, Debug)]
412pub enum Value {
413    Null,
414    Int(i64),
415    Float(f64),
416    Bool(bool),
417    String(SharedString),
418    Bytes(SharedBytes),
419    Array(SharedArray),
420    Map(SharedMap),
421    Callable(SharedCallable),
422}
423
424#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
425#[repr(u8)]
426pub enum ValueType {
427    Unknown = 0,
428    Null = 1,
429    Int = 2,
430    Float = 3,
431    Bool = 4,
432    String = 5,
433    Bytes = 6,
434    Array = 7,
435    Map = 8,
436    Callable = 9,
437}
438
439#[derive(Clone, Debug, Default, PartialEq, Eq)]
440pub struct TypeMap {
441    pub strict_types: bool,
442    pub local_types: Vec<ValueType>,
443    pub local_schemas: Vec<Option<TypeSchema>>,
444    pub callable_slots: Vec<bool>,
445    pub optional_slots: Vec<bool>,
446    pub operand_types: HashMap<usize, (ValueType, ValueType)>,
447}
448
449impl Value {
450    pub fn string(value: impl Into<String>) -> Self {
451        Self::String(Arc::new(value.into()))
452    }
453
454    pub fn array(values: Vec<Value>) -> Self {
455        Self::Array(Arc::new(values))
456    }
457
458    pub fn bytes(value: impl Into<Vec<u8>>) -> Self {
459        Self::Bytes(Arc::new(value.into()))
460    }
461
462    pub fn map(entries: Vec<(Value, Value)>) -> Self {
463        Self::Map(Arc::new(VmMap::from(entries)))
464    }
465
466    pub fn into_owned_string(self) -> Result<String, Self> {
467        match self {
468            Self::String(value) => Ok(unwrap_or_clone_shared(value)),
469            other => Err(other),
470        }
471    }
472
473    pub fn into_owned_array(self) -> Result<Vec<Value>, Self> {
474        match self {
475            Self::Array(values) => Ok(unwrap_or_clone_shared(values)),
476            other => Err(other),
477        }
478    }
479
480    pub fn into_owned_bytes(self) -> Result<Vec<u8>, Self> {
481        match self {
482            Self::Bytes(value) => Ok(unwrap_or_clone_shared(value)),
483            other => Err(other),
484        }
485    }
486
487    pub fn into_owned_map(self) -> Result<VmMap, Self> {
488        match self {
489            Self::Map(entries) => Ok(unwrap_or_clone_shared(entries)),
490            other => Err(other),
491        }
492    }
493}
494
495pub(crate) fn unwrap_or_clone_shared<T: Clone>(value: Arc<T>) -> T {
496    match Arc::try_unwrap(value) {
497        Ok(inner) => inner,
498        Err(shared) => (*shared).clone(),
499    }
500}
501
502impl PartialEq for Value {
503    fn eq(&self, other: &Self) -> bool {
504        match (self, other) {
505            (Self::Null, Self::Null) => true,
506            (Self::Int(lhs), Self::Int(rhs)) => lhs == rhs,
507            (Self::Float(lhs), Self::Float(rhs)) => lhs == rhs,
508            (Self::Bool(lhs), Self::Bool(rhs)) => lhs == rhs,
509            (Self::String(lhs), Self::String(rhs)) => lhs == rhs,
510            (Self::Bytes(lhs), Self::Bytes(rhs)) => lhs == rhs,
511            (Self::Array(lhs), Self::Array(rhs)) => lhs == rhs,
512            (Self::Map(lhs), Self::Map(rhs)) => lhs == rhs,
513            (Self::Callable(lhs), Self::Callable(rhs)) => callable_value_eq(lhs, rhs),
514            _ => false,
515        }
516    }
517}
518
519fn callable_value_eq(lhs: &CallableValue, rhs: &CallableValue) -> bool {
520    if lhs.prototype_id != rhs.prototype_id || lhs.kind != rhs.kind {
521        return false;
522    }
523    match (&lhs.env, &rhs.env) {
524        (None, None) => true,
525        (Some(lhs), Some(rhs)) => Arc::ptr_eq(lhs, rhs),
526        _ => false,
527    }
528}
529
530#[derive(Clone, Debug, PartialEq, Eq, Hash)]
531pub struct HostImport {
532    pub name: String,
533    pub arity: u8,
534    pub return_type: ValueType,
535}
536
537#[allow(dead_code)]
538#[derive(Debug)]
539pub(crate) struct DecodedInstructionData {
540    pub(crate) ldc_values: Box<[Option<Value>]>,
541    pub(crate) jump_targets: Box<[Option<usize>]>,
542    pub(crate) valid_jump_targets: Box<[bool]>,
543    pub(crate) local_indices: Box<[Option<u8>]>,
544}
545
546impl DecodedInstructionData {
547    fn build(program: &Program) -> Self {
548        let mut ldc_values = vec![None; program.code.len()];
549        let mut jump_targets = vec![None; program.code.len()];
550        let mut valid_jump_targets = vec![false; program.code.len()];
551        let mut local_indices = vec![None; program.code.len()];
552        let mut ip = 0usize;
553        while ip < program.code.len() {
554            let opcode = match OpCode::try_from(program.code[ip]) {
555                Ok(opcode) => opcode,
556                Err(_) => break,
557            };
558            match opcode {
559                OpCode::Ldc => {
560                    if let Some(raw_index) = read_u32_at(&program.code, ip + 1)
561                        && let Some(value) = program.constants.get(raw_index as usize)
562                    {
563                        ldc_values[ip] = Some(value.clone());
564                    }
565                }
566                OpCode::Br | OpCode::Brfalse => {
567                    if let Some(target) =
568                        read_u32_at(&program.code, ip + 1).map(|target| target as usize)
569                    {
570                        jump_targets[ip] = Some(target);
571                        if target >= program.code.len() {
572                            ip = ip.saturating_add(1 + opcode.operand_len());
573                            continue;
574                        }
575                        let source_owner = program
576                            .function_regions
577                            .iter()
578                            .find(|region| {
579                                region.start_ip as usize <= ip && ip < region.end_ip as usize
580                            })
581                            .and_then(|region| region.prototype_id);
582                        let target_owner = program
583                            .function_regions
584                            .iter()
585                            .find(|region| {
586                                region.start_ip as usize <= target
587                                    && target < region.end_ip as usize
588                            })
589                            .and_then(|region| region.prototype_id);
590                        if source_owner == target_owner {
591                            valid_jump_targets[ip] = true;
592                        }
593                    }
594                }
595                OpCode::Ldloc | OpCode::Stloc => {
596                    if let Some(index) = program.code.get(ip + 1).copied() {
597                        local_indices[ip] = Some(index);
598                    }
599                }
600                _ => {}
601            }
602            ip = ip.saturating_add(1 + opcode.operand_len());
603        }
604        Self {
605            ldc_values: ldc_values.into_boxed_slice(),
606            jump_targets: jump_targets.into_boxed_slice(),
607            valid_jump_targets: valid_jump_targets.into_boxed_slice(),
608            local_indices: local_indices.into_boxed_slice(),
609        }
610    }
611}
612
613#[derive(Clone, Debug)]
614pub struct Program {
615    pub constants: Vec<Value>,
616    pub code: Vec<u8>,
617    pub local_count: usize,
618    pub imports: Vec<HostImport>,
619    pub debug: Option<crate::debug_info::DebugInfo>,
620    pub type_map: Option<TypeMap>,
621    pub script_functions: Vec<ScriptFunction>,
622    pub callable_prototypes: Vec<CallablePrototype>,
623    pub function_regions: Vec<FunctionRegion>,
624    pub root_callable_bindings: Vec<RootCallableBinding>,
625    pub exported_callables: Vec<ExportedCallable>,
626    #[allow(dead_code)]
627    decoded_instruction_data_cache: Arc<OnceLock<Arc<DecodedInstructionData>>>,
628    operand_type_hints_cache: Arc<OnceLock<Option<Arc<[u8]>>>>,
629}
630
631impl Program {
632    pub fn new(constants: Vec<Value>, code: Vec<u8>) -> Self {
633        let local_count = infer_local_count_from_code(&code);
634        Self {
635            constants,
636            code,
637            local_count,
638            imports: Vec::new(),
639            debug: None,
640            type_map: None,
641            script_functions: Vec::new(),
642            callable_prototypes: Vec::new(),
643            function_regions: Vec::new(),
644            root_callable_bindings: Vec::new(),
645            exported_callables: Vec::new(),
646            decoded_instruction_data_cache: Arc::new(OnceLock::new()),
647            operand_type_hints_cache: Arc::new(OnceLock::new()),
648        }
649    }
650
651    pub fn with_debug(
652        constants: Vec<Value>,
653        code: Vec<u8>,
654        debug: Option<crate::debug_info::DebugInfo>,
655    ) -> Self {
656        let local_count = infer_local_count_from_code(&code);
657        Self {
658            constants,
659            code,
660            local_count,
661            imports: Vec::new(),
662            debug,
663            type_map: None,
664            script_functions: Vec::new(),
665            callable_prototypes: Vec::new(),
666            function_regions: Vec::new(),
667            root_callable_bindings: Vec::new(),
668            exported_callables: Vec::new(),
669            decoded_instruction_data_cache: Arc::new(OnceLock::new()),
670            operand_type_hints_cache: Arc::new(OnceLock::new()),
671        }
672    }
673
674    pub fn with_imports_and_debug(
675        constants: Vec<Value>,
676        code: Vec<u8>,
677        imports: Vec<HostImport>,
678        debug: Option<crate::debug_info::DebugInfo>,
679    ) -> Self {
680        let local_count = infer_local_count_from_code(&code);
681        Self {
682            constants,
683            code,
684            local_count,
685            imports,
686            debug,
687            type_map: None,
688            script_functions: Vec::new(),
689            callable_prototypes: Vec::new(),
690            function_regions: Vec::new(),
691            root_callable_bindings: Vec::new(),
692            exported_callables: Vec::new(),
693            decoded_instruction_data_cache: Arc::new(OnceLock::new()),
694            operand_type_hints_cache: Arc::new(OnceLock::new()),
695        }
696    }
697
698    pub fn with_local_count(mut self, local_count: usize) -> Self {
699        self.local_count = local_count;
700        self
701    }
702
703    pub fn with_type_map(mut self, type_map: TypeMap) -> Self {
704        self.type_map = Some(type_map);
705        self.operand_type_hints_cache = Arc::new(OnceLock::new());
706        self
707    }
708
709    pub fn with_callable_metadata(
710        mut self,
711        script_functions: Vec<ScriptFunction>,
712        callable_prototypes: Vec<CallablePrototype>,
713        function_regions: Vec<FunctionRegion>,
714        root_callable_bindings: Vec<RootCallableBinding>,
715    ) -> Self {
716        self.script_functions = script_functions;
717        self.callable_prototypes = callable_prototypes;
718        self.function_regions = function_regions;
719        self.root_callable_bindings = root_callable_bindings;
720        self
721    }
722
723    pub fn with_exported_callables(mut self, exported_callables: Vec<ExportedCallable>) -> Self {
724        self.exported_callables = exported_callables;
725        self
726    }
727
728    #[allow(dead_code)]
729    pub(crate) fn shared_decoded_instruction_data(&self) -> Arc<DecodedInstructionData> {
730        Arc::clone(
731            self.decoded_instruction_data_cache
732                .get_or_init(|| Arc::new(DecodedInstructionData::build(self))),
733        )
734    }
735
736    #[allow(dead_code)]
737    pub(crate) fn shared_operand_type_hints(&self) -> Option<Arc<[u8]>> {
738        self.operand_type_hints_cache
739            .get_or_init(|| build_operand_type_hints(self.code.len(), self.type_map.as_ref()))
740            .clone()
741    }
742}
743
744#[allow(dead_code)]
745fn build_operand_type_hints(code_len: usize, type_map: Option<&TypeMap>) -> Option<Arc<[u8]>> {
746    let type_map = type_map?;
747    if type_map.operand_types.is_empty() {
748        return None;
749    }
750
751    let mut hints = vec![0u8; code_len];
752    for (offset, (lhs, rhs)) in &type_map.operand_types {
753        let Some(entry) = hints.get_mut(*offset) else {
754            continue;
755        };
756        *entry = (*lhs as u8) | ((*rhs as u8) << 4);
757    }
758    Some(Arc::from(hints.into_boxed_slice()))
759}
760
761#[allow(dead_code)]
762fn read_u32_at(code: &[u8], offset: usize) -> Option<u32> {
763    let bytes = code.get(offset..offset + 4)?;
764    Some(u32::from_le_bytes(bytes.try_into().ok()?))
765}
766
767fn infer_local_count_from_code(code: &[u8]) -> usize {
768    let mut ip = 0usize;
769    let mut max_local_index: Option<u8> = None;
770
771    while let Some(&opcode) = code.get(ip) {
772        ip += 1;
773        let Ok(opcode) = OpCode::try_from(opcode) else {
774            break;
775        };
776        let operand_len = opcode.operand_len();
777        if ip + operand_len > code.len() {
778            break;
779        }
780        match opcode {
781            OpCode::Ldloc | OpCode::Stloc => {
782                let index = code[ip];
783                max_local_index = Some(max_local_index.map_or(index, |prev| prev.max(index)));
784            }
785            _ => {}
786        }
787        ip += operand_len;
788    }
789
790    max_local_index.map_or(0, |index| index as usize + 1)
791}
792
793#[derive(Clone, Copy, Debug, PartialEq, Eq)]
794#[repr(u8)]
795pub enum OpCode {
796    Nop = 0x00,
797    Ret = 0x01,
798    Ldc = 0x02,
799    Add = 0x03,
800    Sub = 0x04,
801    Mul = 0x05,
802    Div = 0x06,
803    Neg = 0x07,
804    Ceq = 0x08,
805    Clt = 0x09,
806    Cgt = 0x0A,
807    Br = 0x0B,
808    Brfalse = 0x0C,
809    Pop = 0x0D,
810    Dup = 0x0E,
811    Ldloc = 0x0F,
812    Stloc = 0x10,
813    Call = 0x11,
814    Shl = 0x12,
815    Shr = 0x13,
816    Mod = 0x14,
817    And = 0x15,
818    Or = 0x16,
819    Not = 0x17,
820    Lshr = 0x18,
821    CallValue = 0x19,
822}
823
824impl TryFrom<u8> for OpCode {
825    type Error = ();
826
827    fn try_from(value: u8) -> Result<Self, Self::Error> {
828        match value {
829            x if x == Self::Nop as u8 => Ok(Self::Nop),
830            x if x == Self::Ret as u8 => Ok(Self::Ret),
831            x if x == Self::Ldc as u8 => Ok(Self::Ldc),
832            x if x == Self::Add as u8 => Ok(Self::Add),
833            x if x == Self::Sub as u8 => Ok(Self::Sub),
834            x if x == Self::Mul as u8 => Ok(Self::Mul),
835            x if x == Self::Div as u8 => Ok(Self::Div),
836            x if x == Self::Neg as u8 => Ok(Self::Neg),
837            x if x == Self::Ceq as u8 => Ok(Self::Ceq),
838            x if x == Self::Clt as u8 => Ok(Self::Clt),
839            x if x == Self::Cgt as u8 => Ok(Self::Cgt),
840            x if x == Self::Br as u8 => Ok(Self::Br),
841            x if x == Self::Brfalse as u8 => Ok(Self::Brfalse),
842            x if x == Self::Pop as u8 => Ok(Self::Pop),
843            x if x == Self::Dup as u8 => Ok(Self::Dup),
844            x if x == Self::Ldloc as u8 => Ok(Self::Ldloc),
845            x if x == Self::Stloc as u8 => Ok(Self::Stloc),
846            x if x == Self::Call as u8 => Ok(Self::Call),
847            x if x == Self::Shl as u8 => Ok(Self::Shl),
848            x if x == Self::Shr as u8 => Ok(Self::Shr),
849            x if x == Self::Mod as u8 => Ok(Self::Mod),
850            x if x == Self::And as u8 => Ok(Self::And),
851            x if x == Self::Or as u8 => Ok(Self::Or),
852            x if x == Self::Not as u8 => Ok(Self::Not),
853            x if x == Self::Lshr as u8 => Ok(Self::Lshr),
854            x if x == Self::CallValue as u8 => Ok(Self::CallValue),
855            _ => Err(()),
856        }
857    }
858}
859
860impl OpCode {
861    pub const fn operand_len(self) -> usize {
862        match self {
863            Self::Nop
864            | Self::Ret
865            | Self::Add
866            | Self::Sub
867            | Self::Mul
868            | Self::Div
869            | Self::Neg
870            | Self::Ceq
871            | Self::Clt
872            | Self::Cgt
873            | Self::Pop
874            | Self::Dup
875            | Self::Shl
876            | Self::Shr
877            | Self::Mod
878            | Self::And
879            | Self::Or
880            | Self::Not
881            | Self::Lshr => 0,
882            Self::Ldc | Self::Br | Self::Brfalse => 4,
883            Self::Ldloc | Self::Stloc | Self::CallValue => 1,
884            Self::Call => 3,
885        }
886    }
887
888    pub fn mnemonic(self) -> &'static str {
889        match self {
890            OpCode::Nop => "nop",
891            OpCode::Ret => "ret",
892            OpCode::Ldc => "ldc",
893            OpCode::Add => "add",
894            OpCode::Sub => "sub",
895            OpCode::Mul => "mul",
896            OpCode::Div => "div",
897            OpCode::Neg => "neg",
898            OpCode::Ceq => "ceq",
899            OpCode::Clt => "clt",
900            OpCode::Cgt => "cgt",
901            OpCode::Br => "br",
902            OpCode::Brfalse => "brfalse",
903            OpCode::Pop => "pop",
904            OpCode::Dup => "dup",
905            OpCode::Ldloc => "ldloc",
906            OpCode::Stloc => "stloc",
907            OpCode::Call => "call",
908            OpCode::Shl => "shl",
909            OpCode::Shr => "shr",
910            OpCode::Mod => "mod",
911            OpCode::And => "and",
912            OpCode::Or => "or",
913            OpCode::Not => "not",
914            OpCode::Lshr => "lshr",
915            Self::CallValue => "callvalue",
916        }
917    }
918
919    pub fn parse_mnemonic(op: &str) -> Option<Self> {
920        match op {
921            "nop" => Some(OpCode::Nop),
922            "ret" => Some(OpCode::Ret),
923            "ldc" => Some(OpCode::Ldc),
924            "add" => Some(OpCode::Add),
925            "sub" => Some(OpCode::Sub),
926            "mul" => Some(OpCode::Mul),
927            "div" => Some(OpCode::Div),
928            "neg" => Some(OpCode::Neg),
929            "ceq" => Some(OpCode::Ceq),
930            "clt" => Some(OpCode::Clt),
931            "cgt" => Some(OpCode::Cgt),
932            "br" => Some(OpCode::Br),
933            "brfalse" => Some(OpCode::Brfalse),
934            "pop" => Some(OpCode::Pop),
935            "dup" => Some(OpCode::Dup),
936            "ldloc" => Some(OpCode::Ldloc),
937            "stloc" => Some(OpCode::Stloc),
938            "call" => Some(OpCode::Call),
939            "shl" => Some(OpCode::Shl),
940            "shr" => Some(OpCode::Shr),
941            "mod" => Some(OpCode::Mod),
942            "and" => Some(OpCode::And),
943            "or" => Some(OpCode::Or),
944            "not" => Some(OpCode::Not),
945            "lshr" => Some(OpCode::Lshr),
946            "callvalue" => Some(OpCode::CallValue),
947            _ => None,
948        }
949    }
950}
951
952#[cfg(test)]
953mod tests {
954    use super::*;
955
956    #[test]
957    fn heap_value_clone_shares_backing() {
958        let string = Value::string("hello");
959        let string_clone = string.clone();
960        let (Value::String(lhs), Value::String(rhs)) = (&string, &string_clone) else {
961            panic!("expected string values");
962        };
963        assert!(Arc::ptr_eq(lhs, rhs));
964
965        let array = Value::array(vec![Value::Int(1), Value::Int(2)]);
966        let array_clone = array.clone();
967        let (Value::Array(lhs), Value::Array(rhs)) = (&array, &array_clone) else {
968            panic!("expected array values");
969        };
970        assert!(Arc::ptr_eq(lhs, rhs));
971
972        let bytes = Value::bytes([1u8, 2, 3]);
973        let bytes_clone = bytes.clone();
974        let (Value::Bytes(lhs), Value::Bytes(rhs)) = (&bytes, &bytes_clone) else {
975            panic!("expected bytes values");
976        };
977        assert!(Arc::ptr_eq(lhs, rhs));
978
979        let map = Value::map(vec![(Value::string("k"), Value::Int(9))]);
980        let map_clone = map.clone();
981        let (Value::Map(lhs), Value::Map(rhs)) = (&map, &map_clone) else {
982            panic!("expected map values");
983        };
984        assert!(Arc::ptr_eq(lhs, rhs));
985    }
986
987    #[test]
988    fn bytes_map_key_uses_value_lookup() {
989        let key = Value::bytes([0x01u8, 0x02, 0x03]);
990        let expected = Value::Bool(true);
991
992        let mut map = VmMap::new();
993        map.insert(key, expected.clone());
994
995        assert_eq!(
996            map.get(&Value::bytes([0x01u8, 0x02, 0x03])),
997            Some(&expected)
998        );
999        assert_eq!(map.get(&Value::bytes([0x01u8, 0x02, 0x04])), None);
1000    }
1001
1002    #[test]
1003    fn composite_map_key_remains_stable_after_alias_detach() {
1004        let source_key = Value::array(vec![Value::Int(1), Value::Int(2)]);
1005        let alias = source_key.clone();
1006        let lookup_key = source_key.clone();
1007        let expected = Value::string("kept");
1008
1009        let mut map = VmMap::new();
1010        map.insert(source_key, expected.clone());
1011
1012        let mutated_alias = match alias {
1013            Value::Array(values) => {
1014                let mut owned = unwrap_or_clone_shared(values);
1015                owned[0] = Value::Int(9);
1016                Value::array(owned)
1017            }
1018            other => panic!("expected array alias, got {other:?}"),
1019        };
1020
1021        assert_eq!(map.get(&lookup_key), Some(&expected));
1022        assert_eq!(
1023            map.get(&Value::array(vec![Value::Int(1), Value::Int(2)])),
1024            None
1025        );
1026        assert_eq!(map.get(&mutated_alias), None);
1027    }
1028
1029    #[test]
1030    fn nested_map_keys_use_identity_lookup() {
1031        let nested_key = Value::map(vec![
1032            (Value::string("a"), Value::Int(1)),
1033            (Value::string("b"), Value::Int(2)),
1034        ]);
1035        let lookup_key = nested_key.clone();
1036        let structural_peer = Value::map(vec![
1037            (Value::string("b"), Value::Int(2)),
1038            (Value::string("a"), Value::Int(1)),
1039        ]);
1040        let expected = Value::Bool(true);
1041
1042        let mut map = VmMap::new();
1043        map.insert(nested_key, expected.clone());
1044
1045        assert_eq!(map.get(&lookup_key), Some(&expected));
1046        assert_eq!(map.get(&structural_peer), None);
1047    }
1048
1049    #[test]
1050    fn vm_map_cached_len_stays_in_sync() {
1051        let mut map = VmMap::new();
1052        assert_eq!(map.len(), 0);
1053
1054        assert_eq!(map.insert(Value::string("a"), Value::Int(1)), None);
1055        assert_eq!(map.len(), 1);
1056
1057        assert_eq!(
1058            map.insert(Value::string("a"), Value::Int(2)),
1059            Some(Value::Int(1))
1060        );
1061        assert_eq!(map.len(), 1);
1062
1063        assert_eq!(map.insert(Value::string("b"), Value::Int(3)), None);
1064        assert_eq!(map.len(), 2);
1065
1066        assert_eq!(map.remove(&Value::string("missing")), None);
1067        assert_eq!(map.len(), 2);
1068
1069        assert_eq!(map.remove(&Value::string("a")), Some(Value::Int(2)));
1070        assert_eq!(map.len(), 1);
1071    }
1072}
vm/bytecode.rs

vm/
bytecode.rs
