incpush 0.1.2

Incrementally back up a big local folder to object storage (GCS/S3/Azure), uploading only changed files and preserving previous versions
Documentation
//! Change detection: walk the source tree and decide, per file, whether it
//! needs uploading — comparing against the last-known manifest state. No
//! destination reads are ever performed here.

use anyhow::{Context, Result};
use ignore::WalkBuilder;
use ignore::overrides::OverrideBuilder;
use std::io::Read;
use std::path::{Path, PathBuf};
use std::time::UNIX_EPOCH;

/// A file's last-known state, as recorded in the manifest.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FileRecord {
    pub size: i64,
    /// Modification time in nanoseconds since the Unix epoch.
    pub mtime: i64,
    /// crc32c of the file contents. `None` in `mtime` diff mode.
    pub crc32c: Option<u32>,
}

/// Reserved subdirectory (both local and in the bucket) for incpush's own
/// state. Always excluded from the walk.
pub const RESERVED_DIR: &str = ".incpush";

/// How aggressively to detect changes. See the crate README for the cost trade-offs.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DiffMode {
    /// Compare size + mtime only. No file contents are read. Default.
    Mtime,
    /// Cheap size/mtime filter first; hash only the candidates to suppress
    /// re-uploads of touched-but-identical files.
    Hash,
    /// Hash every file. Integrity-audit use only; expensive.
    FullHash,
}

/// A file discovered on disk during the walk.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Entry {
    /// Relative, `/`-normalized path from the source root.
    pub rel_path: String,
    /// Absolute path on disk.
    pub abs_path: PathBuf,
    pub size: i64,
    /// Modification time in nanoseconds since the Unix epoch.
    pub mtime: i64,
}

/// The outcome of diffing one file against its manifest record.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Decision {
    /// Unchanged; no upload and no manifest write.
    Skip,
    /// Content identical but metadata (mtime) moved. Refresh the manifest row
    /// (so future cheap-filter runs match) but do not upload.
    Touch { crc32c: Option<u32> },
    /// New or changed; upload it. `crc32c` is stored in the manifest afterwards.
    Upload { crc32c: Option<u32> },
}

/// Decide what to do with one file. `hash` is invoked lazily and only when the
/// chosen mode actually needs the file's contents, so callers pay for I/O only
/// where a hash is required.
pub fn decide<F>(
    mode: DiffMode,
    prior: Option<&FileRecord>,
    size: i64,
    mtime: i64,
    hash: F,
) -> Result<Decision>
where
    F: FnOnce() -> Result<u32>,
{
    match mode {
        DiffMode::Mtime => Ok(match prior {
            Some(p) if p.size == size && p.mtime == mtime => Decision::Skip,
            _ => Decision::Upload { crc32c: None },
        }),

        DiffMode::Hash => {
            // Cheap filter: unchanged metadata means unchanged content — no hash.
            if let Some(p) = prior
                && p.size == size
                && p.mtime == mtime
            {
                return Ok(Decision::Skip);
            }
            // Candidate: hash to see whether the content actually differs.
            let c = hash()?;
            if let Some(p) = prior
                && p.size == size
                && p.crc32c == Some(c)
            {
                // Touched but byte-identical: refresh mtime, skip upload.
                return Ok(Decision::Touch { crc32c: Some(c) });
            }
            Ok(Decision::Upload { crc32c: Some(c) })
        }

        DiffMode::FullHash => {
            let c = hash()?;
            match prior {
                Some(p) if p.size == size && p.crc32c == Some(c) => {
                    if p.mtime == mtime {
                        Ok(Decision::Skip)
                    } else {
                        Ok(Decision::Touch { crc32c: Some(c) })
                    }
                }
                _ => Ok(Decision::Upload { crc32c: Some(c) }),
            }
        }
    }
}

/// Stream a file through crc32c without loading it fully into memory.
pub fn hash_file(path: &Path) -> Result<u32> {
    let mut f =
        std::fs::File::open(path).with_context(|| format!("opening {} to hash", path.display()))?;
    let mut buf = vec![0u8; 1 << 20]; // 1 MiB
    let mut crc = 0u32;
    loop {
        let n = f.read(&mut buf)?;
        if n == 0 {
            break;
        }
        crc = crc32c::crc32c_append(crc, &buf[..n]);
    }
    Ok(crc)
}

/// Normalize a relative path to forward slashes for stable, cross-platform keys.
fn normalize(rel: &Path) -> String {
    let s = rel.to_string_lossy();
    if std::path::MAIN_SEPARATOR == '/' {
        s.into_owned()
    } else {
        s.replace(std::path::MAIN_SEPARATOR, "/")
    }
}

