caret / packages / core / src / crdt.ts

export abstract class CRDT<V> {
  abstract merge(other: CRDT<V>): CRDT<V>;
  abstract getValue(): V;
  abstract get DEBUG_data(): unknown;
  // abstract setActorId(actorId: ActorID): CRDT<V>;
}

export type ActorID = string & { __brand: "ActorID" };
export function createActorID(id: string): ActorID {
  return id as ActorID;
}

type DotHash = string & { __brand: "DotHash" };

export class Dot {
  actorId: ActorID;
  counter: number;

  constructor(actorId: ActorID, counter: number) {
    this.actorId = actorId;
    this.counter = counter;
  }

  toString(): string {
    return `${this.actorId}:${this.counter}`;
  }

  hash(): DotHash {
    // TODO: Different/better hash function?
    return btoa(`${this.actorId}:${this.counter}`) as DotHash;
  }

  equals(other: Dot): boolean {
    return this.actorId === other.actorId && this.counter === other.counter;
  }

  compare(other: Dot): number {
    if (this.counter !== other.counter) {
      return this.counter - other.counter;
    }
    if (this.actorId < other.actorId) {
      return -1;
    }
    if (this.actorId > other.actorId) {
      return 1;
    }
    return 0;
  }

  static equals(a: Dot | null, b: Dot | null): boolean {
    if (a === null || b === null) {
      return a === b;
    }
    return a.equals(b);
  }
}

export class GrowCounterCRDT extends CRDT<number> {
  private data: Map<ActorID, number>;

  constructor(data = new Map<ActorID, number>()) {
    super();
    this.data = data;
  }

  get DEBUG_data(): Map<ActorID, number> {
    return this.data;
  }

  increment(actorId: ActorID, amount: number = 1): GrowCounterCRDT {
    if (amount <= 0) {
      throw new Error("Increment amount must be positive");
    }
    const current = this.data.get(actorId) || 0;

    let newData = new Map(this.data);
    newData.set(actorId, current + amount);
    return new GrowCounterCRDT(newData);
  }

  getValue(): number {
    let total = 0;
    for (const value of this.data.values()) {
      total += value;
    }
    return total;
  }

  merge(other: GrowCounterCRDT): GrowCounterCRDT {
    const mergedData = new Map<ActorID, number>(this.data);
    for (const [actorId, value] of other.data.entries()) {
      const current = mergedData.get(actorId) ?? 0;
      mergedData.set(actorId, Math.max(current, value));
    }

    return new GrowCounterCRDT(mergedData);
  }
}

export class PNCounterCRDT extends CRDT<number> {
  private positive: GrowCounterCRDT;
  private negative: GrowCounterCRDT;

  constructor(
    positive: GrowCounterCRDT = new GrowCounterCRDT(),
    negative: GrowCounterCRDT = new GrowCounterCRDT(),
  ) {
    super();
    this.positive = positive;
    this.negative = negative;
  }

  get DEBUG_data(): {
    positive: Map<ActorID, number>;
    negative: Map<ActorID, number>;
  } {
    return {
      positive: this.positive.DEBUG_data,
      negative: this.negative.DEBUG_data,
    };
  }

  change(actorId: ActorID, amount: number): PNCounterCRDT {
    if (amount > 0) {
      return new PNCounterCRDT(
        this.positive.increment(actorId, amount),
        this.negative,
      );
    } else if (amount < 0) {
      return new PNCounterCRDT(
        this.positive,
        this.negative.increment(actorId, -amount),
      );
    } else {
      return this;
    }
  }

  set(actorId: ActorID, value: number): PNCounterCRDT {
    const currentValue = this.getValue();
    const delta = value - currentValue;
    return this.change(actorId, delta);
  }

  getValue(): number {
    return this.positive.getValue() - this.negative.getValue();
  }

  merge(other: PNCounterCRDT): PNCounterCRDT {
    return new PNCounterCRDT(
      this.positive.merge(other.positive),
      this.negative.merge(other.negative),
    );
  }
}

export class GrowSetCRDT<T> extends CRDT<Set<T>> {
  private data: Set<T>;

  constructor(data: Set<T> = new Set<T>()) {
    super();
    this.data = data;
  }

