Merge pull request #393 from Horusiath/nested-and-roots

Introducing logical collection pointers
y-crdt · Mar 9, 2024 · 1810664 · 1810664
2 parents 5069b56 + 10f3b6d
commit 1810664
Show file tree

Hide file tree

Showing 53 changed files with 7,134 additions and 5,937 deletions.
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/tests-ffi/include/libyrs.h b/tests-ffi/include/libyrs.h
@@ -351,12 +351,12 @@ typedef struct YOptions {
 } YOptions;
 
 /**
- * A Yrs document type. Documents are most important units of collaborative resources management.
+ * A Yrs document type. Documents are the most important units of collaborative resources management.
  * All shared collections live within a scope of their corresponding documents. All updates are
- * generated on per document basis (rather than individual shared type). All operations on shared
+ * generated on per-document basis (rather than individual shared type). All operations on shared
  * collections happen via `YTransaction`, which lifetime is also bound to a document.
  *
- * Document manages so called root types, which are top-level shared types definitions (as opposed
+ * Document manages so-called root types, which are top-level shared types definitions (as opposed
  * to recursively nested types).
  */
 typedef YDoc YDoc;
@@ -971,6 +971,38 @@ typedef struct YUndoEvent {
  */
 typedef StickyIndex YStickyIndex;
 
+typedef union YBranchIdVariant {
+  /**
+   * Clock number timestamp when the creator of a nested shared type created it.
+   */
+  uint32_t clock;
+  /**
+   * Pointer to UTF-8 encoded string representing root-level type name. This pointer is valid
+   * as long as document - in which scope it was created in - was not destroyed. As usually
+   * root-level type names are statically allocated strings, it can also be supplied manually
+   * from the outside.
+   */
+  const uint8_t *name;
+} YBranchIdVariant;
+
+/**
+ * A structure representing logical identifier of a specific shared collection.
+ * Can be obtained by `ybranch_id` executed over alive `Branch`.
+ *
+ * Use `ybranch_get` to resolve a `Branch` pointer from this branch ID.
+ *
+ * This structure doesn't need to be destroyed. It's internal pointer reference is valid through
+ * a lifetime of a document, which collection this branch ID has been created from.
+ */
+typedef struct YBranchId {
+  /**
+   * If positive: Client ID of a creator of a nested shared type, this identifier points to.
+   * If negative: a negated Length of a root-level shared collection name.
+   */
+  int64_t client_or_len;
+  union YBranchIdVariant variant;
+} YBranchId;
+
 /**
  * Returns default ceonfiguration for `YOptions`.
  */
@@ -1114,33 +1146,6 @@ YTransaction *ydoc_read_transaction(YDoc *doc);
  */
 YTransaction *ydoc_write_transaction(YDoc *doc, uint32_t origin_len, const char *origin);
 
-/**
- * Starts a new read-write transaction on a given branches document. All other operations happen in
- * context of a transaction. Yrs transactions do not follow ACID rules. Once a set of operations is
- * complete, a transaction can be finished using `ytransaction_commit` function.
- *
- * Returns `NULL` if read-write transaction couldn't be created, i.e. when another transaction is
- * already opened.
- */
-YTransaction *ybranch_write_transaction(Branch *branch);
-
-/**
- * Starts a new read-only transaction on a given branches document. All other operations happen in
- * context of a transaction. Yrs transactions do not follow ACID rules. Once a set of operations is
- * complete, a transaction can be finished using `ytransaction_commit` function.
- *
- * Returns `NULL` if read-only transaction couldn't be created, i.e. when another read-write
- * transaction is already opened.
- */
-YTransaction *ybranch_read_transaction(Branch *branch);
-
-/**
- * Check if current branch is still alive (returns `Y_TRUE`, otherwise `Y_FALSE`).
- * If it was deleted, this branch pointer is no longer a valid pointer and cannot be used to
- * execute any functions using it.
- */
-uint8_t ytransaction_alive(const YTransaction *txn, Branch *branch);
-
 /**
  * Returns a list of subdocs existing within current document.
  */
@@ -1197,27 +1202,13 @@ Branch *yarray(YDoc *doc,
  */
 Branch *ymap(YDoc *doc, const char *name);
 
-/**
- * Gets or creates a new shared `YXmlElement` data type instance as a root-level type of a given
- * document. This structure can later be accessed using its `name`, which must be a null-terminated
- * UTF-8 compatible string.
- */
-Branch *yxmlelem(YDoc *doc, const char *name);
-
 /**
  * Gets or creates a new shared `YXmlElement` data type instance as a root-level type of a given
  * document. This structure can later be accessed using its `name`, which must be a null-terminated
  * UTF-8 compatible string.
  */
 Branch *yxmlfragment(YDoc *doc, const char *name);
 
-/**
- * Gets or creates a new shared `YXmlText` data type instance as a root-level type of a given
- * document. This structure can later be accessed using its `name`, which must be a null-terminated
- * UTF-8 compatible string.
- */
-Branch *yxmltext(YDoc *doc, const char *name);
-
 /**
  * Returns a state vector of a current transaction's document, serialized using lib0 version 1
  * encoding. Payload created by this function can then be send over the network to a remote peer,
@@ -2453,4 +2444,26 @@ const Weak *yarray_quote(const Branch *array,
                          int8_t start_exclusive,
                          int8_t end_exclusive);
 
+/**
+ * Returns a logical identifier for a given shared collection. That collection must be alive at
+ * the moment of function call.
+ */
+struct YBranchId ybranch_id(const Branch *branch);
+
+/**
+ * Given a logical identifier, returns a physical pointer to a shared collection.
+ * Returns null if collection was not found - either because it was not defined or not synchronized
+ * yet.
+ * Returned pointer may still point to deleted collection. In such case a subsequent `ybranch_alive`
+ * function call is required.
+ */
+Branch *ybranch_get(const struct YBranchId *branch_id, YTransaction *txn);
+
+/**
+ * Check if current branch is still alive (returns `Y_TRUE`, otherwise `Y_FALSE`).
+ * If it was deleted, this branch pointer is no longer a valid pointer and cannot be used to
+ * execute any functions using it.
+ */
+uint8_t ybranch_alive(Branch *branch);
+
 #endif
diff --git a/tests-ffi/main.cpp b/tests-ffi/main.cpp
@@ -271,8 +271,9 @@ TEST_CASE("YMap basic") {
 
 TEST_CASE("YXmlElement basic") {
     YDoc* doc = ydoc_new_with_id(1);
-    Branch* xml = yxmlelem(doc, "test");
+    Branch* frag = yxmlfragment(doc, "test");
     YTransaction* txn = ydoc_write_transaction(doc, 0, NULL);
+    Branch* xml = yxmlelem_insert_elem(frag, txn, 0, "div");
 
     // XML attributes API
     yxmlelem_insert_attr(xml, txn, "key1", "value1");
@@ -326,17 +327,17 @@ TEST_CASE("YXmlElement basic") {
     ystring_destroy(tag);
 
     tag = yxmlelem_tag(xml);
-    REQUIRE(!strcmp(tag, "test"));
+    REQUIRE(!strcmp(tag, "div"));
     ystring_destroy(tag);
 
     // check parents
     Branch* parent = yxmlelem_parent(inner);
     tag = yxmlelem_tag(parent);
-    REQUIRE(!strcmp(tag, "test"));
+    REQUIRE(!strcmp(tag, "div"));
     ystring_destroy(tag);
 
     parent = yxmlelem_parent(xml);
-    REQUIRE(parent == NULL);
+    REQUIRE(parent != NULL);
 
     // check children traversal
     YOutput* curr = yxmlelem_first_child(xml);
@@ -832,8 +833,11 @@ void yxmltext_test_clean(YXmlTextEventTest* t) {
 
 TEST_CASE("YXmlText observe") {
     YDoc* doc = ydoc_new_with_id(1);
-    Branch* txt = yxmltext(doc, "test");
+    Branch* frag = yxmlfragment(doc, "test");
     YTransaction* txn = ydoc_write_transaction(doc, 0, NULL);
+    Branch* txt = yxmlelem_insert_text(frag, txn, 0);
+    ytransaction_commit(txn);
+    txn = ydoc_write_transaction(doc, 0, NULL);
 
     YXmlTextEventTest* t = yxmltext_event_test_new();
     YSubscription* sub = yxmltext_observe(txt, (void*)t, &yxmltext_test_observe);
@@ -842,10 +846,10 @@ TEST_CASE("YXmlText observe") {
     yxmltext_insert(txt, txn, 0, "abcd", NULL);
     ytransaction_commit(txn);
 
-    REQUIRE(t->target != NULL);
     REQUIRE(t->delta_len == 1);
     REQUIRE(t->delta[0].tag == Y_EVENT_CHANGE_ADD);
     REQUIRE(t->delta[0].insert->len == 4);
+    REQUIRE(t->target != NULL);
 
     // remove 2 chars from the middle
     yxmltext_test_clean(t);
@@ -926,8 +930,11 @@ void yxml_test_clean(YXmlEventTest* t) {
 
 TEST_CASE("YXmlElement observe") {
     YDoc* doc = ydoc_new_with_id(1);
-    Branch* xml = yxmlelem(doc, "test");
+    Branch *frag = yxmlfragment(doc, "test");
     YTransaction* txn = ydoc_write_transaction(doc, 0, NULL);
+    Branch* xml = yxmlelem_insert_elem(frag, txn, 0, "div");
+    ytransaction_commit(txn);
+    txn = ydoc_write_transaction(doc, 0, NULL);
 
     YXmlEventTest* t = yxml_event_test_new();
     YSubscription* sub = yxmlelem_observe(xml, (void*)t, &yxml_test_observe);
@@ -1877,6 +1884,57 @@ TEST_CASE("Weak link references") {
 
     yweak_iter_destroy(iter);
 
+    ytransaction_commit(txn);
+    ydoc_destroy(doc);
+}
+
+TEST_CASE("Logical branch pointers") {
+    YDoc *doc = ydoc_new_with_id(1);
+    Branch *arr = yarray(doc, "array");
+    YTransaction *txn = ydoc_write_transaction(doc, 0, NULL);
+
+    // init doc -> 'array' = [{'key':'value'}]
+    char *key = "key";
+    YInput value = yinput_string("value");
+    YInput in = yinput_ymap(&key, &value, 1);
+    yarray_insert_range(arr, txn, 0, &in, 1);
+    YOutput *out = yarray_get(arr, txn, 0);
+    Branch *map = youtput_read_ymap(out);
+    youtput_destroy(out);
+
+    // get branch identifier
+    YBranchId map_id = ybranch_id(map);
+    YBranchId arr_id = ybranch_id(arr);
+
+    // remote changes
+    YDoc *doc2 = ydoc_new_with_id(2);
+    yarray(doc2, "array"); // roots needs to be pre-initialized
+    YTransaction *txn2 = ydoc_write_transaction(doc2, 0, NULL);
+
+    // synchronize the documents
+    uint32_t sv_len = 0;
+    char *sv = ytransaction_state_vector_v1(txn2, &sv_len);
+
+    uint32_t update_len = 0;
+    char *update = ytransaction_state_diff_v1(txn, sv, sv_len, &update_len);
+
+    ytransaction_apply(txn2, update, update_len);
+
+    ybinary_destroy(sv, sv_len);
+    ybinary_destroy(update, update_len);
+
+    // retrieve branch pointers on remote using logical IDs
+    Branch* arr2 = ybranch_get(&arr_id, txn2);
+    Branch* map2 = ybranch_get(&map_id, txn2);
+
+    REQUIRE_EQ(yarray_len(arr2), 1);
+    out = ymap_get(map2, txn2, key);
+    char* val = youtput_read_string(out);
+    REQUIRE(strcmp(val, "value") == 0);
+    youtput_destroy(out);
+
+    ytransaction_commit(txn2);
+    ydoc_destroy(doc2);
     ytransaction_commit(txn);
     ydoc_destroy(doc);
 }
diff --git a/tests-wasm/editing-traces.tests.js b/tests-wasm/editing-traces.tests.js
@@ -8,7 +8,7 @@ import * as zlib from 'zlib'
  * @param {String} filename
  */
 const run = (tc, filename) => {
-    const { startContent, endContent, txns } = JSON.parse(
+    const {startContent, endContent, txns} = JSON.parse(
         filename.endsWith('.gz')
             ? zlib.gunzipSync(fs.readFileSync(filename))
             : fs.readFileSync(filename, 'utf-8')
@@ -20,7 +20,7 @@ const run = (tc, filename) => {
     }
     const start = performance.now()
     for (const {patches} of txns) {
-        let txn = doc.writeTransaction()
+        let txn = doc.beginTransaction()
         for (const [pos, del, chunk] of patches) {
             if (del !== 0) {
                 text.delete(pos, del, txn)
@@ -33,7 +33,7 @@ const run = (tc, filename) => {
         txn.free()
     }
     const end = performance.now()
-    console.log('execution time: ', (end-start), 'milliseconds')
+    console.log('execution time: ', (end - start), 'milliseconds')
 
     const content = text.toString()
     t.compareStrings(content, endContent)

diff --git a/tests-wasm/index.js b/tests-wasm/index.js
@@ -8,10 +8,12 @@ import * as undo from './y-undo.tests.js'
 import * as stickyIndex from './sticky-index.tests.js'
 import * as editingTraces from './editing-traces.tests.js'
 
-import { runTests } from 'lib0/testing'
-import { isBrowser, isNode } from 'lib0/environment'
+import {runTests} from 'lib0/testing'
+import {isBrowser, isNode} from 'lib0/environment'
 import * as log from 'lib0/logging'
+import {setPanicHook} from 'ywasm'
 
+setPanicHook()
 if (isBrowser) {
     log.createVConsole(document.body)
 }

diff --git a/tests-wasm/package.json b/tests-wasm/package.json
@@ -5,6 +5,7 @@
   "description": "Test suite for Yrs Web Assembly package.",
   "main": "index.js",
   "scripts": {
+    "build": "wasm-pack build --target nodejs ../ywasm",
     "test": "node  --experimental-wasm-modules index.js"
   },
   "contributors": [

diff --git a/tests-wasm/testHelper.js b/tests-wasm/testHelper.js
@@ -3,22 +3,22 @@ import * as Y from 'ywasm'
 /**
  * @this {YDoc}
  */
-Y.YDoc.prototype.transact = function(callback, origin) {
-  let txn = this.writeTransaction(origin)
-  try {
-      return callback(txn)
-  } finally {
-      txn.commit()
-      txn.free()
-  }
+Y.YDoc.prototype.transact = function (callback, origin) {
+    let txn = this.beginTransaction(origin)
+    try {
+        return callback(txn)
+    } finally {
+        txn.commit()
+        txn.free()
+    }
 };
 
 /**
  * @param {Array<YDoc>} docs
  */
 export const exchangeUpdates = docs => {
-    for(let d1 of docs) {
-        for(let d2 of docs) {
+    for (let d1 of docs) {
+        for (let d2 of docs) {
             if (d1 !== d2) {
                 let stateVector = Y.encodeStateVector(d1)
                 let diff = Y.encodeStateAsUpdate(d2, stateVector)