Bug 1235883 - Add support for inserting lazily loaded children into a DominatorTreeNode tree; r=jsantell
authorNick Fitzgerald <fitzgen@gmail.com>
Wed, 06 Jan 2016 13:57:12 -0800
changeset 278928 e4226ac7285fa8e8013ff5ab09241132c9070d1f
parent 278927 b1a0a9378c6409bbc0daa0091a5f1fb49a5d89eb
child 278929 a49d0ac82b04527a5673c71bc9568e7b34a6c409
push id69924
push usercbook@mozilla.com
push dateThu, 07 Jan 2016 11:20:40 +0000
treeherdermozilla-inbound@9768993a4e2b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjsantell
bugs1235883
milestone46.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1235883 - Add support for inserting lazily loaded children into a DominatorTreeNode tree; r=jsantell This commit adds the `DominatorTreeNode.insert` method to insert new DominatorTreeNode children that have just been loaded from the HeapAnalysesWorker into an existing partially complete DominatorTreeNode tree. This is done in a persistent and immutable fashion so that we can use === to differentiate different generations of `DominatorTreeNode` trees but still share the vast majority of the underlying structure. As infrastructure for the insertion, HeapAnalysesWorker's `getImmediatelyDominated` response also returns the path from the root to the node whose immediately dominated children are being fetched. This makes it much easier to know where to insert the newly loaded children.
devtools/shared/heapsnapshot/DominatorTreeNode.js
devtools/shared/heapsnapshot/HeapAnalysesClient.js
devtools/shared/heapsnapshot/HeapAnalysesWorker.js
devtools/shared/heapsnapshot/tests/unit/head_heapsnapshot.js
devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_01.js
devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_02.js
devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_03.js
devtools/shared/heapsnapshot/tests/unit/test_HeapAnalyses_getImmediatelyDominated_01.js
devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
--- a/devtools/shared/heapsnapshot/DominatorTreeNode.js
+++ b/devtools/shared/heapsnapshot/DominatorTreeNode.js
@@ -1,14 +1,15 @@
 /* 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 { Visitor, walk } = require("resource://devtools/shared/heapsnapshot/CensusUtils.js");
+const { immutableUpdate } = require("resource://devtools/shared/ThreadSafeDevToolsUtils.js");
 
 const DEFAULT_MAX_DEPTH = 4;
 const DEFAULT_MAX_SIBLINGS = 15;
 
 /**
  * A single node in a dominator tree.
  *
  * @param {NodeId} nodeId
@@ -208,8 +209,45 @@ DominatorTreeNode.partialTraversal = fun
       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);
+};
--- a/devtools/shared/heapsnapshot/HeapAnalysesClient.js
+++ b/devtools/shared/heapsnapshot/HeapAnalysesClient.js
@@ -209,12 +209,15 @@ HeapAnalysesClient.prototype.getDominato
  * @returns {Promise<Object>}
  *          A promise of an object with the following properties:
  *          - {Array<DominatorTreeNode>} nodes
  *            The requested nodes that are immediately dominated by the node
  *            identified by `opts.nodeId`.
  *          - {Boolean} moreChildrenAvailable
  *            True iff there are more children available after the returned
  *            nodes.
+ *          - {Array<NodeId>} path
+ *            The path through the tree from the root to these node's parent, eg
+ *            [root's id, child of root's id, child of child of root's id, ..., `nodeId`].
  */
 HeapAnalysesClient.prototype.getImmediatelyDominated = function (opts) {
   return this._worker.performTask("getImmediatelyDominated", opts);
 };
--- a/devtools/shared/heapsnapshot/HeapAnalysesWorker.js
+++ b/devtools/shared/heapsnapshot/HeapAnalysesWorker.js
@@ -189,12 +189,20 @@ workerHelper.createTask(self, "getImmedi
       const node = new DominatorTreeNode(id, label, shallowSize, retainedSize);
       node.parentId = nodeId;
       // DominatorTree.getImmediatelyDominated will always return non-null here
       // because we got the id directly from the dominator tree.
       node.moreChildrenAvailable = dominatorTree.getImmediatelyDominated(id).length > 0;
       return node;
     });
 
+  const path = [];
+  let id = nodeId;
+  do {
+    path.push(id);
+    id = dominatorTree.getImmediateDominator(id);
+  } while (id !== null);
+  path.reverse();
+
   const moreChildrenAvailable = childIds.length > end;
 
-  return { nodes, moreChildrenAvailable };
+  return { nodes, moreChildrenAvailable, path };
 });
--- a/devtools/shared/heapsnapshot/tests/unit/head_heapsnapshot.js
+++ b/devtools/shared/heapsnapshot/tests/unit/head_heapsnapshot.js
@@ -320,8 +320,58 @@ function assertLabelAndShallowSize(break
   dumpn("Expected shallow size: " + expectedShallowSize);
   dumpn("Actual shallow size: " + visitor.shallowSize());
   equal(visitor.shallowSize(), expectedShallowSize, "Shallow size should be correct");
 
   dumpn("Expected label: " + JSON.stringify(expectedLabel, null, 4));
   dumpn("Actual label: " + JSON.stringify(visitor.label(), null, 4));
   assertStructurallyEquivalent(visitor.label(), expectedLabel);
 }