  get DEBUG_data(): Set<T> {
    return this.data;
  }

  add(element: T): GrowSetCRDT<T> {
    const newData = new Set(this.data);
    newData.add(element);
    return new GrowSetCRDT(newData);
  }

  getValue(): Set<T> {
    return new Set(this.data);
  }

  merge(other: GrowSetCRDT<T>): GrowSetCRDT<T> {
    const mergedData = new Set<T>(this.data);
    for (const element of other.data) {
      mergedData.add(element);
    }
    return new GrowSetCRDT(mergedData);
  }
}

export class SetCRDT<T> extends CRDT<Set<T>> {
  private addSet: GrowSetCRDT<T>;
  private removeSet: GrowSetCRDT<T>;

  constructor(
    addSet: GrowSetCRDT<T> = new GrowSetCRDT<T>(),
    removeSet: GrowSetCRDT<T> = new GrowSetCRDT<T>(),
  ) {
    super();
    this.addSet = addSet;
    this.removeSet = removeSet;
  }

  get DEBUG_data(): { addSet: Set<T>; removeSet: Set<T> } {
    return {
      addSet: this.addSet.DEBUG_data,
      removeSet: this.removeSet.DEBUG_data,
    };
  }

  add(element: T): SetCRDT<T> {
    return new SetCRDT(this.addSet.add(element), this.removeSet);
  }

  remove(element: T): SetCRDT<T> {
    return new SetCRDT(this.addSet, this.removeSet.add(element));
  }

  getValue(): Set<T> {
    const result = new Set<T>();
    for (const element of this.addSet.getValue()) {
      if (!this.removeSet.getValue().has(element)) {
        result.add(element);
      }
    }
    return result;
  }

  merge(other: SetCRDT<T>): SetCRDT<T> {
    return new SetCRDT(
      this.addSet.merge(other.addSet),
      this.removeSet.merge(other.removeSet),
    );
  }
}

export class LWWRegisterCRDT<T> extends CRDT<T> {
  private data: { value: T; dot: Dot };

  constructor(value: T, dot: Dot) {
    super();
    this.data = { value, dot };
  }

  get DEBUG_data() {
    return this.data;
  }

  set(actorId: ActorID, value: T): LWWRegisterCRDT<T> {
    const newCounter = this.data.dot.counter + 1;
    return new LWWRegisterCRDT<T>(value, new Dot(actorId, newCounter));
  }

  getValue(): T {
    return this.data.value;
  }

  merge(other: LWWRegisterCRDT<T>): LWWRegisterCRDT<T> {
    const compare = other.data.dot.compare(this.data.dot);

    if (compare === 0) {
      if (this.data.value === other.data.value) {
        return this;
      } else {
        throw new Error("Conflict detected in LWWRegisterCRDT merge");
      }
    } else if (compare > 0) {
      return other;
    } else {
      return this;
    }
  }
}

export class LWWMapCRDT<K, V> extends CRDT<Map<K, V>> {
  private data: Map<K, LWWRegisterCRDT<V>>;

  constructor(data: Map<K, LWWRegisterCRDT<V>> = new Map()) {
    super();
    this.data = data;
  }

  get DEBUG_data(): Map<K, { value: V; dot: Dot }> {
    const debugData = new Map<K, { value: V; dot: Dot }>();
    for (const [key, register] of this.data.entries()) {
      debugData.set(key, register.DEBUG_data);
    }
    return debugData;
  }

  set(actorId: ActorID, key: K, value: V): LWWMapCRDT<K, V> {
    const newData = new Map(this.data);
    const existingRegister = newData.get(key);
    if (existingRegister) {
      newData.set(key, existingRegister.set(actorId, value));
    } else {
      newData.set(key, new LWWRegisterCRDT<V>(value, new Dot(actorId, 1)));
    }
    return new LWWMapCRDT(newData);
  }

  getRegister(key: K): LWWRegisterCRDT<V> | undefined {
    return this.data.get(key);
  }

  getValue(): Map<K, V> {
    const result = new Map<K, V>();
    for (const [key, register] of this.data.entries()) {
      result.set(key, register.getValue());
    }
    return result;
  }