/// Walk `root`, yielding a file [`Entry`] for every regular file, honoring
/// `.backupignore` files and the extra `excludes` globs, and always skipping the
/// reserved [`RESERVED_DIR`]. Errors reading individual entries are surfaced as
/// `Err` items rather than aborting the whole walk.
///
/// This is a **sorted** depth-first walk: `ignore`'s sequential walker sorts each
/// directory's entries by raw file-name bytes, which — because [`path_cmp`] treats
/// the `/` separator as sorting before every other byte — emits paths in exactly
/// the manifest's canonical order. So the diff needs no separate global sort of
/// the walk. Memory is bounded by directory size + tree depth.
pub fn walk_source(
    root: &Path,
    excludes: &[String],
) -> Result<impl Iterator<Item = Result<Entry>>> {
    let mut ov = OverrideBuilder::new(root);
    // Overrides use gitignore syntax; a leading `!` would *include*, so plain
    // globs here are treated as ignore patterns via the `!`-inverted whitelist.
    for pat in excludes {
        // `!pat` means "exclude pat" in override terms.
        ov.add(&format!("!{pat}"))
            .with_context(|| format!("invalid --exclude glob: {pat}"))?;
    }
    let overrides = ov.build().context("building exclude overrides")?;

    let walker = WalkBuilder::new(root)
        .hidden(false) // don't skip dotfiles by default
        .git_ignore(false)
        .git_global(false)
        .git_exclude(false)
        .ignore(false)
        .parents(false)
        .add_custom_ignore_filename(".backupignore")
        .overrides(overrides)
        .filter_entry(|e| {
            // Never descend into or record the reserved state dir.
            e.file_name() != std::ffi::OsStr::new(RESERVED_DIR)
        })
        // Sort siblings by raw name bytes -> sorted-DFS yields canonical order.
        .sort_by_file_name(|a, b| a.as_encoded_bytes().cmp(b.as_encoded_bytes()))
        .build();

    let root = root.to_path_buf();
    Ok(walker.filter_map(move |res| {
        let dent = match res {
            Ok(d) => d,
            Err(e) => return Some(Err(anyhow::anyhow!("walk error: {e}"))),
        };
        if !dent.file_type().is_some_and(|t| t.is_file()) {
            return None;
        }
        Some(entry_from(&root, &dent))
    }))
}

