maw/model/

join.rs

//! `PatchSet` join — CRDT merge of two patch-sets sharing the same base epoch.
//!
//! The join operation combines two [`PatchSet`]s into one by unioning their
//! path maps. When both patch-sets touch the same path, we resolve:
//!
//! 1. **Identical** — same [`PatchValue`]: idempotent, keep one copy.
//! 2. **Compatible** — mergeable edits on the same path (e.g. both Add the
//!    same blob via different `FileIds` would conflict, but identical Adds are
//!    idempotent per case 1).
//! 3. **Conflicting** — incompatible edits: emit a [`PathConflict`].
//!
//! # CRDT properties
//!
//! `join` is:
//! - **Commutative**: `join(a, b) == join(b, a)`
//! - **Associative**: `join(join(a, b), c) == join(a, join(b, c))`
//! - **Idempotent**: `join(a, a) == a`
//!
//! These hold because:
//! - [`BTreeMap`] iteration is deterministic.
//! - Identical entries collapse (idempotent).
//! - Conflict detection is symmetric (both sides produce the same
//!   [`PathConflict`] regardless of argument order because sides are sorted).

#![allow(clippy::missing_errors_doc)]

use std::collections::BTreeMap;
use std::fmt;
use std::path::PathBuf;

use serde::{Deserialize, Serialize};

use super::patch::{PatchSet, PatchValue};
use super::types::EpochId;

// ---------------------------------------------------------------------------
// JoinResult
// ---------------------------------------------------------------------------

/// The result of joining two [`PatchSet`]s.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct JoinResult {
    /// The merged patch-set containing all non-conflicting entries.
    pub merged: PatchSet,
    /// Paths where the two patch-sets could not be reconciled.
    pub conflicts: Vec<PathConflict>,
}

impl JoinResult {
    /// Returns `true` if the join completed without conflicts.
    #[must_use]
    pub const fn is_clean(&self) -> bool {
        self.conflicts.is_empty()
    }
}

// ---------------------------------------------------------------------------
// PathConflict
// ---------------------------------------------------------------------------

/// A conflict on a single path during [`join`].
///
/// Contains both sides so callers can inspect what each patch-set wanted
/// to do and decide on a resolution strategy.
///
/// `sides` is always sorted (by [`PatchValue`]'s `Ord`-equivalent canonical
/// JSON) to guarantee commutativity.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct PathConflict {
    /// The path where the conflict occurred.
    pub path: PathBuf,
    /// What the two patch-sets each wanted to do to this path.
    /// Always exactly 2 elements, sorted for determinism.
    pub sides: [PatchValue; 2],
    /// Human-readable reason for the conflict.
    pub reason: ConflictReason,
}

// ---------------------------------------------------------------------------
// ConflictReason
// ---------------------------------------------------------------------------

/// Why two [`PatchValue`]s on the same path could not be merged.
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ConflictReason {
    /// Both sides add a file but with different content or file identity.
    DivergentAdd,
    /// Both sides modify a file but produce different new blobs.
    DivergentModify,
    /// One side modifies the file, the other deletes it.
    ModifyDelete,
    /// One side renames, the other modifies in a way that conflicts.
    RenameConflict,
    /// Both sides rename the same file to different destinations.
    DivergentRename,
    /// General incompatibility (different operation types on the same path).
    Incompatible,
}

impl fmt::Display for ConflictReason {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::DivergentAdd => write!(f, "both sides add different content"),
            Self::DivergentModify => write!(f, "both sides modify to different results"),
            Self::ModifyDelete => write!(f, "one side modifies, the other deletes"),
            Self::RenameConflict => write!(f, "rename conflicts with another operation"),
            Self::DivergentRename => write!(f, "both sides rename to different destinations"),
            Self::Incompatible => write!(f, "incompatible operations on the same path"),
        }
    }
}

// ---------------------------------------------------------------------------
// JoinError
// ---------------------------------------------------------------------------

/// Error that occurs if `join` is called on patch-sets with different base epochs.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct EpochMismatch {
    pub left: EpochId,
    pub right: EpochId,
}

impl fmt::Display for EpochMismatch {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "cannot join patch-sets with different base epochs: {} vs {}",
            self.left, self.right
        )
    }
}

impl std::error::Error for EpochMismatch {}

