summaryrefslogtreecommitdiffstats
path: root/devtools/shared/heapsnapshot/census-tree-node.js
diff options
context:
space:
mode:
Diffstat (limited to 'devtools/shared/heapsnapshot/census-tree-node.js')
-rw-r--r--devtools/shared/heapsnapshot/census-tree-node.js748
1 files changed, 0 insertions, 748 deletions
diff --git a/devtools/shared/heapsnapshot/census-tree-node.js b/devtools/shared/heapsnapshot/census-tree-node.js
deleted file mode 100644
index b041e77f9..000000000
--- a/devtools/shared/heapsnapshot/census-tree-node.js
+++ /dev/null
@@ -1,748 +0,0 @@
-/* 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;
-};