/* Any copyright is dedicated to the Public Domain.
   http://creativecommons.org/publicdomain/zero/1.0/ */
"use strict";

// Test that we can get the set of immediately dominated nodes for any given
// node and that this forms a tree.

function run_test() {
  const dominatorTree = saveHeapSnapshotAndComputeDominatorTree();
  equal(
    typeof dominatorTree.getImmediatelyDominated,
    "function",
    "getImmediatelyDominated should be a function"
  );

  // Do a traversal of the dominator tree.
  //
  // Note that we don't assert directly, only if we get an unexpected
  // value. There are just way too many nodes in the heap graph to assert for
  // every one. This test would constantly time out and assertion messages would
  // overflow the log size.

  const root = dominatorTree.root;
  equal(
    dominatorTree.getImmediateDominator(root),
    null,
    "The root should not have a parent"
  );

  const seen = new Set();
  const stack = [root];
  while (stack.length) {
    const top = stack.pop();

    if (seen.has(top)) {
      ok(
        false,
        "This is a tree, not a graph: we shouldn't have " +
          "multiple edges to the same node"
      );
    }
    seen.add(top);
    if (seen.size % 1000 === 0) {
      dumpn("Progress update: seen size = " + seen.size);
    }

    const newNodes = dominatorTree.getImmediatelyDominated(top);
    if (Object.prototype.toString.call(newNodes) !== "[object Array]") {
      ok(
        false,
        "getImmediatelyDominated should return an array for known node ids"
      );
    }

    const topSize = dominatorTree.getRetainedSize(top);

    let lastSize = Infinity;
    for (let i = 0; i < newNodes.length; i++) {
      if (typeof newNodes[i] !== "number") {
        ok(false, "Every dominated id should be a number");
      }

      if (dominatorTree.getImmediateDominator(newNodes[i]) !== top) {
        ok(false, "child's parent should be the expected parent");
      }

      const thisSize = dominatorTree.getRetainedSize(newNodes[i]);

      if (thisSize >= topSize) {
        ok(
          false,
          "the size of children in the dominator tree should" +
            " always be less than that of their parent"
        );
      }

      if (thisSize > lastSize) {
        ok(
          false,
          "children should be sorted by greatest to least retained size, " +
            "lastSize = " +
            lastSize +
            ", thisSize = " +
            thisSize
        );
      }

      lastSize = thisSize;
      stack.push(newNodes[i]);
    }
  }

  ok(true, "Successfully walked the tree");
  dumpn("Walked " + seen.size + " nodes");

  do_test_finished();
}