  merge(other: LWWMapCRDT<K, V>): LWWMapCRDT<K, V> {
    const mergedData = new Map<K, LWWRegisterCRDT<V>>(this.data);
    for (const [key, otherRegister] of other.data.entries()) {
      const existingRegister = mergedData.get(key);
      if (existingRegister) {
        mergedData.set(key, existingRegister.merge(otherRegister));
      } else {
        mergedData.set(key, otherRegister);
      }
    }
    return new LWWMapCRDT(mergedData);
  }
}

class DotIdSet<V extends { id: Dot }> {
  private data: Map<DotHash, V>;
  constructor(data: Map<DotHash, V> | DotIdSet<V> = new Map<DotHash, V>()) {
    this.data = data instanceof DotIdSet ? new Map(data.data) : new Map(data);
  }

  add(element: V): void {
    this.data.set(element.id.hash(), element);
  }

  get(id: Dot): V | undefined {
    return this.data.get(id.hash());
  }

  values(): IterableIterator<V> {
    return this.data.values();
  }

  delete(id: Dot): void {
    this.data.delete(id.hash());
  }
}

export class SequenceCRDT<V, C extends CRDT<V>> extends CRDT<
  { id: Dot; value: V }[]
> {
  private counter: number;
  private data: DotIdSet<{
    id: Dot;
    left: LWWRegisterCRDT<Dot | null>;
    deleted: boolean;
    value: C;
  }>;

  constructor(
    counter: number = 0,
    data: DotIdSet<{
      id: Dot;
      left: LWWRegisterCRDT<Dot | null>;
      deleted: boolean;
      value: C;
    }> = new DotIdSet(),
  ) {
    super();
    this.counter = counter;
    this.data = data;
  }

  get DEBUG_data() {
    return this.data;
  }

  insert(
    actorId: ActorID,
    leftId: Dot | null,
    value: C,
  ): [SequenceCRDT<V, C>, Dot | null] {
    const elementId = new Dot(actorId, this.counter + 1);

    const newData = new DotIdSet(this.data);
    newData.add({
      id: elementId,
      left: new LWWRegisterCRDT<Dot | null>(leftId, new Dot(actorId, 0)),
      deleted: false,
      value,
    });

    // Any existing elements that had leftId as their left should now point to the new element
    for (const element of this.data.values()) {
      const elemLeft = element.left.getValue();
      if (Dot.equals(elemLeft, leftId)) {
        newData.delete(element.id);
        newData.add({
          id: element.id,
          left: element.left.set(actorId, elementId),
          deleted: element.deleted,
          value: element.value,
        });
      }
    }

    return [new SequenceCRDT(this.counter + 1, newData), elementId];
  }

  setItemValue(
    actorId: ActorID,
    id: Dot,
    value: C | ((oldValue: C) => C),
  ): SequenceCRDT<V, C> {
    const newData = new DotIdSet(this.data);
    for (const element of this.data.values()) {
      if (element.id.equals(id)) {
        newData.delete(element.id);
        newData.add({
          id: element.id,
          left: element.left,
          deleted: element.deleted,
          value: typeof value === "function" ? value(element.value) : value,
        });
        break;
      }
    }
    return new SequenceCRDT(this.counter, newData);
  }

  delete(actorId: ActorID, id: Dot): SequenceCRDT<V, C> {
    const newData = new DotIdSet(this.data);
    let deletedElement: {
      id: Dot;
      left: LWWRegisterCRDT<Dot | null>;
      deleted: boolean;
      value: CRDT<unknown>;
    } | null = null;

    for (const element of this.data.values()) {
      if (element.id.equals(id)) {
        if (element.deleted) return this; // Already deleted

        deletedElement = element;
        newData.delete(element.id);
        newData.add({
          id: element.id,
          left: element.left,
          deleted: true,
          value: element.value,
        });
        break;
      }
    }

    if (deletedElement) {
      const deletedLeftId = deletedElement.left.getValue();
      // Reassign right siblings to point to the deleted element's left
      for (const element of this.data.values()) {
        const elemLeft = element.left.getValue();
        if (Dot.equals(elemLeft, deletedElement.id)) {
          newData.delete(element.id);
          newData.add({
            id: element.id,
            left: element.left.set(actorId, deletedLeftId),
            deleted: element.deleted,
            value: element.value,
          });
        }
      }
    }

    return new SequenceCRDT(this.counter, newData);
  }

  getValue(): {
    id: Dot;
    DEBUG_left: Dot | null;
    value: V;
  }[] {
    const getElementsWithLeftId = (leftId: Dot | null) => {
      return new Set(
        [...this.data.values()].filter((element) => {
          const elementLeft = element.left.getValue();
          if (leftId === null || elementLeft === null) {
            return leftId === elementLeft;
          }
          return elementLeft.equals(leftId);
        }),
      );
    };

    const result: {
      id: Dot;
      DEBUG_left: Dot | null;
      value: V;
    }[] = [];
    const visited = new Set<Dot>();

    const isVisited = (id: Dot) => {
      for (const visitedId of visited) {
        if (Dot.equals(visitedId, id)) return true;
      }
      return false;
    };

    const appendRightSiblings = (leftId: Dot | null) => {
      const siblings = getElementsWithLeftId(leftId);
      const sortedSiblings = Array.from(siblings).sort((a, b) =>
        a.id.compare(b.id),
      );
      for (const sibling of sortedSiblings) {
        if (!isVisited(sibling.id)) {
          if (!sibling.deleted) {
            result.push({
              id: sibling.id,
              DEBUG_left: sibling.left.getValue(),
              value: sibling.value.getValue(),
            });
          }
          visited.add(sibling.id);
          appendRightSiblings(sibling.id);
        }
      }
    };

    appendRightSiblings(null);

    return result;
  }

  getValueWithCursor(
    cursor: Dot | null,
  ): [{ id: Dot; DEBUG_left: Dot | null; value: V }[], number] {
    const elements = this.getValue();
    if (cursor === null) {
      return [elements, 0];
    }

    let notDeletedLeftId: Dot = cursor;
    const getElementById = (id: Dot) => {
      for (const element of this.data.values()) {
        if (element.id.equals(id)) return element;
      }
      return null;
    };
    while (getElementById(notDeletedLeftId)?.deleted) {
      const leftOfDeleted = getElementById(notDeletedLeftId)?.left.getValue();
      if (leftOfDeleted === undefined) {
        throw new Error("leftId points to non-existent element");
      }
      if (leftOfDeleted === null) {
        return [elements, 0];
      }
      notDeletedLeftId = leftOfDeleted;
    }

    let index = 0;
    for (const element of elements) {
      if (element.id.equals(notDeletedLeftId)) {
        return [elements, index + 1];
      }
      index++;
    }

    throw new Error("Cursor not found in sequence");
  }

  merge(other: SequenceCRDT<V, C>): SequenceCRDT<V, C> {
    const mergedData = new DotIdSet(this.data);
    for (const otherElement of other.data.values()) {
      // Find if this element already exists
      let exists = false;
      for (const existingElement of mergedData.values()) {
        if (existingElement.id.equals(otherElement.id)) {
          // Merge the LWWMapCRDT values
          const mergedValue = existingElement.value.merge(otherElement.value);
          const mergedLeft = existingElement.left.merge(otherElement.left);
          mergedData.delete(existingElement.id);
          mergedData.add({
            id: existingElement.id,
            left: mergedLeft,
            deleted: existingElement.deleted || otherElement.deleted,
            value: mergedValue as C,
          });
          exists = true;
          break;
        }
      }
      if (!exists) {
        mergedData.add({
          id: otherElement.id,
          left: otherElement.left,
          deleted: otherElement.deleted,
          value: otherElement.value,
        });
      }
    }
    return new SequenceCRDT(Math.max(this.counter, other.counter), mergedData);
  }

  setActorId(actorId: ActorID): SequenceCRDT<V, C> {
    const newData = new DotIdSet<{
      id: Dot;
      left: LWWRegisterCRDT<Dot | null>;
      deleted: boolean;
      value: C;
    }>();
    for (const element of this.data.values()) {
      newData.add({
        id: new Dot(actorId, element.id.counter),
        left: element.left,
        deleted: element.deleted,
        value: element.value,
      });
    }
    return new SequenceCRDT(this.counter, newData);
  }
}