1 files changed, 370 insertions, 0 deletions
diff --git a/devtools/shared/heapsnapshot/DominatorTreeNode.js b/devtools/shared/heapsnapshot/DominatorTreeNode.js
new file mode 100644
index 0000000000..75fad98c11
--- /dev/null
+++ b/devtools/shared/heapsnapshot/DominatorTreeNode.js
@@ -0,0 +1,370 @@
+/* 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.js");
+
+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;
+    }
+
+    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(
+  nodeTree,
+  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(nodeTree, 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 (const node of treeNodes) {
+    const id = node.nodeId;
+    idToTreeNode.set(id, node);
+    targets.push(id);
+  }
+
+  const shortestPaths = snapshot.computeShortestPaths(
+    start,
+    targets,
+    maxNumPaths
+  );
+
+  for (const [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;
+  }
+};