+
+// Counter for mock DominatorTreeNode ids.
+let TEST_NODE_ID_COUNTER = 0;
+
+/**
+ * Create a mock DominatorTreeNode for testing, with sane defaults. Override any
+ * property by providing it on `opts`. Optionally pass child nodes as well.
+ *
+ * @param {Object} opts
+ * @param {Array<DominatorTreeNode>?} children
+ *
+ * @returns {DominatorTreeNode}
+ */
+function makeTestDominatorTreeNode(opts, children) {
+  const nodeId = TEST_NODE_ID_COUNTER++;
+
+  const node = Object.assign({
+    nodeId,
+    label: undefined,
+    shallowSize: 1,
+    retainedSize: (children || []).reduce((size, c) => size + c.retainedSize, 1),
+    parentId: undefined,
+    children,
+    moreChildrenAvailable: true,
+  }, opts);
+
+  if (children && children.length) {
+    children.map(c => c.parentId = node.nodeId);
+  }
+
+  return node;
+}
+
+/**
+ * Insert `newChildren` into the given dominator `tree` as specified by the
+ * `path` from the root to the node the `newChildren` should be inserted
+ * beneath. Assert that the resulting tree matches `expected`.
+ */
+function assertDominatorTreeNodeInsertion(tree, path, newChildren, moreChildrenAvailable, expected) {
+  dumpn("Inserting new children into a dominator tree:");
+  dumpn("Dominator tree: " + JSON.stringify(tree, null, 2));
+  dumpn("Path: " + JSON.stringify(path, null, 2));
+  dumpn("New children: " + JSON.stringify(newChildren, null, 2));
+  dumpn("Expected resulting tree: " + JSON.stringify(expected, null, 2));
+
+  const actual = DominatorTreeNode.insert(tree, path, newChildren, moreChildrenAvailable);
+  dumpn("Actual resulting tree: " + JSON.stringify(actual, null, 2));
+
+  assertStructurallyEquivalent(actual, expected);
+}
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_01.js
@@ -0,0 +1,112 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test that we can insert new children into an existing DominatorTreeNode tree.
+
+const tree = makeTestDominatorTreeNode({ nodeId: 1000 }, [
+  makeTestDominatorTreeNode({}),
+  makeTestDominatorTreeNode({ nodeId: 2000 }, [
+    makeTestDominatorTreeNode({}),
+    makeTestDominatorTreeNode({ nodeId: 3000 }),
+    makeTestDominatorTreeNode({}),
+  ]),
+  makeTestDominatorTreeNode({}),
+]);
+
+const path = [1000, 2000, 3000];
+
+const newChildren = [
+  makeTestDominatorTreeNode({ parentId: 3000 }),
+  makeTestDominatorTreeNode({ parentId: 3000 }),
+];
+
+const moreChildrenAvailable = false;
+
+const expected = {
+  nodeId: 1000,
+  parentId: undefined,
+  label: undefined,
+  shallowSize: 1,
+  retainedSize: 7,
+  children: [
+    {
+      nodeId: 0,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 1000,
+      moreChildrenAvailable: true,
+      children: undefined,
+    },
+    {
+      nodeId: 2000,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 4,
+      parentId: 1000,
+      children: [
+        {
+          nodeId: 1,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 2000,
+          moreChildrenAvailable: true,
+          children: undefined,
+        },
+        {
+          nodeId: 3000,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 2000,
+          children: [
+            {
+              nodeId: 7,
+              parentId: 3000,
+              label: undefined,
+              shallowSize: 1,
+              retainedSize: 1,
+              moreChildrenAvailable: true,
+              children: undefined,
+            },
+            {
+              nodeId: 8,
+              parentId: 3000,
+              label: undefined,
+              shallowSize: 1,
+              retainedSize: 1,
+              moreChildrenAvailable: true,
+              children: undefined,
+            },
+          ],
+          moreChildrenAvailable: false
+        },
+        {
+          nodeId: 3,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 2000,
+          moreChildrenAvailable: true,
+          children: undefined,
+        },
+      ],
+      moreChildrenAvailable: true
+    },
+    {
+      nodeId: 5,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 1000,
+      moreChildrenAvailable: true,
+      children: undefined,
+    }
+  ],
+  moreChildrenAvailable: true
+};
+
+function run_test() {
+  assertDominatorTreeNodeInsertion(tree, path, newChildren, moreChildrenAvailable, expected);
+}
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_02.js
@@ -0,0 +1,30 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test attempting to insert new children into an existing DominatorTreeNode
+// tree with a bad path.
+
+const tree = makeTestDominatorTreeNode({}, [
+  makeTestDominatorTreeNode({}),
+  makeTestDominatorTreeNode({}, [
+    makeTestDominatorTreeNode({}),
+    makeTestDominatorTreeNode({}),
+    makeTestDominatorTreeNode({}),
+  ]),
+  makeTestDominatorTreeNode({}),
+]);
+
+const path = [111111, 222222, 333333];
+
+const newChildren = [
+  makeTestDominatorTreeNode({ parentId: 333333 }),
+  makeTestDominatorTreeNode({ parentId: 333333 }),
+];
+
+const moreChildrenAvailable = false;
+
+const expected = tree;
+
+function run_test() {
+  assertDominatorTreeNodeInsertion(tree, path, newChildren, moreChildrenAvailable, expected);
+}
new file mode 100644
--- /dev/null
+++ b/devtools/shared/heapsnapshot/tests/unit/test_DominatorTreeNode_insert_03.js
@@ -0,0 +1,117 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test inserting new children into an existing DominatorTreeNode at the root.
+
+const tree = makeTestDominatorTreeNode({ nodeId: 666 }, [
+  makeTestDominatorTreeNode({}),
+  makeTestDominatorTreeNode({}, [
+    makeTestDominatorTreeNode({}),
+    makeTestDominatorTreeNode({}),
+    makeTestDominatorTreeNode({}),
+  ]),
+  makeTestDominatorTreeNode({}),
+]);
+
+const path = [666];
+
+const newChildren = [
+  makeTestDominatorTreeNode({
+    nodeId: 777,
+    parentId: 666
+  }),
+  makeTestDominatorTreeNode({
+    nodeId: 888,
+    parentId: 666
+  }),
+];
+
+const moreChildrenAvailable = false;
+
+const expected = {
+  nodeId: 666,
+  label: undefined,
+  parentId: undefined,
+  shallowSize: 1,
+  retainedSize: 7,
+  children: [
+    {
+      nodeId: 0,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 666,
+      moreChildrenAvailable: true,
+      children: undefined
+    },
+    {
+      nodeId: 4,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 4,
+      parentId: 666,
+      children: [
+        {
+          nodeId: 1,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 4,
+          moreChildrenAvailable: true,
+          children: undefined
+        },
+        {
+          nodeId: 2,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 4,
+          moreChildrenAvailable: true,
+          children: undefined
+        },
+        {
+          nodeId: 3,
+          label: undefined,
+          shallowSize: 1,
+          retainedSize: 1,
+          parentId: 4,
+          moreChildrenAvailable: true,
+          children: undefined
+        }
+      ],
+      moreChildrenAvailable: true
+    },
+    {
+      nodeId: 5,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 666,
+      moreChildrenAvailable: true,
+      children: undefined
+    },
+    {
+      nodeId: 777,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 666,
+      moreChildrenAvailable: true,
+      children: undefined
+    },
+    {
+      nodeId: 888,
+      label: undefined,
+      shallowSize: 1,
+      retainedSize: 1,
+      parentId: 666,
+      moreChildrenAvailable: true,
+      children: undefined
+    }
+  ],
+  moreChildrenAvailable: false
+}
+
+function run_test() {
+  assertDominatorTreeNodeInsertion(tree, path, newChildren, moreChildrenAvailable, expected);
+}
--- a/devtools/shared/heapsnapshot/tests/unit/test_HeapAnalyses_getImmediatelyDominated_01.js
+++ b/devtools/shared/heapsnapshot/tests/unit/test_HeapAnalyses_getImmediatelyDominated_01.js
@@ -36,24 +36,28 @@ add_task(function* () {
     nodeId: partialTree.nodeId,
     startIndex: 0,
     maxCount: partialTree.children.length - 1
   });
 
   ok(Array.isArray(response.nodes));
   ok(response.nodes.every(node => node.parentId === partialTree.nodeId));
   ok(response.moreChildrenAvailable);
