use std::collections::HashMap;
use sha2::{Digest, Sha256};
use toktier_store_core::SessionHandle;
const DOMAIN: &[u8] = b"toktier.rust.prefix-index.v1\0";
pub(crate) const MAX_LISTED_HOLDERS: usize = 4;
const SHRINK_FLOOR: usize = 1024;
pub(crate) type BlockKey = [u8; 32];
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct KeyParams {
pub(crate) fingerprint: [u8; 32],
pub(crate) block_chars: u64,
}
impl KeyParams {
fn block_hasher(&self, parent: Option<&BlockKey>, index: u64) -> Sha256 {
let mut hasher = Sha256::new();
hasher.update(DOMAIN);
match parent {
Some(parent) => {
hasher.update([1u8]);
hasher.update(parent);
}
None => {
hasher.update([0u8]);
hasher.update([0u8; 32]);
}
}
hasher.update(index.to_le_bytes());
hasher.update(self.fingerprint);
hasher
}
fn block_chars_usize(&self) -> usize {
usize::try_from(self.block_chars).unwrap_or(usize::MAX)
}
}
fn split_after_chars(text: &str, limit: usize) -> (usize, usize) {
let mut taken = 0usize;
for (offset, _) in text.char_indices() {
if taken == limit {
return (offset, taken);
}
taken += 1;
}
(text.len(), taken)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub(crate) struct Seal {
pub(crate) chars: u64,
pub(crate) bytes: u64,
pub(crate) ids: u64,
}
impl Seal {
pub(crate) fn is_zero(&self) -> bool {
self.ids == 0
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Holder {
pub(crate) handle: SessionHandle,
pub(crate) seal: Seal,
}
#[derive(Debug)]
struct Entry {
refs: u32,
holders: Vec<Holder>,
}
#[derive(Debug, Clone)]
struct Rolling {
partial: Sha256,
partial_chars: u64,
depth: u64,
}
impl Rolling {
fn new(params: &KeyParams) -> Self {
Self {
partial: params.block_hasher(None, 0),
partial_chars: 0,
depth: 0,
}
}
fn feed(&mut self, params: &KeyParams, text: &str, completed: &mut Vec<BlockKey>) {
let block_chars = params.block_chars_usize();
let mut rest = text;
while !rest.is_empty() {
let need = block_chars - self.partial_chars as usize;
let (end, taken) = split_after_chars(rest, need);
self.partial.update(&rest.as_bytes()[..end]);
self.partial_chars += taken as u64;
rest = &rest[end..];
if self.partial_chars == params.block_chars {
self.depth += 1;
let finished = std::mem::replace(&mut self.partial, Sha256::new());
let key: BlockKey = finished.finalize().into();
self.partial = params.block_hasher(Some(&key), self.depth);
self.partial_chars = 0;
completed.push(key);
}
}
}
}
#[derive(Debug, Clone)]
struct Track {
keys: Vec<BlockKey>,
rolling: Rolling,
bytes: u64,
seal: Seal,
attached: bool,
}
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub(crate) struct IndexCounters {
pub(crate) lookups: u64,
pub(crate) hits: u64,
pub(crate) misses: u64,
pub(crate) holder_rejects: u64,
pub(crate) blocks_declined: u64,
pub(crate) reused_ids: u64,
}
#[derive(Debug)]
pub(crate) struct PrefixIndex {
params: KeyParams,
max_blocks: usize,
entries: HashMap<BlockKey, Entry>,
tracks: HashMap<SessionHandle, Track>,
holder_slots: usize,
key_slots: usize,
pub(crate) counters: IndexCounters,
}
impl PrefixIndex {
pub(crate) fn new(params: KeyParams, max_blocks: usize) -> Self {
Self {
params,
max_blocks,
entries: HashMap::new(),
tracks: HashMap::new(),
holder_slots: 0,
key_slots: 0,
counters: IndexCounters::default(),
}
}
pub(crate) fn params(&self) -> KeyParams {
self.params
}
pub(crate) fn enabled(&self) -> bool {
self.max_blocks > 0
}
pub(crate) fn entry_count(&self) -> usize {
self.entries.len()
}
#[cfg(test)]
pub(crate) fn track_count(&self) -> usize {
self.tracks.len()
}
pub(crate) fn approx_bytes(&self) -> u64 {
let estimate = self.bytes_for(self.holder_slots, self.key_slots);
#[cfg(test)]
{
let (holder_slots, key_slots) = self.recount_slots();
assert_eq!(
(self.holder_slots, self.key_slots),
(holder_slots, key_slots),
"running slot totals differ from a recount"
);
}
estimate
}
fn bytes_for(&self, holder_slots: usize, key_slots: usize) -> u64 {
let entry_slot = std::mem::size_of::<BlockKey>() + std::mem::size_of::<Entry>() + 1;
let track_slot = std::mem::size_of::<SessionHandle>() + std::mem::size_of::<Track>() + 1;
(std::mem::size_of::<Self>()
+ self.entries.capacity() * entry_slot
+ holder_slots * std::mem::size_of::<Holder>()
+ self.tracks.capacity() * track_slot
+ key_slots * std::mem::size_of::<BlockKey>()) as u64
}
#[cfg(test)]
pub(crate) fn recount_slots(&self) -> (usize, usize) {
let holders = self
.entries
.values()
.map(|entry| entry.holders.capacity())
.sum();
let keys = self
.tracks
.values()
.map(|track| track.keys.capacity())
.sum();
(holders, keys)
}
#[cfg(test)]
pub(crate) fn approx_bytes_by_walk(&self) -> u64 {
let (holder_slots, key_slots) = self.recount_slots();
self.bytes_for(holder_slots, key_slots)
}
fn put_track(&mut self, handle: SessionHandle, track: Track) {
self.key_slots += track.keys.capacity();
if let Some(replaced) = self.tracks.insert(handle, track) {
self.key_slots -= replaced.keys.capacity();
}
}
fn take_track(&mut self, handle: SessionHandle) -> Option<Track> {
let track = self.tracks.remove(&handle)?;
self.key_slots -= track.keys.capacity();
Some(track)
}
#[cfg(test)]
pub(crate) fn is_tracked(&self, handle: SessionHandle) -> bool {
self.tracks.contains_key(&handle)
}
pub(crate) fn tracked_handles(&self) -> Vec<SessionHandle> {
self.tracks.keys().copied().collect()
}
pub(crate) fn tracked_bytes(&self, handle: SessionHandle) -> Option<u64> {
self.tracks.get(&handle).map(|track| track.bytes)
}
pub(crate) fn insert_session(&mut self, handle: SessionHandle, text: &str, seal_after: Seal) {
if !self.enabled() {
return;
}
self.remove_session(handle);
let mut track = Track {
keys: Vec::new(),
rolling: Rolling::new(&self.params),
bytes: 0,
seal: Seal::default(),
attached: true,
};
self.extend(handle, &mut track, text, seal_after);
self.put_track(handle, track);
}
pub(crate) fn append(&mut self, handle: SessionHandle, delta: &str, seal_after: Seal) {
let Some(mut track) = self.take_track(handle) else {
return;
};
self.extend(handle, &mut track, delta, seal_after);
self.put_track(handle, track);
}
fn extend(&mut self, handle: SessionHandle, track: &mut Track, text: &str, seal_after: Seal) {
track.bytes += text.len() as u64;
if track.attached {
let mut completed = Vec::new();
track.rolling.feed(&self.params, text, &mut completed);
let seal_before = track.seal;
for key in completed {
let full = self.entries.len() >= self.max_blocks;
match self.entries.get_mut(&key) {
Some(entry) => {
entry.refs += 1;
if !seal_before.is_zero() {
let slots = entry.holders.capacity();
list_holder(
entry,
Holder {
handle,
seal: seal_before,
},
);
self.holder_slots =
self.holder_slots - slots + entry.holders.capacity();
}
}
None if full => {
self.counters.blocks_declined += 1;
track.attached = false;
break;
}
None => {
let mut holders = Vec::new();
if !seal_before.is_zero() {
holders.push(Holder {
handle,
seal: seal_before,
});
}
self.holder_slots += holders.capacity();
self.entries.insert(key, Entry { refs: 1, holders });
}
}
track.keys.push(key);
}
}
track.seal = seal_after;
}
pub(crate) fn fork(&mut self, source: SessionHandle, fork: SessionHandle) {
let Some(mut track) = self.tracks.get(&source).cloned() else {
return;
};
self.remove_session(fork);
for (registered, key) in track.keys.iter().enumerate() {
let Some(entry) = self.entries.get_mut(key) else {
track.keys.truncate(registered);
track.attached = false;
break;
};
entry.refs += 1;
let listed = entry
.holders
.iter()
.find(|holder| holder.handle == source)
.map(|holder| holder.seal);
if let Some(seal) = listed {
let slots = entry.holders.capacity();
list_holder(entry, Holder { handle: fork, seal });
self.holder_slots = self.holder_slots - slots + entry.holders.capacity();
}
}
self.put_track(fork, track);
}
pub(crate) fn remove_session(&mut self, handle: SessionHandle) {
let Some(track) = self.take_track(handle) else {
return;
};
for key in &track.keys {
if let Some(entry) = self.entries.get_mut(key) {
let slots = entry.holders.capacity();
entry.holders.retain(|holder| holder.handle != handle);
entry.refs = entry.refs.saturating_sub(1);
if entry.refs == 0 {
self.entries.remove(key);
self.holder_slots -= slots;
} else {
self.holder_slots = self.holder_slots - slots + entry.holders.capacity();
}
}
}
shrink_after_removal(&mut self.entries);
shrink_after_removal(&mut self.tracks);
}
pub(crate) fn probe(&self, key: &BlockKey) -> Option<&[Holder]> {
self.entries.get(key).map(|entry| entry.holders.as_slice())
}
pub(crate) fn is_listed(&self, key: &BlockKey, handle: SessionHandle) -> bool {
self.entries
.get(key)
.is_some_and(|entry| entry.holders.iter().any(|holder| holder.handle == handle))
}
pub(crate) fn reject_holder(&mut self, key: &BlockKey, handle: SessionHandle) {
if let Some(entry) = self.entries.get_mut(key) {
let slots = entry.holders.capacity();
entry.holders.retain(|holder| holder.handle != handle);
self.holder_slots = self.holder_slots - slots + entry.holders.capacity();
}
self.counters.holder_rejects += 1;
}
#[cfg(test)]
pub(crate) fn check_invariants(&self) -> std::result::Result<(), String> {
let mut counted: HashMap<BlockKey, u32> = HashMap::new();
for (handle, track) in &self.tracks {
let mut seen = std::collections::HashSet::new();
for key in &track.keys {
if !seen.insert(*key) {
return Err(format!("handle {} lists a key twice", handle.0));
}
*counted.entry(*key).or_default() += 1;
}
}
if self.entries.len() > self.max_blocks {
return Err(format!(
"{} entries above the cap {}",
self.entries.len(),
self.max_blocks
));
}
if self.recount_slots() != (self.holder_slots, self.key_slots) {
return Err(format!(
"slot totals {:?}, recount {:?}",
(self.holder_slots, self.key_slots),
self.recount_slots()
));
}
if counted.len() != self.entries.len() {
return Err(format!(
"{} keys tracked, {} entries",
counted.len(),
self.entries.len()
));
}
for (key, entry) in &self.entries {
if entry.refs == 0 {
return Err("an entry with no reference".to_owned());
}
if counted.get(key) != Some(&entry.refs) {
return Err(format!(
"entry counts {} references, tracks {:?}",
entry.refs,
counted.get(key)
));
}
if entry.holders.len() > MAX_LISTED_HOLDERS {
return Err(format!("{} listed holders", entry.holders.len()));
}
for holder in &entry.holders {
if holder.seal.is_zero() {
return Err("a listed holder with the zero seal".to_owned());
}
let listed_by_track = self
.tracks
.get(&holder.handle)
.is_some_and(|track| track.keys.contains(key));
if !listed_by_track {
return Err(format!(
"holder {} is not a live session with this block",
holder.handle.0
));
}
}
}
Ok(())
}
#[cfg(test)]
pub(crate) fn refs(&self, key: &BlockKey) -> Option<u32> {
self.entries.get(key).map(|entry| entry.refs)
}
#[cfg(test)]
pub(crate) fn shape(
&self,
) -> (
std::collections::BTreeMap<BlockKey, u32>,
std::collections::BTreeMap<u64, Vec<BlockKey>>,
) {
(
self.entries
.iter()
.map(|(key, entry)| (*key, entry.refs))
.collect(),
self.tracks
.iter()
.map(|(handle, track)| (handle.0, track.keys.clone()))
.collect(),
)
}
}
fn list_holder(entry: &mut Entry, holder: Holder) {
if entry
.holders
.iter()
.any(|listed| listed.handle == holder.handle)
{
return;
}
if entry.holders.len() < MAX_LISTED_HOLDERS {
entry.holders.push(holder);
return;
}
if let Some(oldest) = entry
.holders
.iter_mut()
.min_by_key(|listed| listed.handle)
.filter(|listed| listed.handle < holder.handle)
{
*oldest = holder;
}
}
fn shrink_after_removal<K: std::hash::Hash + Eq, V>(map: &mut HashMap<K, V>) {
if map.is_empty() {
map.shrink_to_fit();
} else if map.capacity() > SHRINK_FLOOR && map.len() * 4 < map.capacity() {
map.shrink_to(map.len() * 2);
}
}
pub(crate) struct Walker<'a> {
params: KeyParams,
text: &'a str,
byte: usize,
parent: Option<BlockKey>,
depth: u64,
}
impl<'a> Walker<'a> {
pub(crate) fn new(params: KeyParams, text: &'a str) -> Self {
Self {
params,
text,
byte: 0,
parent: None,
depth: 0,
}
}
pub(crate) fn next_key(&mut self) -> Option<(BlockKey, usize)> {
let rest = &self.text[self.byte..];
let block_chars = self.params.block_chars_usize();
let (end, taken) = split_after_chars(rest, block_chars);
if taken < block_chars {
return None;
}
let mut hasher = self.params.block_hasher(self.parent.as_ref(), self.depth);
hasher.update(&rest.as_bytes()[..end]);
let key: BlockKey = hasher.finalize().into();
self.parent = Some(key);
self.depth += 1;
self.byte += end;
Some((key, self.byte))
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::BTreeMap;
const BLOCK: u64 = 8;
fn params() -> KeyParams {
KeyParams {
fingerprint: [7; 32],
block_chars: BLOCK,
}
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn below(&mut self, bound: usize) -> usize {
(self.next() % bound as u64) as usize
}
}
const PIECES: [&str; 8] = [
"a",
"b",
"\u{e9}",
"\u{65e5}\u{672c}",
"x y",
"\u{1f642}",
"e\u{301}",
"\n",
];
fn random_text(rng: &mut Rng, pieces: usize) -> String {
(0..pieces)
.map(|_| PIECES[rng.below(PIECES.len())])
.collect()
}
fn random_split<'t>(rng: &mut Rng, text: &'t str) -> Vec<&'t str> {
let mut cuts: Vec<usize> = text
.char_indices()
.map(|(offset, _)| offset)
.filter(|_| rng.below(5) == 0)
.collect();
cuts.push(text.len());
cuts.dedup();
let mut out = Vec::new();
let mut start = 0;
for cut in cuts {
if cut > start {
out.push(&text[start..cut]);
start = cut;
}
}
out
}
fn naive_keys(params: &KeyParams, text: &str) -> Vec<BlockKey> {
let chars: Vec<char> = text.chars().collect();
let mut keys: Vec<BlockKey> = Vec::new();
for (index, block) in chars.chunks_exact(BLOCK as usize).enumerate() {
let bytes: String = block.iter().collect();
let mut hasher = Sha256::new();
hasher.update(DOMAIN);
match keys.last() {
Some(parent) => {
hasher.update([1u8]);
hasher.update(parent);
}
None => {
hasher.update([0u8]);
hasher.update([0u8; 32]);
}
}
hasher.update((index as u64).to_le_bytes());
hasher.update(params.fingerprint);
hasher.update(bytes.as_bytes());
keys.push(hasher.finalize().into());
}
keys
}
fn seal_at(text: &str, chars: usize, ids: u64) -> Seal {
let bytes = text
.char_indices()
.nth(chars)
.map_or(text.len(), |(offset, _)| offset);
Seal {
chars: chars as u64,
bytes: bytes as u64,
ids,
}
}
#[derive(Clone)]
struct ModelSession {
text: String,
seals: Vec<(Seal, u64)>,
block_seals: Vec<Seal>,
keys: Vec<BlockKey>,
}
impl ModelSession {
fn current_seal(&self) -> Seal {
self.seals.last().map_or(Seal::default(), |(seal, _)| *seal)
}
fn chars(&self) -> u64 {
self.text.chars().count() as u64
}
fn apply(&mut self, delta: &str, seal_after: Seal, created: bool) {
let before = if created {
Seal::default()
} else {
self.current_seal()
};
self.text.push_str(delta);
self.keys = naive_keys(¶ms(), &self.text);
let blocks = (self.chars() / BLOCK) as usize;
while self.block_seals.len() < blocks {
self.block_seals.push(before);
}
if self.current_seal() != seal_after || self.seals.is_empty() {
self.seals.push((seal_after, self.chars()));
}
}
}
fn next_seal(rng: &mut Rng, text: &str, previous: Seal, salt: u64) -> Seal {
let chars = text.chars().count();
if chars == 0 || rng.below(4) == 0 {
return previous;
}
let low = previous.chars as usize;
let at = low + rng.below(chars - low + 1);
if at == 0 || at as u64 == previous.chars {
return previous;
}
seal_at(text, at, (at as u64) * 1_000 + salt)
}
struct Harness {
index: PrefixIndex,
live: BTreeMap<u64, ModelSession>,
next_handle: u64,
sealed_registrations: HashMap<BlockKey, usize>,
dead_texts: Vec<Vec<BlockKey>>,
last_dead: String,
}
impl Harness {
fn new(max_blocks: usize) -> Self {
Self {
index: PrefixIndex::new(params(), max_blocks),
live: BTreeMap::new(),
next_handle: 1,
sealed_registrations: HashMap::new(),
dead_texts: Vec::new(),
last_dead: String::new(),
}
}
fn note_registrations(&mut self, session: &ModelSession, first_block: usize) {
for (block, key) in session.keys.iter().enumerate().skip(first_block) {
if !session.block_seals[block].is_zero() {
*self.sealed_registrations.entry(*key).or_default() += 1;
}
}
}
fn insert(&mut self, rng: &mut Rng, text: String) {
let handle = self.next_handle;
self.next_handle += 1;
let seal = next_seal(rng, &text, Seal::default(), handle);
let mut session = ModelSession {
text: String::new(),
seals: Vec::new(),
block_seals: Vec::new(),
keys: Vec::new(),
};
session.apply(&text, seal, true);
self.index
.insert_session(SessionHandle(handle), &text, seal);
self.live.insert(handle, session);
}
fn append(&mut self, rng: &mut Rng, handle: u64, delta: &str) {
let mut session = self.live[&handle].clone();
let blocks_before = session.block_seals.len();
let grown = format!("{}{delta}", session.text);
let seal = next_seal(rng, &grown, session.current_seal(), handle);
session.apply(delta, seal, false);
let pieces = random_split(rng, delta);
let mut seal_so_far = self.live[&handle].current_seal();
let mut model = self.live[&handle].clone();
for (position, piece) in pieces.iter().enumerate() {
let seal_after = if position + 1 == pieces.len() {
seal
} else {
seal_so_far
};
self.index.append(SessionHandle(handle), piece, seal_after);
model.apply(piece, seal_after, false);
seal_so_far = seal_after;
}
assert_eq!(model.block_seals, session.block_seals);
self.note_registrations(&session, blocks_before);
self.live.insert(handle, session);
}
fn fork(&mut self, source: u64) {
let handle = self.next_handle;
self.next_handle += 1;
let session = self.live[&source].clone();
self.index
.fork(SessionHandle(source), SessionHandle(handle));
for key in &session.keys {
if self.index.is_listed(key, SessionHandle(source)) {
*self.sealed_registrations.entry(*key).or_default() += 1;
}
}
self.live.insert(handle, session);
}
fn remove(&mut self, handle: u64) {
let session = self.live.remove(&handle).unwrap();
self.index.remove_session(SessionHandle(handle));
self.last_dead = session.text.clone();
for key in &session.keys {
if self.index.probe(key).is_none() {
self.sealed_registrations.remove(key);
}
}
self.dead_texts.push(session.keys);
if self.dead_texts.len() > 64 {
self.dead_texts.remove(0);
}
}
fn check(&self) {
self.index.check_invariants().unwrap();
let mut refs: HashMap<BlockKey, u32> = HashMap::new();
let mut best: HashMap<BlockKey, u64> = HashMap::new();
let mut block_end: HashMap<BlockKey, u64> = HashMap::new();
for session in self.live.values() {
for (block, key) in session.keys.iter().enumerate() {
*refs.entry(*key).or_default() += 1;
let seal = session.block_seals[block];
let top = best.entry(*key).or_default();
*top = (*top).max(seal.ids);
block_end.insert(*key, (block as u64 + 1) * BLOCK);
}
}
assert_eq!(self.index.entry_count(), refs.len(), "entries");
for (key, count) in &refs {
assert_eq!(self.index.refs(key), Some(*count), "refs");
}
assert_eq!(self.index.track_count(), self.live.len());
for handle in self.live.keys() {
assert!(self.index.is_tracked(SessionHandle(*handle)));
}
for (key, end) in &block_end {
let holders = self.index.probe(key).unwrap();
assert!(holders.len() <= MAX_LISTED_HOLDERS);
for holder in holders {
let session = &self.live[&holder.handle.0];
let made_on = session
.seals
.iter()
.find(|(seal, _)| *seal == holder.seal)
.map(|(_, chars)| *chars)
.expect("a listed seal is one of its session's seals");
assert!(
made_on < *end,
"a seal made on {made_on} characters serves a block ending at {end}"
);
}
let registrations = self.sealed_registrations.get(key).copied().unwrap_or(0);
if registrations <= MAX_LISTED_HOLDERS {
let listed_best = holders.iter().map(|h| h.seal.ids).max().unwrap_or(0);
assert_eq!(listed_best, best[key], "best listed seal");
}
}
for keys in &self.dead_texts {
for key in keys {
assert_eq!(self.index.probe(key).is_some(), refs.contains_key(key));
}
}
}
}
fn related_text(rng: &mut Rng, harness: &Harness) -> String {
let mut text = match harness
.live
.values()
.nth(rng.below(harness.live.len().max(1)))
{
Some(other) if rng.below(3) != 0 => {
let chars = other.text.chars().count();
other.text.chars().take(rng.below(chars + 1)).collect()
}
_ => String::new(),
};
text.push_str(&{
let pieces = rng.below(40);
random_text(rng, pieces)
});
text
}
#[test]
fn the_index_follows_a_naive_model_of_the_live_sessions() {
for seed in [1u64, 2, 0xDEC0DE] {
let mut rng = Rng(seed);
let mut harness = Harness::new(usize::MAX);
for _ in 0..20_000 {
let handles: Vec<u64> = harness.live.keys().copied().collect();
match rng.below(10) {
0 | 1 if harness.live.len() < 24 => {
let text = related_text(&mut rng, &harness);
harness.insert(&mut rng, text);
}
2..=5 if !handles.is_empty() => {
let handle = handles[rng.below(handles.len())];
if harness.live[&handle].text.chars().count() > 240 {
harness.remove(handle);
harness.check();
continue;
}
let delta = {
let pieces = 1 + rng.below(20);
random_text(&mut rng, pieces)
};
harness.append(&mut rng, handle, &delta);
}
6 if !handles.is_empty() && harness.live.len() < 24 => {
harness.fork(handles[rng.below(handles.len())]);
}
7 | 8 if !handles.is_empty() => {
harness.remove(handles[rng.below(handles.len())]);
}
_ => {
let source = if !handles.is_empty() && rng.below(2) == 0 {
harness.live[&handles[rng.below(handles.len())]]
.text
.clone()
} else {
harness.last_dead.clone()
};
let query = format!("{source}{}", random_text(&mut rng, 5));
let mut walker = Walker::new(params(), &query);
for key in naive_keys(¶ms(), &query) {
let (walked, _) = walker.next_key().unwrap();
assert_eq!(walked, key);
let live = harness.live.values().any(|s| s.keys.contains(&key));
assert_eq!(harness.index.probe(&key).is_some(), live);
}
assert!(walker.next_key().is_none());
}
}
harness.check();
}
let handles: Vec<u64> = harness.live.keys().copied().collect();
for handle in handles {
harness.remove(handle);
harness.check();
}
}
}
#[test]
fn removing_every_session_leaves_nothing() {
let mut rng = Rng(9);
let mut harness = Harness::new(usize::MAX);
let empty_bytes = harness.index.approx_bytes();
for _ in 0..300 {
let text = related_text(&mut rng, &harness);
harness.insert(&mut rng, text);
let handles: Vec<u64> = harness.live.keys().copied().collect();
let handle = handles[rng.below(handles.len())];
let delta = random_text(&mut rng, 30);
harness.append(&mut rng, handle, &delta);
if rng.below(3) == 0 {
harness.fork(handle);
}
}
assert!(harness.index.entry_count() > 0);
let handles: Vec<u64> = harness.live.keys().copied().collect();
for handle in handles {
harness.remove(handle);
}
harness.check();
assert_eq!(harness.index.entry_count(), 0);
assert_eq!(harness.index.track_count(), 0);
assert_eq!(harness.index.approx_bytes(), empty_bytes);
}
#[test]
fn the_cap_declines_new_entries_and_keeps_counting_existing_ones() {
let seal = |text: &str| seal_at(text, 1, 5);
let a = "abcdefgh".repeat(4); let mut index = PrefixIndex::new(params(), 3);
index.insert_session(SessionHandle(1), &a[..8], seal(&a));
index.append(SessionHandle(1), &a[8..24], seal(&a));
assert_eq!(index.entry_count(), 3);
index.append(SessionHandle(1), &a[24..], seal(&a));
assert_eq!(index.counters.blocks_declined, 1);
assert_eq!(index.entry_count(), 3);
index.append(SessionHandle(1), &"zzzzzzzz".repeat(2), seal(&a));
assert_eq!(index.counters.blocks_declined, 1);
assert_eq!(index.shape().1[&1].len(), 3);
index.check_invariants().unwrap();
let mut b = a[..24].to_owned();
b.push_str("qqqqqqqq");
index.insert_session(SessionHandle(2), &b, Seal::default());
assert_eq!(index.counters.blocks_declined, 2);
let (entries, tracks) = index.shape();
assert!(entries.values().all(|refs| *refs == 2));
assert_eq!(tracks[&2].len(), 3);
index.check_invariants().unwrap();
index.remove_session(SessionHandle(1));
index.remove_session(SessionHandle(2));
assert_eq!(index.entry_count(), 0);
index.insert_session(SessionHandle(3), &b, Seal::default());
assert_eq!(index.entry_count(), 3);
assert_eq!(index.counters.blocks_declined, 3);
index.remove_session(SessionHandle(3));
index.insert_session(SessionHandle(4), &a[..24], Seal::default());
assert_eq!(index.entry_count(), 3);
assert_eq!(index.counters.blocks_declined, 3);
index.check_invariants().unwrap();
let mut off = PrefixIndex::new(params(), 0);
off.insert_session(SessionHandle(1), &a, Seal::default());
off.append(SessionHandle(1), &a, seal(&a));
off.fork(SessionHandle(1), SessionHandle(2));
assert!(!off.enabled());
assert_eq!(off.entry_count(), 0);
assert_eq!(off.tracked_handles(), Vec::new());
assert_eq!(off.counters.blocks_declined, 0);
}
#[test]
fn many_sessions_on_one_prefix_keep_short_lists_and_right_counts() {
let mut rng = Rng(1024);
let prefix: String = random_text(&mut rng, 25 * BLOCK as usize)
.chars()
.take(25 * BLOCK as usize)
.collect();
let mut index = PrefixIndex::new(params(), usize::MAX);
let mut handles = Vec::new();
for handle in 1..=1024u64 {
let head: String = prefix.chars().take(23 * BLOCK as usize + 3).collect();
index.insert_session(SessionHandle(handle), &head, seal_at(&head, 10, handle));
index.append(
SessionHandle(handle),
&prefix[head.len()..],
seal_at(&prefix, 12, handle + 5_000),
);
handles.push(handle);
}
let keys = naive_keys(¶ms(), &prefix);
assert_eq!(keys.len(), 25);
let check = |index: &PrefixIndex, live: usize| {
index.check_invariants().unwrap();
let (entries, _) = index.shape();
for key in &keys {
assert_eq!(entries.get(key).copied().unwrap_or(0) as usize, live);
if live > 0 {
assert!(index.probe(key).unwrap().len() <= MAX_LISTED_HOLDERS);
}
}
};
check(&index, 1024);
let listed: Vec<u64> = index
.probe(&keys[24])
.unwrap()
.iter()
.map(|h| h.handle.0)
.collect();
assert_eq!(listed.len(), MAX_LISTED_HOLDERS);
assert!(listed.iter().all(|handle| *handle > 1020));
while !handles.is_empty() {
let handle = handles.swap_remove(rng.below(handles.len()));
index.remove_session(SessionHandle(handle));
check(&index, handles.len());
}
assert_eq!(index.entry_count(), 0);
}
#[test]
fn the_walker_and_a_track_compute_the_same_keys() {
for seed in 0..200u64 {
let mut rng = Rng(seed);
let text = {
let pieces = rng.below(120);
random_text(&mut rng, pieces)
};
let expected = naive_keys(¶ms(), &text);
let mut walker = Walker::new(params(), &text);
let mut walked = Vec::new();
let mut last_end = 0;
while let Some((key, end)) = walker.next_key() {
assert!(text.is_char_boundary(end) && end > last_end);
last_end = end;
walked.push(key);
}
assert_eq!(walked, expected);
assert_eq!(
text[..last_end].chars().count() as u64,
expected.len() as u64 * BLOCK
);
let mut index = PrefixIndex::new(params(), usize::MAX);
let pieces = random_split(&mut rng, &text);
let (first, rest) = pieces.split_first().map_or(("", &[][..]), |(f, r)| (*f, r));
index.insert_session(SessionHandle(1), first, Seal::default());
for piece in rest {
index.append(SessionHandle(1), piece, Seal::default());
}
assert_eq!(
index.shape().1.get(&1).cloned().unwrap_or_default(),
expected
);
assert_eq!(
index.tracked_bytes(SessionHandle(1)),
Some(text.len() as u64)
);
}
}
}