roaring_graphs/
delta_debugging_bitmap.rs

1use proptest::{
2    strategy::{Strategy, ValueTree},
3    test_runner::Reason,
4};
5use rand::{distributions::Uniform, prelude::Distribution, Rng};
6use roaring::RoaringBitmap;
7use std::{
8    cmp::{max, min},
9    ops::Range,
10};
11
12#[derive(Debug, Clone)]
13pub struct UniformBitProbabilityStrategy {
14    size: Range<u32>,
15    ones_probability: f64,
16}
17
18pub fn arb_bitmap_uniform(
19    size: impl Into<Range<u32>>,
20    ones_probability: f64,
21) -> UniformBitProbabilityStrategy {
22    UniformBitProbabilityStrategy {
23        size: size.into(),
24        ones_probability,
25    }
26}
27
28impl Strategy for UniformBitProbabilityStrategy {
29    type Tree = DeltaDebuggingBitmapValueTree;
30
31    type Value = RoaringBitmap;
32
33    fn new_tree(
34        &self,
35        runner: &mut proptest::test_runner::TestRunner,
36    ) -> proptest::strategy::NewTree<Self> {
37        // Copied out of self.size.assert_nonempty(), because that's private to proptest
38        if self.size.is_empty() {
39            panic!(
40                "Invalid use of empty size range. (hint: did you \
41                 accidentally write {}..{} where you meant {}..={} \
42                 somewhere?)",
43                self.size.start, self.size.end, self.size.start, self.size.end
44            );
45        }
46        if self.ones_probability < 0.0 || self.ones_probability > 1.0 {
47            panic!(
48                "Invalid propability set for generating ones. \
49                 Needs to be a number between 0 and 1, but got {}",
50                self.ones_probability
51            );
52        }
53        let size = Uniform::new(self.size.start, self.size.end - 1).sample(runner.rng());
54        let iter = (0..size as u32).filter(|_| runner.rng().gen_bool(self.ones_probability));
55        let bitmap =
56            RoaringBitmap::from_sorted_iter(iter).map_err(|e| Reason::from(e.to_string()))?;
57        Ok(DeltaDebuggingBitmapValueTree::new(bitmap))
58    }
59}
60
61/// This struct holds the state needed for an implementation of the
62/// [delta debugging] algorithm on bitmaps.
63///
64/// Together with proptest's shrinking code and the `ValueTree` implementation,
65/// this shrinks bitmaps in O(log(n)) time to a single bit causing a failure,
66/// or shrinks bitmaps in O(n²) time to exactly the bits causing the failure
67/// (more precisely: a set of bits where removing a single one of them will make
68/// the failure go away).
69///
70/// [delta debugging]: https://www.st.cs.uni-saarland.de/papers/tse2002/tse2002.pdf
71#[derive(Debug)]
72pub struct DeltaDebuggingBitmapValueTree {
73    upper: RoaringBitmap,
74    split_into: u64,
75    split_index: u64,
76    subset: SubsetState,
77}
78
79#[derive(Debug, Eq, PartialEq)]
80enum SubsetState {
81    CheckSubset,
82    CheckSubsetComplement,
83}
84
85impl SubsetState {
86    fn is_inside(&self, index: u64, split_index: u64, split_width: u64) -> bool {
87        let split_start = split_width * split_index;
88        let split_end = split_start + split_width;
89        let inside_split = split_start <= index && index < split_end;
90
91        match self {
92            Self::CheckSubset => inside_split,
93            Self::CheckSubsetComplement => !inside_split,
94        }
95    }
96}
97
98impl DeltaDebuggingBitmapValueTree {
99    pub fn new(bitmap: RoaringBitmap) -> Self {
100        // We initialize `split_index` to 1, so .current() returns
101        // `bitmap` initially.
102        Self {
103            upper: bitmap,
104            split_into: 1,
105            split_index: 0,
106            subset: SubsetState::CheckSubset,
107        }
108    }
109}
110
111impl ValueTree for DeltaDebuggingBitmapValueTree {
112    type Value = RoaringBitmap;
113
114    fn current(&self) -> Self::Value {
115        let mut current = RoaringBitmap::new();
116        let num_items = self.upper.len();
117        let split_width = num_items / self.split_into;
118
119        for (i, n) in self.upper.iter().enumerate() {
120            let idx = i as u64;
121
122            if self.subset.is_inside(idx, self.split_index, split_width) {
123                current.insert(n);
124            }
125        }
126
127        current
128    }
129
130    fn simplify(&mut self) -> bool {
131        // This is called when the test case failed (as it should during shrinking!)
132
133        let num_elems = self.upper.len();
134        if num_elems == 0 || num_elems == 1 {
135            return false;
136        }
137
138        self.upper = self.current();
139
140        match self.subset {
141            SubsetState::CheckSubset => {
142                if self.split_into == 1 {
143                    // We add a special case to test the empty set as early as possible
144                    self.subset = SubsetState::CheckSubsetComplement;
145                } else {
146                    // Successfully reduced to subset
147                    self.split_into = 2;
148                }
149            }
150            SubsetState::CheckSubsetComplement => {
151                // Successfully reduced to subset complement
152                self.split_into = max(self.split_into - 1, 2);
153                self.subset = SubsetState::CheckSubset;
154            }
155        }
156        self.split_into = max(1, min(self.split_into, self.upper.len()));
157        self.split_index = 0;
158        true
159    }
160
161    fn complicate(&mut self) -> bool {
162        // This is called when the test case didn't fail anymore.
163        // So we try shrinking somewhere else.
164        let num_elems = self.upper.len();
165        if num_elems == 0 {
166            return false;
167        }
168
169        self.split_index += 1;
170        if self.split_index < self.split_into {
171            return true;
172        }
173
174        // we went through all split indices
175        match self.subset {
176            SubsetState::CheckSubset => {
177                // We went through all split indices once for all subsets.
178                // Checking all of the subsets' complements remains.
179                self.subset = SubsetState::CheckSubsetComplement;
180                self.split_index = 0;
181                true
182            }
183            SubsetState::CheckSubsetComplement => {
184                // We went through all split indices twice:
185                // Once for all subsets, then for all of their complements.
186                // We need to try to increase granularity:
187                if self.split_into < num_elems {
188                    // Try it "twice as granular".
189                    // This is the binary search element that makes this algorithm efficient:
190                    self.split_into = min(num_elems, 2 * self.split_into);
191                    self.subset = SubsetState::CheckSubset;
192                    self.split_index = 0;
193                    true
194                } else {
195                    // We tried the smallest granularity (individual elements).
196                    // Nothing else we can do.
197                    false
198                }
199            }
200        }
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::DeltaDebuggingBitmapValueTree;
207    use proptest::{
208        collection::vec,
209        prelude::*,
210        strategy::ValueTree,
211        test_runner::{TestError, TestRunner},
212    };
213    use roaring::RoaringBitmap;
214
215    fn best_case_complexity(elems: u32) -> u32 {
216        2 * ((elems as f64).log2() as u32)
217    }
218
219    fn worst_case_complexity(elems: u32) -> u32 {
220        elems * elems + 3 * elems
221    }
222
223    fn runner_with_shrink_iters(max_shrink_iters: u32) -> TestRunner {
224        TestRunner::new(ProptestConfig {
225            max_shrink_iters,
226            ..Default::default()
227        })
228    }
229
230    #[test]
231    fn shrinks_to_nothing_immediately() {
232        // should shrink pretty much immedately
233        let mut runner = runner_with_shrink_iters(2);
234
235        let bitmap = RoaringBitmap::from_iter(0..100);
236        let tree = DeltaDebuggingBitmapValueTree::new(bitmap);
237
238        let result = runner.run_one(tree, |_| {
239            // Always fail
240            Err(TestCaseError::Fail("just because".into()))
241        });
242
243        assert_eq!(
244            result,
245            Err(TestError::Fail("just because".into(), RoaringBitmap::new()))
246        )
247    }
248
249    #[test]
250    fn initial_current_is_the_full_set() {
251        let bitmap = RoaringBitmap::from_iter(0..100);
252        let tree = DeltaDebuggingBitmapValueTree::new(bitmap.clone());
253        assert_eq!(tree.current(), bitmap);
254    }
255
256    const SMALL_SIZE: u32 = 1000;
257    const BIG_SIZE: u32 = 100_000;
258
259    proptest! {
260        #[test]
261        fn should_shrink_to_minimal_elements(error_bits in vec(0..SMALL_SIZE, 1..10)) {
262            let bitmap = RoaringBitmap::from_iter(0..SMALL_SIZE);
263            prop_assert!(error_bits.iter().all(|e| bitmap.contains(*e)));
264            let tree = DeltaDebuggingBitmapValueTree::new(bitmap);
265
266            // multiplying with a factor of 2 due to some weird proptest behaviour.
267            let mut runner = runner_with_shrink_iters(2 * worst_case_complexity(SMALL_SIZE));
268            let result = runner.run_one(tree, |bitmap| {
269                if error_bits.iter().all(|err_bit| bitmap.contains(*err_bit)) {
270                    Err(TestCaseError::Fail("contains all error bits".into()))
271                } else {
272                    Ok(())
273                }
274            });
275
276            let minimal_bitmap = RoaringBitmap::from_iter(error_bits.iter());
277            prop_assert_eq!(
278                result,
279                Err(TestError::Fail(
280                    "contains all error bits".into(),
281                    minimal_bitmap
282                ))
283            );
284        }
285
286        #[test]
287        fn test_best_case_complexity(error_bit in 0..BIG_SIZE) {
288            let bitmap = RoaringBitmap::from_iter(0..BIG_SIZE);
289            prop_assert!(bitmap.contains(error_bit));
290            let tree = DeltaDebuggingBitmapValueTree::new(bitmap);
291
292            // multiplying with a factor of 2 due to some weird proptest behaviour.
293            let mut runner = runner_with_shrink_iters(2 * best_case_complexity(BIG_SIZE));
294            let result = runner.run_one(tree, move |bitmap| {
295                if bitmap.contains(error_bit) {
296                    Err(TestCaseError::Fail("contains error bit".into()))
297                } else {
298                    Ok(())
299                }
300            });
301
302            prop_assert_eq!(
303                result,
304                Err(TestError::Fail("contains error bit".into(), RoaringBitmap::from([error_bit])))
305            );
306        }
307    }
308}
roaring_graphs/delta_debugging_bitmap.rs

roaring_graphs/
delta_debugging_bitmap.rs
