fuzzcheck/mutators/
unique.rs

1use std::any::Any;
2use std::cell::{Cell, RefCell};
3use std::hash::Hash;
4use std::marker::PhantomData;
5use std::rc::Rc;
6
7use crate::bloom_filter::BloomFilter;
8use crate::Mutator;
9
10const SIZE_BLOOM: usize = 10_000_000;
11const FALSE_POSITIVE_RATE: f64 = 0.000_001;
12
13/// Experimental mutator which tries to prevent a value from being tested more
14/// than once (using a bloom filter).
15///
16/// **Important:** this mutator cannot be used as a submutator.
17pub struct UniqueMutator<T, TH, Focus, M>
18where
19    T: Clone + 'static,
20    TH: Hash,
21    M: Mutator<T>,
22    Focus: Fn(&T) -> &TH,
23{
24    mutator: M,
25    uniques: Rc<RefCell<BloomFilter<TH>>>,
26    nbr_inserted: Cell<usize>,
27    focus: Focus,
28    _phantom: PhantomData<T>,
29}
30
31impl<T, TH, Focus, M> UniqueMutator<T, TH, Focus, M>
32where
33    T: Clone + 'static,
34    TH: Hash,
35    M: Mutator<T>,
36    Focus: Fn(&T) -> &TH,
37{
38    /// Create a new `UniqueMutator` by wrapping another mutator.
39    ///
40    /// The `Focus` closure points to the hashable part of the value. This should almost always
41    /// be the identity function. But there is an exception when we don't care about some part
42    /// of the generated value. For example, a grammar-based mutator implements `Mutator<(AST, String)>`,
43    /// but it is very likely that the test function will only operate on the String and not the AST.
44    /// In that case, the `Focus` closure is `|x| &x.1`.
45    #[coverage(off)]
46    pub fn new(mutator: M, focus: Focus) -> Self {
47        Self {
48            mutator,
49            uniques: Rc::new(RefCell::new(BloomFilter::new(SIZE_BLOOM, FALSE_POSITIVE_RATE))),
50            nbr_inserted: <_>::default(),
51            focus,
52            _phantom: <_>::default(),
53        }
54    }
55}
56impl<T, TH, Focus, M> UniqueMutator<T, TH, Focus, M>
57where
58    T: Clone + 'static,
59    TH: Hash,
60    M: Mutator<T>,
61    Focus: Fn(&T) -> &TH,
62    Self: 'static,
63{
64    #[coverage(off)]
65    fn clear_if_needed(&self) {
66        if self.nbr_inserted.get() >= SIZE_BLOOM {
67            let bitmap = &mut self.uniques.borrow_mut().bitmap;
68            bitmap.clear();
69            self.nbr_inserted.set(0);
70        }
71    }
72}
73impl<T, TH, Focus, M> Mutator<T> for UniqueMutator<T, TH, Focus, M>
74where
75    T: Clone + 'static,
76    TH: Hash,
77    M: Mutator<T>,
78    Focus: Fn(&T) -> &TH,
79    Self: 'static,
80{
81    type Cache = M::Cache;
82    type MutationStep = M::MutationStep;
83    type ArbitraryStep = M::ArbitraryStep;
84    type UnmutateToken = M::UnmutateToken;
85
86    #[coverage(off)]
87    fn initialize(&self) {
88        self.mutator.initialize();
89    }
90
91    #[coverage(off)]
92    fn default_arbitrary_step(&self) -> Self::ArbitraryStep {
93        self.mutator.default_arbitrary_step()
94    }
95
96    #[coverage(off)]
97    fn is_valid(&self, value: &T) -> bool {
98        self.mutator.is_valid(value)
99    }
100
101    #[coverage(off)]
102    fn validate_value(&self, value: &T) -> Option<Self::Cache> {
103        self.mutator.validate_value(value)
104    }
105    #[coverage(off)]
106    fn default_mutation_step(&self, value: &T, cache: &Self::Cache) -> Self::MutationStep {
107        self.mutator.default_mutation_step(value, cache)
108    }
109
110    #[doc(hidden)]
111    #[coverage(off)]
112    fn global_search_space_complexity(&self) -> f64 {
113        self.mutator.global_search_space_complexity()
114    }
115
116    #[coverage(off)]
117    fn max_complexity(&self) -> f64 {
118        self.mutator.max_complexity()
119    }
120
121    #[coverage(off)]
122    fn min_complexity(&self) -> f64 {
123        self.mutator.min_complexity()
124    }
125
126    #[coverage(off)]
127    fn complexity(&self, value: &T, cache: &Self::Cache) -> f64 {
128        self.mutator.complexity(value, cache)
129    }
130
131    #[coverage(off)]
132    fn ordered_arbitrary(&self, step: &mut Self::ArbitraryStep, max_cplx: f64) -> Option<(T, f64)> {
133        self.clear_if_needed();
134        loop {
135            if let Some((v, cplx)) = self.mutator.ordered_arbitrary(step, max_cplx) {
136                let mut uniques = self.uniques.borrow_mut();
137                let focused = (self.focus)(&v);
138                if uniques.contains(focused) {
139                    drop(uniques);
140                } else {
141                    uniques.insert(focused);
142                    let prev_inserted = self.nbr_inserted.get();
143                    self.nbr_inserted.set(prev_inserted + 1);
144                    return Some((v, cplx));
145                }
146            } else {
147                return None;
148            }
149        }
150    }
151
152    #[coverage(off)]
153    fn random_arbitrary(&self, _max_cplx: f64) -> (T, f64) {
154        panic!()
155    }
156
157    #[coverage(off)]
158    fn ordered_mutate(
159        &self,
160        value: &mut T,
161        cache: &mut Self::Cache,
162        step: &mut Self::MutationStep,
163        subvalue_provider: &dyn crate::SubValueProvider,
164        max_cplx: f64,
165    ) -> Option<(Self::UnmutateToken, f64)> {
166        self.clear_if_needed();
167        loop {
168            if let Some((t, cplx)) = self
169                .mutator
170                .ordered_mutate(value, cache, step, subvalue_provider, max_cplx)
171            {
172                let mut uniques = self.uniques.borrow_mut();
173                let focused = (self.focus)(value);
174                if uniques.contains(focused) || cplx >= max_cplx {
175                    drop(uniques);
176                    self.unmutate(value, cache, t);
177                } else {
178                    uniques.insert(focused);
179                    let prev_inserted = self.nbr_inserted.get();
180                    self.nbr_inserted.set(prev_inserted + 1);
181                    return Some((t, cplx));
182                }
183            } else {
184                return None;
185            }
186        }
187    }
188
189    #[coverage(off)]
190    fn random_mutate(&self, value: &mut T, cache: &mut Self::Cache, max_cplx: f64) -> (Self::UnmutateToken, f64) {
191        self.clear_if_needed();
192        for _ in 0..20 {
193            let (t, cplx) = self.mutator.random_mutate(value, cache, max_cplx);
194            let mut uniques = self.uniques.borrow_mut();
195            let focused = (self.focus)(value);
196            if uniques.contains(focused) || cplx >= max_cplx {
197                drop(uniques);
198                self.unmutate(value, cache, t);
199            } else {
200                uniques.insert(focused);
201                let prev_inserted = self.nbr_inserted.get();
202                self.nbr_inserted.set(prev_inserted + 1);
203                return (t, cplx);
204            }
205        }
206        self.mutator.random_mutate(value, cache, max_cplx)
207    }
208
209    #[coverage(off)]
210    fn unmutate(&self, value: &mut T, cache: &mut Self::Cache, t: Self::UnmutateToken) {
211        self.mutator.unmutate(value, cache, t)
212    }
213
214    #[coverage(off)]
215    fn visit_subvalues<'a>(&self, value: &'a T, cache: &'a Self::Cache, visit: &mut dyn FnMut(&'a dyn Any, f64)) {
216        self.mutator.visit_subvalues(value, cache, visit)
217    }
218}
fuzzcheck/mutators/unique.rs

fuzzcheck/mutators/
unique.rs
