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, LoroList } 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.setContainer("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 allLoroTreeNode
instances from the currentLoroTree
, but this function does not guarantee the order of the nodes. -
roots()
: Retrieves all root nodes from the currentLoroTree
, with the root nodes being ordered. Subsequently, thechildren()
method ofLoroTreeNode
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 oftoArray()
, where each node'smeta
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
node.move(node2);
// 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;