differential_engine/

invariants.rs

//! Invariants 1–4 (spec/invariants.md). All of them run before any document is
//! emitted; every one caught a real bug during prototype validation.

use crate::EngineError;
use crate::model::{DiffView, Disposition, Hunk};
use crate::ports::{ObjectReader, ObjectWriter, RecountSource, TreeBuilder, TreeResolver};
use crate::tree::build_tree;

#[derive(Debug, Clone, serde::Serialize)]
pub struct InvariantReport {
    pub files_total: usize,
    /// Text files (non-binary, non-submodule) checked byte-exactly.
    pub applier_total: usize,
    pub applier_ok: usize,
    pub applier_mismatches: Vec<String>,
    /// Binary files verified by oid instead of by reconstruction.
    pub binary_oid_checked: usize,
    pub hunks_total: usize,
    pub accounting_ok: bool,
    pub built_tree: Option<String>,
    pub head_tree: String,
    pub tree_ok: bool,
    pub recount: usize,
    pub recount_ok: bool,
}

impl InvariantReport {
    pub fn all_ok(&self) -> bool {
        self.applier_mismatches.is_empty()
            && self.applier_ok == self.applier_total
            && self.accounting_ok
            && self.tree_ok
            && self.recount_ok
    }

    /// "n/n" for the audit block.
    pub fn applier_exact(&self) -> String {
        format!("{}/{}", self.applier_ok, self.applier_total)
    }
}

impl std::fmt::Display for InvariantReport {
    /// The human form of the report: totals and invariants 1-4, one per line.
    ///
    /// Formatting, not printing — the engine still writes nothing. The
    /// endpoints are deliberately absent: they are not part of the report (nor
    /// of `--json`), so a caller that wants a range header prints its own.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let verdict = |ok: bool| if ok { "PASS" } else { "FAIL" };
        writeln!(
            f,
            "files      {} ({} binary, checked by oid only — tree assertion is tautological for those)",
            self.files_total, self.binary_oid_checked
        )?;
        writeln!(f, "hunks      {}", self.hunks_total)?;
        writeln!(
            f,
            "inv1 applier fidelity   {}  {}",
            self.applier_exact(),
            verdict(self.applier_mismatches.is_empty())
        )?;
        for m in &self.applier_mismatches {
            writeln!(f, "           mismatch: {m}")?;
        }
        writeln!(f, "inv2 hunk accounting    {}", verdict(self.accounting_ok))?;
        writeln!(
            f,
            "inv3 tree assertion     {}  built {} head {}",
            verdict(self.tree_ok),
            self.built_tree.as_deref().unwrap_or("(not built)"),
            self.head_tree
        )?;
        writeln!(
            f,
            "inv4 independent recount {} of {}  {}",
            self.recount,
            self.hunks_total,
            verdict(self.recount_ok)
        )?;
        write!(
            f,
            "note: tree building writes unreferenced loose objects into the odb (gc-able)"
        )
    }
}

