Tree

When it comes to utilizing hierarchical data structures and even performing operations across different levels of data, tree structures are of paramount importance. Loro implements the concept of a movable tree CRDT, based on the algorithm created by Kleppmann et al. in A highly-available move operation for replicated trees (opens in a new tab).

In addition to this, Loro further employs Fractional Index (an algorithm used in distributed systems to maintain the order of sequences) to sort each child node, ensuring that sibling nodes maintain an orderly sequence. As a result, Loro can provide APIs such as moveAfter() and moveBefore(). This is particularly useful when a custom-ordered hierarchical view is required.

Node Data

Loro associates a Map (opens in a new tab) with each tree node, serving as a data container for the node, allowing you to nest any data structure supported by Loro.

Note: The associated Map Container is considered a child of the Tree Container within the Loro documentation hierarchy.

You can get the associated map by .data of the LoroTreeNode so you can invoke set or setContainer on the map to add some data or sub-containers to the tree node. For example:

import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
 
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let node: LoroTreeNode = tree.createNode();
node.data.set("key", "value");
node.data.serContainer("list", new LoroList());

Ordered Tree Nodes

In certain scenarios such as graphic design or file systems, where sibling nodes may also require a sequential relationship, we have introduced Fractional Index in Loro to support this capability. You can read more about Fractional Index in the Figma blog (opens in a new tab). In simple terms, Fractional Index assigns a sortable value to each object, and if a new insertion occurs between two objects, the Fractional Index of the new object will be between the left and right values. The rust-based Fractional Index implementation of drifting-in-space (opens in a new tab) has good design and minimal document size growth in most cases. We forked it and made a simple extension for use in Loro.

Whenever a new tree node is created or a node is moved to a new position, Loro will generate a Fractional Index for the node based on its position to sort among sibling nodes. In collaborative environments, conflicts with Fractional Indexes can arise, such as different nodes having the same Fractional Index or the situation where the calculation of a new node's position results in the same Fractional Index on both sides. We will discuss the corresponding conflict resolution methods in detail in a new blog post.

Note: Fractional Index has an interleaving issue, but we believe this is acceptable for tree structures.

Events

There are three types of events in the tree structure: Create, Move, and Delete, as follows:

export type TreeDiffItem =
  | {
      target: TreeID;
      action: "create";
      parent: TreeID | undefined;
      index: number;
      fractionalIndex: string;
    }
  | { target: TreeID; action: "delete" }
  | {
      target: TreeID;
      action: "move";
      parent: TreeID | undefined;
      index: number;
      fractionalIndex: string;
    };

Here, index and fractionalIndex represent the node's index and the hex string representation of the Fractional Index, respectively. Loro will emit events in the order of causality. The deletion event signifies that the target node, along with the entire subtree rooted at the target node, has been deleted. Deletion events for the child nodes are not emitted.

Events of node's data

Since the data of the tree nodes is represented using MapContainer, each MapContainer associated with a tree node is a child of the TreeContainer in the document. If you modify the data of a tree node, you will receive an event from the MapContainer. However, the event path contains a element of TreeID to indicate which node's data has been altered.

Retrieving All Nodes

There are multiple ways to retrieve all nodes from a LoroTree:

nodes(): Retrieves all LoroTreeNode instances from the current LoroTree, but this function does not guarantee the order of the nodes.
roots(): Retrieves all root nodes from the current LoroTree, with the root nodes being ordered. Subsequently, the children() method of LoroTreeNode can be used to perform a hierarchical traversal.

toArray(): Retrieves all node information in a hierarchical traversal order, where each node's data structure is as follows:

{
  id: TreeID;
  parent: TreeID | undefined;
  index: number;
  fractionalIndex: string;
  meta: LoroMap;
}

toJSON(): The JSON representation of toArray(), where each node's meta is also recursively parsed into JSON format.

Basic Usage

Example

import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
 
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move the node to become a child of another node
node2.move(node);
// Specify the child's position within the new parent
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the fractional index of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;

Map Composing CRDTs