onioncollab/src/onion/graph_state.ts

import {Delta, Transaction} from "./delta";

import {
  NodeCreation,
  NodeDeletion,
  EdgeUpdate,
  NewEdge, ExistingEdge,
  Target, TargetValue, TargetNode,
} from "./delta";

import {DeltaRegistry} from "./delta_registry";

import {PrimitiveValue} from "./types";


// This interface is used to de-couple the graph state (in our case, a data structure interpreted by the d3 library, and by the 'Graph' react component), from GraphState.
export interface GraphStateListener {
  createNode(ns: NodeState): void;
  createValue(vs: ValueState): void;
  deleteNode(id: PrimitiveValue): void;
  deleteValue(value: PrimitiveValue): void;
  createLinkToNode(sourceId: PrimitiveValue, label: string, targetId: PrimitiveValue): void;
  createLinkToValue(sourceId: PrimitiveValue, label: string, targetValue: PrimitiveValue): void;
  deleteLink(sourceId: PrimitiveValue, label: string): void;
}

// A 'proxy' GraphStateListener that multicasts graph state operations to a bunch of GraphStateListeners.
export class FanOutListener implements GraphStateListener {
  readonly listeners: GraphStateListener[];

  constructor(listeners: GraphStateListener[]) {
    this.listeners = listeners;
  }
  
  createNode(ns: NodeState) {
    this.listeners.forEach(m => m.createNode(ns));
  }
  createValue(vs: ValueState) {
    this.listeners.forEach(m => m.createValue(vs));
  }
  deleteNode(id: PrimitiveValue) {
    this.listeners.forEach(m => m.deleteNode(id));
  }
  deleteValue(value: PrimitiveValue) {
    this.listeners.forEach(m => m.deleteValue(value));
  }
  createLinkToNode(sourceId: PrimitiveValue, label: string, targetId: PrimitiveValue) {
    this.listeners.forEach(m => m.createLinkToNode(sourceId, label, targetId));
  }
  createLinkToValue(sourceId: PrimitiveValue, label: string, targetValue: PrimitiveValue) {
    this.listeners.forEach(m => m.createLinkToValue(sourceId, label, targetValue));
  }
  deleteLink(sourceId: PrimitiveValue, label: string) {
    this.listeners.forEach(m => m.deleteLink(sourceId, label));
  }
}

export class DummyListener implements GraphStateListener {
  createNode(ns: NodeState) {}
  createValue(vs: ValueState) {}
  deleteNode(id: PrimitiveValue) {}
  deleteValue(value: PrimitiveValue) {}
  createLinkToNode(sourceId: PrimitiveValue, label: string, targetId: PrimitiveValue) {}
  createLinkToValue(sourceId: PrimitiveValue, label: string, targetValue: PrimitiveValue) {}
  deleteLink(sourceId: PrimitiveValue, label: string) {}
}

const DUMMY = new DummyListener();

// Helper
function removeFromArray<T>(arr: T[], cb: (elem: T) => boolean) {
  arr.splice(arr.findIndex(cb), 1);
}


abstract class Common {
  // For every currently incoming edge, the label of the edge, the delta that set the edge, and the source of the edge.
  readonly currentlyIncoming: Array<[string, EdgeUpdate, NodeState]> = [];
  // For every previously incoming edge, the delta that set the edge to point somewhere else.
  readonly previouslyIncoming: Set<EdgeUpdate> = new Set();

  addIncoming(label: string, delta: EdgeUpdate, srcState: NodeState, listener: GraphStateListener) {
    this.currentlyIncoming.push([label, delta, srcState]);
  }
  noLongerIncoming(overwritten: EdgeUpdate, overwriter: EdgeUpdate, listener: GraphStateListener) {
    removeFromArray(this.currentlyIncoming, ([_,d]) => d === overwritten);
    this.previouslyIncoming.add(overwriter);
  }
  // only called when undoing a Delta
  unAddIncoming(delta: EdgeUpdate, listener: GraphStateListener) {
    removeFromArray(this.currentlyIncoming, ([_,d]) => d === delta);
  }
  // only called when undoing a Delta
  incomingAgain(label: string, unOverwritten: EdgeUpdate, srcState: NodeState, unOverwriter: EdgeUpdate, listener: GraphStateListener) {
    this.currentlyIncoming.push([label, unOverwritten, srcState]);
    this.previouslyIncoming.delete(unOverwriter);
  }

