From 7d912937cc7a271cd4c85fa1108094055ffe730f Mon Sep 17 00:00:00 2001 From: Josh Kingsley Date: Sat, 15 Nov 2025 23:50:55 +0200 Subject: feat(crdt): add duration to Cell --- Cargo.lock | 46 +++++++++++++++++++++++++++ crdt/Cargo.toml | 1 + crdt/src/lib.rs | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++---- 3 files changed, 137 insertions(+), 6 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 4348085..4156a98 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2,6 +2,12 @@ # It is not intended for manual editing. version = 4 +[[package]] +name = "autocfg" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8" + [[package]] name = "bumpalo" version = "3.19.0" @@ -46,10 +52,50 @@ checksum = "2874a2af47a2325c2001a6e6fad9b16a53b802102b528163885171cf92b15976" name = "notive-crdt" version = "0.1.0" dependencies = [ + "num-rational", "thiserror", "uuid", ] +[[package]] +name = "num-bigint" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5e44f723f1133c9deac646763579fdb3ac745e418f2a7af9cd0c431da1f20b9" +dependencies = [ + "num-integer", + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.46" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-rational" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f83d14da390562dca69fc84082e73e548e1ad308d24accdedd2720017cb37824" +dependencies = [ + "num-bigint", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] + [[package]] name = "once_cell" version = "1.21.3" diff --git a/crdt/Cargo.toml b/crdt/Cargo.toml index d96c04f..fe50142 100644 --- a/crdt/Cargo.toml +++ b/crdt/Cargo.toml @@ -4,5 +4,6 @@ version = "0.1.0" edition = "2024" [dependencies] +num-rational = "0.4.2" thiserror = "2.0.17" uuid = { version = "1.18.1", features = ["v7"] } diff --git a/crdt/src/lib.rs b/crdt/src/lib.rs index 3983692..7b426fc 100644 --- a/crdt/src/lib.rs +++ b/crdt/src/lib.rs @@ -2,6 +2,7 @@ mod vector_clock; use std::{collections::BTreeSet, fmt::Display}; +use num_rational::Ratio; use uuid::Uuid; use crate::vector_clock::VectorClock; @@ -93,11 +94,14 @@ impl Op { rows, base_cells_per_row, } => { + let duration: Ratio = Ratio::new(1, *base_cells_per_row as u32); + 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, }) .collect(); @@ -151,10 +155,16 @@ impl Op { (end_cell_idx, start_cell_idx) }; + let span_duration: Ratio = + row.cells[i..j + 1].iter().map(|cell| cell.duration).sum(); + + let duration: Ratio = span_duration / *subdivisions as u32; + row.cells.splice( i..(j + 1), (0..*subdivisions).map(|subdivision_idx| Cell { id: self.id.derive_id("cell", subdivision_idx), + duration, }), ); } @@ -200,9 +210,10 @@ pub struct Row { #[derive(Debug)] pub struct Cell { id: DerivedId, + duration: Ratio, } -#[derive(PartialEq, Eq, Debug, Clone)] +#[derive(PartialEq, Eq, Debug, Clone, Copy)] pub struct DerivedId { // TODO These IDs can be interned on the Doc id: Uuid, @@ -270,13 +281,58 @@ mod tests { let actor1 = Uuid::now_v7(); let actor2 = Uuid::now_v7(); - let doc = Doc::from_ops( + let mut doc1 = Doc::from_ops( &actor1, &[OpPayload::CreateGrid { rows: 4, base_cells_per_row: 16, }], ); + + let mut doc2 = doc1.clone(); + + { + let realized = doc1.realize().unwrap(); + + 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, + 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, + subdivisions: 3, + }, + ); + } + + doc1.merge(&doc2); + + assert_eq!(doc1.ops.len(), 3); + + let realized = doc1.realize().unwrap(); + + let grid = &realized.grids[0]; + let row = &grid.rows[0]; + + assert_eq!( + row.cells + .iter() + .map(|cell| cell.duration) + .sum::>(), + Ratio::ONE + ); } #[test] @@ -296,15 +352,23 @@ mod tests { { let realized = doc.realize().unwrap(); - assert!(realized.grids.len() == 1); + assert_eq!(realized.grids.len(), 1); let grid = realized.grids.first().unwrap(); - assert!(grid.rows.len() == 4); + assert_eq!(grid.rows.len(), 4); let row = grid.rows.first().unwrap(); - assert!(row.cells.len() == 16); + assert_eq!(row.cells.len(), 16); + + assert_eq!( + row.cells + .iter() + .map(|cell| cell.duration) + .sum::>(), + Ratio::ONE + ); doc.append_op( &actor_id, @@ -327,6 +391,14 @@ mod tests { let grid = &realized.grids[0]; let row = &grid.rows[0]; + assert_eq!( + row.cells + .iter() + .map(|cell| cell.duration) + .sum::>(), + Ratio::ONE + ); + doc.append_op( &actor_id, OpPayload::ChangeSubdivisions { @@ -341,8 +413,20 @@ mod tests { { let realized = doc.realize().unwrap(); - assert_eq!(realized.grids[0].rows[0].cells.len(), 12); + + let grid = &realized.grids[0]; + let row = &grid.rows[0]; + + assert_eq!(row.cells.len(), 12); assert_eq!(realized.grids[0].rows[1].cells.len(), 16); + + assert_eq!( + row.cells + .iter() + .map(|cell| cell.duration) + .sum::>(), + Ratio::ONE + ); } } } -- cgit v1.2.3