From 602145c956bb594ca0d0e10601cc4ad1a71cf70d Mon Sep 17 00:00:00 2001 From: Josh Kingsley Date: Sun, 23 Nov 2025 19:27:57 +0200 Subject: feat: integrate web and doc packages --- crdt/src/doc.rs | 114 ---------------------------------- crdt/src/lib.rs | 99 ------------------------------ crdt/src/op.rs | 21 ------- crdt/src/vector_clock.rs | 156 ----------------------------------------------- 4 files changed, 390 deletions(-) delete mode 100644 crdt/src/doc.rs delete mode 100644 crdt/src/lib.rs delete mode 100644 crdt/src/op.rs delete mode 100644 crdt/src/vector_clock.rs (limited to 'crdt/src') diff --git a/crdt/src/doc.rs b/crdt/src/doc.rs deleted file mode 100644 index fcca1d8..0000000 --- a/crdt/src/doc.rs +++ /dev/null @@ -1,114 +0,0 @@ -use serde::{Deserialize, Serialize}; -use thiserror::Error; -use uuid::Uuid; - -use crate::op::{ChangeSubdivisions, CreateGrid, Op, OpKind}; - -/// An deterministically derived ID, e.g. a grid ID derived from the -/// op ID which creates it. -pub struct DerivedId { - base: String, - tag: &'static str, - index: usize, -} - -impl ToString for DerivedId { - fn to_string(&self) -> String { - format!("{}:{}={}", self.base, self.tag, self.index) - } -} - -trait DerivableId { - fn derive_id(&self, tag: &'static str, index: usize) -> DerivedId; -} - -impl DerivableId for Uuid { - fn derive_id(&self, tag: &'static str, index: usize) -> DerivedId { - DerivedId { - base: self.to_string(), - tag, - index, - } - } -} - -impl DerivableId for DerivedId { - fn derive_id(&self, tag: &'static str, index: usize) -> DerivedId { - DerivedId { - base: self.to_string(), - tag, - index, - } - } -} - -impl Serialize for DerivedId { - fn serialize(&self, serializer: S) -> Result - where - S: serde::Serializer, - { - serializer.serialize_str(&self.to_string()) - } -} - -#[derive(Default, Serialize)] -pub struct Doc { - pub(crate) grids: Vec, -} - -#[derive(Serialize)] -pub struct Grid { - pub(crate) id: DerivedId, - pub(crate) rows: Vec, -} - -#[derive(Serialize)] -pub struct Row { - pub(crate) id: DerivedId, - pub(crate) cells: Vec, -} - -#[derive(Serialize)] -pub struct Cell { - pub(crate) id: DerivedId, -} - -#[derive(Error, Debug)] -pub enum ApplyOpError {} - -pub type ApplyOpResult = Result<(), ApplyOpError>; - -impl Doc { - pub fn apply_op(&mut self, op: &Op) -> ApplyOpResult { - match &op.kind { - OpKind::CreateGrid(data) => apply_create_grid(self, &op.id, data), - OpKind::ChangeSubdivisions(data) => apply_change_subdivisions(self, data), - } - } -} - -fn apply_create_grid(doc: &mut Doc, op_id: &Uuid, data: &CreateGrid) -> ApplyOpResult { - let grid_id = op_id.derive_id("grid", 0); - - let rows = (0..data.rows) - .map(|row_idx| { - let row_id = grid_id.derive_id("row", row_idx); - - let cells = (0..data.base_cells_per_row) - .map(|cell_idx| Cell { - id: row_id.derive_id("cell", cell_idx), - }) - .collect(); - - Row { id: row_id, cells } - }) - .collect(); - - doc.grids.push(Grid { id: grid_id, rows }); - - Ok(()) -} - -fn apply_change_subdivisions(doc: &mut Doc, data: &ChangeSubdivisions) -> ApplyOpResult { - todo!() -} diff --git a/crdt/src/lib.rs b/crdt/src/lib.rs deleted file mode 100644 index 3c89ce9..0000000 --- a/crdt/src/lib.rs +++ /dev/null @@ -1,99 +0,0 @@ -use thiserror::Error; -use uuid::Uuid; -use wasm_bindgen::prelude::*; - -use crate::{ - doc::{ApplyOpError, Doc}, - op::{CreateGrid, Op, OpKind}, - vector_clock::VectorClock, -}; - -mod doc; -mod op; -mod vector_clock; - -#[derive(Error, Debug)] -pub enum Error { - #[error("error while realizing state")] - RealizeError(#[from] ApplyOpError), -} - -#[wasm_bindgen] -pub struct State { - actor_id: Uuid, - ops: Vec, -} - -impl State { - pub fn new() -> Self { - let actor_id = Uuid::now_v7(); - - Self { - actor_id, - ops: vec![], - } - } - - pub fn append_op(&mut self, kind: OpKind) { - let clock = self - .ops - .last() - .map(|op| op.clock.inc(&self.actor_id)) - .unwrap_or_else(|| VectorClock::new().inc(&self.actor_id)); - - self.ops.push(Op { - id: Uuid::now_v7(), - clock, - kind, - }); - } - - pub fn realize(&self) -> Result { - let mut doc = Doc::default(); - - for op in &self.ops { - doc.apply_op(op)?; - } - - Ok(doc) - } -} - -#[wasm_bindgen] -pub fn make_state() -> State { - State::new() -} - -#[wasm_bindgen] -pub fn create_grid(state: &mut State) { - state.append_op(OpKind::CreateGrid(CreateGrid { - rows: 4, - base_cells_per_row: 16 - })); -} - -pub fn realize(state: &State) -> JsValue { - let doc = state.realize().unwrap(); - serde_wasm_bindgen::to_value(&doc).unwrap() -} - -#[cfg(test)] -mod tests { - use crate::op::CreateGrid; - - use super::*; - - #[test] - fn test() { - let mut state = State::new(); - - state.append_op(OpKind::CreateGrid(CreateGrid { - rows: 4, - base_cells_per_row: 16, - })); - - let doc = state.realize().unwrap(); - let grid = doc.grids.first().unwrap(); - assert_eq!(grid.rows.len(), 4); - } -} diff --git a/crdt/src/op.rs b/crdt/src/op.rs deleted file mode 100644 index 8f5f8b5..0000000 --- a/crdt/src/op.rs +++ /dev/null @@ -1,21 +0,0 @@ -use uuid::Uuid; - -use crate::vector_clock::VectorClock; - -pub struct Op { - pub(crate) id: Uuid, - pub(crate) clock: VectorClock, - pub(crate) kind: OpKind, -} - -pub enum OpKind { - CreateGrid(CreateGrid), - ChangeSubdivisions(ChangeSubdivisions), -} - -pub struct CreateGrid { - pub(crate) rows: usize, - pub(crate) base_cells_per_row: usize, -} - -pub struct ChangeSubdivisions {} diff --git a/crdt/src/vector_clock.rs b/crdt/src/vector_clock.rs deleted file mode 100644 index f6ded56..0000000 --- a/crdt/src/vector_clock.rs +++ /dev/null @@ -1,156 +0,0 @@ -use std::{ - cmp::Ordering, - collections::{HashMap, HashSet}, -}; - -use uuid::Uuid; - -#[derive(Debug, Clone, PartialEq, Eq, Default)] -pub struct VectorClock(HashMap); - -impl VectorClock { - pub fn new() -> Self { - Self(HashMap::new()) - } - - pub fn get(&self, actor_id: &Uuid) -> u64 { - self.0.get(actor_id).unwrap_or(&0).clone() - } - - pub fn inc(&self, actor_id: &Uuid) -> Self { - let mut m = self.0.clone(); - m.insert(actor_id.clone(), self.get(actor_id) + 1); - VectorClock(m) - } - - /// Returns true if this clock is concurrent with another (neither happens before the other) - pub fn is_concurrent_with(&self, other: &VectorClock) -> bool { - self.partial_cmp(other).is_none() - } -} - -impl PartialOrd for VectorClock { - fn partial_cmp(&self, other: &Self) -> Option { - let orderings: HashSet<_> = self - .0 - .keys() - .chain(other.0.keys()) - .collect::>() - .into_iter() - .map(|actor_id| self.get(actor_id).cmp(&other.get(actor_id))) - .collect(); - - let less = orderings.contains(&Ordering::Less); - let greater = orderings.contains(&Ordering::Greater); - - match (less, greater) { - (true, true) => None, - (true, false) => Some(Ordering::Less), - (false, true) => Some(Ordering::Greater), - (false, false) => Some(Ordering::Equal), - } - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn vector_clock_compare() { - let alice_id = Uuid::now_v7(); - let bob_id = Uuid::now_v7(); - let carol_id = Uuid::now_v7(); - - assert!(alice_id < bob_id); - assert!(bob_id < carol_id); - - let mut alice = VectorClock::new(); - let mut bob = VectorClock::new(); - - assert!(alice == bob); - assert!(bob == alice); - - bob = bob.inc(&bob_id); - - assert!(alice < bob); - assert!(bob > alice); - - alice = alice.inc(&alice_id); - - assert!(!(alice < bob)); - assert!(!(alice > bob)); - - alice = alice.inc(&bob_id); - bob = bob.inc(&alice_id); - - assert!(alice == bob); - - alice = alice.inc(&alice_id); - - assert!(alice > bob); - assert!(bob < alice); - - bob = bob.inc(&alice_id); - - assert!(alice == bob); - - alice = alice.inc(&carol_id); - - assert!(alice > bob); - assert!(bob < alice); - - bob = bob.inc(&bob_id); - - assert!(!(alice > bob)); - assert!(!(alice < bob)); - - let clock_a = VectorClock::new().inc(&alice_id).inc(&carol_id); - let clock_b = VectorClock::new().inc(&bob_id).inc(&carol_id); - - assert!(!(clock_a > clock_b)); - assert!(!(clock_a < clock_b)); - } - - #[test] - fn concurrent_clocks() { - let alice_id = Uuid::now_v7(); - let bob_id = Uuid::now_v7(); - let carol_id = Uuid::now_v7(); - - // Equal clocks are not concurrent - let clock1 = VectorClock::new(); - let clock2 = VectorClock::new(); - assert!(!clock1.is_concurrent_with(&clock2)); - - // Causally ordered clocks are not concurrent - let clock_before = VectorClock::new().inc(&alice_id); - let clock_after = VectorClock::new().inc(&alice_id).inc(&bob_id); - assert!(!clock_before.is_concurrent_with(&clock_after)); - assert!(!clock_after.is_concurrent_with(&clock_before)); - - // Clocks from different actors are concurrent - let alice_clock = VectorClock::new().inc(&alice_id); - let bob_clock = VectorClock::new().inc(&bob_id); - assert!(alice_clock.is_concurrent_with(&bob_clock)); - assert!(bob_clock.is_concurrent_with(&alice_clock)); - - // Complex concurrent case: diverged branches - let clock_a = VectorClock::new() - .inc(&alice_id) - .inc(&alice_id) - .inc(&bob_id) - .inc(&carol_id); - - let clock_b = VectorClock::new() - .inc(&alice_id) - .inc(&alice_id) - .inc(&bob_id) - .inc(&bob_id); - - // clock_a: {alice: 2, bob: 1, carol: 1} - // clock_b: {alice: 2, bob: 2} - // carol: 1 > 0, but bob: 1 < 2 → concurrent - assert!(clock_a.is_concurrent_with(&clock_b)); - } -} -- cgit v1.2.3