use std::sync::Arc;
use bytes::Bytes;
use unityrs_testkit::Rng;
use super::{Ends, Published, RUN_LEAF, RUN_SHARE, RunIndex, search_steps};
use crate::budget::{Reservation, Unbounded};
use crate::limits::{Meter, MeteredVec};
#[test]
fn a_search_counts_the_probes_a_binary_search_makes_at_most() {
let want = [
(0, 0),
(1, 1),
(2, 2),
(3, 3),
(4, 3),
(5, 4),
(8, 4),
(9, 5),
(40_000, 17),
];
for (n, steps) in want {
assert_eq!(search_steps(n), steps, "{n} rows");
}
}
#[test]
fn the_prefix_finds_the_blocks_a_scan_finds() {
let mut rng = Rng::new(11);
for _ in 0..200 {
let n = rng.below(40);
let lens: Vec<u64> = (0..n)
.map(|_| match rng.below(4) {
0 => 0,
k => u64::try_from(rng.below(5 * k)).unwrap(),
})
.collect();
let ends: Vec<u64> = lens
.iter()
.scan(0, |acc, l| {
*acc += l;
Some(*acc)
})
.collect();
let total = ends.last().copied().unwrap_or(0);
let (table, _charge) = Ends::new(n, &Meter::unlimited()).unwrap();
for known in 0..=n {
assert_eq!(table.known(), known);
for k in 0..=known {
let start = k.checked_sub(1).map_or(0, |j| ends[j]);
assert_eq!(table.start(k), start, "start of {k}");
}
for from in 0..=known {
let most = search_steps(known - from);
for at in 0..=total + 2 {
let past = (from..known).find(|&k| ends[k] > at).unwrap_or(known);
let reach = (from..known).find(|&k| ends[k] >= at).unwrap_or(known);
let (got, probes) = table.first_ending_past(from, known, at);
assert_eq!(got, past, "{lens:?}");
assert!(probes <= most, "{probes} probes of {} rows", known - from);
let (got, probes) = table.first_ending_at(from, known, at);
assert_eq!(got, reach, "{lens:?}");
assert!(probes <= most, "{probes} probes of {} rows", known - from);
}
}
if known < n {
table.learn(known + 1, 7);
assert_eq!(table.known(), known);
table.learn(known, lens[known]);
table.learn(known, lens[known]);
}
}
}
}
fn span_of(bytes: &Bytes) -> (usize, usize) {
(usize::from(bytes[0]), usize::from(bytes[1]))
}
fn run(first: usize, end: usize) -> Bytes {
Bytes::from(vec![
u8::try_from(first).unwrap(),
u8::try_from(end).unwrap(),
])
}
fn covers((f, e): (usize, usize), (first, end): (usize, usize)) -> bool {
f <= first && end <= e
}
#[test]
fn the_run_index_covers_what_every_published_run_covered() {
let mut rng = Rng::new(5);
let meter = Meter::unlimited();
for _ in 0..300 {
let blocks = 1 + rng.below(30);
let mut index = RunIndex::new(&meter);
let mut model: Vec<(usize, usize)> = Vec::new();
for _ in 0..rng.below(80) {
let first = rng.below(blocks);
let end = first + 1 + rng.below(blocks - first);
let span = (first, end);
let covering = model.iter().copied().find(|r| covers(*r, span));
let found = index.covering(first, end).map(|(f, b)| (f, span_of(&b)));
assert_eq!(found.is_some(), covering.is_some(), "{span:?} in {model:?}");
if let Some((f, r)) = found {
assert_eq!(f, r.0);
assert!(covers(r, span), "{r:?} for {span:?}");
}
if rng.below(2) == 0 {
continue;
}
let cached: Vec<(usize, usize)> = index.runs.iter().map(|(f, r)| (*f, r.end)).collect();
let inside: Vec<(usize, usize)> = cached
.iter()
.copied()
.filter(|r| covers(span, *r))
.collect();
assert_eq!(index.covered(first, end), inside.len());
let mut dropped = MeteredVec::new(&meter);
match index.publish(first, end, &run(first, end), &mut dropped) {
Published::Covered(f, b) => {
assert!(covering.is_some(), "{span:?} answered by a run");
assert!(covers(span_of(&b), span) && f == span_of(&b).0);
assert!(dropped.is_empty());
}
Published::Cached => {
assert!(covering.is_none(), "{span:?} cached though covered");
let gone: Vec<(usize, usize)> =
dropped.as_slice().iter().map(span_of).collect();
assert_eq!(gone, inside, "the runs {span:?} covers");
model.push(span);
}
Published::Refused => panic!("an unlimited meter refused"),
}
let now: Vec<(usize, usize)> = index.runs.iter().map(|(f, r)| (*f, r.end)).collect();
for pair in now.windows(2) {
assert!(pair[0].0 < pair[1].0 && pair[0].1 < pair[1].1, "{now:?}");
}
for (f, r) in &index.runs {
assert_eq!(span_of(&r.bytes), (*f, r.end));
}
let len = u64::try_from(index.len()).unwrap();
assert_eq!(index.charge.bytes(), RUN_LEAF + len * RUN_SHARE);
}
}
}
#[test]
fn a_refused_publish_changes_nothing() {
let full = Meter::new(0, Arc::new(Unbounded), Reservation::Input);
let mut index = RunIndex::new(&full);
let mut dropped = MeteredVec::new(&full);
assert!(matches!(
index.publish(0, 5, &run(0, 5), &mut dropped),
Published::Refused
));
assert_eq!((index.len(), index.charge.bytes()), (0, 0));
let unlimited = Meter::unlimited();
let mut index = RunIndex::new(&unlimited);
let mut dropped = MeteredVec::new(&unlimited);
assert!(matches!(
index.publish(1, 2, &run(1, 2), &mut dropped),
Published::Cached
));
let charged = index.charge.bytes();
let mut no_room = MeteredVec::new(&full);
assert!(matches!(
index.publish(0, 5, &run(0, 5), &mut no_room),
Published::Refused
));
assert_eq!(
index.covering(1, 2).map(|(f, b)| (f, span_of(&b))),
Some((1, (1, 2)))
);
assert_eq!((index.len(), index.charge.bytes()), (1, charged));
}