Skip to main content

unityrs_testkit/
search.rs

1//! A limit's **need** (`docs/plans/extract.md` X13): the least value at
2//! which a run meets no refusal of it. [`least`] brackets and bisects a
3//! refusal predicate, then checks it is monotone where the bisection
4//! assumed it: at the need's adjacent values and at sampled values on both
5//! sides, besides every value the bisection itself tried. A run's
6//! allocation path adapts (a growth retried smaller, an eviction), so
7//! monotonicity is checked, not assumed; a [`Counterexample`] is no need,
8//! and comes back for a spec ruling instead of a squeeze result.
9
10use std::collections::BTreeMap;
11use std::fmt;
12
13/// What [`least`] found.
14#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct Least {
16    /// The least value whose run met no refusal.
17    pub need: u64,
18    /// Every value tried, and whether its run was refused.
19    pub tried: BTreeMap<u64, bool>,
20}
21
22/// A value whose answer the need contradicts: refused at or above it, or
23/// not refused below it; or a top value that is itself refused.
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub struct Counterexample {
26    /// The value.
27    pub value: u64,
28    /// Whether its run was refused.
29    pub refused: bool,
30    /// The need the bisection found (`None`: the top was refused).
31    pub need: Option<u64>,
32}
33
34impl fmt::Display for Counterexample {
35    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36        match self.need {
37            None => write!(f, "the top value {} is itself refused", self.value),
38            Some(need) => write!(
39                f,
40                "not monotone: {} is {} while the bisected need is {need}; this needs a spec \
41                 ruling, not a squeeze result",
42                self.value,
43                if self.refused { "refused" } else { "clear" },
44            ),
45        }
46    }
47}
48
49/// The values [`least`] checks beside the bisection's own: the need's
50/// neighbours, `samples` evenly spaced on each side, and powers of two away
51/// from the need on each side, all within `[lo, hi]`.
52fn checks(lo: u64, need: u64, hi: u64, samples: u64) -> Vec<u64> {
53    let mut v = vec![need, need.saturating_add(1).min(hi)];
54    if need > lo {
55        v.push(need - 1);
56    }
57    let mut step = 2_u64;
58    let within = |x: Option<u64>| x.is_some_and(|x| (lo..=hi).contains(&x));
59    while step > 0 && (within(need.checked_sub(step)) || within(need.checked_add(step))) {
60        if let Some(below) = need.checked_sub(step).filter(|&x| x >= lo) {
61            v.push(below);
62        }
63        if let Some(above) = need.checked_add(step).filter(|&x| x <= hi) {
64            v.push(above);
65        }
66        step = step.checked_mul(2).unwrap_or(0);
67    }
68    for k in 1..=samples {
69        if need > lo {
70            v.push(between(lo, need, k, samples));
71        }
72        v.push(between(need, hi, k, samples));
73    }
74    v.sort_unstable();
75    v.dedup();
76    v
77}
78
79/// The `k`th of `samples` evenly spaced values in `[a, b]`, in arithmetic
80/// wide enough for any `u64` span.
81fn between(a: u64, b: u64, k: u64, samples: u64) -> u64 {
82    let span = u128::from(b - a) * u128::from(k) / (u128::from(samples) + 1);
83    // At most `b - a`, so it fits.
84    a.saturating_add(u64::try_from(span).unwrap_or(b - a))
85}
86
87/// The least value in `[lo, hi]` that `refused` answers `false` for, by
88/// bracketing (`hi` must be clear) and bisection, then checked at the
89/// need's adjacent values, at `samples` spaced values on each side and at
90/// powers of two away from it.
91///
92/// # Errors
93/// A [`Counterexample`]: `hi` refused, or a value whose answer is not the
94/// need's side's.
95pub fn least(
96    lo: u64,
97    hi: u64,
98    samples: u64,
99    mut refused: impl FnMut(u64) -> bool,
100) -> Result<Least, Counterexample> {
101    let mut tried = BTreeMap::new();
102    let mut ask =
103        |v: u64, tried: &mut BTreeMap<u64, bool>| *tried.entry(v).or_insert_with(|| refused(v));
104    if ask(hi, &mut tried) {
105        return Err(Counterexample {
106            value: hi,
107            refused: true,
108            need: None,
109        });
110    }
111    let need = if ask(lo, &mut tried) {
112        let (mut bad, mut good) = (lo, hi);
113        while good - bad > 1 {
114            let mid = bad + (good - bad) / 2;
115            if ask(mid, &mut tried) {
116                bad = mid;
117            } else {
118                good = mid;
119            }
120        }
121        good
122    } else {
123        lo
124    };
125    for v in checks(lo, need, hi, samples) {
126        ask(v, &mut tried);
127    }
128    if let Some((&value, &r)) = tried.iter().find(|&(&v, &r)| r != (v < need)) {
129        return Err(Counterexample {
130            value,
131            refused: r,
132            need: Some(need),
133        });
134    }
135    Ok(Least { need, tried })
136}
137
138#[cfg(test)]
139mod tests {
140    use super::{Counterexample, least};
141
142    #[test]
143    fn the_need_is_the_least_clear_value_and_its_neighbours_are_tried() {
144        let found = least(0, 1 << 20, 3, |v| v < 777).unwrap();
145        assert_eq!(found.need, 777);
146        assert_eq!(found.tried.get(&776), Some(&true));
147        assert_eq!(found.tried.get(&777), Some(&false));
148        assert_eq!(found.tried.get(&778), Some(&false));
149        assert!(found.tried.len() < 80, "{}", found.tried.len());
150    }
151
152    #[test]
153    fn a_need_of_zero_is_tested_at_zero_alone() {
154        let found = least(0, 100, 2, |_| false).unwrap();
155        assert_eq!(found.need, 0);
156        assert!(found.tried.keys().all(|&v| v <= 100));
157    }
158
159    /// A predicate clear in a window below its true need, which bisection
160    /// alone can step over: a sampled value finds it.
161    #[test]
162    fn a_window_below_the_need_is_a_counterexample() {
163        let pred = |v: u64| !((250..=260).contains(&v) || v >= 1000);
164        let e = least(0, 1 << 12, 7, pred).unwrap_err();
165        assert!(e.value < 1000 && !e.refused, "{e:?}");
166        assert!(e.to_string().contains("spec ruling"), "{e}");
167    }
168
169    /// The full `u64` range: the sampling's arithmetic never overflows.
170    #[test]
171    fn the_whole_range_is_searched_without_overflow() {
172        let l = least(0, u64::MAX, 4, |v| v < 777).unwrap();
173        assert_eq!(l.need, 777);
174        assert!(l.tried.contains_key(&u64::MAX));
175        assert!(l.tried.keys().any(|&v| v > u64::MAX / 2 && v < u64::MAX));
176        let top = least(u64::MAX - 3, u64::MAX, 4, |v| v < u64::MAX).unwrap();
177        assert_eq!(top.need, u64::MAX);
178    }
179
180    #[test]
181    fn a_refused_top_is_no_bracket() {
182        assert_eq!(
183            least(0, 10, 1, |_| true),
184            Err(Counterexample {
185                value: 10,
186                refused: true,
187                need: None
188            })
189        );
190    }
191}