  getIncomingEdges(): [string, INodeState][] {
    return this.currentlyIncoming.map(([label, _, srcState]) => [label, srcState]);
  }

  // pure
  abstract isNode(uuid: PrimitiveValue): boolean;
  abstract isValue(value: PrimitiveValue): boolean;
  abstract asTarget(): NodeCreation | PrimitiveValue;

  // will notify 'listener'
  abstract createLinkTo(sourceId: PrimitiveValue, label: string, listener: GraphStateListener): void;

  // pure
  abstract getDeltaForSetEdge(registry: DeltaRegistry, label: string, target: NodeCreation | PrimitiveValue, reads?: ExistingEdge[]): EdgeUpdate;
  abstract getDeltasForDelete(registry: DeltaRegistry): (EdgeUpdate|NodeDeletion)[];

  getReads(label: string): EdgeUpdate[] {
    return [];
  }

  // idempotent - may create some new deltas but does not execute them
  getIncomingEdgeDependenciesForDelete(registry: DeltaRegistry): [EdgeUpdate[], EdgeUpdate[]]{
    const newDeltas = this.currentlyIncoming.map(([label, u, ns]) => {
      return registry.newEdgeUpdate(u.overwrite(), null, [], ns.getReads(label).slice());
    });

    return [[...this.previouslyIncoming].concat(newDeltas), newDeltas];
  }
}

// These interfaces allow us to pass around NodeState and ValueState objects while not exposing the stuff that is supposed to remain internal wrt. this module.

interface ICommon {  
  // array of (label, NodeState) pairs
  getIncomingEdges(): [string, INodeState][];

  getDeltaForSetEdge(registry: DeltaRegistry, label: string, target: NodeCreation | PrimitiveValue, reads?: ExistingEdge[]): EdgeUpdate;

  getDeltasForDelete(registry: DeltaRegistry): (EdgeUpdate|NodeDeletion)[];

  asTarget(): NodeCreation | PrimitiveValue;

  isNode(uuid: PrimitiveValue): boolean;
  isValue(value: PrimitiveValue): boolean;
}

export interface IValueState extends ICommon {
  readonly type: "value";

  readonly value: PrimitiveValue;
}

export interface INodeState extends ICommon {
  readonly type: "node";

  readonly outgoingDeltas: ReadonlyMap<string, EdgeUpdate>;

  readonly outgoing: ReadonlyMap<string, IValueState | INodeState>;

  readonly creation: NodeCreation;

  readonly isDeleted: boolean;
}

// In order to edit a graph, we must know what operations most recently "touched" every node, and every edge. This is because new edit operations can depend on earlier operations (that they overwrite).
// This class captures, for a single node, a set of most-recent operations. It also has methods for editing the node. These methods are "pure" (they have no side-effects): they only return Deltas that capture the change. The change doesn't happen until those Deltas are (re)played, with GraphState.
class NodeState extends Common implements INodeState {
  readonly type = "node";

  readonly creation: NodeCreation;

  // For every outgoing edge, the Delta that set this edge to its current value
  readonly outgoingDeltas: Map<string, EdgeUpdate> = new Map();

  // For every outgoing edge, the set of deltas that read the value of this edge.
  // A new EdgeUpdate of this edge must depend ("after") on all these reads.
  // Careful: the values (which are arrays) are updated in-place as GraphState (un)executes deltas!
  readonly outgoingReads: Map<string, EdgeUpdate[]> = new Map();

  // All currently outgoing edges. Edges that were set to null will not be part of this mapping.
  readonly outgoing: Map<string, IValueState | INodeState> = new Map();

  isDeleted: boolean = false; // has the node been deleted?

  constructor(creation: NodeCreation) {
    super();
    this.creation = creation;
  }

  isNode(uuid: PrimitiveValue): boolean {
    return this.creation.id == uuid;
  }

  isValue(value: PrimitiveValue): boolean {
    return false;
  }

  asTarget() {
    return this.creation;
  }

  createLinkTo(sourceId: PrimitiveValue, label: string, listener: GraphStateListener) {
    listener.createLinkToNode(sourceId, label, this.creation.id);
  }

  getReads(label: string): EdgeUpdate[] {
    return this.outgoingReads.get(label) || [];
  }

