Skip to main content

rhue_bytecode/
verify.rs

1//! The bytecode verifier.
2//!
3//! [`verify`] checks that a prototype (and every prototype nested in it) is
4//! well formed before the VM runs it:
5//!
6//! - every opcode is valid, and the code can't run off its end
7//! - every register an instruction reads or writes is below `max_stack`
8//!   (including the hidden ones `FORLOOP`, `TFORCALL` and `SELF` use)
9//! - constant, upvalue and prototype indices exist, and the constants are
10//!   the type the instruction needs (global and field names are strings)
11//! - every jump lands on an instruction (never on a `DATA` word)
12//! - a comparison is followed by its `JMP`, and `SETLIST` by its `DATA`
13//! - an instruction that eats "values up to `top`" comes right after one
14//!   that makes them, and isn't a jump target (so `top` is always the one
15//!   that was just set)
16//! - closures capture registers and upvalues that exist
17//! - debug info is in range: spans are inside the source text, and each
18//!   local's register and pc range exist
19//!
20//! The VM is memory-safe no matter what it runs (no `unsafe`, every access
21//! is checked), but bad bytecode would make it panic instead of raising a
22//! script error. The compiler's output always verifies, the engine checks
23//! it after every compile, and the test suites check every prototype they
24//! compile.
25
26use std::fmt;
27
28use crate::{Constant, Instr, Op, Proto};
29
30/// Why a prototype was rejected.
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct VerifyError {
33    /// The function's name in tracebacks (`<main>` for a chunk).
34    pub function: String,
35    /// The offending instruction, when there is one.
36    pub pc: Option<usize>,
37    pub message: String,
38}
39
40impl fmt::Display for VerifyError {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        match self.pc {
43            Some(pc) => write!(
44                f,
45                "invalid bytecode in {} at {pc}: {}",
46                self.function, self.message
47            ),
48            None => write!(f, "invalid bytecode in {}: {}", self.function, self.message),
49        }
50    }
51}
52
53impl std::error::Error for VerifyError {}
54
55/// The most registers a function can use. The VM keeps a window of a bit more
56/// than 256 slots above every frame, so this leaves room for the registers
57/// above `R(A)` that some instructions touch.
58pub const MAX_STACK: usize = 250;
59
60/// Checks `proto` (a main chunk) and everything nested in it.
61pub fn verify(proto: &Proto) -> Result<(), VerifyError> {
62    verify_one(proto, true)
63}
64
65/// [`verify`], skipped when this prototype already passed (it stays marked for
66/// as long as it lives, the code can't change inside an `Rc`).
67pub fn verify_once(proto: &Proto) -> Result<(), VerifyError> {
68    if proto.verified.get() {
69        return Ok(());
70    }
71    verify(proto)?;
72    proto.verified.set();
73    Ok(())
74}
75
76fn verify_one(proto: &Proto, is_main: bool) -> Result<(), VerifyError> {
77    let function = if is_main {
78        "<main>".to_string()
79    } else {
80        format!("`{}`", proto.display_name())
81    };
82    let fail = |pc: Option<usize>, message: String| VerifyError {
83        function: function.clone(),
84        pc,
85        message,
86    };
87
88    let code = &proto.code;
89    let max = proto.max_stack as usize;
90    if max > MAX_STACK {
91        return Err(fail(
92            None,
93            format!("uses {max} registers (the limit is {MAX_STACK})"),
94        ));
95    }
96    if proto.num_params as usize > max {
97        return Err(fail(None, "has more parameters than registers".into()));
98    }
99    if is_main && !proto.upvalues.is_empty() {
100        // a chunk runs as a closure with no upvalues
101        return Err(fail(None, "a main chunk can't have upvalues".into()));
102    }
103    if proto.spans.len() != code.len() {
104        return Err(fail(None, "needs one source span per instruction".into()));
105    }
106    let text_len = proto.source.text.len() as u32;
107    if let Some(pc) =
108        (proto.spans.iter().chain([&proto.span])).position(|s| s.start > s.end || s.end > text_len)
109    {
110        return Err(fail(
111            (pc < code.len()).then_some(pc),
112            "has a source span outside its source text".into(),
113        ));
114    }
115    for (i, t) in proto.templates.iter().enumerate() {
116        let bad = |why: &str| Err(fail(None, format!("has a bad table template T{i}: {why}")));
117        if t.array > MAX_TEMPLATE_SIZE || t.hash > MAX_TEMPLATE_SIZE {
118            return bad("too large");
119        }
120        if (t.hash as usize) < t.keys.len() {
121            return bad("fewer hash slots than keys");
122        }
123        let mut seen = std::collections::HashSet::with_capacity(t.keys.len());
124        for &k in &t.keys {
125            let Some(Constant::String(s)) = proto.constants.get(k as usize) else {
126                return bad("a key isn't a string constant");
127            };
128            if !seen.insert(&**s) {
129                return bad("a key appears twice");
130            }
131        }
132    }
133    for local in &proto.locals {
134        if local.reg as usize >= max
135            || local.start_pc > local.end_pc
136            || local.end_pc as usize > code.len()
137        {
138            return Err(fail(
139                None,
140                format!("has bad debug info for local `{}`", local.name),
141            ));
142        }
143    }
144    match code.last().and_then(|i| i.op()) {
145        Some(Op::Return | Op::Jmp) => {}
146        _ => return Err(fail(None, "doesn't end with RETURN or JMP".into())),
147    }
148
149    // instructions that consume `top` have to come right after one that sets
150    // it, so neither can be a jump target
151    let mut targets = vec![false; code.len()];
152
153    for (pc, &ins) in code.iter().enumerate() {
154        let err = |message: String| fail(Some(pc), message);
155        let Some(op) = ins.op() else {
156            return Err(err(format!("invalid opcode {:#04x}", ins.0 as u8)));
157        };
158        let (a, b, c) = (ins.a() as usize, ins.b() as usize, ins.c() as usize);
159        let reg = |r: usize, what: &str| {
160            if r < max {
161                Ok(())
162            } else {
163                Err(err(format!(
164                    "{what} register R{r} is beyond max_stack {max}"
165                )))
166            }
167        };
168        let regs = |from: usize, count: usize| {
169            if count == 0 || from + count <= max {
170                Ok(())
171            } else {
172                Err(err(format!(
173                    "registers R{from}..R{} are beyond max_stack {max}",
174                    from + count - 1
175                )))
176            }
177        };
178        let constant = |k: usize| {
179            proto
180                .constants
181                .get(k)
182                .ok_or_else(|| err(format!("no constant K{k}")))
183        };
184        let string_constant = |k: usize| match constant(k)? {
185            Constant::String(_) => Ok(()),
186            Constant::Number(_) => Err(err(format!("K{k} must be a string"))),
187        };
188        let number_constant = |k: usize| match constant(k)? {
189            Constant::Number(_) => Ok(()),
190            Constant::String(_) => Err(err(format!("K{k} must be a number"))),
191        };
192        let mut jump = |by: i32| {
193            let target = pc as i64 + 1 + by as i64;
194            if target < 0 || target >= code.len() as i64 {
195                return Err(err(format!("jump to {target} is outside the code")));
196            }
197            let target = target as usize;
198            if code[target].op() == Some(Op::Data) {
199                return Err(err(format!("jump to {target} lands on a DATA word")));
200            }
201            targets[target] = true;
202            Ok(())
203        };
204        let next = code.get(pc + 1).and_then(|i| i.op());
205
206        match op {
207            Op::LoadNil | Op::LoadN | Op::NewTable => reg(a, "target")?,
208            Op::DupTable => {
209                reg(a, "target")?;
210                if ins.bx() as usize >= proto.templates.len() {
211                    return Err(err(format!("no table template T{}", ins.bx())));
212                }
213            }
214            Op::LoadB => {
215                reg(a, "target")?;
216                if c != 0 {
217                    // skips the next instruction
218                    jump(1)?;
219                }
220            }
221            Op::LoadK => {
222                reg(a, "target")?;
223                constant(ins.bx() as usize)?;
224            }
225            Op::GetGlobal | Op::SetGlobal => {
226                reg(a, "value")?;
227                string_constant(ins.bx() as usize)?;
228            }
229            Op::Move | Op::Unm | Op::Not | Op::Len => {
230                reg(a, "target")?;
231                reg(b, "source")?;
232            }
233            Op::Add | Op::Sub | Op::Mul | Op::Div | Op::IDiv | Op::Mod | Op::Pow | Op::Concat => {
234                reg(a, "target")?;
235                reg(b, "left")?;
236                reg(c, "right")?;
237            }
238            Op::AddK | Op::SubK | Op::MulK | Op::DivK | Op::IDivK | Op::ModK | Op::PowK => {
239                reg(a, "target")?;
240                reg(b, "left")?;
241                number_constant(c)?;
242            }
243            Op::Eq | Op::Lt | Op::Le | Op::EqK | Op::LtK | Op::LeK | Op::GtK | Op::GeK => {
244                reg(b, "left")?;
245                if matches!(op, Op::Eq | Op::Lt | Op::Le) {
246                    reg(c, "right")?;
247                } else {
248                    constant(c)?;
249                }
250                if next != Some(Op::Jmp) {
251                    return Err(err("a comparison must be followed by a JMP".into()));
252                }
253                // skips the jump
254                jump(1)?;
255            }
256            Op::Jmp => jump(ins.sax())?,
257            Op::JmpIf | Op::JmpIfNot => {
258                reg(a, "tested")?;
259                jump(ins.sbx() as i32)?;
260            }
261            Op::ForPrep | Op::ForLoop => {
262                regs(a, 4)?;
263                jump(ins.sbx() as i32)?;
264            }
265            Op::GetUpval | Op::SetUpval => {
266                reg(a, "value")?;
267                if b >= proto.upvalues.len() {
268                    return Err(err(format!("no upvalue U{b}")));
269                }
270            }
271            Op::Close => {
272                if a > max {
273                    return Err(err(format!("closes from R{a}, beyond max_stack {max}")));
274                }
275            }
276            Op::Closure => {
277                reg(a, "target")?;
278                let Some(child) = proto.protos.get(ins.bx() as usize) else {
279                    return Err(err(format!("no prototype P{}", ins.bx())));
280                };
281                for (i, up) in child.upvalues.iter().enumerate() {
282                    let ok = if up.in_stack {
283                        (up.index as usize) < max
284                    } else {
285                        (up.index as usize) < proto.upvalues.len()
286                    };
287                    if !ok {
288                        return Err(err(format!(
289                            "the closure's upvalue {i} captures something that doesn't exist"
290                        )));
291                    }
292                }
293            }
294            Op::Call => {
295                reg(a, "function")?;
296                if b > 0 {
297                    regs(a + 1, b - 1)?;
298                } else {
299                    consumes_top(code, pc, a + 1).map_err(err)?;
300                }
301                if c > 0 {
302                    regs(a, c - 1)?;
303                }
304            }
305            Op::Interp => {
306                reg(a, "target")?;
307                if c == 0 {
308                    return Err(err("INTERP needs at least one piece".into()));
309                }
310                regs(b, c)?;
311            }
312            Op::TailCall => {
313                reg(a, "function")?;
314                if b > 0 {
315                    regs(a + 1, b - 1)?;
316                } else {
317                    consumes_top(code, pc, a + 1).map_err(err)?;
318                }
319                let returns = code.get(pc + 1).is_some_and(|r| {
320                    r.op() == Some(Op::Return) && r.a() as usize == a && r.c() != 0
321                });
322                if c != 0 || !returns {
323                    return Err(err(
324                        "TAILCALL must keep all results and be followed by RETURN of them".into(),
325                    ));
326                }
327            }
328            Op::Vararg => {
329                if b > 0 {
330                    regs(a, b - 1)?;
331                } else if a > max {
332                    return Err(err(format!("R{a} is beyond max_stack {max}")));
333                }
334            }
335            Op::GetTable | Op::SetTable => {
336                reg(a, "table/target")?;
337                reg(b, "table/key")?;
338                reg(c, "key/value")?;
339            }
340            Op::GetField => {
341                reg(a, "target")?;
342                reg(b, "table")?;
343                string_constant(c)?;
344            }
345            Op::SetField => {
346                reg(a, "table")?;
347                string_constant(b)?;
348                reg(c, "value")?;
349            }
350            Op::SelfOp => {
351                regs(a, 2)?;
352                reg(b, "object")?;
353                string_constant(c)?;
354            }
355            Op::SetList => {
356                reg(a, "table")?;
357                if b > 0 {
358                    regs(a + 1, b)?;
359                } else {
360                    consumes_top(code, pc, a + 1).map_err(err)?;
361                }
362                if next != Some(Op::Data) {
363                    return Err(err("SETLIST must be followed by its DATA word".into()));
364                }
365                if code[pc + 1].sax() < 0 {
366                    return Err(err("SETLIST start index is negative".into()));
367                }
368            }
369            Op::Data => {
370                if pc == 0 || code[pc - 1].op() != Some(Op::SetList) {
371                    return Err(err("a DATA word must follow SETLIST".into()));
372                }
373            }
374            Op::TForCall => {
375                // the iterator, state and control, then the call's copies of
376                // them, which double as the variables (at least three)
377                if c == 0 {
378                    return Err(err("a generic for needs at least one variable".into()));
379                }
380                regs(a, 3 + c.max(3))?;
381            }
382            Op::TForLoop => {
383                regs(a, 4)?;
384                jump(ins.sbx() as i32)?;
385            }
386            Op::Return => {
387                if c != 0 {
388                    consumes_top(code, pc, a).map_err(err)?;
389                } else if b > 0 {
390                    regs(a, b)?;
391                } else if a > max {
392                    return Err(err(format!("R{a} is beyond max_stack {max}")));
393                }
394            }
395        }
396    }
397
398    // `top` only carries over from the instruction right before
399    for (pc, &ins) in code.iter().enumerate() {
400        let uses_top = match ins.op() {
401            Some(Op::Call | Op::TailCall) => ins.b() == 0,
402            Some(Op::SetList) => ins.b() == 0,
403            Some(Op::Return) => ins.c() != 0,
404            _ => false,
405        };
406        if uses_top && targets[pc] {
407            return Err(fail(
408                Some(pc),
409                "a jump lands on an instruction that uses the values left by the one before it"
410                    .into(),
411            ));
412        }
413    }
414
415    for child in &proto.protos {
416        verify_one(child, false)?;
417    }
418    Ok(())
419}
420
421/// Checks that the instruction before `pc` leaves its values (`top`) at or
422/// above register `from`: a `CALL` keeping all its results, a `TAILCALL` (when
423/// the callee's a native), or a `VARARG` copying everything.
424fn consumes_top(code: &[Instr], pc: usize, from: usize) -> Result<(), String> {
425    let prev = pc.checked_sub(1).map(|p| code[p]);
426    match prev.and_then(|i| i.op().map(|op| (op, i))) {
427        Some((Op::Call, i)) if i.c() == 0 && i.a() as usize >= from => Ok(()),
428        Some((Op::TailCall, i)) if i.a() as usize >= from => Ok(()),
429        Some((Op::Vararg, i)) if i.b() == 0 && i.a() as usize >= from => Ok(()),
430        _ => Err(
431            "uses the values up to `top`, but the instruction before doesn't leave any \
432                  there"
433                .into(),
434        ),
435    }
436}
437
438/// The most array or hash slots a table template can reserve.
439pub const MAX_TEMPLATE_SIZE: u32 = 1 << 16;
440
441#[cfg(test)]
442mod tests {
443    use super::*;
444    use rhue_common::Span;
445
446    fn proto(code: Vec<Instr>, constants: Vec<Constant>, max_stack: u8) -> Proto {
447        Proto {
448            spans: vec![Span::default(); code.len()],
449            code,
450            constants,
451            max_stack,
452            ..Proto::default()
453        }
454    }
455
456    fn rejects(p: Proto, needle: &str) {
457        let e = verify(&p).expect_err("should be rejected");
458        assert!(e.to_string().contains(needle), "{e}");
459    }
460
461    #[test]
462    fn accepts_a_minimal_function() {
463        verify(&proto(vec![Instr::abc(Op::Return, 0, 0, 0)], vec![], 0)).unwrap();
464    }
465
466    #[test]
467    fn rejects_malformed_code() {
468        rejects(proto(vec![], vec![], 0), "doesn't end");
469        rejects(
470            proto(vec![Instr::asbx(Op::LoadN, 0, 1)], vec![], 1),
471            "doesn't end",
472        );
473        rejects(
474            proto(
475                vec![Instr(0xff), Instr::abc(Op::Return, 0, 0, 0)],
476                vec![],
477                1,
478            ),
479            "invalid opcode",
480        );
481        rejects(
482            proto(
483                vec![
484                    Instr::abc(Op::Move, 3, 0, 0),
485                    Instr::abc(Op::Return, 0, 0, 0),
486                ],
487                vec![],
488                2,
489            ),
490            "R3",
491        );
492        rejects(
493            proto(
494                vec![Instr::abx(Op::LoadK, 0, 5), Instr::abc(Op::Return, 0, 0, 0)],
495                vec![],
496                1,
497            ),
498            "no constant K5",
499        );
500        rejects(
501            proto(
502                vec![
503                    Instr::abx(Op::GetGlobal, 0, 0),
504                    Instr::abc(Op::Return, 0, 0, 0),
505                ],
506                vec![Constant::Number(1.0)],
507                1,
508            ),
509            "must be a string",
510        );
511        rejects(
512            proto(
513                vec![Instr::asax(Op::Jmp, 5), Instr::abc(Op::Return, 0, 0, 0)],
514                vec![],
515                0,
516            ),
517            "outside the code",
518        );
519        rejects(
520            proto(
521                vec![Instr::abc(Op::Lt, 0, 0, 0), Instr::abc(Op::Return, 0, 0, 0)],
522                vec![],
523                1,
524            ),
525            "followed by a JMP",
526        );
527        rejects(
528            proto(
529                vec![
530                    Instr::abc(Op::Call, 0, 0, 1),
531                    Instr::abc(Op::Return, 0, 0, 0),
532                ],
533                vec![],
534                1,
535            ),
536            "top",
537        );
538        rejects(
539            proto(
540                vec![
541                    Instr::abc(Op::GetUpval, 0, 0, 0),
542                    Instr::abc(Op::Return, 0, 0, 0),
543                ],
544                vec![],
545                1,
546            ),
547            "no upvalue",
548        );
549        rejects(
550            proto(
551                vec![
552                    Instr::abc(Op::SetList, 0, 1, 0),
553                    Instr::abc(Op::Return, 0, 0, 0),
554                ],
555                vec![],
556                2,
557            ),
558            "DATA",
559        );
560    }
561
562    #[test]
563    fn rejects_jumps_onto_data_and_into_top_consumers() {
564        rejects(
565            proto(
566                vec![
567                    Instr::asax(Op::Jmp, 1),
568                    Instr::abc(Op::SetList, 0, 1, 0),
569                    Instr::asax(Op::Data, 0),
570                    Instr::abc(Op::Return, 0, 0, 0),
571                ],
572                vec![],
573                2,
574            ),
575            "DATA word",
576        );
577        rejects(
578            proto(
579                vec![
580                    Instr::abc(Op::Call, 0, 1, 0),
581                    Instr::asax(Op::Jmp, 0),
582                    Instr::abc(Op::Return, 0, 0, 1),
583                ],
584                vec![],
585                1,
586            ),
587            "before",
588        );
589    }
590}