a Moveable Tree CRDT, built on top of Yjs's Y.Map.

1-moveable-tree.ts

/**
 * Moveable tree.
 *
 * This implementation uses fractional indexing for children positions
 * and a parent id on the children for descendance.
 *
 * Pros:
 * - move operations are last-writer-wins.
 * - move operations can't produce duplicates.
 * - Can be built on top of existing last-writer-wins map crdts.
 *
 * Cons:
 * - Cycles are possible in theory (but could be ignored or resolved
 *   automatically when serializing, and shouldn't happen in practice).
 *
 */

import groupBy from 'lodash/groupBy';
import mapValues from 'lodash/mapValues';
import zip from 'lodash/zip';
import { v4 } from 'uuid';

import type { FractionalIndex } from '../fractional-index';
import {
    fractionalIndexAsc,
    generateKeyBetween,
    generateNKeysBetween,
} from '../fractional-index';
import type { YObject } from '../y-object';
import { createYObject, unwrapYObject } from '../y-object';

type Id = string;

export type Tree<T> = { id: Id; value: T; children: Tree<T>[] };

/**
 * An opaque branded type, only updatable using the `YMoveableTree`
 * namespace.
 */

const brand = Symbol.for('@crdt/brand');

export type YMoveableTree<T> = {
    [brand]: [name: '@crdts/YMoveableTree', valueType: T];
};

/**
 * The internal representation of the moveable tree:
 */

type YMoveableTreeInternal<T> = YObject<{
    root: YObject<{ id: Id; data: T }>;
    // nodes are flatten out.
    nodes: YObject<Record<Id, YObject<MoveableTreeNode<T>>>>;
}>;

type MoveableTree<T> = {
    root: { id: Id; data: T };
    nodes: Record<Id, MoveableTreeNode<T>>;
};

type MoveableTreeNode<T> = {
    // the position of a node is just it's parent
    // id and a fractionalIndex for its position in the list.
    parent: Id;
    fractionalIndex: FractionalIndex;
    data: T;
};

export type RelativePosition = {
    parent: Id;
    childBefore?: Id;
    childAfter?: Id;
};

const tabId = v4();

const getTransact = <T>(crdt: YObject<T>): ((f: () => void) => void) =>
    crdt.doc?.transact ?? ((f) => f());

const fromInternal = <T>(tree: YMoveableTreeInternal<T>): YMoveableTree<T> =>
    tree as any;

const toInternal = <T>(tree: YMoveableTree<T>): YMoveableTreeInternal<T> =>
    tree as any;

// eslint-disable-next-line @typescript-eslint/no-redeclare
export namespace YMoveableTree {
    export const create = <T>(treeProp: Tree<T>): YMoveableTree<T> => {
        const createRec = (tree: Tree<T>): MoveableTree<T> => {
            const root = { id: tree.id, data: tree.value };

            const withIndices = zip(
                tree.children,
                generateNKeysBetween(
                    tree.children.length,
                    undefined,
                    undefined,
                ),
            ) as [Tree<T>, string][];

            const entries = withIndices.flatMap(([node, idx]) => {
                const nodeEntry = [
                    node.id,
                    {
                        data: node.value,
                        fractionalIndex: [tabId, idx],
                        parent: root.id,
                    },
                ] satisfies [Id, MoveableTreeNode<T>];

                const subtree = createRec(node);
                const childrenEntries = Object.entries(
                    subtree.nodes,
                ) satisfies [Id, MoveableTreeNode<T>][];

                return [nodeEntry, ...childrenEntries];
            });

            const nodes = Object.fromEntries(entries);

            return {
                root,
                nodes,
            };
        };
        const rawMoveableTree = createRec(treeProp);

        return fromInternal(
            createYObject({
                root: createYObject(rawMoveableTree.root),
                nodes: createYObject(
                    mapValues(rawMoveableTree.nodes, (node) => {
                        return createYObject(node);
                    }),
                ),
            }),
        );
    };

