use crate::rowset::{Ones, Repr, RowSet, WORD, select};
use crate::runtime::RuntimeColumn;
const DRIVE_RATIO: usize = 256;
const RANDOM_TRIES: usize = 8;
const GUESS_COST: usize = 1024;
const GUESSES: usize = 1024;
const GUESS_MARGIN: f64 = 4.0;
#[derive(Debug, Clone, Default)]
pub struct RowSets<'a> {
first: [Option<&'a RowSet>; 3],
more: Vec<&'a RowSet>,
}
impl<'a> RowSets<'a> {
#[must_use]
pub const fn new() -> Self {
Self {
first: [None; 3],
more: Vec::new(),
}
}
pub fn push(&mut self, set: &'a RowSet) {
if self.iter().any(|known| std::ptr::eq(known, set)) {
return;
}
match self.first.iter_mut().find(|slot| slot.is_none()) {
Some(slot) => *slot = Some(set),
None => self.more.push(set),
}
}
pub(crate) fn distinct(sets: impl IntoIterator<Item = &'a RowSet>) -> Self {
let mut sets = sets.into_iter();
let mut first = [None; 3];
first.iter_mut().for_each(|slot| *slot = sets.next());
Self {
first,
more: sets.collect(),
}
}
pub fn iter(&self) -> impl Iterator<Item = &'a RowSet> + Clone + '_ {
self.first.iter().flatten().chain(&self.more).copied()
}
}
impl<'a> FromIterator<&'a RowSet> for RowSets<'a> {
fn from_iter<I: IntoIterator<Item = &'a RowSet>>(sets: I) -> Self {
let mut this = Self::new();
sets.into_iter().for_each(|set| this.push(set));
this
}
}
#[derive(Debug, Clone)]
pub enum Filter<'a> {
Is(&'a RowSet),
Not(&'a RowSet),
AnyOf(RowSets<'a>),
Runtime(&'a RuntimeColumn, bool),
}
impl Filter<'_> {
fn contains(&self, row: usize) -> bool {
match self {
Self::Is(set) => set.contains(row),
Self::Not(set) => !set.contains(row),
Self::AnyOf(sets) => sets.iter().any(|set| set.contains(row)),
Self::Runtime(column, value) => column.get(row) == *value,
}
}
fn share(&self, rows: usize) -> f64 {
let rows_in = match self {
Self::Is(set) => set.len(),
Self::Not(set) => rows.saturating_sub(set.len()),
Self::AnyOf(sets) => sets.iter().map(RowSet::len).sum(),
Self::Runtime(..) => rows,
};
rows_in.min(rows) as f64 / rows as f64
}
fn walk_cost(&self) -> Option<usize> {
let cost = |set: &RowSet| match set.repr() {
Repr::Sparse(rows) => rows.len(),
Repr::Dense(words, ones) => words.len() + ones,
};
match self {
Self::Is(set) => Some(cost(set)),
Self::AnyOf(sets) => Some(sets.iter().map(cost).sum()),
Self::Not(_) | Self::Runtime(..) => None,
}
}
}
#[derive(Debug, Clone)]
pub struct Plan<'a> {
rows: usize,
slots: Vec<Option<Filter<'a>>>,
extra: Vec<Filter<'a>>,
}
impl<'a> Plan<'a> {
#[must_use]
pub fn new(rows: usize, slots: usize) -> Self {
assert!(
rows <= RowSet::MAX_ROWS,
"venndb: a database holds at most u32::MAX rows"
);
Self {
rows,
slots: vec![None; slots],
extra: Vec::new(),
}
}
pub fn reset(&mut self) {
self.slots.fill(None);
self.extra.clear();
}
pub fn set(&mut self, slot: usize, filter: Filter<'a>) {
self.slots[slot] = Some(filter);
}
pub fn or(&mut self, slot: usize, set: Option<&'a RowSet>) {
if !matches!(self.slots[slot], Some(Filter::AnyOf(_))) {
self.slots[slot] = Some(Filter::AnyOf(RowSets::new()));
}
if let (Some(Filter::AnyOf(sets)), Some(set)) = (&mut self.slots[slot], set) {
sets.push(set);
}
}
pub fn and(&mut self, filter: Filter<'a>) {
self.extra.push(filter);
}
fn filters(&self) -> impl Iterator<Item = &Filter<'a>> + Clone {
self.slots.iter().flatten().chain(&self.extra)
}
#[must_use]
pub fn execute(&self) -> Option<Matches<'a>> {
if self.rows == 0 {
return None;
}
let mut driver: Option<(usize, usize)> = None;
let mut only = None;
let mut count = 0;
for (at, filter) in self.filters().enumerate() {
count += 1;
only = Some(filter);
if let Some(cost) = filter.walk_cost() {
if cost == 0 {
return None;
}
if driver.is_none_or(|(best, _)| cost < best) {
driver = Some((cost, at));
}
}
}
match (count, only, driver) {
(0, ..) => Some(Matches(Repr2::All(self.rows))),
(1, Some(Filter::Is(set)), _) if set.span() <= self.rows => {
Some(Matches(Repr2::Set(set)))
}
(_, _, Some((cost, at))) if cost.saturating_mul(DRIVE_RATIO) <= self.rows => {
self.walk(at)
}
_ => self.combine(),
}
}
#[must_use]
pub fn random(&self) -> Option<usize> {
match self.guess(|_| true) {
Guess::Found(row) => Some(row),
Guess::Nothing => None,
Guess::Unknown => self.execute().map(|matches| matches.random()),
}
}
#[must_use]
pub fn random_where(&self, mut predicate: impl FnMut(usize) -> bool) -> Option<usize> {
match self.guess(&mut predicate) {
Guess::Found(row) => Some(row),
Guess::Nothing => None,
Guess::Unknown => self.execute()?.random_where(predicate),
}
}
fn guess(&self, mut accept: impl FnMut(usize) -> bool) -> Guess {
if self.rows == 0 || self.filters().any(|filter| filter.walk_cost() == Some(0)) {
return Guess::Nothing;
}
let share: f64 = self
.filters()
.map(|filter| filter.share(self.rows))
.product();
let guesses = (self.rows / GUESS_COST).min(GUESSES);
if share * (guesses as f64) < GUESS_MARGIN {
return Guess::Unknown;
}
for _ in 0..guesses {
let row = crate::rng::below(self.rows);
if self.filters().all(|filter| filter.contains(row)) && accept(row) {
return Guess::Found(row);
}
}
Guess::Unknown
}
fn walk(&self, driver: usize) -> Option<Matches<'a>> {
let keep = |row: &usize| {
*row < self.rows
&& self
.filters()
.enumerate()
.all(|(at, filter)| at == driver || filter.contains(*row))
};
let mut found: Vec<u32> = Vec::new();
match self.filters().nth(driver) {
Some(Filter::Is(set)) => found.extend(set.iter().filter(keep).map(|row| row as u32)),
Some(Filter::AnyOf(sets)) => {
for set in sets.iter() {
found.extend(set.iter().filter(keep).map(|row| row as u32));
}
if sets.iter().nth(1).is_some() {
found.sort_unstable();
found.dedup();
}
}
_ => unreachable!("not a filter to walk over"),
}
(!found.is_empty()).then_some(Matches(Repr2::Rows(found)))
}
fn combine(&self) -> Option<Matches<'a>> {
let len = self.rows.div_ceil(WORD);
let start = self
.filters()
.enumerate()
.find_map(|(at, filter)| match filter {
Filter::Is(set) => match set.repr() {
Repr::Dense(words, _) => Some((at, words)),
Repr::Sparse(_) => None,
},
_ => None,
});
let mut mask = match start {
Some((_, words)) => {
let mut mask: Vec<u64> = Vec::with_capacity(len);
mask.extend(words.iter().take(len));
mask.resize(len, 0);
mask
}
None => vec![u64::MAX; len],
};
let mut scratch = Vec::new();
for (at, filter) in self.filters().enumerate() {
if start.is_some_and(|(start, _)| start == at) {
continue;
}
match filter {
Filter::Is(set) => match set.repr() {
Repr::Dense(words, _) => and(&mut mask, words.iter().copied()),
Repr::Sparse(found) => {
scratch.clear();
scratch.resize(len, 0);
for row in found.iter().map(|row| *row as usize) {
if let Some(word) = mask.get(row / WORD) {
scratch[row / WORD] |= word & (1 << (row % WORD));
}
}
std::mem::swap(&mut mask, &mut scratch);
}
},
Filter::Not(set) => match set.repr() {
Repr::Dense(words, _) => {
for (word, other) in mask.iter_mut().zip(words) {
*word &= !other;
}
}
Repr::Sparse(found) => {
for row in found.iter().map(|row| *row as usize) {
if let Some(word) = mask.get_mut(row / WORD) {
*word &= !(1 << (row % WORD));
}
}
}
},
Filter::AnyOf(sets) => {
scratch.clear();
scratch.resize(len, 0);
for set in sets.iter() {
match set.repr() {
Repr::Dense(words, _) => {
for (word, other) in scratch.iter_mut().zip(words) {
*word |= other;
}
}
Repr::Sparse(found) => {
for row in found.iter().map(|row| *row as usize) {
if let Some(word) = scratch.get_mut(row / WORD) {
*word |= 1 << (row % WORD);
}
}
}
}
}
and(&mut mask, scratch.iter().copied());
}
Filter::Runtime(column, value) => column.filter(&mut mask, *value),
}
}
if !self.rows.is_multiple_of(WORD) {
mask[len - 1] &= (1 << (self.rows % WORD)) - 1;
}
let ones: usize = mask.iter().map(|word| word.count_ones() as usize).sum();
(ones > 0).then_some(Matches(Repr2::Mask(mask, ones)))
}
}
#[derive(Debug, PartialEq, Eq)]
enum Guess {
Found(usize),
Nothing,
Unknown,
}
fn and(mask: &mut [u64], other: impl ExactSizeIterator<Item = u64>) {
let known = other.len().min(mask.len());
for (word, other) in mask.iter_mut().zip(other) {
*word &= other;
}
mask[known..].fill(0);
}
#[derive(Debug, Clone)]
pub struct Matches<'a>(Repr2<'a>);
#[derive(Debug, Clone)]
enum Repr2<'a> {
All(usize),
Set(&'a RowSet),
Rows(Vec<u32>),
Mask(Vec<u64>, usize),
}
impl Matches<'_> {
#[expect(clippy::len_without_is_empty, reason = "matches are never empty")]
#[must_use]
pub fn len(&self) -> usize {
match &self.0 {
Repr2::All(rows) => *rows,
Repr2::Set(set) => set.len(),
Repr2::Rows(rows) => rows.len(),
Repr2::Mask(_, ones) => *ones,
}
}
#[must_use]
pub fn nth(&self, n: usize) -> Option<usize> {
match &self.0 {
Repr2::All(rows) => (n < *rows).then_some(n),
Repr2::Set(set) => set.nth(n),
Repr2::Rows(rows) => rows.get(n).map(|row| *row as usize),
Repr2::Mask(words, _) => select(words, n),
}
}
#[must_use]
pub fn first(&self) -> usize {
self.nth(0).expect("matches are never empty")
}
#[must_use]
pub fn random(&self) -> usize {
self.nth(crate::rng::below(self.len()))
.expect("matches are never empty")
}
#[must_use]
pub fn random_where(&self, mut predicate: impl FnMut(usize) -> bool) -> Option<usize> {
for _ in 0..RANDOM_TRIES.min(self.len()) {
let row = self.random();
if predicate(row) {
return Some(row);
}
}
self.filter(predicate).map(|matches| matches.random())
}
#[must_use]
pub fn filter(&self, mut predicate: impl FnMut(usize) -> bool) -> Option<Matches<'static>> {
let rows: Vec<u32> = self
.iter()
.filter(|row| predicate(*row))
.map(|row| row as u32)
.collect();
(!rows.is_empty()).then_some(Matches(Repr2::Rows(rows)))
}
#[must_use]
pub fn iter(&self) -> MatchesIter<'_> {
MatchesIter(match &self.0 {
Repr2::All(rows) => IterRepr::All(0..*rows),
Repr2::Set(set) => IterRepr::Set(set.iter()),
Repr2::Rows(rows) => IterRepr::Rows(rows.iter()),
Repr2::Mask(words, _) => IterRepr::Mask(Ones::new(words)),
})
}
}
impl<'a> IntoIterator for &'a Matches<'_> {
type Item = usize;
type IntoIter = MatchesIter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[derive(Debug, Clone)]
pub struct MatchesIter<'a>(IterRepr<'a>);
#[derive(Debug, Clone)]
enum IterRepr<'a> {
All(std::ops::Range<usize>),
Set(crate::rowset::Iter<'a>),
Rows(std::slice::Iter<'a, u32>),
Mask(Ones<'a>),
}
impl Iterator for MatchesIter<'_> {
type Item = usize;
fn next(&mut self) -> Option<usize> {
match &mut self.0 {
IterRepr::All(rows) => rows.next(),
IterRepr::Set(rows) => rows.next(),
IterRepr::Rows(rows) => rows.next().map(|row| *row as usize),
IterRepr::Mask(ones) => ones.next(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
struct Random(u64);
impl Random {
fn next(&mut self, limit: usize) -> usize {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
(self.0 % limit as u64) as usize
}
fn set(&mut self, rows: usize, one_in: usize) -> RowSet {
(0..rows).filter(|_| self.next(one_in) == 0).collect()
}
}
fn naive(rows: usize, filters: &[Filter<'_>]) -> Vec<usize> {
(0..rows)
.filter(|row| filters.iter().all(|filter| filter.contains(*row)))
.collect()
}
fn found(matches: Option<Matches<'_>>) -> Vec<usize> {
let Some(matches) = matches else {
return Vec::new();
};
let rows: Vec<usize> = matches.iter().collect();
assert!(!rows.is_empty(), "matches are never empty");
assert_eq!(matches.len(), rows.len());
assert_eq!(matches.first(), rows[0]);
for (n, row) in rows.iter().enumerate() {
assert_eq!(matches.nth(n), Some(*row));
}
assert_eq!(matches.nth(rows.len()), None);
assert!(rows.contains(&matches.random()));
assert!((&matches).into_iter().eq(rows.iter().copied()));
rows
}
#[test]
fn both_ways_agree_with_a_scan() {
let mut random = Random(0x1234_5678_9ABC_DEF1);
for rows in [1, 63, 64, 65, 200, 1000, 5000] {
let column = RuntimeColumn::new();
for row in 0..rows + 70 {
column.set(row, random.next(3) == 0);
}
let sets: Vec<RowSet> = [1, 2, 3, 10, 50, 100, 400, 1, 7, 300]
.into_iter()
.map(|one_in| {
let span = rows + random.next(2) * 70;
random.set(span, one_in)
})
.collect();
for _ in 0..300 {
let filters: Vec<Filter<'_>> = (0..1 + random.next(4))
.map(|_| {
let set = &sets[random.next(sets.len())];
match random.next(6) {
0 | 1 => Filter::Is(set),
2 => Filter::Not(set),
3 | 4 => Filter::AnyOf(
(0..random.next(4))
.map(|_| &sets[random.next(sets.len())])
.collect(),
),
_ => Filter::Runtime(&column, random.next(2) == 0),
}
})
.collect();
let expected = naive(rows, &filters);
let mut plan = Plan::new(rows, 0);
filters.iter().for_each(|filter| plan.and(filter.clone()));
assert_eq!(found(plan.combine()), expected, "{filters:?}");
for (at, filter) in filters.iter().enumerate() {
if filter.walk_cost().is_some() {
assert_eq!(found(plan.walk(at)), expected, "{filters:?}");
}
}
assert_eq!(found(plan.execute()), expected, "{filters:?}");
for _ in 0..3 {
let row = plan.random();
assert_eq!(row.is_some(), !expected.is_empty(), "{filters:?}");
assert!(row.is_none_or(|row| expected.contains(&row)), "{filters:?}");
let odd = plan.random_where(|row| row % 2 == 1);
assert_eq!(odd.is_some(), expected.iter().any(|row| row % 2 == 1));
assert!(odd.is_none_or(|row| row % 2 == 1 && expected.contains(&row)));
}
match plan.guess(|_| true) {
Guess::Found(row) => assert!(expected.contains(&row), "{filters:?}"),
Guess::Nothing => assert!(expected.is_empty(), "{filters:?}"),
Guess::Unknown => (),
}
}
}
}
#[test]
#[cfg(target_pointer_width = "64")]
#[should_panic(expected = "at most u32::MAX rows")]
fn rows_have_to_fit() {
let _ = Plan::new(RowSet::MAX_ROWS + 1, 0);
}
#[test]
fn random_reaches_every_row() {
let odd: RowSet = (0..640).filter(|row| row % 2 == 1).collect();
let few: RowSet = [3, 500, 77].into_iter().collect();
let column = RuntimeColumn::new();
let mut plans = [
Plan::new(8, 0),
Plan::new(640, 0),
Plan::new(640, 0),
Plan::new(640, 0),
];
plans[1].and(Filter::Not(&odd));
plans[1].and(Filter::Runtime(&column, false));
plans[2].and(Filter::Is(&few));
plans[3].and(Filter::Is(&odd));
plans[3].and(Filter::Not(&few));
for plan in &plans {
let matches = plan.execute().unwrap();
let rows: Vec<usize> = matches.iter().collect();
let mut seen = std::collections::BTreeSet::new();
for _ in 0..rows.len() * 40 {
seen.insert(matches.random());
let row = matches.random_where(|row| row % 3 != 0).unwrap();
assert!(row % 3 != 0 && rows.contains(&row));
}
assert!(seen.iter().eq(rows.iter()), "{seen:?}");
}
}
#[test]
fn guesses_when_many_rows_match() {
let rows = 64_000;
let half: RowSet = (0..rows).filter(|row| row % 2 == 0).collect();
let few: RowSet = (0..rows).filter(|row| row % 100 == 0).collect();
let none = RowSet::new();
let column = RuntimeColumn::new();
let mut plan = Plan::new(rows, 0);
assert!(matches!(plan.guess(|_| true), Guess::Found(_)));
plan.and(Filter::Is(&half));
plan.and(Filter::Not(&few));
plan.and(Filter::Runtime(&column, false));
let mut seen = std::collections::BTreeSet::new();
for _ in 0..2000 {
let Guess::Found(row) = plan.guess(|_| true) else {
panic!("1 row in 2 meets the filters");
};
assert!(row % 2 == 0 && row % 100 != 0);
seen.insert(row);
seen.insert(plan.random().unwrap());
}
assert!(seen.len() > 1000 && seen.first() < Some(&1000) && seen.last() > Some(&63_000));
assert_eq!(plan.guess(|_| false), Guess::Unknown);
assert_eq!(plan.random_where(|_| false), None);
assert_eq!(plan.random_where(|row| row == 42), Some(42));
let mut plan = Plan::new(rows, 0);
plan.and(Filter::Is(&few));
assert_eq!(plan.guess(|_| true), Guess::Unknown);
assert!(plan.random().unwrap().is_multiple_of(100));
let tenth: RowSet = (0..rows).filter(|row| row % 10 == 0).collect();
let mut plan = Plan::new(rows, 0);
plan.and(Filter::Is(&tenth));
assert!((0..50).any(|_| matches!(plan.guess(|_| true), Guess::Found(_))));
plan.and(Filter::Is(&half));
assert_eq!(plan.guess(|_| true), Guess::Unknown);
let million = 1_000_000;
let one_in = |n: usize| (0..million).filter(|row| row % n == 0).collect::<RowSet>();
let (few_of_many, fewer) = (one_in(100), one_in(600));
let mut plan = Plan::new(million, 0);
plan.and(Filter::Is(&few_of_many));
let found = |guess| matches!(guess, Guess::Found(row) if row % 100 == 0);
assert!((0..20).all(|_| found(plan.guess(|_| true))));
let mut plan = Plan::new(million, 0);
plan.and(Filter::Is(&fewer));
assert_eq!(plan.guess(|_| true), Guess::Unknown);
let mut plan = Plan::new(4000, 0);
assert_eq!(plan.guess(|_| true), Guess::Unknown);
plan.and(Filter::Is(&half));
assert_eq!(plan.guess(|_| true), Guess::Unknown);
assert!(plan.random().unwrap().is_multiple_of(2));
assert!(matches!(
Plan::new(4096, 0).guess(|_| true),
Guess::Found(_)
));
let mut plan = Plan::new(rows, 0);
plan.and(Filter::Is(&none));
assert_eq!(plan.guess(|_| true), Guess::Nothing);
assert_eq!((plan.random(), plan.random_where(|_| true)), (None, None));
assert_eq!(Plan::new(0, 0).guess(|_| true), Guess::Nothing);
let beyond: RowSet = (0..rows * 2).collect();
let mut plan = Plan::new(rows / 2, 0);
plan.and(Filter::Is(&beyond));
assert!(
(0..200).all(|_| matches!(plan.guess(|_| true), Guess::Found(row) if row < rows / 2))
);
}
#[test]
fn many_distinct_sets() {
let sets: Vec<RowSet> = (0..10).map(|row| [row].into_iter().collect()).collect();
let list = RowSets::distinct(&sets);
assert!(list.iter().eq(sets.iter()));
assert_eq!(RowSets::distinct(&sets[..2]).iter().count(), 2);
let mut list: RowSets<'_> = sets.iter().chain(&sets).collect();
assert!(list.iter().eq(sets.iter()));
list.push(&sets[9]);
assert_eq!(list.iter().count(), 10);
}
#[test]
fn no_filters_match_all_rows() {
assert!(Plan::new(0, 0).execute().is_none());
assert_eq!(found(Plan::new(3, 2).execute()), [0, 1, 2]);
}
#[test]
fn a_single_set_is_borrowed() {
let set: RowSet = [1, 5].into_iter().collect();
let mut plan = Plan::new(6, 0);
plan.and(Filter::Is(&set));
let matches = plan.execute().unwrap();
assert!(matches!(matches.0, Repr2::Set(_)));
assert_eq!(found(Some(matches)), [1, 5]);
let mut plan = Plan::new(5, 0);
plan.and(Filter::Is(&set));
assert_eq!(found(plan.execute()), [1]);
}
#[test]
fn slots() {
let (a, b, empty): (RowSet, RowSet, RowSet) = (
[0, 1].into_iter().collect(),
[1, 2].into_iter().collect(),
RowSet::new(),
);
let mut plan = Plan::new(4, 2);
plan.set(0, Filter::Is(&a));
plan.set(0, Filter::Not(&a));
assert_eq!(found(plan.execute()), [2, 3]);
plan.or(0, Some(&a));
plan.or(0, Some(&a));
assert!(matches!(&plan.slots[0], Some(Filter::AnyOf(sets)) if sets.iter().count() == 1));
plan.or(0, Some(&b));
plan.or(0, None);
assert_eq!(found(plan.execute()), [0, 1, 2]);
plan.or(1, Some(&b));
assert_eq!(found(plan.execute()), [1, 2]);
plan.and(Filter::Not(&a));
assert_eq!(found(plan.execute()), [2]);
plan.reset();
assert_eq!(found(plan.execute()), [0, 1, 2, 3]);
plan.or(1, None);
assert_eq!(found(plan.execute()), []);
plan.reset();
plan.and(Filter::Is(&empty));
plan.and(Filter::Not(&a));
assert_eq!(found(plan.execute()), []);
}
#[test]
fn small_sets_are_walked() {
let rows = DRIVE_RATIO * 40;
let small: RowSet = (0..40).map(|row| row * 200).collect();
let big: RowSet = (0..rows).filter(|row| row % 2 == 0).collect();
let mut plan = Plan::new(rows, 0);
plan.and(Filter::Is(&big));
plan.and(Filter::Is(&small));
let matches = plan.execute().unwrap();
assert!(matches!(matches.0, Repr2::Rows(_)));
assert!(matches.iter().eq((0..40).map(|row| row * 200)));
let small: RowSet = (0..41).map(|row| row * 200).collect();
let mut plan = Plan::new(rows, 0);
plan.and(Filter::Is(&big));
plan.and(Filter::Is(&small));
let matches = plan.execute().unwrap();
assert!(matches!(matches.0, Repr2::Mask(..)));
assert!(matches.iter().eq((0..41).map(|row| row * 200)));
}
#[test]
fn filter_and_random_where() {
let mut plan = Plan::new(100, 0);
let odd: RowSet = (0..100).filter(|row| row % 2 == 1).collect();
plan.and(Filter::Not(&odd));
let matches = plan.execute().unwrap();
assert_eq!(matches.len(), 50);
let filtered = matches.filter(|row| row >= 90).unwrap();
assert_eq!(found(Some(filtered)), [90, 92, 94, 96, 98]);
assert!(matches.filter(|row| row > 98).is_none());
for _ in 0..50 {
assert_eq!(matches.random_where(|row| row == 42), Some(42));
assert!(matches.random_where(|row| row < 10).unwrap() < 10);
}
assert_eq!(matches.random_where(|_| false), None);
let one = Plan::new(1, 0).execute().unwrap();
let mut calls = 0;
assert_eq!(
one.random_where(|_| {
calls += 1;
false
}),
None
);
assert_eq!(calls, 2);
}
}