use std::collections::BTreeMap;
use std::path::Path;
use std::time::UNIX_EPOCH;
use anyhow::{Context, Result};
use chrono::{DateTime, Utc};
use sha2::{Digest, Sha256};
use uuid::Uuid;
use super::symbols::{self, DiscoveredFile, SymbolScan};
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct FileFingerprint {
pub mtime_ns: i128,
pub size: u64,
pub hash: [u8; 32],
}
#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize)]
pub struct Manifest {
pub files: BTreeMap<String, FileFingerprint>,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct DeltaPlan {
pub added: Vec<String>,
pub changed: Vec<String>,
pub removed: Vec<String>,
pub renamed: Vec<(String, String)>,
}
impl DeltaPlan {
pub fn is_empty(&self) -> bool {
self.added.is_empty()
&& self.changed.is_empty()
&& self.removed.is_empty()
&& self.renamed.is_empty()
}
pub fn touched(&self) -> usize {
self.added.len() + self.changed.len() + self.removed.len() + self.renamed.len()
}
fn to_reparse(&self) -> impl Iterator<Item = &String> {
self.added.iter().chain(self.changed.iter())
}
fn to_evict(&self) -> impl Iterator<Item = &String> {
self.changed.iter().chain(self.removed.iter())
}
}
pub fn diff(old: &Manifest, new: &Manifest) -> DeltaPlan {
let mut plan = DeltaPlan::default();
for (path, nf) in &new.files {
match old.files.get(path) {
None => plan.added.push(path.clone()),
Some(of) if of.hash != nf.hash => plan.changed.push(path.clone()),
Some(_) => {} }
}
for path in old.files.keys() {
if !new.files.contains_key(path) {
plan.removed.push(path.clone());
}
}
detect_renames(&mut plan, old, new);
plan
}
fn detect_renames(plan: &mut DeltaPlan, old: &Manifest, new: &Manifest) {
if plan.added.is_empty() || plan.removed.is_empty() {
return;
}
let mut removed_by_hash: BTreeMap<[u8; 32], Vec<String>> = BTreeMap::new();
for r in &plan.removed {
if let Some(f) = old.files.get(r) {
removed_by_hash.entry(f.hash).or_default().push(r.clone());
}
}
let mut consumed_removed: Vec<String> = Vec::new();
let mut still_added: Vec<String> = Vec::new();
for a in std::mem::take(&mut plan.added) {
let hash = new.files.get(&a).map(|f| f.hash);
let matched = hash
.and_then(|h| removed_by_hash.get_mut(&h))
.and_then(|q| if q.is_empty() { None } else { Some(q.remove(0)) });
match matched {
Some(old_path) => {
consumed_removed.push(old_path.clone());
plan.renamed.push((old_path, a));
}
None => still_added.push(a),
}
}
plan.added = still_added;
plan.removed.retain(|r| !consumed_removed.contains(r));
}
impl Manifest {
pub fn build(repo_root: &Path, files: &[DiscoveredFile]) -> Result<Self> {
Ok(Self::refresh_inner(repo_root, files, None)?.0)
}
pub fn refresh(&self, repo_root: &Path, files: &[DiscoveredFile]) -> Result<(Manifest, DeltaPlan)> {
Self::refresh_inner(repo_root, files, Some(self))
}
fn refresh_inner(
repo_root: &Path,
files: &[DiscoveredFile],
old: Option<&Manifest>,
) -> Result<(Manifest, DeltaPlan)> {
let mut new = Manifest::default();
for f in files {
let rel = symbols::rel_path(repo_root, &f.path);
let meta = std::fs::metadata(&f.path)
.with_context(|| format!("stat {}", f.path.display()))?;
let size = meta.len();
let mtime_ns = meta
.modified()
.ok()
.and_then(|m| m.duration_since(UNIX_EPOCH).ok())
.map(|d| d.as_nanos() as i128)
.unwrap_or(0);
let reused = old
.and_then(|o| o.files.get(&rel))
.filter(|of| of.mtime_ns == mtime_ns && of.size == size && mtime_ns != 0);
let fp = match reused {
Some(of) => of.clone(),
None => {
let bytes = std::fs::read(&f.path)
.with_context(|| format!("read {}", f.path.display()))?;
let mut hasher = Sha256::new();
hasher.update(&bytes);
FileFingerprint { mtime_ns, size, hash: hasher.finalize().into() }
}
};
new.files.insert(rel, fp);
}
let plan = diff(old.unwrap_or(&EMPTY_MANIFEST), &new);
Ok((new, plan))
}
}
static EMPTY_MANIFEST: Manifest = Manifest { files: BTreeMap::new() };
#[derive(Debug)]
pub struct SymbolDelta {
pub repo: String,
pub manifest: Manifest,
pub scan: SymbolScan,
}
impl SymbolDelta {
pub fn full_build(
repo_root: &Path,
repo_name: &str,
snapshot_id: Uuid,
ts: DateTime<Utc>,
) -> Result<Self> {
let files = symbols::discover_files(repo_root);
let manifest = Manifest::build(repo_root, &files)?;
let scan = symbols::scan_repo(repo_root, repo_name, snapshot_id, ts)?;
Ok(Self { repo: repo_name.to_string(), manifest, scan })
}
pub fn rescan(
&mut self,
repo_root: &Path,
snapshot_id: Uuid,
ts: DateTime<Utc>,
) -> Result<DeltaPlan> {
let files = symbols::discover_files(repo_root);
let (new_manifest, plan) = self.manifest.refresh(repo_root, &files)?;
if plan.is_empty() {
functional_mark("scan", true, &format!("no-op repo={} files={}", self.repo, files.len()));
self.manifest = new_manifest;
return Ok(plan);
}
let mut evicted = 0usize;
for rel in plan.to_evict() {
evicted += evict_file(&mut self.scan, rel);
}
functional_mark(
"evict",
true,
&format!("repo={} files={} rows={evicted}", self.repo, plan.changed.len() + plan.removed.len()),
);
let reparse: Vec<DiscoveredFile> = {
let want: std::collections::BTreeSet<&str> =
plan.to_reparse().map(|s| s.as_str()).collect();
files
.iter()
.filter(|f| want.contains(symbols::rel_path(repo_root, &f.path).as_str()))
.cloned()
.collect()
};
let delta_scan =
symbols::scan_selected_files(repo_root, &self.repo, snapshot_id, ts, &reparse);
functional_mark(
"scan",
true,
&format!(
"repo={} reparsed={} syms+={} calls+={}",
self.repo,
reparse.len(),
delta_scan.symbols.len(),
delta_scan.calls.len()
),
);
merge_scan(&mut self.scan, delta_scan);
let mut relabelled = 0usize;
for (old_rel, new_rel) in &plan.renamed {
relabelled += relabel_file(&mut self.scan, old_rel, new_rel);
}
functional_mark(
"merge",
true,
&format!("repo={} renamed={} relabelled_rows={relabelled}", self.repo, plan.renamed.len()),
);
self.manifest = new_manifest;
Ok(plan)
}
pub fn evict_file(&mut self, rel: &str) -> usize {
evict_file(&mut self.scan, rel)
}
}
fn evict_file(scan: &mut SymbolScan, rel: &str) -> usize {
let before = scan.symbols.len() + scan.calls.len() + scan.features.len() + scan.tests.len();
scan.symbols.retain(|r| r.file != rel);
scan.calls.retain(|r| r.file != rel);
scan.features.retain(|r| r.file != rel);
scan.tests.retain(|r| r.file != rel);
before - (scan.symbols.len() + scan.calls.len() + scan.features.len() + scan.tests.len())
}
fn merge_scan(scan: &mut SymbolScan, mut delta: SymbolScan) {
scan.symbols.append(&mut delta.symbols);
scan.calls.append(&mut delta.calls);
scan.features.append(&mut delta.features);
scan.tests.append(&mut delta.tests);
}
fn relabel_file(scan: &mut SymbolScan, old_rel: &str, new_rel: &str) -> usize {
let mut n = 0usize;
for r in scan.symbols.iter_mut().filter(|r| r.file == old_rel) {
r.file = new_rel.to_string();
n += 1;
}
for r in scan.calls.iter_mut().filter(|r| r.file == old_rel) {
r.file = new_rel.to_string();
n += 1;
}
for r in scan.features.iter_mut().filter(|r| r.file == old_rel) {
r.file = new_rel.to_string();
n += 1;
}
for r in scan.tests.iter_mut().filter(|r| r.file == old_rel) {
r.file = new_rel.to_string();
n += 1;
}
n
}
#[inline]
fn functional_mark(branch: &str, ok: bool, detail: &str) {
nornir_testmatrix::functional_status("introspect-delta", branch, ok, detail);
}
#[cfg(test)]
mod tests {
use super::*;
fn fp(mtime: i128, size: u64, seed: u8) -> FileFingerprint {
FileFingerprint { mtime_ns: mtime, size, hash: [seed; 32] }
}
fn manifest(entries: &[(&str, FileFingerprint)]) -> Manifest {
let mut m = Manifest::default();
for (p, f) in entries {
m.files.insert((*p).to_string(), f.clone());
}
m
}
#[test]
fn diff_detects_added_changed_removed() {
let old = manifest(&[("a.rs", fp(1, 10, 1)), ("b.rs", fp(1, 20, 2))]);
let new = manifest(&[("a.rs", fp(9, 10, 1)), ("b.rs", fp(1, 20, 9)), ("c.rs", fp(1, 5, 3))]);
let plan = diff(&old, &new);
assert_eq!(plan.added, vec!["c.rs".to_string()]);
assert_eq!(plan.changed, vec!["b.rs".to_string()]);
assert!(plan.removed.is_empty());
assert!(plan.renamed.is_empty());
}
#[test]
fn diff_detects_removed() {
let old = manifest(&[("a.rs", fp(1, 10, 1)), ("gone.rs", fp(1, 20, 2))]);
let new = manifest(&[("a.rs", fp(1, 10, 1))]);
let plan = diff(&old, &new);
assert_eq!(plan.removed, vec!["gone.rs".to_string()]);
assert!(plan.added.is_empty() && plan.changed.is_empty());
}
#[test]
fn diff_detects_rename_by_identical_content() {
let old = manifest(&[("old.rs", fp(1, 10, 7))]);
let new = manifest(&[("new.rs", fp(2, 10, 7))]);
let plan = diff(&old, &new);
assert_eq!(plan.renamed, vec![("old.rs".to_string(), "new.rs".to_string())]);
assert!(plan.added.is_empty(), "rename is not an add");
assert!(plan.removed.is_empty(), "rename is not a remove");
}
#[test]
fn diff_empty_when_nothing_changed() {
let m = manifest(&[("a.rs", fp(1, 10, 1)), ("b.rs", fp(1, 20, 2))]);
assert!(diff(&m, &m.clone()).is_empty());
}
fn scaffold(n: usize) -> tempfile::TempDir {
let dir = tempfile::tempdir().unwrap();
std::fs::write(
dir.path().join("Cargo.toml"),
"[package]\nname = \"deltacrate\"\nversion = \"0.0.0\"\nedition = \"2021\"\n",
)
.unwrap();
let src = dir.path().join("src");
std::fs::create_dir_all(&src).unwrap();
let mut lib = String::new();
for i in 0..n {
std::fs::write(src.join(format!("foo{i}.rs")), format!("pub fn item{i}() {{}}\n")).unwrap();
lib.push_str(&format!("pub mod foo{i};\n"));
}
std::fs::write(src.join("lib.rs"), lib).unwrap();
dir
}
fn sym_names(scan: &SymbolScan) -> std::collections::BTreeSet<String> {
scan.symbols.iter().map(|s| s.item_name.clone()).collect()
}
#[test]
fn full_build_then_noop_rescan_is_empty() {
let dir = scaffold(3);
let mut wh =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
let baseline = sym_names(&wh.scan);
let plan = wh.rescan(dir.path(), Uuid::new_v4(), Utc::now()).unwrap();
assert!(plan.is_empty(), "unchanged tree ⇒ empty delta: {plan:?}");
assert_eq!(sym_names(&wh.scan), baseline, "no-op rescan must not alter the row set");
}
#[test]
fn edit_one_file_reparses_only_it_and_evicts_old_symbols() {
let dir = scaffold(5);
let mut wh =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
assert!(sym_names(&wh.scan).contains("item2"));
std::fs::write(
dir.path().join("src/foo2.rs"),
"pub fn renamed_item() {}\npub struct NewType;\n",
)
.unwrap();
filetime_bump(&dir.path().join("src/foo2.rs"));
let plan = wh.rescan(dir.path(), Uuid::new_v4(), Utc::now()).unwrap();
assert_eq!(plan.touched(), 1, "exactly one file changed: {plan:?}");
assert_eq!(plan.changed, vec!["src/foo2.rs".to_string()]);
let names = sym_names(&wh.scan);
assert!(!names.contains("item2"), "evict-on-change: item2 must be gone: {names:?}");
assert!(names.contains("renamed_item"));
assert!(names.contains("NewType"));
assert!(names.contains("item0") && names.contains("item4"));
}
#[test]
fn added_and_removed_files_update_the_symbol_set() {
let dir = scaffold(2);
let mut wh =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
std::fs::write(dir.path().join("src/foo9.rs"), "pub fn added9() {}\n").unwrap();
std::fs::remove_file(dir.path().join("src/foo0.rs")).unwrap();
let plan = wh.rescan(dir.path(), Uuid::new_v4(), Utc::now()).unwrap();
assert_eq!(plan.added, vec!["src/foo9.rs".to_string()]);
assert_eq!(plan.removed, vec!["src/foo0.rs".to_string()]);
let names = sym_names(&wh.scan);
assert!(names.contains("added9"), "added file's symbol present");
assert!(!names.contains("item0"), "removed file's symbol evicted");
assert!(names.contains("item1"), "untouched file's symbol kept");
}
#[test]
fn rename_relabels_rows_without_reparsing() {
let dir = scaffold(3);
let mut wh =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
let from = dir.path().join("src/foo1.rs");
let to = dir.path().join("src/bar1.rs");
std::fs::rename(&from, &to).unwrap();
let plan = wh.rescan(dir.path(), Uuid::new_v4(), Utc::now()).unwrap();
assert_eq!(
plan.renamed,
vec![("src/foo1.rs".to_string(), "src/bar1.rs".to_string())],
"content-identical move is a rename: {plan:?}"
);
assert!(wh.scan.symbols.iter().any(|s| s.item_name == "item1" && s.file == "src/bar1.rs"));
assert!(!wh.scan.symbols.iter().any(|s| s.file == "src/foo1.rs"), "old path gone");
}
#[test]
fn delta_matches_full_rebuild() {
let dir = scaffold(4);
let mut wh =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
std::fs::write(dir.path().join("src/foo1.rs"), "pub fn changed1() {}\n").unwrap();
filetime_bump(&dir.path().join("src/foo1.rs"));
std::fs::write(dir.path().join("src/foo7.rs"), "pub fn brand_new() {}\n").unwrap();
std::fs::remove_file(dir.path().join("src/foo3.rs")).unwrap();
wh.rescan(dir.path(), Uuid::new_v4(), Utc::now()).unwrap();
let from_scratch =
SymbolDelta::full_build(dir.path(), "deltacrate", Uuid::new_v4(), Utc::now()).unwrap();
assert_eq!(
sym_names(&wh.scan),
sym_names(&from_scratch.scan),
"delta warehouse must equal a full rebuild of the mutated tree"
);
}
fn filetime_bump(path: &Path) {
let content = std::fs::read(path).unwrap();
std::thread::sleep(std::time::Duration::from_millis(10));
std::fs::write(path, &content).unwrap();
}
}