diff options
| -rw-r--r-- | crdt/src/lib.rs | 212 |
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 ); |