summaryrefslogtreecommitdiffstats
path: root/devtools/shared/heapsnapshot/shortest-paths.js
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /devtools/shared/heapsnapshot/shortest-paths.js
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'devtools/shared/heapsnapshot/shortest-paths.js')
-rw-r--r--devtools/shared/heapsnapshot/shortest-paths.js91
1 files changed, 91 insertions, 0 deletions
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 };
+};