From ba0011606d53b1f3fd00625b68aa3aa6e6f55332 Mon Sep 17 00:00:00 2001
From: "Matt A. Tobin" <email@mattatobin.com>
Date: Sun, 23 Feb 2020 10:38:36 -0500
Subject: Follow-up to 4e2e9be6a - Move HeapSnapshot DevTools-only Modules back
 to DevTools

I am so done with this.

Resolves #316
---
 devtools/shared/heapsnapshot/shortest-paths.js | 91 ++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
 create mode 100644 devtools/shared/heapsnapshot/shortest-paths.js

(limited to 'devtools/shared/heapsnapshot/shortest-paths.js')

diff --git a/devtools/shared/heapsnapshot/shortest-paths.js b/devtools/shared/heapsnapshot/shortest-paths.js
new file mode 100644
index 000000000..2d97b7de9
--- /dev/null
+++ b/devtools/shared/heapsnapshot/shortest-paths.js
@@ -0,0 +1,91 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+"use strict";
+
+/**
+ * Compress a set of paths leading to `target` into a single graph, returned as
+ * a set of nodes and a set of edges.
+ *
+ * @param {NodeId} target
+ *        The target node passed to `HeapSnapshot.computeShortestPaths`.
+ *
+ * @param {Array<Path>} paths
+ *        An array of paths to `target`, as returned by
+ *        `HeapSnapshot.computeShortestPaths`.
+ *
+ * @returns {Object}
+ *          An object with two properties:
+ *          - edges: An array of unique objects of the form:
+ *              {
+ *                 from: <node ID>,
+ *                 to: <node ID>,
+ *                 name: <string or null>
+ *              }
+ *          - nodes: An array of unique node IDs. Every `from` and `to` id is
+ *            guaranteed to be in this array exactly once.
+ */
+exports.deduplicatePaths = function (target, paths) {
+  // Use this structure to de-duplicate edges among many retaining paths from
+  // start to target.
+  //
+  // Map<FromNodeId, Map<ToNodeId, Set<EdgeName>>>
+  const deduped = new Map();
+
+  function insert(from, to, name) {
+    let toMap = deduped.get(from);
+    if (!toMap) {
+      toMap = new Map();
+      deduped.set(from, toMap);
+    }
+
+    let nameSet = toMap.get(to);
+    if (!nameSet) {
+      nameSet = new Set();
+      toMap.set(to, nameSet);
+    }
+
+    nameSet.add(name);
+  }
+
+  outer: for (let path of paths) {
+    const pathLength = path.length;
+
+    // Check for duplicate predecessors in the path, and skip paths that contain
+    // them.
+    const predecessorsSeen = new Set();
+    predecessorsSeen.add(target);
+    for (let i = 0; i < pathLength; i++) {
+      if (predecessorsSeen.has(path[i].predecessor)) {
+        continue outer;
+      }
+      predecessorsSeen.add(path[i].predecessor);
+    }
+
+    for (let i = 0; i < pathLength - 1; i++) {
+      insert(path[i].predecessor, path[i + 1].predecessor, path[i].edge);
+    }
+
+    insert(path[pathLength - 1].predecessor, target, path[pathLength - 1].edge);
+  }
+
+  const nodes = [target];
+  const edges = [];
+
+  for (let [from, toMap] of deduped) {
+    // If the second/third/etc shortest path contains the `target` anywhere
+    // other than the very last node, we could accidentally put the `target` in
+    // `nodes` more than once.
+    if (from !== target) {
+      nodes.push(from);
+    }
+
+    for (let [to, edgeNameSet] of toMap) {
+      for (let name of edgeNameSet) {
+        edges.push({ from, to, name });
+      }
+    }
+  }
+
+  return { nodes, edges };
+};
-- 
cgit v1.2.3