Reclassify heapsnapshot and nsJSInspector as not part of devtools

This resolves Issue #316

1 files changed, 748 insertions, 0 deletions

diff --git a/dom/heapsnapshot/census-tree-node.js b/dom/heapsnapshot/census-tree-node.js
new file mode 100644
index 000000000..b041e77f9
--- /dev/null
+++ b/dom/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;
+};