Add lots of documentation and cleanups

y-crdt · Oct 20, 2020 · d7e3037 · d7e3037
1 parent 69db877
commit d7e3037
Show file tree

Hide file tree

Showing 10 changed files with 686 additions and 415 deletions.
diff --git a/README.md b/README.md
@@ -1,9 +1,20 @@
 # Yrs
+
 > Yjs port to Rust (WIP)
 
 Yrs "wires" is a Rust port of the Yjs framework. The [Ywasm](https://github.com/yjs/Ywasm) project generates a wasm library based on this package.
 
-## Run examples
+## Status
+
+> :warning: Highly experimental. Feedback and involvement is welcome!
+
+* Partially implemented the binary encoding protocol. Still need to port the rest of lib0/encoding.
+* Only implements the Text type.
+* No conflict resolution yet.
+
+I'm currently mainly experimenting with designing a convenient API for the Yrs CRDT. I want to make it work very similar to Yjs, but contrary to Yjs you should always know what you get back (proper types, no duck typing).
+
+## Run an example
 
 ```sh
 cargo run --example [example-name]
@@ -15,12 +26,44 @@ cargo run --example [example-name]
 cargo bench
 ```
 
-## Status
+## Run tests & documentation examples
 
-> :warning: Highly experimental. Feedback and involvement is welcome!
+```sh
+cargo test
+```
 
-* Partially implemented the binary encoding protocol. Still need to port the rest of lib0/encoding.
-* Only implements the Text type.
-* No conflict resolution yet.
+## Internal Documentation
 
-I'm currently mainly experimenting with designing a convenient API for the Yrs CRDT. I want to make it work very similar to Yjs, but contrary to Yjs you should always know what you get back (proper types, no duck typing).
+Yrs implements the same algorithm and uses the same data structures as Yjs. We
+hope to achieve better performance because we can manually manage memory.
+Eventually Yrs might replace the Yjs module by generating a wasm module from
+this package.
+
+In this package we want to use better terminology and experiment with new data
+structures to index data. Most CRDTs need to iterate the list structure to find
+an insert position. When the document is large, finding the correct position
+might be very expensive. Yjs uses a form of caching to index list positions. In
+Yrs we want to use skip lists to index positions (e.g.
+[skiplistrs](https://github.com/josephg/skiplistrs)).
+
+In Yjs we use the term *Struct* to refer to the building blocks of which Yjs
+types are composed. In some CRDTs, the term operation is prefered. In Yjs the
+document is composed out of the operations objects. Since operations usually
+represent a change on a document, the term seems inapproriate in implementations
+of Yjs. Now the term **Struct** is ambigious in the Rust language because 
+*"struct* is a keyword and is used in a different context.
+
+Each change on the document generates a small piece of information that is
+integrated into the document. In Yrs we call these small pieces **blocks**.
+Thinks of them as small Lego blocks that compose your document. Each block is
+uniquely identified by an identifier. When you receive a duplicate block, you
+discard it. In some cases blocks can be put together to form a larger block. If
+necessary, blocks can be disassembled if only a part of the composed block is needed.
+
+More information on the implemented algorithm can be found here:
+
+* [Paper describing the YATA conflict resolution algorithm](https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types)
+* [Short overview of the Yjs optimizations](https://github.com/yjs/yjs/blob/main/README.md#yjs-crdt-algorithm)
+* [Motivation for composable blocks](https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/)
+* [Internal documentation of the Yjs project](https://github.com/yjs/yjs/blob/main/INTERNALS.md)
+* [Walkthrough of the Yjs codebase](https://youtu.be/0l5XgnQ6rB4)
diff --git a/benches/benches.rs b/benches/benches.rs
@@ -3,14 +3,22 @@ use yrs::*;
 
 const ITERATIONS: u32 = 1000000;
 
-fn ytext_insert() {
+fn ytext_prepend() {
     let doc = Doc::new();
-    // let tr = doc.transact();
+    let tr = doc.transact();
     let t = doc.get_type("");
     for _ in 0..ITERATIONS {
-        t.insert(0, 'a')
+        t.insert(&tr, 0, 'a')
+    }
+}
+
+fn ytext_append() {
+    let doc = Doc::new();
+    let tr = doc.transact();
+    let t = doc.get_type("");
+    for i in 0..6000 {
+        t.insert(&tr, i, 'a')
     }
-    // tr.end();
 }
 
 const MULT_STRUCT_SIZE: u32 = 7;
@@ -30,7 +38,8 @@ fn gen_vec_perf_pred_optimal () {
 }
 
 fn criterion_benchmark(c: &mut Criterion) {
-    c.bench_function("ytext insert", |b| b.iter(|| ytext_insert()));
+    c.bench_function("ytext insert", |b| b.iter(|| ytext_prepend()));
+    c.bench_function("ytext insert", |b| b.iter(|| ytext_append()));
     c.bench_function("gen vec perf optimal", |b| b.iter(|| gen_vec_perf_optimal()));
     c.bench_function("gen vec perf pred optimal", |b| b.iter(|| gen_vec_perf_pred_optimal()));
 }

diff --git a/examples/custom_provider.rs b/examples/custom_provider.rs
@@ -0,0 +1,34 @@
+use std::rc::Rc;
+
+struct MyProvider {
+    doc: yrs::Doc
+}
+
+impl yrs::Subscriber<yrs::events::UpdateEvent> for MyProvider {
+    fn on_change (&self, event: yrs::events::UpdateEvent) {
+        self.doc.apply_update(&event.update);
+    }
+}
+
+fn main () {
+    let doc1 = yrs::Doc::new();
+    let doc2 = yrs::Doc::new();
+
+    // register update observer
+    let provider = Rc::from(MyProvider {
+        doc: doc2.clone()
+    });
+    doc1.on_update(Rc::downgrade(&provider));
+
+    let my_type = doc1.get_type("my first shared type");
+
+    {
+        // All changes must happen within a transaction. 
+        // When the transaction is dropped, the yrs::Doc fires event (e.g. the update event)
+        let tr = doc1.transact();
+        my_type.insert(&tr, 0, 'a');
+    } // transaction is dropped and changes are automatically synced to doc2
+
+    println!("synced document state: {}", doc2.get_type("my first shared type").to_string());
+    assert_eq!(doc2.get_type("my first shared type").to_string(), "a");
+}
diff --git a/examples/example.rs b/examples/example.rs
@@ -11,8 +11,8 @@ struct YProvider {
     doc: Rc<Doc>
 }
 
-impl Observable<UpdateEvent> for YProvider {
-    fn on_change (&self, event: UpdateEvent) {
+impl Subscriber<events::UpdateEvent> for YProvider {
+    fn on_change (&self, event: events::UpdateEvent) {
         self.doc.apply_update(&event.update[..])
     }
 }
@@ -28,9 +28,9 @@ fn main () {
     {
         // scope the transaction so that it is droped and the update is synced
         // to doc_synced
-        t.insert(0, 'x');
-        for i in 1..ITERATIONS {
-            t.insert(i, 'a')
+        t.insert(&doc1.transact(), 0, 'x');
+        for _ in 0..ITERATIONS {
+            t.insert(&doc1.transact(), 0, 'a')
         }
     }
     println!("doc1 content {}", t.to_string());

diff --git a/src/block.rs b/src/block.rs
@@ -7,15 +7,15 @@ pub struct ID {
 }
 
 #[derive(Copy, Clone)]
-pub struct StructPtr {
+pub struct BlockPtr {
     pub id: ID,
     pub pivot: u32
 }
 
 pub struct Item {
     pub id: ID,
-    pub left: Option<StructPtr>,
-    pub right: Option<StructPtr>,
+    pub left: Option<BlockPtr>,
+    pub right: Option<BlockPtr>,
     pub origin: Option<ID>,
     pub right_origin: Option<ID>,
     pub content: char,
@@ -29,22 +29,22 @@ impl Item {
         // We only implement the reconnection part:
         if let Some(right_id) = self.right {
             let right = doc.ss.get_item_mut(&right_id);
-            right.left = Some(StructPtr {
+            right.left = Some(BlockPtr {
                 pivot,
                 id: self.id
             });
         }
         match self.left {
             Some(left_id) => {
                 let left = doc.ss.get_item_mut(&left_id);
-                left.right = Some(StructPtr {
+                left.right = Some(BlockPtr {
                     pivot,
                     id: self.id
                 });
             }
             None => {
                 let parent_type = doc.get_type_from_ptr(&self.parent);
-                parent_type.start.set(Some(StructPtr {
+                parent_type.start.set(Some(BlockPtr {
                     pivot,
                     id: self.id
                 }));
@@ -56,5 +56,5 @@ impl Item {
 #[derive(Copy, Clone)]
 pub struct ItemPosition <'a> {
     pub parent: &'a Type,
-    pub after: Option<StructPtr>
+    pub after: Option<BlockPtr>
 }