Dexie v4.0.1-beta.14

Support for sync-consistently moving tree structures (via PR #1910)

• New version of dexie-cloud-addon: 4.0.1-beta.58
• New version of dexie: 4.0.1-beta.14
• New export in 'dexie': replacePrefix
• New support for replacePrefix in Dexie Cloud

Background: The parentPath pattern:

One pattern for managing tree structures in a database is to have an indexed property representing the path to the parent node, such as parentPath. This makes it efficient to delete or list all descendants in one query without any need of recursion:

// Add new node
function addNode(childProps, parentId = null) {
  return db.transaction('rw', db.treeNodes, async ()=> {
    const parent = parentId && await db.treeNodes.get(parentId);
    await db.treeNodes.add({
      ...childProps,
      parentPath: parent
        ? `${parent.parentPath}${parent.id}/`
        : '' // If no parent, parentPath will be empty string (added at the root)
    });
  }
}

// List direct children
function listChildren(node) {
  return db.treeNodes.where({parentPath: `${node.parentPath}${node.id}/`}).toArray();
}

// List all descendants without recursion:
function listAllDescendants(node) {
  return db.treeNodes.where('parentPath').startsWith(`${node.parentPath}${node.id}/`).toArray();
}

// Load parent
function loadParent(node) {
  return db.treeNodes.get(node.parentPath.split('/').at(-2));
}

// Load all ancestors
function async loadAllAncestors(node) {
  return (node.parentPath
    ? await db.treeNodes.bulkGet(node.parentPath.substring(0, node.parentPath.length - 1).split('/'))
    : []
  );
}

// Delete the node and all its descendants:
function deleteNode(node) {
  return db.transaction('rw', db.treeNodes, () => {
    db.treeNodes.where('parentPath')
      .startsWith(`${node.parentPath}${node.id}/`)
      .delete();
    db.treeNodes.where({
      parentPath: node.parentPath, // for consistence
      id: node.id
    }).delete();
  });
}

// NOTE:
// Where schema is defined, use a compound index on '[parentPath+id]':
// db.version(x).stores({
//   treeNodes: 'id, [parentPath+id]' // enables where({parentPath: X, id: Y})
// });

All the mutating operations above are also sync consistent: If one offline client adds a child under "/a/b/c" and another offline client modifies all descendants under "/a/b/c" to have a new property {color: "blue"}, the merge of these operation will set {color: "blue"} on the added child also no matter in which order the clients became online. This works due to Dexie Cloud's built-in CRDT capabilities without the user having to use certain types in the objects they are storing.

The new support for moving trees

But modify-operations that use a JS callback does not benefit from sync consistency, only local consistency. Moving an entire tree from one node to another has been one of those operation that need a JS function because the new parentPath's value depends on its existing value. So a tree move has only been possible with local consistency but not sync consistency before:

function moveNode(node, newParentPath) {
  return db.transaction('rw', db.treeNodes, () => {
    // Move node. Having the parentPath criteria here is for consistency:
    // Only perform the 2 moves if parentPath is still the same.
    db.treeNodes.where({
      parentPath: node.parentPath,
      id: node.id
    }).modify({
      parentPath: newParentPath
    });
    // Move all its descendants in relation to their sub path:
    db.treeNodes.where('parentPath').startsWith(`${node.parentPath}${node.id}/`).modify(node => {
      // This is a JS callback that cannot be expressed to the server
      node.parentPath = newParentPath + node.parentPath.substring(node.parentPath.length);
    });
  });
}

JS code cannot securely be sent to the server due to several reasons: closures information missing + the risk of sending code that injects arbitrary code on the server. The operation above won't be sync consistent. If an offline client did add a new node under /a/b/c and that node is moved to /x/y/z, the merging of these operations would not be consistent - a node would still be placed under /a/b/c even though the c node has moved and doesn't exist anymore. So there is a need for declarative ways of doing certain operations, and moving trees is one of them.

A new export replacePrefix now available for this purpose. We will add more of these in coming versions (such as increment, push, deleteArrayItem, etc). replacePrefix is the first "complex" operation that already has support in Dexie Cloud (if upgrading dexie-cloud-addon to 4.0.1-beta.58) and can be executed to perform sync consistent tree moves:

import { replacePrefix } from 'dexie';

// Move subtree with sync consistency:
function moveNode(node, newParentPath) {
  return db.transaction('rw', db.treeNodes, () => {
    // Move node
    db.treeNodes.where({
      parentPath: node.parentPath, // consistency-check
      id: node.id
    }).modify({
      parentPath: newParentPath
    });
    // Move all its descendants in relation to their sub path:
    db.treeNodes
      .where('parentPath')
      .startsWith(`${node.parentPath}${node.id}/`)
      .modify({
        // Here we're in a declarative object - not a JS callback - ==> Consistent operation.
        parentPath: replacePrefix(node.parentPath, newParentPath);
      });
  });
}

This transaction does it all - it moves the node and all its descendants consistently in one atomic all-or-nothing transaction but also preserves the where-condition and the replacePrefix operation in the information to the server so that if an offline client added a node under /a/b/c, and then this operation happened, moving all descendants to the new location, and then the offline client comes online again and syncs, the new node would be placed on the correct new location and be hanging below a non-existing /a/b/c.

Consistency in conflicting move operations

If two operations competes in a move operation involving the same nodes, consistency is maintained by the extra criteria on parentPath in both the move of the parent node and the operation to move its descendants. A move operation will not be performed if another move operation came first. The end result will always be a consistent tree. The last syncer might then experience that the move operation they made got rolled back after a sync and they would instead see the peer's hierarchy.