README.md

@sabaki/crdt-gametree

An immutable, conflict-free replicated game tree data type.

Installation

Use npm to install:

$ npm install @sabaki/crdt-gametree

Usage

const GameTree = require('@sabaki/crdt-gametree')

let tree1 = new GameTree()
let tree2 = new GameTree()

let newTree1 = tree1.mutate(draft => {
    let id1 = draft.appendNode(draft.root.id, {B: ['dd']})
    let id2 = draft.appendNode(id1, {W: ['dq']})

    draft.addToProperty(id2, 'W', 'qd')
})

let newTree2 = tree2.mutate(draft => {
    draft.updateProperty(draft.root.id, 'AB', ['dd'])
    draft.appendNode(draft.root.id, {W: ['dp']})
})

let mergedTree1 = newTree1.applyChanges(newTree2.getChanges())
let mergedTree2 = newTree2.applyChanges(newTree1.getChanges())

console.log(
    newTree1 !== tree1
    && newTree2 !== tree2
    && newTree1 !== newTree2
    && newTree1 !== mergedTree1
    && newTree2 !== mergedTree2
    && mergedTree1 !== mergedTree2
)
// => true
console.log(JSON.stringify(mergedTree1.root) === JSON.stringify(mergedTree2.root))
// => true

API

This library is based upon and is completely compatible with @sabaki/immutable-gametree. Nearly all properties, functions, and behavior that @sabaki/immutable-gametree exports you can expect in this library as well.

We will only point out subtle differences and additional functions in this document. Please consult the @sabaki/immutable-gametree documentation for a full overview of the functionalities.

---

Node Object

A node is represented by an object of the following form:

{
    id: <Primitive>,
    data: {
        [property: <String>]: <Array<Primitive>> | <Array<CollaborativeText>>
    },
    parentId: <Primitive> | null,
    children: <Array<NodeObject>>
}

Note that a so-called collaborative text property can contain a non-primitive value. To get the string value from a CollaborativeText, simply call the instance function toString(). The class CollaborativeText serializes into a JSON string, so calling JSON.stringify on node objects will still work.

Collaborative Text Properties

Adding and removing values to or from properties are merged when happening simultaneously. However, if you have a property that only has a single value and needs to be replaced, the update will follow the "winner takes it all" strategy.

That means if two users update a single property value simultaneously, only the changes of one user will be reflected in the game tree eventually. The changes of the other user will be discarded.

To allow collaborative editing for certain cases, you can specify certain properties as collaborative text properties. These properties can only contain one value, a CollaborativeText class which contains the string.

Updates to a collaborative text property made by multiple users will be merged consistently in the end.

Change Object

Every mutation operation made to a game tree draft will be represented by a change object:

{
    id: <Primitive>,
    operation: <String>,
    args: <Array>,
    ret,
    author: <Primitive>,
    timestamp: <Number>
}

id contains a unique change id while author contains the GameTree id that made the change.

---

class GameTree

new GameTree([options])

• options <Object> (optional)
  • id <Primitive> (optional) - A unique author id. Default: A random UUID
  • collaborativeTextProperties <Array<String>> (optional) - An array of property identifiers that are collaborative text properties
  • See @sabaki/immutable-gametree GameTree
    • getId <Function> (optional) - If you specify this function, you have to make sure it generates globally unique ids, not just locally unique ones.

tree.id

<Primitive> - The unique author id.

tree.timestamp

<Number> - Current logical timestamp.

tree.collaborativeTextProperties

<Array<String>> - An array of property identifiers that are collaborative text properties. This property will be inherited to all mutations.

*tree.listHistory()

A generator function that yields all changes made to the tree since initialization in reverse order.

tree.getHistory()

Returns an array of change objects that consists of all the changes made to the tree since initialization in logical order.

tree.getChangeId()

Returns the id of the change that led to the current tree state.

tree.getChanges([oldTree])

• oldTree <GameTree> (optional)

Compares the history of tree and oldTree and returns an array of changes that are missing in tree in logical order.

oldTree defaults to the game tree we mutated from.

tree.applyChanges(changes)

• changes <Array<Change>>

Returns a new GameTree instance that applies the given changes to the current tree.

tree.reset([changeId])

• changeId <Primitive> (optional)

Returns a new GameTree instance that represents the tree state at the change in the history of tree with the given changeId.

If changeId is not given, it returns a new GameTree instance that represents the tree state at the very beginning of the tree history.

This operation does not destroy the previous history.

---

class Draft

Differences to @sabaki/immutable-gametree Draft

• Functions prefixed with UNSAFE_ will throw errors.
• updateProperty, addToProperty, removeFromProperty will throw errors for collaborative text properties.

draft.id

<Primitive> - The GameTree id on which the draft is based on.

draft.timestamp

<Number> - The current logical timestamp.

draft.updateCollaborativeTextProperty(id, property, change)

• id <Primitive>
• property <String>
• change <Object> | <String>

Updates the collaborative text property of the node with the given id according to a collaborative text change object change of the following structure:

{
    deletions: <Array<Number>>,
    insertions: <Array<{
        at: <Number>,
        insert: <String>
    }>>
}

For example, applying the following collaborative text change object to "Hello World!"

{
    deletions: [11, 6],
    insertions: [
        {
            at: 12,
            insert: ". How are you?"
        },
        {
            at: 6,
            insert: "cruel w"
        }
    ]
}

will result in "Hello cruel world. How are you?". If you specify a string as change, we will perform a diff between the old string and the new one, and automatically generate a minimal collaborative text change object for you in the background.

Releated

• immutable-gametree - An immutable game tree data type.