path: root/docs/design/branch-based-merge.md

# Branch-Based Merge with Conflict Detection

**Last Updated:** 2025-11-13

## Overview

This document describes the approach for handling concurrent operations in the CRDT, using vector clocks to detect causal branches and implementing smart merge logic that automatically resolves safe conflicts while flagging ambiguous ones for user resolution.

## The Core Challenge

When two users make concurrent subdivisions to a music notation grid, we need to:
1. Apply both operations (CRDT convergence requirement)
2. Detect when operations conflict (overlapping edits, duration violations)
3. Present conflicts to users in an understandable way
4. Preserve both users' intent without silent data loss

## Detecting Concurrent Operations

Vector clocks allow us to determine if two operations are concurrent (neither causally depends on the other):

```rust
impl VectorClock {
    pub fn is_concurrent_with(&self, other: &VectorClock) -> bool {
        // Two clocks are concurrent if neither is ≤ the other
        // This means each has seen events the other hasn't
        match self.partial_cmp(other) {
            None => true,  // Incomparable = concurrent
            Some(Ordering::Equal) => false,
            _ => false,
        }
    }
}
```

**Example:**
```
Alice's clock: {alice: 5, bob: 2}
Bob's clock:   {alice: 3, bob: 6}

Alice has seen 5 of her ops, 2 of Bob's
Bob has seen 3 of Alice's ops, 6 of his own

Neither clock is ≤ the other → Concurrent!
```

## Grouping Operations into Causal Branches

Operations form a directed acyclic graph (DAG) based on causality:

```rust
pub struct Branch {
    pub tip_clock: VectorClock,
    pub ops: Vec<Op>,
}

impl Doc {
    /// Detect causal branches in the operation history
    pub fn detect_branches(&self) -> Vec<Branch> {
        let mut branches: Vec<Branch> = vec![];

        for op in &self.ops {
            // Find branches this op extends (causally after)
            let extends: Vec<usize> = branches.iter()
                .enumerate()
                .filter(|(_, b)| op.clock > b.tip_clock)
                .map(|(i, _)| i)
                .collect();

            match extends.len() {
                0 => {
                    // New concurrent branch
                    branches.push(Branch {
                        tip_clock: op.clock.clone(),
                        ops: vec![op.clone()],
                    });
                }
                1 => {
                    // Extends single branch (linear history)
                    let branch = &mut branches[extends[0]];
                    branch.ops.push(op.clone());
                    branch.tip_clock = op.clock.clone();
                }
                _ => {
                    // Merges multiple branches
                    // This op can see all previous concurrent branches
                    // Could create a new "merge node" in the DAG
                }
            }
        }

        branches
    }
}
```

## Reconstructing Actor Views

Each actor has a causal view of the state at their last operation:

```rust
impl Doc {
    /// Realize the state as a specific actor saw it
    pub fn realize_actor_view(&self, actor_id: &Uuid) -> RealizedDoc {
        let last_op = self.ops.iter()
            .filter(|op| op.clock.get(actor_id) > 0)
            .last();

        if let Some(last_op) = last_op {
            let mut realized = RealizedDoc::default();

            // Apply only operations in this actor's causal past
            for op in &self.ops {
                if op.clock <= last_op.clock {
                    op.apply(&mut realized);
                }
            }

            realized
        } else {
            RealizedDoc::default()
        }
    }
}
```

**Why this works:** Vector clocks define a partial order. If `op.clock <= actor_last_clock`, then the actor had seen (or could have seen) that operation when they made their edit.

## Smart Conflict Detection

Not all concurrent operations conflict! We detect specific problematic patterns:

### 1. Overlapping Subdivisions