  // Has no side effects - instead returns the deltas that capture the creation or update of the given outgoing edge
  getDeltaForSetEdge(registry: DeltaRegistry, label: string, target: NodeCreation | PrimitiveValue, reads: readonly ExistingEdge[] = []): EdgeUpdate {
    const previousEdgeUpdate = this.outgoingDeltas.get(label);
    if (previousEdgeUpdate === undefined) {
      return registry.newEdgeUpdate(this.creation.createOutgoingEdge(label), target, reads, []);
    }
    else {
      return registry.newEdgeUpdate(previousEdgeUpdate.overwrite(), target, reads, this.getReads(label).slice());
    }
  }

  // Has no side effects - instead returns the deltas that capture the deletion of this node (and its incoming+outgoing edges)
  getDeltasForDelete(registry: DeltaRegistry): (EdgeUpdate|NodeDeletion)[] {
    // set all incoming edges to 'null' (if they aren't already):
    const [afterTgt, newDeltas] = this.getIncomingEdgeDependenciesForDelete(registry);
    console.log({afterTgt});
    // set all outgoing edges to 'null':
    const afterSrc = [...this.outgoingDeltas.values()].map(u => {
      return registry.newEdgeUpdate(u.overwrite(), null, [], this.getReads(u.overwrites.label).slice());
    });
    // console.log("deleting", this.creation.id, {afterTgt, afterSrc});
    const nodeDeletion = registry.newNodeDeletion(this.creation, afterSrc, afterTgt);
    return [...newDeltas, ...afterSrc, nodeDeletion];
  }
}


class ValueState extends Common implements IValueState {
  readonly type = "value";

  shown: boolean = false; // does a (visible) node currently exist for this value?

  readonly value: PrimitiveValue;

  constructor(value: PrimitiveValue) {
    super();
    this.value = value;
  }

  isNode(uuid: PrimitiveValue) {
    return false;
  }

  isValue(value: PrimitiveValue) {
    return this.value === value;
  }

  asTarget() {
    return this.value;
  }

  createLinkTo(sourceId: PrimitiveValue, label: string, listener: GraphStateListener) {
    listener.createLinkToValue(sourceId, label, this.value);
  }

  addIncoming(label: string, delta: EdgeUpdate, srcState: NodeState, listener: GraphStateListener) {
    super.addIncoming(label, delta, srcState, listener);
    this._showOrHide(listener);
  }
  noLongerIncoming(overwritten: EdgeUpdate, overwriter: EdgeUpdate, listener: GraphStateListener) {
    super.noLongerIncoming(overwritten, overwriter, listener);
    this._showOrHide(listener);
  }
  // only called when undoing a Delta
  unAddIncoming(delta: EdgeUpdate, listener: GraphStateListener) {
    super.unAddIncoming(delta, listener);
    this._showOrHide(listener);
  }
  // only called when undoing a Delta
  incomingAgain(label: string, unOverwritten: EdgeUpdate, srcState: NodeState, unOverwriter: EdgeUpdate, listener: GraphStateListener) {
    super.incomingAgain(label, unOverwritten, srcState, unOverwriter, listener);
    this._showOrHide(listener);
  }

  // Value nodes are "always already there", but they are only rendered when they are currently the target of an edge. This function determines whether a value node should be rendered, and creates/deletes the corresponding node using the 'listener'.
  private _showOrHide(listener: GraphStateListener) {
    const willShow = this.currentlyIncoming.length > 0;
    if (!this.shown && willShow) {
      listener.createValue(this);
    }
    else if (this.shown && !willShow) {
      listener.deleteValue(this.value);
    }
    this.shown = willShow;
  }

  getDeltaForSetEdge(registry: DeltaRegistry, label: string, target: NodeCreation | PrimitiveValue, reads: ExistingEdge[] = []): EdgeUpdate {
    // A value cannot be the source of an edge, so we return no deltas.
    throw new Error("Assertion failed: A value cannot be the source of an edge.")
  }
  getDeltasForDelete(registry: DeltaRegistry): (EdgeUpdate|NodeDeletion)[] {
    const [edgeUnsettings, _] = this.getIncomingEdgeDependenciesForDelete(registry);
    return edgeUnsettings;
  }
}

