use super::format::compute_file_hash;
use std::{
collections::{BTreeSet, HashMap, HashSet},
path::{Path, PathBuf},
};
const DEFAULT_MAX_PATHS: usize = 30;
const DEFAULT_MAX_VERSIONS_PER_PATH: usize = 4;
const DEFAULT_MAX_TOTAL_BYTES: usize = 64 * 1024 * 1024;
#[derive(Debug, Clone)]
pub struct HashlineSnapshotStore {
snapshots_by_path: HashMap<PathBuf, Vec<HashlineSnapshot>>,
tick: u64,
total_text_bytes: usize,
coldest_paths: BTreeSet<(u64, PathBuf)>,
max_paths: usize,
max_versions_per_path: usize,
max_total_bytes: usize,
}
impl Default for HashlineSnapshotStore {
fn default() -> Self {
Self {
snapshots_by_path: HashMap::new(),
tick: 0,
total_text_bytes: 0,
coldest_paths: BTreeSet::new(),
max_paths: DEFAULT_MAX_PATHS,
max_versions_per_path: DEFAULT_MAX_VERSIONS_PER_PATH,
max_total_bytes: DEFAULT_MAX_TOTAL_BYTES,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct HashlineSnapshot {
pub path: PathBuf,
pub hash: String,
pub text: String,
pub seen_lines: HashSet<usize>,
recorded_at: u64,
last_accessed: u64,
}
impl HashlineSnapshotStore {
pub fn len(&self) -> usize {
self.snapshots_by_path.values().map(Vec::len).sum()
}
#[cfg(test)]
pub fn with_limits(
max_paths: usize,
max_versions_per_path: usize,
max_total_bytes: usize,
) -> Self {
Self {
max_paths,
max_versions_per_path,
max_total_bytes,
..Self::default()
}
}
pub fn record(
&mut self,
path: impl Into<PathBuf>,
normalized_text: impl Into<String>,
seen_lines: impl IntoIterator<Item = usize>,
) -> String {
let path = path.into();
let text = normalized_text.into();
let hash = compute_file_hash(&text);
let seen_lines = seen_lines.into_iter().collect::<HashSet<_>>();
self.tick = self.tick.saturating_add(1);
let now = self.tick;
self.remove_path_metadata(&path);
let history = self.snapshots_by_path.entry(path.clone()).or_default();
if let Some(index) = history
.iter()
.position(|snapshot| snapshot.hash == hash && snapshot.text == text)
{
let mut snapshot = history.remove(index);
snapshot.recorded_at = now;
snapshot.last_accessed = now;
snapshot.seen_lines.extend(seen_lines);
history.insert(0, snapshot);
self.refresh_path_metadata(path);
self.evict_to_limits();
return hash;
}
history.insert(
0,
HashlineSnapshot {
path: path.clone(),
hash: hash.clone(),
text,
seen_lines,
recorded_at: now,
last_accessed: now,
},
);
history.truncate(self.max_versions_per_path);
self.refresh_path_metadata(path);
self.evict_to_limits();
hash
}
pub fn by_hash(&self, hash: &str) -> Vec<&HashlineSnapshot> {
self.snapshots_by_path
.values()
.flat_map(|snapshots| snapshots.iter())
.filter(|snapshot| snapshot.hash == hash)
.collect()
}
pub fn find_by_hash(&self, path: &Path, hash: &str) -> Option<&HashlineSnapshot> {
self.snapshots_by_path
.get(path)?
.iter()
.find(|snapshot| snapshot.hash == hash)
}
pub fn head(&self, path: &Path) -> Option<&HashlineSnapshot> {
self.snapshots_by_path.get(path)?.first()
}
pub fn by_content(&self, path: &Path, normalized_text: &str) -> Option<&HashlineSnapshot> {
self.snapshots_by_path
.get(path)?
.iter()
.find(|snapshot| snapshot.text == normalized_text)
}
pub fn record_seen_lines(
&mut self,
path: &Path,
hash: &str,
lines: impl IntoIterator<Item = usize>,
) {
let lines = lines.into_iter().collect::<HashSet<_>>();
if lines.is_empty() {
return;
}
let path = path.to_path_buf();
self.remove_path_metadata(&path);
let now = self.tick.saturating_add(1);
let found = self
.snapshots_by_path
.get_mut(&path)
.and_then(|history| history.iter_mut().find(|snapshot| snapshot.hash == hash))
.map(|snapshot| {
snapshot.seen_lines.extend(lines);
snapshot.last_accessed = now;
})
.is_some();
if found {
self.tick = now;
}
self.refresh_path_metadata(path);
}
pub fn invalidate(&mut self, path: &Path) {
self.remove_path(path);
}
pub fn relocate(&mut self, from: &Path, to: impl Into<PathBuf>) {
let to = to.into();
if from == to {
return;
}
if !self.snapshots_by_path.contains_key(from) {
return;
}
self.remove_path_metadata(from);
self.remove_path_metadata(&to);
let Some(mut relocated) = self.snapshots_by_path.remove(from) else {
return;
};
for snapshot in &mut relocated {
snapshot.path = to.clone();
}
if let Some(destination) = self.snapshots_by_path.get_mut(&to) {
relocated.append(destination);
let mut seen = HashSet::new();
relocated
.retain(|snapshot| seen.insert((snapshot.hash.clone(), snapshot.text.clone())));
relocated.truncate(self.max_versions_per_path);
*destination = relocated;
} else {
relocated.truncate(self.max_versions_per_path);
self.snapshots_by_path.insert(to.clone(), relocated);
}
self.refresh_path_metadata(to);
self.evict_to_limits();
}
fn evict_to_limits(&mut self) {
while self.snapshots_by_path.len() > self.max_paths
|| self.total_text_bytes > self.max_total_bytes
{
let Some((_, path)) = self.coldest_paths.iter().next().cloned() else {
break;
};
self.remove_path(&path);
}
}
#[cfg(test)]
fn total_text_bytes(&self) -> usize {
self.total_text_bytes
}
fn remove_path_metadata(&mut self, path: &Path) {
let Some(history) = self.snapshots_by_path.get(path) else {
return;
};
let bytes: usize = history.iter().map(|snapshot| snapshot.text.len()).sum();
if let Some(last_accessed) = history.iter().map(|snapshot| snapshot.last_accessed).min() {
self.coldest_paths
.remove(&(last_accessed, path.to_path_buf()));
}
self.total_text_bytes = self.total_text_bytes.saturating_sub(bytes);
}
fn refresh_path_metadata(&mut self, path: PathBuf) {
let Some(history) = self.snapshots_by_path.get(&path) else {
return;
};
let bytes: usize = history.iter().map(|snapshot| snapshot.text.len()).sum();
let last_accessed = history
.iter()
.map(|snapshot| snapshot.last_accessed)
.min()
.unwrap_or(0);
self.total_text_bytes = self.total_text_bytes.saturating_add(bytes);
self.coldest_paths.insert((last_accessed, path));
}
fn remove_path(&mut self, path: &Path) {
self.remove_path_metadata(path);
self.snapshots_by_path.remove(path);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn assert_accounting(store: &HashlineSnapshotStore) {
let expected: usize = store
.snapshots_by_path
.values()
.flatten()
.map(|snapshot| snapshot.text.len())
.sum();
assert_eq!(store.total_text_bytes(), expected);
}
#[test]
fn snapshot_store_records_finds_invalidates_and_relocates() {
let mut store = HashlineSnapshotStore::default();
let old = PathBuf::from("a.txt");
let new = PathBuf::from("b.txt");
let hash = store.record(&old, "one\n", [1]);
assert_accounting(&store);
assert_eq!(store.len(), 1);
assert_eq!(store.by_hash(&hash).len(), 1);
assert!(
store
.find_by_hash(&old, &hash)
.unwrap()
.seen_lines
.contains(&1)
);
store.relocate(&old, &new);
assert_accounting(&store);
assert!(store.find_by_hash(&old, &hash).is_none());
assert_eq!(store.find_by_hash(&new, &hash).unwrap().path, new);
store.invalidate(&new);
assert_accounting(&store);
assert_eq!(store.len(), 0);
}
#[test]
fn record_dedups_same_text_and_unions_seen_lines() {
let mut store = HashlineSnapshotStore::default();
let path = PathBuf::from("a.txt");
let hash = store.record(&path, "one\ntwo\n", [1]);
assert_eq!(store.record(&path, "one\ntwo\n", [2]), hash);
assert_eq!(
store.find_by_hash(&path, &hash).unwrap().seen_lines,
HashSet::from([1, 2])
);
assert_accounting(&store);
}
#[test]
fn record_retains_bounded_versions_and_paths() {
let mut store = HashlineSnapshotStore::with_limits(2, 2, usize::MAX);
store.record("a.txt", "a1", []);
store.record("a.txt", "a2", []);
store.record("a.txt", "a3", []);
assert_eq!(store.snapshots_by_path[Path::new("a.txt")].len(), 2);
store.record("b.txt", "b", []);
store.record("c.txt", "c", []);
assert!(store.snapshots_by_path.len() <= 2);
assert_accounting(&store);
}
#[test]
fn record_evicts_cold_paths_to_total_byte_limit() {
let mut store = HashlineSnapshotStore::with_limits(30, 4, 3);
store.record("a.txt", "aaa", []);
store.record("b.txt", "bbb", []);
assert!(store.total_text_bytes() <= 3);
assert_accounting(&store);
}
#[test]
fn seen_lines_refreshes_recency_for_eviction() {
let mut store = HashlineSnapshotStore::with_limits(2, 4, usize::MAX);
let a_hash = store.record("a.txt", "a", []);
store.record("b.txt", "b", []);
store.record_seen_lines(Path::new("a.txt"), &a_hash, [1]);
store.record("c.txt", "c", []);
assert!(store.find_by_hash(Path::new("a.txt"), &a_hash).is_some());
assert_accounting(&store);
}
#[test]
fn relocate_merges_dedupes_and_truncates_accounting() {
let mut store = HashlineSnapshotStore::with_limits(30, 2, usize::MAX);
let source_hash = store.record("source", "same", []);
store.record("source", "old", []);
store.record("destination", "same", []);
store.record("destination", "new", []);
store.relocate(Path::new("source"), PathBuf::from("destination"));
assert_eq!(store.len(), 2);
assert!(
store
.find_by_hash(Path::new("destination"), &source_hash)
.is_some()
);
assert_accounting(&store);
}
#[test]
fn missing_relocate_preserves_destination_accounting() {
let mut store = HashlineSnapshotStore::with_limits(30, 4, usize::MAX);
let hash = store.record("destination", "value", []);
store.relocate(Path::new("missing"), PathBuf::from("destination"));
assert_eq!(store.total_text_bytes(), "value".len());
assert!(
store
.find_by_hash(Path::new("destination"), &hash)
.is_some()
);
assert_accounting(&store);
}
}