wasmtime_fuzzing/generators/gc_ops/
mutator.rs

1//! Mutators for the `gc` operations.
2use crate::generators::gc_ops::limits::GcOpsLimits;
3use crate::generators::gc_ops::ops::{GcOp, GcOpMutator, GcOps};
4use crate::generators::gc_ops::types::{SubType, TypeId, Types};
5use mutatis::{
6    Candidates, Context, DefaultMutate, Generate, Mutate, Result as MutResult, mutators as m,
7};
8use smallvec::SmallVec;
9use std::collections::BTreeMap;
10
11/// Mutator for [`Types`]: handles adding/removing types and all rec-group
12/// structural mutations (duplicate, remove, merge, split, move).
13#[derive(Debug, Default)]
14pub struct TypesMutator;
15
16impl TypesMutator {
17    /// Add a type with a randomly generated definition to a random existing rec
18    /// group, or create a rec group when there are none (if `limits` allow).
19    fn add_type(
20        &mut self,
21        c: &mut Candidates<'_>,
22        types: &mut Types,
23        limits: &GcOpsLimits,
24    ) -> mutatis::Result<()> {
25        if c.shrink() || types.type_defs.len() >= usize::try_from(limits.max_types).unwrap() {
26            return Ok(());
27        }
28
29        if types.rec_groups.is_empty() && limits.max_rec_groups == 0 {
30            return Ok(());
31        }
32
33        c.mutation(|ctx| {
34            let gid = match ctx.rng().choose(types.rec_groups.keys()).copied() {
35                Some(gid) => gid,
36                None => {
37                    let new_gid = types.fresh_rec_group_id(ctx.rng());
38                    types.insert_rec_group(new_gid);
39                    new_gid
40                }
41            };
42
43            let tid = types.fresh_type_id(ctx.rng());
44            let def = m::default::<SubType>().generate(ctx)?;
45
46            types.insert_type(tid, gid, def.is_final, def.supertype, def.composite_type);
47            log::debug!("Added type {tid:?} to rec group {gid:?}");
48            Ok(())
49        })?;
50        Ok(())
51    }
52
53    /// Remove a random type from its rec group.
54    fn remove_type(&mut self, c: &mut Candidates<'_>, types: &mut Types) -> mutatis::Result<()> {
55        if types.type_defs.is_empty() {
56            return Ok(());
57        }
58        c.mutation(|ctx| {
59            let Some(tid) = ctx.rng().choose(types.type_defs.keys()).copied() else {
60                return Ok(());
61            };
62            types.remove_type(tid);
63            log::debug!("Removed type {tid:?}");
64            Ok(())
65        })?;
66        Ok(())
67    }
68
69    /// Swap two random types within a rec group.
70    fn swap_within_group(
71        &mut self,
72        c: &mut Candidates<'_>,
73        types: &mut Types,
74    ) -> mutatis::Result<()> {
75        if types.rec_groups.is_empty() || types.type_defs.len() <= 2 {
76            return Ok(());
77        }
78        c.mutation(|ctx| {
79            for _ in 0..16 {
80                let Some(gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
81                    return Ok(());
82                };
83
84                let Some(member_set) = types.rec_groups.get(&gid) else {
85                    continue;
86                };
87                let members: SmallVec<[TypeId; 32]> = member_set.iter().copied().collect();
88                if members.len() < 2 {
89                    continue;
90                }
91
92                let Some(tid_a) = ctx.rng().choose(&members).copied() else {
93                    return Ok(());
94                };
95                let Some(mut tid_b) = ctx.rng().choose(&members).copied() else {
96                    return Ok(());
97                };
98                for _ in 0..members.len() {
99                    if tid_a != tid_b {
100                        break;
101                    }
102                    let Some(next_tid) = ctx.rng().choose(&members).copied() else {
103                        return Ok(());
104                    };
105                    tid_b = next_tid;
106                }
107                if tid_a == tid_b {
108                    continue;
109                }
110
111                let Some(a_def) = types.type_defs.remove(&tid_a) else {
112                    return Ok(());
113                };
114                let Some(b_def) = types.type_defs.remove(&tid_b) else {
115                    types.type_defs.insert(tid_a, a_def);
116                    return Ok(());
117                };
118                types.type_defs.insert(tid_a, b_def);
119                types.type_defs.insert(tid_b, a_def);
120                log::debug!("Swapped types {tid_a:?} and {tid_b:?} in rec group {gid:?}");
121                return Ok(());
122            }
123            Ok(())
124        })?;
125        Ok(())
126    }
127
128    /// Move a random type from one rec group to another.
129    fn move_between_groups(
130        &mut self,
131        c: &mut Candidates<'_>,
132        types: &mut Types,
133    ) -> mutatis::Result<()> {
134        if types.rec_groups.len() < 2 {
135            return Ok(());
136        }
137        c.mutation(|ctx| {
138            let mut old_gid = None;
139            for _ in 0..16 {
140                let Some(gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
141                    return Ok(());
142                };
143                if types
144                    .rec_groups
145                    .get(&gid)
146                    .map(|s| !s.is_empty())
147                    .unwrap_or(false)
148                {
149                    old_gid = Some(gid);
150                    break;
151                }
152            }
153            let Some(old_gid) = old_gid else {
154                return Ok(());
155            };
156
157            let Some(tid) = types
158                .rec_groups
159                .get(&old_gid)
160                .and_then(|members| ctx.rng().choose(members.iter()).copied())
161            else {
162                return Ok(());
163            };
164
165            let Some(new_gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
166                return Ok(());
167            };
168
169            let Some(old_members) = types.rec_groups.get_mut(&old_gid) else {
170                return Ok(());
171            };
172            old_members.remove(&tid);
173            let Some(new_members) = types.rec_groups.get_mut(&new_gid) else {
174                return Ok(());
175            };
176            new_members.insert(tid);
177            log::debug!("Moved type {tid:?} from {old_gid:?} to {new_gid:?}");
178            Ok(())
179        })?;
180        Ok(())
181    }
182
183    /// Duplicate a rec group (copy its structure with fresh type ids).
184    fn duplicate_group(
185        &mut self,
186        c: &mut Candidates<'_>,
187        types: &mut Types,
188        limits: &GcOpsLimits,
189    ) -> mutatis::Result<()> {
190        if c.shrink()
191            || types.rec_groups.is_empty()
192            || types.rec_groups.len() >= usize::try_from(limits.max_rec_groups).unwrap()
193            || types.type_defs.len() >= usize::try_from(limits.max_types).unwrap()
194        {
195            return Ok(());
196        }
197        c.mutation(|ctx| {
198            let Some(src_gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
199                return Ok(());
200            };
201            let Some(src_members) = types.rec_groups.get(&src_gid) else {
202                return Ok(());
203            };
204            if src_members.is_empty() {
205                return Ok(());
206            }
207
208            // Snapshot the source group's members.
209            let members: SmallVec<[(TypeId, SubType); 32]> = src_members
210                .iter()
211                .filter_map(|tid| types.type_defs.get(tid).map(|def| (*tid, def.clone())))
212                .collect();
213
214            if members.is_empty() {
215                return Ok(());
216            }
217
218            // Create a new rec group.
219            let new_gid = types.fresh_rec_group_id(ctx.rng());
220            types.insert_rec_group(new_gid);
221
222            // Allocate fresh type ids for each member and build old-to-new map.
223            let mut old_to_new: BTreeMap<TypeId, TypeId> = BTreeMap::new();
224            for (old_tid, _) in &members {
225                old_to_new.insert(*old_tid, types.fresh_type_id(ctx.rng()));
226            }
227
228            // Insert duplicated defs, rewriting intra-group supertype edges to cloned ids.
229            for (old_tid, def) in &members {
230                let new_tid = old_to_new[old_tid];
231                let mapped_super = def.supertype.map(|st| *old_to_new.get(&st).unwrap_or(&st));
232                types.insert_type(
233                    new_tid,
234                    new_gid,
235                    def.is_final,
236                    mapped_super,
237                    def.composite_type.clone(),
238                );
239            }
240
241            log::debug!(
242                "Duplicated rec group {src_gid:?} as {new_gid:?} ({count} types)",
243                count = members.len()
244            );
245            Ok(())
246        })?;
247        Ok(())
248    }
249
250    /// Remove a whole rec group and all its member types.
251    fn remove_group(&mut self, c: &mut Candidates<'_>, types: &mut Types) -> mutatis::Result<()> {
252        if types.rec_groups.len() <= 2 {
253            return Ok(());
254        }
255        c.mutation(|ctx| {
256            let Some(gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
257                return Ok(());
258            };
259            let Some(members) = types.rec_groups.remove(&gid) else {
260                return Ok(());
261            };
262            for tid in &members {
263                types.type_defs.remove(tid);
264            }
265            log::debug!(
266                "Removed rec group {gid:?} and its {len} member types",
267                len = members.len()
268            );
269            Ok(())
270        })?;
271        Ok(())
272    }
273
274    /// Merge two rec groups into one.
275    fn merge_groups(&mut self, c: &mut Candidates<'_>, types: &mut Types) -> mutatis::Result<()> {
276        if types.rec_groups.len() <= 2 {
277            return Ok(());
278        }
279        c.mutation(|ctx| {
280            let Some(dst_gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
281                return Ok(());
282            };
283
284            // Find a distinct source group.
285            let mut src_gid = None;
286            for _ in 0..16 {
287                let Some(g) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
288                    return Ok(());
289                };
290                if g != dst_gid {
291                    src_gid = Some(g);
292                    break;
293                }
294            }
295            let Some(src_gid) = src_gid else {
296                return Ok(());
297            };
298
299            // Move all members from src into dst.
300            let Some(src_members) = types.rec_groups.remove(&src_gid) else {
301                return Ok(());
302            };
303            let Some(dst_members) = types.rec_groups.get_mut(&dst_gid) else {
304                return Ok(());
305            };
306            dst_members.extend(src_members.iter());
307            log::debug!("Merged rec group {src_gid:?} into {dst_gid:?}");
308            Ok(())
309        })?;
310        Ok(())
311    }
312
313    /// Split a rec group into two.
314    fn split_group(
315        &mut self,
316        c: &mut Candidates<'_>,
317        types: &mut Types,
318        limits: &GcOpsLimits,
319    ) -> mutatis::Result<()> {
320        if c.shrink()
321            || types.rec_groups.is_empty()
322            || types.type_defs.len() < 2
323            || types.rec_groups.len() >= usize::try_from(limits.max_rec_groups).unwrap()
324        {
325            return Ok(());
326        }
327        c.mutation(|ctx| {
328            // Find a group with >= 2 members.
329            let mut old_gid = None;
330            for _ in 0..16 {
331                let Some(gid) = ctx.rng().choose(types.rec_groups.keys()).copied() else {
332                    return Ok(());
333                };
334                if types.rec_groups.get(&gid).map(|s| s.len()).unwrap_or(0) >= 2 {
335                    old_gid = Some(gid);
336                    break;
337                }
338            }
339            let Some(old_gid) = old_gid else {
340                return Ok(());
341            };
342
343            let new_gid = types.fresh_rec_group_id(ctx.rng());
344            types.insert_rec_group(new_gid);
345
346            // Collect members so we can pick from them.
347            let Some(old_members) = types.rec_groups.get(&old_gid) else {
348                return Ok(());
349            };
350            let mut members: SmallVec<[TypeId; 32]> = old_members.iter().copied().collect();
351            let len = members.len();
352
353            // Choose k in [1, len-1] so both groups stay non-empty.
354            let Some(k_minus_1) = ctx.rng().gen_index(len - 1) else {
355                return Ok(());
356            };
357            let k = k_minus_1 + 1;
358
359            for _ in 0..k {
360                let Some(i) = ctx.rng().gen_index(members.len()) else {
361                    break;
362                };
363                let tid = members.remove(i);
364                let Some(old_members) = types.rec_groups.get_mut(&old_gid) else {
365                    return Ok(());
366                };
367                old_members.remove(&tid);
368                let Some(new_members) = types.rec_groups.get_mut(&new_gid) else {
369                    return Ok(());
370                };
371                new_members.insert(tid);
372            }
373
374            log::debug!("Split rec group {old_gid:?}: moved {k} of {len} members into {new_gid:?}");
375            Ok(())
376        })?;
377        Ok(())
378    }
379
380    /// Run all type / rec-group mutations. [`GcOpsLimits`] come from [`GcOps`].
381    fn mutate_with_limits(
382        &mut self,
383        c: &mut Candidates<'_>,
384        types: &mut Types,
385        limits: &GcOpsLimits,
386    ) -> mutatis::Result<()> {
387        self.add_type(c, types, limits)?;
388        self.remove_type(c, types)?;
389        self.swap_within_group(c, types)?;
390        self.move_between_groups(c, types)?;
391        self.duplicate_group(c, types, limits)?;
392        self.remove_group(c, types)?;
393        self.merge_groups(c, types)?;
394        self.split_group(c, types, limits)?;
395
396        // Add, remove, rename, and redefine individual types, then let `fixup`
397        // clean things up.
398        m::btree_map(m::default::<TypeId>(), m::default::<SubType>())
399            .mutate(c, &mut types.type_defs)?;
400
401        Ok(())
402    }
403}
404
405/// Mutator for `GcOps`.
406#[derive(Debug, Default)]
407pub struct GcOpsMutator {
408    /// Mutates the type definitions and rec groups.
409    types_mutator: TypesMutator,
410}
411
412impl Mutate<GcOp> for GcOpsMutator {
413    fn mutate(&mut self, c: &mut Candidates<'_>, value: &mut GcOp) -> MutResult<()> {
414        // The derived `GcOpMutator` is deliberately not `GcOp`'s default
415        // mutator: it offers one candidate per variant plus one per field, so
416        // across a test case's ops it would account for the overwhelming
417        // majority of the candidates and starve the type and rec-group
418        // mutations below. Every operand is an index that `fixup` normalizes
419        // anyway, so regenerating doesn't hurt.
420        c.mutation(|ctx| {
421            *value = GcOpMutator::default().generate(ctx)?;
422            Ok(())
423        })
424    }
425}
426
427impl Generate<GcOp> for GcOpsMutator {
428    fn generate(&mut self, ctx: &mut Context) -> MutResult<GcOp> {
429        GcOpMutator::default().generate(ctx)
430    }
431}
432
433impl DefaultMutate for GcOp {
434    type DefaultMutate = GcOpsMutator;
435}
436
437impl Mutate<GcOps> for GcOpsMutator {
438    fn mutate(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> MutResult<()> {
439        m::default::<GcOpsLimits>()
440            .map(|_ctx, limits: &mut GcOpsLimits| {
441                limits.fixup_limits();
442                Ok(())
443            })
444            .mutate(c, &mut ops.limits)?;
445        m::vec(m::default::<GcOp>()).mutate(c, &mut ops.ops)?;
446        self.types_mutator
447            .mutate_with_limits(c, &mut ops.types, &ops.limits)?;
448        Ok(())
449    }
450}
451
452impl DefaultMutate for GcOps {
453    type DefaultMutate = GcOpsMutator;
454}
455
456impl<'a> arbitrary::Arbitrary<'a> for GcOps {
457    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
458        let mut session = mutatis::Session::new().seed(u.arbitrary()?);
459        session
460            .generate()
461            .map_err(|_| arbitrary::Error::IncorrectFormat)
462    }
463}
464
465impl Generate<GcOps> for GcOpsMutator {
466    fn generate(&mut self, ctx: &mut Context) -> MutResult<GcOps> {
467        let mut ops = GcOps::default();
468        let mut session = mutatis::Session::new().seed(ctx.rng().gen_u64());
469        for _ in 0..2048 {
470            session.mutate(&mut ops)?;
471        }
472        Ok(ops)
473    }
474}
wasmtime_fuzzing/generators/gc_ops/mutator.rs

wasmtime_fuzzing/generators/gc_ops/
mutator.rs
