@parcel/core/lib/Graph.js

"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.mapVisitor = mapVisitor;
exports.default = exports.ALL_EDGE_TYPES = void 0;

var _assert = _interopRequireDefault(require("assert"));

var _utils = require("@parcel/utils");

var _nullthrows = _interopRequireDefault(require("nullthrows"));

function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }

function _defineProperty(obj, key, value) { if (key in obj) { Object.defineProperty(obj, key, { value: value, enumerable: true, configurable: true, writable: true }); } else { obj[key] = value; } return obj; }

const ALL_EDGE_TYPES = '@@all_edge_types';
exports.ALL_EDGE_TYPES = ALL_EDGE_TYPES;

class Graph {
  constructor(opts = {}) // flow is dumb
  {
    _defineProperty(this, "nodes", void 0);

    _defineProperty(this, "inboundEdges", new _utils.DefaultMap(() => new _utils.DefaultMap(() => new Set())));

    _defineProperty(this, "outboundEdges", new _utils.DefaultMap(() => new _utils.DefaultMap(() => new Set())));

    _defineProperty(this, "rootNodeId", void 0);

    this.nodes = opts.nodes || new Map();
    this.rootNodeId = opts.rootNodeId;

    if (opts.edges) {
      for (let edge of opts.edges) {
        this.addEdge(edge.from, edge.to, edge.type);
      }
    }
  }

  static deserialize(opts) {
    return new this(opts);
  }

  serialize() {
    return {
      nodes: this.nodes,
      edges: this.getAllEdges(),
      rootNodeId: this.rootNodeId
    };
  } // Returns a list of all edges in the graph. This can be large, so iterating
  // the complete list can be costly in large graphs. Used in serialization and
  // copying of graphs.


  getAllEdges() {
    let edges = [];

    for (let [from, edgeList] of this.outboundEdges) {
      for (let [type, toNodes] of edgeList) {
        for (let to of toNodes) {
          edges.push({
            from,
            to,
            type
          });
        }
      }
    }

    return edges;
  }

  addNode(node) {
    this.nodes.set(node.id, node);
    return node;
  }

  hasNode(id) {
    return this.nodes.has(id);
  }

  getNode(id) {
    return this.nodes.get(id);
  }

  setRootNode(node) {
    this.addNode(node);
    this.rootNodeId = node.id;
  }

  getRootNode() {
    return this.rootNodeId ? this.getNode(this.rootNodeId) : null;
  }

  addEdge(from, to, type = null) {
    if (!this.getNode(from)) {
      throw new Error(`"from" node '${from}' not found`);
    }

    if (!this.getNode(to)) {
      throw new Error(`"to" node '${to}' not found`);
    }

    this.outboundEdges.get(from).get(type).add(to);
    this.inboundEdges.get(to).get(type).add(from);
  }

  hasEdge(from, to, type = null) {
    return this.outboundEdges.get(from).get(type).has(to);
  }

  getNodesConnectedTo(node, type = null) {
    assertHasNode(this, node);
    let nodes;

    if (type === ALL_EDGE_TYPES) {
      nodes = new Set();

      for (let [, typeNodes] of this.inboundEdges.get(node.id)) {
        for (let node of typeNodes) {
          nodes.add(node);
        }
      }
    } else {
      nodes = this.inboundEdges.get(node.id).get(type).values();
    }

    return [...nodes].map(to => (0, _nullthrows.default)(this.nodes.get(to)));
  }

  getNodesConnectedFrom(node, type = null) {
    assertHasNode(this, node);
    let nodes;

    if (type === ALL_EDGE_TYPES) {
      nodes = new Set();

      for (let [, typeNodes] of this.outboundEdges.get(node.id)) {
        for (let node of typeNodes) {
          nodes.add(node);
        }
      }
    } else {
      nodes = this.outboundEdges.get(node.id).get(type).values();
    }

    return [...nodes].map(to => (0, _nullthrows.default)(this.nodes.get(to)));
  }

  merge(graph) {
    for (let [, node] of graph.nodes) {
      this.addNode(node);
    }

    for (let edge of graph.getAllEdges()) {
      this.addEdge(edge.from, edge.to, edge.type);
    }
  } // Removes node and any edges coming from or to that node


