From 5447ffaf2f8f94cea5ad634472da1515172525e6 Mon Sep 17 00:00:00 2001 From: Josh Kingsley Date: Fri, 14 Nov 2025 00:06:56 +0200 Subject: feat(crdt): implement ChangeSubdivisions op --- Cargo.lock | 21 +++++++++++ crdt/Cargo.toml | 1 + crdt/src/lib.rs | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 3 files changed, 122 insertions(+), 6 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 296b0db..4348085 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -46,6 +46,7 @@ checksum = "2874a2af47a2325c2001a6e6fad9b16a53b802102b528163885171cf92b15976" name = "notive-crdt" version = "0.1.0" dependencies = [ + "thiserror", "uuid", ] @@ -96,6 +97,26 @@ dependencies = [ "unicode-ident", ] +[[package]] +name = "thiserror" +version = "2.0.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f63587ca0f12b72a0600bcba1d40081f830876000bb46dd2337a3051618f4fc8" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "2.0.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3ff15c8ecd7de3849db632e14d18d2571fa09dfc5ed93479bc4485c7a517c913" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + [[package]] name = "unicode-ident" version = "1.0.22" diff --git a/crdt/Cargo.toml b/crdt/Cargo.toml index 18af1fe..d96c04f 100644 --- a/crdt/Cargo.toml +++ b/crdt/Cargo.toml @@ -4,4 +4,5 @@ version = "0.1.0" edition = "2024" [dependencies] +thiserror = "2.0.17" uuid = { version = "1.18.1", features = ["v7"] } diff --git a/crdt/src/lib.rs b/crdt/src/lib.rs index 4c41dd0..c0214b3 100644 --- a/crdt/src/lib.rs +++ b/crdt/src/lib.rs @@ -1,9 +1,19 @@ mod vector_clock; +use std::fmt::Display; + use uuid::Uuid; use crate::vector_clock::VectorClock; +use thiserror::Error; + +#[derive(Error, Debug)] +pub enum Error { + #[error("object with ID {0} not found")] + NotFound(DerivedId), +} + #[derive(Default)] pub struct Doc { ops: Vec, @@ -26,17 +36,18 @@ impl Doc { }); } - pub fn realize(&self) -> RealizedDoc { + pub fn realize(&self) -> Result { let mut realized = RealizedDoc::default(); for op in &self.ops { - op.apply(&mut realized); + op.apply(&mut realized)?; } - realized + Ok(realized) } } +#[derive(Debug)] pub struct Op { id: Uuid, payload: OpPayload, @@ -44,7 +55,7 @@ pub struct Op { } impl Op { - fn apply(&self, realized: &mut RealizedDoc) { + fn apply(&self, realized: &mut RealizedDoc) -> Result<(), Error> { match &self.payload { OpPayload::CreateGrid { rows, @@ -70,42 +81,109 @@ impl Op { rows, }); } + + OpPayload::ChangeSubdivisions { + grid_id, + row_id, + start_cell_id, + end_cell_id, + subdivisions, + } => { + let grid = realized + .grids + .iter_mut() + .find(|g| g.id == *grid_id) + .ok_or(Error::NotFound(grid_id.clone()))?; + + let row = grid + .rows + .iter_mut() + .find(|r| r.id == *row_id) + .ok_or(Error::NotFound(row_id.clone()))?; + + let start_cell_idx = row + .cells + .iter() + .position(|c| c.id == *start_cell_id) + .ok_or(Error::NotFound(start_cell_id.clone()))?; + + let end_cell_idx = row + .cells + .iter() + .position(|c| c.id == *end_cell_id) + .ok_or(Error::NotFound(end_cell_id.clone()))?; + + let (i, j) = if start_cell_idx <= end_cell_idx { + (start_cell_idx, end_cell_idx) + } else { + (end_cell_idx, start_cell_idx) + }; + + row.cells.splice( + i..(j + 1), + (0..*subdivisions).map(|subdivision_idx| Cell { + id: self.id.derive_id("cell", subdivision_idx), + }), + ); + } } + + Ok(()) } } +#[derive(Debug)] pub enum OpPayload { CreateGrid { rows: usize, base_cells_per_row: usize, }, + + ChangeSubdivisions { + grid_id: DerivedId, + row_id: DerivedId, + start_cell_id: DerivedId, + end_cell_id: DerivedId, + subdivisions: usize, + }, } -#[derive(Default)] +#[derive(Default, Debug)] pub struct RealizedDoc { grids: Vec, } +#[derive(Debug)] pub struct Grid { id: DerivedId, rows: Vec, } +#[derive(Debug)] pub struct Row { id: DerivedId, cells: Vec, } +#[derive(Debug)] pub struct Cell { id: DerivedId, } +#[derive(PartialEq, Eq, Debug, Clone)] pub struct DerivedId { + // TODO These IDs can be interned on the Doc id: Uuid, tag: &'static str, index: usize, } +impl Display for DerivedId { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}:{}:{}", self.id, self.tag, self.index) + } +} + trait DerivableId { fn derive_id(&self, tag: &'static str, index: usize) -> DerivedId; } @@ -138,7 +216,7 @@ mod tests { }, ); - let realized = doc.realize(); + let realized = doc.realize().unwrap(); assert!(realized.grids.len() == 1); @@ -149,5 +227,21 @@ mod tests { let row = grid.rows.first().unwrap(); assert!(row.cells.len() == 16); + + doc.append_op( + &actor_id, + OpPayload::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(), + subdivisions: 3, + }, + ); + + let realized2 = doc.realize().unwrap(); + + assert_eq!(realized2.grids[0].rows[0].cells.len(), 15); + assert_eq!(realized2.grids[0].rows[1].cells.len(), 16); } } -- cgit v1.2.3