use anyhow::{Context, Result, bail};
use std::fs::File;
use std::io::{BufReader, BufWriter, Read, Seek, SeekFrom, Write};
use std::path::{Path, PathBuf};
const MAGIC: &[u8; 8] = b"FCMANIF1";
const HEADER_LEN: u64 = 8 + 4 + 8 + 4 + 8;
pub const DEFAULT_BLOCK_SIZE: usize = 1024;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Record {
pub path: String,
pub size: i64,
pub mtime: i64,
pub crc32c: Option<u32>,
}
impl Record {
pub fn tombstone(path: String) -> Record {
Record {
path,
size: -1,
mtime: -1,
crc32c: None,
}
}
pub fn is_tombstone(&self) -> bool {
self.size < 0
}
}
pub fn path_cmp(a: &str, b: &str) -> std::cmp::Ordering {
#[inline]
fn key(byte: u8) -> u8 {
if byte == b'/' { 0 } else { byte }
}
let (a, b) = (a.as_bytes(), b.as_bytes());
let n = a.len().min(b.len());
for i in 0..n {
let (ka, kb) = (key(a[i]), key(b[i]));
if ka != kb {
return ka.cmp(&kb);
}
}
a.len().cmp(&b.len())
}
fn put_uvarint(out: &mut Vec<u8>, mut v: u64) {
loop {
let b = (v & 0x7f) as u8;
v >>= 7;
if v != 0 {
out.push(b | 0x80);
} else {
out.push(b);
break;
}
}
}
fn get_uvarint(buf: &[u8], pos: &mut usize) -> Result<u64> {
let mut v = 0u64;
let mut shift = 0;
loop {
let b = *buf.get(*pos).context("truncated varint")?;
*pos += 1;
v |= ((b & 0x7f) as u64) << shift;
if b & 0x80 == 0 {
break;
}
shift += 7;
if shift >= 64 {
bail!("varint overflow");
}
}
Ok(v)
}
fn common_prefix(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
let mut i = 0;
while i < n && a[i] == b[i] {
i += 1;
}
i
}
fn encode_block(records: &[Record]) -> Vec<u8> {
let mut out = Vec::new();
let mut prev: &[u8] = b"";
for r in records {
let p = r.path.as_bytes();
let lcp = common_prefix(prev, p);
let suf = &p[lcp..];
put_uvarint(&mut out, lcp as u64);
put_uvarint(&mut out, suf.len() as u64);
out.extend_from_slice(suf);
put_uvarint(&mut out, r.size as u64);
put_uvarint(&mut out, r.mtime as u64);
put_uvarint(&mut out, r.crc32c.map_or(0, |c| c as u64 + 1));
prev = p;
}
out
}
fn decode_block(buf: &[u8], out: &mut Vec<Record>) -> Result<()> {
let mut pos = 0;
let mut prev: Vec<u8> = Vec::new();
while pos < buf.len() {
let lcp = get_uvarint(buf, &mut pos)? as usize;
let sl = get_uvarint(buf, &mut pos)? as usize;
if lcp > prev.len() || pos + sl > buf.len() {
bail!("corrupt block");
}
let mut path = Vec::with_capacity(lcp + sl);
path.extend_from_slice(&prev[..lcp]);
path.extend_from_slice(&buf[pos..pos + sl]);
pos += sl;
let size = get_uvarint(buf, &mut pos)? as i64;
let mtime = get_uvarint(buf, &mut pos)? as i64;
let crcv = get_uvarint(buf, &mut pos)?;
let crc32c = if crcv == 0 {
None
} else {
Some((crcv - 1) as u32)
};
prev = path.clone();
out.push(Record {
path: String::from_utf8(path).context("non-utf8 path in block")?,
size,
mtime,
crc32c,
});
}
Ok(())
}
pub struct FcmWriter {
path: PathBuf,
w: BufWriter<File>,
block_size: usize,
level: i32,
buf: Vec<Record>,
index: Vec<(u64, u32, String)>,
offset: u64,
record_count: u64,
block_count: u32,
last_path: Option<String>,
}
impl FcmWriter {
pub fn create(path: &Path, block_size: usize, level: i32) -> Result<Self> {
let f = File::create(path).with_context(|| format!("creating {}", path.display()))?;
let mut w = BufWriter::new(f);
w.write_all(&[0u8; HEADER_LEN as usize])?;
Ok(Self {
path: path.to_path_buf(),
w,
block_size: block_size.max(1),
level,
buf: Vec::with_capacity(block_size.max(1)),
index: Vec::new(),
offset: HEADER_LEN,
record_count: 0,
block_count: 0,
last_path: None,
})
}
pub fn push(&mut self, rec: Record) -> Result<()> {
debug_assert!(
self.last_path
.as_deref()
.is_none_or(|p| path_cmp(p, rec.path.as_str()) != std::cmp::Ordering::Greater),
"FcmWriter requires sorted input"
);
self.last_path = Some(rec.path.clone());
self.buf.push(rec);
if self.buf.len() >= self.block_size {
self.flush_block()?;
}
Ok(())
}
fn flush_block(&mut self) -> Result<()> {
if self.buf.is_empty() {
return Ok(());
}
let body = encode_block(&self.buf);
let comp = zstd::encode_all(&body[..], self.level).context("zstd block")?;
let comp_len = comp.len() as u32;
self.w.write_all(&comp_len.to_le_bytes())?;
self.w.write_all(&comp)?;
self.index
.push((self.offset, comp_len, self.buf[0].path.clone()));
self.offset += 4 + comp.len() as u64;
self.record_count += self.buf.len() as u64;
self.block_count += 1;
self.buf.clear();
Ok(())
}
pub fn finish(mut self) -> Result<u64> {
self.flush_block()?;
let index_offset = self.offset;
for (boff, clen, first) in &self.index {
self.w.write_all(&boff.to_le_bytes())?;
self.w.write_all(&clen.to_le_bytes())?;
let fb = first.as_bytes();
self.w.write_all(&(fb.len() as u32).to_le_bytes())?;
self.w.write_all(fb)?;
}
self.w.flush()?;
let mut file = self.w.into_inner()?;
file.seek(SeekFrom::Start(0))?;
let mut header = Vec::with_capacity(HEADER_LEN as usize);
header.extend_from_slice(MAGIC);
header.extend_from_slice(&(self.block_size as u32).to_le_bytes());
header.extend_from_slice(&self.record_count.to_le_bytes());
header.extend_from_slice(&self.block_count.to_le_bytes());
header.extend_from_slice(&index_offset.to_le_bytes());
file.write_all(&header)?;
file.flush()?;
Ok(std::fs::metadata(&self.path)?.len())
}
}
pub fn write(path: &Path, records: &mut [Record], block_size: usize, level: i32) -> Result<u64> {
records.sort_unstable_by(|a, b| path_cmp(&a.path, &b.path));
let mut w = FcmWriter::create(path, block_size, level)?;
for r in records.iter() {
w.push(r.clone())?;
}
w.finish()
}
pub struct Fcm {
path: PathBuf,
block_size: usize,
record_count: u64,
block_count: u32,
index: Vec<(u64, u32, String)>,
}
impl Fcm {
pub fn open(path: &Path) -> Result<Self> {
let mut f = File::open(path).with_context(|| format!("opening {}", path.display()))?;
let mut header = [0u8; HEADER_LEN as usize];
f.read_exact(&mut header)
.with_context(|| format!("reading FCM header of {}", path.display()))?;
if &header[..8] != MAGIC {
bail!("not an FCM file: {}", path.display());
}
let block_size = u32::from_le_bytes(header[8..12].try_into().unwrap()) as usize;
let record_count = u64::from_le_bytes(header[12..20].try_into().unwrap());
let block_count = u32::from_le_bytes(header[20..24].try_into().unwrap());
let index_offset = u64::from_le_bytes(header[24..32].try_into().unwrap());
f.seek(SeekFrom::Start(index_offset))?;
let mut r = BufReader::new(f);
let mut index = Vec::with_capacity(block_count as usize);
for _ in 0..block_count {
let boff = read_u64(&mut r)?;
let clen = read_u32(&mut r)?;
let flen = read_u32(&mut r)? as usize;
let mut fb = vec![0u8; flen];
r.read_exact(&mut fb)?;
let first = String::from_utf8(fb).context("non-utf8 first_path in index")?;
index.push((boff, clen, first));
}
Ok(Self {
path: path.to_path_buf(),
block_size,
record_count,
block_count,
index,
})
}
pub fn record_count(&self) -> u64 {
self.record_count
}
pub fn block_size(&self) -> usize {
self.block_size
}
pub fn block_count(&self) -> u32 {
self.block_count
}
pub fn iter(&self) -> Result<FcmReader> {
let mut f = File::open(&self.path)?;
f.seek(SeekFrom::Start(HEADER_LEN))?;
Ok(FcmReader {
r: BufReader::new(f),
remaining_blocks: self.block_count,
block_size: self.block_size,
buf: Vec::new(),
idx: 0,
})
}
pub fn lookup(&self, path: &str) -> Result<Option<Record>> {
if self.index.is_empty() {
return Ok(None);
}
let mut lo = 0usize;
let mut hi = self.index.len();
while lo < hi {
let mid = (lo + hi) / 2;
if path_cmp(self.index[mid].2.as_str(), path) != std::cmp::Ordering::Greater {
lo = mid + 1;
} else {
hi = mid;
}
}
if lo == 0 {
return Ok(None); }
let (boff, clen, _) = &self.index[lo - 1];
let mut f = File::open(&self.path)?;
f.seek(SeekFrom::Start(boff + 4))?; let mut comp = vec![0u8; *clen as usize];
f.read_exact(&mut comp)?;
let body = zstd::decode_all(&comp[..])?;
let mut recs = Vec::with_capacity(self.block_size);
decode_block(&body, &mut recs)?;
Ok(recs.into_iter().find(|r| r.path == path))
}
}
fn read_u32(r: &mut impl Read) -> Result<u32> {
let mut b = [0u8; 4];
r.read_exact(&mut b)?;
Ok(u32::from_le_bytes(b))
}
fn read_u64(r: &mut impl Read) -> Result<u64> {
let mut b = [0u8; 8];
r.read_exact(&mut b)?;
Ok(u64::from_le_bytes(b))
}
pub struct FcmReader {
r: BufReader<File>,
remaining_blocks: u32,
block_size: usize,
buf: Vec<Record>,
idx: usize,
}
impl FcmReader {
fn load_next_block(&mut self) -> Result<bool> {
if self.remaining_blocks == 0 {
return Ok(false);
}
let comp_len = read_u32(&mut self.r)? as usize;
let mut comp = vec![0u8; comp_len];
self.r.read_exact(&mut comp)?;
let body = zstd::decode_all(&comp[..])?;
self.buf.clear();
self.buf.reserve(self.block_size);
decode_block(&body, &mut self.buf)?;
self.idx = 0;
self.remaining_blocks -= 1;
Ok(true)
}
}
impl Iterator for FcmReader {
type Item = Result<Record>;
fn next(&mut self) -> Option<Self::Item> {
if self.idx >= self.buf.len() {
match self.load_next_block() {
Ok(false) => return None,
Ok(true) => {}
Err(e) => {
self.remaining_blocks = 0;
return Some(Err(e));
}
}
}
let r = self.buf[self.idx].clone();
self.idx += 1;
Some(Ok(r))
}
}
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct DiffCounts {
pub new: u64,
pub changed: u64,
pub unchanged: u64,
pub deleted: u64,
}
pub fn merge_diff<M, W>(mut manifest: M, mut walk: W) -> Result<DiffCounts>
where
M: Iterator<Item = Result<(String, i64, i64)>>,
W: Iterator<Item = Result<(String, i64, i64)>>,
{
let mut c = DiffCounts::default();
let mut m = manifest.next().transpose()?;
let mut w = walk.next().transpose()?;
loop {
match (&m, &w) {
(None, None) => break,
(Some(_), None) => {
c.deleted += 1;
m = manifest.next().transpose()?;
}
(None, Some(_)) => {
c.new += 1;
w = walk.next().transpose()?;
}
(Some((mp, msz, mmt)), Some((wp, wsz, wmt))) => match mp.as_str().cmp(wp.as_str()) {
std::cmp::Ordering::Less => {
c.deleted += 1;
m = manifest.next().transpose()?;
}
std::cmp::Ordering::Greater => {
c.new += 1;
w = walk.next().transpose()?;
}
std::cmp::Ordering::Equal => {
if msz != wsz || mmt != wmt {
c.changed += 1;
} else {
c.unchanged += 1;
}
m = manifest.next().transpose()?;
w = walk.next().transpose()?;
}
},
}
}
Ok(c)
}
#[cfg(test)]
mod tests {
use super::*;
fn rec(p: &str, size: i64, mtime: i64, crc: Option<u32>) -> Record {
Record {
path: p.into(),
size,
mtime,
crc32c: crc,
}
}
#[test]
fn write_read_roundtrip_sorted() {
let dir = tempfile::tempdir().unwrap();
let file = dir.path().join("m.fcm");
let mut recs = vec![
rec("photos/2024/b.jpg", 20, 200, Some(2)),
rec("photos/2024/a.jpg", 10, 100, None),
rec("docs/readme.txt", 5, 50, Some(9)),
rec("photos/2023/z.png", 30, 300, Some(7)),
];
write(&file, &mut recs, 2, 3).unwrap();
let fcm = Fcm::open(&file).unwrap();
assert_eq!(fcm.record_count(), 4);
let got: Vec<Record> = fcm.iter().unwrap().map(|r| r.unwrap()).collect();
let mut expect = recs.clone();
expect.sort_by(|a, b| path_cmp(&a.path, &b.path));
assert_eq!(got, expect);
}
#[test]
fn empty_fcm_roundtrips() {
let dir = tempfile::tempdir().unwrap();
let file = dir.path().join("empty.fcm");
write(&file, &mut [], 16, 3).unwrap();
let fcm = Fcm::open(&file).unwrap();
assert_eq!(fcm.record_count(), 0);
assert_eq!(fcm.iter().unwrap().count(), 0);
assert_eq!(fcm.lookup("anything").unwrap(), None);
}
#[test]
fn point_lookup_via_index() {
let dir = tempfile::tempdir().unwrap();
let file = dir.path().join("m.fcm");
let mut recs = vec![
rec("a/1", 1, 1, None),
rec("a/2", 2, 2, Some(2)),
rec("b/1", 3, 3, None),
rec("c/9", 9, 9, Some(4)),
rec("c/z", 26, 26, None),
];
write(&file, &mut recs, 2, 3).unwrap();
let fcm = Fcm::open(&file).unwrap();
assert_eq!(fcm.lookup("b/1").unwrap(), Some(rec("b/1", 3, 3, None)));
assert_eq!(fcm.lookup("c/z").unwrap(), Some(rec("c/z", 26, 26, None)));
assert_eq!(fcm.lookup("a/1").unwrap(), Some(rec("a/1", 1, 1, None)));
assert_eq!(fcm.lookup("missing").unwrap(), None);
assert_eq!(fcm.lookup("a/0").unwrap(), None); }
#[test]
fn front_coding_handles_long_shared_prefixes() {
let dir = tempfile::tempdir().unwrap();
let file = dir.path().join("m.fcm");
let base = "very/deep/nested/directory/structure/that/repeats/file_";
let mut recs: Vec<Record> = (0..100)
.map(|i| rec(&format!("{base}{i:03}.dat"), i, i * 10, Some(i as u32)))
.collect();
write(&file, &mut recs, 16, 3).unwrap();
let fcm = Fcm::open(&file).unwrap();
let got: Vec<Record> = fcm.iter().unwrap().map(|r| r.unwrap()).collect();
recs.sort_by(|a, b| path_cmp(&a.path, &b.path));
assert_eq!(got, recs);
}
#[test]
fn path_cmp_orders_separator_first() {
use std::cmp::Ordering;
assert_eq!(path_cmp("a/x", "a.txt"), Ordering::Less);
assert_eq!(path_cmp("a", "a/x"), Ordering::Less);
assert_eq!(path_cmp("a/b", "a/b"), Ordering::Equal);
assert_eq!(path_cmp("ab", "a/x"), Ordering::Greater); }
#[test]
fn merge_diff_classifies_all_cases() {
let manifest = vec![
Ok(("a".to_string(), 1, 1)),
Ok(("b".to_string(), 2, 2)),
Ok(("c".to_string(), 3, 3)),
Ok(("d".to_string(), 4, 4)),
];
let walk = vec![
Ok(("b".to_string(), 2, 999)), Ok(("c".to_string(), 3, 3)), Ok(("e".to_string(), 5, 5)), ];
let counts = merge_diff(manifest.into_iter(), walk.into_iter()).unwrap();
assert_eq!(
counts,
DiffCounts {
new: 1,
changed: 1,
unchanged: 1,
deleted: 2
}
);
}
#[test]
fn merge_diff_via_fcm_reader() {
let dir = tempfile::tempdir().unwrap();
let file = dir.path().join("m.fcm");
let mut recs = vec![
rec("x/a", 1, 1, None),
rec("x/b", 2, 2, None),
rec("x/c", 3, 3, None),
];
write(&file, &mut recs, 2, 3).unwrap();
let fcm = Fcm::open(&file).unwrap();
let manifest = fcm
.iter()
.unwrap()
.map(|r| r.map(|x| (x.path, x.size, x.mtime)));
let walk = vec![
Ok(("x/a".to_string(), 1, 1)), Ok(("x/b".to_string(), 99, 2)), Ok(("x/d".to_string(), 4, 4)), ];
let counts = merge_diff(manifest, walk.into_iter()).unwrap();
assert_eq!(
counts,
DiffCounts {
new: 1,
changed: 1,
unchanged: 1,
deleted: 1
}
);
}
}