1 //! Mutators for the `gc` operations.
2 
3 use crate::generators::gc_ops::ops::{GcOp, GcOps};
4 use crate::generators::gc_ops::types::{RecGroupId, TypeId};
5 use mutatis::{Candidates, Context, DefaultMutate, Generate, Mutate, Result as MutResult};
6 use smallvec::SmallVec;
7 
8 /// A mutator for the gc ops.
9 #[derive(Debug)]
10 pub struct GcOpsMutator;
11 
12 impl GcOpsMutator {
13     // Define a mutation that adds an operation to the ops list.
14     fn add_operation(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
15         if c.shrink() {
16             return Ok(());
17         }
18         c.mutation(|ctx| {
19             if let Some(idx) = ctx.rng().gen_index(ops.ops.len() + 1) {
20                 let op = GcOp::generate(ctx)?;
21                 ops.ops.insert(idx, op);
22                 log::debug!("Added operation {op:?} to ops list");
23             }
24             Ok(())
25         })?;
26         Ok(())
27     }
28 
29     // Define a mutation that removes an operation from the ops list.
30     fn remove_operation(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
31         if ops.ops.is_empty() {
32             return Ok(());
33         }
34         c.mutation(|ctx| {
35             let idx = ctx.rng().gen_index(ops.ops.len()).expect("ops not empty");
36             let removed = ops.ops.remove(idx);
37             log::debug!("Removed operation {removed:?} from ops list");
38             Ok(())
39         })?;
40         Ok(())
41     }
42 
43     // Define a mutation that adds an empty struct type to an existing (rec ...) group.
44     fn add_new_struct_type_to_rec_group(
45         &mut self,
46         c: &mut Candidates<'_>,
47         ops: &mut GcOps,
48     ) -> mutatis::Result<()> {
49         if c.shrink()
50             || ops.types.rec_groups.is_empty()
51             || ops.types.type_defs.len() >= usize::try_from(ops.limits.max_types).unwrap()
52         {
53             return Ok(());
54         }
55         c.mutation(|ctx| {
56             let group_id = ctx
57                 .rng()
58                 .choose(&ops.types.rec_groups)
59                 .copied()
60                 .expect("rec_groups not empty");
61             let new_tid = ops.types.fresh_type_id(ctx.rng());
62             ops.types.insert_empty_struct(new_tid, group_id);
63             log::debug!("Added empty struct type {new_tid:?} to rec group {group_id:?}");
64             Ok(())
65         })?;
66         Ok(())
67     }
68 
69     // Define a mutation that removes a struct type from an existing (rec ...).
70     // It may result in empty rec groups. Empty rec groups are allowed.
71     fn remove_struct_type_from_rec_group(
72         &mut self,
73         c: &mut Candidates<'_>,
74         ops: &mut GcOps,
75     ) -> mutatis::Result<()> {
76         if ops.types.type_defs.is_empty() {
77             return Ok(());
78         }
79         c.mutation(|ctx| {
80             let tid = ctx
81                 .rng()
82                 .choose(ops.types.type_defs.keys())
83                 .copied()
84                 .expect("type_defs not empty");
85             ops.types.type_defs.remove(&tid);
86             log::debug!("Removed struct type {tid:?}");
87             Ok(())
88         })?;
89         Ok(())
90     }
91 
92     // Define a mutation that moves a struct type within an existing rec group.
93     fn move_struct_type_within_rec_group(
94         &mut self,
95         c: &mut Candidates<'_>,
96         ops: &mut GcOps,
97     ) -> mutatis::Result<()> {
98         if ops.types.rec_groups.is_empty() || ops.types.type_defs.len() < 2 {
99             return Ok(());
100         }
101         c.mutation(|ctx| {
102             let mut chosen: Option<(RecGroupId, TypeId, TypeId)> = None;
103 
104             // Randomly choose a rec group.
105             for _ in 0..ops.limits.max_rec_groups {
106                 let gid = ctx
107                     .rng()
108                     .choose(&ops.types.rec_groups)
109                     .copied()
110                     .expect("rec_groups not empty");
111 
112                 // Collect member TypeIds of that rec group.
113                 let mut members: SmallVec<[TypeId; 32]> = SmallVec::new();
114                 for (tid, def) in ops.types.type_defs.iter() {
115                     if def.rec_group == gid {
116                         members.push(*tid);
117                     }
118                 }
119 
120                 // If this is a singleton/empty group, try another rec group.
121                 if members.len() < 2 {
122                     continue;
123                 }
124 
125                 // Pick two distinct members randomly.
126                 let tid_a = *ctx.rng().choose(&members).expect("len >= 2");
127                 let mut tid_b = *ctx.rng().choose(&members).expect("len >= 2");
128                 for _ in 0..members.len() {
129                     if tid_a != tid_b {
130                         break;
131                     }
132                     tid_b = *ctx.rng().choose(&members).unwrap();
133                 }
134                 if tid_a == tid_b {
135                     continue;
136                 }
137                 chosen = Some((gid, tid_a, tid_b));
138                 break;
139             }
140 
141             // Move within group - reorder for encoding by swapping map values.
142             if let Some((gid, tid_a, tid_b)) = chosen {
143                 let a_def = ops.types.type_defs.remove(&tid_a).expect("tid_a present");
144                 let b_def = ops.types.type_defs.remove(&tid_b).expect("tid_b present");
145                 debug_assert!(a_def.rec_group == gid);
146                 debug_assert!(b_def.rec_group == gid);
147                 ops.types.type_defs.insert(tid_a, b_def);
148                 ops.types.type_defs.insert(tid_b, a_def);
149                 log::debug!("Reordered types {tid_a:?} and {tid_b:?} in rec group {gid:?}");
150             }
151 
152             Ok(())
153         })?;
154         Ok(())
155     }
156 
157     // Define a mutation that moves a struct type from one (rec ...) group to another.
158     // It will be a different rec group with high probability but it may try
159     // to move it to the same rec group.
160     fn move_struct_type_between_rec_groups(
161         &mut self,
162         c: &mut Candidates<'_>,
163         ops: &mut GcOps,
164     ) -> mutatis::Result<()> {
165         if ops.types.type_defs.is_empty() || ops.types.rec_groups.len() < 2 {
166             return Ok(());
167         }
168         c.mutation(|ctx| {
169             let tid = ctx
170                 .rng()
171                 .choose(ops.types.type_defs.keys())
172                 .copied()
173                 .expect("type_defs not empty");
174             let new_gid = ctx
175                 .rng()
176                 .choose(&ops.types.rec_groups)
177                 .copied()
178                 .expect("rec_groups not empty");
179             let old_gid = ops.types.type_defs.get(&tid).unwrap().rec_group;
180             ops.types.type_defs.get_mut(&tid).unwrap().rec_group = new_gid;
181             log::debug!("Moved type {tid:?} from rec group {old_gid:?} to {new_gid:?}");
182             Ok(())
183         })?;
184         Ok(())
185     }
186 
187     // Define a mutation that duplicates a (rec ...) group.
188     fn duplicate_rec_group(
189         &mut self,
190         c: &mut Candidates<'_>,
191         ops: &mut GcOps,
192     ) -> mutatis::Result<()> {
193         if c.shrink()
194             || ops.types.rec_groups.is_empty()
195             || ops.types.rec_groups.len() >= usize::try_from(ops.limits.max_rec_groups).unwrap()
196             || ops.types.type_defs.len() >= usize::try_from(ops.limits.max_types).unwrap()
197         {
198             return Ok(());
199         }
200         c.mutation(|ctx| {
201             let source_gid = ctx
202                 .rng()
203                 .choose(&ops.types.rec_groups)
204                 .copied()
205                 .expect("rec_groups not empty");
206 
207             // Create a new rec group.
208             let new_gid = ops.types.fresh_rec_group_id(ctx.rng());
209             ops.types.insert_rec_group(new_gid);
210 
211             let count = ops
212                 .types
213                 .type_defs
214                 .values()
215                 .filter(|def| def.rec_group == source_gid)
216                 .count();
217 
218             // Skip empty rec groups.
219             if count == 0 {
220                 return Ok(());
221             }
222 
223             // Since our structs are empty, we can just insert them into the new rec group.
224             // We will update mutators while adding new features to the fuzzer.
225             for _ in 0..count {
226                 ops.types
227                     .insert_empty_struct(ops.types.fresh_type_id(ctx.rng()), new_gid);
228             }
229 
230             log::debug!(
231                 "Duplicated rec group {source_gid:?} as new group {new_gid:?} ({count} types)"
232             );
233             Ok(())
234         })?;
235         Ok(())
236     }
237 
238     // Define a mutation that removes a whole (rec ...) group.
239     fn remove_rec_group(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
240         if ops.types.rec_groups.len() <= 2 {
241             return Ok(());
242         }
243         c.mutation(|ctx| {
244             let gid = ctx
245                 .rng()
246                 .choose(&ops.types.rec_groups)
247                 .copied()
248                 .expect("rec_groups not empty");
249 
250             ops.types.type_defs.retain(|_, def| def.rec_group != gid);
251             ops.types.rec_groups.remove(&gid);
252 
253             log::debug!("Removed rec group {gid:?} and its member types");
254             Ok(())
255         })?;
256         Ok(())
257     }
258 
259     // Define a mutation that merges two (rec ...) groups.
260     fn merge_rec_groups(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
261         if ops.types.rec_groups.is_empty() || ops.types.rec_groups.len() <= 2 {
262             return Ok(());
263         }
264         c.mutation(|ctx| {
265             let dst_gid = ctx
266                 .rng()
267                 .choose(&ops.types.rec_groups)
268                 .copied()
269                 .expect("rec_groups not empty");
270 
271             let mut src_gid = None;
272             for _ in 0..16 {
273                 let g = ctx
274                     .rng()
275                     .choose(&ops.types.rec_groups)
276                     .copied()
277                     .expect("rec_groups not empty");
278 
279                 if g != dst_gid {
280                     src_gid = Some(g);
281                     break;
282                 }
283             }
284 
285             let Some(src_gid) = src_gid else {
286                 // Could not find a distinct group (should be very unlikely with len>2).
287                 return Ok(());
288             };
289 
290             // Collect all members of src_gid.
291             let mut members: SmallVec<[TypeId; 32]> = SmallVec::new();
292             for (tid, def) in ops.types.type_defs.iter() {
293                 if def.rec_group == src_gid {
294                     members.push(*tid);
295                 }
296             }
297 
298             // Move all types from src_gid into dst_gid.
299             for tid in members {
300                 if let Some(def) = ops.types.type_defs.get_mut(&tid) {
301                     def.rec_group = dst_gid;
302                 }
303             }
304 
305             // Remove the now-merged-away group id.
306             ops.types.rec_groups.remove(&src_gid);
307             log::debug!("Merged rec group {src_gid:?} into {dst_gid:?}");
308 
309             Ok(())
310         })?;
311         Ok(())
312     }
313 
314     // Define a mutation that splits a (rec ...) group in two, if possible.
315     fn split_rec_group(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
316         if c.shrink()
317             || ops.types.rec_groups.len() >= usize::try_from(ops.limits.max_rec_groups).unwrap()
318             || ops.types.type_defs.len() < 2
319         {
320             return Ok(());
321         }
322         c.mutation(|ctx| {
323             // Pick a rec group with at least 2 members.
324             let mut old_gid = None;
325             let mut members: SmallVec<[TypeId; 32]> = SmallVec::new();
326 
327             for _ in 0..16 {
328                 let gid = ctx
329                     .rng()
330                     .choose(&ops.types.rec_groups)
331                     .copied()
332                     .expect("rec_groups not empty");
333 
334                 members.clear();
335                 for (tid, def) in ops.types.type_defs.iter() {
336                     if def.rec_group == gid {
337                         members.push(*tid);
338                     }
339                 }
340 
341                 if members.len() >= 2 {
342                     old_gid = Some(gid);
343                     break;
344                 }
345             }
346 
347             let Some(old_gid) = old_gid else {
348                 return Ok(());
349             };
350 
351             // Create a new rec group.
352             let new_gid = ops.types.fresh_rec_group_id(ctx.rng());
353             ops.types.insert_rec_group(new_gid);
354 
355             // Choose k in [1, len-1] (so both groups remain non-empty).
356             let len = members.len();
357             let Some(k_minus_1) = ctx.rng().gen_index(len - 1) else {
358                 return Ok(());
359             };
360             let k = k_minus_1 + 1;
361 
362             // Move k distinct members by removing them from `members` as we pick.
363             for _ in 0..k {
364                 let Some(i) = ctx.rng().gen_index(members.len()) else {
365                     break;
366                 };
367                 let tid = members.remove(i);
368                 if let Some(def) = ops.types.type_defs.get_mut(&tid) {
369                     def.rec_group = new_gid;
370                 }
371             }
372 
373             log::debug!(
374                 "Split rec group {old_gid:?}: moved {k} of {len} members into new group {new_gid:?}"
375             );
376             Ok(())
377         })?;
378         Ok(())
379     }
380 }
381 
382 impl Mutate<GcOps> for GcOpsMutator {
383     fn mutate(&mut self, c: &mut Candidates<'_>, ops: &mut GcOps) -> mutatis::Result<()> {
384         self.add_operation(c, ops)?;
385         self.remove_operation(c, ops)?;
386         self.add_new_struct_type_to_rec_group(c, ops)?;
387         self.remove_struct_type_from_rec_group(c, ops)?;
388         self.move_struct_type_within_rec_group(c, ops)?;
389         self.move_struct_type_between_rec_groups(c, ops)?;
390         self.duplicate_rec_group(c, ops)?;
391         self.remove_rec_group(c, ops)?;
392         self.merge_rec_groups(c, ops)?;
393         self.split_rec_group(c, ops)?;
394 
395         Ok(())
396     }
397 }
398 
399 impl DefaultMutate for GcOps {
400     type DefaultMutate = GcOpsMutator;
401 }
402 
403 impl Default for GcOpsMutator {
404     fn default() -> Self {
405         GcOpsMutator
406     }
407 }
408 
409 impl<'a> arbitrary::Arbitrary<'a> for GcOps {
410     fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
411         let mut session = mutatis::Session::new().seed(u.arbitrary()?);
412         session
413             .generate()
414             .map_err(|_| arbitrary::Error::IncorrectFormat)
415     }
416 }
417 
418 impl Generate<GcOps> for GcOpsMutator {
419     fn generate(&mut self, _ctx: &mut Context) -> MutResult<GcOps> {
420         let mut ops = GcOps::default();
421         let mut session = mutatis::Session::new();
422 
423         for _ in 0..64 {
424             session.mutate(&mut ops)?;
425         }
426 
427         Ok(ops)
428     }
429 }
430