Follow-up to 4e2e9be6a - Move HeapSnapshot DevTools-only Modules back to DevTools

I am so done with this.

Resolves #316

9 files changed, 2355 insertions, 0 deletions

diff --git a/devtools/shared/heapsnapshot/CensusUtils.js b/devtools/shared/heapsnapshot/CensusUtils.js
new file mode 100644
index 0000000000..36bdd2d820
--- /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 0000000000..13a847fd04
--- /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 0000000000..98601a2b1c
--- /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 0000000000..d07d67f80e
--- /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 0000000000..abd44fc309
--- /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 0000000000..b041e77f9c
--- /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 0000000000..9a915e4268
--- /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 0000000000..2d97b7de93
--- /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 };
+};
diff --git a/devtools/shared/moz.build b/devtools/shared/moz.build
index 9dd4a20d65..e4de1d84a5 100644
--- a/devtools/shared/moz.build
+++ b/devtools/shared/moz.build
@@ -14,6 +14,7 @@ DIRS += [
     'discovery',
     'fronts',
     'gcli',
+    'heapsnapshot',
     'inspector',
     'jsbeautify',
     'layout',