// ---------------------------------------------------------------------------
// join
// ---------------------------------------------------------------------------

/// Join (CRDT merge) two [`PatchSet`]s that share the same base epoch.
///
/// # Precondition
///
/// Both patch-sets must share the same `base_epoch`. If they don't,
/// [`EpochMismatch`] is returned.
///
/// # Algorithm
///
/// 1. Iterate the union of all paths from both patch-sets (`BTreeMap` ensures
///    sorted, deterministic order).
/// 2. For each path:
///    - Present in only one side → take it (disjoint union).
///    - Present in both, identical → keep one copy (idempotent).
///    - Present in both, different → classify as compatible or conflicting.
///
/// # CRDT guarantees
///
/// - **Commutativity**: `join(a, b) == join(b, a)` — ensured by sorting
///   conflict sides canonically.
/// - **Associativity**: `join(join(a, b), c) == join(a, join(b, c))` —
///   ensured by deterministic conflict detection and identical-entry collapse.
/// - **Idempotency**: `join(a, a) == a` — identical entries collapse.
pub fn join(a: &PatchSet, b: &PatchSet) -> Result<JoinResult, EpochMismatch> {
    if a.base_epoch != b.base_epoch {
        return Err(EpochMismatch {
            left: a.base_epoch.clone(),
            right: b.base_epoch.clone(),
        });
    }

    let mut merged = BTreeMap::new();
    let mut conflicts = Vec::new();

    // Collect all paths from both sides.
    let all_paths: BTreeMap<&PathBuf, (Option<&PatchValue>, Option<&PatchValue>)> = {
        let mut m: BTreeMap<&PathBuf, (Option<&PatchValue>, Option<&PatchValue>)> = BTreeMap::new();
        for (path, val) in &a.patches {
            m.entry(path).or_insert((None, None)).0 = Some(val);
        }
        for (path, val) in &b.patches {
            m.entry(path).or_insert((None, None)).1 = Some(val);
        }
        m
    };

    for (path, (left, right)) in &all_paths {
        match (left, right) {
            // Only in left → take it.
            (Some(l), None) => {
                merged.insert((*path).clone(), (*l).clone());
            }
            // Only in right → take it.
            (None, Some(r)) => {
                merged.insert((*path).clone(), (*r).clone());
            }
            // In both — check if identical.
            (Some(l), Some(r)) => {
                if *l == *r {
                    // Idempotent: identical entries collapse.
                    merged.insert((*path).clone(), (*l).clone());
                } else {
                    // Try to classify the conflict.
                    let reason = classify_conflict(l, r);
                    let sides = sorted_sides(l, r);
                    conflicts.push(PathConflict {
                        path: (*path).clone(),
                        sides,
                        reason,
                    });
                }
            }
            // Neither (impossible due to construction, but handle gracefully).
            (None, None) => {}
        }
    }

    Ok(JoinResult {
        merged: PatchSet {
            base_epoch: a.base_epoch.clone(),
            patches: merged,
        },
        conflicts,
    })
}

// ---------------------------------------------------------------------------
// Conflict classification
// ---------------------------------------------------------------------------

/// Classify why two different `PatchValues` on the same path conflict.
fn classify_conflict(left: &PatchValue, right: &PatchValue) -> ConflictReason {
    use PatchValue::{Add, Delete, Modify, Rename};
    match (left, right) {
        // Both Add, different content/identity → divergent add.
        (Add { .. }, Add { .. }) => ConflictReason::DivergentAdd,

        // Both Modify, different new_blob → divergent modify.
        (Modify { .. }, Modify { .. }) => ConflictReason::DivergentModify,

        // Modify + Delete or Delete + Modify → modify/delete conflict.
        (Modify { .. }, Delete { .. }) | (Delete { .. }, Modify { .. }) => {
            ConflictReason::ModifyDelete
        }

        // Both Rename → check if destinations differ.
        (Rename { from: from_l, .. }, Rename { from: from_r, .. }) => {
            if from_l == from_r {
                ConflictReason::DivergentRename
            } else {
                ConflictReason::Incompatible
            }
        }

        // Rename + something else → rename conflict.
        (Rename { .. }, _) | (_, Rename { .. }) => ConflictReason::RenameConflict,

        // Anything else → generic incompatible.
        _ => ConflictReason::Incompatible,
    }
}

