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,
            }
        }
    }
}
```

## Implementation Strategy

### Realization with Conflict Detection

When realizing a document:

1. **Apply all operations** - Every op in the log applies, creating cells and tombstones
2. **Detect conflicts** - Find where concurrent ops interfere (overlapping deletions, duration mismatches)
3. **Pick display winner** - Use tie-breaker (op ID, or current viewer's changes) for showing a working state
4. **Mark conflicted regions** - Track which cells/ranges are involved in conflicts
5. **Enable resolution** - User can drill into conflicts to see actor views and choose final version

```rust
pub struct RealizedDoc {
    grids: Vec<Grid>,
    conflicts: Vec<Conflict>,  // Detected conflicts
}

pub struct Conflict {
    kind: ConflictKind,
    affected_cells: Vec<DerivedId>,
    conflicting_ops: Vec<Uuid>,
}

impl Doc {
    pub fn realize(&self) -> RealizedDoc {
        let mut realized = RealizedDoc::default();
        let mut conflicts = vec![];

        // Apply all ops, tracking conflicts
        for op in &self.ops {
            if let Err(conflict) = op.apply(&mut realized) {
                conflicts.push(conflict);
                // Apply arbitrary winner for display
                op.apply_with_tiebreaker(&mut realized);
            }
        }

        realized.conflicts = conflicts;
        realized
    }
}
```

### Arbitrary Winner Selection

When concurrent ops target the same cells, pick a winner for display purposes:

**Strategy 1: Deterministic (Op ID)**
```rust
// Lexicographically larger op ID wins
if op1.id > op2.id {
    // Apply op1's changes
}
```

**Strategy 2: Viewer-based**
```rust
// Current viewer's changes win by default
if op.created_by_actor() == current_viewer {
    // Apply this viewer's changes
} else {
    // Use fallback (op ID)
}
```

This gives each user a familiar view (their changes visible) while still highlighting 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 (Updated)

**Initial View: Conflicted Region Highlighted**

```
Row 1: (Viewing as Alice)
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │⚠️T1│⚠️T2│⚠️T3│   │   │   │  ⚠️ Conflict detected
└───┴───┴───┴───┴───┴───┴───┴───┘
         └─────────┘
         Click to resolve

// Alice's changes are shown by default (viewer-based winner)
// Conflicted cells are highlighted with a warning indicator
```

**Resolution View: Click to See Actor Versions**

```
┌──────────────────────────────────────────────────────────┐
│ Conflict Resolution: Overlapping Subdivisions            │
├──────────────────────────────────────────────────────────┤
│                                                           │
│ Alice and Bob edited cells [B, C, D] concurrently        │
│                                                           │
│ 👤 Alice's version:                                      │
│ ┌───┬───┬───┬───┐                                        │
│ │ A │T1 │T2 │T3 │  (3 triplets from [B,C,D])            │
│ └───┴───┴───┴───┘  Duration: 1.0 ✓                      │
│                                                           │
│ 👤 Bob's version:                                        │
│ ┌───┬───┬───┬───┬───┬───┐                               │
│ │ A │Q1 │Q2 │Q3 │Q4 │Q5 │  (5 quintuplets from [B,C,D]) │
│ └───┴───┴───┴───┴───┴───┘  Duration: 1.0 ✓              │
│                                                           │
│ [✓ Keep Alice's version ]  [ Keep Bob's version ]        │
│                            [ Manually merge     ]        │
└──────────────────────────────────────────────────────────┘
```

**Key UX Properties:**

1. **Always shows working state** - Uses arbitrary winner (viewer's changes by default)
2. **Conflicts are visible** - Highlighted regions indicate resolution needed
3. **Non-intrusive** - User can keep working, resolve conflicts when ready
4. **Context preservation** - Actor views show what each person saw when they edited

## 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 Requirements

### Data Structures

```rust
// Cell with tombstone tracking
pub struct Cell {
    id: DerivedId,
    duration: Ratio<u32>,
    created_by: Uuid,         // Op that created this cell
    deleted_by: Option<Uuid>,  // Op that deleted this cell (if any)
}

// Realized state includes conflicts
pub struct RealizedDoc {
    grids: Vec<Grid>,
    conflicts: Vec<Conflict>,
    deleted_cells: HashMap<DerivedId, Uuid>,  // Quick lookup: cell_id -> deleting_op_id
}

// Conflict representation
pub struct Conflict {
    kind: ConflictKind,
    affected_cells: Vec<DerivedId>,
    conflicting_ops: Vec<Uuid>,
}

pub enum ConflictKind {
    OverlappingSubdivision { op1: Uuid, op2: Uuid },
    DurationMismatch { expected: Ratio<u32>, actual: Ratio<u32> },
    // ... other conflict types
}
```

### Realization Algorithm

```rust
impl Doc {
    pub fn realize(&self) -> RealizedDoc {
        let mut realized = RealizedDoc::default();

        // Step 1: Apply all ops (with tombstones)
        for op in &self.ops {
            op.apply_with_tombstones(&mut realized);
        }

        // Step 2: Detect conflicts
        realized.conflicts = self.detect_conflicts(&realized);

        // Step 3: Apply tie-breaker for display
        // (Viewer-based or deterministic)
        self.apply_conflict_winners(&mut realized);

        realized
    }

    fn detect_conflicts(&self, realized: &RealizedDoc) -> Vec<Conflict> {
        let mut conflicts = vec![];

        // Find overlapping concurrent subdivisions
        for (i, op_a) in self.ops.iter().enumerate() {
            for op_b in &self.ops[i+1..] {
                if op_a.clock.is_concurrent_with(&op_b.clock) {
                    if let Some(conflict) = self.check_subdivision_conflict(op_a, op_b) {
                        conflicts.push(conflict);
                    }
                }
            }
        }

        // Check duration invariants
        for grid in &realized.grids {
            for row in &grid.rows {
                if let Some(conflict) = self.check_duration_conflict(row) {
                    conflicts.push(conflict);
                }
            }
        }

        conflicts
    }
}
```

### Actor View Reconstruction

For conflict resolution UI:

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

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

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

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

    /// Get actor views for all participants in a conflict
    pub fn get_conflict_actor_views(&self, conflict: &Conflict) -> HashMap<Uuid, RealizedDoc> {
        conflict.conflicting_ops.iter()
            .map(|op_id| {
                let op = self.ops.iter().find(|o| o.id == *op_id).unwrap();
                let actor = op.get_actor();
                (actor, self.realize_actor_view(&actor))
            })
            .collect()
    }
}
```

## Implementation Notes

- **Store all operations** - Even if they create conflicts, preserve in log
- **Tombstones enable cascading ops** - Later ops can reference cells created by conflicting ops
- **Conflicts tracked separately** - Not part of cell structure, computed during realize()
- **Resolution creates new ops** - "Choose Alice's version" becomes part of history
- **Viewer-based display** - Each user sees their changes by default, conflicts highlighted
- **Deterministic fallback** - When no viewer context, use op ID for tie-breaking

## 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