Bug 1260307 - Add the `CensusUtils.getReportLeaves` utility for getting leaves in a census report; r=jimb
authorNick Fitzgerald <fitzgen@gmail.com>
Tue, 29 Mar 2016 08:54:00 +0200
changeset 290857 85d231a303cfe702634035ae2470e343842e9e21
parent 290856 f3ea2fdec3196f6a498c7fe8c1e48e460331f602
child 290858 f3160a1e4fb6e866cad99f8b183a456f258c7f17
push id19656
push usergwagner@mozilla.com
push dateMon, 04 Apr 2016 13:43:23 +0000
treeherderb2g-inbound@e99061fde28a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjimb
bugs1260307
milestone48.0a1
Bug 1260307 - Add the `CensusUtils.getReportLeaves` utility for getting leaves in a census report; r=jimb
devtools/shared/heapsnapshot/CensusUtils.js
devtools/shared/heapsnapshot/tests/unit/test_getReportLeaves_01.js
devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
--- a/devtools/shared/heapsnapshot/CensusUtils.js
+++ b/devtools/shared/heapsnapshot/CensusUtils.js
@@ -151,17 +151,17 @@ function recursiveWalk(breakdown, edge, 
  * @param {Object} report
  *        The census report.
  *
  * @param {Visitor} visitor
  *        The Visitor instance to call into while traversing.
  */
 function walk(breakdown, report, visitor) {
   recursiveWalk(breakdown, null, report, visitor);
-};
+}
 exports.walk = walk;
 
 /*** diff *******************************************************************/
 
 /**
  * Return true if the object is a Map, false otherwise. Works with Map objects
  * from other globals, unlike `instanceof`.
  *
@@ -409,8 +409,55 @@ exports.countToBucketBreakdown = functio
 
   const result = {};
   for (let i = 0, length = keys.length; i < length; i++) {
     result[keys[i]] = vals[i];
   }
 
   return Object.freeze(result);
 };
+
+/**
+ * A Visitor for finding report leaves by their DFS index.
+ */
+function GetLeavesVisitor(targetIndices) {
+  this._index = -1;
+  this._targetIndices = targetIndices;
+  this._leaves = [];
+}
+
+GetLeavesVisitor.prototype = Object.create(Visitor.prototype);
+
+/**
+ * @overrides Visitor.prototype.enter
+ */
+GetLeavesVisitor.prototype.enter = function(breakdown, report, edge) {
+  this._index++;
+  if (this._targetIndices.has(this._index)) {
+    this._leaves.push(report);
+  }
+};
+
+/**
+ * Get the accumulated report leaves after traversal.
+ */
+GetLeavesVisitor.prototype.leaves = function() {
+  if (this._index === -1) {
+    throw new Error("Attempt to call `leaves` before traversing report!");
+  }
+  return this._leaves;
+};
+
+/**
+ * Given a set of indices of leaves in a pre-order depth-first traversal of the
+ * given census report, return the leaves.
+ *
+ * @param {Set<Number>} indices
+ * @param {Object} breakdown
+ * @param {Object} report
+ *
+ * @returns {Array<Object>}
+ */
+exports.getReportLeaves = function(indices, breakdown, report) {
+  const visitor = new GetLeavesVisitor(indices);
+  walk(breakdown, report, visitor);
+  return visitor.leaves();
+};
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_getReportLeaves_01.js
@@ -0,0 +1,114 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+"use strict";
+
+// Test basic functionality of `CensusUtils.getReportLeaves`.
+
+function run_test() {
+  const BREAKDOWN = {
+    by: "coarseType",
+    objects: {
+      by: "objectClass",
+      then: { by: "count", count: true, bytes: true },
+      other: { by: "count", count: true, bytes: true },
+    },
+    strings: { by: "count", count: true, bytes: true },
+    scripts: {
+      by: "filename",
+      then: {
+        by: "internalType",
+        then: { by: "count", count: true, bytes: true },
+      },
+      noFilename: {
+        by: "internalType",
+        then: { by: "count", count: true, bytes: true },
+      },
+    },
+    other: {
+      by: "internalType",
+      then: { by: "count", count: true, bytes: true },
+    },
+  };
+
+  const REPORT = {
+    objects: {
+      Array: { count: 6, bytes: 60 },
+      Function: { count: 1, bytes: 10 },
+      Object: { count: 1, bytes: 10 },
+      RegExp: { count: 1, bytes: 10 },
+      other: { count: 0, bytes: 0 },
+    },
+    strings: { count: 1, bytes: 10 },
+    scripts: {
+      "foo.js": {
+        JSScript: { count: 1, bytes: 10 },
+        "js::jit::IonScript": { count: 1, bytes: 10 },
+      },
+      noFilename: {
+        JSScript: { count: 1, bytes: 10 },
+        "js::jit::IonScript": { count: 1, bytes: 10 },
+      },
+    },
+    other: {
+      "js::Shape": { count: 7, bytes: 70 },
+      "js::BaseShape": { count: 1, bytes: 10 },
+    },
+  };
+
+  const root = censusReportToCensusTreeNode(BREAKDOWN, REPORT);
+  dumpn("CensusTreeNode tree = " + JSON.stringify(root, null, 4));
+
+  (function assertEveryNodeCanFindItsLeaf(node) {
+    if (node.reportLeafIndex) {
+      const [ leaf ] = CensusUtils.getReportLeaves(new Set([node.reportLeafIndex]),
+                                                   BREAKDOWN,
+                                                   REPORT);
+      ok(leaf, "Should be able to find leaf for a node with a reportLeafIndex = " + node.reportLeafIndex);
+    }
+
+    if (node.children) {
+      for (let child of node.children) {
+        assertEveryNodeCanFindItsLeaf(child);
+      }
+    }
+  }(root));
+
+  // Test finding multiple leaves at a time.
+
+  function find(name, node) {
+    if (node.name === name) {
+      return node;
+    }
+
+    if (node.children) {
+      for (let child of node.children) {
+        const found = find(name, child);
+        if (found) {
+          return found;
+        }
+      }
+    }
+  }
+
+  const arrayNode = find("Array", root);
+  ok(arrayNode);
+  equal(typeof arrayNode.reportLeafIndex, "number");
+
+  const shapeNode = find("js::Shape", root);
+  ok(shapeNode);
+  equal(typeof shapeNode.reportLeafIndex, "number");
+
+  const indices = new Set([arrayNode.reportLeafIndex, shapeNode.reportLeafIndex]);
+  const leaves = CensusUtils.getReportLeaves(indices, BREAKDOWN, REPORT);
+  equal(leaves.length, 2);
+
+  // `getReportLeaves` does not guarantee order of the results, so handle both
+  // cases.
+  ok(leaves.some(l => l === REPORT.objects.Array));
+  ok(leaves.some(l => l === REPORT.other["js::Shape"]));
+
+  // Test that bad indices do not yield results.
+
+  const none = CensusUtils.getReportLeaves(new Set([999999999999]), BREAKDOWN, REPORT);
+  equal(none.length, 0);
+}
--- a/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
+++ b/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
@@ -45,16 +45,17 @@ support-files =
 [test_DominatorTreeNode_insert_01.js]
 [test_DominatorTreeNode_insert_02.js]
 [test_DominatorTreeNode_insert_03.js]
 [test_DominatorTreeNode_LabelAndShallowSize_01.js]
 [test_DominatorTreeNode_LabelAndShallowSize_02.js]
 [test_DominatorTreeNode_LabelAndShallowSize_03.js]
 [test_DominatorTreeNode_LabelAndShallowSize_04.js]
 [test_DominatorTreeNode_partialTraversal_01.js]
+[test_getReportLeaves_01.js]
 [test_HeapAnalyses_computeDominatorTree_01.js]
 [test_HeapAnalyses_computeDominatorTree_02.js]
 [test_HeapAnalyses_deleteHeapSnapshot_01.js]
 [test_HeapAnalyses_deleteHeapSnapshot_02.js]
 [test_HeapAnalyses_deleteHeapSnapshot_03.js]
 [test_HeapAnalyses_getCreationTime_01.js]
 [test_HeapAnalyses_getDominatorTree_01.js]
 [test_HeapAnalyses_getDominatorTree_02.js]