onioncollab/graph_state.ts

// NodeJS libraries
import {inspect} from "util";

type PrimitiveType = string | number | boolean;

// This class is here to distinguish UUIDs from ordinary strings
export class UUID {
  uuid: PrimitiveType;
  
  constructor(uuid: PrimitiveType) {
    this.uuid = uuid;
  }

  [inspect.custom](depth: number, options: object) {
    return "UUID{" + inspect(this.uuid, options) + "}"
  }
}

type NodeId = PrimitiveType | UUID;

function nodeIdsEqual(a: NodeId, b: NodeId) {
  if (a === b) return true;
  if (a instanceof UUID && b instanceof UUID) {
    return a.uuid === b.uuid;
  }
}

// In- and outgoing edges of a node.
// This is the only place where edges are recorded.
// Every edge corresponds to one entry in the source's 'outgoing', and one entry in the target's 'incoming'.
class Node {
  outgoing: Map<string, NodeId>;
  incoming: Array<{label: string, srcId: NodeId}>;

  constructor() {
    this.outgoing = new Map();
    this.incoming = [];
  }
}

// Helper class. Stores all nodes.
class NodeMap {
  // ordinary nodes: they are created and deleted
  nodes: Map<PrimitiveType, Node>;

  // value nodes: we pretend that they always already exist
  values: Map<PrimitiveType, Node>;

  constructor() {
    this.nodes = new Map();
    this.values = new Map();
  }

  getOptional(id: NodeId): Node | undefined {
    if (id instanceof UUID) {
      // ordinary node: can only get it if it actually exists,
      // i.e., it has already been created and has not yet been deleted.
      return this.nodes.get(id.uuid); // may return undefined
    }

    // value node: implicitly create it if it doesn't exist yet,
    // pretending that it's "always already there"
    const v = this.values.get(id);
    if (v !== undefined) {
      return v;
    }
    // auto-construct non-existing value node
    const node = new Node();
    this.values.set(id, node);
    return node;
  }

  // same as get, but raises error when not found
  get(id: NodeId): Node {
    const node = this.getOptional(id);
    if (node === undefined) {
      throw Error("node not found");
    }
    return node;
  }

  // create a new ordinary node
  create(id: UUID): Node {
    const node = new Node();
    this.nodes.set(id.uuid, node);
    return node;
  }

  // delete an ordinary node
  // Idempotent.
  delete(id: UUID) {
    this.nodes.delete(id.uuid);
  }
}

type UUIDCallbackType = () => UUID;

export class GraphState {
  nodes: NodeMap;
  uuidCallback: UUIDCallbackType;

  constructor(uuidCallback: UUIDCallbackType) {
    this.nodes = new NodeMap();
    this.uuidCallback = uuidCallback;
  }

  // Create a new node.
  createNode(): UUID {
    const uuid = this.uuidCallback();
    this.nodes.create(uuid);
    return uuid;
  }

  // Delete node and delete all of its outgoing + incoming edges.
  // Does nothing when given uuid does not exist.
  // Idempotent.
  deleteNode(uuid: UUID) {
    const node = this.nodes.getOptional(uuid);
    if (node !== undefined) {
      // delete outgoing edges
      for (const [label, targetId] of node.outgoing.entries()) {
        const targetNode = this.nodes.get(targetId);
        // remove edge from targetNode.incoming
        const i = this.lookupIncoming(targetNode, label, uuid);
        targetNode.incoming.splice(i, 1);
      }
      // delete incoming edges
      for (const {label, srcId} of node.incoming) {
        const srcNode = this.nodes.get(srcId);
        // remove edge from srcNode.outgoing
        srcNode.outgoing.delete(label);
      }
      // delete node itself
      this.nodes.delete(uuid);      
    }
  }

  // Create or update a node's outgoing edge to point to a node
  // Idempotent.
  setEdge(srcId: NodeId, label: string, targetId: NodeId) {
    // gotta remove the existing edge first, if it exists
    this.deleteEdge(srcId, label);

    const srcNode = this.nodes.get(srcId);
    srcNode.outgoing.set(label, targetId);
    const targetNode = this.nodes.get(targetId);
    targetNode.incoming.push({label, srcId});
  }

  // Delete an edge.
  // Idempotent.
  deleteEdge(srcId: NodeId, label: string) {
    const srcNode = this.nodes.get(srcId);
    const existingTargetId = srcNode.outgoing.get(label);
    if (existingTargetId !== undefined) {
      // remove the respective entry in the existingTargetNode's 'incoming' array:
      const existingTargetNode = this.nodes.get(existingTargetId);
      const i = this.lookupIncoming(existingTargetNode, label, srcId);
      existingTargetNode.incoming.splice(i, 1); // remove from array
    }
    srcNode.outgoing.delete(label);
  }

  // In a node's array of incoming edges, search for {label, srcId}, and return the position in the array.
  private lookupIncoming(node: Node, label: string, srcId: NodeId): number {
    for (const [i, {label: l, srcId: s}] of node.incoming.entries()) {
      if (l === label && nodeIdsEqual(s, srcId)) {
        return i;
      }
    }
    throw new Error("Not found!");
  }

  // Read a node's outgoing edge with given label.
  // If no such edge exists, returns undefined.
  readEdge(srcId: NodeId, label: string): NodeId | undefined {
    const srcNode = this.nodes.getOptional(srcId);
    if (srcNode !== undefined) {
      return srcNode.outgoing.get(label);
    }
  }

  // Get all the edges in the graph. Slow. For debugging purposes.
  getEdges(): Array<[NodeId, NodeId, string]> {
    const result: Array<[NodeId, NodeId, string]> = [];
    // get all outgoing edges of ordinary nodes
    for (const [srcId, srcNode] of this.nodes.nodes.entries()) {
      for (const [label, targetId] of srcNode.outgoing) {
        result.push([new UUID(srcId), targetId, label]);
      }
    }
    // get all outgoing edges of value nodes
    for (const [srcId, srcNode] of this.nodes.values.entries()) {
      for (const [label, targetId] of srcNode.outgoing) {
        result.push([srcId, targetId, label]);
      }
    }
    return result;
  }
}