// Executes (primitive) deltas, and updates the graph state accordingly.
// External representations (e.g., d3) can be kept in sync through GraphStateListener.
export class GraphState {

  readonly nodes: Map<PrimitiveValue, NodeState> = new Map();
  readonly values: Map<PrimitiveValue, ValueState> = new Map();

  private deltasSinceCheckpoint: Array<Array<Delta>> = [];

  // Deltas that are part of current state
  readonly deltas: Set<Delta> = new Set();

  // Stores a snapshot of the current graph state. Kind of like Git stash.
  pushState() {
    this.deltasSinceCheckpoint.push([]);
  }
  // Restores a previously stored graph state snapshot
  popState(): Array<Delta> {
    const toUnexec = this.deltasSinceCheckpoint.at(-1);
    if (toUnexec === undefined) {
      throw new Error("GraphState: cannot popState(), must pushState() first");
    }
    const result = toUnexec.slice(); // clone this array
    toUnexec.reduceRight((_,d)=>{this.unexec(d); return null;}, null);
    this.deltasSinceCheckpoint.pop();
    return result;
  }

  exec(delta: Delta, listener: GraphStateListener = DUMMY) {
    if (delta instanceof NodeCreation) {
      this.execNodeCreation(delta, listener);
    }
    else if (delta instanceof NodeDeletion) {
      this.execNodeDeletion(delta, listener);
    }
    else if (delta instanceof EdgeUpdate) {
      this.execEdgeUpdate(delta, listener);
    }
    else if (delta instanceof Transaction) {
      delta.deltas.forEach(d => this.exec(d, listener));
    }
    else {
      throw new Error("Assertion failed: Unexpected delta type");
    }
    this.deltasSinceCheckpoint.at(-1)?.push(delta);
    this.deltas.add(delta);
  }
  unexec(delta: Delta, listener: GraphStateListener = DUMMY) {
    this.deltas.delete(delta);
    if (delta instanceof NodeCreation) {
      this.unexecNodeCreation(delta, listener);
    }
    else if (delta instanceof NodeDeletion) {
      this.unexecNodeDeletion(delta, listener);
    }
    else if (delta instanceof EdgeUpdate) {
      this.unexecEdgeUpdate(delta, listener);
    }
    else if (delta instanceof Transaction) {
      delta.deltas.reduceRight((_, d) => {this.unexec(d, listener); return null;}, null);
    }
    else {
      throw new Error("Assertion failed: Unexpected delta type");
    }
    const checkpoint = this.deltasSinceCheckpoint.at(-1);
    if (checkpoint !== undefined) {
      const lastDelta = checkpoint.pop()!;
      if (lastDelta !== delta) {
        throw new Error("GraphState: asymmetrical call to unexec");
      }
    }
  }

  private _getEdgeTargetState(target: Target): NodeState | ValueState | undefined {
    if (target instanceof TargetNode) {
      return this.nodes.get(target.value.id); // may return undefined
    }
    else if (target instanceof TargetValue && target.value !== null) {
      return this.getValueState(target.value);
    }
  }
  private getValueState(value: PrimitiveValue): ValueState {
    let vs = this.values.get(value);
    if (vs === undefined) {
      vs = new ValueState(value);
      this.values.set(value, vs);
    }
    return vs;
  }

  private execNodeCreation(delta: NodeCreation, listener: GraphStateListener) {
    // console.log("execNodeCreation", delta)
    const nodeState = new NodeState(delta);
    this.nodes.set(delta.id, nodeState);
    listener.createNode(nodeState);
  }
  private unexecNodeCreation(delta: NodeCreation, listener: GraphStateListener) {
    // console.log("unexecNodeCreation", delta)
    this.nodes.delete(delta.id);
    listener.deleteNode(delta.id);
  }

  private execNodeDeletion(delta: NodeDeletion, listener: GraphStateListener) {
    // console.log("execNodeDeletion", delta)
    const id = delta.node.id;
    const nodeState = this.nodes.get(id);
    if (nodeState === undefined) {
      throw new Error("Assertion failed: deleted node does not exist")
    }
    nodeState.isDeleted = true;
    listener.deleteNode(id);
  }
  private unexecNodeDeletion(delta: NodeDeletion, listener: GraphStateListener) {
    // restore outgoing links
    const id = delta.node.id;
    const nodeState = this.nodes.get(id);
    if (nodeState === undefined) {
      throw new Error("Assertion failed: deleted node does not exist")
    }
    nodeState.isDeleted = false;
    listener.createNode(nodeState);
  }