    export const toTree = <T>(treeProp: YMoveableTree<T>): Tree<T> => {
        const treeCRDT = toInternal(treeProp);
        const nodes = treeCRDT.get('nodes');
        const root = treeCRDT.get('root');

        const allNodeEntries = Array.from(nodes.entries()).map(
            ([key, value]) => [key, unwrapYObject(value)] as const,
        );

        const grouped = groupBy(
            allNodeEntries,
            ([, node]) => node.parent ?? 'null',
        );

        const entriesByParent = mapValues(grouped, (entries) =>
            entries.sort((a, b) =>
                fractionalIndexAsc(a[1].fractionalIndex, b[1].fractionalIndex),
            ),
        );

        const buildTrees = (parentId: Id): Tree<T>[] => {
            return (entriesByParent[parentId] ?? []).map(
                ([id, node]): Tree<T> => ({
                    value: node.data,
                    id,
                    children: buildTrees(id),
                }),
            );
        };

        return {
            value: root.get('data'),
            id: root.get('id'),
            children: buildTrees(root.get('id')),
        };
    };

    export const moveBetween = <T>(
        nodeIdsToMove: Id[],
        position: RelativePosition,
        treeProp: YMoveableTree<T>,
    ): void => {
        const treeCRDT = toInternal(treeProp);
        const nodes = treeCRDT.get('nodes');

        const transact = getTransact(treeCRDT);

        const nodeBefore = position.childBefore
            ? nodes.get(position.childBefore)
            : undefined;
        const nodeAfter = position.childAfter
            ? nodes.get(position.childAfter)
            : undefined;

        const nodesToMove = nodeIdsToMove
            .map((id) => nodes.get(id))
            .filter((x) => !!x);
        const keys = generateNKeysBetween(
            nodesToMove.length,
            nodeBefore?.get('fractionalIndex')[1],
            nodeAfter?.get('fractionalIndex')[1],
        );
        const nodesAndKeys = zip(nodesToMove, keys);

        transact(() => {
            for (const [node, key] of nodesAndKeys) {
                if (!node || !key) {
                    continue;
                }
                node.set('parent', position.parent);
                node.set('fractionalIndex', [tabId, key]);
            }
        });
    };

    export const addNodeBetween = <T>(
        node: { id: Id; data: T },
        position: RelativePosition,
        treeProp: YMoveableTree<T>,
    ): void => {
        const treeCRDT = toInternal(treeProp);
        const nodes = treeCRDT.get('nodes');

        const nodeBefore = position.childBefore
            ? nodes.get(position.childBefore)
            : undefined;
        const nodeAfter = position.childAfter
            ? nodes.get(position.childAfter)
            : undefined;

        nodes.set(
            node.id,
            createYObject({
                data: node.data,
                parent: position.parent,
                fractionalIndex: [
                    tabId,
                    generateKeyBetween(
                        nodeBefore?.get('fractionalIndex')[1],
                        nodeAfter?.get('fractionalIndex')[1],
                    ),
                ],
            }),
        );
    };

    export const removeNode = <T>(
        nodeId: Id,
        treeProp: YMoveableTree<T>,
    ): void => {
        const treeCRDT = toInternal(treeProp);
        const nodes = treeCRDT.get('nodes');
        nodes.delete(nodeId);
    };

    export const getNode = <T>(
        nodeId: Id,
        treeProp: YMoveableTree<T>,
    ): T | undefined => {
        const treeCRDT = toInternal(treeProp);
        return treeCRDT.get('nodes').get(nodeId)?.get('data');
    };

    export const getAllNodes = <T>(
        treeProp: YMoveableTree<T>,
    ): Record<Id, T> => {
        const treeCRDT = toInternal(treeProp);
        return Object.fromEntries(
            Array.from(treeCRDT.get('nodes').entries()).map(([key, value]) => [
                key,
                value.get('data'),
            ]),
        );
    };
}

2-fractional-index.ts

const scale = (
    domain: [number, number],
    range: [number, number],
    value: number,
) =>
    range[0] +
    ((value - domain[0]) / (domain[1] - domain[0])) * (range[1] - range[0]);

export const DIGITS =
    "_-,;:!?.'()[]{}@*/&#%`^+<=>|~$0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";

const DIGIT_TO_INDEX = Object.fromEntries(
    DIGITS.split('').map((c, i) => [c, i]),
);

const SMALLEST_DIGIT = DIGITS.at(0)!;
const LARGEST_DIGIT = DIGITS.at(-1)!;

const deserializeKey = (key: string) =>
    key.split('').map((c) => DIGIT_TO_INDEX[c]);

const serializeKey = (key: number[]) =>
    key.map((index) => DIGITS[index]).join('');

const getMidDigit = (prevD: number, nextD: number) => {
    // We add some jitter to avoid concurrently creating
    // indices that are too close to each other.
    const betweenRatio = scale([0, 1], [0.25, 0.75], Math.random());
    return Math.floor(prevD + (nextD - prevD) * betweenRatio);
};

