List and Movable List
Loro supports two types of lists: List and MovableList. The List is a
standard list that supports Insert and Delete operations. In contrast, the
MovableList supports additional Set and Move operations.
Using a combination of insert and delete operations, one can simulate set and
move operations on a List. However, this approach fails in concurrent editing
scenarios. For example, if the same element is set or moved concurrently, the
simulation would result in the deletion of the original element and the
insertion of two new elements, which does not meet expectations.
The MovableList addresses these issues by ensuring that set and move
operations do not lead to such problems, though it incurs additional overheads.
Specifically, when performing only insertions/deletions, the MovableList is
approximately 80% slower in encode/decode and consumes about 50% more memory
compared to the List.
Both List and MovableList utilize the
Fugue to achieve maximal
non-interleaving. Additionally, MovableList uses the algorithm from
Moving Elements in List CRDTs
to implement the move operation.
Basic Usage
List
const = new ();
.("1");
const = .("list");
.(0);
.(1);
.(2);
const : = .({ : "snapshot" });
const = .();
.("2");
const = .("list");
{
// Concurrently docA and docB update element at index 2
// docA updates it to 8
// docB updates it to 9
// docA.toJSON() should return { list: [0, 1, 8] }
// docB.toJSON() should return { list: [0, 1, 9] }
.(2, 1);
.(2, 9);
(.()).({ : [0, 1, 9] });
.(2, 1);
.(2, 8);
(.()).({ : [0, 1, 8] });
}
{
// Merge docA and docB
.(.({ : "update", : .() }));
.(.({ : "update", : .() }));
}
(.()).({ : [0, 1, 8, 9] });
(.()).({ : [0, 1, 8, 9] });MovableList
const = new ();
.("1");
const = .("list");
.(0);
.(1);
.(2);
const : = .({ : "snapshot" });
const = .();
.("2");
const = .("list");
{
// Concurrently docA and docB update element at index 2
// docA updates it to 8
// docB updates it to 9
// docA.toJSON() should return { list: [0, 1, 8] }
// docB.toJSON() should return { list: [0, 1, 9] }
.(2, 8);
(.()).({ : [0, 1, 8] });
.(2, 9);
(.()).({ : [0, 1, 9] });
}
{
// Merge docA and docB
.(.({ : "update", : .() }));
.(.({ : "update", : .() }));
}
// Converge to [0, 1, 9] because docB has larger peerId thus larger logical time
(.()).({ : [0, 1, 9] });
(.()).({ : [0, 1, 9] });
{
// Concurrently docA and docB move element at index 0
// docA moves it to 2
// docB moves it to 1
// docA.toJSON() should return { list: [1, 9, 0] }
// docB.toJSON() should return { list: [1, 0, 9] }
.(0, 2);
.(0, 1);
(.()).({ : [1, 9, 0] });
(.()).({ : [1, 0, 9] });
}
{
// Merge docA and docB
.(.({ : "update", : .() }));
.(.({ : "update", : .() }));
}
// Converge to [1, 0, 9] because docB has larger peerId thus larger logical time
(.()).({ : [1, 0, 9] });
(.()).({ : [1, 0, 9] });Using Cursor on List
The Cursor on a List changes with the list’s modifications. If new elements are inserted in front of it, it moves to the right. If elements in front are deleted, it moves to the left. If elements are inserted or deleted behind it, it remains stationary.
If you use a List to represent paragraphs in an article, you can use a Cursor to stably represent the selection range on the paragraph.
const = new ();
.("1");
const = .("list");
.("Hello");
.("World");
const = .(1)!;
.(.()); // OUTPUT: { peer: "1", counter: 1 }
const : = .();
const : = .({ : "snapshot" });
// Sending the exported snapshot and the encoded cursor to peer 2
// Peer 2 will decode the cursor and get the position of the cursor in the list
// Peer 2 will then insert "Hello" at the beginning of the list
const = new ();
.("2");
const = .("list");
.();
.(0, "Foo");
.(.()); // OUTPUT: { list: ["Foo", "Hello", "World"] }
const = .();
{
// The cursor position is shifted to the right by 1
const = .();
.(.); // OUTPUT: 2
}
.(1, "Bar");
.(.()); // OUTPUT: { list: ["Foo", "Bar", "Hello", "World"] }
{
// The cursor position is shifted to the right by 1
const = .();
.(.); // OUTPUT: 3
}
.(3, 1);
.(.()); // OUTPUT: { list: ["Foo", "Bar", "Hello"] }
{
// The position the cursor points to is now deleted,
// but it should still get the position
const = .();
.(.); // OUTPUT: 3
// It will also offer an update on the cursor position.
//
// Because the old cursor position is deleted, `doc.getCursorPos()` will slow down over time.
// Internally, it needs to traverse the related history to find the correct position for a deleted
// cursor position.
//
// After refreshing the cursor, the performance of `doc.getCursorPos()` will improve.
.(.); // OUTPUT: { peer: "2", counter: 1 }
const : = .!;
// The new cursor position is undefined because the cursor is at the end of the list
.(.()); // OUTPUT: undefined
// The side is 1 because the cursor is at the right end of the list
.(.()); // OUTPUT: 1
const = .();
// The offset doesn't change
.(.); // OUTPUT: 3
// The update is undefined because the cursor no longer needs to be updated
.(.); // OUTPUT: undefined
}