+  equal(response.path.length, 1);
+  equal(response.path[0], partialTree.nodeId);
 
   // Next, test getting a subset of children available.
   const secondResponse = yield client.getImmediatelyDominated({
     dominatorTreeId,
     breakdown,
     nodeId: partialTree.nodeId,
     startIndex: 0,
     maxCount: Infinity
   });
 
   ok(Array.isArray(secondResponse.nodes));
   ok(secondResponse.nodes.every(node => node.parentId === partialTree.nodeId));
   ok(!secondResponse.moreChildrenAvailable);
+  equal(secondResponse.path.length, 1);
+  equal(secondResponse.path[0], partialTree.nodeId);
 
   client.destroy();
 });
--- a/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
+++ b/devtools/shared/heapsnapshot/tests/unit/xpcshell.ini
@@ -28,16 +28,19 @@ support-files =
 [test_census-tree-node-06.js]
 [test_census-tree-node-07.js]
 [test_census-tree-node-08.js]
 [test_DominatorTree_01.js]
 [test_DominatorTree_02.js]
 [test_DominatorTree_03.js]
 [test_DominatorTree_04.js]
 [test_DominatorTree_05.js]
+[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_HeapAnalyses_computeDominatorTree_01.js]
 [test_HeapAnalyses_computeDominatorTree_02.js]
 [test_HeapAnalyses_getCreationTime_01.js]
 [test_HeapAnalyses_getDominatorTree_01.js]