  removeNode(node) {
    assertHasNode(this, node);

    for (let [type, nodesForType] of this.inboundEdges.get(node.id)) {
      for (let from of nodesForType) {
        this.removeEdge(from, node.id, type, // Do not allow orphans to be removed as this node could be one
        // and is already being removed.
        false
        /* removeOrphans */
        );
      }
    }

    for (let [type, toNodes] of this.outboundEdges.get(node.id)) {
      for (let to of toNodes) {
        this.removeEdge(node.id, to, type);
      }
    }

    let wasRemoved = this.nodes.delete(node.id);
    (0, _assert.default)(wasRemoved);
  }

  removeById(id) {
    let node = (0, _nullthrows.default)(this.getNode(id));
    this.removeNode(node);
  }

  removeEdges(node, type = null) {
    assertHasNode(this, node);

    for (let to of this.outboundEdges.get(node.id).get(type)) {
      this.removeEdge(node.id, to, type);
    }
  } // Removes edge and node the edge is to if the node is orphaned


  removeEdge(from, to, type = null, removeOrphans = true) {
    if (!this.outboundEdges.get(from).get(type).has(to)) {
      throw new Error(`Outbound edge from ${from} to ${to} not found!`);
    }

    if (!this.inboundEdges.get(to).get(type).has(from)) {
      throw new Error(`Inbound edge from ${to} to ${from} not found!`);
    }

    this.outboundEdges.get(from).get(type).delete(to);
    this.inboundEdges.get(to).get(type).delete(from);
    let connectedNode = (0, _nullthrows.default)(this.nodes.get(to));

    if (removeOrphans && this.isOrphanedNode(connectedNode)) {
      this.removeNode(connectedNode);
    }
  }

  isOrphanedNode(node) {
    assertHasNode(this, node);
    let rootNode = this.getRootNode();

    if (rootNode == null) {
      // If the graph does not have a root, and there are inbound edges,
      // this node should not be considered orphaned.
      // return false;
      for (let [, inboundNodeIds] of this.inboundEdges.get(node.id)) {
        if (inboundNodeIds.size > 0) {
          return false;
        }
      }

      return true;
    } // Otherwise, attempt to traverse backwards to the root. If there is a path,
    // then this is not an orphaned node.


    let hasPathToRoot = false;
    this.traverseAncestors(node, (ancestor, _, actions) => {
      if (ancestor.id === rootNode.id) {
        hasPathToRoot = true;
        actions.stop();
      }
    }, // $FlowFixMe
    ALL_EDGE_TYPES);

    if (hasPathToRoot) {
      return false;
    }

    return true;
  }

  replaceNode(fromNode, toNode, type = null) {
    assertHasNode(this, fromNode);
    this.addNode(toNode);

    for (let parent of this.inboundEdges.get(fromNode.id).get(type)) {
      this.addEdge(parent, toNode.id, type);
      this.removeEdge(parent, fromNode.id, type);
    }

    this.removeNode(fromNode);
  } // Update a node's downstream nodes making sure to prune any orphaned branches


  replaceNodesConnectedTo(fromNode, toNodes, replaceFilter, type = null) {
    assertHasNode(this, fromNode);
    let outboundEdges = this.outboundEdges.get(fromNode.id).get(type);
    let childrenToRemove = new Set(replaceFilter ? [...outboundEdges].filter(toNodeId => replaceFilter((0, _nullthrows.default)(this.nodes.get(toNodeId)))) : outboundEdges);

    for (let toNode of toNodes) {
      this.addNode(toNode);
      childrenToRemove.delete(toNode.id);

      if (!this.hasEdge(fromNode.id, toNode.id, type)) {
        this.addEdge(fromNode.id, toNode.id, type);
      }
    }

    for (let child of childrenToRemove) {
      this.removeEdge(fromNode.id, child, type);
    }
  }

  traverse(visit, startNode, type = null) {
    return this.dfs({
      visit,
      startNode,
      getChildren: node => this.getNodesConnectedFrom(node, type)
    });
  }

  filteredTraverse(filter, visit, startNode, type) {
    return this.traverse(mapVisitor(filter, visit), startNode, type);
  }