  private execEdgeUpdate(delta: EdgeUpdate, listener: GraphStateListener) {
    const edge = delta.overwrites;
    const label = edge.label;
    const sourceId = edge.source.id;
    const sourceState = this.nodes.get(sourceId);

    if (sourceState === undefined) {
      throw new Error(`Assertion failed: Must have sourceState -> cannot execute EdgeUpdate. (${delta.description})`);
    }

    // Remove edge from old target
    if (edge instanceof NewEdge) {
      // Nothing was overwritten
    }
    else if (edge instanceof ExistingEdge) {
      const overwrittenUpdate = edge.delta;
      const oldTarget = overwrittenUpdate.target;
      const oldTargetState = this._getEdgeTargetState(oldTarget);
      if (oldTargetState === undefined) {
        if (oldTarget.value !== null) {
          console.log("TODO: Check: Possibly an assertion error here.");
        }
      }
      else {
        oldTargetState.noLongerIncoming(overwrittenUpdate, delta, listener);
        listener.deleteLink(sourceId, label);
      }
    }

    // Add edge to new target
    const newTarget = delta.target;
    const newTargetState = this._getEdgeTargetState(newTarget);
    if (newTargetState === undefined) {
      if (newTarget.value !== null) {
        console.log("TODO: Check: Possibly an assertion error here.");
      }
      sourceState.outgoing.delete(label);
    }
    else {
      newTargetState.addIncoming(label, delta, sourceState, listener);
      newTargetState.createLinkTo(sourceId, label, listener);
      sourceState.outgoing.set(label, newTargetState);
    }
    sourceState.outgoingDeltas.set(label, delta);

    // Add reads
    for (const r of delta.reads) {
      const readsNode = this.nodes.get(r.source.id);
      const reads = readsNode!.outgoingReads.get(r.label) || (() => {
        const newReads = [];
        readsNode!.outgoingReads.set(r.label, newReads);
        return newReads;
      })();
      reads.push(delta);
    }
  }
  private unexecEdgeUpdate(delta: EdgeUpdate, listener: GraphStateListener) {
    const edge = delta.overwrites;
    const label = edge.label;
    const sourceId = edge.source.id;
    const sourceState = this.nodes.get(sourceId);

    if (sourceState === undefined) {
      throw new Error("Assertion failed: Must have sourceState -> cannot un-execute EdgeUpdate.");
    }

    // Remove reads
    for (const r of delta.reads) {
      const readsNode = this.nodes.get(r.source.id);
      const reads = readsNode!.outgoingReads.get(r.label) || (() => {
        const newReads = [];
        readsNode!.outgoingReads.set(r.label, newReads);
        return newReads;
      })();
      removeFromArray(reads, elem => elem === delta);
    }

    // Remove edge from new target
    const newTarget = delta.target;
    const newTargetState = this._getEdgeTargetState(newTarget);
    if (newTargetState === undefined) {
      if (newTarget.value !== null) {
        console.log("TODO: Check: Possibly an assertion error here.");
      }
    }
    else {
      newTargetState.unAddIncoming(delta, listener);
      listener.deleteLink(sourceId, label);
    }

    // Add edge to old target
    if (edge instanceof NewEdge) {
      // Nothing was overwritten
      sourceState.outgoingDeltas.delete(label);
      sourceState.outgoing.delete(label);
    }
    else if (edge instanceof ExistingEdge) {
      const overwrittenUpdate = edge.delta;
      const oldTarget = overwrittenUpdate.target;
      const oldTargetState = this._getEdgeTargetState(oldTarget);
      if (oldTargetState === undefined) {
        if (oldTarget.value !== null) {
          console.log("TODO: Check: Possibly an assertion error here.");
        }
        sourceState.outgoing.delete(label);
      }
      else {
        oldTargetState.incomingAgain(label, overwrittenUpdate, sourceState, delta, listener);
        oldTargetState.createLinkTo(sourceId, label, listener);
        sourceState.outgoing.set(label, oldTargetState);
      }
      sourceState.outgoingDeltas.set(label, overwrittenUpdate);
    }
  }
}