feat(crdt): add crdt crate

6 files changed, 402 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index 6b80039..4bdd91b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,4 +2,6 @@
 **/node_modules/
 
 /.turbo/
-**/.turbo/
\ No newline at end of file
+**/.turbo/
+
+/target/
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..296b0db
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,174 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "bumpalo"
+version = "3.19.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "46c5e41b57b8bba42a04676d81cb89e9ee8e859a1a66f80a5a72e1cb76b34d43"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9330f8b2ff13f34540b44e946ef35111825727b38d33286ef986142615121801"
+
+[[package]]
+name = "getrandom"
+version = "0.3.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "899def5c37c4fd7b2664648c28120ecec138e4d395b459e5ca34f9cce2dd77fd"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "r-efi",
+ "wasip2",
+]
+
+[[package]]
+name = "js-sys"
+version = "0.3.82"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b011eec8cc36da2aab2d5cff675ec18454fad408585853910a202391cf9f8e65"
+dependencies = [
+ "once_cell",
+ "wasm-bindgen",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.177"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2874a2af47a2325c2001a6e6fad9b16a53b802102b528163885171cf92b15976"
+
+[[package]]
+name = "notive-crdt"
+version = "0.1.0"
+dependencies = [
+ "uuid",
+]
+
+[[package]]
+name = "once_cell"
+version = "1.21.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "42f5e15c9953c5e4ccceeb2e7382a716482c34515315f7b03532b8b4e8393d2d"
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.103"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5ee95bc4ef87b8d5ba32e8b7714ccc834865276eab0aed5c9958d00ec45f49e8"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.42"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a338cc41d27e6cc6dce6cefc13a0729dfbb81c262b1f519331575dd80ef3067f"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "r-efi"
+version = "5.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "69cdb34c158ceb288df11e18b4bd39de994f6657d83847bdffdbd7f346754b0f"
+
+[[package]]
+name = "rustversion"
+version = "1.0.22"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b39cdef0fa800fc44525c84ccb54a029961a8215f9619753635a9c0d2538d46d"
+
+[[package]]
+name = "syn"
+version = "2.0.110"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a99801b5bd34ede4cf3fc688c5919368fea4e4814a4664359503e6015b280aea"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.22"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9312f7c4f6ff9069b165498234ce8be658059c6728633667c526e27dc2cf1df5"
+
+[[package]]
+name = "uuid"
+version = "1.18.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2f87b8aa10b915a06587d0dec516c282ff295b475d94abf425d62b57710070a2"
+dependencies = [
+ "getrandom",
+ "js-sys",
+ "wasm-bindgen",
+]
+
+[[package]]
+name = "wasip2"
+version = "1.0.1+wasi-0.2.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0562428422c63773dad2c345a1882263bbf4d65cf3f42e90921f787ef5ad58e7"
+dependencies = [
+ "wit-bindgen",
+]
+
+[[package]]
+name = "wasm-bindgen"
+version = "0.2.105"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "da95793dfc411fbbd93f5be7715b0578ec61fe87cb1a42b12eb625caa5c5ea60"
+dependencies = [
+ "cfg-if",
+ "once_cell",
+ "rustversion",
+ "wasm-bindgen-macro",
+ "wasm-bindgen-shared",
+]
+
+[[package]]
+name = "wasm-bindgen-macro"
+version = "0.2.105"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "04264334509e04a7bf8690f2384ef5265f05143a4bff3889ab7a3269adab59c2"
+dependencies = [
+ "quote",
+ "wasm-bindgen-macro-support",
+]
+
+[[package]]
+name = "wasm-bindgen-macro-support"
+version = "0.2.105"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "420bc339d9f322e562942d52e115d57e950d12d88983a14c79b86859ee6c7ebc"
+dependencies = [
+ "bumpalo",
+ "proc-macro2",
+ "quote",
+ "syn",
+ "wasm-bindgen-shared",
+]
+
+[[package]]
+name = "wasm-bindgen-shared"
+version = "0.2.105"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "76f218a38c84bcb33c25ec7059b07847d465ce0e0a76b995e134a45adcb6af76"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "wit-bindgen"
+version = "0.46.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f17a85883d4e6d00e8a97c586de764dabcc06133f7f1d55dce5cdc070ad7fe59"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..17dba07
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,3 @@
+[workspace]
+resolver = "3"
+members = ["crdt"]
diff --git a/crdt/Cargo.toml b/crdt/Cargo.toml
new file mode 100644
index 0000000..18af1fe
--- /dev/null
+++ b/crdt/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "notive-crdt"
+version = "0.1.0"
+edition = "2024"
+
+[dependencies]
+uuid = { version = "1.18.1", features = ["v7"] }
diff --git a/crdt/src/lib.rs b/crdt/src/lib.rs
new file mode 100644
index 0000000..dcef55c
--- /dev/null
+++ b/crdt/src/lib.rs
@@ -0,0 +1,92 @@
+mod vector_clock;
+
+use uuid::Uuid;
+
+use crate::vector_clock::VectorClock;
+
+pub struct Doc {
+    ops: Vec<Op>,
+}
+
+impl Doc {
+    pub fn new(actor_id: &Uuid) -> Self {
+        Self {
+            ops: vec![Op {
+                id: Uuid::now_v7(),
+                clock: VectorClock::new().inc(actor_id),
+                payload: OpPayload::Init,
+            }],
+        }
+    }
+
+    pub fn append_op(&mut self, payload: OpPayload, actor_id: &Uuid) {
+        let clock = self
+            .ops
+            .last()
+            .expect("doc should have at least an Init op")
+            .clock
+            .inc(actor_id);
+
+        self.ops.push(Op {
+            id: Uuid::now_v7(),
+            clock,
+            payload,
+        });
+    }
+
+    pub fn realize(&self) -> RealizedDoc {
+        let mut realized = RealizedDoc::default();
+        for op in &self.ops {
+            op.apply(&mut realized);
+        }
+        realized
+    }
+}
+
+pub struct Op {
+    id: Uuid,
+    payload: OpPayload,
+    clock: VectorClock,
+}
+
+impl Op {
+    fn apply(&self, realized: &mut RealizedDoc) {
+        match self.payload {
+            OpPayload::Init => {}
+            OpPayload::ChangeSubdivisions { rowId } => {}
+        }
+    }
+}
+
+pub enum OpPayload {
+    Init,
+    ChangeSubdivisions { rowId: Uuid },
+}
+
+pub struct RealizedDoc {
+    grids: Vec<Grid>,
+}
+
+impl Default for RealizedDoc {
+    fn default() -> Self {
+        RealizedDoc {
+            grids: vec![Grid {}],
+        }
+    }
+}
+
+pub struct Grid {}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn realize_doc() {
+        let actor_id = Uuid::now_v7();
+        let doc = Doc::new(&actor_id);
+        let realized = doc.realize();
+
+        assert!(realized.grids.len() == 1);
+    }
+}
diff --git a/crdt/src/vector_clock.rs b/crdt/src/vector_clock.rs
new file mode 100644
index 0000000..e80180f
--- /dev/null
+++ b/crdt/src/vector_clock.rs
@@ -0,0 +1,123 @@
+use std::{
+    cmp::Ordering,
+    collections::{HashMap, HashSet},
+};
+
+use uuid::Uuid;
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+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)
+    }
+}
+
+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) => {
+                let mut actors: Vec<_> = self.0.keys().collect();
+                actors.sort();
+
+                let mut other_actors: Vec<_> = other.0.keys().collect();
+                other_actors.sort();
+
+                Some(actors.cmp(&other_actors))
+            }
+            (true, false) => Some(Ordering::Less),
+            (false, true) => Some(Ordering::Greater),
+            (false, false) => Some(Ordering::Equal),
+        }
+    }
+}
+
+impl Ord for VectorClock {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.partial_cmp(other).unwrap()
+    }
+}
+
+#[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!(bob > alice);
+
+        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!(bob < alice);
+
+        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_b > clock_a);
+    }
+}