incpush 0.1.3

Incrementally back up a big local folder to object storage (GCS/S3/Azure), uploading only changed files and preserving previous versions
Documentation
//! Log-structured manifest: a compact sorted `base.fcm` plus a series of tiny
//! per-run `seg-NNNNN.fcm` segments holding only that run's changes (upserts and
//! deletion tombstones).
//!
//! - **Reads** merge base + segments newest-wins ([`Lsm::current`]) into one sorted
//!   stream — so a single changed file never forces reading or rewriting the whole
//!   manifest.
//! - **Writes** append one small segment per run ([`Lsm::append_segment`]).
//! - **Compaction** ([`Lsm::compact`]) folds everything back into a fresh `base`
//!   only occasionally, amortizing the whole-file rewrite.
//!
//! All ordering uses [`fcm::path_cmp`]; segments are numbered in apply order, and
//! a higher-numbered segment wins ties.

use anyhow::{Context, Result};
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::path::PathBuf;

use crate::fcm::{self, DEFAULT_BLOCK_SIZE, Fcm, FcmReader, Record, path_cmp};

pub struct Lsm {
    dir: PathBuf,
}

impl Lsm {
    pub fn new(dir: impl Into<PathBuf>) -> Self {
        Self { dir: dir.into() }
    }

    fn base_path(&self) -> PathBuf {
        self.dir.join("base.fcm")
    }

    fn seg_path(&self, n: u64) -> PathBuf {
        self.dir.join(format!("seg-{n:05}.fcm"))
    }

    pub fn has_base(&self) -> bool {
        self.base_path().exists()
    }

    /// Segment numbers present on disk, ascending.
    pub fn segments(&self) -> Result<Vec<u64>> {
        let mut segs = Vec::new();
        if !self.dir.exists() {
            return Ok(segs);
        }
        for entry in std::fs::read_dir(&self.dir)
            .with_context(|| format!("reading manifest dir {}", self.dir.display()))?
        {
            let name = entry?.file_name();
            let name = name.to_string_lossy();
            if let Some(mid) = name
                .strip_prefix("seg-")
                .and_then(|s| s.strip_suffix(".fcm"))
                && let Ok(n) = mid.parse::<u64>()
            {
                segs.push(n);
            }
        }
        segs.sort_unstable();
        Ok(segs)
    }

    pub fn segment_count(&self) -> Result<usize> {
        Ok(self.segments()?.len())
    }

    /// Whether a manifest exists at all (base or any segment).
    pub fn is_empty(&self) -> Result<bool> {
        Ok(!self.has_base() && self.segments()?.is_empty())
    }

    /// Merge base + segments into one sorted, tombstone-resolved record stream.
    pub fn current(&self) -> Result<LsmMerge> {
        let mut readers: Vec<FcmReader> = Vec::new();
        // Priority = index; base is oldest (0), later segments newer.
        if self.has_base() {
            readers.push(Fcm::open(&self.base_path())?.iter()?);
        }
        for n in self.segments()? {
            readers.push(Fcm::open(&self.seg_path(n))?.iter()?);
        }
        LsmMerge::new(readers)
    }

    /// Append a new segment holding this run's records (upserts + tombstones).
    /// Records may be in any order; they are sorted before writing.
    pub fn append_segment(&self, records: &mut [Record], zstd_level: i32) -> Result<()> {
        std::fs::create_dir_all(&self.dir)?;
        let next = self.segments()?.last().copied().unwrap_or(0) + 1;
        fcm::write(
            &self.seg_path(next),
            records,
            DEFAULT_BLOCK_SIZE,
            zstd_level,
        )?;
        Ok(())
    }

    /// Fold base + all segments into a fresh `base.fcm` (dropping tombstones) and
    /// delete the segments. This is the only operation that rewrites the whole
    /// manifest, and it runs only periodically. Guarantees a `base.fcm` exists
    /// afterwards (an empty one if the manifest is empty), so callers can always
    /// treat the base as the full current state.
    pub fn compact(&self, zstd_level: i32) -> Result<()> {
        let segs = self.segments()?;
        if segs.is_empty() && self.has_base() {
            return Ok(()); // already a single base file
        }
        std::fs::create_dir_all(&self.dir)?;
        let tmp = self.dir.join("base.fcm.tmp");
        {
            let mut writer = fcm::FcmWriter::create(&tmp, DEFAULT_BLOCK_SIZE, zstd_level)?;
            for rec in self.current()? {
                writer.push(rec?)?;
            }
            writer.finish()?;
        }
        std::fs::rename(&tmp, self.base_path())?;
        for n in segs {
            std::fs::remove_file(self.seg_path(n))?;
        }
        Ok(())
    }

    /// Install a downloaded snapshot FCM as the base (replacing any local state).
    pub fn install_base(&self, fcm_bytes: &[u8]) -> Result<()> {
        std::fs::create_dir_all(&self.dir)?;
        for n in self.segments()? {
            std::fs::remove_file(self.seg_path(n))?;
        }
        std::fs::write(self.base_path(), fcm_bytes)
            .with_context(|| format!("writing base {}", self.base_path().display()))?;
        Ok(())
    }

    /// Path to the compacted base file (call [`Lsm::compact`] first to make it
    /// reflect the full current state) — used to upload a remote snapshot.
    pub fn base_file(&self) -> PathBuf {
        self.base_path()
    }
}

