diff options
Diffstat (limited to 'docs/design/branch-based-merge.md')
| -rw-r--r-- | docs/design/branch-based-merge.md | 594 |
1 files changed, 0 insertions, 594 deletions
diff --git a/docs/design/branch-based-merge.md b/docs/design/branch-based-merge.md deleted file mode 100644 index 85dc58d..0000000 --- a/docs/design/branch-based-merge.md +++ /dev/null @@ -1,594 +0,0 @@ -# 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 |