/// Run invariants 1–4. Invariant 1 (applier fidelity) is asserted BEFORE the
/// tree is built; if it fails, nothing is built on top of it.
pub fn check_all<G>(
    git: &G,
    base: &str,
    head: &str,
    view: &DiffView,
) -> Result<InvariantReport, EngineError>
where
    G: ObjectReader + ObjectWriter + TreeResolver + TreeBuilder + RecountSource,
{
    // ---- Invariant 1: applier fidelity ------------------------------------
    let mut applier_total = 0usize;
    let mut applier_ok = 0usize;
    let mut mismatches = Vec::new();
    let mut binary_checked = 0usize;

    for f in &view.files {
        match fidelity(f) {
            Fidelity::Skip => continue,
            Fidelity::ByOid(oid) => {
                // The recorded object must exist in the odb.
                git.require_object(oid)?;
                binary_checked += 1;
                continue;
            }
            Fidelity::NoOid => {
                binary_checked += 1;
                continue;
            }
            Fidelity::Reconstruct => {}
        }
        applier_total += 1;
        let hunks: Vec<&Hunk> = f.hunks.iter().map(|&i| &view.hunks[i]).collect();
        let base_content = git.blob(base, &f.path)?;
        let got = crate::apply::apply_hunks(base_content.as_deref(), &hunks);
        let want = if f.disposition == Disposition::Deleted {
            Vec::new()
        } else {
            git.blob(head, &f.path)?.unwrap_or_default()
        };
        if got == want {
            applier_ok += 1;
        } else {
            mismatches.push(format!(
                "{}: reconstructed {}B, expected {}B",
                String::from_utf8_lossy(&f.path),
                got.len(),
                want.len()
            ));
        }
    }

    // ---- Invariant 2: hunk accounting --------------------------------------
    let accounting_ok = check_accounting(view);

    let head_tree = git.tree_of(head)?;

    // ---- Invariant 3: non-tautological tree assertion ----------------------
    // Refuse to build on a broken applier (the prototype's rule).
    let (built_tree, tree_ok) = if may_build_tree(applier_total, applier_ok, &mismatches) {
        let built = build_tree(git, base, view)?;
        let ok = built == head_tree;
        (Some(built), ok)
    } else {
        (None, false)
    };

    // ---- Invariant 4: independent recount -----------------------------------
    // Computed from git's own output over the BUILT tree, by a counter that is
    // deliberately not the parser.
    let (recount, recount_ok) = match &built_tree {
        Some(t) => {
            // Invariant 4's own port, never enumeration's: a change to one
            // cannot move both sides of this comparison.
            let out = git.recount_patch(base, t.as_str())?;
            let n = dumb_hunk_count(&out);
            (n, n == view.hunks.len())
        }
        None => (0, false),
    };

    Ok(InvariantReport {
        files_total: view.files.len(),
        applier_total,
        applier_ok,
        applier_mismatches: mismatches,
        binary_oid_checked: binary_checked,
        hunks_total: view.hunks.len(),
        accounting_ok,
        built_tree,
        head_tree,
        tree_ok,
        recount,
        recount_ok,
    })
}

/// How invariant 1 verifies one file.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Fidelity<'a> {
    /// Submodules: a gitlink has no content to reconstruct.
    Skip,
    /// Binary: no hunks exist, so the recorded oid is all there is to check.
    ByOid(&'a str),
    /// Binary with nothing recorded — counted, but there is nothing to assert.
    NoOid,
    /// Text: rebuild from base + hunks and compare byte for byte.
    Reconstruct,
}

fn fidelity(f: &crate::model::FileChange) -> Fidelity<'_> {
    if f.submodule.is_some() {
        return Fidelity::Skip;
    }
    if f.binary {
        return match f.new_oid.as_deref() {
            Some(oid) => Fidelity::ByOid(oid),
            None => Fidelity::NoOid,
        };
    }
    Fidelity::Reconstruct
}

/// Invariant 2, entire: every hunk belongs to exactly one file, that file
/// agrees, and the per-file lists sum to the canonical count.
///
/// Touches no git — it is a statement about the view's internal consistency,
/// which is why it can be exercised against a hand-built view.
fn check_accounting(view: &DiffView) -> bool {
    let mut seen = vec![false; view.hunks.len()];
    let mut ok = true;
    let mut carried = 0usize;
    for (fi, f) in view.files.iter().enumerate() {
        for &hi in &f.hunks {
            if hi >= seen.len() || seen[hi] || view.hunks[hi].file != fi {
                ok = false;
                continue;
            }
            seen[hi] = true;
            carried += 1;
        }
    }
    ok && carried == view.hunks.len()
}

/// Whether invariant 3 may run: never build a tree on a broken applier, or the
/// tree assertion is being made on top of a failure it cannot see.
fn may_build_tree(applier_total: usize, applier_ok: usize, mismatches: &[String]) -> bool {
    mismatches.is_empty() && applier_ok == applier_total
}

/// The deliberately dumb `@@` counter. Must never share code with `parse.rs` —
/// a shared bug would make invariant 4 circular.
pub fn dumb_hunk_count(patch: &[u8]) -> usize {
    patch
        .split(|&b| b == b'\n')
        .filter(|l| l.starts_with(b"@@ -"))
        .count()
}

