onioncollab/src/parser/rountangle_parser.ts

import {Delta, PrimitiveDelta} from "../onion/delta";
import {PrimitiveValue, UUID} from "../onion/types";
import {visitPartialOrdering} from "../util/partial_ordering";

import {
  NodeCreation,
  NodeDeletion,
  EdgeCreation,
  EdgeUpdate,
} from "../onion/delta";

import {DeltaRegistry} from "../onion/delta_registry";

import {
  GraphState,
  INodeState,
} from "../onion/graph_state";

export class ParseError extends Error {}

export interface Geometry2DRect {
  x: number;
  y: number;
  w: number;
  h: number;
}

const geometryLabels = ["x", "y", "width", "height"];

// Whether a is inside of b
export const isInside = (a: Geometry2DRect, b: Geometry2DRect): boolean => 
    a.x > b.x && a.y > b.y && a.x+a.w < b.x+b.w && a.y+a.h < b.y+b.h;

export function getGeometry(sourceState: GraphState, nodeId: PrimitiveValue): Geometry2DRect | undefined {
  const node = sourceState.nodes.get(nodeId);
  if (node !== undefined) {
    try {
      return {
        x: (node.getOutgoingEdges().get("x")!.asTarget()) as number,
        y: (node.getOutgoingEdges().get("y")!.asTarget()) as number,
        w: (node.getOutgoingEdges().get("width")!.asTarget()) as number,
        h: (node.getOutgoingEdges().get("height")!.asTarget()) as number,
      };
    }
    catch(e) {}
  }
}

// A parser that creates an AS-node for every CS-node, with a Corr-node in between.
export class RountangleParser  {
  readonly getUuid: () => UUID;

  readonly deltaRegistry: DeltaRegistry;

  constructor(deltaRegistry: DeltaRegistry, getUuid: () => UUID,
    /*compositeLvls: {csLvl: CompositeLevel, asLvl: CompositeLevel, corrLvl: CompositeLevel}*/) {
    this.deltaRegistry = deltaRegistry;
    this.getUuid = getUuid;
  }

