compiler/
snapshot.rs

1//! Binary serialization for compiled [`Bytecode`] (`.mbc` files).
2//!
3//! Format and safety model: docs/bytecode-snapshot-design.md. This module is
4//! defense layer L1: structural validation plus a linear scan over every
5//! instruction stream, so bytecode that reaches the VM never indexes out of
6//! range and never jumps into the middle of an instruction. Stack discipline
7//! and runtime types are deliberately left to the VM's own checks (L3).
8
9use std::collections::HashMap;
10use std::convert::{TryFrom, TryInto};
11use std::rc::Rc;
12
13use object::builtins::BuiltIns;
14use object::{CompiledFunction, Object};
15use parser::lexer::token::Span;
16use strum::IntoEnumIterator;
17
18use crate::compiler::{Bytecode, DebugInfo, PcSpan};
19use crate::op_code::{read_operands, Instructions, Opcode, DEFINITIONS};
20
21/// Bump when the container layout changes (header, sections, tags, varint
22/// rules). Bytecode ABI changes are covered by the fingerprint instead.
23pub const FORMAT_VERSION: u8 = 1;
24
25pub(crate) const MAGIC: [u8; 4] = *b"MBC\0";
26pub(crate) const FLAG_HAS_DEBUG_INFO: u8 = 0b0000_0001;
27
28pub(crate) const TAG_INTEGER: u8 = 1;
29pub(crate) const TAG_STRING: u8 = 2;
30pub(crate) const TAG_FUNCTION: u8 = 3;
31
32#[derive(Debug, PartialEq)]
33pub enum SnapshotWriteError {
34    /// `Bytecode.constants` is a public field, so the writer cannot assume it
35    /// only holds the three variants the compiler emits.
36    UnsupportedConstant { index: usize, kind: String },
37}
38
39#[derive(Debug, PartialEq)]
40pub enum SnapshotError {
41    BadMagic,
42    UnsupportedVersion {
43        found: u8,
44        expected: u8,
45    },
46    AbiFingerprintMismatch {
47        found: u32,
48        expected: u32,
49    },
50    UnexpectedEof,
51    InvalidLeb128,
52    IntegerOverflow,
53    /// A declared size exceeds the remaining input bytes.
54    LimitExceeded,
55    BadTag(u8),
56    BadUtf8,
57    BadFlags(u8),
58    TrailingBytes,
59    /// Instruction-stream validation failure, with stream and offset.
60    InvalidInstruction(String),
61    DuplicateDebugEntry(usize),
62    DebugPcNotIncreasing {
63        pc: usize,
64    },
65    /// The debug entry's constant index does not name a function constant.
66    DebugIndexNotFunction(usize),
67    DebugPcOutOfRange {
68        pc: usize,
69        len: usize,
70    },
71}
72
73lazy_static! {
74    static ref ABI_FINGERPRINT: u32 = compute_abi_fingerprint();
75}
76
77/// Fingerprint of the bytecode ABI: every opcode (discriminant, name,
78/// operand widths, in enum order) and every builtin (index, name, in table
79/// order — `OpGetBuiltin` operands are indexes into that table). This is a
80/// compatibility sentinel, not integrity protection: safety against forged
81/// headers rests on the L1/L2/L3 checks, not on this value.
82pub fn bytecode_abi_fingerprint() -> u32 {
83    *ABI_FINGERPRINT
84}
85
86fn compute_abi_fingerprint() -> u32 {
87    let mut hash = Fnv1a::new();
88    for opcode in Opcode::iter() {
89        let definition = DEFINITIONS
90            .get(&opcode)
91            .unwrap_or_else(|| panic!("opcode {:?} missing from DEFINITIONS", opcode));
92        hash.absorb_u64(opcode as u64);
93        hash.absorb_bytes(definition.name().as_bytes());
94        for &width in definition.operand_widths() {
95            hash.absorb_u64(width as u64);
96        }
97    }
98    for (index, builtin) in BuiltIns.iter().enumerate() {
99        hash.absorb_u64(index as u64);
100        hash.absorb_bytes(builtin.name.as_bytes());
101    }
102    hash.finish()
103}
104
105/// FNV-1a, 32-bit.
106struct Fnv1a(u32);
107
108impl Fnv1a {
109    fn new() -> Self {
110        Fnv1a(0x811c_9dc5)
111    }
112
113    fn write(&mut self, bytes: &[u8]) {
114        for &byte in bytes {
115            self.0 ^= u32::from(byte);
116            self.0 = self.0.wrapping_mul(0x0100_0193);
117        }
118    }
119
120    /// Absorb one field as (ULEB length, content) so adjacent fields cannot
121    /// be reinterpreted across their boundary.
122    fn absorb_bytes(&mut self, bytes: &[u8]) {
123        let mut length = Vec::new();
124        write_uleb128(&mut length, bytes.len() as u64);
125        self.write(&length);
126        self.write(bytes);
127    }
128
129    fn absorb_u64(&mut self, value: u64) {
130        let mut encoded = Vec::new();
131        write_uleb128(&mut encoded, value);
132        self.absorb_bytes(&encoded);
133    }
134
135    fn finish(&self) -> u32 {
136        self.0
137    }
138}
139
140/// Serialize `bytecode` into the `.mbc` container. With `strip_debug` the
141/// debug section is omitted entirely (flags bit 0 cleared).
142///
143/// Output is deterministic: `function_debug_info` entries are written in
144/// ascending constant-index order.
145pub fn write_bytecode(
146    bytecode: &Bytecode,
147    strip_debug: bool,
148) -> Result<Vec<u8>, SnapshotWriteError> {
149    let mut out = Vec::new();
150    out.extend_from_slice(&MAGIC);
151    out.push(FORMAT_VERSION);
152    out.extend_from_slice(&bytecode_abi_fingerprint().to_le_bytes());
153    out.push(if strip_debug { 0 } else { FLAG_HAS_DEBUG_INFO });
154
155    write_bytes(&mut out, &bytecode.instructions.data);
156    write_uleb128(&mut out, bytecode.constants.len() as u64);
157    for (index, constant) in bytecode.constants.iter().enumerate() {
158        write_constant(&mut out, index, constant)?;
159    }
160
161    if !strip_debug {
162        write_debug_info(&mut out, &bytecode.debug_info);
163        let mut entries: Vec<_> = bytecode.function_debug_info.iter().collect();
164        entries.sort_by_key(|(index, _)| **index);
165        write_uleb128(&mut out, entries.len() as u64);
166        for (index, debug_info) in entries {
167            write_uleb128(&mut out, *index as u64);
168            write_debug_info(&mut out, debug_info);
169        }
170    }
171    Ok(out)
172}
173
174fn write_constant(
175    out: &mut Vec<u8>,
176    index: usize,
177    constant: &Object,
178) -> Result<(), SnapshotWriteError> {
179    match constant {
180        Object::Integer(value) => {
181            out.push(TAG_INTEGER);
182            write_sleb128(out, *value);
183        }
184        Object::String(value) => {
185            out.push(TAG_STRING);
186            write_string(out, value);
187        }
188        Object::CompiledFunction(function) => {
189            out.push(TAG_FUNCTION);
190            write_string(out, &function.name);
191            write_uleb128(out, function.num_locals as u64);
192            write_uleb128(out, function.num_parameters as u64);
193            write_bytes(out, &function.instructions);
194        }
195        other => {
196            return Err(SnapshotWriteError::UnsupportedConstant {
197                index,
198                kind: object_kind(other).to_string(),
199            })
200        }
201    }
202    Ok(())
203}
204
205fn write_debug_info(out: &mut Vec<u8>, debug_info: &DebugInfo) {
206    write_uleb128(out, debug_info.pc_spans.len() as u64);
207    for pc_span in &debug_info.pc_spans {
208        write_uleb128(out, pc_span.pc as u64);
209        write_uleb128(out, pc_span.span.start as u64);
210        write_uleb128(out, pc_span.span.end as u64);
211    }
212}
213
214fn write_string(out: &mut Vec<u8>, value: &str) {
215    write_bytes(out, value.as_bytes());
216}
217
218fn write_bytes(out: &mut Vec<u8>, bytes: &[u8]) {
219    write_uleb128(out, bytes.len() as u64);
220    out.extend_from_slice(bytes);
221}
222
223pub(crate) fn write_uleb128(out: &mut Vec<u8>, mut value: u64) {
224    loop {
225        let byte = (value & 0x7f) as u8;
226        value >>= 7;
227        if value == 0 {
228            out.push(byte);
229            return;
230        }
231        out.push(byte | 0x80);
232    }
233}
234
235pub(crate) fn write_sleb128(out: &mut Vec<u8>, mut value: i64) {
236    loop {
237        let byte = (value & 0x7f) as u8;
238        value >>= 7;
239        let sign_bit_clear = byte & 0x40 == 0;
240        if (value == 0 && sign_bit_clear) || (value == -1 && !sign_bit_clear) {
241            out.push(byte);
242            return;
243        }
244        out.push(byte | 0x80);
245    }
246}
247
248fn object_kind(object: &Object) -> &'static str {
249    match object {
250        Object::Integer(_) => "Integer",
251        Object::Boolean(_) => "Boolean",
252        Object::String(_) => "String",
253        Object::Array(_) => "Array",
254        Object::Hash(_) => "Hash",
255        Object::Null => "Null",
256        Object::ReturnValue(_) => "ReturnValue",
257        Object::Function(..) => "Function",
258        Object::Builtin(_) => "Builtin",
259        Object::Error(_) => "Error",
260        Object::CompiledFunction(_) => "CompiledFunction",
261        Object::ClosureObj(_) => "Closure",
262        Object::Class(_) => "Class",
263        Object::Instance(_) => "Instance",
264        Object::BoundMethod(_) => "BoundMethod",
265    }
266}
267
268/// Deserialize and validate an `.mbc` buffer. The input is untrusted: every
269/// malformed input returns `Err`, and anything returned `Ok` has passed the
270/// L1 checks (§6 of the design doc).
271pub fn read_bytecode(buf: &[u8]) -> Result<Bytecode, SnapshotError> {
272    let mut reader = Reader::new(buf);
273
274    let magic = reader.read_exact(MAGIC.len())?;
275    if magic != MAGIC {
276        return Err(SnapshotError::BadMagic);
277    }
278    let version = reader.read_u8()?;
279    if version != FORMAT_VERSION {
280        return Err(SnapshotError::UnsupportedVersion {
281            found: version,
282            expected: FORMAT_VERSION,
283        });
284    }
285    let found = u32::from_le_bytes(reader.read_exact(4)?.try_into().unwrap());
286    let expected = bytecode_abi_fingerprint();
287    if found != expected {
288        return Err(SnapshotError::AbiFingerprintMismatch {
289            found,
290            expected,
291        });
292    }
293    let flags = reader.read_u8()?;
294    if flags & !FLAG_HAS_DEBUG_INFO != 0 {
295        return Err(SnapshotError::BadFlags(flags));
296    }
297    let has_debug = flags & FLAG_HAS_DEBUG_INFO != 0;
298
299    let main_instructions = reader.read_length_prefixed_bytes()?.to_vec();
300    let constant_count = reader.read_count()?;
301    let mut constants: Vec<Rc<Object>> = Vec::with_capacity(constant_count);
302    for _ in 0..constant_count {
303        constants.push(Rc::new(read_constant(&mut reader)?));
304    }
305
306    let (debug_info, function_debug_info) = if has_debug {
307        read_debug_section(&mut reader, &constants, main_instructions.len())?
308    } else {
309        (DebugInfo::default(), HashMap::new())
310    };
311
312    if reader.remaining() != 0 {
313        return Err(SnapshotError::TrailingBytes);
314    }
315
316    validate_instruction_stream("main", &main_instructions, &constants)?;
317    for (index, constant) in constants.iter().enumerate() {
318        if let Object::CompiledFunction(function) = constant.as_ref() {
319            validate_instruction_stream(
320                &format!("constant {}", index),
321                &function.instructions,
322                &constants,
323            )?;
324        }
325    }
326
327    Ok(Bytecode {
328        instructions: Instructions {
329            data: main_instructions,
330        },
331        constants,
332        debug_info,
333        function_debug_info,
334    })
335}
336
337fn read_constant(reader: &mut Reader) -> Result<Object, SnapshotError> {
338    let tag = reader.read_u8()?;
339    match tag {
340        TAG_INTEGER => Ok(Object::Integer(reader.read_sleb128()?)),
341        TAG_STRING => Ok(Object::String(reader.read_string()?)),
342        TAG_FUNCTION => {
343            let name = reader.read_string()?;
344            let num_locals = reader.read_usize()?;
345            let num_parameters = reader.read_usize()?;
346            let instructions = reader.read_length_prefixed_bytes()?.to_vec();
347            Ok(Object::CompiledFunction(Rc::new(CompiledFunction {
348                name,
349                instructions,
350                num_locals,
351                num_parameters,
352            })))
353        }
354        other => Err(SnapshotError::BadTag(other)),
355    }
356}
357
358fn read_debug_section(
359    reader: &mut Reader,
360    constants: &[Rc<Object>],
361    main_len: usize,
362) -> Result<(DebugInfo, HashMap<usize, DebugInfo>), SnapshotError> {
363    let main_debug = read_debug_info(reader, main_len)?;
364    let entry_count = reader.read_count()?;
365    let mut function_debug_info = HashMap::with_capacity(entry_count);
366    for _ in 0..entry_count {
367        let constant_index = reader.read_usize()?;
368        let function_len = match constants.get(constant_index).map(Rc::as_ref) {
369            Some(Object::CompiledFunction(function)) => function.instructions.len(),
370            _ => return Err(SnapshotError::DebugIndexNotFunction(constant_index)),
371        };
372        let debug_info = read_debug_info(reader, function_len)?;
373        if function_debug_info
374            .insert(constant_index, debug_info)
375            .is_some()
376        {
377            return Err(SnapshotError::DuplicateDebugEntry(constant_index));
378        }
379    }
380    Ok((main_debug, function_debug_info))
381}
382
383fn read_debug_info(
384    reader: &mut Reader,
385    instruction_len: usize,
386) -> Result<DebugInfo, SnapshotError> {
387    let count = reader.read_count()?;
388    let mut pc_spans = Vec::with_capacity(count);
389    let mut previous: Option<usize> = None;
390    for _ in 0..count {
391        let pc = reader.read_usize()?;
392        if let Some(previous) = previous {
393            if pc <= previous {
394                return Err(SnapshotError::DebugPcNotIncreasing {
395                    pc,
396                });
397            }
398        }
399        if pc > instruction_len {
400            return Err(SnapshotError::DebugPcOutOfRange {
401                pc,
402                len: instruction_len,
403            });
404        }
405        let start = reader.read_usize()?;
406        let end = reader.read_usize()?;
407        pc_spans.push(PcSpan {
408            pc,
409            span: Span {
410                start,
411                end,
412            },
413        });
414        previous = Some(pc);
415    }
416    Ok(DebugInfo {
417        pc_spans,
418    })
419}
420
421/// L1 linear scan of one instruction stream (§6 of the design doc): every
422/// opcode is defined, operands are complete, jumps land on instruction
423/// boundaries (or one past the end), and index operands stay inside the
424/// constant pool / builtin table with the constant kind each opcode needs.
425///
426/// Deliberately not checked here: stack depth, operand runtime types,
427/// local/free index validity. Those depend on execution state and are the
428/// VM's defensive checks (L3).
429fn validate_instruction_stream(
430    stream: &str,
431    instructions: &[u8],
432    constants: &[Rc<Object>],
433) -> Result<(), SnapshotError> {
434    let len = instructions.len();
435    let mut is_boundary = vec![false; len + 1];
436    let mut jumps: Vec<(usize, usize)> = Vec::new();
437    let mut offset = 0;
438    while offset < len {
439        is_boundary[offset] = true;
440        let byte = instructions[offset];
441        let opcode = Opcode::from_repr(byte)
442            .ok_or_else(|| invalid(stream, offset, format!("unknown opcode 0x{:02x}", byte)))?;
443        let definition = DEFINITIONS.get(&opcode).expect("missing opcode definition");
444        let operand_len: usize = definition
445            .operand_widths()
446            .iter()
447            .map(|w| *w as usize)
448            .sum();
449        if offset + 1 + operand_len > len {
450            return Err(invalid(
451                stream,
452                offset,
453                format!("truncated operands for {}", definition.name()),
454            ));
455        }
456        let (operands, _) = read_operands(definition, &instructions[offset + 1..]);
457        match opcode {
458            Opcode::OpJump | Opcode::OpJumpNotTruthy => jumps.push((offset, operands[0])),
459            Opcode::OpConst => {
460                if operands[0] >= constants.len() {
461                    return Err(invalid(
462                        stream,
463                        offset,
464                        format!("constant index {} out of range", operands[0]),
465                    ));
466                }
467            }
468            Opcode::OpClosure => {
469                let index = operands[0];
470                if !matches!(
471                    constants.get(index).map(Rc::as_ref),
472                    Some(Object::CompiledFunction(_))
473                ) {
474                    return Err(invalid(
475                        stream,
476                        offset,
477                        format!("OpClosure needs a function constant at index {}", index),
478                    ));
479                }
480            }
481            Opcode::OpClass | Opcode::OpMethod | Opcode::OpGetProperty | Opcode::OpSetProperty => {
482                let index = operands[0];
483                if !matches!(constants.get(index).map(Rc::as_ref), Some(Object::String(_))) {
484                    return Err(invalid(
485                        stream,
486                        offset,
487                        format!("{} needs a string constant at index {}", definition.name(), index),
488                    ));
489                }
490            }
491            Opcode::OpGetBuiltin => {
492                if operands[0] >= BuiltIns.len() {
493                    return Err(invalid(
494                        stream,
495                        offset,
496                        format!("builtin index {} out of range", operands[0]),
497                    ));
498                }
499            }
500            Opcode::OpHash if operands[0] % 2 != 0 => {
501                return Err(invalid(
502                    stream,
503                    offset,
504                    format!("OpHash needs an even element count, got {}", operands[0]),
505                ));
506            }
507            _ => {}
508        }
509        offset += 1 + operand_len;
510    }
511    is_boundary[len] = true;
512    for (offset, target) in jumps {
513        if target > len || !is_boundary[target] {
514            return Err(invalid(
515                stream,
516                offset,
517                format!("jump target {} is not an instruction boundary", target),
518            ));
519        }
520    }
521    Ok(())
522}
523
524fn invalid(stream: &str, offset: usize, message: String) -> SnapshotError {
525    SnapshotError::InvalidInstruction(format!("{} (stream {}, offset {})", message, stream, offset))
526}
527
528pub(crate) struct Reader<'a> {
529    buf: &'a [u8],
530    pos: usize,
531}
532
533impl<'a> Reader<'a> {
534    pub(crate) fn new(buf: &'a [u8]) -> Self {
535        Reader {
536            buf,
537            pos: 0,
538        }
539    }
540
541    /// Cursor offset from the start of the buffer, for byte-range annotation
542    /// (see `snapshot_layout`).
543    pub(crate) fn position(&self) -> usize {
544        self.pos
545    }
546
547    fn remaining(&self) -> usize {
548        self.buf.len() - self.pos
549    }
550
551    pub(crate) fn read_u8(&mut self) -> Result<u8, SnapshotError> {
552        let byte = *self.buf.get(self.pos).ok_or(SnapshotError::UnexpectedEof)?;
553        self.pos += 1;
554        Ok(byte)
555    }
556
557    pub(crate) fn read_exact(&mut self, len: usize) -> Result<&'a [u8], SnapshotError> {
558        if len > self.remaining() {
559            return Err(SnapshotError::UnexpectedEof);
560        }
561        let slice = &self.buf[self.pos..self.pos + len];
562        self.pos += len;
563        Ok(slice)
564    }
565
566    /// Non-canonical encodings are accepted; only length and 64-bit range
567    /// are enforced (§4.1 hard rules).
568    pub(crate) fn read_uleb128(&mut self) -> Result<u64, SnapshotError> {
569        let mut result: u64 = 0;
570        let mut shift = 0u32;
571        for _ in 0..10 {
572            let byte = self.read_u8()?;
573            let bits = u64::from(byte & 0x7f);
574            if shift == 63 && bits > 1 {
575                return Err(SnapshotError::InvalidLeb128);
576            }
577            result |= bits << shift;
578            if byte & 0x80 == 0 {
579                return Ok(result);
580            }
581            shift += 7;
582        }
583        Err(SnapshotError::InvalidLeb128)
584    }
585
586    pub(crate) fn read_sleb128(&mut self) -> Result<i64, SnapshotError> {
587        let mut result: i64 = 0;
588        let mut shift = 0u32;
589        for _ in 0..10 {
590            let byte = self.read_u8()?;
591            let bits = i64::from(byte & 0x7f);
592            if shift == 63 {
593                // Tenth byte: only one value bit is left in an i64, so the
594                // payload must be all sign bits and end the encoding.
595                if byte & 0x80 != 0 || (bits != 0 && bits != 0x7f) {
596                    return Err(SnapshotError::InvalidLeb128);
597                }
598                return Ok(result | bits.wrapping_shl(63));
599            }
600            result |= bits << shift;
601            if byte & 0x80 == 0 {
602                if byte & 0x40 != 0 {
603                    result |= -1i64 << (shift + 7);
604                }
605                return Ok(result);
606            }
607            shift += 7;
608        }
609        Err(SnapshotError::InvalidLeb128)
610    }
611
612    /// ULEB128 checked into `usize` (they differ on wasm32).
613    pub(crate) fn read_usize(&mut self) -> Result<usize, SnapshotError> {
614        let value = self.read_uleb128()?;
615        usize::try_from(value).map_err(|_| SnapshotError::IntegerOverflow)
616    }
617
618    /// Entry count under the resource rule: every entry occupies at least
619    /// one input byte, so a count above the remaining input is rejected and
620    /// `Vec::with_capacity(count)` stays O(input size).
621    fn read_count(&mut self) -> Result<usize, SnapshotError> {
622        let count = self.read_usize()?;
623        if count > self.remaining() {
624            return Err(SnapshotError::LimitExceeded);
625        }
626        Ok(count)
627    }
628
629    fn read_length_prefixed_bytes(&mut self) -> Result<&'a [u8], SnapshotError> {
630        let len = self.read_usize()?;
631        if len > self.remaining() {
632            return Err(SnapshotError::LimitExceeded);
633        }
634        self.read_exact(len)
635    }
636
637    fn read_string(&mut self) -> Result<String, SnapshotError> {
638        let bytes = self.read_length_prefixed_bytes()?;
639        String::from_utf8(bytes.to_vec()).map_err(|_| SnapshotError::BadUtf8)
640    }
641}
compiler/snapshot.rs

compiler/
snapshot.rs
