CRDT parody

crdt-parody.js

const randomUint32 = () => (Math.random() * 2 ** 32) >>> 0;

const merge = (operations) => {
  const result = [];

  for (const operation of operations) {
    switch (operation.kind) {
      case "insert": {
        if (!result[operation.position]) {
          result[operation.position] = operation;
        } else {
          if (operation.clock >= result[operation.position].clock) {
            result.splice(operation.position, 0, operation); // insert before
          } else {
            result.splice(operation.position + 1, 0, operation); // insert after
          }
        }
        break;
      }
      case "delete": {
        result.splice(operation.position, 1);
        break;
      }
    }
  }

  return result.map((o) => o.content).join("");
};

const CRDT = () => {
  let _clock = 0;
  const _peer = randomUint32();
  const _operations = [];
  return {
    get operations() {
      return _operations;
    },
    insert: ({ position, content }) => {
      _operations.push({
        kind: "insert",
        peer: _peer,
        clock: _clock++,
        position,
        content,
      });
    },
    delete: ({ position }) => {
      _operations.push({
        kind: "delete",
        peer: _peer,
        clock: _clock++,
        position,
      });
    },
    apply: (operations) => {
      for (const op of operations) {
        // sync local clock
        if (op.clock > _clock) {
          _clock = op.clock + 1;
        }
        // skip duplicates
        if (
          !_operations.find(
            (_op) => _op.peer === op.peer && _op.clock === op.clock
          )
        ) {
          _operations.push(op);
        }
      }
      // sort
      _operations.sort((a, b) => {
        return a.peer !== b.peer ? a.peer - b.peer : a.clock - b.clock;
      });
    },
    toString: () => merge(_operations),
  };
};

const sync = (a, b) => {
  a.apply(b.operations);
  b.apply(a.operations);
};

// example

const A = CRDT();
const B = CRDT();
A.insert({ position: 0, content: "C" });
A.insert({ position: 1, content: "X" });
A.delete({ position: 1 });
A.insert({ position: 1, content: "T" });

sync(A, B);

B.insert({ position: 1, content: "D" });
A.insert({ position: 1, content: "R" });

sync(A, B);

A.delete({ position: 1 });
A.insert({ position: 1, content: "R" });

sync(A, B);

const a = A.toString();
const b = B.toString();
console.log(a, a === b ? "==" : "!=", b);

const fromString = (str) => {
  const struct = CRDT();
  Array.from(str).forEach((content, position) => {
    struct.insert({ content, position });
  });
  return struct;
};

const alice = fromString("HELLO ALICE");
const bob = fromString("HELLO BOB");
sync(alice, bob);
console.log(alice.toString());
console.log(bob.toString());