void_core/diff/

three_way.rs

//! Three-way diff algorithm for merge operations.
//!
//! Computes file-level differences between a base commit and two branches (ours/theirs)
//! to detect conflicts and auto-mergeable changes.

use std::collections::{HashMap, HashSet};

use serde::{Deserialize as SerdeDeserialize, Serialize};

use super::collect::{collect_commit_files, load_commit_and_reader};
use crate::cid::VoidCid;
use crate::crypto::KeyVault;

use crate::ContentHash;
use crate::store::ObjectStoreExt;
use crate::Result;

/// Which side made a change in a three-way diff.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, SerdeDeserialize)]
pub enum Side {
    /// Our branch (the branch we're merging into).
    Ours,
    /// Their branch (the branch being merged).
    Theirs,
}

/// Status of a file in a three-way diff.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, SerdeDeserialize)]
pub enum ThreeWayStatus {
    /// File unchanged in all three versions.
    Unchanged,
    /// Only our side modified the file (theirs unchanged from base).
    OursOnly,
    /// Only their side modified the file (ours unchanged from base).
    TheirsOnly,
    /// Both sides made identical changes (auto-mergeable).
    BothSame,
    /// Both sides modified differently (conflict).
    Conflict,
    /// Both sides added with same content (auto-mergeable).
    AddedBothSame,
    /// Both sides added with different content (conflict).
    AddedBothDifferent,
    /// One side deleted, other side modified (conflict).
    DeleteModify {
        /// Which side deleted the file.
        deleted_by: Side,
    },
    /// Both sides deleted the file.
    BothDeleted,
}

impl ThreeWayStatus {
    /// Returns true if this status represents a conflict.
    pub fn is_conflict(&self) -> bool {
        matches!(
            self,
            ThreeWayStatus::Conflict
                | ThreeWayStatus::AddedBothDifferent
                | ThreeWayStatus::DeleteModify { .. }
        )
    }

    /// Returns true if this status can be auto-merged.
    pub fn is_auto_mergeable(&self) -> bool {
        matches!(
            self,
            ThreeWayStatus::OursOnly
                | ThreeWayStatus::TheirsOnly
                | ThreeWayStatus::BothSame
                | ThreeWayStatus::AddedBothSame
                | ThreeWayStatus::BothDeleted
        )
    }
}

/// Result of a three-way diff operation.
#[derive(Debug, Clone, Serialize, SerdeDeserialize)]
pub struct ThreeWayDiff {
    /// Status of each file by path.
    pub files: HashMap<String, ThreeWayStatus>,
    /// Paths that have conflicts (subset of files where status.is_conflict()).
    pub conflicts: Vec<String>,
    /// Paths that can be auto-merged (subset of files where status.is_auto_mergeable()).
    pub auto_mergeable: Vec<String>,
}

impl ThreeWayDiff {
    /// Creates an empty three-way diff (no changes).
    pub fn empty() -> Self {
        Self {
            files: HashMap::new(),
            conflicts: Vec::new(),
            auto_mergeable: Vec::new(),
        }
    }

    /// Returns true if there are no conflicts.
    pub fn is_clean(&self) -> bool {
        self.conflicts.is_empty()
    }

    /// Returns the number of files with changes.
    pub fn len(&self) -> usize {
        self.files.len()
    }

    /// Returns true if there are no changes.
    pub fn is_empty(&self) -> bool {
        self.files.is_empty()
    }
}

/// Collects all file entries from a commit via its TreeManifest.
fn collect_commit_file_map<S: ObjectStoreExt>(
    store: &S,
    vault: &KeyVault,
    commit_cid: &VoidCid,
) -> Result<HashMap<String, ContentHash>> {
    let (commit, reader) = load_commit_and_reader(store, vault, commit_cid)?;
    let files = collect_commit_files(store, &commit, &reader)?;
    Ok(files.into_iter().map(|f| (f.path, f.content_hash)).collect())
}

