feat(crdt): wrap sequence items in Entry

1 files changed, 131 insertions, 81 deletions

diff --git a/crdt/src/lib.rs b/crdt/src/lib.rs
index 88133a6..a92b52d 100644
--- a/crdt/src/lib.rs
+++ b/crdt/src/lib.rs
@@ -16,32 +16,32 @@ pub enum Error {
 }
 
 #[derive(Default, Clone)]
-pub struct Doc {
+pub struct State {
     ops: Vec<Op>,
 }
 
-impl Doc {
-    pub fn from_ops(actor_id: &Uuid, payloads: &[OpPayload]) -> Self {
+impl State {
+    pub fn from_ops(actor_id: &Uuid, data: &[OpData]) -> Self {
         let mut clock = VectorClock::new();
 
-        let ops = payloads
+        let ops = data
             .iter()
             .cloned()
-            .map(|payload| {
+            .map(|data| {
                 clock = clock.inc(&actor_id);
 
                 Op {
                     id: Uuid::now_v7(),
                     clock: clock.clone(),
-                    payload,
+                    data,
                 }
             })
             .collect();
 
-        Doc { ops }
+        State { ops }
     }
 
-    pub fn append_op(&mut self, actor_id: &Uuid, payload: OpPayload) {
+    pub fn append_op(&mut self, actor_id: &Uuid, data: OpData) {
         // Increment the last clock for the provided actor
         let clock = self
             .ops
@@ -53,11 +53,11 @@ impl Doc {
         self.ops.push(Op {
             id: Uuid::now_v7(),
             clock,
-            payload,
+            data,
         });
     }
 
-    pub fn merge(&mut self, other: &Doc) {
+    pub fn merge(&mut self, other: &State) {
         let op_ids: BTreeSet<Uuid> = self.ops.iter().map(|op| op.id).collect();
 
         for op in &other.ops {
@@ -74,28 +74,28 @@ impl Doc {
         });
     }
 
-    pub fn realize(&self) -> Result<RealizedDoc, Error> {
-        let mut realized = RealizedDoc::default();
+    pub fn realize(&self) -> Result<Doc, Error> {
+        let mut doc = Doc::default();
 
         for op in &self.ops {
-            op.apply(&mut realized)?;
+            op.apply(&mut doc)?;
         }
 
-        Ok(realized)
+        Ok(doc)
     }
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Op {
     id: Uuid,
-    payload: OpPayload,
     clock: VectorClock,
+    data: OpData,
 }
 
 impl Op {
-    fn apply(&self, realized: &mut RealizedDoc) -> Result<(), Error> {
-        match &self.payload {
-            OpPayload::CreateGrid {
+    fn apply(&self, doc: &mut Doc) -> Result<(), Error> {
+        match &self.data {
+            OpData::CreateGrid {
                 rows,
                 base_cells_per_row,
             } => {
@@ -104,54 +104,59 @@ impl Op {
                 let rows = (0..*rows)
                     .map(|row_idx| {
                         let cells = (0..*base_cells_per_row)
-                            .map(|cell_idx| Cell {
-                                id: self.id.derive_id("cell", cell_idx),
-                                duration,
+                            .map(|cell_idx| {
+                                Entry::active(Cell {
+                                    id: self.id.derive_id("cell", cell_idx),
+                                    duration,
+                                })
                             })
                             .collect();
 
-                        Row {
+                        Entry::active(Row {
                             id: self.id.derive_id("row", row_idx),
                             cells,
-                        }
+                        })
                     })
                     .collect();
 
-                realized.grids.push(Grid {
+                doc.grids.push(Entry::active(Grid {
                     id: self.id.derive_id("grid", 0),
                     rows,
-                });
+                }));
             }
 
-            OpPayload::ChangeSubdivisions {
+            OpData::ChangeSubdivisions {
                 grid_id,
                 row_id,
                 start_cell_id,
                 end_cell_id,
                 subdivisions,
             } => {
-                let grid = realized
+                let grid = doc
                     .grids
                     .iter_mut()
-                    .find(|g| g.id == *grid_id)
+                    .find(|entry| entry.is_active_and(|g| g.id == *grid_id))
                     .ok_or(Error::NotFound(grid_id.clone()))?;
 
                 let row = grid
+                    .value_mut()
                     .rows
                     .iter_mut()
-                    .find(|r| r.id == *row_id)
+                    .find(|entry| entry.is_active_and(|r| r.id == *row_id))
                     .ok_or(Error::NotFound(row_id.clone()))?;
 
                 let start_cell_idx = row
+                    .value()
                     .cells
                     .iter()
-                    .position(|c| c.id == *start_cell_id)
+                    .position(|entry| entry.is_active_and(|c| c.id == *start_cell_id))
                     .ok_or(Error::NotFound(start_cell_id.clone()))?;
 
                 let end_cell_idx = row
+                    .value()
                     .cells
                     .iter()
-                    .position(|c| c.id == *end_cell_id)
+                    .position(|entry| entry.is_active_and(|c| c.id == *end_cell_id))
                     .ok_or(Error::NotFound(end_cell_id.clone()))?;
 
                 let (i, j) = if start_cell_idx <= end_cell_idx {
@@ -160,16 +165,20 @@ impl Op {
                     (end_cell_idx, start_cell_idx)
                 };
 
-                let span_duration: Ratio<u32> =
-                    row.cells[i..j + 1].iter().map(|cell| cell.duration).sum();
+                let span_duration: Ratio<u32> = row.value().cells[i..j + 1]
+                    .iter()
+                    .map(|cell| cell.value().duration)
+                    .sum();
 
                 let duration: Ratio<u32> = span_duration / *subdivisions as u32;
 
-                row.cells.splice(
+                row.value_mut().cells.splice(
                     i..(j + 1),
-                    (0..*subdivisions).map(|subdivision_idx| Cell {
-                        id: self.id.derive_id("cell", subdivision_idx),
-                        duration,
+                    (0..*subdivisions).map(|subdivision_idx| {
+                        Entry::active(Cell {
+                            id: self.id.derive_id("cell", subdivision_idx),
+                            duration,
+                        })
                     }),
                 );
             }
@@ -180,7 +189,7 @@ impl Op {
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum OpPayload {
+pub enum OpData {
     CreateGrid {
         rows: usize,
         base_cells_per_row: usize,
@@ -196,20 +205,53 @@ pub enum OpPayload {
 }
 
 #[derive(Default, Debug)]
-pub struct RealizedDoc {
-    grids: Vec<Grid>,
+pub struct Doc {
+    grids: Vec<Entry<Grid>>,
+}
+
+#[derive(Debug)]
+pub enum Entry<T> {
+    Active { value: T },
+    Deleted { value: T, deleted_by: Uuid },
+}
+
+impl<T> Entry<T> {
+    pub fn active(value: T) -> Self {
+        Self::Active { value }
+    }
+
+    pub fn is_active_and(&self, f: impl FnOnce(&T) -> bool) -> bool {
+        match self {
+            Self::Active { value } => f(value),
+            _ => false,
+        }
+    }
+
+    pub fn value(&self) -> &T {
+        match self {
+            Self::Active { value } => value,
+            Self::Deleted { value, .. } => value,
+        }
+    }
+
+    pub fn value_mut(&mut self) -> &mut T {
+        match self {
+            Self::Active { value } => value,
+            Self::Deleted { value, .. } => value,
+        }
+    }
 }
 
 #[derive(Debug)]
 pub struct Grid {
     id: DerivedId,
-    rows: Vec<Row>,
+    rows: Vec<Entry<Row>>,
 }
 
 #[derive(Debug)]
 pub struct Row {
     id: DerivedId,
-    cells: Vec<Cell>,
+    cells: Vec<Entry<Cell>>,
 }
 
 #[derive(Debug)]
@@ -255,17 +297,17 @@ mod tests {
         let actor1 = Uuid::now_v7();
         let actor2 = Uuid::now_v7();
 
-        let mut doc1 = Doc::from_ops(
+        let mut doc1 = State::from_ops(
             &actor1,
-            &[OpPayload::CreateGrid {
+            &[OpData::CreateGrid {
                 rows: 4,
                 base_cells_per_row: 16,
             }],
         );
 
-        let mut doc2 = Doc::from_ops(
+        let mut doc2 = State::from_ops(
             &actor2,
-            &[OpPayload::CreateGrid {
+            &[OpData::CreateGrid {
                 rows: 4,
                 base_cells_per_row: 16,
             }],
@@ -286,9 +328,9 @@ mod tests {
         let actor1 = Uuid::now_v7();
         let actor2 = Uuid::now_v7();
 
-        let mut doc1 = Doc::from_ops(
+        let mut doc1 = State::from_ops(
             &actor1,
-            &[OpPayload::CreateGrid {
+            &[OpData::CreateGrid {
                 rows: 4,
                 base_cells_per_row: 16,
             }],
@@ -301,22 +343,30 @@ mod tests {
 
             doc1.append_op(
                 &actor1,
-                OpPayload::ChangeSubdivisions {
-                    grid_id: realized.grids[0].id,
-                    row_id: realized.grids[0].rows[0].id,
-                    start_cell_id: realized.grids[0].rows[0].cells[0].id,
-                    end_cell_id: realized.grids[0].rows[0].cells[3].id,
+                OpData::ChangeSubdivisions {
+                    grid_id: realized.grids[0].value().id,
+                    row_id: realized.grids[0].value().rows[0].value().id,
+                    start_cell_id: realized.grids[0].value().rows[0].value().cells[0]
+                        .value()
+                        .id,
+                    end_cell_id: realized.grids[0].value().rows[0].value().cells[3]
+                        .value()
+                        .id,
                     subdivisions: 3,
                 },
             );
 
             doc2.append_op(
                 &actor2,
-                OpPayload::ChangeSubdivisions {
-                    grid_id: realized.grids[0].id,
-                    row_id: realized.grids[0].rows[0].id,
-                    start_cell_id: realized.grids[0].rows[0].cells[0].id,
-                    end_cell_id: realized.grids[0].rows[0].cells[3].id,
+                OpData::ChangeSubdivisions {
+                    grid_id: realized.grids[0].value().id,
+                    row_id: realized.grids[0].value().rows[0].value().id,
+                    start_cell_id: realized.grids[0].value().rows[0].value().cells[0]
+                        .value()
+                        .id,
+                    end_cell_id: realized.grids[0].value().rows[0].value().cells[3]
+                        .value()
+                        .id,
                     subdivisions: 3,
                 },
             );
@@ -337,13 +387,13 @@ mod tests {
 
         let realized = doc1.realize().unwrap();
 
-        let grid = &realized.grids[0];
-        let row = &grid.rows[0];
+        let grid = &realized.grids[0].value();
+        let row = &grid.rows[0].value();
 
         assert_eq!(
             row.cells
                 .iter()
-                .map(|cell| cell.duration)
+                .map(|cell| cell.value().duration)
                 .sum::<Ratio<u32>>(),
             Ratio::ONE
         );
@@ -353,11 +403,11 @@ mod tests {
     fn realize_doc() {
         let actor_id = Uuid::now_v7();
 
-        let mut doc = Doc::default();
+        let mut doc = State::default();
 
         doc.append_op(
             &actor_id,
-            OpPayload::CreateGrid {
+            OpData::CreateGrid {
                 rows: 4,
                 base_cells_per_row: 16,
             },
@@ -368,29 +418,29 @@ mod tests {
 
             assert_eq!(realized.grids.len(), 1);
 
-            let grid = realized.grids.first().unwrap();
+            let grid = realized.grids.first().unwrap().value();
 
             assert_eq!(grid.rows.len(), 4);
 
-            let row = grid.rows.first().unwrap();
+            let row = grid.rows.first().unwrap().value();
 
             assert_eq!(row.cells.len(), 16);
 
             assert_eq!(
                 row.cells
                     .iter()
-                    .map(|cell| cell.duration)
+                    .map(|cell| cell.value().duration)
                     .sum::<Ratio<u32>>(),
                 Ratio::ONE
             );
 
             doc.append_op(
                 &actor_id,
-                OpPayload::ChangeSubdivisions {
+                OpData::ChangeSubdivisions {
                     grid_id: grid.id.clone(),
                     row_id: row.id.clone(),
-                    start_cell_id: row.cells[0].id.clone(),
-                    end_cell_id: row.cells[3].id.clone(),
+                    start_cell_id: row.cells[0].value().id.clone(),
+                    end_cell_id: row.cells[3].value().id.clone(),
                     subdivisions: 3,
                 },
             );
@@ -399,27 +449,27 @@ mod tests {
         {
             let realized = doc.realize().unwrap();
 
-            assert_eq!(realized.grids[0].rows[0].cells.len(), 15);
-            assert_eq!(realized.grids[0].rows[1].cells.len(), 16);
+            assert_eq!(realized.grids[0].value().rows[0].value().cells.len(), 15);
+            assert_eq!(realized.grids[0].value().rows[1].value().cells.len(), 16);
 
-            let grid = &realized.grids[0];
-            let row = &grid.rows[0];
+            let grid = &realized.grids[0].value();
+            let row = &grid.rows[0].value();
 
             assert_eq!(
                 row.cells
                     .iter()
-                    .map(|cell| cell.duration)
+                    .map(|cell| cell.value().duration)
                     .sum::<Ratio<u32>>(),
                 Ratio::ONE
             );
 
             doc.append_op(
                 &actor_id,
-                OpPayload::ChangeSubdivisions {
+                OpData::ChangeSubdivisions {
                     grid_id: grid.id.clone(),
                     row_id: row.id.clone(),
-                    start_cell_id: row.cells[0].id.clone(),
-                    end_cell_id: row.cells.last().unwrap().id.clone(),
+                    start_cell_id: row.cells[0].value().id.clone(),
+                    end_cell_id: row.cells.last().unwrap().value().id.clone(),
                     subdivisions: 12,
                 },
             );
@@ -428,16 +478,16 @@ mod tests {
         {
             let realized = doc.realize().unwrap();
 
-            let grid = &realized.grids[0];
-            let row = &grid.rows[0];
+            let grid = &realized.grids[0].value();
+            let row = &grid.rows[0].value();
 
             assert_eq!(row.cells.len(), 12);
-            assert_eq!(realized.grids[0].rows[1].cells.len(), 16);
+            assert_eq!(realized.grids[0].value().rows[1].value().cells.len(), 16);
 
             assert_eq!(
                 row.cells
                     .iter()
-                    .map(|cell| cell.duration)
+                    .map(|cell| cell.value().duration)
                     .sum::<Ratio<u32>>(),
                 Ratio::ONE
             );