diff options
author | Matt A. Tobin <email@mattatobin.com> | 2020-02-22 17:32:39 -0500 |
---|---|---|
committer | Matt A. Tobin <email@mattatobin.com> | 2020-02-22 17:32:39 -0500 |
commit | 4e2e9be6abed3225406b466099e397acc0f914d2 (patch) | |
tree | 023551018892b8e76ae80e63a08d9d6a27c21a77 /devtools/shared/heapsnapshot/DominatorTreeNode.js | |
parent | a7888b8cf20691a4090715ab9b055ec3cb75f5e8 (diff) | |
download | UXP-4e2e9be6abed3225406b466099e397acc0f914d2.tar UXP-4e2e9be6abed3225406b466099e397acc0f914d2.tar.gz UXP-4e2e9be6abed3225406b466099e397acc0f914d2.tar.lz UXP-4e2e9be6abed3225406b466099e397acc0f914d2.tar.xz UXP-4e2e9be6abed3225406b466099e397acc0f914d2.zip |
Reclassify heapsnapshot and nsJSInspector as not part of devtools
This resolves Issue #316
Diffstat (limited to 'devtools/shared/heapsnapshot/DominatorTreeNode.js')
-rw-r--r-- | devtools/shared/heapsnapshot/DominatorTreeNode.js | 336 |
1 files changed, 0 insertions, 336 deletions
diff --git a/devtools/shared/heapsnapshot/DominatorTreeNode.js b/devtools/shared/heapsnapshot/DominatorTreeNode.js deleted file mode 100644 index 13a847fd0..000000000 --- a/devtools/shared/heapsnapshot/DominatorTreeNode.js +++ /dev/null @@ -1,336 +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"; - -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; - } -}; |