tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

test_DominatorTree_05.js (2664B)

      1 /* Any copyright is dedicated to the Public Domain.
      2   http://creativecommons.org/publicdomain/zero/1.0/ */
      3 "use strict";
      4 
      5 // Test that we can get the set of immediately dominated nodes for any given
      6 // node and that this forms a tree.
      7 
      8 function run_test() {
      9  const dominatorTree = saveHeapSnapshotAndComputeDominatorTree();
     10  equal(
     11    typeof dominatorTree.getImmediatelyDominated,
     12    "function",
     13    "getImmediatelyDominated should be a function"
     14  );
     15 
     16  // Do a traversal of the dominator tree.
     17  //
     18  // Note that we don't assert directly, only if we get an unexpected
     19  // value. There are just way too many nodes in the heap graph to assert for
     20  // every one. This test would constantly time out and assertion messages would
     21  // overflow the log size.
     22 
     23  const root = dominatorTree.root;
     24  equal(
     25    dominatorTree.getImmediateDominator(root),
     26    null,
     27    "The root should not have a parent"
     28  );
     29 
     30  const seen = new Set();
     31  const stack = [root];
     32  while (stack.length) {
     33    const top = stack.pop();
     34 
     35    if (seen.has(top)) {
     36      ok(
     37        false,
     38        "This is a tree, not a graph: we shouldn't have " +
     39          "multiple edges to the same node"
     40      );
     41    }
     42    seen.add(top);
     43    if (seen.size % 1000 === 0) {
     44      dumpn("Progress update: seen size = " + seen.size);
     45    }
     46 
     47    const newNodes = dominatorTree.getImmediatelyDominated(top);
     48    if (Object.prototype.toString.call(newNodes) !== "[object Array]") {
     49      ok(
     50        false,
     51        "getImmediatelyDominated should return an array for known node ids"
     52      );
     53    }
     54 
     55    const topSize = dominatorTree.getRetainedSize(top);
     56 
     57    let lastSize = Infinity;
     58    for (let i = 0; i < newNodes.length; i++) {
     59      if (typeof newNodes[i] !== "number") {
     60        ok(false, "Every dominated id should be a number");
     61      }
     62 
     63      if (dominatorTree.getImmediateDominator(newNodes[i]) !== top) {
     64        ok(false, "child's parent should be the expected parent");
     65      }
     66 
     67      const thisSize = dominatorTree.getRetainedSize(newNodes[i]);
     68 
     69      if (thisSize >= topSize) {
     70        ok(
     71          false,
     72          "the size of children in the dominator tree should" +
     73            " always be less than that of their parent"
     74        );
     75      }
     76 
     77      if (thisSize > lastSize) {
     78        ok(
     79          false,
     80          "children should be sorted by greatest to least retained size, " +
     81            "lastSize = " +
     82            lastSize +
     83            ", thisSize = " +
     84            thisSize
     85        );
     86      }
     87 
     88      lastSize = thisSize;
     89      stack.push(newNodes[i]);
     90    }
     91  }
     92 
     93  ok(true, "Successfully walked the tree");
     94  dumpn("Walked " + seen.size + " nodes");
     95 
     96  do_test_finished();
     97 }