diff options
Diffstat (limited to 'devtools/shared/heapsnapshot/census-tree-node.js')
| -rw-r--r-- | devtools/shared/heapsnapshot/census-tree-node.js | 748 |
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; -}; |