fn entry_from(root: &Path, dent: &ignore::DirEntry) -> Result<Entry> {
    let abs = dent.path();
    let meta = dent
        .metadata()
        .with_context(|| format!("stat {}", abs.display()))?;
    let mtime = meta
        .modified()
        .ok()
        .and_then(|m| m.duration_since(UNIX_EPOCH).ok())
        .map(|d| d.as_nanos() as i64)
        .unwrap_or(0);
    let rel = abs.strip_prefix(root).unwrap_or(abs);
    Ok(Entry {
        rel_path: normalize(rel),
        abs_path: abs.to_path_buf(),
        size: meta.len() as i64,
        mtime,
    })
}

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

    fn rec(size: i64, mtime: i64, crc: Option<u32>) -> FileRecord {
        FileRecord {
            size,
            mtime,
            crc32c: crc,
        }
    }

    // A hasher that records whether it was invoked, so we can assert that cheap
    // modes never read file contents.
    fn tracked(value: u32) -> (impl Fn() -> Result<u32>, std::rc::Rc<Cell<bool>>) {
        let called = std::rc::Rc::new(Cell::new(false));
        let c = called.clone();
        (
            move || {
                c.set(true);
                Ok(value)
            },
            called,
        )
    }

    #[test]
    fn mtime_new_file_uploads_without_hashing() {
        let (h, called) = tracked(1);
        let d = decide(DiffMode::Mtime, None, 10, 100, || h()).unwrap();
        assert_eq!(d, Decision::Upload { crc32c: None });
        assert!(!called.get(), "mtime mode must never hash");
    }

    #[test]
    fn mtime_unchanged_skips() {
        let prior = rec(10, 100, None);
        let d = decide(DiffMode::Mtime, Some(&prior), 10, 100, || unreachable!()).unwrap();
        assert_eq!(d, Decision::Skip);
    }

    #[test]
    fn mtime_size_or_mtime_change_uploads() {
        let prior = rec(10, 100, None);
        assert_eq!(
            decide(DiffMode::Mtime, Some(&prior), 11, 100, || unreachable!()).unwrap(),
            Decision::Upload { crc32c: None }
        );
        assert_eq!(
            decide(DiffMode::Mtime, Some(&prior), 10, 101, || unreachable!()).unwrap(),
            Decision::Upload { crc32c: None }
        );
    }

    #[test]
    fn hash_skips_on_cheap_filter_without_hashing() {
        let prior = rec(10, 100, Some(42));
        let (h, called) = tracked(42);
        let d = decide(DiffMode::Hash, Some(&prior), 10, 100, || h()).unwrap();
        assert_eq!(d, Decision::Skip);
        assert!(
            !called.get(),
            "matching size+mtime must short-circuit the hash"
        );
    }

    #[test]
    fn hash_touched_identical_content_is_touch_not_upload() {
        // mtime moved but content (and size) identical -> Touch.
        let prior = rec(10, 100, Some(42));
        let (h, called) = tracked(42);
        let d = decide(DiffMode::Hash, Some(&prior), 10, 200, || h()).unwrap();
        assert_eq!(d, Decision::Touch { crc32c: Some(42) });
        assert!(called.get(), "candidate should have been hashed");
    }

    #[test]
    fn hash_real_content_change_uploads() {
        let prior = rec(10, 100, Some(42));
        let d = decide(DiffMode::Hash, Some(&prior), 10, 200, || Ok(99)).unwrap();
        assert_eq!(d, Decision::Upload { crc32c: Some(99) });
    }

    #[test]
    fn fullhash_hashes_every_file() {
        let (h, called) = tracked(7);
        let d = decide(DiffMode::FullHash, None, 10, 100, || h()).unwrap();
        assert_eq!(d, Decision::Upload { crc32c: Some(7) });
        assert!(called.get());
    }

    #[test]
    fn fullhash_identical_content_skips_or_touches() {
        let prior = rec(10, 100, Some(7));
        assert_eq!(
            decide(DiffMode::FullHash, Some(&prior), 10, 100, || Ok(7)).unwrap(),
            Decision::Skip
        );
        assert_eq!(
            decide(DiffMode::FullHash, Some(&prior), 10, 555, || Ok(7)).unwrap(),
            Decision::Touch { crc32c: Some(7) }
        );
    }

    #[test]
    fn fullhash_uploads_when_prior_has_no_crc() {
        // Prior recorded in mtime mode (crc None): cannot compare, so upload.
        let prior = rec(10, 100, None);
        let d = decide(DiffMode::FullHash, Some(&prior), 10, 100, || Ok(7)).unwrap();
        assert_eq!(d, Decision::Upload { crc32c: Some(7) });
    }

    #[test]
    fn hash_file_matches_known_crc32c() {
        use std::io::Write;
        let dir = tempfile::tempdir().unwrap();
        let p = dir.path().join("data.bin");
        std::fs::File::create(&p)
            .unwrap()
            .write_all(b"123456789")
            .unwrap();
        // Standard crc32c check value for "123456789".
        assert_eq!(hash_file(&p).unwrap(), 0xe306_9283);
    }

    #[test]
    fn walk_finds_files_excludes_reserved_and_globs() {
        let dir = tempfile::tempdir().unwrap();
        let root = dir.path();
        std::fs::create_dir_all(root.join("a/b")).unwrap();
        std::fs::create_dir_all(root.join(RESERVED_DIR)).unwrap();
        std::fs::write(root.join("a/b/keep.txt"), b"hi").unwrap();
        std::fs::write(root.join("a/skip.tmp"), b"x").unwrap();
        std::fs::write(root.join(RESERVED_DIR).join("manifest.db"), b"db").unwrap();

        let mut found: Vec<String> = walk_source(root, &["*.tmp".into()])
            .unwrap()
            .map(|r| r.unwrap().rel_path)
            .collect();
        found.sort();
        assert_eq!(found, vec!["a/b/keep.txt".to_string()]);
    }

    #[test]
    fn walk_emits_canonical_sorted_order() {
        use crate::fcm::path_cmp;
        let dir = tempfile::tempdir().unwrap();
        let root = dir.path();
        // Names chosen so raw-string order != separator-first order:
        //   "a.txt" vs "a/x": '.' < '/' as raw bytes, but canonical puts "a/x" first.
        std::fs::create_dir_all(root.join("a")).unwrap();
        std::fs::create_dir_all(root.join("ab")).unwrap();
        std::fs::write(root.join("a.txt"), b"1").unwrap();
        std::fs::write(root.join("a/x"), b"2").unwrap();
        std::fs::write(root.join("a/y"), b"3").unwrap();
        std::fs::write(root.join("ab/z"), b"4").unwrap();
        std::fs::write(root.join("a-b"), b"5").unwrap();

        let got: Vec<String> = walk_source(root, &[])
            .unwrap()
            .map(|r| r.unwrap().rel_path)
            .collect();

        // The walk must already be in canonical order (no re-sorting needed).
        let mut expect = got.clone();
        expect.sort_by(|a, b| path_cmp(a, b));
        assert_eq!(got, expect, "walk output must be in canonical path order");
        // Sanity: separator-first really is in effect.
        let ax = got.iter().position(|p| p == "a/x").unwrap();
        let atxt = got.iter().position(|p| p == "a.txt").unwrap();
        assert!(ax < atxt, "'a/x' must precede 'a.txt' in canonical order");
    }
}