/// Return both sides sorted by their canonical JSON for deterministic ordering.
///
/// This ensures `join(a, b)` and `join(b, a)` produce the same conflict entries.
fn sorted_sides(left: &PatchValue, right: &PatchValue) -> [PatchValue; 2] {
    let l_json = serde_json::to_string(left).unwrap_or_default();
    let r_json = serde_json::to_string(right).unwrap_or_default();
    if l_json <= r_json {
        [left.clone(), right.clone()]
    } else {
        [right.clone(), left.clone()]
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
#[allow(clippy::all, clippy::pedantic, clippy::nursery)]
mod tests {
    use super::*;
    use crate::model::patch::{FileId, PatchSet, PatchValue};
    use crate::model::types::{EpochId, GitOid};

    // -----------------------------------------------------------------------
    // Helpers
    // -----------------------------------------------------------------------

    fn oid(c: char) -> String {
        c.to_string().repeat(40)
    }

    fn epoch(c: char) -> EpochId {
        EpochId::new(&oid(c)).unwrap()
    }

    fn git_oid(c: char) -> GitOid {
        GitOid::new(&oid(c)).unwrap()
    }

    fn fid(n: u128) -> FileId {
        FileId::new(n)
    }

    fn empty_ps(e: char) -> PatchSet {
        PatchSet::empty(epoch(e))
    }

    // -----------------------------------------------------------------------
    // Precondition: epoch mismatch
    // -----------------------------------------------------------------------

    #[test]
    fn join_epoch_mismatch() {
        let a = empty_ps('a');
        let b = empty_ps('b');
        let err = join(&a, &b).unwrap_err();
        assert_eq!(err.left, epoch('a'));
        assert_eq!(err.right, epoch('b'));
    }

    // -----------------------------------------------------------------------
    // Disjoint paths (union)
    // -----------------------------------------------------------------------

    #[test]
    fn join_disjoint_paths() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "src/foo.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "src/bar.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 2);
        assert!(
            result
                .merged
                .patches
                .contains_key(&PathBuf::from("src/foo.rs"))
        );
        assert!(
            result
                .merged
                .patches
                .contains_key(&PathBuf::from("src/bar.rs"))
        );
    }

    #[test]
    fn join_empty_with_non_empty() {
        let a = empty_ps('a');
        let mut b = empty_ps('a');
        b.patches.insert(
            "file.txt".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 1);
    }

    #[test]
    fn join_two_empties() {
        let a = empty_ps('a');
        let b = empty_ps('a');
        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert!(result.merged.is_empty());
    }

    // -----------------------------------------------------------------------
    // Identical entries (idempotent)
    // -----------------------------------------------------------------------

    #[test]
    fn join_identical_add() {
        let pv = PatchValue::Add {
            blob: git_oid('1'),
            file_id: fid(1),
        };
        let mut a = empty_ps('a');
        a.patches.insert("file.rs".into(), pv.clone());

        let mut b = empty_ps('a');
        b.patches.insert("file.rs".into(), pv.clone());

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 1);
        assert_eq!(result.merged.patches[&PathBuf::from("file.rs")], pv);
    }

    #[test]
    fn join_identical_modify() {
        let pv = PatchValue::Modify {
            base_blob: git_oid('1'),
            new_blob: git_oid('2'),
            file_id: fid(1),
        };
        let mut a = empty_ps('a');
        a.patches.insert("file.rs".into(), pv.clone());

        let mut b = empty_ps('a');
        b.patches.insert("file.rs".into(), pv);

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 1);
    }

    #[test]
    fn join_identical_delete() {
        let pv = PatchValue::Delete {
            previous_blob: git_oid('1'),
            file_id: fid(1),
        };
        let mut a = empty_ps('a');
        a.patches.insert("file.rs".into(), pv.clone());

        let mut b = empty_ps('a');
        b.patches.insert("file.rs".into(), pv);

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 1);
    }

    #[test]
    fn join_identical_rename() {
        let pv = PatchValue::Rename {
            from: "old.rs".into(),
            file_id: fid(1),
            new_blob: None,
        };
        let mut a = empty_ps('a');
        a.patches.insert("new.rs".into(), pv.clone());

        let mut b = empty_ps('a');
        b.patches.insert("new.rs".into(), pv);

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 1);
    }

    // -----------------------------------------------------------------------
    // Conflicting entries
    // -----------------------------------------------------------------------

    #[test]
    fn join_divergent_add() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts.len(), 1);
        assert_eq!(result.conflicts[0].path, PathBuf::from("file.rs"));
        assert_eq!(result.conflicts[0].reason, ConflictReason::DivergentAdd);
        // Conflicted path should NOT be in merged.
        assert!(
            !result
                .merged
                .patches
                .contains_key(&PathBuf::from("file.rs"))
        );
    }

    #[test]
    fn join_divergent_modify() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('1'),
                new_blob: git_oid('2'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('1'),
                new_blob: git_oid('3'),
                file_id: fid(1),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts.len(), 1);
        assert_eq!(result.conflicts[0].reason, ConflictReason::DivergentModify);
    }

    #[test]
    fn join_modify_delete() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('1'),
                new_blob: git_oid('2'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Delete {
                previous_blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts.len(), 1);
        assert_eq!(result.conflicts[0].reason, ConflictReason::ModifyDelete);
    }

    #[test]
    fn join_divergent_rename() {
        // Same source file renamed to two different destinations by the two sides.
        // Side a: old.rs → new_a.rs
        // Side b: old.rs → new_b.rs
        // Both entries appear under their respective destination paths,
        // but since the destinations differ, they land in disjoint paths.
        // However, if both appear under the SAME destination path with
        // different source, that's an incompatible conflict.

        // Actually, for divergent rename: same `from`, different destination key.
        // These would be disjoint paths, so no conflict at the path level.
        // Rename conflicts at the path level happen when both sides
        // write to the SAME destination from the SAME source with different content.

        let mut a = empty_ps('a');
        a.patches.insert(
            "dest.rs".into(),
            PatchValue::Rename {
                from: "src.rs".into(),
                file_id: fid(1),
                new_blob: None,
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "dest.rs".into(),
            PatchValue::Rename {
                from: "src.rs".into(),
                file_id: fid(1),
                new_blob: Some(git_oid('2')),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts.len(), 1);
        assert_eq!(result.conflicts[0].reason, ConflictReason::DivergentRename);
    }

    #[test]
    fn join_rename_vs_modify() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Rename {
                from: "old.rs".into(),
                file_id: fid(1),
                new_blob: None,
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('1'),
                new_blob: git_oid('2'),
                file_id: fid(1),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts[0].reason, ConflictReason::RenameConflict);
    }

    #[test]
    fn join_add_vs_delete() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Delete {
                previous_blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let result = join(&a, &b).unwrap();
        assert!(!result.is_clean());
        assert_eq!(result.conflicts[0].reason, ConflictReason::Incompatible);
    }

    // -----------------------------------------------------------------------
    // Mixed: some disjoint, some identical, some conflicting
    // -----------------------------------------------------------------------

    #[test]
    fn join_mixed_scenario() {
        let mut a = empty_ps('a');
        // Disjoint: only in a
        a.patches.insert(
            "only_a.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );
        // Identical: same in both
        a.patches.insert(
            "shared.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('2'),
                new_blob: git_oid('3'),
                file_id: fid(2),
            },
        );
        // Conflicting: different in both
        a.patches.insert(
            "conflict.rs".into(),
            PatchValue::Add {
                blob: git_oid('4'),
                file_id: fid(3),
            },
        );

        let mut b = empty_ps('a');
        // Disjoint: only in b
        b.patches.insert(
            "only_b.rs".into(),
            PatchValue::Delete {
                previous_blob: git_oid('5'),
                file_id: fid(4),
            },
        );
        // Identical: same as a
        b.patches.insert(
            "shared.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('2'),
                new_blob: git_oid('3'),
                file_id: fid(2),
            },
        );
        // Conflicting: different from a
        b.patches.insert(
            "conflict.rs".into(),
            PatchValue::Add {
                blob: git_oid('6'),
                file_id: fid(5),
            },
        );

        let result = join(&a, &b).unwrap();
        // 3 paths merged (only_a, only_b, shared), 1 conflict
        assert_eq!(result.merged.len(), 3);
        assert!(
            result
                .merged
                .patches
                .contains_key(&PathBuf::from("only_a.rs"))
        );
        assert!(
            result
                .merged
                .patches
                .contains_key(&PathBuf::from("only_b.rs"))
        );
        assert!(
            result
                .merged
                .patches
                .contains_key(&PathBuf::from("shared.rs"))
        );
        assert!(
            !result
                .merged
                .patches
                .contains_key(&PathBuf::from("conflict.rs"))
        );
        assert_eq!(result.conflicts.len(), 1);
        assert_eq!(result.conflicts[0].path, PathBuf::from("conflict.rs"));
    }

    // -----------------------------------------------------------------------
    // CRDT property: commutativity
    // -----------------------------------------------------------------------

    #[test]
    fn join_is_commutative_disjoint() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "a.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "b.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let ab = join(&a, &b).unwrap();
        let ba = join(&b, &a).unwrap();
        assert_eq!(ab, ba, "join must be commutative");
    }

    #[test]
    fn join_is_commutative_conflicting() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let ab = join(&a, &b).unwrap();
        let ba = join(&b, &a).unwrap();
        assert_eq!(ab, ba, "join must be commutative even with conflicts");
    }

    // -----------------------------------------------------------------------
    // CRDT property: idempotency
    // -----------------------------------------------------------------------

    #[test]
    fn join_is_idempotent() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Modify {
                base_blob: git_oid('1'),
                new_blob: git_oid('2'),
                file_id: fid(1),
            },
        );
        a.patches.insert(
            "other.rs".into(),
            PatchValue::Delete {
                previous_blob: git_oid('3'),
                file_id: fid(2),
            },
        );

        let result = join(&a, &a).unwrap();
        assert!(result.is_clean(), "join(a, a) must have no conflicts");
        assert_eq!(result.merged, a, "join(a, a) must equal a");
    }

    // -----------------------------------------------------------------------
    // CRDT property: associativity
    // -----------------------------------------------------------------------

    #[test]
    fn join_is_associative_disjoint() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "a.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "b.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let mut c = empty_ps('a');
        c.patches.insert(
            "c.rs".into(),
            PatchValue::Add {
                blob: git_oid('3'),
                file_id: fid(3),
            },
        );

        // (a ⊕ b) ⊕ c
        let ab = join(&a, &b).unwrap();
        assert!(ab.is_clean());
        let abc_left = join(&ab.merged, &c).unwrap();

        // a ⊕ (b ⊕ c)
        let bc = join(&b, &c).unwrap();
        assert!(bc.is_clean());
        let abc_right = join(&a, &bc.merged).unwrap();

        assert_eq!(abc_left, abc_right, "join must be associative");
    }

    // -----------------------------------------------------------------------
    // Edge cases
    // -----------------------------------------------------------------------

    #[test]
    fn join_many_disjoint_paths() {
        let mut a = empty_ps('a');
        let mut b = empty_ps('a');
        for i in 0..50 {
            a.patches.insert(
                format!("a_{i:03}.rs").into(),
                PatchValue::Add {
                    blob: git_oid('a'),
                    file_id: fid(i as u128),
                },
            );
            b.patches.insert(
                format!("b_{i:03}.rs").into(),
                PatchValue::Add {
                    blob: git_oid('b'),
                    file_id: fid(100 + i as u128),
                },
            );
        }

        let result = join(&a, &b).unwrap();
        assert!(result.is_clean());
        assert_eq!(result.merged.len(), 100);
    }

    #[test]
    fn join_result_serde_round_trip() {
        let mut a = empty_ps('a');
        a.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('1'),
                file_id: fid(1),
            },
        );

        let mut b = empty_ps('a');
        b.patches.insert(
            "file.rs".into(),
            PatchValue::Add {
                blob: git_oid('2'),
                file_id: fid(2),
            },
        );

        let result = join(&a, &b).unwrap();
        let json = serde_json::to_string(&result).unwrap();
        let decoded: JoinResult = serde_json::from_str(&json).unwrap();
        assert_eq!(decoded, result);
    }

    #[test]
    fn conflict_reason_display() {
        assert!(!ConflictReason::DivergentAdd.to_string().is_empty());
        assert!(!ConflictReason::DivergentModify.to_string().is_empty());
        assert!(!ConflictReason::ModifyDelete.to_string().is_empty());
        assert!(!ConflictReason::RenameConflict.to_string().is_empty());
        assert!(!ConflictReason::DivergentRename.to_string().is_empty());
        assert!(!ConflictReason::Incompatible.to_string().is_empty());
    }

    #[test]
    fn epoch_mismatch_display() {
        let err = EpochMismatch {
            left: epoch('a'),
            right: epoch('b'),
        };
        let msg = format!("{err}");
        assert!(msg.contains("different base epochs"));
    }
}