  // We can use pretty much the same code for both parsing and rendering :)
  propagate_change(parse: boolean, sourceDeltas: PrimitiveDelta[], sourceState: GraphState, corrState: GraphState, targetState: GraphState) {
    const targetDeltas: Delta[] = []; // deltas that are only part of target model
    const corrDeltas: Delta[] = []; // deltas that are part of correspondence model, but NOT target model

    const sourceOverrides: Map<Delta,Delta> = new Map();
    const targetOverrides: Map<Delta,Delta> = new Map();

    const corr2SourceLabel = parse ? "cs" : "as";
    const corr2TargetLabel = parse ? "as" : "cs";

    // In order to parse, the CS/CORR/AS-state may be altered in-place.
    // Whenever the state is altered, a callback must be pushed to this array that undoes the change.
    // const revertState: (()=>void)[] = [];

    const applyToState = (state: GraphState, delta: PrimitiveDelta | PrimitiveDelta[]) => {
      if (Array.isArray(delta)) {
        delta.forEach(d => applyToState(state, d));
      }
      else {
        state.exec(delta);
        // revertState.push(() => state.unexec(delta));
      }
    }

    let complete = true; // is parsing/rendering complete, or do we need manual adjustment? (for missing geometry information)

    try {
      for (const sourceDelta of sourceDeltas) {
        // We'll update the sourceState, in-place, for every delta that we are parsing/rendering
        applyToState(sourceState, sourceDelta);

        if (sourceDelta instanceof NodeCreation) {

          // Creations are easy, and never cause conflicts:
          const sourceCreation = sourceDelta; // alias for readability :)
          const corrCreation = this.deltaRegistry.newNodeCreation(this.getUuid());
          const corr2Source = this.deltaRegistry.newEdgeCreation(corrCreation, corr2SourceLabel, sourceCreation);
          const targetCreation = this.deltaRegistry.newNodeCreation(this.getUuid());
          const corr2Target = this.deltaRegistry.newEdgeCreation(corrCreation, corr2TargetLabel, targetCreation);

          // We also update the corrState, in-place, for every change that is the result of parsing/rendering
          applyToState(corrState, sourceCreation);
          applyToState(corrState, targetCreation);
          applyToState(corrState, [corrCreation, corr2Source, corr2Target]);

          corrDeltas.push(corrCreation, corr2Source, corr2Target);
          targetDeltas.push(targetCreation);

          if (!parse) {
            // generate a Rountangle with some default geometry:
            const edges: [string,PrimitiveValue][] = [
              ["type", "Rountangle"],
              // ["label", ""],
              ["x", 0],
              ["y", 0],
              ["z-index", 0],
              ["width", 100],
              ["height", 60],
            ];
            targetDeltas.push(...edges.map(([edgeLabel, value]) =>
              this.deltaRegistry.newEdgeCreation(targetCreation, edgeLabel, value)));

            complete = false; // actual geometry of new rountangle to be determined by user
          }
        }
        else if (sourceDelta instanceof NodeDeletion) {
          const sourceDeletion = sourceDelta; // alias for readability :)
          const sourceCreation = sourceDeletion.creation; // the NodeCreation of the deleted cs node
          const sourceId = sourceCreation.id.value;

          // Follow 'cs'/'as' edges in correspondence model to find the corresponding node:
          const sourceNodeState = corrState.nodes.get(sourceId)!;
          const [_, corrNodeState] = sourceNodeState.getIncomingEdges().find(([label, nodeState]) => label === corr2SourceLabel)!;
          const targetNodeState = corrNodeState.getOutgoingEdges().get(corr2TargetLabel) as INodeState;

          // Deletion of correspondence node, and its outgoing ('cs', 'as') edges:
          const corrDeletion = corrNodeState.getDeltasForDelete(this.deltaRegistry);

          // The following operations on corrState depend on 'corrDeletion'. That's why update corrState now. We'll undo these changes later.
          applyToState(corrState, corrDeletion);

          // We create 2 asDeletions:
          // one that is to be used only in the AS model, unaware of any CORR-stuff, and one that is to be used in the CORR model.
          const targetDeletion = targetState.nodes.get(targetNodeState.creation.id.value)!.getDeltasForDelete(this.deltaRegistry);
          const targetDeletion1 = targetNodeState.getDeltasForDelete(this.deltaRegistry);

          applyToState(corrState, targetDeletion1);

          // We already have the deletion in the CS model, so we only need to create another one to be used in the CORR model:
          const sourceDeletion1 = sourceNodeState.getDeltasForDelete(this.deltaRegistry);

          applyToState(corrState, sourceDeletion1);

          sourceOverrides.set(sourceDeletion, sourceDeletion1[sourceDeletion1.length-1]);
          targetOverrides.set(targetDeletion[targetDeletion.length-1], targetDeletion1[targetDeletion1.length-1]);

          targetDeltas.push(...targetDeletion);
          corrDeltas.push(...corrDeletion);
        }
        else { // sourceDelta is EdgeCreation or EdgeUpdate
          if (!parse) {
            // Special case: an edge is being deleted (i.e., its target is set to null) and the previous target of the edge is a node that's being deleted - in this case, we *can* render the result (and we don't even have to do anything).
            if (sourceDelta instanceof EdgeUpdate) {
              const target = sourceDelta.target.getTarget();
              if (target === null) {
                const prevTarget = sourceDelta.overwrites.target.getTarget();
                if (sourceDeltas.some(d => d instanceof NodeDeletion && d.creation === prevTarget)) {
                  continue;
                }
              }
            }

            // parent edge updated: need to update geometry: (manually)
            complete = false;
            continue;
          }

          const edgeCreation = (sourceDelta as (EdgeCreation | EdgeUpdate)).getCreation();
          const label = edgeCreation.label;

          function findCorrespondingAsNode(csNode: INodeState, reverse: boolean = false) {
            const pair = csNode.getIncomingEdges().find(([label]) => label===(reverse?"as":"cs"));
            if (pair === undefined) {
              throw new Error("No incoming 'cs' edge.");
            }
            const [_, corrNodeState] = pair;
            const asState = corrNodeState.getOutgoingEdges().get(reverse?"cs":"as");
            if (asState === undefined) {
              throw new Error("Found correspondence node, but it has no outgoing 'as' edge.")
            }
            return asState as INodeState;
          }

          if (geometryLabels.includes(label)) {
            const updatedNodeId = edgeCreation.source.id.value;
            const updatedGeometry = getGeometry(sourceState, updatedNodeId);
            if (updatedGeometry !== undefined) {
              const updatedSurface = updatedGeometry.w * updatedGeometry.h;
              const updatedAsNode = findCorrespondingAsNode(corrState.nodes.get(updatedNodeId) as INodeState);

              const findAndSetNewParent = (geometry: Geometry2DRect, asNodeState: INodeState) => {
                const surface = geometry.w * geometry.h;
                // Of all other geometries that we are inside of, find the one with the smallest surface area.
                // This will be our new parent.
                let smallestParent: INodeState | null = null;
                let smallestSurface = Infinity;
                for (const [otherNodeId,otherNodeState] of sourceState.nodes.entries()) {
                  if (otherNodeState.isDeleted) {
                    continue; // skip deleted rountangles
                  }
                  if (otherNodeState.creation === edgeCreation.source) {
                    continue; // don't compare with ourselves
                  }
                  const otherGeometry = getGeometry(sourceState, otherNodeId);
                  if (otherGeometry !== undefined) {
                    const inside = isInside(geometry, otherGeometry);
                    if (inside) {
                      const surface = otherGeometry.w * otherGeometry.h;
                      if (surface < smallestSurface) {
                        smallestSurface = surface;
                        smallestParent = findCorrespondingAsNode(corrState.nodes.get(otherNodeId) as INodeState);
                      }
                    }
                  }
                }
                if (smallestParent !== null) {
                  const existingLink = asNodeState.getOutgoingEdges().get("hasParent");
                  if (existingLink !== smallestParent) {
                    // console.log("updated geometry is on inside...");
                    const asParentLink = asNodeState.getDeltasForSetEdge(this.deltaRegistry, "hasParent", smallestParent.asTarget());
                    applyToState(corrState, asParentLink);
                    targetDeltas.push(...asParentLink);
                  }
                }
              }

              // 1. Check if existing parent links still hold
              // 1.a. outgoing parent links
              const otherAsNodeState = updatedAsNode.getOutgoingEdges().get("hasParent");
              if (otherAsNodeState !== undefined && otherAsNodeState.type === "node") {
                const otherCsNodeState = findCorrespondingAsNode(otherAsNodeState, true);
                const otherNodeId = otherCsNodeState.creation.id.value;
                const otherGeometry = getGeometry(sourceState, otherNodeId);
                if (otherGeometry === undefined || !isInside(updatedGeometry, otherGeometry)) {
                  // parent relation no longer holds
                  // console.log("deleting outgoing link...")
                  // CORRECT: we'll find updatedAsNode's new parent in step 2.
                  const deleteLink = updatedAsNode.getDeltasForSetEdge(this.deltaRegistry, "hasParent", null); // deletes the edge
                  applyToState(corrState, deleteLink);
                  targetDeltas.push(...deleteLink);
                }
              }
              // 1.b. incoming parent links
              for (const [_, otherAsNodeState] of updatedAsNode.getIncomingEdges().filter(([label, ns]) => label === "hasParent")) {
                const otherCsNodeState = findCorrespondingAsNode(otherAsNodeState, true);
                const otherNodeId = otherCsNodeState.creation.id.value;
                const otherGeometry = getGeometry(sourceState, otherNodeId);
                if (otherGeometry === undefined) {
                  throw new Error("Assertion failed: The Corresponding CS node of an AS node that is target of 'hasParent' has no geometry.");
                }
                if (!isInside(otherGeometry, updatedGeometry)) {
                  // parent relation no longer holds
                  const otherAsNode = findCorrespondingAsNode(corrState.nodes.get(otherNodeId) as INodeState);
                  console.log("deleting incoming link...")
                  // WRONG (TODO): must also find otherAsNode's new parent.
                  const deleteLink = otherAsNode.getDeltasForSetEdge(this.deltaRegistry, "hasParent", null); // deletes the edge
                  applyToState(corrState, deleteLink);
                  targetDeltas.push(...deleteLink);
                  // Find new parent of otherAsNode:
                  findAndSetNewParent(otherGeometry, otherAsNode);
                  // The above function call leads to time complexity O(n^2) for parsing.
                  // There should be ways to make it more efficient (e.g., keeping all rountangles sorted by their surface area, in order to find the new parent much quicker), but for our demonstrator, the bottleneck is React/d3, not the parsing/rendering process.
                }
              }

              // 2. Compare the new geometry to every other rountangle
              for (const [otherNodeId,otherNodeState] of sourceState.nodes.entries()) {
                if (otherNodeState.isDeleted) {
                  continue; // no point comparing ourselves with deleted rountangles
                }
                if (otherNodeState.creation === edgeCreation.source) {
                  continue; // don't compare with ourselves
                }
                const otherGeometry = getGeometry(sourceState, otherNodeId);
                if (otherGeometry !== undefined) {
                  findAndSetNewParent(updatedGeometry, updatedAsNode);
                  const outside = isInside(otherGeometry, updatedGeometry);
                  // CORRECT: For geometries that are inside of our updated geometry, we should only "steal" their outgoing parent link if our updated geometry is smaller than their current parent.
                  if (outside) {
                    const otherAsNode = findCorrespondingAsNode(corrState.nodes.get(otherNodeId) as INodeState);
                    const otherCurrentParent = otherAsNode.getOutgoingEdges().get("hasParent");
                    const otherCurrentParentSurface = (() => {
                      // find surface area of existing parent of other geometry...
                      if (otherCurrentParent === undefined || otherCurrentParent.type !== "node") {
                        return Infinity;
                      }
                      const otherCurrentParentCs = findCorrespondingAsNode(otherCurrentParent as INodeState, true);
                      const otherCurrentParentGeometry = getGeometry(sourceState, otherCurrentParentCs.creation.id.value);
                      if (otherCurrentParentGeometry === undefined) {
                        return Infinity;
                      }
                      return otherCurrentParentGeometry.w * otherCurrentParentGeometry.h;
                    })();
                    if (updatedSurface < otherCurrentParentSurface) {
                      // console.log("updated geometry is on outside...");
                      const asParentLink = otherAsNode.getDeltasForSetEdge(this.deltaRegistry, "hasParent", updatedAsNode.asTarget());
                      applyToState(corrState, asParentLink);
                      targetDeltas.push(...asParentLink);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    finally {
      // Rollback all changes that were made (in-place) to the CS/CORR/AS-state
      // revertState.reduceRight((_,callback) => {callback(); return null;}, null);
    }

    const corrDeltasOrderedByDependency: PrimitiveDelta[] = [];
    visitPartialOrdering([
      ...sourceDeltas.map(d => sourceOverrides.get(d) || d),
      ...targetDeltas.map(d => targetOverrides.get(d) || d),
      ...corrDeltas],
      (d: Delta) => d.getDependencies(),
      (d: Delta) => corrDeltasOrderedByDependency.push(d)
    );


    const result = {
      corrDeltas: corrDeltasOrderedByDependency,
      targetDeltas,
      sourceOverrides,
      targetOverrides,
      complete,
    };
    // console.log(result);
    return result;
  }

  parse(csDeltas: PrimitiveDelta[], csState: GraphState, corrState: GraphState, asState: GraphState) {
    const {
      corrDeltas,
      targetDeltas,
      sourceOverrides: csOverrides,
      targetOverrides: asOverrides,
      complete,
    } = this.propagate_change(true, csDeltas, csState, corrState, asState);

    return { corrDeltas, asDeltas: targetDeltas, csOverrides, asOverrides, complete };
  }

  render(asDeltas: PrimitiveDelta[], csState: GraphState, corrState: GraphState, asState: GraphState) {
    const {
      corrDeltas,
      targetDeltas,
      sourceOverrides: asOverrides,
      targetOverrides: csOverrides,
      complete,
    } = this.propagate_change(false, asDeltas, asState, corrState, csState);

    return { corrDeltas, csDeltas: targetDeltas, csOverrides, asOverrides, complete };
  }
}