#[cfg(test)]
mod tests {
    use super::{Fidelity, check_accounting, dumb_hunk_count, fidelity, may_build_tree};
    use crate::model::{DiffView, Disposition, FileChange, Hunk};

    fn hunk(file: usize) -> Hunk {
        Hunk {
            file,
            old_start: 1,
            old_count: 1,
            new_start: 1,
            new_count: 1,
            removed: vec![],
            added: vec![],
            nonl_old: false,
            nonl_new: false,
        }
    }

    fn file(hunks: Vec<usize>) -> FileChange {
        FileChange {
            path: b"f".to_vec(),
            disposition: Disposition::Modified,
            new_mode: Some("100644".into()),
            old_mode: None,
            binary: false,
            submodule: None,
            old_oid: None,
            new_oid: None,
            hunks,
            rename_similarity: None,
            rename_from: None,
            rename_to: None,
            generated: None,
        }
    }

    /// Invariant 2 was 14 lines inlined in a function that needed a repository,
    /// so none of these cases had ever been asserted directly.
    #[test]
    fn accounting_holds_when_every_hunk_belongs_to_exactly_one_file() {
        let view = DiffView {
            files: vec![file(vec![0, 1]), file(vec![2])],
            hunks: vec![hunk(0), hunk(0), hunk(1)],
        };
        assert!(check_accounting(&view));
    }

    #[test]
    fn accounting_catches_a_hunk_claimed_twice() {
        let view = DiffView {
            files: vec![file(vec![0]), file(vec![0])],
            hunks: vec![hunk(0)],
        };
        assert!(!check_accounting(&view), "one hunk in two files");
    }

    #[test]
    fn accounting_catches_a_hunk_no_file_claims() {
        let view = DiffView {
            files: vec![file(vec![0])],
            hunks: vec![hunk(0), hunk(0)],
        };
        assert!(!check_accounting(&view), "h1 is carried by nothing");
    }

    #[test]
    fn accounting_catches_a_file_claiming_another_files_hunk() {
        // The disagreement that matters: the file lists it, the hunk denies it.
        let view = DiffView {
            files: vec![file(vec![0]), file(vec![1])],
            hunks: vec![hunk(0), hunk(0)],
        };
        assert!(!check_accounting(&view));
    }

    #[test]
    fn accounting_catches_an_out_of_range_index() {
        let view = DiffView {
            files: vec![file(vec![7])],
            hunks: vec![hunk(0)],
        };
        assert!(!check_accounting(&view));
    }

    #[test]
    fn binary_and_submodule_files_are_verified_differently_from_text() {
        let mut f = file(vec![]);
        assert_eq!(fidelity(&f), Fidelity::Reconstruct);

        f.binary = true;
        f.new_oid = Some("abc".into());
        assert_eq!(fidelity(&f), Fidelity::ByOid("abc"));

        f.new_oid = None;
        assert_eq!(fidelity(&f), Fidelity::NoOid);

        f.binary = false;
        f.submodule = Some((None, Some("s".into())));
        assert_eq!(fidelity(&f), Fidelity::Skip);
    }

    /// The prototype's rule: a tree built on a broken applier would assert
    /// nothing, so invariant 3 does not run at all.
    #[test]
    fn a_broken_applier_stops_the_tree_from_being_built() {
        assert!(may_build_tree(3, 3, &[]));
        assert!(!may_build_tree(3, 2, &[]));
        assert!(!may_build_tree(3, 3, &["f: mismatch".to_string()]));
    }

    #[test]
    fn dumb_counter_counts_headers_only() {
        let patch = b"diff --git a/f b/f\n@@ -1,2 +1,2 @@\n-a\n+b\n@@ -9 +9 @@\n-x\n+y\n";
        assert_eq!(dumb_hunk_count(patch), 2);
    }

    #[test]
    fn dumb_counter_ignores_content_lines_that_mention_hunks() {
        // An added line whose content starts with "@@ -" gets a "+" prefix in
        // the patch, so it cannot collide.
        let patch = b"@@ -1,0 +1,1 @@\n+@@ -5,5 +5,5 @@\n";
        assert_eq!(dumb_hunk_count(patch), 1);
    }
}