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 --- packages/doc/.gitignore | 1 + packages/doc/Cargo.toml | 15 ++++ packages/doc/package.json | 12 +++ packages/doc/src/doc.rs | 114 ++++++++++++++++++++++++++++ packages/doc/src/lib.rs | 97 ++++++++++++++++++++++++ packages/doc/src/op.rs | 21 ++++++ packages/doc/src/vector_clock.rs | 156 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 416 insertions(+) create mode 100644 packages/doc/.gitignore create mode 100644 packages/doc/Cargo.toml create mode 100644 packages/doc/package.json create mode 100644 packages/doc/src/doc.rs create mode 100644 packages/doc/src/lib.rs create mode 100644 packages/doc/src/op.rs create mode 100644 packages/doc/src/vector_clock.rs (limited to 'packages/doc') diff --git a/packages/doc/.gitignore b/packages/doc/.gitignore new file mode 100644 index 0000000..838458f --- /dev/null +++ b/packages/doc/.gitignore @@ -0,0 +1 @@ +/dist/ \ No newline at end of file diff --git a/packages/doc/Cargo.toml b/packages/doc/Cargo.toml new file mode 100644 index 0000000..5e5458d --- /dev/null +++ b/packages/doc/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "notive-doc" +version = "0.1.0" +edition = "2024" + +[lib] +crate-type = ["cdylib"] + +[dependencies] +num-rational = "0.4.2" +serde = { version = "1.0.228", features = ["derive"] } +serde-wasm-bindgen = "0.6.5" +thiserror = "2.0.17" +uuid = { version = "1.18.1", features = ["js", "v7"] } +wasm-bindgen = "0.2.105" diff --git a/packages/doc/package.json b/packages/doc/package.json new file mode 100644 index 0000000..654ef67 --- /dev/null +++ b/packages/doc/package.json @@ -0,0 +1,12 @@ +{ + "name": "@notive/doc", + "private": true, + "main": "dist/notive_doc.js", + "module": true, + "scripts": { + "build": "wasm-pack build --target bundler --release --out-dir dist" + }, + "devDependencies": { + "wasm-pack": "^0.13.1" + } +} diff --git a/packages/doc/src/doc.rs b/packages/doc/src/doc.rs new file mode 100644 index 0000000..fcca1d8 --- /dev/null +++ b/packages/doc/src/doc.rs @@ -0,0 +1,114 @@ +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/packages/doc/src/lib.rs b/packages/doc/src/lib.rs new file mode 100644 index 0000000..a1d7497 --- /dev/null +++ b/packages/doc/src/lib.rs @@ -0,0 +1,97 @@ +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, +} + +#[wasm_bindgen] +impl State { + #[wasm_bindgen(constructor)] + pub fn new() -> Self { + let actor_id = Uuid::now_v7(); + + Self { + actor_id, + ops: vec![], + } + } + + pub fn create_grid(&mut self) { + self.append_op(OpKind::CreateGrid(CreateGrid { + rows: 4, + base_cells_per_row: 16, + })); + } + + pub fn to_json(&self) -> JsValue { + let doc = self.realize().unwrap(); + serde_wasm_bindgen::to_value(&doc).unwrap() + } +} + +impl State { + 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) + } +} + +#[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/packages/doc/src/op.rs b/packages/doc/src/op.rs new file mode 100644 index 0000000..8f5f8b5 --- /dev/null +++ b/packages/doc/src/op.rs @@ -0,0 +1,21 @@ +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/packages/doc/src/vector_clock.rs b/packages/doc/src/vector_clock.rs new file mode 100644 index 0000000..f6ded56 --- /dev/null +++ b/packages/doc/src/vector_clock.rs @@ -0,0 +1,156 @@ +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