Quelle  census-tree-node.js

/* 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.
 */
class CensusTreeNodeCache {
  /**
   * 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.
   */
  static hashFrame(frame) {
    // eslint-disable-next-line max-len
    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.
   */
  static hashNode(node) {
    return isSavedFrame(node.name)
      ? this.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
   */
  static insertFrame(cache, value) {
    cache[this.hashFrame(value.node.name)] = value;
  }

  /**
   * Insert the given value in the cache.
   *
   * @param {CensusTreeNodeCache} cache
   * @param {CensusTreeNodeCacheValue} value
   */
  static insertNode(cache, value) {
    if (isSavedFrame(value.node.name)) {
      this.insertFrame(cache, value);
    } else {
      cache[this.hashNode(value.node)] = value;
    }
  }

  /**
   * Lookup `frame` in `cache` and return its value if it exists.
   *
   * @param {CensusTreeNodeCache} cache
   * @param {SavedFrame} frame
   *
   * @returns {undefined|CensusTreeNodeCacheValue}
   */
  static lookupFrame(cache, frame) {
    return cache[this.hashFrame(frame)];
  }

  /**
   * Lookup `node` in `cache` and return its value if it exists.
   *
   * @param {CensusTreeNodeCache} cache
   * @param {CensusTreeNode} node
   *
   * @returns {undefined|CensusTreeNodeCacheValue}
   */
  static lookupNode(cache, node) {
    return isSavedFrame(node.name)
      ? this.lookupFrame(cache, node.name)
      : cache[this.hashNode(node)];
  }
}

/**
 * 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.
 */
class CensusTreeNodeCacheValue {
  constructor() {
    // The CensusTreeNode for this cache value.
    this.node = undefined;
    // The CensusTreeNodeCache for this frame's children.
    this.children = undefined;
  }
}

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

  /**
   * Create the CensusTreeNode subtree for this sub-report and link it to the
   * parent CensusTreeNode.
   *
   * @override
   */
  enter(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);
  }

  /**
   * 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.
   *
   * @override
   */
  exit() {
    // 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);
  }

  /**
   * @override
   */
  count(breakdown, report) {
    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}
   */
  root() {
    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;
  }
}

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
  );
}

/**
 * Create a single, uninitialized CensusTreeNode.
 */
class CensusTreeNode {
  /**
   *
   * @param {null | string | SavedFrame} name
   */
  constructor(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;
  }
}

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

    const 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;
};