onioncollab/src/onion/graph_state.ts

import {Delta} from "./delta";

import {
  NodeCreation,
  NodeDeletion,
  EdgeCreation,
  EdgeUpdate,
  EdgeTargetType,
  SetsTarget,
  PrimitiveRegistry,
} from "./primitive_delta";

import {CompositeDelta} from "./composite_delta";

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);
  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);
}

// 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));
  }
}


type IncomingEdgeDelta = EdgeCreation|EdgeUpdate|NodeDeletion;

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();


abstract class Common {
  // If there once was an incoming edge on this node (or value), this contains the Delta that (un)set the edge to point to this node (or value)
  readonly incoming: Array<IncomingEdgeDelta> = [];

  // For every currently incoming edge, the pair (label, source)
  readonly incomingStates: Array<[string, NodeState]> = [];

  addIncoming(delta: IncomingEdgeDelta, listener: GraphStateListener) {
    this.incoming.push(delta);
  }
  replaceIncoming(prevDelta: IncomingEdgeDelta, newDelta: IncomingEdgeDelta, listener: GraphStateListener) {
    this.incoming.splice(this.incoming.indexOf(prevDelta), 1, newDelta);
  }
  // only called when undoing a Delta
  removeIncoming(delta: IncomingEdgeDelta, listener: GraphStateListener) {
    this.incoming.splice(this.incoming.indexOf(delta), 1);
  }

  getIncomingEdges(): [string, INodeState][] {
    return this.incomingStates;
  }

  // pure
  abstract isNode(uuid: PrimitiveValue): boolean;
  abstract isValue(value: PrimitiveValue): boolean;
  // abstract isTargetOf(setsTarget: SetsTarget): boolean;
  abstract asTarget(): EdgeTargetType;

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

  // pure
  abstract getDeltasForSetEdge(registry: PrimitiveRegistry, label: string, target: EdgeTargetType): (EdgeCreation|EdgeUpdate)[];
  abstract getDeltasForDelete(registry: PrimitiveRegistry): (EdgeUpdate|NodeDeletion)[];

  // pure
  getIncomingEdgeDependenciesForDelete(registry: PrimitiveRegistry): [EdgeUpdate[], (EdgeUpdate|NodeDeletion)[]] {
    const edgeUnsettings: EdgeUpdate[] = [];
    const incomingEdgeDependencies = this.incoming.map((incomingEdge) => {
      // We also depend on incoming edges that were deleted (because their source node was deleted):
      if (incomingEdge instanceof NodeDeletion) {
        return incomingEdge;
      }
      else if (incomingEdge.target.getTarget() === this.asTarget()) {
          // Must set the value of every incoming edge to 'null' (with an EdgeUpdate):
          const edgeUnsetting = registry.newEdgeUpdate(incomingEdge, null);
          edgeUnsettings.push(edgeUnsetting);
          return edgeUnsetting;
      }
      else {
        // Edge is already pointing somewhere else: just include the operation as a dependency for the deletion.
        if (!(incomingEdge instanceof EdgeUpdate)) {
          throw new Error("Assertion failed: incomingEdge must be EdgeUpdate here.")
        }
        return incomingEdge;
      }
    });

    // incomingEdgeDependencies are dependencies of the (future) deletion of this node.
    // edgeUnsettings is the subset (of incomingEdgeDependencies) of NEW deltas.
    return [edgeUnsettings, incomingEdgeDependencies];
  }
}

// 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][];

  getDeltasForSetEdge(registry: PrimitiveRegistry, label: string, target: EdgeTargetType): (EdgeCreation|EdgeUpdate)[];

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

  asTarget(): EdgeTargetType;

  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";

  // mapping of label to NodeState
  getOutgoingEdges(): Map<string, IValueState | INodeState>;

  readonly creation: NodeCreation;
}

