← snapshot

//! Tree diffing: the blast-radius primitive.
//!
//! The gate asks one question — "which paths did this change touch?" — and
//! this module answers it. A path is reported if it was added, removed, or
//! points at different content on the two sides. Recursion prunes on equal
//! subtree ids, so an untouched directory costs one comparison regardless of
//! size; that is the content-addressing dividend.

use std::collections::BTreeSet;

use jac_core::{CoreError, RepoPath, TreeId};

use crate::store::{ObjectError, ObjectStore};
use crate::tree::{Tree, TreeNode};

/// Failures while diffing.
#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum DiffError {
    /// A referenced object could not be read.
    #[error("object store error: {0}")]
    Store(#[from] ObjectError),
    /// A tree entry produced an invalid path (should be unreachable given
    /// segment validation, kept as an error rather than a panic).
    #[error("path construction failed: {0}")]
    Path(#[from] CoreError),
}

/// Paths that differ between two trees.
///
/// # Errors
///
/// Returns [`DiffError::Store`] if a referenced subtree cannot be read.
pub fn diff_trees(
    store: &dyn ObjectStore,
    a: TreeId,
    b: TreeId,
) -> Result<BTreeSet<RepoPath>, DiffError> {
    let mut changed = BTreeSet::new();
    if a == b {
        return Ok(changed);
    }
    let tree_a = store.tree(a)?;
    let tree_b = store.tree(b)?;
    diff_into(store, tree_a, tree_b, None, &mut changed)?;
    Ok(changed)
}

fn child_path(parent: Option<&RepoPath>, name: &str) -> Result<RepoPath, DiffError> {
    match parent {
        Some(p) => Ok(p.join(name)?),
        None => Ok(RepoPath::parse(name)?),
    }
}

/// Records every path under `node` as changed (used for wholly added or
/// removed subtrees).
fn record_all(
    store: &dyn ObjectStore,
    node: TreeNode,
    at: &RepoPath,
    out: &mut BTreeSet<RepoPath>,
) -> Result<(), DiffError> {
    match node {
        TreeNode::Blob(_) => {
            out.insert(at.clone());
        }
        TreeNode::Tree(id) => {
            let tree = store.tree(id)?;
            for entry in tree.entries() {
                let path = at.join(entry.name.as_str())?;
                record_all(store, entry.node, &path, out)?;
            }
        }
    }
    Ok(())
}

fn diff_into(
    store: &dyn ObjectStore,
    a: &Tree,
    b: &Tree,
    prefix: Option<&RepoPath>,
    out: &mut BTreeSet<RepoPath>,
) -> Result<(), DiffError> {
    // Both entry lists are sorted; walk them like a merge.
    let mut ia = a.entries().iter().peekable();
    let mut ib = b.entries().iter().peekable();

    loop {
        match (ia.peek(), ib.peek()) {
            (None, None) => return Ok(()),
            (Some(ea), None) => {
                let path = child_path(prefix, ea.name.as_str())?;
                record_all(store, ea.node, &path, out)?;
                ia.next();
            }
            (None, Some(eb)) => {
                let path = child_path(prefix, eb.name.as_str())?;
                record_all(store, eb.node, &path, out)?;
                ib.next();
            }
            (Some(ea), Some(eb)) => match ea.name.cmp(&eb.name) {
                core::cmp::Ordering::Less => {
                    let path = child_path(prefix, ea.name.as_str())?;
                    record_all(store, ea.node, &path, out)?;
                    ia.next();
                }
                core::cmp::Ordering::Greater => {
                    let path = child_path(prefix, eb.name.as_str())?;
                    record_all(store, eb.node, &path, out)?;
                    ib.next();
                }
                core::cmp::Ordering::Equal => {
                    let path = child_path(prefix, ea.name.as_str())?;
                    match (ea.node, eb.node) {
                        (TreeNode::Blob(x), TreeNode::Blob(y)) => {
                            if x != y {
                                out.insert(path);
                            }
                        }
                        (TreeNode::Tree(x), TreeNode::Tree(y)) => {
                            // The pruning step: equal ids mean equal subtrees.
                            if x != y {
                                let ta = store.tree(x)?;
                                let tb = store.tree(y)?;
                                diff_into(store, ta, tb, Some(&path), out)?;
                            }
                        }
                        (na, nb) => {
                            // Kind changed at this name: both sides count.
                            record_all(store, na, &path, out)?;
                            record_all(store, nb, &path, out)?;
                        }
                    }
                    ia.next();
                    ib.next();
                }
            },
        }
    }
}

#[cfg(test)]
#[expect(
    clippy::unwrap_used,
    reason = "test assertions read better with unwrap"
)]
mod tests {
    use super::*;
    use crate::object::Blob;
    use crate::tree::{Segment, TreeEntry};

    /// Builds a one-level tree of named file contents.
    fn flat_tree(store: &mut crate::MemoryObjectStore, files: &[(&str, &[u8])]) -> TreeId {
        let entries = files
            .iter()
            .map(|(name, content)| TreeEntry {
                name: Segment::parse(name).unwrap(),
                node: TreeNode::Blob(store.put_blob(Blob::new(content.to_vec()))),
            })
            .collect();
        store.put_tree(Tree::new(entries).unwrap())
    }

    fn dir(store: &mut crate::MemoryObjectStore, name: &str, inner: TreeId) -> TreeId {
        store.put_tree(
            Tree::new(vec![TreeEntry {
                name: Segment::parse(name).unwrap(),
                node: TreeNode::Tree(inner),
            }])
            .unwrap(),
        )
    }

    #[test]
    fn identical_trees_diff_empty() {
        let mut store = crate::MemoryObjectStore::new();
        let t = flat_tree(&mut store, &[("a.rs", b"x")]);
        assert!(diff_trees(&store, t, t).unwrap().is_empty());
    }

    #[test]
    fn changed_added_and_removed_paths_are_reported() {
        let mut store = crate::MemoryObjectStore::new();
        let before = flat_tree(&mut store, &[("keep.rs", b"same"), ("edit.rs", b"one")]);
        let after = flat_tree(
            &mut store,
            &[("keep.rs", b"same"), ("edit.rs", b"two"), ("new.rs", b"n")],
        );
        let changed = diff_trees(&store, before, after).unwrap();
        let paths: Vec<&str> = changed.iter().map(RepoPath::as_str).collect();
        assert_eq!(paths, vec!["edit.rs", "new.rs"]);
    }

    #[test]
    fn nested_changes_carry_full_paths() {
        let mut store = crate::MemoryObjectStore::new();
        let inner_before = flat_tree(&mut store, &[("backoff.rs", b"v1")]);
        let inner_after = flat_tree(&mut store, &[("backoff.rs", b"v2")]);
        let auth_before = dir(&mut store, "auth", inner_before);
        let auth_after = dir(&mut store, "auth", inner_after);
        let before = dir(&mut store, "src", auth_before);
        let after = dir(&mut store, "src", auth_after);

        let changed = diff_trees(&store, before, after).unwrap();
        let paths: Vec<&str> = changed.iter().map(RepoPath::as_str).collect();
        assert_eq!(paths, vec!["src/auth/backoff.rs"]);
    }
}