/// Heap entry for the newest-wins k-way merge.
struct HeapItem {
    rec: Record,
    priority: usize,
}
impl PartialEq for HeapItem {
    fn eq(&self, other: &Self) -> bool {
        self.priority == other.priority && self.rec.path == other.rec.path
    }
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
    fn cmp(&self, other: &Self) -> Ordering {
        // BinaryHeap is a max-heap; make "greater" mean "popped first": smallest
        // path first, and among equal paths the highest priority (newest) first.
        match path_cmp(&self.rec.path, &other.rec.path) {
            Ordering::Less => Ordering::Greater,
            Ordering::Greater => Ordering::Less,
            Ordering::Equal => self.priority.cmp(&other.priority),
        }
    }
}
impl PartialOrd for HeapItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Newest-wins k-way merge over base + segments, skipping tombstones.
pub struct LsmMerge {
    readers: Vec<FcmReader>,
    heap: BinaryHeap<HeapItem>,
}

impl LsmMerge {
    fn new(mut readers: Vec<FcmReader>) -> Result<Self> {
        let mut heap = BinaryHeap::with_capacity(readers.len());
        for (priority, r) in readers.iter_mut().enumerate() {
            if let Some(rec) = r.next() {
                heap.push(HeapItem {
                    rec: rec?,
                    priority,
                });
            }
        }
        Ok(Self { readers, heap })
    }

    fn refill(&mut self, priority: usize) -> Result<()> {
        if let Some(rec) = self.readers[priority].next() {
            self.heap.push(HeapItem {
                rec: rec?,
                priority,
            });
        }
        Ok(())
    }
}

impl Iterator for LsmMerge {
    type Item = Result<Record>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let top = self.heap.pop()?;
            if let Err(e) = self.refill(top.priority) {
                return Some(Err(e));
            }
            // Discard any older duplicates of the same path.
            while let Some(peek) = self.heap.peek() {
                if path_cmp(&peek.rec.path, &top.rec.path) == Ordering::Equal {
                    let dup = self.heap.pop().unwrap();
                    if let Err(e) = self.refill(dup.priority) {
                        return Some(Err(e));
                    }
                } else {
                    break;
                }
            }
            // A tombstone hides older entries but is not itself emitted.
            if top.rec.is_tombstone() {
                continue;
            }
            return Some(Ok(top.rec));
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn rec(p: &str, size: i64) -> Record {
        Record {
            path: p.into(),
            size,
            mtime: size,
            crc32c: None,
        }
    }

    fn collect(lsm: &Lsm) -> Vec<(String, i64)> {
        lsm.current()
            .unwrap()
            .map(|r| {
                let r = r.unwrap();
                (r.path, r.size)
            })
            .collect()
    }

    #[test]
    fn base_only() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.append_segment(&mut [rec("a", 1), rec("b", 2)], 3)
            .unwrap();
        // one segment acts as the only source
        assert_eq!(collect(&lsm), vec![("a".into(), 1), ("b".into(), 2)]);
    }

    #[test]
    fn newer_segment_overrides_and_tombstones_delete() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.append_segment(&mut [rec("a", 1), rec("b", 2), rec("c", 3)], 3)
            .unwrap();
        // seg 2: change b, delete c, add d
        lsm.append_segment(
            &mut [rec("b", 20), Record::tombstone("c".into()), rec("d", 4)],
            3,
        )
        .unwrap();

        assert_eq!(
            collect(&lsm),
            vec![("a".into(), 1), ("b".into(), 20), ("d".into(), 4)]
        );
    }

    #[test]
    fn compaction_folds_segments_and_drops_tombstones() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.append_segment(&mut [rec("a", 1), rec("b", 2), rec("c", 3)], 3)
            .unwrap();
        lsm.append_segment(&mut [rec("b", 20), Record::tombstone("c".into())], 3)
            .unwrap();
        assert_eq!(lsm.segment_count().unwrap(), 2);

        lsm.compact(3).unwrap();
        assert_eq!(lsm.segment_count().unwrap(), 0);
        assert!(lsm.has_base());
        // Same logical contents, now in one base file.
        assert_eq!(collect(&lsm), vec![("a".into(), 1), ("b".into(), 20)]);

        // Further segments still layer on top of the compacted base.
        lsm.append_segment(&mut [rec("a", 100)], 3).unwrap();
        assert_eq!(collect(&lsm), vec![("a".into(), 100), ("b".into(), 20)]);
    }

    #[test]
    fn empty_manifest_current_is_empty() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        assert!(lsm.is_empty().unwrap());
        assert_eq!(collect(&lsm), Vec::<(String, i64)>::new());
    }

    #[test]
    fn compact_empty_manifest_creates_empty_base() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.compact(3).unwrap();
        assert!(lsm.has_base(), "compact must leave a base even when empty");
        assert_eq!(collect(&lsm), Vec::<(String, i64)>::new());
        // A base-only, no-segment manifest compacts to a no-op.
        lsm.compact(3).unwrap();
        assert!(lsm.has_base());
    }

    #[test]
    fn tombstone_for_absent_path_is_harmless() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.append_segment(&mut [rec("a", 1)], 3).unwrap();
        // Delete a path that was never present.
        lsm.append_segment(&mut [Record::tombstone("never".into())], 3)
            .unwrap();
        assert_eq!(collect(&lsm), vec![("a".into(), 1)]);
    }

    #[test]
    fn canonical_order_across_segments() {
        let dir = tempfile::tempdir().unwrap();
        let lsm = Lsm::new(dir.path());
        lsm.append_segment(&mut [rec("a.txt", 1), rec("a/y", 2)], 3)
            .unwrap();
        lsm.append_segment(&mut [rec("a/x", 3)], 3).unwrap();
        // Separator-first order: a/x, a/y, a.txt
        let paths: Vec<String> = lsm.current().unwrap().map(|r| r.unwrap().path).collect();
        assert_eq!(paths, vec!["a/x", "a/y", "a.txt"]);
    }
}