lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0

//! Three-way merge implementation with conflict detection.
//!
//! This module implements git-style three-way merging:
//! 1. Find common ancestor (merge base)
//! 2. Diff base→ours and base→theirs
//! 3. Apply non-conflicting changes
//! 4. Detect and report conflicts

use alloc::collections::BTreeMap;
use alloc::string::{String, ToString};
use alloc::vec;
use alloc::vec::Vec;

use super::types::{
    BranchError, ChangeType, Commit, ConflictType, FileChange, FileVersion, MergeConflict,
    MergeResult, MergeStrategy,
};

// ═══════════════════════════════════════════════════════════════════════════════
// FILE STATE PROVIDER
// ═══════════════════════════════════════════════════════════════════════════════

/// Trait for accessing file state at different TXGs.
pub trait FileStateProvider {
    /// List all files at a given TXG.
    fn list_files(&self, txg: u64) -> Result<Vec<FileInfo>, String>;

    /// Get file info at a given TXG.
    fn get_file(&self, path: &str, txg: u64) -> Result<Option<FileInfo>, String>;

    /// Read file content at a given TXG.
    fn read_file(&self, path: &str, txg: u64) -> Result<Vec<u8>, String>;

    /// Compare two files for equality.
    fn files_equal(&self, path1: &str, txg1: u64, path2: &str, txg2: u64) -> Result<bool, String>;
}

/// File information at a specific TXG.
#[derive(Debug, Clone)]
pub struct FileInfo {
    /// File path.
    pub path: String,
    /// File size.
    pub size: u64,
    /// File checksum.
    pub checksum: [u64; 4],
    /// Modification time.
    pub mtime: u64,
    /// Is this a directory?
    pub is_dir: bool,
}