/// Classifies the status of a file given its hash in base, ours, and theirs.
///
/// Uses the following rules:
/// | Base | Ours | Theirs | Result |
/// |------|------|--------|--------|
/// | A    | A    | A      | Unchanged |
/// | A    | A    | B      | TheirsOnly |
/// | A    | B    | A      | OursOnly |
/// | A    | B    | B      | BothSame |
/// | A    | B    | C      | Conflict |
/// | -    | A    | A      | AddedBothSame |
/// | -    | A    | B      | AddedBothDifferent |
/// | A    | -    | A      | OursOnly (deleted) |
/// | A    | A    | -      | TheirsOnly (deleted) |
/// | A    | -    | -      | BothDeleted |
/// | A    | B    | -      | DeleteModify(Theirs) |
/// | A    | -    | B      | DeleteModify(Ours) |
fn classify_file(
    base: Option<&ContentHash>,
    ours: Option<&ContentHash>,
    theirs: Option<&ContentHash>,
) -> Option<ThreeWayStatus> {
    match (base, ours, theirs) {
        // All three present
        (Some(b), Some(o), Some(t)) => {
            if o == b && t == b {
                Some(ThreeWayStatus::Unchanged)
            } else if o == b && t != b {
                Some(ThreeWayStatus::TheirsOnly)
            } else if o != b && t == b {
                Some(ThreeWayStatus::OursOnly)
            } else if o == t {
                Some(ThreeWayStatus::BothSame)
            } else {
                Some(ThreeWayStatus::Conflict)
            }
        }

        // No base (file added in both)
        (None, Some(o), Some(t)) => {
            if o == t {
                Some(ThreeWayStatus::AddedBothSame)
            } else {
                Some(ThreeWayStatus::AddedBothDifferent)
            }
        }

        // No ours (we deleted or never had)
        (Some(b), None, Some(t)) => {
            if t == b {
                Some(ThreeWayStatus::OursOnly)
            } else {
                Some(ThreeWayStatus::DeleteModify {
                    deleted_by: Side::Ours,
                })
            }
        }

        // No theirs (they deleted or never had)
        (Some(b), Some(o), None) => {
            if o == b {
                Some(ThreeWayStatus::TheirsOnly)
            } else {
                Some(ThreeWayStatus::DeleteModify {
                    deleted_by: Side::Theirs,
                })
            }
        }

        // Both deleted
        (Some(_), None, None) => Some(ThreeWayStatus::BothDeleted),

        // Only in ours (added by us only)
        (None, Some(_), None) => Some(ThreeWayStatus::OursOnly),

        // Only in theirs (added by them only)
        (None, None, Some(_)) => Some(ThreeWayStatus::TheirsOnly),

        // None have it
        (None, None, None) => None,
    }
}

