tor-browser

DominatorTreeNode.js (10260B)

---

/* 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.js");

const DEFAULT_MAX_DEPTH = 4;
const DEFAULT_MAX_SIBLINGS = 15;
const DEFAULT_MAX_NUM_PATHS = 5;

/**
* 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.
*/
class LabelAndShallowSizeVisitor extends Visitor {
 constructor() {
   super();

   // 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;
 }
 /**
  * @override
  */
 enter(breakdown, report, edge) {
   if (this._labelPieces && edge) {
     this._labelPieces.push(edge);
   }
 }
 /**
  * @override
  */
 exit(breakdown, report, edge) {
   if (this._labelPieces && edge) {
     this._labelPieces.pop();
   }
 }
 /**
  * @override
  */
 count(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}
  */
 label() {
   return this._label;
 }
 /**
  * Get the shallow size of the node this visitor visited.
  *
  * @returns {number}
  */
 shallowSize() {
   return this._shallowSize;
 }
}

/**
* A single node in a dominator tree.
*/
class DominatorTreeNode {
 /**
  * @param {NodeId} nodeId
  * @param {NodeSize} retainedSize
  */
 constructor(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;
 }

 /**
  * Add `child` to the `parent`'s set of children.
  *
  * @param {DominatorTreeNode} parent
  * @param {DominatorTreeNode} child
  */
 static addChild(parent, child) {
   if (parent.children === undefined) {
     parent.children = [];
   }

   parent.children.push(child);
   child.parentId = parent.nodeId;
 }

 /**
  * 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
  */
 static getLabelAndShallowSize(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}
  */
 static partialTraversal(
   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}
  */
 static insert(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}
  */
 static getNodeByIdAlongPath(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
  */
 static attachShortestPaths(
   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;
   }
 }

 static LabelAndShallowSizeVisitor = LabelAndShallowSizeVisitor;
}

module.exports = DominatorTreeNode;