tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

shortest-paths.js (2770B)

      1 /* This Source Code Form is subject to the terms of the Mozilla Public
      2 * License, v. 2.0. If a copy of the MPL was not distributed with this
      3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      4 "use strict";
      5 
      6 /**
      7 * Compress a set of paths leading to `target` into a single graph, returned as
      8 * a set of nodes and a set of edges.
      9 *
     10 * @param {NodeId} target
     11 *        The target node passed to `HeapSnapshot.computeShortestPaths`.
     12 *
     13 * @param {Array<Path>} paths
     14 *        An array of paths to `target`, as returned by
     15 *        `HeapSnapshot.computeShortestPaths`.
     16 *
     17 * @returns {object}
     18 *          An object with two properties:
     19 *          - edges: An array of unique objects of the form:
     20 *              {
     21 *                 from: <node ID>,
     22 *                 to: <node ID>,
     23 *                 name: <string or null>
     24 *              }
     25 *          - nodes: An array of unique node IDs. Every `from` and `to` id is
     26 *            guaranteed to be in this array exactly once.
     27 */
     28 exports.deduplicatePaths = function (target, paths) {
     29  // Use this structure to de-duplicate edges among many retaining paths from
     30  // start to target.
     31  //
     32  // Map<FromNodeId, Map<ToNodeId, Set<EdgeName>>>
     33  const deduped = new Map();
     34 
     35  function insert(from, to, name) {
     36    let toMap = deduped.get(from);
     37    if (!toMap) {
     38      toMap = new Map();
     39      deduped.set(from, toMap);
     40    }
     41 
     42    let nameSet = toMap.get(to);
     43    if (!nameSet) {
     44      nameSet = new Set();
     45      toMap.set(to, nameSet);
     46    }
     47 
     48    nameSet.add(name);
     49  }
     50 
     51  // eslint-disable-next-line no-labels
     52  outer: for (const path of paths) {
     53    const pathLength = path.length;
     54 
     55    // Check for duplicate predecessors in the path, and skip paths that contain
     56    // them.
     57    const predecessorsSeen = new Set();
     58    predecessorsSeen.add(target);
     59    for (let i = 0; i < pathLength; i++) {
     60      if (predecessorsSeen.has(path[i].predecessor)) {
     61        // eslint-disable-next-line no-labels
     62        continue outer;
     63      }
     64      predecessorsSeen.add(path[i].predecessor);
     65    }
     66 
     67    for (let i = 0; i < pathLength - 1; i++) {
     68      insert(path[i].predecessor, path[i + 1].predecessor, path[i].edge);
     69    }
     70 
     71    insert(path[pathLength - 1].predecessor, target, path[pathLength - 1].edge);
     72  }
     73 
     74  const nodes = [target];
     75  const edges = [];
     76 
     77  for (const [from, toMap] of deduped) {
     78    // If the second/third/etc shortest path contains the `target` anywhere
     79    // other than the very last node, we could accidentally put the `target` in
     80    // `nodes` more than once.
     81    if (from !== target) {
     82      nodes.push(from);
     83    }
     84 
     85    for (const [to, edgeNameSet] of toMap) {
     86      for (const name of edgeNameSet) {
     87        edges.push({ from, to, name });
     88      }
     89    }
     90  }
     91 
     92  return { nodes, edges };
     93 };