robust_binary_search/
lib.rs

1// Copyright 2020 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use log::trace;
16use std::borrow::Borrow;
17use std::cmp;
18use std::rc::Rc;
19
20mod flakiness_tracker;
21use flakiness_tracker::*;
22mod range_map;
23use range_map::*;
24
25mod dag;
26
27/// Reference to a node in a CompressedDAG.
28#[derive(Default, Copy, Clone, Debug, PartialEq, Eq)]
29pub struct CompressedDAGNodeRef {
30    /// Index of the segment in the CompressedDAG.
31    pub segment: usize,
32    /// Index of the expanded node within the segment.
33    pub index: usize,
34}
35
36/// A segment in a CompressedDAG. This is a node in a DAG but corresponds to a linear sequence of
37/// nodes in a conceptual expanded graph. The size is the number of nodes in the expanded graph
38/// represented by this segment.
39#[derive(Clone, Debug)]
40pub struct CompressedDAGSegment {
41    len: usize,
42}
43
44impl CompressedDAGSegment {
45    /// Creates a CompressedDAGSegment of a given size.
46    pub fn new(len: usize) -> Self {
47        CompressedDAGSegment { len }
48    }
49
50    /// Returns the size of the segment.
51    pub fn len(&self) -> usize {
52        self.len
53    }
54}
55
56/// A DAG whose nodes are CompressedDAGSegments, which represent sequences of nodes in a conceptual
57/// expanded graph. For example, given the graph:
58///
59/// ```text
60///   B-C-D
61///  /     \
62/// A       G
63///  \     /
64///   E---F
65/// ```
66///
67/// this can be expressed in a CompressedDAG as:
68///
69/// ```text
70///   B'
71///  / \
72/// A'  G'
73///  \ /
74///   E'
75/// ```
76///
77/// where `A'` and `G'` are segments of size 1 corresponding to `A` and `G`, `E'` is a segment of
78/// size 2 corresponding to `E` and `F`, and `B'` is a segment of size 3 corresponding to `B`, `C`,
79/// and `D`.
80///
81/// More formally, the nodes represented by a segment must be in a linear formation (i.e. directed,
82/// acyclic, connected, with each node having at most one incoming edge from another node in the
83/// segment and at most one outgoing edge to another node in the segment), with only the first node
84/// allowing edges from outside the segment, and only the last node allowing edges to outside the
85/// segment.
86///
87/// This representation allows many common graphs to be represented in a more compact form than
88/// directly as a DAG.
89pub type CompressedDAG = dag::DAG<CompressedDAGSegment>;
90
91mod compressed_dag_flakiness_tracker;
92use compressed_dag_flakiness_tracker::*;
93
94/// Finds the index such that the sum of values at indices [0, i] (inclusive) is as close as
95/// possible to the argument. Returns the index and the sum.
96fn confidence_percentile_nearest(range_map: &RangeMap<f64>, percentile: f64) -> (usize, f64) {
97    let mut sum = 0.0;
98    let mut index = 0;
99    let mut best_index = 0;
100    let mut best_percentile = f64::NEG_INFINITY;
101    for w in range_map.ranges() {
102        let delta = w.len() as f64 * w.value();
103        trace!(
104            "percentile = {}, sum = {}, w.value = {}",
105            percentile,
106            sum,
107            w.value()
108        );
109        trace!(
110            "(percentile - sum) / w.value() - 0.5 = {}",
111            (percentile - sum) / w.value() - 0.5
112        );
113        let ix = index
114            + cmp::min(
115                w.len() - 1,
116                ((percentile - sum) / w.value() - 0.5).max(0.0) as usize,
117            );
118        let ix_percentile = sum + (ix - index + 1) as f64 * w.value();
119        trace!("ix = {} ix_percentile = {}", ix, ix_percentile);
120        if (ix_percentile - percentile).abs() < (best_percentile - percentile).abs() {
121            best_index = ix;
122            best_percentile = ix_percentile;
123        }
124        sum += delta;
125        index += w.len();
126    }
127    assert!(best_percentile > f64::NEG_INFINITY);
128    trace!(
129        "confidence_percentile_nearest returning {:?}",
130        (best_index, best_percentile)
131    );
132    (best_index, best_percentile)
133}
134
135/// Finds the smallest index such that the sum of values at indices [0, i] (inclusive) is greater
136/// than or equal to the argument. Returns the index and the sum. If no sum is greater than or equal
137/// to the argument, returns the last index and the sum over all values.
138fn confidence_percentile_ceil(range_map: &RangeMap<f64>, percentile: f64) -> (usize, f64) {
139    let mut sum = 0.0;
140    let mut index = 0;
141    for w in range_map.ranges() {
142        let delta = w.len() as f64 * w.value();
143        if sum + delta >= percentile {
144            let ix = index + ((percentile - sum) / w.value() - 1e-9) as usize;
145            let ret = (ix, sum + (ix - index + 1) as f64 * w.value());
146            trace!("confidence_percentile_ceil returning {:?}", ret);
147            return ret;
148        }
149        sum += delta;
150        index += w.len();
151    }
152    (range_map.len() - 1, sum)
153}
154
155// Does not normalize.
156fn report_range(weights: &mut RangeMap<f64>, index: usize, heads: bool, stiffness: f64) {
157    if heads {
158        for w in weights.split(index).0 {
159            *w.value_mut() *= 1.0 + stiffness;
160        }
161        let (left, _right) = weights.split(index + 1);
162        *left.rev().next().unwrap().value_mut() *= 1.0 + stiffness;
163    } else {
164        weights.split(index);
165        let (_left, right) = weights.split(index + 1);
166        for w in right {
167            *w.value_mut() *= 1.0 + stiffness;
168        }
169    }
170}
171
172/// Performs a robust binary search over a linear range.
173#[derive(Clone, Debug)]
174pub struct Searcher {
175    weights: RangeMap<f64>,
176    len: usize,
177}
178
179impl Searcher {
180    /// Creates a new Searcher over a range with the given number of testable indices.
181    pub fn new(len: usize) -> Self {
182        Searcher {
183            weights: RangeMap::new(len + 1, 1.0 / (len as f64 + 1.0)),
184            len,
185        }
186    }
187
188    /// Same as `report` but with a specified stiffness. Only public for use by the tuner, not for
189    /// public use.
190    ///
191    /// # Panics
192    ///
193    /// Panics if `index >= len`.
194    #[doc(hidden)]
195    pub fn report_with_stiffness(&mut self, index: usize, heads: bool, stiffness: f64) {
196        assert!(index < self.len);
197        report_range(&mut self.weights, index, heads, stiffness);
198        let weight_sum: f64 = self
199            .weights
200            .ranges()
201            .map(|w| w.value() * w.len() as f64)
202            .sum();
203        for w in self.weights.ranges_mut() {
204            *w.value_mut() /= weight_sum;
205        }
206    }
207
208    /// Adds a vote to the internal statistics. With low flakiness, false votes are expected to have
209    /// smaller indices than true votes.
210    ///
211    /// # Panics
212    ///
213    /// Panics if `index >= len`.
214    pub fn report(&mut self, index: usize, heads: bool, flakiness: f64) {
215        self.report_with_stiffness(index, heads, optimal_stiffness(flakiness));
216    }
217
218    /// Returns the next index that should be tested. Can return values in the range 0 to len,
219    /// exclusive.
220    pub fn next_index(&self) -> usize {
221        cmp::min(
222            confidence_percentile_nearest(&self.weights, 0.5).0,
223            self.len - 1,
224        )
225    }
226
227    /// Returns the current estimate of the best index. Can return values in the range 0 to len,
228    /// inclusive.
229    pub fn best_index(&self) -> usize {
230        confidence_percentile_ceil(&self.weights, 0.5).0
231    }
232
233    /// Only public for use by the tuner, not for public use.
234    #[doc(hidden)]
235    pub fn confidence_percentile_ceil(&self, percentile: f64) -> usize {
236        confidence_percentile_ceil(&self.weights, percentile).0
237    }
238
239    /// Returns the likelihood of the given index.
240    ///
241    /// # Panics
242    ///
243    /// Panics if `index > len`.
244    pub fn likelihood(&self, index: usize) -> f64 {
245        *self.weights.range_for_index(index).value()
246    }
247}
248
249/// Returns the stiffness which should be optimal for the given flakiness.
250fn optimal_stiffness(flakiness: f64) -> f64 {
251    // Values calculated by tuner.rs
252    (2.6 / flakiness.powf(0.37))
253        .min(0.58 / flakiness.powf(0.97))
254        .min(0.19 / flakiness.powf(2.4))
255}
256
257/// Performs a robust binary search over a linear range and automatically infers the flakiness based
258/// on the votes.
259#[derive(Clone, Debug)]
260pub struct AutoSearcher {
261    searcher: Searcher,
262    flakiness_tracker: FlakinessTracker,
263}
264
265impl AutoSearcher {
266    /// Creates a new AutoSearcher over a range with the given number of testable indices.
267    pub fn new(len: usize) -> Self {
268        AutoSearcher {
269            searcher: Searcher::new(len),
270            flakiness_tracker: FlakinessTracker::default(),
271        }
272    }
273
274    /// Adds a vote to the internal statistics. With low flakiness, false votes are expected to have
275    /// smaller indices than true votes.
276    ///
277    /// # Panics
278    ///
279    /// Panics if `index >= len`.
280    pub fn report(&mut self, index: usize, heads: bool) {
281        self.flakiness_tracker.report(index, heads);
282        self.searcher
283            .report(index, heads, self.flakiness_tracker.flakiness());
284    }
285
286    /// Returns the next index that should be tested. Can return values in the range 0 to len,
287    /// exclusive.
288    pub fn next_index(&self) -> usize {
289        self.searcher.next_index()
290    }
291
292    /// Returns the current estimate of the best index. Can return values in the range 0 to len,
293    /// inclusive.
294    pub fn best_index(&self) -> usize {
295        self.searcher.best_index()
296    }
297
298    /// Returns the likelihood of the given index.
299    ///
300    /// # Panics
301    ///
302    /// Panics if `index > len`.
303    pub fn likelihood(&self, index: usize) -> f64 {
304        self.searcher.likelihood(index)
305    }
306}
307
308/// Performs a robust binary search over a CompressedDAG.
309#[derive(Clone, Debug)]
310pub struct CompressedDAGSearcher {
311    graph: Rc<CompressedDAG>,
312    segment_range_maps: Vec<RangeMap<f64>>,
313}
314
315impl CompressedDAGSearcher {
316    /// Creates a new CompressedDAGSearcher.
317    pub fn new(graph: Rc<CompressedDAG>) -> Self {
318        let n = graph
319            .nodes()
320            .iter()
321            .map(|node| node.value().len())
322            .fold(0, |x, y| x + y);
323        let segment_range_maps = graph
324            .nodes()
325            .iter()
326            .map(|node| RangeMap::new(node.value().len(), 1.0 / n as f64))
327            .collect();
328        CompressedDAGSearcher {
329            graph,
330            segment_range_maps,
331        }
332    }
333
334    /// Returns the sums at the beginning and end of every segment. Each vector entry corresponds to
335    /// a single segment. The first entry in the tuple is the sum of all weights in the segment's
336    /// ancestors (i.e. source segments will have a start of 0.0), and the second entry is the sum
337    /// of all weights in the segment and its ancestors.
338    fn segment_percentile_ranges(&self) -> Vec<(f64, f64)> {
339        let mut segment_ranges = Vec::<(f64, f64)>::new();
340        let mut segment_sums = Vec::<f64>::new();
341        let graph: &CompressedDAG = self.graph.borrow();
342        for (i, range_map) in self.segment_range_maps.iter().enumerate() {
343            let inputs = graph.node(i).inputs();
344            let start = if inputs.is_empty() {
345                0.0
346            } else {
347                let mut start = segment_ranges[inputs[0]].1;
348                for ancestor in graph.node(i).remainder_ancestors() {
349                    start += segment_sums[*ancestor];
350                }
351                start
352            };
353            let mut segment_sum = 0.0;
354            for range in range_map.ranges() {
355                segment_sum += range.value() * range.len() as f64;
356            }
357            segment_sums.push(segment_sum);
358            let end = start + segment_sum;
359            assert!(
360                start >= 0.0 && start <= 1.0 + 1e-11 && end >= 0.0 && end <= 1.0 + 1e-11,
361                "i = {} of {}, start = {}, end = {}",
362                i,
363                self.segment_range_maps.len(),
364                start,
365                end
366            );
367            segment_ranges.push((start, end));
368        }
369        segment_ranges
370    }
371
372    /// Returns the node whose percentile (i.e. the sum of weights over the node and its ancestors)
373    /// is nearest the argument.
374    fn confidence_percentile_nearest(&self, percentile: f64) -> CompressedDAGNodeRef {
375        let segment_ranges = self.segment_percentile_ranges();
376        trace!("segment_ranges = {:?}", segment_ranges);
377        let mut best_node = CompressedDAGNodeRef {
378            segment: 0,
379            index: 0,
380        };
381        let mut best_value = f64::NEG_INFINITY;
382        for (i, range) in segment_ranges.iter().enumerate() {
383            let (ix, mut value) =
384                confidence_percentile_nearest(&self.segment_range_maps[i], percentile - range.0);
385            value += range.0;
386            if (percentile - value).abs() < (percentile - best_value).abs() {
387                best_node = CompressedDAGNodeRef {
388                    segment: i,
389                    index: ix,
390                };
391                best_value = value;
392            }
393        }
394        assert!(best_value > f64::NEG_INFINITY);
395        best_node
396    }
397
398    /// Returns the node whose percentile (i.e. the sum of weights over the node and its ancestors)
399    /// is smallest but greater than or equal to the argument.
400    pub fn confidence_percentile_ceil(&self, percentile: f64) -> CompressedDAGNodeRef {
401        let segment_ranges = self.segment_percentile_ranges();
402        let mut min_end = 0;
403        let mut min_end_segment = 0;
404        let mut min_end_value = f64::INFINITY;
405        for (i, range) in segment_ranges.iter().enumerate() {
406            let (ix, mut value) =
407                confidence_percentile_ceil(&self.segment_range_maps[i], percentile - range.0);
408            value += range.0;
409            trace!(
410                "i = {}, ix = {}, value = {}, min_end_value = {}",
411                i,
412                ix,
413                value,
414                min_end_value
415            );
416            if value < min_end_value && value >= percentile {
417                min_end = ix;
418                min_end_segment = i;
419                min_end_value = value;
420            }
421        }
422        let ret = CompressedDAGNodeRef {
423            segment: min_end_segment,
424            index: min_end,
425        };
426        trace!(
427            "CompressedDAGSearcher::confidence_percentile_ceil returning {:?}",
428            ret
429        );
430        ret
431    }
432
433    /// Returns the current estimate of the best node.
434    pub fn best_node(&self) -> CompressedDAGNodeRef {
435        self.confidence_percentile_ceil(0.5)
436    }
437
438    /// Returns the next node that should be tested.
439    pub fn next_node(&self) -> CompressedDAGNodeRef {
440        self.confidence_percentile_nearest(0.5)
441    }
442
443    /// Adds a vote to the internal statistics. With low flakiness, nodes with false votes are
444    /// expected not to nodes with true votes as ancestors.
445    ///
446    /// # Panics
447    ///
448    /// Panics if the node is out of range.
449    pub fn report(&mut self, node: CompressedDAGNodeRef, heads: bool, flakiness: f64) {
450        let stiffness = optimal_stiffness(flakiness);
451        let graph: &CompressedDAG = self.graph.borrow();
452        if heads {
453            for segment in graph.node(node.segment).ancestors() {
454                for w in self.segment_range_maps[*segment].ranges_mut() {
455                    *w.value_mut() *= 1.0 + stiffness;
456                }
457            }
458        } else {
459            let ancestor_segments = graph.node(node.segment).ancestors();
460            for segment in 0..graph.nodes().len() {
461                if ancestor_segments.contains(&segment) || segment == node.segment {
462                    continue;
463                }
464                for w in self.segment_range_maps[segment].ranges_mut() {
465                    *w.value_mut() *= 1.0 + stiffness;
466                }
467            }
468        }
469        report_range(
470            &mut self.segment_range_maps[node.segment],
471            node.index,
472            heads,
473            stiffness,
474        );
475        let weight_sum: f64 = self
476            .segment_range_maps
477            .iter()
478            .map(|range_map| {
479                range_map
480                    .ranges()
481                    .map(|w| w.value() * w.len() as f64)
482                    .sum::<f64>()
483            })
484            .sum();
485        for range_map in &mut self.segment_range_maps {
486            for w in range_map.ranges_mut() {
487                *w.value_mut() /= weight_sum;
488            }
489        }
490    }
491
492    /// Returns the likelihood of the given index.
493    ///
494    /// # Panics
495    ///
496    /// Panics if the node is out of range.
497    pub fn likelihood(&self, node: CompressedDAGNodeRef) -> f64 {
498        *self.segment_range_maps[node.segment]
499            .range_for_index(node.index)
500            .value()
501    }
502}
503
504/// Performs a robust binary search over a CompressedDAG and automatically infers the flakiness
505/// based on the votes.
506#[derive(Clone, Debug)]
507pub struct AutoCompressedDAGSearcher {
508    searcher: CompressedDAGSearcher,
509    flakiness_tracker: CompressedDAGFlakinessTracker,
510}
511
512impl AutoCompressedDAGSearcher {
513    /// Creates a new AutoCompressedDAGSearcher.
514    pub fn new(graph: Rc<CompressedDAG>) -> Self {
515        Self {
516            searcher: CompressedDAGSearcher::new(graph.clone()),
517            flakiness_tracker: CompressedDAGFlakinessTracker::new(graph),
518        }
519    }
520
521    /// Adds a vote to the internal statistics. With low flakiness, nodes with false votes are
522    /// expected not to nodes with true votes as ancestors.
523    ///
524    /// # Panics
525    ///
526    /// Panics if the node is out of range.
527    pub fn report(&mut self, node: CompressedDAGNodeRef, heads: bool) {
528        self.flakiness_tracker.report(node, heads);
529        self.searcher
530            .report(node, heads, self.flakiness_tracker.flakiness());
531    }
532
533    /// Returns the next node that should be tested.
534    pub fn next_node(&self) -> CompressedDAGNodeRef {
535        self.searcher.next_node()
536    }
537
538    /// Returns the current estimate of the best node.
539    pub fn best_node(&self) -> CompressedDAGNodeRef {
540        self.searcher.best_node()
541    }
542
543    /// Returns the likelihood of the given index.
544    ///
545    /// # Panics
546    ///
547    /// Panics if the node is out of range.
548    pub fn likelihood(&self, index: CompressedDAGNodeRef) -> f64 {
549        self.searcher.likelihood(index)
550    }
551
552    /// Returns the estimated flakiness.
553    pub fn flakiness(&self) -> f64 {
554        self.flakiness_tracker.flakiness()
555    }
556}
557
558#[cfg(test)]
559mod tests {
560    use super::*;
561
562    const DEFAULT_FLAKINESS: f64 = 0.01;
563
564    macro_rules! assert_index {
565        ($searcher:expr, $next:expr, $best:expr, $heads:expr, $flakiness:expr) => {
566            assert_eq!($searcher.next_index(), $next, "next_index");
567            assert_eq!($searcher.best_index(), $best, "best_index");
568            $searcher.report($next, $heads, $flakiness);
569        };
570    }
571
572    // Each test should run until a cycle repeats itself three times, and the
573    // best_index is stable. The cycle may consist of a single element.
574
575    #[test]
576    fn one_element_zero() {
577        let mut s = Searcher::new(1);
578        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
579        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
580        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
581    }
582
583    #[test]
584    fn one_element_one() {
585        let mut s = Searcher::new(1);
586        assert_index!(s, 0, 0, false, DEFAULT_FLAKINESS);
587        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
588        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
589        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
590    }
591
592    #[test]
593    fn two_elements_zero() {
594        let mut s = Searcher::new(2);
595        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
596        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
597        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
598        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
599        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
600    }
601
602    #[test]
603    fn two_elements_one() {
604        let mut s = Searcher::new(2);
605        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
606        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
607        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
608        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
609        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
610        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
611        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
612        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
613        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
614        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
615    }
616
617    #[test]
618    fn two_elements_two() {
619        let mut s = Searcher::new(2);
620        assert_index!(s, 1, 1, false, DEFAULT_FLAKINESS);
621        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
622        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
623        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
624    }
625
626    #[test]
627    fn three_elements_zero() {
628        let mut s = Searcher::new(3);
629        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
630        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
631        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
632        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
633        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
634    }
635
636    #[test]
637    fn three_elements_one() {
638        let mut s = Searcher::new(3);
639        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
640        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
641        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
642        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
643        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
644        assert_index!(s, 0, 1, false, DEFAULT_FLAKINESS);
645    }
646
647    #[test]
648    fn three_elements_two() {
649        let mut s = Searcher::new(3);
650        assert_index!(s, 1, 1, false, DEFAULT_FLAKINESS);
651        assert_index!(s, 2, 2, true, DEFAULT_FLAKINESS);
652        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
653        assert_index!(s, 2, 2, true, DEFAULT_FLAKINESS);
654        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
655        assert_index!(s, 2, 2, true, DEFAULT_FLAKINESS);
656        assert_index!(s, 1, 2, false, DEFAULT_FLAKINESS);
657    }
658
659    #[test]
660    fn three_elements_three() {
661        let mut s = Searcher::new(3);
662        assert_index!(s, 1, 1, false, DEFAULT_FLAKINESS);
663        assert_index!(s, 2, 2, false, DEFAULT_FLAKINESS);
664        assert_index!(s, 2, 3, false, DEFAULT_FLAKINESS);
665        assert_index!(s, 2, 3, false, DEFAULT_FLAKINESS);
666        assert_index!(s, 2, 3, false, DEFAULT_FLAKINESS);
667    }
668
669    #[test]
670    fn many_elements_first() {
671        let mut s = Searcher::new(1024);
672        assert_index!(s, 512, 512, true, DEFAULT_FLAKINESS);
673        assert_index!(s, 272, 273, true, DEFAULT_FLAKINESS);
674        assert_index!(s, 144, 145, true, DEFAULT_FLAKINESS);
675        assert_index!(s, 76, 77, true, DEFAULT_FLAKINESS);
676        assert_index!(s, 40, 41, true, DEFAULT_FLAKINESS);
677        assert_index!(s, 21, 21, true, DEFAULT_FLAKINESS);
678        assert_index!(s, 11, 11, true, DEFAULT_FLAKINESS);
679        assert_index!(s, 5, 6, true, DEFAULT_FLAKINESS);
680        assert_index!(s, 2, 3, true, DEFAULT_FLAKINESS);
681        assert_index!(s, 1, 1, true, DEFAULT_FLAKINESS);
682        assert_index!(s, 0, 1, true, DEFAULT_FLAKINESS);
683        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
684        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
685        assert_index!(s, 0, 0, true, DEFAULT_FLAKINESS);
686    }
687
688    #[test]
689    fn many_elements_last() {
690        let mut s = Searcher::new(1024);
691        assert_index!(s, 512, 512, false, DEFAULT_FLAKINESS);
692        assert_index!(s, 751, 752, false, DEFAULT_FLAKINESS);
693        assert_index!(s, 879, 879, false, DEFAULT_FLAKINESS);
694        assert_index!(s, 947, 947, false, DEFAULT_FLAKINESS);
695        assert_index!(s, 983, 983, false, DEFAULT_FLAKINESS);
696        assert_index!(s, 1002, 1003, false, DEFAULT_FLAKINESS);
697        assert_index!(s, 1012, 1013, false, DEFAULT_FLAKINESS);
698        assert_index!(s, 1018, 1018, false, DEFAULT_FLAKINESS);
699        assert_index!(s, 1021, 1021, false, DEFAULT_FLAKINESS);
700        assert_index!(s, 1022, 1023, false, DEFAULT_FLAKINESS);
701        assert_index!(s, 1023, 1023, false, DEFAULT_FLAKINESS);
702        assert_index!(s, 1023, 1024, false, DEFAULT_FLAKINESS);
703        assert_index!(s, 1023, 1024, false, DEFAULT_FLAKINESS);
704        assert_index!(s, 1023, 1024, false, DEFAULT_FLAKINESS);
705    }
706
707    #[test]
708    fn graph_confidence_percentile_nearest_singleton() {
709        let mut graph = CompressedDAG::new();
710        graph.add_node(CompressedDAGSegment::new(1), vec![]);
711        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
712        assert_eq!(
713            searcher.confidence_percentile_nearest(0.5),
714            CompressedDAGNodeRef {
715                segment: 0,
716                index: 0
717            }
718        );
719    }
720
721    #[test]
722    fn graph_confidence_percentile_nearest_single_segment() {
723        let mut graph = CompressedDAG::new();
724        graph.add_node(CompressedDAGSegment::new(10), vec![]);
725        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
726        assert_eq!(
727            searcher.confidence_percentile_nearest(0.5),
728            CompressedDAGNodeRef {
729                segment: 0,
730                index: 4
731            }
732        );
733    }
734
735    #[test]
736    fn graph_confidence_percentile_nearest_parallel_segments() {
737        let mut graph = CompressedDAG::new();
738        graph.add_node(CompressedDAGSegment::new(10), vec![]);
739        graph.add_node(CompressedDAGSegment::new(10), vec![]);
740        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
741        assert_eq!(
742            searcher.confidence_percentile_nearest(0.5),
743            CompressedDAGNodeRef {
744                segment: 0,
745                index: 9
746            }
747        );
748    }
749
750    #[test]
751    fn graph_confidence_percentile_nearest_parallel_unequal_segments() {
752        let mut graph = CompressedDAG::new();
753        graph.add_node(CompressedDAGSegment::new(100), vec![]);
754        graph.add_node(CompressedDAGSegment::new(10), vec![]);
755        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
756        assert_eq!(
757            searcher.confidence_percentile_nearest(0.5),
758            CompressedDAGNodeRef {
759                segment: 0,
760                index: 54
761            }
762        );
763    }
764
765    #[test]
766    fn graph_confidence_percentile_nearest_parallel_unequal_segments2() {
767        let mut graph = CompressedDAG::new();
768        graph.add_node(CompressedDAGSegment::new(10), vec![]);
769        graph.add_node(CompressedDAGSegment::new(100), vec![]);
770        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
771        assert_eq!(
772            searcher.confidence_percentile_nearest(0.5),
773            CompressedDAGNodeRef {
774                segment: 1,
775                index: 54
776            }
777        );
778    }
779
780    #[test]
781    fn graph_confidence_percentile_nearest_sequential_segments() {
782        let mut graph = CompressedDAG::new();
783        graph.add_node(CompressedDAGSegment::new(10), vec![]);
784        graph.add_node(CompressedDAGSegment::new(10), vec![0]);
785        graph.add_node(CompressedDAGSegment::new(10), vec![1]);
786        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
787        assert_eq!(
788            searcher.confidence_percentile_nearest(0.5),
789            CompressedDAGNodeRef {
790                segment: 1,
791                index: 4
792            }
793        );
794    }
795
796    #[test]
797    fn graph_confidence_percentile_nearest_fork() {
798        let mut graph = CompressedDAG::new();
799        graph.add_node(CompressedDAGSegment::new(10), vec![]);
800        graph.add_node(CompressedDAGSegment::new(10), vec![0]);
801        graph.add_node(CompressedDAGSegment::new(10), vec![0]);
802        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
803        assert_eq!(
804            searcher.confidence_percentile_nearest(0.5),
805            CompressedDAGNodeRef {
806                segment: 1,
807                index: 4
808            }
809        );
810    }
811
812    #[test]
813    fn graph_confidence_percentile_nearest_merge() {
814        let mut graph = CompressedDAG::new();
815        graph.add_node(CompressedDAGSegment::new(10), vec![]);
816        graph.add_node(CompressedDAGSegment::new(10), vec![]);
817        graph.add_node(CompressedDAGSegment::new(10), vec![0, 1]);
818        let searcher = CompressedDAGSearcher::new(Rc::new(graph));
819        assert_eq!(
820            searcher.confidence_percentile_nearest(0.5),
821            CompressedDAGNodeRef {
822                segment: 0,
823                index: 9
824            }
825        );
826    }
827
828    macro_rules! assert_graph_index {
829        ($searcher:expr, $next:expr, $best:expr, $heads:expr, $flakiness:expr) => {
830            assert_eq!(
831                $searcher.next_node(),
832                CompressedDAGNodeRef {
833                    segment: $next.0,
834                    index: $next.1
835                },
836                "next_index"
837            );
838            assert_eq!(
839                $searcher.best_node(),
840                CompressedDAGNodeRef {
841                    segment: $best.0,
842                    index: $best.1
843                },
844                "best_index"
845            );
846            $searcher.report(
847                CompressedDAGNodeRef {
848                    segment: $next.0,
849                    index: $next.1,
850                },
851                $heads,
852                $flakiness,
853            );
854        };
855    }
856
857    #[test]
858    fn graph_two_elements_zero() {
859        let mut graph = CompressedDAG::new();
860        graph.add_node(CompressedDAGSegment::new(2), vec![]);
861        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
862        assert_graph_index!(s, (0, 0), (0, 0), true, DEFAULT_FLAKINESS);
863        assert_graph_index!(s, (0, 0), (0, 0), true, DEFAULT_FLAKINESS);
864    }
865
866    #[test]
867    fn graph_two_elements_one() {
868        let mut graph = CompressedDAG::new();
869        graph.add_node(CompressedDAGSegment::new(2), vec![]);
870        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
871        assert_graph_index!(s, (0, 0), (0, 0), false, DEFAULT_FLAKINESS);
872        assert_graph_index!(s, (0, 0), (0, 1), false, DEFAULT_FLAKINESS);
873        assert_graph_index!(s, (0, 0), (0, 1), false, DEFAULT_FLAKINESS);
874    }
875
876    #[test]
877    fn graph_many_elements_last() {
878        let mut graph = CompressedDAG::new();
879        graph.add_node(CompressedDAGSegment::new(1024), vec![]);
880        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
881        assert_graph_index!(s, (0, 511), (0, 511), false, DEFAULT_FLAKINESS);
882        assert_graph_index!(s, (0, 750), (0, 751), false, DEFAULT_FLAKINESS);
883        assert_graph_index!(s, (0, 878), (0, 878), false, DEFAULT_FLAKINESS);
884        assert_graph_index!(s, (0, 946), (0, 946), false, DEFAULT_FLAKINESS);
885        assert_graph_index!(s, (0, 982), (0, 982), false, DEFAULT_FLAKINESS);
886    }
887
888    #[test]
889    fn graph_parallel_first_first() {
890        let mut graph = CompressedDAG::new();
891        graph.add_node(CompressedDAGSegment::new(100), vec![]);
892        graph.add_node(CompressedDAGSegment::new(100), vec![]);
893        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
894        assert_graph_index!(s, (0, 99), (0, 99), true, DEFAULT_FLAKINESS);
895        assert_graph_index!(s, (0, 52), (0, 53), true, DEFAULT_FLAKINESS);
896        assert_graph_index!(s, (0, 27), (0, 28), true, DEFAULT_FLAKINESS);
897        assert_graph_index!(s, (0, 14), (0, 14), true, DEFAULT_FLAKINESS);
898        assert_graph_index!(s, (0, 7), (0, 7), true, DEFAULT_FLAKINESS);
899        assert_graph_index!(s, (0, 3), (0, 4), true, DEFAULT_FLAKINESS);
900        assert_graph_index!(s, (0, 1), (0, 2), true, DEFAULT_FLAKINESS);
901        assert_graph_index!(s, (0, 0), (0, 1), true, DEFAULT_FLAKINESS);
902        assert_graph_index!(s, (0, 0), (0, 0), true, DEFAULT_FLAKINESS);
903        assert_graph_index!(s, (0, 0), (0, 0), true, DEFAULT_FLAKINESS);
904    }
905
906    #[test]
907    fn graph_parallel_first_last() {
908        let mut graph = CompressedDAG::new();
909        graph.add_node(CompressedDAGSegment::new(100), vec![]);
910        graph.add_node(CompressedDAGSegment::new(100), vec![]);
911        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
912        assert_graph_index!(s, (0, 99), (0, 99), true, DEFAULT_FLAKINESS);
913        assert_graph_index!(s, (0, 52), (0, 53), false, DEFAULT_FLAKINESS);
914        assert_graph_index!(s, (0, 77), (0, 78), false, DEFAULT_FLAKINESS);
915        assert_graph_index!(s, (0, 90), (0, 91), false, DEFAULT_FLAKINESS);
916        assert_graph_index!(s, (0, 97), (0, 98), false, DEFAULT_FLAKINESS);
917        assert_graph_index!(s, (1, 68), (1, 69), false, DEFAULT_FLAKINESS);
918        assert_graph_index!(s, (1, 99), (0, 99), false, DEFAULT_FLAKINESS);
919        assert_graph_index!(s, (0, 98), (0, 98), false, DEFAULT_FLAKINESS);
920        assert_graph_index!(s, (0, 99), (0, 99), true, DEFAULT_FLAKINESS);
921        assert_graph_index!(s, (0, 98), (0, 99), false, DEFAULT_FLAKINESS);
922        assert_graph_index!(s, (1, 99), (0, 99), false, DEFAULT_FLAKINESS);
923    }
924
925    #[test]
926    fn graph_parallel_last_first() {
927        let mut graph = CompressedDAG::new();
928        graph.add_node(CompressedDAGSegment::new(100), vec![]);
929        graph.add_node(CompressedDAGSegment::new(100), vec![]);
930        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
931        assert_graph_index!(s, (0, 99), (0, 99), false, DEFAULT_FLAKINESS);
932        assert_graph_index!(s, (1, 52), (1, 53), true, DEFAULT_FLAKINESS);
933        assert_graph_index!(s, (1, 27), (1, 28), true, DEFAULT_FLAKINESS);
934        assert_graph_index!(s, (1, 14), (1, 14), true, DEFAULT_FLAKINESS);
935        assert_graph_index!(s, (1, 7), (1, 7), true, DEFAULT_FLAKINESS);
936        assert_graph_index!(s, (1, 3), (1, 4), true, DEFAULT_FLAKINESS);
937        assert_graph_index!(s, (1, 1), (1, 2), true, DEFAULT_FLAKINESS);
938        assert_graph_index!(s, (1, 0), (1, 1), true, DEFAULT_FLAKINESS);
939        assert_graph_index!(s, (1, 0), (1, 0), true, DEFAULT_FLAKINESS);
940        assert_graph_index!(s, (1, 0), (1, 0), true, DEFAULT_FLAKINESS);
941    }
942
943    #[test]
944    fn graph_parallel_last_last() {
945        let mut graph = CompressedDAG::new();
946        graph.add_node(CompressedDAGSegment::new(100), vec![]);
947        graph.add_node(CompressedDAGSegment::new(100), vec![]);
948        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
949        assert_graph_index!(s, (0, 99), (0, 99), false, DEFAULT_FLAKINESS);
950        assert_graph_index!(s, (1, 52), (1, 53), false, DEFAULT_FLAKINESS);
951        assert_graph_index!(s, (1, 77), (1, 78), false, DEFAULT_FLAKINESS);
952        assert_graph_index!(s, (1, 90), (1, 91), false, DEFAULT_FLAKINESS);
953        assert_graph_index!(s, (1, 97), (1, 98), false, DEFAULT_FLAKINESS);
954        assert_graph_index!(s, (0, 68), (0, 69), false, DEFAULT_FLAKINESS);
955        assert_graph_index!(s, (0, 99), (1, 99), false, DEFAULT_FLAKINESS);
956        assert_graph_index!(s, (1, 98), (1, 98), false, DEFAULT_FLAKINESS);
957        assert_graph_index!(s, (0, 99), (1, 99), false, DEFAULT_FLAKINESS);
958        assert_graph_index!(s, (1, 98), (1, 99), false, DEFAULT_FLAKINESS);
959    }
960
961    #[test]
962    fn graph_parallel_first_half() {
963        let mut graph = CompressedDAG::new();
964        graph.add_node(CompressedDAGSegment::new(100), vec![]);
965        graph.add_node(CompressedDAGSegment::new(100), vec![]);
966        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
967        assert_graph_index!(s, (0, 99), (0, 99), true, DEFAULT_FLAKINESS);
968        assert_graph_index!(s, (0, 52), (0, 53), true, DEFAULT_FLAKINESS);
969        assert_graph_index!(s, (0, 27), (0, 28), false, DEFAULT_FLAKINESS);
970        assert_graph_index!(s, (0, 40), (0, 41), false, DEFAULT_FLAKINESS);
971        assert_graph_index!(s, (0, 47), (0, 48), false, DEFAULT_FLAKINESS);
972        assert_graph_index!(s, (0, 51), (0, 51), true, DEFAULT_FLAKINESS);
973        assert_graph_index!(s, (0, 49), (0, 49), false, DEFAULT_FLAKINESS);
974        assert_graph_index!(s, (0, 50), (0, 51), true, DEFAULT_FLAKINESS);
975        assert_graph_index!(s, (0, 49), (0, 50), false, DEFAULT_FLAKINESS);
976        assert_graph_index!(s, (0, 50), (0, 50), true, DEFAULT_FLAKINESS);
977    }
978
979    #[test]
980    fn graph_parallel_second_half() {
981        let mut graph = CompressedDAG::new();
982        graph.add_node(CompressedDAGSegment::new(100), vec![]);
983        graph.add_node(CompressedDAGSegment::new(100), vec![]);
984        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
985        assert_graph_index!(s, (0, 99), (0, 99), false, DEFAULT_FLAKINESS);
986        assert_graph_index!(s, (1, 52), (1, 53), true, DEFAULT_FLAKINESS);
987        assert_graph_index!(s, (1, 27), (1, 28), false, DEFAULT_FLAKINESS);
988        assert_graph_index!(s, (1, 40), (1, 41), false, DEFAULT_FLAKINESS);
989        assert_graph_index!(s, (1, 47), (1, 48), false, DEFAULT_FLAKINESS);
990        assert_graph_index!(s, (1, 51), (1, 51), true, DEFAULT_FLAKINESS);
991        assert_graph_index!(s, (1, 49), (1, 49), false, DEFAULT_FLAKINESS);
992        assert_graph_index!(s, (1, 50), (1, 51), true, DEFAULT_FLAKINESS);
993        assert_graph_index!(s, (1, 49), (1, 50), false, DEFAULT_FLAKINESS);
994        assert_graph_index!(s, (1, 50), (1, 50), true, DEFAULT_FLAKINESS);
995    }
996
997    #[test]
998    fn graph_fork_join() {
999        //      /-1-\
1000        // *-0-*     *-3-*
1001        //      \-2-/
1002        let mut graph = CompressedDAG::new();
1003        graph.add_node(CompressedDAGSegment::new(100), vec![]);
1004        graph.add_node(CompressedDAGSegment::new(100), vec![0]);
1005        graph.add_node(CompressedDAGSegment::new(100), vec![0]);
1006        graph.add_node(CompressedDAGSegment::new(100), vec![1, 2]);
1007        let mut s = CompressedDAGSearcher::new(Rc::new(graph));
1008        assert_graph_index!(s, (1, 99), (1, 99), false, DEFAULT_FLAKINESS);
1009        assert_graph_index!(s, (2, 99), (2, 99), true, DEFAULT_FLAKINESS);
1010        assert_graph_index!(s, (2, 49), (2, 50), false, DEFAULT_FLAKINESS);
1011        assert_graph_index!(s, (2, 76), (2, 76), true, DEFAULT_FLAKINESS);
1012        assert_graph_index!(s, (2, 62), (2, 62), true, DEFAULT_FLAKINESS);
1013        assert_graph_index!(s, (2, 54), (2, 55), true, DEFAULT_FLAKINESS);
1014        assert_graph_index!(s, (2, 50), (2, 50), true, DEFAULT_FLAKINESS);
1015        assert_graph_index!(s, (2, 31), (2, 31), false, DEFAULT_FLAKINESS);
1016        assert_graph_index!(s, (2, 49), (2, 49), false, DEFAULT_FLAKINESS);
1017        assert_graph_index!(s, (2, 50), (2, 50), true, DEFAULT_FLAKINESS);
1018        assert_graph_index!(s, (2, 49), (2, 50), false, DEFAULT_FLAKINESS);
1019    }
1020}
robust_binary_search/lib.rs

robust_binary_search/
lib.rs
