use std::collections::{BTreeMap, HashSet};
use std::io::Read as _;
use std::os::unix::fs::MetadataExt as _;
use std::path::{Path, PathBuf};
/// linking keeps the identity, rewriting changes it.
type Identity = (u64, u64, i64, i64);
#[derive(Clone, Copy)]
pub struct File {
identity: Identity,
len: u64,
disk: u64,
}
#[derive(Default)]
pub struct Tree {
files: BTreeMap<PathBuf, File>,
}
/// `follow` walks symlinked directories, the way nginx does through the git mounts.
pub fn scan(root: &Path, follow: bool) -> Tree {
let mut tree = Tree::default();
visit(root, root, follow, &mut tree);
tree
}
fn visit(root: &Path, directory: &Path, follow: bool, tree: &mut Tree) {
let Ok(entries) = std::fs::read_dir(directory) else {
return;
};
for entry in entries.flatten() {
let path = entry.path();
let metadata = if follow {
std::fs::metadata(&path)
} else {
std::fs::symlink_metadata(&path)
};
let Ok(metadata) = metadata else { continue };
if metadata.is_dir() {
visit(root, &path, follow, tree);
} else if metadata.is_file() {
tree.files.insert(
path.strip_prefix(root).unwrap().to_path_buf(),
File {
identity: (
metadata.dev(),
metadata.ino(),
metadata.mtime(),
metadata.mtime_nsec(),
),
len: metadata.len(),
disk: metadata.blocks() * 512,
},
);
}
}
}
impl Tree {
fn unique(&self) -> impl Iterator<Item = (&PathBuf, &File)> {
let mut seen = HashSet::new();
self.files
.iter()
.filter(move |(_, file)| seen.insert(file.identity))
}
pub fn disk_bytes(&self) -> u64 {
self.unique().map(|(_, file)| file.disk).sum()
}
pub fn files(&self) -> u64 {
self.unique().count() as u64
}
}
#[derive(Debug, Default, serde::Serialize, serde::Deserialize)]
pub struct Written {
pub files: u64,
pub bytes: u64,
pub disk_bytes: u64,
pub removed_files: u64,
}
pub fn written(before: &Tree, after: &Tree) -> Written {
let old: HashSet<Identity> = before.files.values().map(|file| file.identity).collect();
let now: HashSet<Identity> = after.files.values().map(|file| file.identity).collect();
let mut written = Written {
removed_files: old.difference(&now).count() as u64,
..Written::default()
};
for (_, file) in after
.unique()
.filter(|(_, file)| !old.contains(&file.identity))
{
written.files += 1;
written.bytes += file.len;
written.disk_bytes += file.disk;
}
written
}
#[derive(Debug, Default, Clone, Copy, serde::Serialize, serde::Deserialize)]
pub struct Kinds {
pub shared: u64,
pub identical: u64,
pub changed: u64,
pub new: u64,
}
impl Kinds {
fn add(&mut self, other: &Kinds) {
self.shared += other.shared;
self.identical += other.identical;
self.changed += other.changed;
self.new += other.new;
}
}
#[derive(Debug, Default, serde::Serialize, serde::Deserialize)]
pub struct Sharing {
pub files: u64,
pub bytes: Kinds,
pub file_counts: Kinds,
pub by_group: BTreeMap<String, Kinds>,
}
pub fn sharing(previous_root: &Path, previous: &Tree, next_root: &Path, next: &Tree) -> Sharing {
let mut sharing = Sharing::default();
for (path, file) in &next.files {
let mut bytes = Kinds::default();
let mut count = Kinds::default();
let (slot, tally) = match previous.files.get(path) {
None => (&mut bytes.new, &mut count.new),
Some(old) if old.identity == file.identity => (&mut bytes.shared, &mut count.shared),
Some(old)
if old.len == file.len
&& same_bytes(&previous_root.join(path), &next_root.join(path)) =>
{
(&mut bytes.identical, &mut count.identical)
}
Some(_) => (&mut bytes.changed, &mut count.changed),
};
*slot = file.len;
*tally = 1;
sharing.files += 1;
sharing.bytes.add(&bytes);
sharing.file_counts.add(&count);
sharing.by_group.entry(group(path)).or_default().add(&bytes);
}
sharing
}
fn same_bytes(left: &Path, right: &Path) -> bool {
let (Ok(mut left), Ok(mut right)) = (std::fs::File::open(left), std::fs::File::open(right))
else {
return false;
};
let mut a = vec![0; 1 << 16];
let mut b = vec![0; 1 << 16];
loop {
let n = left.read(&mut a).unwrap_or(0);
if right.read_exact(&mut b[..n]).is_err() || a[..n] != b[..n] {
return false;
}
if n == 0 {
return right.read(&mut b[..1]).is_ok_and(|more| more == 0);
}
}
}
pub fn group(path: &Path) -> String {
path.components()
.take(5)
.map(|component| wildcard(&component.as_os_str().to_string_lossy()))
.collect::<Vec<_>>()
.join("/")
}
fn wildcard(name: &str) -> String {
name.split('.')
.map(|piece| {
piece
.split('-')
.map(wildcard_part)
.collect::<Vec<_>>()
.join("-")
})
.collect::<Vec<_>>()
.join(".")
}
fn wildcard_part(part: &str) -> String {
if part.len() >= 16 && part.bytes().all(|byte| byte.is_ascii_hexdigit()) {
return "*".to_string();
}
let mut out = String::new();
for character in part.chars() {
if !character.is_ascii_digit() {
out.push(character);
} else if !out.ends_with('N') {
out.push('N');
}
}
out
}