onioncollab/src/onion/delta.ts

import {NodeId, PrimitiveType, UUID, nodeIdsEqual} from "./types";

type Conflict = [MicroOperation, MicroOperation];

interface MicroOperation {
  // get conflicts between MicroOperations that depend on this MicroOperation.
  getConflicts(): Array<Conflict>;
}

export class NodeCreation implements MicroOperation {
  readonly id: NodeId;

  // Inverse dependency: Deletions of this node.
  deletions: Array<NodeDeletion>; // append-only

  // Inverse dependency: Creation of incoming and outgoing edges.
  edges: Array<EdgeCreation>; // append-only

  constructor(id: NodeId) {
    this.id = id;

    this.deletions = [];
    this.edges = [];
  }

  // There are 2 types of conflicts that can occur whose most nearby common ancestor is a NodeCreation: {DELETE,DELETE} and {DELETE,REQUIRE}.

  // Whenever a node is deleted more than once, concurrently, there's a {DELETE,DELETE}-conflict
  getDeleteDeleteConflicts(): Array<[NodeDeletion, NodeDeletion]> {
    // Basically get all pairs of 'deletions'
    const result = new Array(this.deletions.length*(this.deletions.length-1));
    let i = 0;
    for (const del1 of this.deletions) {
      for (const del2 of this.deletions) {
        if (del1 !== del2) {
          result[i] = [del1, del2]; // conflict: this node is concurrently deleted more than once
          i++;
        }
      }
    }
    return result;
  }

  // Whenever a node is deleted, and the source/target of a concurrent edge creation, there's a {DELETE,REQUIRE}-conflict.
  getDeleteRequireConflicts(): Array<[NodeDeletion, EdgeCreation]> {
    const result: Array<[NodeDeletion, EdgeCreation]> = [];
    for (const del of this.deletions) {
      for (const edgeCreation of this.edges) {
        let edgeDeleted = false;
        for (const edgeDel of del.edgeDeletions) {
          if (edgeDel.getCreation() === edgeCreation) {
            edgeDeleted = true;
            break;
          }
        }
        if (!edgeDeleted) {
          result.push([del, edgeCreation]); // conflict: this node is deleted, and at the same time it is the source or target of an edge
        }
      }
    }
    return result;
  }

  // Whenever two edges with the same source and the same label are concurrently created
  getEdgeCreationConflicts(): Array<[EdgeCreation, EdgeCreation]> {
    const result: Array<[EdgeCreation, EdgeCreation]> = [];
    for (const c1 of this.edges) {
      for (const c2 of this.edges) {
        if (c1 !== c2) {
          if (c1.label === c2.label) {
            result.push([c1, c2]); // conflict: same edge created concurrently
          }
        }
      }
    }
    return result;
  }

  getConflicts(): Array<Conflict> {
    return (this.getDeleteDeleteConflicts() as Array<Conflict>) // downcast :)
      .concat(this.getDeleteRequireConflicts() as Array<Conflict>) // downcast
      .concat(this.getEdgeCreationConflicts() as Array<Conflict>); // downcast
  }
}

export class NodeDeletion implements MicroOperation {
  // Dependency: The node being deleted.
  readonly deletes: NodeCreation;

  // Dependency: Deletion of a node depends on deletion of its incoming and outgoing edges.
  readonly edgeDeletions: Array<EdgeDeletion>;

  constructor(deletes: NodeCreation, edgeDeletions: Array<EdgeDeletion>) {
    this.deletes = deletes;
    this.edgeDeletions = edgeDeletions;

    // Create inverse dependency
    this.deletes.deletions.push(this);
  }

  getConflicts(): Array<Conflict> {
    return [];
  }
}

export interface EdgeOperation extends MicroOperation {
  // Edge operations always form a tree (or sequence, if non-conflicting) where the path from root to leaf is as follows: create, update, update, ..., update, delete
  // Therefore, any 'node' in this tree traces back to a 'root', the creation.
  getCreation(): EdgeCreation;
}

type EdgeUpdateOrDeletion = EdgeUpdate | EdgeDeletion;

abstract class EdgeCreationOrUpdate {
  // Dependency: (new) target node
  readonly target: NodeCreation;

  // Inverse dependency: Next operation on the edge
  nextOperations: Array<EdgeUpdate | EdgeDeletion>; // append-only

  constructor(target: NodeCreation) {
    this.target = target;

    this.nextOperations = [];
  }

  // {UPDATE,UPDATE}, {UDPATE,DELETE}, {DELETE,DELETE} on two edges with the same source and label.
  getUpdateOrDeleteConflicts(): Array<[EdgeUpdateOrDeletion, EdgeUpdateOrDeletion]> {
    const result = new Array(this.nextOperations.length*(this.nextOperations.length-1));
    let i = 0;
    for (const n1 of this.nextOperations) {
      for (const n2 of this.nextOperations) {
        if (n1 !== n2) {
          result[i] = [n1, n2];
          i++;
        }
      }
    }
    return result;
  }

  getConflicts(): Array<Conflict> {
    return this.getUpdateOrDeleteConflicts();
  }

  abstract getCreation(): EdgeCreation;
}

export class EdgeCreation extends EdgeCreationOrUpdate implements EdgeOperation {
  // Dependency: source node
  readonly source: NodeCreation;

  readonly label: string;

  constructor(source: NodeCreation, label: string, target: NodeCreation) {
    super(target);

    this.source = source;
    this.label = label;

    // Create inverse dependency
    this.source.edges.push(this);
  }

  getCreation(): EdgeCreation {
    return this;
  }
}

export class EdgeUpdate extends EdgeCreationOrUpdate implements EdgeOperation {
  readonly edge: EdgeCreationOrUpdate; // UPD-dependency

  constructor(edge: EdgeCreationOrUpdate, newTarget: NodeCreation) {
    super(newTarget);

    this.edge = edge;

    // Create inverse dependency
    this.edge.nextOperations.push(this);
  }

  getCreation(): EdgeCreation {
    return this.edge.getCreation();
  }
}

export class EdgeDeletion implements EdgeOperation {
  readonly edge: EdgeCreationOrUpdate; // UPD-dependency

  constructor(edge: EdgeCreationOrUpdate) {
    this.edge = edge;

    // Create inverse dependency
    this.edge.nextOperations.push(this);
  }

  getCreation(): EdgeCreation {
    return this.edge.getCreation();
  }

  getConflicts(): Array<Conflict> {
    return [];
  }
}


// class GraphState {
//   nodes: Map<NodeId, NodeCreation>;

//   createNode(id: NodeId): NodeCreation {
//     nodes.set()
//   }

//   createEdge(source: NodeCreation, label: string, target: NodeCreation) {

//   }
// }