diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/branch-based-merge.md | 258 |
1 files changed, 233 insertions, 25 deletions
diff --git a/docs/design/branch-based-merge.md b/docs/design/branch-based-merge.md index 331af5f..85dc58d 100644 --- a/docs/design/branch-based-merge.md +++ b/docs/design/branch-based-merge.md @@ -293,6 +293,74 @@ impl Doc { } ``` +## 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) @@ -306,39 +374,53 @@ Result: [Triplet1, Triplet2, Triplet3, Quintuplet1, ..., Quintuplet5] Duration preserved ✓ ``` -### Conflict Detection UI +### 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** ``` ┌──────────────────────────────────────────────────────────┐ -│ Merge Conflict: Overlapping Subdivisions │ +│ Conflict Resolution: Overlapping Subdivisions │ ├──────────────────────────────────────────────────────────┤ │ │ -│ Alice and Bob edited the same cells concurrently │ +│ Alice and Bob edited cells [B, C, D] concurrently │ │ │ -│ Alice's version (Row 1): │ +│ 👤 Alice's version: │ │ ┌───┬───┬───┬───┐ │ -│ │T1 │T2 │T3 │ D │ Duration: 1.0 ✓ │ -│ └───┴───┴───┴───┘ │ -│ Triplets from subdividing [A, B, C] │ +│ │ A │T1 │T2 │T3 │ (3 triplets from [B,C,D]) │ +│ └───┴───┴───┴───┘ Duration: 1.0 ✓ │ │ │ -│ Bob's version (Row 1): │ +│ 👤 Bob's version: │ │ ┌───┬───┬───┬───┬───┬───┐ │ -│ │ A │Q1 │Q2 │Q3 │Q4 │Q5 │ Duration: 1.0 ✓ │ -│ └───┴───┴───┴───┴───┴───┘ │ -│ Quintuplets from subdividing [B, C, D] │ +│ │ A │Q1 │Q2 │Q3 │Q4 │Q5 │ (5 quintuplets from [B,C,D]) │ +│ └───┴───┴───┴───┴───┴───┘ Duration: 1.0 ✓ │ │ │ -│ 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 ] │ +│ [✓ 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 @@ -365,13 +447,139 @@ Create a new operation that: 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) -- 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) +- **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 |