  traverseAncestors(startNode, visit, type = null) {
    return this.dfs({
      visit,
      startNode,
      getChildren: node => this.getNodesConnectedTo(node, type)
    });
  }

  dfs({
    visit,
    startNode,
    getChildren
  }) {
    let root = startNode !== null && startNode !== void 0 ? startNode : this.getRootNode();

    if (root == null) {
      throw new Error('A start node is required to traverse');
    }

    assertHasNode(this, root);
    let visited = new Set();
    let stopped = false;
    let skipped = false;
    let actions = {
      skipChildren() {
        skipped = true;
      },

      stop() {
        stopped = true;
      }

    };

    let walk = (node, context) => {
      visited.add(node);
      skipped = false;
      let enter = typeof visit === 'function' ? visit : visit.enter;

      if (enter) {
        let newContext = enter(node, context, actions);

        if (typeof newContext !== 'undefined') {
          context = newContext;
        }
      }

      if (skipped) {
        return;
      }

      if (stopped) {
        return context;
      }

      for (let child of getChildren(node)) {
        if (visited.has(child)) {
          continue;
        }

        visited.add(child);
        let result = walk(child, context);

        if (stopped) {
          return result;
        }
      }

      if (typeof visit !== 'function' && visit.exit) {
        let newContext = visit.exit(node, context, actions);

        if (typeof newContext !== 'undefined') {
          context = newContext;
        }
      }

      if (skipped) {
        return;
      }

      if (stopped) {
        return context;
      }
    };

    return walk(root);
  }

  bfs(visit) {
    let root = this.getRootNode();

    if (!root) {
      throw new Error('A root node is required to traverse');
    }

    let queue = [root];
    let visited = new Set([root]);

    while (queue.length > 0) {
      let node = queue.shift();
      let stop = visit(node);

      if (stop === true) {
        return node;
      }

      for (let child of this.getNodesConnectedFrom(node)) {
        if (!visited.has(child)) {
          visited.add(child);
          queue.push(child);
        }
      }
    }

    return null;
  }

  getSubGraph(node) {
    let graph = new this.constructor();
    graph.setRootNode(node);
    let nodes = [];
    this.traverse(node => {
      nodes.push(node);
      graph.addNode(node);
    }, node);

    for (let node of nodes) {
      for (let [type, toNodes] of this.outboundEdges.get(node.id)) {
        for (let to of toNodes) {
          graph.addEdge(node.id, to, type);
        }
      }
    }

    return graph;
  }

  findAncestor(node, fn) {
    let res = null;
    this.traverseAncestors(node, (node, ctx, traversal) => {
      if (fn(node)) {
        res = node;
        traversal.stop();
      }
    });
    return res;
  }

  findAncestors(node, fn) {
    let res = [];
    this.traverseAncestors(node, (node, ctx, traversal) => {
      if (fn(node)) {
        res.push(node);
        traversal.skipChildren();
      }
    });
    return res;
  }

  findDescendant(node, fn) {
    let res = null;
    this.traverse((node, ctx, traversal) => {
      if (fn(node)) {
        res = node;
        traversal.stop();
      }
    }, node);
    return res;
  }

  findDescendants(node, fn) {
    let res = [];
    this.traverse((node, ctx, traversal) => {
      if (fn(node)) {
        res.push(node);
        traversal.skipChildren();
      }
    }, node);
    return res;
  }

  findNode(predicate) {
    return Array.from(this.nodes.values()).find(predicate);
  }

  findNodes(predicate) {
    return Array.from(this.nodes.values()).filter(predicate);
  }

}

exports.default = Graph;

function mapVisitor(filter, visit) {
  return {
    enter: (node, context, actions) => {
      let enter = typeof visit === 'function' ? visit : visit.enter;

      if (!enter) {
        return;
      }

      let value = filter(node, actions);

      if (value != null) {
        return enter(value, context, actions);
      }
    },
    exit: (node, context, actions) => {
      if (typeof visit === 'function') {
        return;
      }

      let exit = visit.exit;

      if (!exit) {
        return;
      }

      let value = filter(node, actions);

      if (value != null) {
        return exit(value, context, actions);
      }
    }
  };
}

function assertHasNode(graph, node) {
  if (!graph.hasNode(node.id)) {
    throw new Error('Does not have node ' + node.id);
  }
}