summaryrefslogtreecommitdiffstats
path: root/devtools/shared/heapsnapshot
diff options
context:
space:
mode:
Diffstat (limited to 'devtools/shared/heapsnapshot')
-rw-r--r--devtools/shared/heapsnapshot/CensusUtils.js489
-rw-r--r--devtools/shared/heapsnapshot/DominatorTreeNode.js336
-rw-r--r--devtools/shared/heapsnapshot/HeapAnalysesClient.js277
-rw-r--r--devtools/shared/heapsnapshot/HeapAnalysesWorker.js303
-rw-r--r--devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js95
-rw-r--r--devtools/shared/heapsnapshot/census-tree-node.js748
-rw-r--r--devtools/shared/heapsnapshot/moz.build15
-rw-r--r--devtools/shared/heapsnapshot/shortest-paths.js91
8 files changed, 2354 insertions, 0 deletions
diff --git a/devtools/shared/heapsnapshot/CensusUtils.js b/devtools/shared/heapsnapshot/CensusUtils.js
new file mode 100644
index 000000000..36bdd2d82
--- /dev/null
+++ b/devtools/shared/heapsnapshot/CensusUtils.js
@@ -0,0 +1,489 @@
+/* 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";
+
+const { flatten } = require("resource://devtools/shared/ThreadSafeDevToolsUtils.js");
+
+/** * Visitor ****************************************************************/
+
+/**
+ * A Visitor visits each node and edge of a census report tree as the census
+ * report is being traversed by `walk`.
+ */
+function Visitor() { }
+exports.Visitor = Visitor;
+
+/**
+ * The `enter` method is called when a new sub-report is entered in traversal.
+ *
+ * @param {Object} breakdown
+ * The breakdown for the sub-report that is being entered by traversal.
+ *
+ * @param {Object} report
+ * The report generated by the given breakdown.
+ *
+ * @param {any} edge
+ * The edge leading to this sub-report. The edge is null if (but not iff!
+ * eg, null allocation stack edges) we are entering the root report.
+ */
+Visitor.prototype.enter = function (breakdown, report, edge) { };
+
+/**
+ * The `exit` method is called when traversal of a sub-report has finished.
+ *
+ * @param {Object} breakdown
+ * The breakdown for the sub-report whose traversal has finished.
+ *
+ * @param {Object} report
+ * The report generated by the given breakdown.
+ *
+ * @param {any} edge
+ * The edge leading to this sub-report. The edge is null if (but not iff!
+ * eg, null allocation stack edges) we are entering the root report.
+ */
+Visitor.prototype.exit = function (breakdown, report, edge) { };
+
+/**
+ * The `count` method is called when leaf nodes (reports whose breakdown is
+ * by: "count") in the report tree are encountered.
+ *
+ * @param {Object} breakdown
+ * The count breakdown for this report.
+ *
+ * @param {Object} report
+ * The report generated by a breakdown by "count".
+ *
+ * @param {any|null} edge
+ * The edge leading to this count report. The edge is null if we are
+ * entering the root report.
+ */
+Visitor.prototype.count = function (breakdown, report, edge) { };
+
+/** * getReportEdges *********************************************************/
+
+const EDGES = Object.create(null);
+
+EDGES.count = function (breakdown, report) {
+ return [];
+};
+
+EDGES.bucket = function (breakdown, report) {
+ return [];
+};
+
+EDGES.internalType = function (breakdown, report) {
+ return Object.keys(report).map(key => ({
+ edge: key,
+ referent: report[key],
+ breakdown: breakdown.then
+ }));
+};
+
+EDGES.objectClass = function (breakdown, report) {
+ return Object.keys(report).map(key => ({
+ edge: key,
+ referent: report[key],
+ breakdown: key === "other" ? breakdown.other : breakdown.then
+ }));
+};
+
+EDGES.coarseType = function (breakdown, report) {
+ return [
+ { edge: "objects", referent: report.objects, breakdown: breakdown.objects },
+ { edge: "scripts", referent: report.scripts, breakdown: breakdown.scripts },
+ { edge: "strings", referent: report.strings, breakdown: breakdown.strings },
+ { edge: "other", referent: report.other, breakdown: breakdown.other },
+ ];
+};
+
+EDGES.allocationStack = function (breakdown, report) {
+ const edges = [];
+ report.forEach((value, key) => {
+ edges.push({
+ edge: key,
+ referent: value,
+ breakdown: key === "noStack" ? breakdown.noStack : breakdown.then
+ });
+ });
+ return edges;
+};
+
+EDGES.filename = function (breakdown, report) {
+ return Object.keys(report).map(key => ({
+ edge: key,
+ referent: report[key],
+ breakdown: key === "noFilename" ? breakdown.noFilename : breakdown.then
+ }));
+};
+
+/**
+ * Get the set of outgoing edges from `report` as specified by the given
+ * breakdown.
+ *
+ * @param {Object} breakdown
+ * The census breakdown.
+ *
+ * @param {Object} report
+ * The census report.
+ */
+function getReportEdges(breakdown, report) {
+ return EDGES[breakdown.by](breakdown, report);
+}
+exports.getReportEdges = getReportEdges;
+
+/** * walk *******************************************************************/
+
+function recursiveWalk(breakdown, edge, report, visitor) {
+ if (breakdown.by === "count") {
+ visitor.enter(breakdown, report, edge);
+ visitor.count(breakdown, report, edge);
+ visitor.exit(breakdown, report, edge);
+ } else {
+ visitor.enter(breakdown, report, edge);
+ for (let { edge, referent, breakdown: subBreakdown } of getReportEdges(breakdown, report)) {
+ recursiveWalk(subBreakdown, edge, referent, visitor);
+ }
+ visitor.exit(breakdown, report, edge);
+ }
+}
+
+/**
+ * Walk the given `report` that was generated by taking a census with the
+ * specified `breakdown`.
+ *
+ * @param {Object} breakdown
+ * The census breakdown.
+ *
+ * @param {Object} report
+ * The census report.
+ *
+ * @param {Visitor} visitor
+ * The Visitor instance to call into while traversing.
+ */
+function walk(breakdown, report, visitor) {
+ recursiveWalk(breakdown, null, report, visitor);
+}
+exports.walk = walk;
+
+/** * diff *******************************************************************/
+
+/**
+ * Return true if the object is a Map, false otherwise. Works with Map objects
+ * from other globals, unlike `instanceof`.
+ *
+ * @returns {Boolean}
+ */
+function isMap(obj) {
+ return Object.prototype.toString.call(obj) === "[object Map]";
+}
+
+/**
+ * A Visitor for computing the difference between the census report being
+ * traversed and the given other census.
+ *
+ * @param {Object} otherCensus
+ * The other census report.
+ */
+function DiffVisitor(otherCensus) {
+ // The other census we are comparing against.
+ this._otherCensus = otherCensus;
+
+ // The total bytes and count of the basis census we are traversing.
+ this._totalBytes = 0;
+ this._totalCount = 0;
+
+ // Stack maintaining the current corresponding sub-report for the other
+ // census we are comparing against.
+ this._otherCensusStack = [];
+
+ // Stack maintaining the set of edges visited at each sub-report.
+ this._edgesVisited = [new Set()];
+
+ // The final delta census. Valid only after traversal.
+ this._results = null;
+
+ // Stack maintaining the results corresponding to each sub-report we are
+ // currently traversing.
+ this._resultsStack = [];
+}
+
+DiffVisitor.prototype = Object.create(Visitor.prototype);
+
+/**
+ * Given a report and an outgoing edge, get the edge's referent.
+ */
+DiffVisitor.prototype._get = function (report, edge) {
+ if (!report) {
+ return undefined;
+ }
+ return isMap(report) ? report.get(edge) : report[edge];
+};
+
+/**
+ * Given a report, an outgoing edge, and a value, set the edge's referent to
+ * the given value.
+ */
+DiffVisitor.prototype._set = function (report, edge, val) {
+ if (isMap(report)) {
+ report.set(edge, val);
+ } else {
+ report[edge] = val;
+ }
+};
+
+/**
+ * @overrides Visitor.prototype.enter
+ */
+DiffVisitor.prototype.enter = function (breakdown, report, edge) {
+ const isFirstTimeEntering = this._results === null;
+
+ const newResults = breakdown.by === "allocationStack" ? new Map() : {};
+ let newOther;
+
+ if (!this._results) {
+ // This is the first time we have entered a sub-report.
+ this._results = newResults;
+ newOther = this._otherCensus;
+ } else {
+ const topResults = this._resultsStack[this._resultsStack.length - 1];
+ this._set(topResults, edge, newResults);
+
+ const topOther = this._otherCensusStack[this._otherCensusStack.length - 1];
+ newOther = this._get(topOther, edge);
+ }
+
+ this._resultsStack.push(newResults);
+ this._otherCensusStack.push(newOther);
+
+ const visited = this._edgesVisited[this._edgesVisited.length - 1];
+ visited.add(edge);
+ this._edgesVisited.push(new Set());
+};
+
+/**
+ * @overrides Visitor.prototype.exit
+ */
+DiffVisitor.prototype.exit = function (breakdown, report, edge) {
+ // Find all the edges in the other census report that were not traversed and
+ // add them to the results directly.
+ const other = this._otherCensusStack[this._otherCensusStack.length - 1];
+ if (other) {
+ const visited = this._edgesVisited[this._edgesVisited.length - 1];
+ const unvisited = getReportEdges(breakdown, other)
+ .map(e => e.edge)
+ .filter(e => !visited.has(e));
+ const results = this._resultsStack[this._resultsStack.length - 1];
+ for (let edge of unvisited) {
+ this._set(results, edge, this._get(other, edge));
+ }
+ }
+
+ this._otherCensusStack.pop();
+ this._resultsStack.pop();
+ this._edgesVisited.pop();
+};
+
+/**
+ * @overrides Visitor.prototype.count
+ */
+DiffVisitor.prototype.count = function (breakdown, report, edge) {
+ const other = this._otherCensusStack[this._otherCensusStack.length - 1];
+ const results = this._resultsStack[this._resultsStack.length - 1];
+
+ if (breakdown.count) {
+ this._totalCount += report.count;
+ }
+ if (breakdown.bytes) {
+ this._totalBytes += report.bytes;
+ }
+
+ if (other) {
+ if (breakdown.count) {
+ results.count = other.count - report.count;
+ }
+ if (breakdown.bytes) {
+ results.bytes = other.bytes - report.bytes;
+ }
+ } else {
+ if (breakdown.count) {
+ results.count = -report.count;
+ }
+ if (breakdown.bytes) {
+ results.bytes = -report.bytes;
+ }
+ }
+};
+
+const basisTotalBytes = exports.basisTotalBytes = Symbol("basisTotalBytes");
+const basisTotalCount = exports.basisTotalCount = Symbol("basisTotalCount");
+
+/**
+ * Get the resulting report of the difference between the traversed census
+ * report and the other census report.
+ *
+ * @returns {Object}
+ * The delta census report.
+ */
+DiffVisitor.prototype.results = function () {
+ if (!this._results) {
+ throw new Error("Attempt to get results before computing diff!");
+ }
+
+ if (this._resultsStack.length) {
+ throw new Error("Attempt to get results while still computing diff!");
+ }
+
+ this._results[basisTotalBytes] = this._totalBytes;
+ this._results[basisTotalCount] = this._totalCount;
+
+ return this._results;
+};
+
+/**
+ * Take the difference between two censuses. The resulting delta report
+ * contains the number/size of things that are in the `endCensus` that are not
+ * in the `startCensus`.
+ *
+ * @param {Object} breakdown
+ * The breakdown used to generate both census reports.
+ *
+ * @param {Object} startCensus
+ * The first census report.
+ *
+ * @param {Object} endCensus
+ * The second census report.
+ *
+ * @returns {Object}
+ * A delta report mirroring the structure of the two census reports (as
+ * specified by the given breakdown). Has two additional properties:
+ * - {Number} basisTotalBytes: the total number of bytes in the start
+ * census.
+ * - {Number} basisTotalCount: the total count in the start census.
+ */
+function diff(breakdown, startCensus, endCensus) {
+ const visitor = new DiffVisitor(endCensus);
+ walk(breakdown, startCensus, visitor);
+ return visitor.results();
+}
+exports.diff = diff;
+
+/**
+ * Creates a hash map mapping node IDs to its parent node.
+ *
+ * @param {CensusTreeNode} node
+ * @param {Object<number, TreeNode>} aggregator
+ *
+ * @return {Object<number, TreeNode>}
+ */
+const createParentMap = exports.createParentMap = function (node,
+ getId = node => node.id,
+ aggregator = Object.create(null)) {
+ if (node.children) {
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ const child = node.children[i];
+ aggregator[getId(child)] = node;
+ createParentMap(child, getId, aggregator);
+ }
+ }
+
+ return aggregator;
+};
+
+const BUCKET = Object.freeze({ by: "bucket" });
+
+/**
+ * Convert a breakdown whose leaves are { by: "count" } to an identical
+ * breakdown, except with { by: "bucket" } leaves.
+ *
+ * @param {Object} breakdown
+ * @returns {Object}
+ */
+exports.countToBucketBreakdown = function (breakdown) {
+ if (typeof breakdown !== "object" || !breakdown) {
+ return breakdown;
+ }
+
+ if (breakdown.by === "count") {
+ return BUCKET;
+ }
+
+ const keys = Object.keys(breakdown);
+ const vals = keys.reduce((vs, k) => {
+ vs.push(exports.countToBucketBreakdown(breakdown[k]));
+ return vs;
+ }, []);
+
+ const result = {};
+ for (let i = 0, length = keys.length; i < length; i++) {
+ result[keys[i]] = vals[i];
+ }
+
+ return Object.freeze(result);
+};
+
+/**
+ * A Visitor for finding report leaves by their DFS index.
+ */
+function GetLeavesVisitor(targetIndices) {
+ this._index = -1;
+ this._targetIndices = targetIndices;
+ this._leaves = [];
+}
+
+GetLeavesVisitor.prototype = Object.create(Visitor.prototype);
+
+/**
+ * @overrides Visitor.prototype.enter
+ */
+GetLeavesVisitor.prototype.enter = function (breakdown, report, edge) {
+ this._index++;
+ if (this._targetIndices.has(this._index)) {
+ this._leaves.push(report);
+ }
+};
+
+/**
+ * Get the accumulated report leaves after traversal.
+ */
+GetLeavesVisitor.prototype.leaves = function () {
+ if (this._index === -1) {
+ throw new Error("Attempt to call `leaves` before traversing report!");
+ }
+ return this._leaves;
+};
+
+/**
+ * Given a set of indices of leaves in a pre-order depth-first traversal of the
+ * given census report, return the leaves.
+ *
+ * @param {Set<Number>} indices
+ * @param {Object} breakdown
+ * @param {Object} report
+ *
+ * @returns {Array<Object>}
+ */
+exports.getReportLeaves = function (indices, breakdown, report) {
+ const visitor = new GetLeavesVisitor(indices);
+ walk(breakdown, report, visitor);
+ return visitor.leaves();
+};
+
+/**
+ * Get a list of the individual node IDs that belong to the census report leaves
+ * of the given indices.
+ *
+ * @param {Set<Number>} indices
+ * @param {Object} breakdown
+ * @param {HeapSnapshot} snapshot
+ *
+ * @returns {Array<NodeId>}
+ */
+exports.getCensusIndividuals = function (indices, countBreakdown, snapshot) {
+ const bucketBreakdown = exports.countToBucketBreakdown(countBreakdown);
+ const bucketReport = snapshot.takeCensus({ breakdown: bucketBreakdown });
+ const buckets = exports.getReportLeaves(indices,
+ bucketBreakdown,
+ bucketReport);
+ return flatten(buckets);
+};
diff --git a/devtools/shared/heapsnapshot/DominatorTreeNode.js b/devtools/shared/heapsnapshot/DominatorTreeNode.js
new file mode 100644
index 000000000..13a847fd0
--- /dev/null
+++ b/devtools/shared/heapsnapshot/DominatorTreeNode.js
@@ -0,0 +1,336 @@
+/* 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";
+
+const { immutableUpdate } = require("resource://devtools/shared/ThreadSafeDevToolsUtils.js");
+const { Visitor, walk } = require("resource://devtools/shared/heapsnapshot/CensusUtils.js");
+const { deduplicatePaths } = require("resource://devtools/shared/heapsnapshot/shortest-paths");
+
+const DEFAULT_MAX_DEPTH = 4;
+const DEFAULT_MAX_SIBLINGS = 15;
+const DEFAULT_MAX_NUM_PATHS = 5;
+
+/**
+ * A single node in a dominator tree.
+ *
+ * @param {NodeId} nodeId
+ * @param {NodeSize} retainedSize
+ */
+function DominatorTreeNode(nodeId, label, shallowSize, retainedSize) {
+ // The id of this node.
+ this.nodeId = nodeId;
+
+ // The label structure generated by describing the given node.
+ this.label = label;
+
+ // The shallow size of this node.
+ this.shallowSize = shallowSize;
+
+ // The retained size of this node.
+ this.retainedSize = retainedSize;
+
+ // The id of this node's parent or undefined if this node is the root.
+ this.parentId = undefined;
+
+ // An array of immediately dominated child `DominatorTreeNode`s, or undefined.
+ this.children = undefined;
+
+ // An object of the form returned by `deduplicatePaths`, encoding the set of
+ // the N shortest retaining paths for this node as a graph.
+ this.shortestPaths = undefined;
+
+ // True iff the `children` property does not contain every immediately
+ // dominated node.
+ //
+ // * If children is an array and this property is true: the array does not
+ // contain the complete set of immediately dominated children.
+ // * If children is an array and this property is false: the array contains
+ // the complete set of immediately dominated children.
+ // * If children is undefined and this property is true: there exist
+ // immediately dominated children for this node, but they have not been
+ // loaded yet.
+ // * If children is undefined and this property is false: this node does not
+ // dominate any others and therefore has no children.
+ this.moreChildrenAvailable = true;
+}
+
+DominatorTreeNode.prototype = null;
+
+module.exports = DominatorTreeNode;
+
+/**
+ * Add `child` to the `parent`'s set of children.
+ *
+ * @param {DominatorTreeNode} parent
+ * @param {DominatorTreeNode} child
+ */
+DominatorTreeNode.addChild = function (parent, child) {
+ if (parent.children === undefined) {
+ parent.children = [];
+ }
+
+ parent.children.push(child);
+ child.parentId = parent.nodeId;
+};
+
+/**
+ * A Visitor that is used to generate a label for a node in the heap snapshot
+ * and get its shallow size as well while we are at it.
+ */
+function LabelAndShallowSizeVisitor() {
+ // As we walk the description, we accumulate edges in this array.
+ this._labelPieces = [];
+
+ // Once we reach the non-zero count leaf node in the description, we move the
+ // labelPieces here to signify that we no longer need to accumulate edges.
+ this._label = undefined;
+
+ // Once we reach the non-zero count leaf node in the description, we grab the
+ // shallow size and place it here.
+ this._shallowSize = 0;
+}
+
+DominatorTreeNode.LabelAndShallowSizeVisitor = LabelAndShallowSizeVisitor;
+
+LabelAndShallowSizeVisitor.prototype = Object.create(Visitor);
+
+/**
+ * @overrides Visitor.prototype.enter
+ */
+LabelAndShallowSizeVisitor.prototype.enter = function (breakdown, report, edge) {
+ if (this._labelPieces && edge) {
+ this._labelPieces.push(edge);
+ }
+};
+
+/**
+ * @overrides Visitor.prototype.exit
+ */
+LabelAndShallowSizeVisitor.prototype.exit = function (breakdown, report, edge) {
+ if (this._labelPieces && edge) {
+ this._labelPieces.pop();
+ }
+};
+
+/**
+ * @overrides Visitor.prototype.count
+ */
+LabelAndShallowSizeVisitor.prototype.count = function (breakdown, report, edge) {
+ if (report.count === 0) {
+ return;
+ }
+
+ this._label = this._labelPieces;
+ this._labelPieces = undefined;
+
+ this._shallowSize = report.bytes;
+};
+
+/**
+ * Get the generated label structure accumulated by this visitor.
+ *
+ * @returns {Object}
+ */
+LabelAndShallowSizeVisitor.prototype.label = function () {
+ return this._label;
+};
+
+/**
+ * Get the shallow size of the node this visitor visited.
+ *
+ * @returns {Number}
+ */
+LabelAndShallowSizeVisitor.prototype.shallowSize = function () {
+ return this._shallowSize;
+};
+
+/**
+ * Generate a label structure for the node with the given id and grab its
+ * shallow size.
+ *
+ * What is a "label" structure? HeapSnapshot.describeNode essentially takes a
+ * census of a single node rather than the whole heap graph. The resulting
+ * report has only one count leaf that is non-zero. The label structure is the
+ * path in this report from the root to the non-zero count leaf.
+ *
+ * @param {Number} nodeId
+ * @param {HeapSnapshot} snapshot
+ * @param {Object} breakdown
+ *
+ * @returns {Object}
+ * An object with the following properties:
+ * - {Number} shallowSize
+ * - {Object} label
+ */
+DominatorTreeNode.getLabelAndShallowSize = function (nodeId,
+ snapshot,
+ breakdown) {
+ const description = snapshot.describeNode(breakdown, nodeId);
+
+ const visitor = new LabelAndShallowSizeVisitor();
+ walk(breakdown, description, visitor);
+
+ return {
+ label: visitor.label(),
+ shallowSize: visitor.shallowSize(),
+ };
+};
+
+/**
+ * Do a partial traversal of the given dominator tree and convert it into a tree
+ * of `DominatorTreeNode`s. Dominator trees have a node for every node in the
+ * snapshot's heap graph, so we must not allocate a JS object for every node. It
+ * would be way too many and the node count is effectively unbounded.
+ *
+ * Go no deeper down the tree than `maxDepth` and only consider at most
+ * `maxSiblings` within any single node's children.
+ *
+ * @param {DominatorTree} dominatorTree
+ * @param {HeapSnapshot} snapshot
+ * @param {Object} breakdown
+ * @param {Number} maxDepth
+ * @param {Number} maxSiblings
+ *
+ * @returns {DominatorTreeNode}
+ */
+DominatorTreeNode.partialTraversal = function (dominatorTree,
+ snapshot,
+ breakdown,
+ maxDepth = DEFAULT_MAX_DEPTH,
+ maxSiblings = DEFAULT_MAX_SIBLINGS) {
+ function dfs(nodeId, depth) {
+ const { label, shallowSize } =
+ DominatorTreeNode.getLabelAndShallowSize(nodeId, snapshot, breakdown);
+ const retainedSize = dominatorTree.getRetainedSize(nodeId);
+ const node = new DominatorTreeNode(nodeId, label, shallowSize, retainedSize);
+ const childNodeIds = dominatorTree.getImmediatelyDominated(nodeId);
+
+ const newDepth = depth + 1;
+ if (newDepth < maxDepth) {
+ const endIdx = Math.min(childNodeIds.length, maxSiblings);
+ for (let i = 0; i < endIdx; i++) {
+ DominatorTreeNode.addChild(node, dfs(childNodeIds[i], newDepth));
+ }
+ node.moreChildrenAvailable = endIdx < childNodeIds.length;
+ } else {
+ node.moreChildrenAvailable = childNodeIds.length > 0;
+ }
+
+ return node;
+ }
+
+ return dfs(dominatorTree.root, 0);
+};
+
+/**
+ * Insert more children into the given (partially complete) dominator tree.
+ *
+ * The tree is updated in an immutable and persistent manner: a new tree is
+ * returned, but all unmodified subtrees (which is most) are shared with the
+ * original tree. Only the modified nodes are re-allocated.
+ *
+ * @param {DominatorTreeNode} tree
+ * @param {Array<NodeId>} path
+ * @param {Array<DominatorTreeNode>} newChildren
+ * @param {Boolean} moreChildrenAvailable
+ *
+ * @returns {DominatorTreeNode}
+ */
+DominatorTreeNode.insert = function (tree, path, newChildren, moreChildrenAvailable) {
+ function insert(tree, i) {
+ if (tree.nodeId !== path[i]) {
+ return tree;
+ }
+
+ if (i == path.length - 1) {
+ return immutableUpdate(tree, {
+ children: (tree.children || []).concat(newChildren),
+ moreChildrenAvailable,
+ });
+ }
+
+ return tree.children
+ ? immutableUpdate(tree, {
+ children: tree.children.map(c => insert(c, i + 1))
+ })
+ : tree;
+ }
+
+ return insert(tree, 0);
+};
+
+/**
+ * Get the new canonical node with the given `id` in `tree` that exists along
+ * `path`. If there is no such node along `path`, return null.
+ *
+ * This is useful if we have a reference to a now-outdated DominatorTreeNode due
+ * to a recent call to DominatorTreeNode.insert and want to get the up-to-date
+ * version. We don't have to walk the whole tree: if there is an updated version
+ * of the node then it *must* be along the path.
+ *
+ * @param {NodeId} id
+ * @param {DominatorTreeNode} tree
+ * @param {Array<NodeId>} path
+ *
+ * @returns {DominatorTreeNode|null}
+ */
+DominatorTreeNode.getNodeByIdAlongPath = function (id, tree, path) {
+ function find(node, i) {
+ if (!node || node.nodeId !== path[i]) {
+ return null;
+ }
+
+ if (node.nodeId === id) {
+ return node;
+ }
+
+ if (i === path.length - 1 || !node.children) {
+ return null;
+ }
+
+ const nextId = path[i + 1];
+ return find(node.children.find(c => c.nodeId === nextId), i + 1);
+ }
+
+ return find(tree, 0);
+};
+
+/**
+ * Find the shortest retaining paths for the given set of DominatorTreeNodes,
+ * and populate each node's `shortestPaths` property with them in place.
+ *
+ * @param {HeapSnapshot} snapshot
+ * @param {Object} breakdown
+ * @param {NodeId} start
+ * @param {Array<DominatorTreeNode>} treeNodes
+ * @param {Number} maxNumPaths
+ */
+DominatorTreeNode.attachShortestPaths = function (snapshot,
+ breakdown,
+ start,
+ treeNodes,
+ maxNumPaths = DEFAULT_MAX_NUM_PATHS) {
+ const idToTreeNode = new Map();
+ const targets = [];
+ for (let node of treeNodes) {
+ const id = node.nodeId;
+ idToTreeNode.set(id, node);
+ targets.push(id);
+ }
+
+ const shortestPaths = snapshot.computeShortestPaths(start,
+ targets,
+ maxNumPaths);
+
+ for (let [target, paths] of shortestPaths) {
+ const deduped = deduplicatePaths(target, paths);
+ deduped.nodes = deduped.nodes.map(id => {
+ const { label } =
+ DominatorTreeNode.getLabelAndShallowSize(id, snapshot, breakdown);
+ return { id, label };
+ });
+
+ idToTreeNode.get(target).shortestPaths = deduped;
+ }
+};
diff --git a/devtools/shared/heapsnapshot/HeapAnalysesClient.js b/devtools/shared/heapsnapshot/HeapAnalysesClient.js
new file mode 100644
index 000000000..98601a2b1
--- /dev/null
+++ b/devtools/shared/heapsnapshot/HeapAnalysesClient.js
@@ -0,0 +1,277 @@
+/* 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";
+
+const DevToolsUtils = require("devtools/shared/DevToolsUtils");
+const { DevToolsWorker } = require("devtools/shared/worker/worker");
+
+const WORKER_URL =
+ "resource://devtools/shared/heapsnapshot/HeapAnalysesWorker.js";
+var workerCounter = 0;
+
+/**
+ * A HeapAnalysesClient instance provides a developer-friendly interface for
+ * interacting with a HeapAnalysesWorker. This enables users to be ignorant of
+ * the message passing protocol used to communicate with the worker. The
+ * HeapAnalysesClient owns the worker, and terminating the worker is done by
+ * terminating the client (see the `destroy` method).
+ */
+const HeapAnalysesClient = module.exports = function () {
+ this._worker = new DevToolsWorker(WORKER_URL, {
+ name: `HeapAnalyses-${workerCounter++}`,
+ verbose: DevToolsUtils.dumpv.wantVerbose
+ });
+};
+
+/**
+ * Destroy the worker, causing it to release its resources (such as heap
+ * snapshots it has deserialized and read into memory). The client is no longer
+ * usable after calling this method.
+ */
+HeapAnalysesClient.prototype.destroy = function () {
+ this._worker.destroy();
+ this._worker = null;
+};
+
+/**
+ * Tell the worker to read into memory the heap snapshot at the given file
+ * path. This is a prerequisite for asking the worker to perform various
+ * analyses on a heap snapshot.
+ *
+ * @param {String} snapshotFilePath
+ *
+ * @returns Promise
+ * The promise is fulfilled if the heap snapshot is successfully
+ * deserialized and read into memory. The promise is rejected if that
+ * does not happen, eg due to a bad file path or malformed heap
+ * snapshot file.
+ */
+HeapAnalysesClient.prototype.readHeapSnapshot = function (snapshotFilePath) {
+ return this._worker.performTask("readHeapSnapshot", { snapshotFilePath });
+};
+
+/**
+ * Tell the worker to delete all references to the snapshot and dominator trees
+ * linked to the provided snapshot file path.
+ *
+ * @param {String} snapshotFilePath
+ * @return Promise<undefined>
+ */
+HeapAnalysesClient.prototype.deleteHeapSnapshot = function (snapshotFilePath) {
+ return this._worker.performTask("deleteHeapSnapshot", { snapshotFilePath });
+};
+
+/**
+ * Request the creation time given a snapshot file path. Returns `null`
+ * if snapshot does not exist.
+ *
+ * @param {String} snapshotFilePath
+ * The path to the snapshot.
+ * @return {Number?}
+ * The unix timestamp of the creation time of the snapshot, or null if
+ * snapshot does not exist.
+ */
+HeapAnalysesClient.prototype.getCreationTime = function (snapshotFilePath) {
+ return this._worker.performTask("getCreationTime", snapshotFilePath);
+};
+
+/** * Censuses *****************************************************************/
+
+/**
+ * Ask the worker to perform a census analysis on the heap snapshot with the
+ * given path. The heap snapshot at the given path must have already been read
+ * into memory by the worker (see `readHeapSnapshot`).
+ *
+ * @param {String} snapshotFilePath
+ *
+ * @param {Object} censusOptions
+ * A structured-cloneable object specifying the requested census's
+ * breakdown. See the "takeCensus" section of
+ * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation.
+ *
+ * @param {Object} requestOptions
+ * An object specifying options of this worker request.
+ * - {Boolean} asTreeNode
+ * Whether or not the census is returned as a CensusTreeNode,
+ * or just a breakdown report. Defaults to false.
+ * @see `devtools/shared/heapsnapshot/census-tree-node.js`
+ * - {Boolean} asInvertedTreeNode
+ * Whether or not the census is returned as an inverted
+ * CensusTreeNode. Defaults to false.
+ * - {String} filter
+ * A filter string to prune the resulting tree with. Only applies if
+ * either asTreeNode or asInvertedTreeNode is true.
+ *
+ * @returns Promise<Object>
+ * An object with the following properties:
+ * - report:
+ * The report generated by the given census breakdown, or a
+ * CensusTreeNode generated by the given census breakdown if
+ * `asTreeNode` is true.
+ * - parentMap:
+ * The result of calling CensusUtils.createParentMap on the generated
+ * report. Only exists if asTreeNode or asInvertedTreeNode are set.
+ */
+HeapAnalysesClient.prototype.takeCensus = function (snapshotFilePath,
+ censusOptions,
+ requestOptions = {}) {
+ return this._worker.performTask("takeCensus", {
+ snapshotFilePath,
+ censusOptions,
+ requestOptions,
+ });
+};
+
+/**
+ * Get the individual nodes that correspond to the given census report leaf
+ * indices.
+ *
+ * @param {Object} opts
+ * An object with the following properties:
+ * - {DominatorTreeId} dominatorTreeId: The id of the dominator tree.
+ * - {Set<Number>} indices: The indices of the census report leaves we
+ * would like to get the individuals for.
+ * - {Object} censusBreakdown: The breakdown used to generate the census.
+ * - {Object} labelBreakdown: The breakdown we would like to use when
+ * labeling the resulting nodes.
+ * - {Number} maxRetainingPaths: The maximum number of retaining paths to
+ * compute for each node.
+ * - {Number} maxIndividuals: The maximum number of individual nodes to
+ * return.
+ *
+ * @returns {Promise<Object>}
+ * A promise of an object with the following properties:
+ * - {Array<DominatorTreeNode>} nodes: An array of `DominatorTreeNode`s
+ * with their shortest paths attached, and without any dominator tree
+ * child/parent information attached. The results are sorted by
+ * retained size.
+ *
+ */
+HeapAnalysesClient.prototype.getCensusIndividuals = function (opts) {
+ return this._worker.performTask("getCensusIndividuals", opts);
+};
+
+/**
+ * Request that the worker take a census on the heap snapshots with the given
+ * paths and then return the difference between them. Both heap snapshots must
+ * have already been read into memory by the worker (see `readHeapSnapshot`).
+ *
+ * @param {String} firstSnapshotFilePath
+ * The first snapshot file path.
+ *
+ * @param {String} secondSnapshotFilePath
+ * The second snapshot file path.
+ *
+ * @param {Object} censusOptions
+ * A structured-cloneable object specifying the requested census's
+ * breakdown. See the "takeCensus" section of
+ * `js/src/doc/Debugger/Debugger.Memory.md` for detailed documentation.
+ *
+ * @param {Object} requestOptions
+ * An object specifying options for this request.
+ * - {Boolean} asTreeNode
+ * Whether the resulting delta report should be converted to a census
+ * tree node before returned. Defaults to false.
+ * - {Boolean} asInvertedTreeNode
+ * Whether or not the census is returned as an inverted
+ * CensusTreeNode. Defaults to false.
+ * - {String} filter
+ * A filter string to prune the resulting tree with. Only applies if
+ * either asTreeNode or asInvertedTreeNode is true.
+ *
+ * @returns Promise<Object>
+ * - delta:
+ * The delta report generated by diffing the two census reports, or a
+ * CensusTreeNode generated from the delta report if
+ * `requestOptions.asTreeNode` was true.
+ * - parentMap:
+ * The result of calling CensusUtils.createParentMap on the generated
+ * delta. Only exists if asTreeNode or asInvertedTreeNode are set.
+ */
+HeapAnalysesClient.prototype.takeCensusDiff = function (firstSnapshotFilePath,
+ secondSnapshotFilePath,
+ censusOptions,
+ requestOptions = {}) {
+ return this._worker.performTask("takeCensusDiff", {
+ firstSnapshotFilePath,
+ secondSnapshotFilePath,
+ censusOptions,
+ requestOptions
+ });
+};
+
+/** * Dominator Trees **********************************************************/
+
+/**
+ * Compute the dominator tree of the heap snapshot loaded from the given file
+ * path. Returns the id of the computed dominator tree.
+ *
+ * @param {String} snapshotFilePath
+ *
+ * @returns {Promise<DominatorTreeId>}
+ */
+HeapAnalysesClient.prototype.computeDominatorTree = function (snapshotFilePath) {
+ return this._worker.performTask("computeDominatorTree", snapshotFilePath);
+};
+
+/**
+ * Get the initial, partial view of the dominator tree with the given id.
+ *
+ * @param {Object} opts
+ * An object specifying options for this request.
+ * - {DominatorTreeId} dominatorTreeId
+ * The id of the dominator tree.
+ * - {Object} breakdown
+ * The breakdown used to generate node labels.
+ * - {Number} maxDepth
+ * The maximum depth to traverse down the tree to create this initial
+ * view.
+ * - {Number} maxSiblings
+ * The maximum number of siblings to visit within each traversed node's
+ * children.
+ * - {Number} maxRetainingPaths
+ * The maximum number of retaining paths to find for each node.
+ *
+ * @returns {Promise<DominatorTreeNode>}
+ */
+HeapAnalysesClient.prototype.getDominatorTree = function (opts) {
+ return this._worker.performTask("getDominatorTree", opts);
+};
+
+/**
+ * Get a subset of a nodes children in the dominator tree.
+ *
+ * @param {Object} opts
+ * An object specifying options for this request.
+ * - {DominatorTreeId} dominatorTreeId
+ * The id of the dominator tree.
+ * - {NodeId} nodeId
+ * The id of the node whose children are being found.
+ * - {Object} breakdown
+ * The breakdown used to generate node labels.
+ * - {Number} startIndex
+ * The starting index within the full set of immediately dominated
+ * children of the children being requested. Children are always sorted
+ * by greatest to least retained size.
+ * - {Number} maxCount
+ * The maximum number of children to return.
+ * - {Number} maxRetainingPaths
+ * The maximum number of retaining paths to find for each node.
+ *
+ * @returns {Promise<Object>}
+ * A promise of an object with the following properties:
+ * - {Array<DominatorTreeNode>} nodes
+ * The requested nodes that are immediately dominated by the node
+ * identified by `opts.nodeId`.
+ * - {Boolean} moreChildrenAvailable
+ * True iff there are more children available after the returned
+ * nodes.
+ * - {Array<NodeId>} path
+ * The path through the tree from the root to these node's parent, eg
+ * [root's id, child of root's id, child of child of root's id, ..., `nodeId`].
+ */
+HeapAnalysesClient.prototype.getImmediatelyDominated = function (opts) {
+ return this._worker.performTask("getImmediatelyDominated", opts);
+};
diff --git a/devtools/shared/heapsnapshot/HeapAnalysesWorker.js b/devtools/shared/heapsnapshot/HeapAnalysesWorker.js
new file mode 100644
index 000000000..d07d67f80
--- /dev/null
+++ b/devtools/shared/heapsnapshot/HeapAnalysesWorker.js
@@ -0,0 +1,303 @@
+/* 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/. */
+/* global ThreadSafeChromeUtils*/
+
+// This is a worker which reads offline heap snapshots into memory and performs
+// heavyweight analyses on them without blocking the main thread. A
+// HeapAnalysesWorker is owned and communicated with by a HeapAnalysesClient
+// instance. See HeapAnalysesClient.js.
+
+"use strict";
+
+importScripts("resource://gre/modules/workers/require.js");
+importScripts("resource://devtools/shared/worker/helper.js");
+const { censusReportToCensusTreeNode } = require("resource://devtools/shared/heapsnapshot/census-tree-node.js");
+const DominatorTreeNode = require("resource://devtools/shared/heapsnapshot/DominatorTreeNode.js");
+const CensusUtils = require("resource://devtools/shared/heapsnapshot/CensusUtils.js");
+
+const DEFAULT_START_INDEX = 0;
+const DEFAULT_MAX_COUNT = 50;
+
+/**
+ * The set of HeapSnapshot instances this worker has read into memory. Keyed by
+ * snapshot file path.
+ */
+const snapshots = Object.create(null);
+
+/**
+ * The set of `DominatorTree`s that have been computed, mapped by their id (aka
+ * the index into this array).
+ *
+ * @see /dom/webidl/DominatorTree.webidl
+ */
+const dominatorTrees = [];
+
+/**
+ * The i^th HeapSnapshot in this array is the snapshot used to generate the i^th
+ * dominator tree in `dominatorTrees` above. This lets us map from a dominator
+ * tree id to the snapshot it came from.
+ */
+const dominatorTreeSnapshots = [];
+
+/**
+ * @see HeapAnalysesClient.prototype.readHeapSnapshot
+ */
+workerHelper.createTask(self, "readHeapSnapshot", ({ snapshotFilePath }) => {
+ snapshots[snapshotFilePath] =
+ ThreadSafeChromeUtils.readHeapSnapshot(snapshotFilePath);
+ return true;
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.deleteHeapSnapshot
+ */
+workerHelper.createTask(self, "deleteHeapSnapshot", ({ snapshotFilePath }) => {
+ let snapshot = snapshots[snapshotFilePath];
+ if (!snapshot) {
+ throw new Error(`No known heap snapshot for '${snapshotFilePath}'`);
+ }
+
+ snapshots[snapshotFilePath] = undefined;
+
+ let dominatorTreeId = dominatorTreeSnapshots.indexOf(snapshot);
+ if (dominatorTreeId != -1) {
+ dominatorTreeSnapshots[dominatorTreeId] = undefined;
+ dominatorTrees[dominatorTreeId] = undefined;
+ }
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.takeCensus
+ */
+workerHelper.createTask(self, "takeCensus", ({ snapshotFilePath, censusOptions, requestOptions }) => {
+ if (!snapshots[snapshotFilePath]) {
+ throw new Error(`No known heap snapshot for '${snapshotFilePath}'`);
+ }
+
+ let report = snapshots[snapshotFilePath].takeCensus(censusOptions);
+ let parentMap;
+
+ if (requestOptions.asTreeNode || requestOptions.asInvertedTreeNode) {
+ const opts = { filter: requestOptions.filter || null };
+ if (requestOptions.asInvertedTreeNode) {
+ opts.invert = true;
+ }
+ report = censusReportToCensusTreeNode(censusOptions.breakdown, report, opts);
+ parentMap = CensusUtils.createParentMap(report);
+ }
+
+ return { report, parentMap };
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.getCensusIndividuals
+ */
+workerHelper.createTask(self, "getCensusIndividuals", request => {
+ const {
+ dominatorTreeId,
+ indices,
+ censusBreakdown,
+ labelBreakdown,
+ maxRetainingPaths,
+ maxIndividuals,
+ } = request;
+
+ const dominatorTree = dominatorTrees[dominatorTreeId];
+ if (!dominatorTree) {
+ throw new Error(
+ `There does not exist a DominatorTree with the id ${dominatorTreeId}`);
+ }
+
+ const snapshot = dominatorTreeSnapshots[dominatorTreeId];
+ const nodeIds = CensusUtils.getCensusIndividuals(indices, censusBreakdown, snapshot);
+
+ const nodes = nodeIds
+ .sort((a, b) => dominatorTree.getRetainedSize(b) - dominatorTree.getRetainedSize(a))
+ .slice(0, maxIndividuals)
+ .map(id => {
+ const { label, shallowSize } =
+ DominatorTreeNode.getLabelAndShallowSize(id, snapshot, labelBreakdown);
+ const retainedSize = dominatorTree.getRetainedSize(id);
+ const node = new DominatorTreeNode(id, label, shallowSize, retainedSize);
+ node.moreChildrenAvailable = false;
+ return node;
+ });
+
+ DominatorTreeNode.attachShortestPaths(snapshot,
+ labelBreakdown,
+ dominatorTree.root,
+ nodes,
+ maxRetainingPaths);
+
+ return { nodes };
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.takeCensusDiff
+ */
+workerHelper.createTask(self, "takeCensusDiff", request => {
+ const {
+ firstSnapshotFilePath,
+ secondSnapshotFilePath,
+ censusOptions,
+ requestOptions
+ } = request;
+
+ if (!snapshots[firstSnapshotFilePath]) {
+ throw new Error(`No known heap snapshot for '${firstSnapshotFilePath}'`);
+ }
+
+ if (!snapshots[secondSnapshotFilePath]) {
+ throw new Error(`No known heap snapshot for '${secondSnapshotFilePath}'`);
+ }
+
+ const first = snapshots[firstSnapshotFilePath].takeCensus(censusOptions);
+ const second = snapshots[secondSnapshotFilePath].takeCensus(censusOptions);
+ let delta = CensusUtils.diff(censusOptions.breakdown, first, second);
+ let parentMap;
+
+ if (requestOptions.asTreeNode || requestOptions.asInvertedTreeNode) {
+ const opts = { filter: requestOptions.filter || null };
+ if (requestOptions.asInvertedTreeNode) {
+ opts.invert = true;
+ }
+ delta = censusReportToCensusTreeNode(censusOptions.breakdown, delta, opts);
+ parentMap = CensusUtils.createParentMap(delta);
+ }
+
+ return { delta, parentMap };
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.getCreationTime
+ */
+workerHelper.createTask(self, "getCreationTime", snapshotFilePath => {
+ if (!snapshots[snapshotFilePath]) {
+ throw new Error(`No known heap snapshot for '${snapshotFilePath}'`);
+ }
+ return snapshots[snapshotFilePath].creationTime;
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.computeDominatorTree
+ */
+workerHelper.createTask(self, "computeDominatorTree", snapshotFilePath => {
+ const snapshot = snapshots[snapshotFilePath];
+ if (!snapshot) {
+ throw new Error(`No known heap snapshot for '${snapshotFilePath}'`);
+ }
+
+ const id = dominatorTrees.length;
+ dominatorTrees.push(snapshot.computeDominatorTree());
+ dominatorTreeSnapshots.push(snapshot);
+ return id;
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.getDominatorTree
+ */
+workerHelper.createTask(self, "getDominatorTree", request => {
+ const {
+ dominatorTreeId,
+ breakdown,
+ maxDepth,
+ maxSiblings,
+ maxRetainingPaths,
+ } = request;
+
+ if (!(0 <= dominatorTreeId && dominatorTreeId < dominatorTrees.length)) {
+ throw new Error(
+ `There does not exist a DominatorTree with the id ${dominatorTreeId}`);
+ }
+
+ const dominatorTree = dominatorTrees[dominatorTreeId];
+ const snapshot = dominatorTreeSnapshots[dominatorTreeId];
+
+ const tree = DominatorTreeNode.partialTraversal(dominatorTree,
+ snapshot,
+ breakdown,
+ maxDepth,
+ maxSiblings);
+
+ const nodes = [];
+ (function getNodes(node) {
+ nodes.push(node);
+ if (node.children) {
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ getNodes(node.children[i]);
+ }
+ }
+ }(tree));
+
+ DominatorTreeNode.attachShortestPaths(snapshot,
+ breakdown,
+ dominatorTree.root,
+ nodes,
+ maxRetainingPaths);
+
+ return tree;
+});
+
+/**
+ * @see HeapAnalysesClient.prototype.getImmediatelyDominated
+ */
+workerHelper.createTask(self, "getImmediatelyDominated", request => {
+ const {
+ dominatorTreeId,
+ nodeId,
+ breakdown,
+ startIndex,
+ maxCount,
+ maxRetainingPaths,
+ } = request;
+
+ if (!(0 <= dominatorTreeId && dominatorTreeId < dominatorTrees.length)) {
+ throw new Error(
+ `There does not exist a DominatorTree with the id ${dominatorTreeId}`);
+ }
+
+ const dominatorTree = dominatorTrees[dominatorTreeId];
+ const snapshot = dominatorTreeSnapshots[dominatorTreeId];
+
+ const childIds = dominatorTree.getImmediatelyDominated(nodeId);
+ if (!childIds) {
+ throw new Error(`${nodeId} is not a node id in the dominator tree`);
+ }
+
+ const start = startIndex || DEFAULT_START_INDEX;
+ const count = maxCount || DEFAULT_MAX_COUNT;
+ const end = start + count;
+
+ const nodes = childIds
+ .slice(start, end)
+ .map(id => {
+ const { label, shallowSize } =
+ DominatorTreeNode.getLabelAndShallowSize(id, snapshot, breakdown);
+ const retainedSize = dominatorTree.getRetainedSize(id);
+ const node = new DominatorTreeNode(id, label, shallowSize, retainedSize);
+ node.parentId = nodeId;
+ // DominatorTree.getImmediatelyDominated will always return non-null here
+ // because we got the id directly from the dominator tree.
+ node.moreChildrenAvailable = dominatorTree.getImmediatelyDominated(id).length > 0;
+ return node;
+ });
+
+ const path = [];
+ let id = nodeId;
+ do {
+ path.push(id);
+ id = dominatorTree.getImmediateDominator(id);
+ } while (id !== null);
+ path.reverse();
+
+ const moreChildrenAvailable = childIds.length > end;
+
+ DominatorTreeNode.attachShortestPaths(snapshot,
+ breakdown,
+ dominatorTree.root,
+ nodes,
+ maxRetainingPaths);
+
+ return { nodes, moreChildrenAvailable, path };
+});
diff --git a/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js b/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js
new file mode 100644
index 000000000..abd44fc30
--- /dev/null
+++ b/devtools/shared/heapsnapshot/HeapSnapshotFileUtils.js
@@ -0,0 +1,95 @@
+/* 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/. */
+
+// Heap snapshots are always saved in the temp directory, and have a regular
+// naming convention. This module provides helpers for working with heap
+// snapshot files in a safe manner. Because we attempt to avoid unnecessary
+// copies of the heap snapshot files by checking the local filesystem for a heap
+// snapshot file with the given snapshot id, we want to ensure that we are only
+// attempting to open heap snapshot files and not `~/.ssh/id_rsa`, for
+// example. Therefore, the RDP only talks about snapshot ids, or transfering the
+// bulk file data. A file path can be recovered from a snapshot id, which allows
+// one to check for the presence of the heap snapshot file on the local file
+// system, but we don't have to worry about opening arbitrary files.
+//
+// The heap snapshot file path conventions permits the following forms:
+//
+// $TEMP_DIRECTORY/XXXXXXXXXX.fxsnapshot
+// $TEMP_DIRECTORY/XXXXXXXXXX-XXXXX.fxsnapshot
+//
+// Where the strings of "X" are zero or more digits.
+
+"use strict";
+
+const { Ci } = require("chrome");
+loader.lazyRequireGetter(this, "FileUtils",
+ "resource://gre/modules/FileUtils.jsm", true);
+loader.lazyRequireGetter(this, "OS", "resource://gre/modules/osfile.jsm", true);
+
+function getHeapSnapshotFileTemplate() {
+ return OS.Path.join(OS.Constants.Path.tmpDir, `${Date.now()}.fxsnapshot`);
+}
+
+/**
+ * Get a unique temp file path for a new heap snapshot. The file is guaranteed
+ * not to exist before this call.
+ *
+ * @returns String
+ */
+exports.getNewUniqueHeapSnapshotTempFilePath = function () {
+ let file = new FileUtils.File(getHeapSnapshotFileTemplate());
+ // The call to createUnique will append "-N" after the leaf name (but before
+ // the extension) until a new file is found and create it. This guarantees we
+ // won't accidentally choose the same file twice.
+ file.createUnique(Ci.nsIFile.NORMAL_FILE_TYPE, 0o666);
+ return file.path;
+};
+
+function isValidSnapshotFileId(snapshotId) {
+ return /^\d+(\-\d+)?$/.test(snapshotId);
+}
+
+/**
+ * Get the file path for the given snapshot id.
+ *
+ * @param {String} snapshotId
+ *
+ * @returns String | null
+ */
+exports.getHeapSnapshotTempFilePath = function (snapshotId) {
+ // Don't want anyone sneaking "../../../.." strings into the snapshot id and
+ // trying to make us open arbitrary files.
+ if (!isValidSnapshotFileId(snapshotId)) {
+ return null;
+ }
+ return OS.Path.join(OS.Constants.Path.tmpDir, snapshotId + ".fxsnapshot");
+};
+
+/**
+ * Return true if we have the heap snapshot file for the given snapshot id on
+ * the local file system. False is returned otherwise.
+ *
+ * @returns Promise<Boolean>
+ */
+exports.haveHeapSnapshotTempFile = function (snapshotId) {
+ const path = exports.getHeapSnapshotTempFilePath(snapshotId);
+ if (!path) {
+ return Promise.resolve(false);
+ }
+
+ return OS.File.stat(path).then(() => true,
+ () => false);
+};
+
+/**
+ * Given a heap snapshot's file path, extricate the snapshot id.
+ *
+ * @param {String} path
+ *
+ * @returns String
+ */
+exports.getSnapshotIdFromPath = function (path) {
+ return path.slice(OS.Constants.Path.tmpDir.length + 1,
+ path.length - ".fxsnapshot".length);
+};
diff --git a/devtools/shared/heapsnapshot/census-tree-node.js b/devtools/shared/heapsnapshot/census-tree-node.js
new file mode 100644
index 000000000..b041e77f9
--- /dev/null
+++ b/devtools/shared/heapsnapshot/census-tree-node.js
@@ -0,0 +1,748 @@
+/* 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";
+
+// CensusTreeNode is an intermediate representation of a census report that
+// exists between after a report is generated by taking a census and before the
+// report is rendered in the DOM. It must be dead simple to render, with no
+// further data processing or massaging needed before rendering DOM nodes. Our
+// goal is to do the census report to CensusTreeNode transformation in the
+// HeapAnalysesWorker, and ensure that the **only** work that the main thread
+// has to do is strictly DOM rendering work.
+
+const {
+ Visitor,
+ walk,
+ basisTotalBytes,
+ basisTotalCount,
+} = require("resource://devtools/shared/heapsnapshot/CensusUtils.js");
+
+// Monotonically increasing integer for CensusTreeNode `id`s.
+let censusTreeNodeIdCounter = 0;
+
+/**
+ * Return true if the given object is a SavedFrame stack object, false otherwise.
+ *
+ * @param {any} obj
+ * @returns {Boolean}
+ */
+function isSavedFrame(obj) {
+ return Object.prototype.toString.call(obj) === "[object SavedFrame]";
+}
+
+/**
+ * A CensusTreeNodeCache maps from SavedFrames to CensusTreeNodes. It is used when
+ * aggregating multiple SavedFrame allocation stack keys into a tree of many
+ * CensusTreeNodes. Each stack may share older frames, and we want to preserve
+ * this sharing when converting to CensusTreeNode, so before creating a new
+ * CensusTreeNode, we look for an existing one in one of our CensusTreeNodeCaches.
+ */
+function CensusTreeNodeCache() {}
+CensusTreeNodeCache.prototype = null;
+
+/**
+ * The value of a single entry stored in a CensusTreeNodeCache. It is a pair of
+ * the CensusTreeNode for this cache value, and the subsequent
+ * CensusTreeNodeCache for this node's children.
+ *
+ * @param {SavedFrame} frame
+ * The frame being cached.
+ */
+function CensusTreeNodeCacheValue() {
+ // The CensusTreeNode for this cache value.
+ this.node = undefined;
+ // The CensusTreeNodeCache for this frame's children.
+ this.children = undefined;
+}
+
+CensusTreeNodeCacheValue.prototype = null;
+
+/**
+ * Create a unique string for the given SavedFrame (ignoring the frame's parent
+ * chain) that can be used as a hash to key this frame within a CensusTreeNodeCache.
+ *
+ * NB: We manually hash rather than using an ES6 Map because we are purposely
+ * ignoring the parent chain and wish to consider frames with everything the
+ * same except their parents as the same.
+ *
+ * @param {SavedFrame} frame
+ * The SavedFrame object we would like to lookup in or insert into a
+ * CensusTreeNodeCache.
+ *
+ * @returns {String}
+ * The unique string that can be used as a key in a CensusTreeNodeCache.
+ */
+CensusTreeNodeCache.hashFrame = function (frame) {
+ return `FRAME,${frame.functionDisplayName},${frame.source},${frame.line},${frame.column},${frame.asyncCause}`;
+};
+
+/**
+ * Create a unique string for the given CensusTreeNode **with regards to
+ * siblings at the current depth of the tree, not within the whole tree.** It
+ * can be used as a hash to key this node within a CensusTreeNodeCache.
+ *
+ * @param {CensusTreeNode} node
+ * The node we would like to lookup in or insert into a cache.
+ *
+ * @returns {String}
+ * The unique string that can be used as a key in a CensusTreeNodeCache.
+ */
+CensusTreeNodeCache.hashNode = function (node) {
+ return isSavedFrame(node.name)
+ ? CensusTreeNodeCache.hashFrame(node.name)
+ : `NODE,${node.name}`;
+};
+
+/**
+ * Insert the given CensusTreeNodeCacheValue whose node.name is a SavedFrame
+ * object in the given cache.
+ *
+ * @param {CensusTreeNodeCache} cache
+ * @param {CensusTreeNodeCacheValue} value
+ */
+CensusTreeNodeCache.insertFrame = function (cache, value) {
+ cache[CensusTreeNodeCache.hashFrame(value.node.name)] = value;
+};
+
+/**
+ * Insert the given value in the cache.
+ *
+ * @param {CensusTreeNodeCache} cache
+ * @param {CensusTreeNodeCacheValue} value
+ */
+CensusTreeNodeCache.insertNode = function (cache, value) {
+ if (isSavedFrame(value.node.name)) {
+ CensusTreeNodeCache.insertFrame(cache, value);
+ } else {
+ cache[CensusTreeNodeCache.hashNode(value.node)] = value;
+ }
+};
+
+/**
+ * Lookup `frame` in `cache` and return its value if it exists.
+ *
+ * @param {CensusTreeNodeCache} cache
+ * @param {SavedFrame} frame
+ *
+ * @returns {undefined|CensusTreeNodeCacheValue}
+ */
+CensusTreeNodeCache.lookupFrame = function (cache, frame) {
+ return cache[CensusTreeNodeCache.hashFrame(frame)];
+};
+
+/**
+ * Lookup `node` in `cache` and return its value if it exists.
+ *
+ * @param {CensusTreeNodeCache} cache
+ * @param {CensusTreeNode} node
+ *
+ * @returns {undefined|CensusTreeNodeCacheValue}
+ */
+CensusTreeNodeCache.lookupNode = function (cache, node) {
+ return isSavedFrame(node.name)
+ ? CensusTreeNodeCache.lookupFrame(cache, node.name)
+ : cache[CensusTreeNodeCache.hashNode(node)];
+};
+
+/**
+ * Add `child` to `parent`'s set of children and store the parent ID
+ * on the child.
+ *
+ * @param {CensusTreeNode} parent
+ * @param {CensusTreeNode} child
+ */
+function addChild(parent, child) {
+ if (!parent.children) {
+ parent.children = [];
+ }
+ child.parent = parent.id;
+ parent.children.push(child);
+}
+
+/**
+ * Get an array of each frame in the provided stack.
+ *
+ * @param {SavedFrame} stack
+ * @returns {Array<SavedFrame>}
+ */
+function getArrayOfFrames(stack) {
+ const frames = [];
+ let frame = stack;
+ while (frame) {
+ frames.push(frame);
+ frame = frame.parent;
+ }
+ frames.reverse();
+ return frames;
+}
+
+/**
+ * Given an `edge` to a sub-`report` whose structure is described by
+ * `breakdown`, create a CensusTreeNode tree.
+ *
+ * @param {Object} breakdown
+ * The breakdown specifying the structure of the given report.
+ *
+ * @param {Object} report
+ * The census report.
+ *
+ * @param {null|String|SavedFrame} edge
+ * The edge leading to this report from the parent report.
+ *
+ * @param {CensusTreeNodeCache} cache
+ * The cache of CensusTreeNodes we have already made for the siblings of
+ * the node being created. The existing nodes are reused when possible.
+ *
+ * @param {Object} outParams
+ * The return values are attached to this object after this function
+ * returns. Because we create a CensusTreeNode for each frame in a
+ * SavedFrame stack edge, there may multiple nodes per sub-report.
+ *
+ * - top: The deepest node in the CensusTreeNode subtree created.
+ *
+ * - bottom: The shallowest node in the CensusTreeNode subtree created.
+ * This is null if the shallowest node in the subtree was
+ * found in the `cache` and reused.
+ *
+ * Note that top and bottom are not necessarily different. In the case
+ * where there is a 1:1 correspondence between an edge in the report and
+ * a CensusTreeNode, top and bottom refer to the same node.
+ */
+function makeCensusTreeNodeSubTree(breakdown, report, edge, cache, outParams) {
+ if (!isSavedFrame(edge)) {
+ const node = new CensusTreeNode(edge);
+ outParams.top = outParams.bottom = node;
+ return;
+ }
+
+ const frames = getArrayOfFrames(edge);
+ let currentCache = cache;
+ let prevNode;
+ for (let i = 0, length = frames.length; i < length; i++) {
+ const frame = frames[i];
+
+ // Get or create the CensusTreeNodeCacheValue for this frame. If we already
+ // have a CensusTreeNodeCacheValue (and hence a CensusTreeNode) for this
+ // frame, we don't need to add the node to the previous node's children as
+ // we have already done that. If we don't have a CensusTreeNodeCacheValue
+ // and CensusTreeNode for this frame, then create one and make sure to hook
+ // it up as a child of the previous node.
+ let isNewNode = false;
+ let val = CensusTreeNodeCache.lookupFrame(currentCache, frame);
+ if (!val) {
+ isNewNode = true;
+ val = new CensusTreeNodeCacheValue();
+ val.node = new CensusTreeNode(frame);
+
+ CensusTreeNodeCache.insertFrame(currentCache, val);
+ if (prevNode) {
+ addChild(prevNode, val.node);
+ }
+ }
+
+ if (i === 0) {
+ outParams.bottom = isNewNode ? val.node : null;
+ }
+ if (i === length - 1) {
+ outParams.top = val.node;
+ }
+
+ prevNode = val.node;
+
+ if (i !== length - 1 && !val.children) {
+ // This is not the last frame and therefore this node will have
+ // children, which we must cache.
+ val.children = new CensusTreeNodeCache();
+ }
+
+ currentCache = val.children;
+ }
+}
+
+/**
+ * A Visitor that walks a census report and creates the corresponding
+ * CensusTreeNode tree.
+ */
+function CensusTreeNodeVisitor() {
+ // The root of the resulting CensusTreeNode tree.
+ this._root = null;
+
+ // The stack of CensusTreeNodes that we are in the process of building while
+ // walking the census report.
+ this._nodeStack = [];
+
+ // To avoid unnecessary allocations, we reuse the same out parameter object
+ // passed to `makeCensusTreeNodeSubTree` every time we call it.
+ this._outParams = {
+ top: null,
+ bottom: null,
+ };
+
+ // The stack of `CensusTreeNodeCache`s that we use to aggregate many
+ // SavedFrame stacks into a single CensusTreeNode tree.
+ this._cacheStack = [new CensusTreeNodeCache()];
+
+ // The current index in the DFS of the census report tree.
+ this._index = -1;
+}
+
+CensusTreeNodeVisitor.prototype = Object.create(Visitor);
+
+/**
+ * Create the CensusTreeNode subtree for this sub-report and link it to the
+ * parent CensusTreeNode.
+ *
+ * @overrides Visitor.prototype.enter
+ */
+CensusTreeNodeVisitor.prototype.enter = function (breakdown, report, edge) {
+ this._index++;
+
+ const cache = this._cacheStack[this._cacheStack.length - 1];
+ makeCensusTreeNodeSubTree(breakdown, report, edge, cache, this._outParams);
+ const { top, bottom } = this._outParams;
+
+ if (!this._root) {
+ this._root = bottom;
+ } else if (bottom) {
+ addChild(this._nodeStack[this._nodeStack.length - 1], bottom);
+ }
+
+ this._cacheStack.push(new CensusTreeNodeCache());
+ this._nodeStack.push(top);
+};
+
+function values(cache) {
+ return Object.keys(cache).map(k => cache[k]);
+}
+
+function isNonEmpty(node) {
+ return (node.children !== undefined && node.children.length)
+ || node.bytes !== 0
+ || node.count !== 0;
+}
+
+/**
+ * We have finished adding children to the CensusTreeNode subtree for the
+ * current sub-report. Make sure that the children are sorted for every node in
+ * the subtree.
+ *
+ * @overrides Visitor.prototype.exit
+ */
+CensusTreeNodeVisitor.prototype.exit = function (breakdown, report, edge) {
+ // Ensure all children are sorted and have their counts/bytes aggregated. We
+ // only need to consider cache children here, because other children
+ // correspond to other sub-reports and we already fixed them up in an earlier
+ // invocation of `exit`.
+
+ function dfs(node, childrenCache) {
+ if (childrenCache) {
+ const childValues = values(childrenCache);
+ for (let i = 0, length = childValues.length; i < length; i++) {
+ dfs(childValues[i].node, childValues[i].children);
+ }
+ }
+
+ node.totalCount = node.count;
+ node.totalBytes = node.bytes;
+
+ if (node.children) {
+ // Prune empty leaves.
+ node.children = node.children.filter(isNonEmpty);
+
+ node.children.sort(compareByTotal);
+
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ node.totalCount += node.children[i].totalCount;
+ node.totalBytes += node.children[i].totalBytes;
+ }
+ }
+ }
+
+ const top = this._nodeStack.pop();
+ const cache = this._cacheStack.pop();
+ dfs(top, cache);
+};
+
+/**
+ * @overrides Visitor.prototype.count
+ */
+CensusTreeNodeVisitor.prototype.count = function (breakdown, report, edge) {
+ const node = this._nodeStack[this._nodeStack.length - 1];
+ node.reportLeafIndex = this._index;
+
+ if (breakdown.count) {
+ node.count = report.count;
+ }
+
+ if (breakdown.bytes) {
+ node.bytes = report.bytes;
+ }
+};
+
+/**
+ * Get the root of the resulting CensusTreeNode tree.
+ *
+ * @returns {CensusTreeNode}
+ */
+CensusTreeNodeVisitor.prototype.root = function () {
+ if (!this._root) {
+ throw new Error("Attempt to get the root before walking the census report!");
+ }
+
+ if (this._nodeStack.length) {
+ throw new Error("Attempt to get the root while walking the census report!");
+ }
+
+ return this._root;
+};
+
+/**
+ * Create a single, uninitialized CensusTreeNode.
+ *
+ * @param {null|String|SavedFrame} name
+ */
+function CensusTreeNode(name) {
+ // Display name for this CensusTreeNode. Either null, a string, or a
+ // SavedFrame.
+ this.name = name;
+
+ // The number of bytes occupied by matching things in the heap snapshot.
+ this.bytes = 0;
+
+ // The sum of `this.bytes` and `child.totalBytes` for each child in
+ // `this.children`.
+ this.totalBytes = 0;
+
+ // The number of things in the heap snapshot that match this node in the
+ // census tree.
+ this.count = 0;
+
+ // The sum of `this.count` and `child.totalCount` for each child in
+ // `this.children`.
+ this.totalCount = 0;
+
+ // An array of this node's children, or undefined if it has no children.
+ this.children = undefined;
+
+ // The unique ID of this node.
+ this.id = ++censusTreeNodeIdCounter;
+
+ // If present, the unique ID of this node's parent. If this node does not have
+ // a parent, then undefined.
+ this.parent = undefined;
+
+ // The `reportLeafIndex` property allows mapping a CensusTreeNode node back to
+ // a leaf in the census report it was generated from. It is always one of the
+ // following variants:
+ //
+ // * A `Number` index pointing a leaf report in a pre-order DFS traversal of
+ // this CensusTreeNode's census report.
+ //
+ // * A `Set` object containing such indices, when this is part of an inverted
+ // CensusTreeNode tree and multiple leaves in the report map onto this node.
+ //
+ // * Finally, `undefined` when no leaves in the census report correspond with
+ // this node.
+ //
+ // The first and third cases are the common cases. The second case is rather
+ // uncommon, and to avoid doubling the number of allocations when creating
+ // CensusTreeNode trees, and objects that get structured cloned when sending
+ // such trees from the HeapAnalysesWorker to the main thread, we only allocate
+ // a Set object once a node actually does have multiple leaves it corresponds
+ // to.
+ this.reportLeafIndex = undefined;
+}
+
+CensusTreeNode.prototype = null;
+
+/**
+ * Compare the given nodes by their `totalBytes` properties, and breaking ties
+ * with the `totalCount`, `bytes`, and `count` properties (in that order).
+ *
+ * @param {CensusTreeNode} node1
+ * @param {CensusTreeNode} node2
+ *
+ * @returns {Number}
+ * A number suitable for using with Array.prototype.sort.
+ */
+function compareByTotal(node1, node2) {
+ return Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes)
+ || Math.abs(node2.totalCount) - Math.abs(node1.totalCount)
+ || Math.abs(node2.bytes) - Math.abs(node1.bytes)
+ || Math.abs(node2.count) - Math.abs(node1.count);
+}
+
+/**
+ * Compare the given nodes by their `bytes` properties, and breaking ties with
+ * the `count`, `totalBytes`, and `totalCount` properties (in that order).
+ *
+ * @param {CensusTreeNode} node1
+ * @param {CensusTreeNode} node2
+ *
+ * @returns {Number}
+ * A number suitable for using with Array.prototype.sort.
+ */
+function compareBySelf(node1, node2) {
+ return Math.abs(node2.bytes) - Math.abs(node1.bytes)
+ || Math.abs(node2.count) - Math.abs(node1.count)
+ || Math.abs(node2.totalBytes) - Math.abs(node1.totalBytes)
+ || Math.abs(node2.totalCount) - Math.abs(node1.totalCount);
+}
+
+/**
+ * Given a parent cache value from a tree we are building and a child node from
+ * a tree we are basing the new tree off of, if we already have a corresponding
+ * node in the parent's children cache, merge this node's counts with
+ * it. Otherwise, create the corresponding node, add it to the parent's children
+ * cache, and create the parent->child edge.
+ *
+ * @param {CensusTreeNodeCacheValue} parentCachevalue
+ * @param {CensusTreeNode} node
+ *
+ * @returns {CensusTreeNodeCacheValue}
+ * The new or extant child node's corresponding cache value.
+ */
+function insertOrMergeNode(parentCacheValue, node) {
+ if (!parentCacheValue.children) {
+ parentCacheValue.children = new CensusTreeNodeCache();
+ }
+
+ let val = CensusTreeNodeCache.lookupNode(parentCacheValue.children, node);
+
+ if (val) {
+ // When inverting, it is possible that multiple leaves in the census report
+ // get merged into a single CensusTreeNode node. When this occurs, switch
+ // from a single index to a set of indices.
+ if (val.node.reportLeafIndex !== undefined &&
+ val.node.reportLeafIndex !== node.reportLeafIndex) {
+ if (typeof val.node.reportLeafIndex === "number") {
+ const oldIndex = val.node.reportLeafIndex;
+ val.node.reportLeafIndex = new Set();
+ val.node.reportLeafIndex.add(oldIndex);
+ val.node.reportLeafIndex.add(node.reportLeafIndex);
+ } else {
+ val.node.reportLeafIndex.add(node.reportLeafIndex);
+ }
+ }
+
+ val.node.count += node.count;
+ val.node.bytes += node.bytes;
+ } else {
+ val = new CensusTreeNodeCacheValue();
+
+ val.node = new CensusTreeNode(node.name);
+ val.node.reportLeafIndex = node.reportLeafIndex;
+ val.node.count = node.count;
+ val.node.totalCount = node.totalCount;
+ val.node.bytes = node.bytes;
+ val.node.totalBytes = node.totalBytes;
+
+ addChild(parentCacheValue.node, val.node);
+ CensusTreeNodeCache.insertNode(parentCacheValue.children, val);
+ }
+
+ return val;
+}
+
+/**
+ * Given an un-inverted CensusTreeNode tree, return the corresponding inverted
+ * CensusTreeNode tree. The input tree is not modified. The resulting inverted
+ * tree is sorted by self bytes rather than by total bytes.
+ *
+ * @param {CensusTreeNode} tree
+ * The un-inverted tree.
+ *
+ * @returns {CensusTreeNode}
+ * The corresponding inverted tree.
+ */
+function invert(tree) {
+ const inverted = new CensusTreeNodeCacheValue();
+ inverted.node = new CensusTreeNode(null);
+
+ // Do a depth-first search of the un-inverted tree. As we reach each leaf,
+ // take the path from the old root to the leaf, reverse that path, and add it
+ // to the new, inverted tree's root.
+
+ const path = [];
+ (function addInvertedPaths(node) {
+ path.push(node);
+
+ if (node.children) {
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ addInvertedPaths(node.children[i]);
+ }
+ } else {
+ // We found a leaf node, add the reverse path to the inverted tree.
+ let currentCacheValue = inverted;
+ for (let i = path.length - 1; i >= 0; i--) {
+ currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]);
+ }
+ }
+
+ path.pop();
+ }(tree));
+
+ // Ensure that the root node always has the totals.
+ inverted.node.totalBytes = tree.totalBytes;
+ inverted.node.totalCount = tree.totalCount;
+
+ return inverted.node;
+}
+
+/**
+ * Given a CensusTreeNode tree and predicate function, create the tree
+ * containing only the nodes in any path `(node_0, node_1, ..., node_n-1)` in
+ * the given tree where `predicate(node_j)` is true for `0 <= j < n`, `node_0`
+ * is the given tree's root, and `node_n-1` is a leaf in the given tree. The
+ * given tree is left unmodified.
+ *
+ * @param {CensusTreeNode} tree
+ * @param {Function} predicate
+ *
+ * @returns {CensusTreeNode}
+ */
+function filter(tree, predicate) {
+ const filtered = new CensusTreeNodeCacheValue();
+ filtered.node = new CensusTreeNode(null);
+
+ // Do a DFS over the given tree. If the predicate returns true for any node,
+ // add that node and its whole subtree to the filtered tree.
+
+ const path = [];
+ let match = false;
+
+ function addMatchingNodes(node) {
+ path.push(node);
+
+ let oldMatch = match;
+ if (!match && predicate(node)) {
+ match = true;
+ }
+
+ if (node.children) {
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ addMatchingNodes(node.children[i]);
+ }
+ } else if (match) {
+ // We found a matching leaf node, add it to the filtered tree.
+ let currentCacheValue = filtered;
+ for (let i = 0, length = path.length; i < length; i++) {
+ currentCacheValue = insertOrMergeNode(currentCacheValue, path[i]);
+ }
+ }
+
+ match = oldMatch;
+ path.pop();
+ }
+
+ if (tree.children) {
+ for (let i = 0, length = tree.children.length; i < length; i++) {
+ addMatchingNodes(tree.children[i]);
+ }
+ }
+
+ filtered.node.count = tree.count;
+ filtered.node.totalCount = tree.totalCount;
+ filtered.node.bytes = tree.bytes;
+ filtered.node.totalBytes = tree.totalBytes;
+
+ return filtered.node;
+}
+
+/**
+ * Given a filter string, return a predicate function that takes a node and
+ * returns true iff the node matches the filter.
+ *
+ * @param {String} filterString
+ * @returns {Function}
+ */
+function makeFilterPredicate(filterString) {
+ return function (node) {
+ if (!node.name) {
+ return false;
+ }
+
+ if (isSavedFrame(node.name)) {
+ return node.name.source.includes(filterString)
+ || (node.name.functionDisplayName || "").includes(filterString)
+ || (node.name.asyncCause || "").includes(filterString);
+ }
+
+ return String(node.name).includes(filterString);
+ };
+}
+
+/**
+ * Takes a report from a census (`dbg.memory.takeCensus()`) and the breakdown
+ * used to generate the census and returns a structure used to render
+ * a tree to display the data.
+ *
+ * Returns a recursive "CensusTreeNode" object, looking like:
+ *
+ * CensusTreeNode = {
+ * // `children` if it exists, is sorted by `bytes`, if they are leaf nodes.
+ * children: ?[<CensusTreeNode...>],
+ * name: <?String>
+ * count: <?Number>
+ * bytes: <?Number>
+ * id: <?Number>
+ * parent: <?Number>
+ * }
+ *
+ * @param {Object} breakdown
+ * The breakdown used to generate the census report.
+ *
+ * @param {Object} report
+ * The census report generated with the specified breakdown.
+ *
+ * @param {Object} options
+ * Configuration options.
+ * - invert: Whether to invert the resulting tree or not. Defaults to
+ * false, ie uninverted.
+ *
+ * @returns {CensusTreeNode}
+ */
+exports.censusReportToCensusTreeNode = function (breakdown, report,
+ options = {
+ invert: false,
+ filter: null
+ }) {
+ // Reset the counter so that turning the same census report into a
+ // CensusTreeNode tree repeatedly is idempotent.
+ censusTreeNodeIdCounter = 0;
+
+ const visitor = new CensusTreeNodeVisitor();
+ walk(breakdown, report, visitor);
+ let result = visitor.root();
+
+ if (options.invert) {
+ result = invert(result);
+ }
+
+ if (typeof options.filter === "string") {
+ result = filter(result, makeFilterPredicate(options.filter));
+ }
+
+ // If the report is a delta report that was generated by diffing two other
+ // reports, make sure to use the basis totals rather than the totals of the
+ // difference.
+ if (typeof report[basisTotalBytes] === "number") {
+ result.totalBytes = report[basisTotalBytes];
+ result.totalCount = report[basisTotalCount];
+ }
+
+ // Inverting and filtering could have messed up the sort order, so do a
+ // depth-first search of the tree and ensure that siblings are sorted.
+ const comparator = options.invert ? compareBySelf : compareByTotal;
+ (function ensureSorted(node) {
+ if (node.children) {
+ node.children.sort(comparator);
+ for (let i = 0, length = node.children.length; i < length; i++) {
+ ensureSorted(node.children[i]);
+ }
+ }
+ }(result));
+
+ return result;
+};
diff --git a/devtools/shared/heapsnapshot/moz.build b/devtools/shared/heapsnapshot/moz.build
new file mode 100644
index 000000000..9a915e426
--- /dev/null
+++ b/devtools/shared/heapsnapshot/moz.build
@@ -0,0 +1,15 @@
+# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# 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/.
+
+DevToolsModules(
+ 'census-tree-node.js',
+ 'CensusUtils.js',
+ 'DominatorTreeNode.js',
+ 'HeapAnalysesClient.js',
+ 'HeapAnalysesWorker.js',
+ 'HeapSnapshotFileUtils.js',
+ '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 };
+};