fuzzcheck_mutators/
vector.rs

1use crate::DefaultMutator;
2use fastrand::Rng;
3use fuzzcheck_traits::Mutator;
4
5use std::ops::Range;
6use std::{iter::repeat, marker::PhantomData};
7
8pub struct VecMutator<T: Clone, M: Mutator<T>> {
9    pub rng: Rng,
10    pub m: M,
11    _phantom: PhantomData<T>,
12}
13impl<T: Clone, M: Mutator<T>> VecMutator<T, M> {
14    pub fn new(mutator: M) -> Self {
15        Self {
16            rng: Rng::default(),
17            m: mutator,
18            _phantom: <_>::default(),
19        }
20    }
21}
22impl<T: Clone, M: Mutator<T>> Default for VecMutator<T, M>
23where
24    M: Default,
25{
26    fn default() -> Self {
27        Self {
28            rng: Rng::default(),
29            m: M::default(),
30            _phantom: <_>::default(),
31        }
32    }
33}
34impl<T: Clone> DefaultMutator for Vec<T>
35where
36    T: DefaultMutator,
37{
38    type Mutator = VecMutator<T, <T as DefaultMutator>::Mutator>;
39    fn default_mutator() -> Self::Mutator {
40        Self::Mutator::new(T::default_mutator())
41    }
42}
43
44#[derive(Clone)]
45pub struct MutationStep<S> {
46    inner: Vec<S>,
47    element_step: usize,
48}
49
50#[derive(Clone)]
51pub struct VecMutatorCache<C> {
52    inner: Vec<C>,
53    sum_cplx: f64,
54}
55impl<C> Default for VecMutatorCache<C> {
56    fn default() -> Self {
57        Self {
58            inner: Vec::new(),
59            sum_cplx: 0.0,
60        }
61    }
62}
63
64pub enum UnmutateVecToken<T: Clone, M: Mutator<T>> {
65    Element(usize, M::UnmutateToken, f64),
66    Remove(usize, f64),
67    RemoveMany(Range<usize>, f64),
68    Insert(usize, T, M::Cache),
69    InsertMany(usize, Vec<T>, <VecMutator<T, M> as Mutator<Vec<T>>>::Cache),
70    Replace(Vec<T>, <VecMutator<T, M> as Mutator<Vec<T>>>::Cache),
71    Nothing,
72}
73
74impl<T: Clone, M: Mutator<T>> VecMutator<T, M> {
75    fn mutate_element(
76        &self,
77        value: &mut Vec<T>,
78        cache: &mut VecMutatorCache<M::Cache>,
79        step: &mut MutationStep<M::MutationStep>,
80        idx: usize,
81        spare_cplx: f64,
82    ) -> Option<UnmutateVecToken<T, M>> {
83        let el = &mut value[idx];
84        let el_cache = &mut cache.inner[idx];
85        let el_step = &mut step.inner[idx];
86
87        let old_cplx = self.m.complexity(&el, el_cache);
88
89        if let Some(token) = self.m.ordered_mutate(el, el_cache, el_step, spare_cplx + old_cplx) {
90            let new_cplx = self.m.complexity(&el, el_cache);
91            cache.sum_cplx += new_cplx - old_cplx;
92            Some(UnmutateVecToken::Element(idx, token, old_cplx - new_cplx))
93        } else {
94            None
95        }
96    }
97
98    fn insert_element(
99        &self,
100        value: &mut Vec<T>,
101        cache: &mut VecMutatorCache<M::Cache>,
102        spare_cplx: f64,
103    ) -> Option<UnmutateVecToken<T, M>> {
104        let idx = if value.is_empty() {
105            0
106        } else {
107            self.rng.usize(0..value.len())
108        };
109
110        let (el, el_cache) = self.m.random_arbitrary(spare_cplx);
111        let el_cplx = self.m.complexity(&el, &el_cache);
112
113        value.insert(idx, el);
114        cache.inner.insert(idx, el_cache);
115
116        let token = UnmutateVecToken::Remove(idx, el_cplx);
117
118        cache.sum_cplx += el_cplx;
119
120        Some(token)
121    }
122
123    fn remove_element(
124        &self,
125        value: &mut Vec<T>,
126        cache: &mut VecMutatorCache<M::Cache>,
127    ) -> Option<UnmutateVecToken<T, M>> {
128        if value.is_empty() {
129            return None;
130        }
131
132        let idx = self.rng.usize(0..value.len());
133
134        let el = &value[idx];
135        let el_cplx = self.m.complexity(&el, &cache.inner[idx]);
136
137        let removed_el = value.remove(idx);
138        let removed_el_cache = cache.inner.remove(idx);
139
140        let token = UnmutateVecToken::Insert(idx, removed_el, removed_el_cache);
141
142        cache.sum_cplx -= el_cplx;
143
144        Some(token)
145    }
146
147    fn remove_many_elements(
148        &self,
149        value: &mut Vec<T>,
150        cache: &mut VecMutatorCache<M::Cache>,
151    ) -> Option<UnmutateVecToken<T, M>> {
152        if value.is_empty() {
153            return None;
154        }
155        let start_idx = if value.len() == 1 {
156            0
157        } else {
158            self.rng.usize(0..value.len() - 1)
159        };
160        let end_idx = std::cmp::min(value.len(), start_idx + self.rng.usize(1..10));
161        let (removed_elements, removed_cache) = {
162            let removed_elements: Vec<_> = value.drain(start_idx..end_idx).collect();
163            let removed_cache: Vec<_> = cache.inner.drain(start_idx..end_idx).collect();
164            (removed_elements, removed_cache)
165        };
166        let removed_els_cplx = removed_elements
167            .iter()
168            .zip(removed_cache.iter())
169            .fold(0.0, |cplx, (v, c)| self.m.complexity(&v, &c) + cplx);
170
171        let removed_cache = VecMutatorCache {
172            inner: removed_cache,
173            sum_cplx: removed_els_cplx,
174        };
175
176        let token = UnmutateVecToken::InsertMany(start_idx, removed_elements, removed_cache);
177
178        cache.sum_cplx -= removed_els_cplx;
179
180        Some(token)
181    }
182
183    fn insert_repeated_elements(
184        &self,
185        value: &mut Vec<T>,
186        cache: &mut VecMutatorCache<M::Cache>,
187        spare_cplx: f64,
188    ) -> Option<UnmutateVecToken<T, M>> {
189        if spare_cplx < 0.01 {
190            return None;
191        }
192
193        let idx = if value.is_empty() {
194            0
195        } else {
196            self.rng.usize(0..value.len())
197        };
198
199        let target_cplx = crate::gen_f64(
200            &self.rng,
201            0.0..crate::gen_f64(
202                &self.rng,
203                0.0..crate::gen_f64(&self.rng, 0.0..crate::gen_f64(&self.rng, 0.0..spare_cplx)),
204            ),
205        );
206        let (min_length, max_length) = self.choose_slice_length(target_cplx);
207        let min_length = min_length.unwrap_or(0);
208
209        let len = if min_length >= max_length {
210            min_length
211        } else {
212            self.rng.usize(min_length..max_length)
213        };
214        if len == 0 {
215            // TODO: maybe that shouldn't happen under normal circumstances?
216            return None;
217        }
218        // println!("len: {:.2}", len);
219        // println!("max_cplx: {:.2}", target_cplx / (len as f64));
220        let (el, el_cache) = self.m.random_arbitrary(target_cplx / (len as f64));
221        let el_cplx = self.m.complexity(&el, &el_cache);
222
223        insert_many(value, idx, repeat(el).take(len));
224        insert_many(&mut cache.inner, idx, repeat(el_cache).take(len));
225
226        let added_cplx = el_cplx * (len as f64);
227        cache.sum_cplx += added_cplx;
228
229        let token = UnmutateVecToken::RemoveMany(idx..(idx + len), added_cplx);
230
231        Some(token)
232    }
233
234    fn choose_slice_length(&self, target_cplx: f64) -> (Option<usize>, usize) {
235        let min_cplx_el = self.m.min_complexity();
236
237        // slight underestimate of the maximum number of elements required to produce an input of max_cplx
238        let max_len_most_complex = {
239            let overestimated_max_len: f64 = target_cplx / min_cplx_el;
240            let max_len = if overestimated_max_len.is_infinite() {
241                // min_cplx_el is 0, so the max length is the maximum complexity of the length component of the vector
242                crate::cplxity_to_size(target_cplx)
243            } else {
244                // an underestimate of the true max_length, but not by much
245                (overestimated_max_len - overestimated_max_len.log2()) as usize
246            };
247            if max_len > 10_000 {
248                /* TODO */
249                // 10_000?
250                target_cplx.trunc() as usize
251            } else {
252                max_len
253            }
254        };
255        let max_cplx_el = self.m.max_complexity();
256        // slight underestimate of the minimum number of elements required to produce an input of max_cplx
257        // will be inf. if elements can be of infinite complexity
258        // or if elements are of max_cplx 0.0
259        let min_len_most_complex = target_cplx / max_cplx_el - (target_cplx / max_cplx_el).log2();
260
261        // arbitrary restriction on the length of the generated number, to avoid creating absurdly large vectors
262        // of very simple elements, that take up too much memory
263        let max_len_most_complex = if max_len_most_complex > 10_000 {
264            /* TODO */
265            // 10_000?
266            target_cplx.trunc() as usize
267        } else {
268            max_len_most_complex
269        };
270
271        if !min_len_most_complex.is_finite() {
272            (None, max_len_most_complex)
273        } else {
274            let min_len_most_complex = min_len_most_complex.trunc() as usize;
275            (Some(min_len_most_complex), max_len_most_complex)
276        }
277    }
278
279    fn new_input_with_length_and_complexity(
280        &self,
281        target_len: usize,
282        target_cplx: f64,
283    ) -> (Vec<T>, <Self as Mutator<Vec<T>>>::Cache) {
284        // TODO: create a new_input_with_complexity method
285        let mut v = Vec::with_capacity(target_len);
286        let mut cache = VecMutatorCache {
287            inner: Vec::with_capacity(target_len),
288            sum_cplx: 0.0,
289        };
290
291        let mut remaining_cplx = target_cplx;
292        for i in 0..target_len {
293            let max_cplx_element = remaining_cplx / ((target_len - i) as f64);
294            let min_cplx_el = self.m.min_complexity();
295            if min_cplx_el >= max_cplx_element {
296                break;
297            }
298            let cplx_element = crate::gen_f64(&self.rng, min_cplx_el..max_cplx_element);
299            let (x, x_cache) = self.m.random_arbitrary(cplx_element);
300            let x_cplx = self.m.complexity(&x, &x_cache);
301            v.push(x);
302            cache.inner.push(x_cache);
303            cache.sum_cplx += x_cplx;
304            remaining_cplx -= x_cplx;
305        }
306        (v, cache)
307    }
308}
309
310impl<T: Clone, M: Mutator<T>> Mutator<Vec<T>> for VecMutator<T, M> {
311    type Cache = VecMutatorCache<M::Cache>;
312    type MutationStep = MutationStep<M::MutationStep>;
313    type ArbitraryStep = bool; // false: check empty vector, true: random
314    type UnmutateToken = UnmutateVecToken<T, M>;
315
316    fn cache_from_value(&self, value: &Vec<T>) -> Self::Cache {
317        let inner: Vec<_> = value.iter().map(|x| self.m.cache_from_value(&x)).collect();
318
319        let sum_cplx = value
320            .iter()
321            .zip(inner.iter())
322            .fold(0.0, |cplx, (v, cache)| cplx + self.m.complexity(&v, cache));
323
324        VecMutatorCache { inner, sum_cplx }
325    }
326
327    fn initial_step_from_value(&self, value: &Vec<T>) -> Self::MutationStep {
328        let inner: Vec<_> = value.iter().map(|x| self.m.initial_step_from_value(&x)).collect();
329        MutationStep { inner, element_step: 0 }
330    }
331
332    fn max_complexity(&self) -> f64 {
333        std::f64::INFINITY
334    }
335
336    fn min_complexity(&self) -> f64 {
337        1.0
338    }
339
340    fn complexity(&self, value: &Vec<T>, cache: &Self::Cache) -> f64 {
341        1.0 + cache.sum_cplx + crate::size_to_cplxity(value.len() + 1)
342    }
343
344    fn ordered_arbitrary(&self, step: &mut Self::ArbitraryStep, max_cplx: f64) -> Option<(Vec<T>, Self::Cache)> {
345        if max_cplx < self.min_complexity() {
346            return None;
347        }
348        if !*step || max_cplx <= 1.0 {
349            *step = true;
350            return Some((<_>::default(), Self::Cache::default()));
351        } else {
352            return Some(self.random_arbitrary(max_cplx));
353        }
354    }
355
356    fn random_arbitrary(&self, max_cplx: f64) -> (Vec<T>, Self::Cache) {
357        let target_cplx = fastrand::f64() * crate::gen_f64(&self.rng, 0.0..max_cplx);
358        let lengths = self.choose_slice_length(target_cplx);
359
360        if lengths.0.is_none() && self.m.max_complexity() < 0.001 {
361            // distinguish between the case where elements are of max_cplx 0 and the case where they are of max_cplx inf.
362            // in this case, the elements are always of cplx 0, so we can only vary the length of the vector
363            // that's not true!!!
364            if lengths.1 <= 0 {
365                return (<_>::default(), Self::Cache::default());
366            }
367            assert!(lengths.1 > 0);
368            let len = self.rng.usize(0..lengths.1);
369            let (el, el_cache) = self.m.random_arbitrary(0.0);
370            let v = repeat(el).take(len).collect();
371            let cache = Self::Cache {
372                inner: repeat(el_cache).take(len).collect(),
373                sum_cplx: 0.0,
374            };
375            return (v, cache);
376        }
377        let (min_length, max_length) = (lengths.0.unwrap_or(0), lengths.1);
378
379        // choose a length between min_len_most_complex and max_len_most_complex
380        let target_len = if min_length >= max_length {
381            min_length
382        } else {
383            self.rng.usize(min_length..max_length)
384        };
385
386        self.new_input_with_length_and_complexity(target_len, target_cplx)
387    }
388
389    fn ordered_mutate(
390        &self,
391        value: &mut Vec<T>,
392        cache: &mut Self::Cache,
393        step: &mut Self::MutationStep,
394        max_cplx: f64,
395    ) -> Option<Self::UnmutateToken> {
396        // Some(self.random_mutate(value, cache, max_cplx))
397        if max_cplx < self.min_complexity() {
398            return None;
399        }
400        let spare_cplx = max_cplx - self.complexity(value, cache);
401
402        let token = if value.is_empty() || self.rng.usize(0..20) == 0 {
403            // vector mutation
404            match self.rng.usize(0..10) {
405                0..=3 => self.insert_element(value, cache, spare_cplx),
406                4..=7 => self.remove_element(value, cache),
407                8 => self.insert_repeated_elements(value, cache, spare_cplx),
408                9 => self.remove_many_elements(value, cache),
409                _ => unreachable!(),
410            }
411        } else {
412            // element mutation
413            let idx = step.element_step % value.len();
414            step.element_step += 1;
415            self.mutate_element(value, cache, step, idx, spare_cplx)
416        };
417        if let Some(token) = token {
418            Some(token)
419        } else {
420            Some(self.random_mutate(value, cache, max_cplx))
421        }
422    }
423
424    fn random_mutate(&self, value: &mut Vec<T>, cache: &mut Self::Cache, max_cplx: f64) -> Self::UnmutateToken {
425        let spare_cplx = max_cplx - self.complexity(value, cache);
426
427        if value.is_empty() || self.rng.usize(0..10) == 0 {
428            // vector mutation
429            match self.rng.usize(0..10) {
430                0..=3 => self.insert_element(value, cache, spare_cplx),
431                4..=7 => self.remove_element(value, cache),
432                8 => self.insert_repeated_elements(value, cache, spare_cplx),
433                9 => self.remove_many_elements(value, cache),
434                _ => unreachable!(),
435            }
436            .unwrap_or_else(|| self.random_mutate(value, cache, max_cplx))
437        } else {
438            // element mutation
439            let idx = self.rng.usize(0..value.len());
440            let el = &mut value[idx];
441            let el_cache = &mut cache.inner[idx];
442
443            let old_el_cplx = self.m.complexity(&el, el_cache);
444            let token = self.m.random_mutate(el, el_cache, spare_cplx + old_el_cplx);
445
446            let new_el_cplx = self.m.complexity(&el, el_cache);
447            cache.sum_cplx += new_el_cplx - old_el_cplx;
448            UnmutateVecToken::Element(idx, token, old_el_cplx - new_el_cplx)
449        }
450    }
451
452    fn unmutate(&self, value: &mut Vec<T>, cache: &mut Self::Cache, t: Self::UnmutateToken) {
453        match t {
454            UnmutateVecToken::Element(idx, inner_t, diff_cplx) => {
455                let el = &mut value[idx];
456                let el_cache = &mut cache.inner[idx];
457                self.m.unmutate(el, el_cache, inner_t);
458                cache.sum_cplx += diff_cplx;
459            }
460            UnmutateVecToken::Insert(idx, el, el_cache) => {
461                cache.sum_cplx += self.m.complexity(&el, &el_cache);
462
463                value.insert(idx, el);
464                cache.inner.insert(idx, el_cache);
465            }
466            UnmutateVecToken::Remove(idx, el_cplx) => {
467                value.remove(idx);
468                cache.inner.remove(idx);
469                cache.sum_cplx -= el_cplx;
470            }
471            UnmutateVecToken::Replace(new_value, new_cache) => {
472                // M::ValueConversion::replace(value, new_value);
473                let _ = std::mem::replace(value, new_value);
474                let _ = std::mem::replace(cache, new_cache);
475            }
476            UnmutateVecToken::InsertMany(idx, v, c) => {
477                insert_many(value, idx, v.into_iter());
478                insert_many(&mut cache.inner, idx, c.inner.into_iter());
479                let added_cplx = c.sum_cplx;
480                cache.sum_cplx += added_cplx;
481            }
482            UnmutateVecToken::RemoveMany(range, cplx) => {
483                value.drain(range.clone());
484                cache.inner.drain(range);
485                cache.sum_cplx -= cplx;
486            }
487            UnmutateVecToken::Nothing => {}
488        }
489    }
490}
491
492fn insert_many<T>(v: &mut Vec<T>, idx: usize, iter: impl Iterator<Item = T>) {
493    let moved_slice = v.drain(idx..).collect::<Vec<T>>().into_iter();
494    v.extend(iter);
495    v.extend(moved_slice);
496}
fuzzcheck_mutators/vector.rs

fuzzcheck_mutators/
vector.rs
