Function three_way_merge

atomic-core/src/merge/three_way.rs:99–157

Perform a three-way merge of token sequences. `base` — the common ancestor's tokens `left` — one side's tokens `right` — the other side's tokens Returns [`ThreeWayResult::Merged`] when all edits are to different positions, or [`ThreeWayResult::Conflict`] when at least one token position was changed by both sides to different values.

(
    base: &[MergeToken],
    left: &[MergeToken],
    right: &[MergeToken],
)

/// positions, or [`ThreeWayResult::Conflict`] when at least one token
/// position was changed by both sides to different values.
pub fn three_way_merge(
    base: &[MergeToken],
    left: &[MergeToken],
    right: &[MergeToken],
) -> ThreeWayResult {
    // Fast path: if left and right are identical, no conflict possible.
    if left == right {
        let content = reassemble_tokens(left);
        return ThreeWayResult::Merged(content);
    }

    // Fast path: if left is unchanged, take right.
    if left == base {
        let content = reassemble_tokens(right);
        return ThreeWayResult::Merged(content);
    }

    // Fast path: if right is unchanged, take left.
    if right == base {
        let content = reassemble_tokens(left);
        return ThreeWayResult::Merged(content);
    }

    // --- General case: LCS-based alignment ---

    let left_ops = diff_tokens(base, left);
    let right_ops = diff_tokens(base, right);

    // Collect base indices modified by each side.
    let left_modified = modified_indices(&left_ops);
    let right_modified = modified_indices(&right_ops);

    // Check for overlapping modifications.
    for idx in left_modified.intersection(&right_modified) {
        // Both sides touched the same base index. This is only OK
        // if they produced the *same* replacement.
        let left_replacement = replacement_for(&left_ops, *idx);
        let right_replacement = replacement_for(&right_ops, *idx);
        if left_replacement != right_replacement {
            return ThreeWayResult::Conflict;
        }
    }

    // Check for conflicting insertions at the same position.
    let left_inserts = insert_positions(&left_ops);
    let right_inserts = insert_positions(&right_ops);
    for pos in left_inserts.keys() {
        if let Some(right_content) = right_inserts.get(pos) {
            let left_content = &left_inserts[pos];
            if left_content != right_content {
                return ThreeWayResult::Conflict;
            }
        }
    }

    // No conflicts — merge.
    let merged = merge_ops(base, &left_ops, &right_ops);
    ThreeWayResult::Merged(merged)