summaryrefslogtreecommitdiff
path: root/crdt
diff options
context:
space:
mode:
Diffstat (limited to 'crdt')
-rw-r--r--crdt/Cargo.toml15
-rw-r--r--crdt/src/doc.rs114
-rw-r--r--crdt/src/lib.rs99
-rw-r--r--crdt/src/op.rs21
-rw-r--r--crdt/src/vector_clock.rs156
5 files changed, 0 insertions, 405 deletions
diff --git a/crdt/Cargo.toml b/crdt/Cargo.toml
deleted file mode 100644
index 71f745a..0000000
--- a/crdt/Cargo.toml
+++ /dev/null
@@ -1,15 +0,0 @@
-[package]
-name = "notive-crdt"
-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 = ["v7"] }
-wasm-bindgen = "0.2.105"
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<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
- where
- S: serde::Serializer,
- {
- serializer.serialize_str(&self.to_string())
- }
-}
-
-#[derive(Default, Serialize)]
-pub struct Doc {
- pub(crate) grids: Vec<Grid>,
-}
-
-#[derive(Serialize)]
-pub struct Grid {
- pub(crate) id: DerivedId,
- pub(crate) rows: Vec<Row>,
-}
-
-#[derive(Serialize)]
-pub struct Row {
- pub(crate) id: DerivedId,
- pub(crate) cells: Vec<Cell>,
-}
-
-#[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<Op>,
-}
-
-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<Doc, Error> {
- 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<Uuid, u64>);
-
-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<Ordering> {
- let orderings: HashSet<_> = self
- .0
- .keys()
- .chain(other.0.keys())
- .collect::<HashSet<_>>()
- .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));
- }
-}
generated by cgit v1.2.3 (git 2.46.0) at 2025-12-06 09:07:59 +0000