// ---------------------------------------------------------------------------
// Property tests
// ---------------------------------------------------------------------------

#[cfg(test)]
#[allow(clippy::all, clippy::pedantic, clippy::nursery)]
mod proptests {
    use super::*;
    use crate::model::patch::{FileId, PatchSet, PatchValue};
    use crate::model::types::{EpochId, GitOid};
    use proptest::prelude::*;

    // Strategy: generate a random PatchSet with a fixed epoch.
    fn arb_git_oid() -> impl Strategy<Value = GitOid> {
        "[0-9a-f]{40}".prop_map(|s| GitOid::new(&s).unwrap())
    }

    fn arb_file_id() -> impl Strategy<Value = FileId> {
        any::<u128>().prop_map(FileId::new)
    }

    fn arb_patch_value() -> impl Strategy<Value = PatchValue> {
        prop_oneof![
            (arb_git_oid(), arb_file_id())
                .prop_map(|(blob, file_id)| PatchValue::Add { blob, file_id }),
            (arb_git_oid(), arb_file_id()).prop_map(|(previous_blob, file_id)| {
                PatchValue::Delete {
                    previous_blob,
                    file_id,
                }
            }),
            (arb_git_oid(), arb_git_oid(), arb_file_id()).prop_map(
                |(base_blob, new_blob, file_id)| PatchValue::Modify {
                    base_blob,
                    new_blob,
                    file_id
                }
            ),
        ]
    }