/// Computes a three-way diff between a base commit and two branch commits.
pub fn diff_three_way<S: ObjectStoreExt>(
    store: &S,
    vault: &KeyVault,
    base: Option<&VoidCid>,
    ours: &VoidCid,
    theirs: &VoidCid,
) -> Result<ThreeWayDiff> {
    // Load file lists from all three commits via manifest
    let base_files: HashMap<String, ContentHash> = match base {
        Some(cid) => collect_commit_file_map(store, vault, cid)?,
        None => HashMap::new(),
    };

    let ours_files = collect_commit_file_map(store, vault, ours)?;
    let theirs_files = collect_commit_file_map(store, vault, theirs)?;

    // Collect all unique paths across all three commits
    let mut all_paths: HashSet<&str> = HashSet::new();
    all_paths.extend(base_files.keys().map(|s| s.as_str()));
    all_paths.extend(ours_files.keys().map(|s| s.as_str()));
    all_paths.extend(theirs_files.keys().map(|s| s.as_str()));

    let mut files = HashMap::new();
    let mut conflicts = Vec::new();
    let mut auto_mergeable = Vec::new();

    // Classify each file
    for path in all_paths {
        let base_hash = base_files.get(path);
        let ours_hash = ours_files.get(path);
        let theirs_hash = theirs_files.get(path);

        if let Some(status) = classify_file(base_hash, ours_hash, theirs_hash) {
            // Skip unchanged files to keep the result minimal
            if matches!(status, ThreeWayStatus::Unchanged) {
                continue;
            }

            let path_owned = path.to_string();

            if status.is_conflict() {
                conflicts.push(path_owned.clone());
            } else if status.is_auto_mergeable() {
                auto_mergeable.push(path_owned.clone());
            }

            files.insert(path_owned, status);
        }
    }

    // Sort for deterministic output
    conflicts.sort();
    auto_mergeable.sort();

    Ok(ThreeWayDiff {
        files,
        conflicts,
        auto_mergeable,
    })
}

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

    // Helper to create a test hash from a simple value
    fn hash(val: u8) -> ContentHash {
        let mut h = [0u8; 32];
        h[0] = val;
        ContentHash(h)
    }

    #[test]
    fn test_classify_unchanged() {
        let a = hash(1);
        let result = classify_file(Some(&a), Some(&a), Some(&a));
        assert_eq!(result, Some(ThreeWayStatus::Unchanged));
    }

    #[test]
    fn test_classify_theirs_only() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(Some(&a), Some(&a), Some(&b));
        assert_eq!(result, Some(ThreeWayStatus::TheirsOnly));
    }

    #[test]
    fn test_classify_ours_only() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(Some(&a), Some(&b), Some(&a));
        assert_eq!(result, Some(ThreeWayStatus::OursOnly));
    }

    #[test]
    fn test_classify_both_same() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(Some(&a), Some(&b), Some(&b));
        assert_eq!(result, Some(ThreeWayStatus::BothSame));
    }

    #[test]
    fn test_classify_conflict() {
        let a = hash(1);
        let b = hash(2);
        let c = hash(3);
        let result = classify_file(Some(&a), Some(&b), Some(&c));
        assert_eq!(result, Some(ThreeWayStatus::Conflict));
    }

    #[test]
    fn test_classify_added_both_same() {
        let a = hash(1);
        let result = classify_file(None, Some(&a), Some(&a));
        assert_eq!(result, Some(ThreeWayStatus::AddedBothSame));
    }

    #[test]
    fn test_classify_added_both_different() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(None, Some(&a), Some(&b));
        assert_eq!(result, Some(ThreeWayStatus::AddedBothDifferent));
    }

    #[test]
    fn test_classify_ours_deleted() {
        let a = hash(1);
        let result = classify_file(Some(&a), None, Some(&a));
        assert_eq!(result, Some(ThreeWayStatus::OursOnly));
    }

    #[test]
    fn test_classify_theirs_deleted() {
        let a = hash(1);
        let result = classify_file(Some(&a), Some(&a), None);
        assert_eq!(result, Some(ThreeWayStatus::TheirsOnly));
    }

    #[test]
    fn test_classify_both_deleted() {
        let a = hash(1);
        let result = classify_file(Some(&a), None, None);
        assert_eq!(result, Some(ThreeWayStatus::BothDeleted));
    }

    #[test]
    fn test_classify_delete_modify_ours_deleted() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(Some(&a), None, Some(&b));
        assert_eq!(
            result,
            Some(ThreeWayStatus::DeleteModify {
                deleted_by: Side::Ours
            })
        );
    }

    #[test]
    fn test_classify_delete_modify_theirs_deleted() {
        let a = hash(1);
        let b = hash(2);
        let result = classify_file(Some(&a), Some(&b), None);
        assert_eq!(
            result,
            Some(ThreeWayStatus::DeleteModify {
                deleted_by: Side::Theirs
            })
        );
    }

    #[test]
    fn test_classify_ours_added_only() {
        let a = hash(1);
        let result = classify_file(None, Some(&a), None);
        assert_eq!(result, Some(ThreeWayStatus::OursOnly));
    }

    #[test]
    fn test_classify_theirs_added_only() {
        let a = hash(1);
        let result = classify_file(None, None, Some(&a));
        assert_eq!(result, Some(ThreeWayStatus::TheirsOnly));
    }

    #[test]
    fn test_classify_none() {
        let result = classify_file(None, None, None);
        assert_eq!(result, None);
    }

    #[test]
    fn test_status_is_conflict() {
        assert!(ThreeWayStatus::Conflict.is_conflict());
        assert!(ThreeWayStatus::AddedBothDifferent.is_conflict());
        assert!(ThreeWayStatus::DeleteModify {
            deleted_by: Side::Ours
        }
        .is_conflict());
        assert!(ThreeWayStatus::DeleteModify {
            deleted_by: Side::Theirs
        }
        .is_conflict());

        assert!(!ThreeWayStatus::Unchanged.is_conflict());
        assert!(!ThreeWayStatus::OursOnly.is_conflict());
        assert!(!ThreeWayStatus::TheirsOnly.is_conflict());
        assert!(!ThreeWayStatus::BothSame.is_conflict());
        assert!(!ThreeWayStatus::AddedBothSame.is_conflict());
        assert!(!ThreeWayStatus::BothDeleted.is_conflict());
    }

    #[test]
    fn test_status_is_auto_mergeable() {
        assert!(ThreeWayStatus::OursOnly.is_auto_mergeable());
        assert!(ThreeWayStatus::TheirsOnly.is_auto_mergeable());
        assert!(ThreeWayStatus::BothSame.is_auto_mergeable());
        assert!(ThreeWayStatus::AddedBothSame.is_auto_mergeable());
        assert!(ThreeWayStatus::BothDeleted.is_auto_mergeable());

        assert!(!ThreeWayStatus::Unchanged.is_auto_mergeable());
        assert!(!ThreeWayStatus::Conflict.is_auto_mergeable());
        assert!(!ThreeWayStatus::AddedBothDifferent.is_auto_mergeable());
        assert!(!ThreeWayStatus::DeleteModify {
            deleted_by: Side::Ours
        }
        .is_auto_mergeable());
    }

    #[test]
    fn test_three_way_diff_empty() {
        let diff = ThreeWayDiff::empty();
        assert!(diff.is_empty());
        assert!(diff.is_clean());
        assert_eq!(diff.len(), 0);
    }
}