// 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 *currently* outgoing edge, the Delta that set this edge to its current value
  readonly outgoing: Map<string, EdgeCreation|EdgeUpdate> = new Map();

  readonly outgoingStates: Map<string, IValueState | INodeState> = new Map();

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

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

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

  asTarget(): EdgeTargetType {
    return this.creation;
  }

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

  getOutgoingEdges(): Map<string, IValueState | INodeState> {
    return this.outgoingStates;
  }

  // Has no side effects - instead returns the deltas that capture the creation or update of the given outgoing edge
  getDeltasForSetEdge(registry: PrimitiveRegistry, label: string, target: EdgeTargetType): (EdgeCreation|EdgeUpdate)[] {
    const previousEdgeUpdate = this.outgoing.get(label);
    if (previousEdgeUpdate !== undefined) {
      return [registry.newEdgeUpdate(previousEdgeUpdate, target)];
    }
    else {
      return [registry.newEdgeCreation(this.creation, label, target)];
    }
  }

  // Has no side effects - instead returns the deltas that capture the deletion of this node (and its incoming+outgoing edges)
  getDeltasForDelete(registry: PrimitiveRegistry): (EdgeUpdate|NodeDeletion)[] {
    const [edgeUnsettings, incomingEdgeDependencies] = this.getIncomingEdgeDependenciesForDelete(registry);
    const outgoingEdgeDependencies = [...this.outgoing.values()];
    const nodeDeletion = registry.newNodeDeletion(this.creation, outgoingEdgeDependencies, incomingEdgeDependencies);
    return [...edgeUnsettings, 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(): EdgeTargetType {
    return this.value;
  }

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

  addIncoming(delta: IncomingEdgeDelta, listener: GraphStateListener) {
    super.addIncoming(delta, listener);
    this._showOrHide(listener);
  }
  replaceIncoming(prevDelta: IncomingEdgeDelta, newDelta: IncomingEdgeDelta, listener: GraphStateListener) {
    super.replaceIncoming(prevDelta, newDelta, listener);
    this._showOrHide(listener);
  }
  removeIncoming(delta: IncomingEdgeDelta, listener: GraphStateListener) {
    super.removeIncoming(delta, 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.incoming.some(delta => {
      // Does 'delta' require a value node to be displayed?
      if (delta instanceof EdgeCreation) {
        return true;
      }
      else if (delta instanceof EdgeUpdate) {
        return delta.target.getTarget() === this.value;
      }
      else if (delta instanceof NodeDeletion) {
        return false;
      }
    });
    if (!this.shown && willShow) {
      listener.createValue(this);
    }
    else if (this.shown && !willShow) {
      listener.deleteValue(this.value);
    }
    this.shown = willShow;
  }

  getDeltasForSetEdge(registry: PrimitiveRegistry, label: string, target: EdgeTargetType): (EdgeCreation|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: PrimitiveRegistry): (EdgeUpdate|NodeDeletion)[] {
    const [edgeUnsettings, _] = this.getIncomingEdgeDependenciesForDelete(registry);
    return edgeUnsettings;
  }
}

// Executes (primitive) deltas, and updates the graph state accordingly (through GraphStateListener)
// Decouples execution of deltas from any specific graph state representation (e.g. d3).
export class GraphState {

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

  // private readonly listener: GraphStateListener;

  // constructor(listener: GraphStateListener = DUMMY) {
  //   this.listener = listener;
  // }

  exec(delta: Delta, listener: GraphStateListener = DUMMY) {
    if (delta instanceof CompositeDelta) {
      delta.deltas.forEach(d => this.exec(d, listener));
    }
    else if (delta instanceof NodeCreation) {
      this.execNodeCreation(delta, listener);
    }
    else if (delta instanceof NodeDeletion) {
      this.execNodeDeletion(delta, listener);
    }
    else if (delta instanceof EdgeCreation) {
      this.execEdgeCreation(delta, listener);
    }
    else if (delta instanceof EdgeUpdate) {
      this.execEdgeUpdate(delta, listener);
    }
    else {
      throw new Error("Assertion failed: Unexpected delta type");
    }
  }
  unexec(delta: Delta, listener: GraphStateListener = DUMMY) {
    if (delta instanceof CompositeDelta) {
      // must un-exec them in reverse order:
      delta.deltas.reduceRight((_, currentDelta) => {this.unexec(currentDelta, listener); return null;}, null);
    }
    else if (delta instanceof NodeCreation) {
      this.unexecNodeCreation(delta, listener);
    }
    else if (delta instanceof NodeDeletion) {
      this.unexecNodeDeletion(delta, listener);
    }
    else if (delta instanceof EdgeCreation) {
      this.unexecEdgeCreation(delta, listener);
    }
    else if (delta instanceof EdgeUpdate) {
      this.unexecEdgeUpdate(delta, listener);
    }
    else {
      throw new Error("Assertion failed: Unexpected delta type");
    }
  }

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

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

  execNodeDeletion(delta: NodeDeletion, listener: GraphStateListener) {
    // console.log("execNodeDeletion", delta)
    const id = delta.creation.id.value;
    const nodeState = this.nodes.get(id);
    if (nodeState === undefined) {
      throw new Error("Assertion failed: deleted node does not exist")
    }
    // For every outgoing edge of deleted node, replace in the target node the incoming edge operation by the deletion:
    for (const outgoingEdgeOperation of nodeState.outgoing.values()) {
      const target = outgoingEdgeOperation.target.getTarget();
      const targetState = this._getEdgeTargetState(target);
      if (targetState !== undefined) {
        targetState.replaceIncoming(outgoingEdgeOperation, delta, listener);
        const outgoingEdgeCreation = outgoingEdgeOperation.getCreation();
        const sourceId = outgoingEdgeCreation.source.id.value;
        const label = outgoingEdgeCreation.label;
        listener.deleteLink(sourceId, label);
      }
    }
    listener.deleteNode(id);
  }
  unexecNodeDeletion(delta: NodeDeletion, listener: GraphStateListener) {
    // restore outgoing links
    const id = delta.creation.id.value;
    const nodeState = this.nodes.get(id);
    if (nodeState === undefined) {
      throw new Error("Assertion failed: deleted node does not exist")
    }
    listener.createNode(nodeState);
    // For every outgoing edge of deleted node, restore in the target node the incoming edge operation by whatever was there before
    for (const outgoingEdgeOperation of nodeState.outgoing.values()) {
      const target = outgoingEdgeOperation.target.getTarget();
      const targetState = this._getEdgeTargetState(target);
      if (targetState !== undefined) {
        targetState.replaceIncoming(delta, outgoingEdgeOperation, listener);
        const outgoingEdgeCreation = outgoingEdgeOperation.getCreation();
        const sourceId = outgoingEdgeCreation.source.id.value;
        const label = outgoingEdgeCreation.label;
        targetState.createLinkTo(sourceId, label, listener);
      }
    }
  }

  execEdgeCreation(delta: EdgeCreation, listener: GraphStateListener) {
    // console.log("execEdgeCreation", delta)
    const sourceId = delta.source.id.value;
    const target = delta.target.getTarget();
    if (target === null) {
      throw new Error("Assertion failed: EdgeCreation never sets edge target to null.");
    }
    const targetState = this._getEdgeTargetState(target);
    const label = delta.label;
    const sourceState = this.nodes.get(sourceId);
    if (sourceState === undefined) {
      throw new Error("Assertion failed: Source node is non-existing.")
    }
    if (targetState === undefined) {
      throw new Error("Assertion failed: Target node is non-existing.");
    }
    sourceState.outgoing.set(label, delta);
    sourceState.outgoingStates.set(label, targetState);
    targetState.addIncoming(delta, listener);
    targetState.incomingStates.push([label, sourceState]);
    targetState.createLinkTo(sourceId, label, listener);
  }
  unexecEdgeCreation(delta: EdgeCreation, listener: GraphStateListener) {
    const sourceId = delta.source.id.value;
    const target = delta.target.getTarget();
    if (target === null) {
      throw new Error("Assertion failed: EdgeCreation never sets edge target to null.");
    }
    const label = delta.label;
    const sourceState = this.nodes.get(sourceId);
    const targetState = this._getEdgeTargetState(target);
    if (sourceState === undefined) {
      throw new Error("Assertion failed: Source node is non-existing.")
    }
    if (targetState === undefined) {
      throw new Error("Assertion failed: Target node is non-existing.");
    }
    sourceState.outgoing.delete(label);
    sourceState.outgoingStates.delete(label);
    targetState.removeIncoming(delta, listener);
    targetState.incomingStates.splice(targetState.incomingStates.findIndex(([l,s]) => l===label && s===sourceState), 1);
    listener.deleteLink(sourceId, label);
  }

  execEdgeUpdate(delta: EdgeUpdate, listener: GraphStateListener) {
    // console.log("execEdgeUpdate", delta)
    // Delete link to old target
    const edgeCreation = delta.getCreation();
    const sourceId = edgeCreation.source.id.value;
    const label = edgeCreation.label;
    const overwrittenEdgeOperation = delta.overwrites;
    const sourceState = this.nodes.get(sourceId);
    if (sourceState === undefined) {
      throw new Error("Assertion failed: Must have sourceState.");
    }
    // Delete link to old target
    const oldTarget = overwrittenEdgeOperation.target.getTarget();
    if (oldTarget !== null) {
      // The old target was a node
      const oldTargetState = this._getEdgeTargetState(oldTarget);
      // Delete from old target's incoming edges:
      if (oldTargetState !== undefined) {
        oldTargetState.replaceIncoming(overwrittenEdgeOperation, delta, listener);
        oldTargetState.incomingStates.splice(oldTargetState.incomingStates.findIndex(([l,s]) => l===label && s===sourceState), 1);
        listener.deleteLink(sourceId, label);
      }
    }
    // Create link to new target (if there is a target)
    const newTarget = delta.target.getTarget();
    if (newTarget !== null) {
      // The new target is a node
      const newTargetState = this._getEdgeTargetState(newTarget);
      // Add to new target's incoming edges
      if (newTargetState !== undefined) {
        if (newTarget !== oldTarget) { // if newTarget === oldTarget, the 'delta' is already part of 'incoming'
          newTargetState.addIncoming(delta, listener);
        }
        newTargetState.incomingStates.push([label, sourceState]);
        newTargetState.createLinkTo(sourceId, label, listener);
        sourceState.outgoingStates.set(label, newTargetState);
      }
    } else {
      sourceState.outgoingStates.delete(label);
    }
    sourceState.outgoing.set(label, delta);
  }
  unexecEdgeUpdate(delta: EdgeUpdate, listener: GraphStateListener) {
    // console.log("execEdgeUpdate", delta)
    // Delete link to old target
    const edgeCreation = delta.getCreation();
    const sourceId = edgeCreation.source.id.value;
    const label = edgeCreation.label;
    const overwrittenEdgeOperation = delta.overwrites;
    const sourceState = this.nodes.get(sourceId);
    if (sourceState === undefined) {
      throw new Error("Assertion failed: Must have sourceState.");
    }
    // Delete link to new target (if there is a target)
    const newTarget = delta.target.getTarget();
    if (newTarget !== null) {
      // The new target is a node
      const newTargetState = this._getEdgeTargetState(newTarget);
      // Add to new target's incoming edges
      if (newTargetState !== undefined) {
        newTargetState.removeIncoming(delta, listener);
        newTargetState.incomingStates.splice(newTargetState.incomingStates.findIndex(([l,s]) => l===label && s===sourceState), 1);
        listener.deleteLink(sourceId, label);
      }
    }
    // Restore link to old target
    const oldTarget = overwrittenEdgeOperation.target.getTarget();
    if (oldTarget !== null) {
      // The old target was a node
      const oldTargetState = this._getEdgeTargetState(oldTarget);
      // Delete from old target's incoming edges:
      if (oldTargetState !== undefined) {
        oldTargetState.replaceIncoming(delta, overwrittenEdgeOperation, listener);
        oldTargetState.incomingStates.push([label, sourceState]);
        oldTargetState.createLinkTo(sourceId, label, listener);
        sourceState.outgoingStates.set(label, oldTargetState);
      }
    } else {
      sourceState.outgoingStates.delete(label);
    }
    sourceState.outgoing.set(label, overwrittenEdgeOperation);
  }
}