1use std::fmt;
27
28use crate::{Constant, Instr, Op, Proto};
29
30#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct VerifyError {
33 pub function: String,
35 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
55pub const MAX_STACK: usize = 250;
59
60pub fn verify(proto: &Proto) -> Result<(), VerifyError> {
62 verify_one(proto, true)
63}
64
65pub 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 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 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 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 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 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 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
421fn 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
438pub 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}