Source code
Revision control
Copy as Markdown
Other Tools
/* 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
"use strict";
const {
immutableUpdate,
const {
Visitor,
walk,
const {
deduplicatePaths,
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) {
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;
}
};