export const generateKeyBetween = (
    prevKey: string | undefined = SMALLEST_DIGIT,
    nextKey: string | undefined = LARGEST_DIGIT,
): string => {
    const prevDigits = deserializeKey(prevKey);
    const nextDigits = deserializeKey(nextKey);

    const betweenDigits: number[] = [];
    const maxLength = Math.max(prevDigits.length, nextDigits.length);
    for (let i = 0; i < maxLength; i++) {
        let prevD = prevDigits[i] ?? 0;
        let nextD = nextDigits[i] ?? DIGITS.length - 1;

        if (prevD === nextD) {
            betweenDigits.push(prevD);
            continue;
        }

        let middleD = getMidDigit(prevD, nextD);
        betweenDigits.push(middleD);
        while (middleD === prevD) {
            i++;
            prevD = prevDigits[i] ?? 0;
            nextD = nextDigits[i] ?? DIGITS.length - 1;
            middleD = getMidDigit(prevD, nextD);
            betweenDigits.push(middleD);
        }
    }
    return serializeKey(betweenDigits);
};

export const generateNKeysBetween = (
    n: number,
    prevKey: string | undefined = SMALLEST_DIGIT,
    nextKey: string | undefined = LARGEST_DIGIT,
): string[] => {
    if (n === 0) {
        return [];
    }
    if (n === 1) {
        return [generateKeyBetween(prevKey, nextKey)];
    }
    if (nextKey == null) {
        let newKey = generateKeyBetween(prevKey, nextKey);
        const result = [newKey];
        for (let i = 0; i < n - 1; i++) {
            newKey = generateKeyBetween(newKey, nextKey);
            result.push(newKey);
        }
        return result;
    }
    if (prevKey == null) {
        let newKey = generateKeyBetween(prevKey, nextKey);
        const result = [newKey];
        for (let i = 0; i < n - 1; i++) {
            newKey = generateKeyBetween(prevKey, newKey);
            result.push(newKey);
        }
        result.reverse();
        return result;
    }
    const mid = Math.floor(n / 2);
    const newKey = generateKeyBetween(prevKey, nextKey);
    return [
        ...generateNKeysBetween(mid, prevKey, newKey),
        newKey,
        ...generateNKeysBetween(n - mid - 1, newKey, nextKey),
    ];
};

/**
 * `FractionalIndex` is a tuple because we have
 * to resolve potential conflicts where several users would
 * generate the same key.
 */
export type FractionalIndex = [replicaId: string, key: string];

export const fractionalIndexAsc = (a: FractionalIndex, b: FractionalIndex) => {
    const comp = a[1].localeCompare(b[1]);
    return comp === 0 ? a[0].localeCompare(b[0]) : comp;
};

3-y-object.ts

/**
 * Better Y.Map type for objects with a static set of keys.
 */
interface YObjectConstructor {
    new <T extends {}>(entries?: Iterable<Entries<T>>): YObject<T>;
}

export const YObject = Y.Map as unknown as YObjectConstructor;

// eslint-disable-next-line @typescript-eslint/no-redeclare
export interface YObject<T>
    extends Omit<
        Y.Map<ValueOf<T>>,
        | 'new'
        | 'set'
        | 'get'
        | 'delete'
        | 'has'
        | 'forEach'
        | 'toJSON'
        | 'entries'
    > {
    set: YObjectSet<T>;
    get: YObjectGet<T>;
    delete: YObjectDelete<T>;
    has: YObjectHas<T>;
    forEach: YObjectForEach<T>;
    toJSON(): object;
    entries(): Iterable<Entries<Extract<T, {}>>>;
}

type YObjectSet<T> = <K extends keyof T>(key: K, value: T[K]) => void;

type YObjectGet<T> = <K extends keyof T>(key: K) => T[K];

type YObjectDelete<T> = (key: OptionalKeysOf<T>) => void;

type YObjectHas<T> = (key: keyof T) => boolean;

type YObjectForEach<T> = <K extends keyof T>(
    f: (value: T[K], key: K) => void,
) => void;

export const createYObject = <T extends object>(obj: T): YObject<T> => {
    const yObj = new YObject<T>();
    for (const [key, value] of Object.entries(obj)) {
        yObj.set(key as keyof T, value);
    }
    return yObj;
};

export const unwrapYObject = <T extends object>(obj: YObject<T>): T => {
    return Object.fromEntries(obj.entries());
};