    fn arb_path() -> impl Strategy<Value = PathBuf> {
        prop_oneof![
            Just(PathBuf::from("src/main.rs")),
            Just(PathBuf::from("src/lib.rs")),
            Just(PathBuf::from("src/model.rs")),
            Just(PathBuf::from("README.md")),
            Just(PathBuf::from("Cargo.toml")),
            Just(PathBuf::from("tests/test.rs")),
            Just(PathBuf::from("src/a.rs")),
            Just(PathBuf::from("src/b.rs")),
        ]
    }

    fn arb_patchset() -> impl Strategy<Value = PatchSet> {
        // Fixed epoch for join compatibility.
        let epoch = EpochId::new(&"a".repeat(40)).unwrap();
        prop::collection::btree_map(arb_path(), arb_patch_value(), 0..5).prop_map(move |patches| {
            PatchSet {
                base_epoch: epoch.clone(),
                patches,
            }
        })
    }

    proptest! {
        #[test]
        fn prop_commutativity(a in arb_patchset(), b in arb_patchset()) {
            let ab = join(&a, &b).unwrap();
            let ba = join(&b, &a).unwrap();
            prop_assert_eq!(ab, ba, "join must be commutative");
        }

        #[test]
        fn prop_idempotency(a in arb_patchset()) {
            let aa = join(&a, &a).unwrap();
            prop_assert!(aa.is_clean(), "join(a, a) must have no conflicts");
            prop_assert_eq!(aa.merged, a, "join(a, a) must equal a");
        }

        #[test]
        fn prop_associativity_clean(
            a in arb_patchset(),
            b in arb_patchset(),
            c in arb_patchset()
        ) {
            // Associativity only holds cleanly when there are no conflicts
            // in intermediate joins (conflicted paths are excluded from merged,
            // so the composition may differ). Test the clean case.
            let ab = join(&a, &b).unwrap();
            let bc = join(&b, &c).unwrap();
            if ab.is_clean() && bc.is_clean() {
                let abc_left = join(&ab.merged, &c).unwrap();
                let abc_right = join(&a, &bc.merged).unwrap();
                prop_assert_eq!(abc_left, abc_right, "join must be associative for clean joins");
            }
            // When there are conflicts, we intentionally skip — associativity
            // with conflicts requires a richer algebra (conflict sets).
        }
    }
}