```rust
fn detect_overlapping_subdivisions(&self) -> Vec<ConflictDetail> {
    let mut conflicts = vec![];

    for (i, op_a) in self.ops.iter().enumerate() {
        if let OpPayload::Subdivide { deleted_cell_ids: cells_a, .. } = &op_a.payload {
            for op_b in &self.ops[i+1..] {
                if let OpPayload::Subdivide { deleted_cell_ids: cells_b, .. } = &op_b.payload {
                    // Must be concurrent
                    if !op_a.clock.is_concurrent_with(&op_b.clock) {
                        continue;
                    }

                    // Check for overlapping target cells
                    let overlap: Vec<_> = cells_a.iter()
                        .filter(|c| cells_b.contains(c))
                        .cloned()
                        .collect();

                    if !overlap.is_empty() {
                        conflicts.push(ConflictDetail {
                            kind: ConflictKind::OverlappingSubdivision,
                            ops: vec![op_a.id, op_b.id],
                            affected_cells: overlap,
                        });
                    }
                }
            }
        }
    }

    conflicts
}
```

**Example:**
```
Initial: [A, B, C, D]

Alice subdivides [A, B] → concurrent → Both apply
Bob subdivides [B, C]   → concurrent → Duration mismatch!

Cell B is deleted by both operations
Result has extra duration from both new cell sets
```

### 2. Lost Edits (Edit-Delete Conflict)

```rust
fn detect_lost_edits(&self) -> Vec<ConflictDetail> {
    let mut conflicts = vec![];

    for (i, op_a) in self.ops.iter().enumerate() {
        if let OpPayload::SetCellValue { cell_id, .. } = op_a.payload {
            for op_b in &self.ops[i+1..] {
                if let OpPayload::Subdivide { deleted_cell_ids, .. } = &op_b.payload {
                    if op_a.clock.is_concurrent_with(&op_b.clock)
                       && deleted_cell_ids.contains(&cell_id) {
                        conflicts.push(ConflictDetail {
                            kind: ConflictKind::CellValueLostBySubdivision,
                            ops: vec![op_a.id, op_b.id],
                            affected_cells: vec![cell_id],
                        });
                    }
                }
            }
        }
    }

    conflicts
}
```

**Example:**
```
Alice sets cell B value to "C#"  → concurrent
Bob subdivides [B, C]            → concurrent

Alice's edit is "lost" because B is deleted
User should be warned about this
```

### 3. Duration Mismatches

```rust
fn detect_duration_mismatches(&self, realized: &RealizedDoc) -> Vec<ConflictDetail> {
    let mut conflicts = vec![];

    for row in &realized.grid.rows {
        let active_cells: Vec<_> = row.cells.iter()
            .filter(|c| !c.deleted)
            .collect();

        let actual: f64 = active_cells.iter()
            .map(|c| c.duration)
            .sum();

        let expected = row.expected_duration;

        if (actual - expected).abs() > 0.001 {
            // Find which operations affected this row
            let affecting_ops = self.find_ops_affecting_row(row.id);

            conflicts.push(ConflictDetail {
                kind: ConflictKind::DurationMismatch {
                    expected,
                    actual,
                },
                ops: affecting_ops,
                affected_cells: active_cells.iter().map(|c| c.id).collect(),
            });
        }
    }

    conflicts
}
```

## The Smart Merge Algorithm

```rust
pub enum MergeResult {
    Clean(RealizedDoc),
    Conflict {
        branches: Vec<(Uuid, RealizedDoc)>,  // Actor views
        conflicts: Vec<ConflictDetail>,
    },
}

impl Doc {
    pub fn smart_merge(&self) -> MergeResult {
        // Apply all operations (CRDT convergence)
        let mut merged = RealizedDoc::default();
        for op in &self.ops {
            op.apply(&mut merged);
        }

        // Detect conflicts
        let mut conflicts = vec![];
        conflicts.extend(self.detect_overlapping_subdivisions());
        conflicts.extend(self.detect_lost_edits());
        conflicts.extend(self.detect_duration_mismatches(&merged));

        if conflicts.is_empty() {
            // Clean merge - all concurrent ops are compatible
            MergeResult::Clean(merged)
        } else {
            // Reconstruct each actor's view for the merge UI
            let actors = self.get_divergent_actors();
            let actor_views = actors.into_iter()
                .map(|actor_id| (actor_id, self.realize_actor_view(&actor_id)))
                .collect();

            MergeResult::Conflict {
                branches: actor_views,
                conflicts,
            }
        }
    }
}
```

