1use mutatis::mutators as m;
3use mutatis::{Candidates, Context, DefaultMutate, Generate, Mutate, Result as MutResult};
4use serde::{Deserialize, Serialize};
5use smallvec::SmallVec;
6use std::ops::RangeInclusive;
7use wasm_encoder::{
8 CodeSection, ConstExpr, EntityType, ExportKind, ExportSection, Function, FunctionSection,
9 GlobalSection, ImportSection, Instruction, Module, RefType, TableSection, TableType,
10 TypeSection, ValType,
11};
12
13const NUM_PARAMS_RANGE: RangeInclusive<u32> = 0..=10;
14const NUM_GLOBALS_RANGE: RangeInclusive<u32> = 0..=10;
15const TABLE_SIZE_RANGE: RangeInclusive<u32> = 0..=100;
16const NUM_REC_GROUPS_RANGE: RangeInclusive<u32> = 0..=10;
17const MAX_OPS: usize = 100;
18
19#[derive(Debug, Clone, Eq, PartialOrd, PartialEq, Ord, Hash, Default, Serialize, Deserialize)]
21pub struct RecGroupId(u32);
22
23#[derive(Debug, Default, Serialize, Deserialize)]
25pub struct Types {
26 rec_groups: std::collections::BTreeSet<RecGroupId>,
27}
28
29impl Types {
30 pub fn new() -> Self {
32 Self {
33 rec_groups: Default::default(),
34 }
35 }
36
37 pub fn insert_rec_group(&mut self, id: RecGroupId) -> bool {
39 self.rec_groups.insert(id)
40 }
41
42 pub fn groups(&self) -> impl Iterator<Item = &RecGroupId> {
44 self.rec_groups.iter()
45 }
46}
47
48#[derive(Debug, Default, Serialize, Deserialize)]
50pub struct TableOpsLimits {
51 pub(crate) num_params: u32,
52 pub(crate) num_globals: u32,
53 pub(crate) table_size: u32,
54 pub(crate) num_rec_groups: u32,
55}
56
57impl TableOpsLimits {
58 fn fixup(&mut self) {
59 let Self {
62 num_params,
63 num_globals,
64 table_size,
65 num_rec_groups,
66 } = self;
67
68 let clamp = |limit: &mut u32, range: RangeInclusive<u32>| {
69 *limit = (*limit).clamp(*range.start(), *range.end())
70 };
71 clamp(table_size, TABLE_SIZE_RANGE);
72 clamp(num_params, NUM_PARAMS_RANGE);
73 clamp(num_globals, NUM_GLOBALS_RANGE);
74 clamp(num_rec_groups, NUM_REC_GROUPS_RANGE);
75 }
76}
77
78#[derive(Debug, Default, Serialize, Deserialize)]
81pub struct TableOps {
82 pub(crate) limits: TableOpsLimits,
83 pub(crate) ops: Vec<TableOp>,
84 pub(crate) types: Types,
85}
86
87impl TableOps {
88 pub fn to_wasm_binary(&mut self) -> Vec<u8> {
100 self.fixup();
101
102 let mut module = Module::new();
103
104 let mut types = TypeSection::new();
106
107 types.ty().function(
109 vec![],
110 vec![ValType::EXTERNREF, ValType::EXTERNREF, ValType::EXTERNREF],
117 );
118
119 let mut params: Vec<ValType> = Vec::with_capacity(self.limits.num_params as usize);
121 for _i in 0..self.limits.num_params {
122 params.push(ValType::EXTERNREF);
123 }
124 let results = vec![];
125 types.ty().function(params, results);
126
127 types.ty().function(
129 vec![ValType::EXTERNREF, ValType::EXTERNREF, ValType::EXTERNREF],
130 vec![],
131 );
132
133 types.ty().function(
135 vec![],
136 vec![ValType::EXTERNREF, ValType::EXTERNREF, ValType::EXTERNREF],
137 );
138
139 let mut imports = ImportSection::new();
141 imports.import("", "gc", EntityType::Function(0));
142 imports.import("", "take_refs", EntityType::Function(2));
143 imports.import("", "make_refs", EntityType::Function(3));
144
145 let mut tables = TableSection::new();
147 tables.table(TableType {
148 element_type: RefType::EXTERNREF,
149 minimum: u64::from(self.limits.table_size),
150 maximum: None,
151 table64: false,
152 shared: false,
153 });
154
155 let mut globals = GlobalSection::new();
157 for _ in 0..self.limits.num_globals {
158 globals.global(
159 wasm_encoder::GlobalType {
160 val_type: wasm_encoder::ValType::EXTERNREF,
161 mutable: true,
162 shared: false,
163 },
164 &ConstExpr::ref_null(wasm_encoder::HeapType::EXTERN),
165 );
166 }
167
168 let mut functions = FunctionSection::new();
170 functions.function(1);
171
172 let mut exports = ExportSection::new();
173 exports.export("run", ExportKind::Func, 3);
174
175 let mut func = Function::new(vec![(1, ValType::EXTERNREF)]);
178
179 func.instruction(&Instruction::Loop(wasm_encoder::BlockType::Empty));
180 for op in &self.ops {
181 op.insert(&mut func, self.limits.num_params);
182 }
183 func.instruction(&Instruction::Br(0));
184 func.instruction(&Instruction::End);
185 func.instruction(&Instruction::End);
186
187 for _ in self.types.groups() {
189 types.ty().rec(Vec::<wasm_encoder::SubType>::new());
190 }
191
192 let mut code = CodeSection::new();
193 code.function(&func);
194
195 module
196 .section(&types)
197 .section(&imports)
198 .section(&functions)
199 .section(&tables)
200 .section(&globals)
201 .section(&exports)
202 .section(&code);
203
204 module.finish()
205 }
206
207 pub fn abstract_stack_depth(&self, index: usize) -> usize {
209 debug_assert!(index <= self.ops.len());
210 let mut stack: usize = 0;
211 for op in self.ops.iter().take(index) {
212 let pop = op.operands_len();
213 let push = op.results_len();
214 stack = stack.saturating_sub(pop);
215 stack += push;
216 }
217 stack
218 }
219
220 fn fixup(&mut self) {
232 self.limits.fixup();
233
234 let mut new_ops = Vec::with_capacity(self.ops.len());
235 let mut stack = 0;
236
237 for mut op in self.ops.iter().copied() {
238 op.fixup(&self.limits);
239
240 let mut temp = SmallVec::<[_; 4]>::new();
241
242 while stack < op.operands_len() {
243 temp.push(TableOp::Null());
244 stack += 1;
245 }
246
247 temp.push(op);
248 stack = stack - op.operands_len() + op.results_len();
249
250 new_ops.extend(temp);
251 }
252
253 for _ in 0..stack {
255 new_ops.push(TableOp::Drop());
256 }
257
258 self.ops = new_ops;
259 }
260
261 pub fn pop(&mut self) -> bool {
265 self.ops.pop().is_some()
266 }
267}
268
269#[derive(Debug)]
271pub struct TableOpsMutator;
272
273impl Mutate<TableOps> for TableOpsMutator {
274 fn mutate(&mut self, c: &mut Candidates<'_>, ops: &mut TableOps) -> mutatis::Result<()> {
275 if !c.shrink() {
276 c.mutation(|ctx| {
277 if let Some(idx) = ctx.rng().gen_index(ops.ops.len() + 1) {
278 let stack = ops.abstract_stack_depth(idx);
279 let (op, _new_stack_size) = TableOp::generate(ctx, &ops, stack)?;
280 ops.ops.insert(idx, op);
281 }
282 Ok(())
283 })?;
284 }
285 if !ops.ops.is_empty() {
286 c.mutation(|ctx| {
287 let idx = ctx
288 .rng()
289 .gen_index(ops.ops.len())
290 .expect("ops is not empty");
291 ops.ops.remove(idx);
292 Ok(())
293 })?;
294 }
295
296 Ok(())
297 }
298}
299
300impl DefaultMutate for TableOps {
301 type DefaultMutate = TableOpsMutator;
302}
303
304impl Default for TableOpsMutator {
305 fn default() -> Self {
306 TableOpsMutator
307 }
308}
309
310impl<'a> arbitrary::Arbitrary<'a> for TableOps {
311 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
312 let mut session = mutatis::Session::new().seed(u.arbitrary()?);
313 session
314 .generate()
315 .map_err(|_| arbitrary::Error::IncorrectFormat)
316 }
317}
318
319impl Generate<TableOps> for TableOpsMutator {
320 fn generate(&mut self, ctx: &mut Context) -> MutResult<TableOps> {
321 let num_params = m::range(NUM_PARAMS_RANGE).generate(ctx)?;
322 let num_globals = m::range(NUM_GLOBALS_RANGE).generate(ctx)?;
323 let table_size = m::range(TABLE_SIZE_RANGE).generate(ctx)?;
324
325 let num_rec_groups = m::range(NUM_REC_GROUPS_RANGE).generate(ctx)?;
326
327 let mut ops = TableOps {
328 limits: TableOpsLimits {
329 num_params,
330 num_globals,
331 table_size,
332 num_rec_groups,
333 },
334 ops: vec![
335 TableOp::Null(),
336 TableOp::Drop(),
337 TableOp::Gc(),
338 TableOp::LocalSet(0),
339 TableOp::LocalGet(0),
340 TableOp::GlobalSet(0),
341 TableOp::GlobalGet(0),
342 ],
343 types: Types::new(),
344 };
345
346 for i in 0..ops.limits.num_rec_groups {
347 ops.types.insert_rec_group(RecGroupId(i));
348 }
349
350 let mut stack: usize = 0;
351 while ops.ops.len() < MAX_OPS {
352 let (op, new_stack_len) = TableOp::generate(ctx, &ops, stack)?;
353 ops.ops.push(op);
354 stack = new_stack_len;
355 }
356
357 for _ in 0..stack {
359 ops.ops.push(TableOp::Drop());
360 }
361
362 Ok(ops)
363 }
364}
365
366macro_rules! define_table_ops {
367 (
368 $(
369 $op:ident $( ( $($limit_var:ident : $limit:expr => $ty:ty),* ) )? : $params:expr => $results:expr ,
370 )*
371 ) => {
372 #[derive(Copy, Clone, Debug, Serialize, Deserialize)]
373 pub(crate) enum TableOp {
374 $(
375 $op ( $( $($ty),* )? ),
376 )*
377 }
378 #[cfg(test)]
379 const OP_NAMES: &'static[&'static str] = &[
380 $(
381 stringify!($op),
382 )*
383 ];
384
385 impl TableOp {
386 #[cfg(test)]
387 fn name(&self) -> &'static str {
388 match self {
389 $(
390 Self::$op (..) => stringify!($op),
391 )*
392 }
393 }
394
395 pub fn operands_len(&self) -> usize {
396 match self {
397 $(
398 Self::$op (..) => $params,
399 )*
400 }
401 }
402
403 pub fn results_len(&self) -> usize {
404 match self {
405 $(
406 Self::$op (..) => $results,
407 )*
408 }
409 }
410 }
411
412 $(
413 #[allow(non_snake_case, reason = "macro-generated code")]
414 fn $op(
415 _ctx: &mut mutatis::Context,
416 _limits: &TableOpsLimits,
417 stack: usize,
418 ) -> mutatis::Result<(TableOp, usize)> {
419 #[allow(unused_comparisons, reason = "macro-generated code")]
420 {
421 debug_assert!(stack >= $params);
422 }
423
424 let op = TableOp::$op(
425 $($({
426 let limit_fn = $limit as fn(&TableOpsLimits) -> $ty;
427 let limit = (limit_fn)(_limits);
428 debug_assert!(limit > 0);
429 m::range(0..=limit - 1).generate(_ctx)?
430 })*)?
431 );
432 let new_stack = stack - $params + $results;
433 Ok((op, new_stack))
434 }
435 )*
436
437 impl TableOp {
438 fn fixup(&mut self, limits: &TableOpsLimits) {
439 match self {
440 $(
441 Self::$op( $( $( $limit_var ),* )? ) => {
442 $( $(
443 let limit_fn = $limit as fn(&TableOpsLimits) -> $ty;
444 let limit = (limit_fn)(limits);
445 debug_assert!(limit > 0);
446 *$limit_var = *$limit_var % limit;
447 )* )?
448 }
449 )*
450 }
451 }
452
453 fn generate(
454 ctx: &mut mutatis::Context,
455 ops: &TableOps,
456 stack: usize,
457 ) -> mutatis::Result<(TableOp, usize)> {
458 let mut valid_choices: Vec<
459 fn(&mut Context, &TableOpsLimits, usize) -> mutatis::Result<(TableOp, usize)>
460 > = vec![];
461 $(
462 #[allow(unused_comparisons, reason = "macro-generated code")]
463 if stack >= $params $($(
464 && {
465 let limit_fn = $limit as fn(&TableOpsLimits) -> $ty;
466 let limit = (limit_fn)(&ops.limits);
467 limit > 0
468 }
469 )*)? {
470 valid_choices.push($op);
471 }
472 )*
473
474 let f = *ctx.rng()
475 .choose(&valid_choices)
476 .expect("should always have a valid op choice");
477
478 (f)(ctx, &ops.limits, stack)
479 }
480 }
481 };
482}
483
484define_table_ops! {
485 Gc : 0 => 3,
486
487 MakeRefs : 0 => 3,
488 TakeRefs : 3 => 0,
489
490 TableGet(elem_index: |ops| ops.table_size + 1 => u32) : 0 => 1,
492 TableSet(elem_index: |ops| ops.table_size + 1 => u32) : 1 => 0,
493
494 GlobalGet(global_index: |ops| ops.num_globals => u32) : 0 => 1,
495 GlobalSet(global_index: |ops| ops.num_globals => u32) : 1 => 0,
496
497 LocalGet(local_index: |ops| ops.num_params => u32) : 0 => 1,
498 LocalSet(local_index: |ops| ops.num_params => u32) : 1 => 0,
499
500 Drop : 1 => 0,
501
502 Null : 0 => 1,
503}
504
505impl TableOp {
506 fn insert(self, func: &mut Function, scratch_local: u32) {
507 let gc_func_idx = 0;
508 let take_refs_func_idx = 1;
509 let make_refs_func_idx = 2;
510
511 match self {
512 Self::Gc() => {
513 func.instruction(&Instruction::Call(gc_func_idx));
514 }
515 Self::MakeRefs() => {
516 func.instruction(&Instruction::Call(make_refs_func_idx));
517 }
518 Self::TakeRefs() => {
519 func.instruction(&Instruction::Call(take_refs_func_idx));
520 }
521 Self::TableGet(x) => {
522 func.instruction(&Instruction::I32Const(x.cast_signed()));
523 func.instruction(&Instruction::TableGet(0));
524 }
525 Self::TableSet(x) => {
526 func.instruction(&Instruction::LocalSet(scratch_local));
527 func.instruction(&Instruction::I32Const(x.cast_signed()));
528 func.instruction(&Instruction::LocalGet(scratch_local));
529 func.instruction(&Instruction::TableSet(0));
530 }
531 Self::GlobalGet(x) => {
532 func.instruction(&Instruction::GlobalGet(x));
533 }
534 Self::GlobalSet(x) => {
535 func.instruction(&Instruction::GlobalSet(x));
536 }
537 Self::LocalGet(x) => {
538 func.instruction(&Instruction::LocalGet(x));
539 }
540 Self::LocalSet(x) => {
541 func.instruction(&Instruction::LocalSet(x));
542 }
543 Self::Drop() => {
544 func.instruction(&Instruction::Drop);
545 }
546 Self::Null() => {
547 func.instruction(&Instruction::RefNull(wasm_encoder::HeapType::EXTERN));
548 }
549 }
550 }
551}
552
553#[cfg(test)]
554mod tests {
555 use super::*;
556
557 fn empty_test_ops() -> TableOps {
559 let mut t = TableOps {
560 limits: TableOpsLimits {
561 num_params: 5,
562 num_globals: 5,
563 table_size: 5,
564 num_rec_groups: 5,
565 },
566 ops: vec![],
567 types: Types::new(),
568 };
569 for i in 0..t.limits.num_rec_groups {
570 t.types.insert_rec_group(RecGroupId(i));
571 }
572 t
573 }
574
575 fn test_ops(num_params: u32, num_globals: u32, table_size: u32) -> TableOps {
577 let mut t = TableOps {
578 limits: TableOpsLimits {
579 num_params,
580 num_globals,
581 table_size,
582 num_rec_groups: 3,
583 },
584 ops: vec![
585 TableOp::Null(),
586 TableOp::Drop(),
587 TableOp::Gc(),
588 TableOp::LocalSet(0),
589 TableOp::LocalGet(0),
590 TableOp::GlobalSet(0),
591 TableOp::GlobalGet(0),
592 TableOp::Null(),
593 TableOp::Drop(),
594 TableOp::Gc(),
595 TableOp::LocalSet(0),
596 TableOp::LocalGet(0),
597 TableOp::GlobalSet(0),
598 TableOp::GlobalGet(0),
599 TableOp::Null(),
600 TableOp::Drop(),
601 ],
602 types: Types::new(),
603 };
604 for i in 0..t.limits.num_rec_groups {
605 t.types.insert_rec_group(RecGroupId(i));
606 }
607 t
608 }
609
610 #[test]
611 fn mutate_table_ops_with_default_mutator() -> mutatis::Result<()> {
612 let _ = env_logger::try_init();
613 let mut res = test_ops(5, 5, 5);
614
615 let mut session = mutatis::Session::new();
616
617 for _ in 0..1024 {
618 session.mutate(&mut res)?;
619 let wasm = res.to_wasm_binary();
620
621 let feats = wasmparser::WasmFeatures::default();
622 feats.reference_types();
623 feats.gc();
624 let mut validator = wasmparser::Validator::new_with_features(feats);
625
626 let wat = wasmprinter::print_bytes(&wasm).expect("[-] Failed .print_bytes(&wasm).");
627 let result = validator.validate_all(&wasm);
628 log::debug!("{wat}");
629 assert!(
630 result.is_ok(),
631 "\n[-] Invalid wat: {}\n\t\t==== Failed Wat ====\n{}",
632 result.err().expect("[-] Failed .err() in assert macro."),
633 wat
634 );
635 }
636 Ok(())
637 }
638
639 #[test]
640 fn every_op_generated() -> mutatis::Result<()> {
641 let _ = env_logger::try_init();
642 let mut unseen_ops: std::collections::HashSet<_> = OP_NAMES.iter().copied().collect();
643
644 let mut res = empty_test_ops();
645 let mut session = mutatis::Session::new();
646
647 'outer: for _ in 0..=1024 {
648 session.mutate(&mut res)?;
649 for op in &res.ops {
650 unseen_ops.remove(op.name());
651 if unseen_ops.is_empty() {
652 break 'outer;
653 }
654 }
655 }
656
657 assert!(unseen_ops.is_empty(), "Failed to generate {unseen_ops:?}");
658 Ok(())
659 }
660
661 #[test]
662 fn test_wat_string() -> mutatis::Result<()> {
663 let _ = env_logger::try_init();
664
665 let mut table_ops = test_ops(2, 2, 5);
666
667 let wasm = table_ops.to_wasm_binary();
668
669 let actual_wat = wasmprinter::print_bytes(&wasm).expect("Failed to convert to WAT");
670 let actual_wat = actual_wat.trim();
671
672 let expected_wat = r#"
673(module
674 (type (;0;) (func (result externref externref externref)))
675 (type (;1;) (func (param externref externref)))
676 (type (;2;) (func (param externref externref externref)))
677 (type (;3;) (func (result externref externref externref)))
678 (rec)
679 (rec)
680 (rec)
681 (import "" "gc" (func (;0;) (type 0)))
682 (import "" "take_refs" (func (;1;) (type 2)))
683 (import "" "make_refs" (func (;2;) (type 3)))
684 (table (;0;) 5 externref)
685 (global (;0;) (mut externref) ref.null extern)
686 (global (;1;) (mut externref) ref.null extern)
687 (export "run" (func 3))
688 (func (;3;) (type 1) (param externref externref)
689 (local externref)
690 loop ;; label = @1
691 ref.null extern
692 drop
693 call 0
694 local.set 0
695 local.get 0
696 global.set 0
697 global.get 0
698 ref.null extern
699 drop
700 call 0
701 local.set 0
702 local.get 0
703 global.set 0
704 global.get 0
705 ref.null extern
706 drop
707 drop
708 drop
709 drop
710 drop
711 drop
712 drop
713 br 0 (;@1;)
714 end
715 )
716)
717 "#;
718 let expected_wat = expected_wat.trim();
719
720 eprintln!("=== actual ===\n{actual_wat}");
721 eprintln!("=== expected ===\n{expected_wat}");
722 assert_eq!(
723 actual_wat, expected_wat,
724 "actual WAT does not match expected"
725 );
726
727 Ok(())
728 }
729
730 #[test]
731 fn emits_empty_rec_groups_and_validates() -> mutatis::Result<()> {
732 let _ = env_logger::try_init();
733
734 let mut ops = TableOps {
735 limits: TableOpsLimits {
736 num_params: 2,
737 num_globals: 1,
738 table_size: 5,
739 num_rec_groups: 2,
740 },
741 ops: vec![TableOp::Null(), TableOp::Drop()],
742 types: Types::new(),
743 };
744
745 for i in 0..ops.limits.num_rec_groups {
746 ops.types.insert_rec_group(RecGroupId(i));
747 }
748
749 let wasm = ops.to_wasm_binary();
750
751 let feats = wasmparser::WasmFeatures::default();
752 feats.reference_types();
753 feats.gc();
754 let mut validator = wasmparser::Validator::new_with_features(feats);
755 assert!(
756 validator.validate_all(&wasm).is_ok(),
757 "GC validation failed"
758 );
759
760 let wat = wasmprinter::print_bytes(&wasm).expect("to WAT");
761 let recs = wat.matches("(rec").count();
762 let structs = wat.matches("(struct)").count();
763
764 assert_eq!(recs, 2, "expected 2 (rec) blocks, got {recs}");
765 assert_eq!(structs, 0, "expected no struct types, got {structs}");
767
768 Ok(())
769 }
770}