impl FileInfo {
    /// Convert to FileVersion.
    pub fn to_version(&self, txg: u64) -> FileVersion {
        FileVersion::new(txg, self.size, self.checksum, self.mtime)
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// DIFF ENTRY
// ═══════════════════════════════════════════════════════════════════════════════

/// A diff entry between two TXGs.
#[derive(Debug, Clone)]
pub enum DiffEntry {
    /// File was added.
    Added(FileInfo),
    /// File was deleted.
    Deleted(FileInfo),
    /// File was modified.
    Modified {
        /// Old version.
        old: FileInfo,
        /// New version.
        new: FileInfo,
    },
}

impl DiffEntry {
    /// Get the file path.
    pub fn path(&self) -> &str {
        match self {
            DiffEntry::Added(f) => &f.path,
            DiffEntry::Deleted(f) => &f.path,
            DiffEntry::Modified { new, .. } => &new.path,
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// THREE-WAY MERGE
// ═══════════════════════════════════════════════════════════════════════════════

/// Three-way merge engine.
pub struct ThreeWayMerge<'a, P: FileStateProvider> {
    /// File state provider.
    provider: &'a P,
    /// Merge strategy.
    strategy: MergeStrategy,
}

impl<'a, P: FileStateProvider> ThreeWayMerge<'a, P> {
    /// Create a new merge engine.
    pub fn new(provider: &'a P, strategy: MergeStrategy) -> Self {
        Self { provider, strategy }
    }

    /// Compute diff between two TXGs.
    pub fn diff(&self, base_txg: u64, target_txg: u64) -> Result<Vec<DiffEntry>, BranchError> {
        let base_files = self
            .provider
            .list_files(base_txg)
            .map_err(BranchError::IoError)?;
        let target_files = self
            .provider
            .list_files(target_txg)
            .map_err(BranchError::IoError)?;

        // Index files by path
        let base_map: BTreeMap<_, _> = base_files
            .into_iter()
            .map(|f| (f.path.clone(), f))
            .collect();
        let target_map: BTreeMap<_, _> = target_files
            .into_iter()
            .map(|f| (f.path.clone(), f))
            .collect();

        let mut diffs = Vec::new();

        // Find additions and modifications
        for (path, target_file) in &target_map {
            match base_map.get(path) {
                Some(base_file) => {
                    // File exists in both - check if modified
                    if base_file.checksum != target_file.checksum {
                        diffs.push(DiffEntry::Modified {
                            old: base_file.clone(),
                            new: target_file.clone(),
                        });
                    }
                }
                None => {
                    // File only in target - added
                    diffs.push(DiffEntry::Added(target_file.clone()));
                }
            }
        }

        // Find deletions
        for (path, base_file) in &base_map {
            if !target_map.contains_key(path) {
                diffs.push(DiffEntry::Deleted(base_file.clone()));
            }
        }

        Ok(diffs)
    }

    /// Perform a three-way merge.
    ///
    /// - `base_txg`: Common ancestor TXG
    /// - `ours_txg`: Our branch's head TXG
    /// - `theirs_txg`: Their branch's head TXG
    pub fn merge(
        &self,
        base_txg: u64,
        ours_txg: u64,
        theirs_txg: u64,
    ) -> Result<MergeAnalysis, BranchError> {
        // Compute diffs
        let ours_diff = self.diff(base_txg, ours_txg)?;
        let theirs_diff = self.diff(base_txg, theirs_txg)?;

        // Index diffs by path
        let ours_changes: BTreeMap<_, _> = ours_diff
            .into_iter()
            .map(|d| (d.path().to_string(), d))
            .collect();
        let theirs_changes: BTreeMap<_, _> = theirs_diff
            .into_iter()
            .map(|d| (d.path().to_string(), d))
            .collect();

        // Collect all changed paths
        let mut all_paths: Vec<_> = ours_changes
            .keys()
            .chain(theirs_changes.keys())
            .cloned()
            .collect();
        all_paths.sort();
        all_paths.dedup();

        let mut merged_changes = Vec::new();
        let mut conflicts = Vec::new();

        for path in all_paths {
            let ours = ours_changes.get(&path);
            let theirs = theirs_changes.get(&path);

            match (ours, theirs) {
                // Only we changed the file
                (Some(our_change), None) => {
                    merged_changes.push(self.diff_to_change(our_change)?);
                }

                // Only they changed the file
                (None, Some(their_change)) => {
                    merged_changes.push(self.diff_to_change(their_change)?);
                }

                // Both changed the same file - potential conflict
                (Some(our_change), Some(their_change)) => {
                    match self.resolve_conflict(
                        &path,
                        our_change,
                        their_change,
                        base_txg,
                        ours_txg,
                        theirs_txg,
                    )? {
                        ConflictResolution::NoConflict(change) => {
                            merged_changes.push(change);
                        }
                        ConflictResolution::Conflict(conflict) => {
                            // Apply strategy
                            match self.strategy {
                                MergeStrategy::Normal => {
                                    conflicts.push(conflict);
                                }
                                MergeStrategy::Ours => {
                                    merged_changes.push(self.diff_to_change(our_change)?);
                                }
                                MergeStrategy::Theirs => {
                                    merged_changes.push(self.diff_to_change(their_change)?);
                                }
                                MergeStrategy::ConflictMarkers => {
                                    // Mark as conflict but allow merge to proceed
                                    conflicts.push(conflict);
                                }
                            }
                        }
                        ConflictResolution::BothSame => {
                            // Both made the same change - just use ours
                            merged_changes.push(self.diff_to_change(our_change)?);
                        }
                    }
                }

                (None, None) => {
                    // Should never happen
                }
            }
        }

        Ok(MergeAnalysis {
            base_txg,
            ours_txg,
            theirs_txg,
            changes: merged_changes,
            conflicts,
            strategy: self.strategy,
        })
    }

    /// Convert a diff entry to a file change.
    fn diff_to_change(&self, diff: &DiffEntry) -> Result<FileChange, BranchError> {
        match diff {
            DiffEntry::Added(file) => Ok(FileChange::created(
                file.path.clone(),
                file.checksum,
                file.size,
            )),
            DiffEntry::Deleted(file) => Ok(FileChange::deleted(
                file.path.clone(),
                file.checksum,
                file.size,
            )),
            DiffEntry::Modified { old, new } => Ok(FileChange::modified(
                new.path.clone(),
                old.checksum,
                new.checksum,
                old.size,
                new.size,
            )),
        }
    }

    /// Resolve a potential conflict.
    fn resolve_conflict(
        &self,
        path: &str,
        ours: &DiffEntry,
        theirs: &DiffEntry,
        base_txg: u64,
        ours_txg: u64,
        theirs_txg: u64,
    ) -> Result<ConflictResolution, BranchError> {
        match (ours, theirs) {
            // Both added the same file
            (DiffEntry::Added(our_file), DiffEntry::Added(their_file)) => {
                if our_file.checksum == their_file.checksum {
                    // Same content - no conflict
                    Ok(ConflictResolution::BothSame)
                } else {
                    // Different content - conflict
                    Ok(ConflictResolution::Conflict(MergeConflict::both_created(
                        path.to_string(),
                        our_file.to_version(ours_txg),
                        their_file.to_version(theirs_txg),
                    )))
                }
            }

            // Both deleted the same file
            (DiffEntry::Deleted(_), DiffEntry::Deleted(_)) => {
                // Same action - no conflict
                Ok(ConflictResolution::BothSame)
            }

            // Both modified the same file
            (
                DiffEntry::Modified {
                    old: our_old,
                    new: our_new,
                },
                DiffEntry::Modified {
                    old: _their_old,
                    new: their_new,
                },
            ) => {
                if our_new.checksum == their_new.checksum {
                    // Same result - no conflict
                    Ok(ConflictResolution::BothSame)
                } else {
                    // Different modifications - conflict
                    Ok(ConflictResolution::Conflict(MergeConflict::both_modified(
                        path.to_string(),
                        our_old.to_version(base_txg),
                        our_new.to_version(ours_txg),
                        their_new.to_version(theirs_txg),
                    )))
                }
            }

            // We modified, they deleted
            (DiffEntry::Modified { old, new }, DiffEntry::Deleted(_)) => {
                Ok(ConflictResolution::Conflict(MergeConflict::modify_delete(
                    path.to_string(),
                    old.to_version(base_txg),
                    new.to_version(ours_txg),
                )))
            }

            // We deleted, they modified
            (DiffEntry::Deleted(deleted), DiffEntry::Modified { new, .. }) => {
                Ok(ConflictResolution::Conflict(MergeConflict::delete_modify(
                    path.to_string(),
                    deleted.to_version(base_txg),
                    new.to_version(theirs_txg),
                )))
            }

            // We added, they modified (shouldn't happen - file didn't exist in base)
            // We modified, they added (shouldn't happen)
            // Other edge cases
            _ => {
                // Treat as conflict
                let base_version = self
                    .provider
                    .get_file(path, base_txg)
                    .map_err(BranchError::IoError)?
                    .map(|f| f.to_version(base_txg));

                let ours_version = self
                    .provider
                    .get_file(path, ours_txg)
                    .map_err(BranchError::IoError)?
                    .map(|f| f.to_version(ours_txg));

                let theirs_version = self
                    .provider
                    .get_file(path, theirs_txg)
                    .map_err(BranchError::IoError)?
                    .map(|f| f.to_version(theirs_txg));

                Ok(ConflictResolution::Conflict(MergeConflict {
                    path: path.to_string(),
                    conflict_type: ConflictType::BothModified,
                    base: base_version,
                    ours: ours_version,
                    theirs: theirs_version,
                }))
            }
        }
    }
}

/// Result of conflict resolution.
enum ConflictResolution {
    /// No conflict, apply this change.
    NoConflict(FileChange),
    /// Conflict detected.
    Conflict(MergeConflict),
    /// Both sides made the same change.
    BothSame,
}

// ═══════════════════════════════════════════════════════════════════════════════
// MERGE ANALYSIS
// ═══════════════════════════════════════════════════════════════════════════════

/// Result of merge analysis.
#[derive(Debug, Clone)]
pub struct MergeAnalysis {
    /// Base TXG (common ancestor).
    pub base_txg: u64,
    /// Our TXG.
    pub ours_txg: u64,
    /// Their TXG.
    pub theirs_txg: u64,
    /// Non-conflicting changes to apply.
    pub changes: Vec<FileChange>,
    /// Conflicts detected.
    pub conflicts: Vec<MergeConflict>,
    /// Strategy used.
    pub strategy: MergeStrategy,
}

impl MergeAnalysis {
    /// Check if merge can proceed without conflicts.
    pub fn is_clean(&self) -> bool {
        self.conflicts.is_empty()
    }

    /// Get the number of conflicts.
    pub fn conflict_count(&self) -> usize {
        self.conflicts.len()
    }

    /// Get changes count.
    pub fn change_count(&self) -> usize {
        self.changes.len()
    }

    /// Convert to MergeResult.
    pub fn to_result(&self, result_txg: Option<u64>, merge_commit: Option<Commit>) -> MergeResult {
        MergeResult {
            merged_files: self.changes.len(),
            conflicts: self.conflicts.clone(),
            result_txg,
            merge_commit,
        }
    }

    /// Get all conflicting paths.
    pub fn conflicting_paths(&self) -> Vec<&str> {
        self.conflicts.iter().map(|c| c.path.as_str()).collect()
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// MERGE EXECUTOR
// ═══════════════════════════════════════════════════════════════════════════════

/// Trait for executing merge operations.
pub trait MergeExecutor {
    /// Apply a merge to create a new TXG.
    fn apply_merge(&mut self, analysis: &MergeAnalysis) -> Result<u64, String>;

    /// Create conflict markers in files.
    fn create_conflict_markers(
        &mut self,
        path: &str,
        base_content: Option<&[u8]>,
        ours_content: &[u8],
        theirs_content: &[u8],
    ) -> Result<(), String>;
}

// ═══════════════════════════════════════════════════════════════════════════════
// TESTS
// ═══════════════════════════════════════════════════════════════════════════════

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

    /// Mock file state provider for testing.
    struct MockFileProvider {
        states: BTreeMap<u64, BTreeMap<String, FileInfo>>,
    }

    impl MockFileProvider {
        fn new() -> Self {
            Self {
                states: BTreeMap::new(),
            }
        }

        fn add_file(&mut self, txg: u64, path: &str, checksum: [u64; 4], size: u64) {
            let state = self.states.entry(txg).or_default();
            state.insert(
                path.to_string(),
                FileInfo {
                    path: path.to_string(),
                    size,
                    checksum,
                    mtime: txg * 1000,
                    is_dir: false,
                },
            );
        }
    }

    impl FileStateProvider for MockFileProvider {
        fn list_files(&self, txg: u64) -> Result<Vec<FileInfo>, String> {
            Ok(self
                .states
                .get(&txg)
                .map(|s| s.values().cloned().collect())
                .unwrap_or_default())
        }

        fn get_file(&self, path: &str, txg: u64) -> Result<Option<FileInfo>, String> {
            Ok(self.states.get(&txg).and_then(|s| s.get(path).cloned()))
        }

        fn read_file(&self, _path: &str, _txg: u64) -> Result<Vec<u8>, String> {
            Ok(vec![])
        }

        fn files_equal(
            &self,
            path1: &str,
            txg1: u64,
            path2: &str,
            txg2: u64,
        ) -> Result<bool, String> {
            let f1 = self.get_file(path1, txg1)?;
            let f2 = self.get_file(path2, txg2)?;
            match (f1, f2) {
                (Some(a), Some(b)) => Ok(a.checksum == b.checksum),
                (None, None) => Ok(true),
                _ => Ok(false),
            }
        }
    }

    #[test]
    fn test_diff_added() {
        let mut provider = MockFileProvider::new();

        // Base: empty
        provider.states.insert(0, BTreeMap::new());

        // Target: has a file
        provider.add_file(1, "/new.txt", [1; 4], 100);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let diff = merger.diff(0, 1).unwrap();

        assert_eq!(diff.len(), 1);
        assert!(matches!(diff[0], DiffEntry::Added(_)));
    }

    #[test]
    fn test_diff_deleted() {
        let mut provider = MockFileProvider::new();

        // Base: has a file
        provider.add_file(0, "/old.txt", [1; 4], 100);

        // Target: empty
        provider.states.insert(1, BTreeMap::new());

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let diff = merger.diff(0, 1).unwrap();

        assert_eq!(diff.len(), 1);
        assert!(matches!(diff[0], DiffEntry::Deleted(_)));
    }

    #[test]
    fn test_diff_modified() {
        let mut provider = MockFileProvider::new();

        // Base: file with checksum [1;4]
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Target: file with different checksum
        provider.add_file(1, "/file.txt", [2; 4], 200);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let diff = merger.diff(0, 1).unwrap();

        assert_eq!(diff.len(), 1);
        assert!(matches!(diff[0], DiffEntry::Modified { .. }));
    }

    #[test]
    fn test_merge_no_conflict() {
        let mut provider = MockFileProvider::new();

        // Base: has file_a
        provider.add_file(0, "/file_a.txt", [1; 4], 100);

        // Ours: modified file_a
        provider.add_file(1, "/file_a.txt", [2; 4], 100);

        // Theirs: added file_b (no overlap with our changes)
        provider.add_file(0, "/file_a.txt", [1; 4], 100); // clone base for theirs
        provider.add_file(2, "/file_a.txt", [1; 4], 100);
        provider.add_file(2, "/file_b.txt", [3; 4], 200);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let analysis = merger.merge(0, 1, 2).unwrap();

        assert!(analysis.is_clean());
        assert_eq!(analysis.change_count(), 2); // our modification + their addition
    }

    #[test]
    fn test_merge_conflict_both_modified() {
        let mut provider = MockFileProvider::new();

        // Base: has file
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Ours: modified to checksum [2;4]
        provider.add_file(1, "/file.txt", [2; 4], 100);

        // Theirs: modified to checksum [3;4]
        provider.add_file(2, "/file.txt", [3; 4], 100);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let analysis = merger.merge(0, 1, 2).unwrap();

        assert!(!analysis.is_clean());
        assert_eq!(analysis.conflict_count(), 1);
        assert!(matches!(
            analysis.conflicts[0].conflict_type,
            ConflictType::BothModified
        ));
    }

    #[test]
    fn test_merge_conflict_modify_delete() {
        let mut provider = MockFileProvider::new();

        // Base: has file
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Ours: modified
        provider.add_file(1, "/file.txt", [2; 4], 100);

        // Theirs: deleted (empty state)
        provider.states.insert(2, BTreeMap::new());

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let analysis = merger.merge(0, 1, 2).unwrap();

        assert!(!analysis.is_clean());
        assert_eq!(analysis.conflict_count(), 1);
        assert!(matches!(
            analysis.conflicts[0].conflict_type,
            ConflictType::ModifyDelete
        ));
    }

    #[test]
    fn test_merge_both_same_change() {
        let mut provider = MockFileProvider::new();

        // Base: has file
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Ours: modified to checksum [2;4]
        provider.add_file(1, "/file.txt", [2; 4], 100);

        // Theirs: also modified to checksum [2;4]
        provider.add_file(2, "/file.txt", [2; 4], 100);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Normal);
        let analysis = merger.merge(0, 1, 2).unwrap();

        // Should not be a conflict - both made the same change
        assert!(analysis.is_clean());
        assert_eq!(analysis.change_count(), 1);
    }

    #[test]
    fn test_merge_strategy_ours() {
        let mut provider = MockFileProvider::new();

        // Base: has file
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Ours: modified
        provider.add_file(1, "/file.txt", [2; 4], 100);

        // Theirs: differently modified
        provider.add_file(2, "/file.txt", [3; 4], 100);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Ours);
        let analysis = merger.merge(0, 1, 2).unwrap();

        // With "ours" strategy, conflicts are auto-resolved
        assert!(analysis.is_clean());
        assert_eq!(analysis.change_count(), 1);

        // Our change should be the one applied
        let change = &analysis.changes[0];
        assert_eq!(change.new_checksum, Some([2; 4]));
    }

    #[test]
    fn test_merge_strategy_theirs() {
        let mut provider = MockFileProvider::new();

        // Base: has file
        provider.add_file(0, "/file.txt", [1; 4], 100);

        // Ours: modified
        provider.add_file(1, "/file.txt", [2; 4], 100);

        // Theirs: differently modified
        provider.add_file(2, "/file.txt", [3; 4], 100);

        let merger = ThreeWayMerge::new(&provider, MergeStrategy::Theirs);
        let analysis = merger.merge(0, 1, 2).unwrap();

        // With "theirs" strategy, conflicts are auto-resolved
        assert!(analysis.is_clean());
        assert_eq!(analysis.change_count(), 1);

        // Their change should be the one applied
        let change = &analysis.changes[0];
        assert_eq!(change.new_checksum, Some([3; 4]));
    }

    #[test]
    fn test_merge_analysis_to_result() {
        let analysis = MergeAnalysis {
            base_txg: 0,
            ours_txg: 1,
            theirs_txg: 2,
            changes: vec![FileChange::created("/file.txt".into(), [1; 4], 100)],
            conflicts: vec![],
            strategy: MergeStrategy::Normal,
        };

        let result = analysis.to_result(Some(3), None);

        assert!(result.is_success());
        assert_eq!(result.merged_files, 1);
        assert_eq!(result.result_txg, Some(3));
    }

    #[test]
    fn test_conflicting_paths() {
        let analysis = MergeAnalysis {
            base_txg: 0,
            ours_txg: 1,
            theirs_txg: 2,
            changes: vec![],
            conflicts: vec![
                MergeConflict {
                    path: "/a.txt".into(),
                    conflict_type: ConflictType::BothModified,
                    base: None,
                    ours: None,
                    theirs: None,
                },
                MergeConflict {
                    path: "/b.txt".into(),
                    conflict_type: ConflictType::ModifyDelete,
                    base: None,
                    ours: None,
                    theirs: None,
                },
            ],
            strategy: MergeStrategy::Normal,
        };

        let paths = analysis.conflicting_paths();
        assert_eq!(paths, vec!["/a.txt", "/b.txt"]);
    }
}