## User Experience

### Auto-Merge (No Conflict)

```
Alice subdivides [A, B]  → Triplets
Bob subdivides [C, D]    → Quintuplets

No overlap, no conflict
Result: [Triplet1, Triplet2, Triplet3, Quintuplet1, ..., Quintuplet5]
Duration preserved ✓
```

### Conflict Detection UI

```
┌──────────────────────────────────────────────────────────┐
│ Merge Conflict: Overlapping Subdivisions                 │
├──────────────────────────────────────────────────────────┤
│                                                           │
│ Alice and Bob edited the same cells concurrently         │
│                                                           │
│ Alice's version (Row 1):                                 │
│ ┌───┬───┬───┬───┐                                        │
│ │T1 │T2 │T3 │ D │  Duration: 1.0 ✓                      │
│ └───┴───┴───┴───┘                                        │
│ Triplets from subdividing [A, B, C]                      │
│                                                           │
│ Bob's version (Row 1):                                   │
│ ┌───┬───┬───┬───┬───┬───┐                               │
│ │ A │Q1 │Q2 │Q3 │Q4 │Q5 │  Duration: 1.0 ✓              │
│ └───┴───┴───┴───┴───┴───┘                               │
│ Quintuplets from subdividing [B, C, D]                   │
│                                                           │
│ Merged result (both applied):                            │
│ ┌───┬───┬───┬───┬───┬───┬───┬───┐                       │
│ │T1 │T2 │T3 │Q1 │Q2 │Q3 │Q4 │Q5 │  Duration: 1.5 ✗      │
│ └───┴───┴───┴───┴───┴───┴───┴───┘                       │
│                                                           │
│ [ Keep Alice's version ]                                 │
│ [ Keep Bob's version   ]                                 │
│ [ Keep both as separate grids ]                          │
│ [ Manually resolve ]                                     │
└──────────────────────────────────────────────────────────┘
```

## Resolution Strategies

### 1. Keep One Version
Create a new operation that:
- Undoes the unwanted changes (marks those cells as deleted)
- Re-applies one actor's version as a new operation
- Preserves causality (new operation depends on both branches)

### 2. Keep Both as Separate Grids
- Fork the grid into two separate grids
- Each preserves one actor's version
- Allows manual copying between grids later

### 3. Manual Resolution
- UI allows editing the merged (invalid) state
- Create operations to fix duration mismatches
- New operations causally depend on all previous ops

## Key Design Properties

1. **No Silent Data Loss** - Both operations always apply; conflicts are explicit
2. **Automatic Safe Merges** - Non-overlapping concurrent edits merge cleanly
3. **Deterministic Convergence** - All replicas converge to same state (including conflicts)
4. **User Control** - Ambiguous cases are presented to users, not arbitrarily resolved
5. **Causal Consistency** - Vector clocks ensure we can reconstruct any actor's view

## Implementation Notes

- Store all operations (even if they create conflicts)
- Conflicts are part of the realized state, not errors
- Resolution creates new operations (not undoing history)
- UI must handle temporary invalid states gracefully
- Consider conflict "severity" (overlapping subdivisions vs. minor duration drift)

## Future Enhancements

- **Operational Transformation** - Automatically adjust positions in some cases
- **Three-way Merge** - Show common ancestor state in conflict UI
- **Conflict Clustering** - Group related conflicts (e.g., same row)
- **Suggested Resolutions** - AI/heuristic-based merge suggestions

## References

- See `crdt-design.md` for overall CRDT architecture
- See `fractional-indexing.md` for position semantics