1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
/* Any copyright is dedicated to the Public Domain.
http://creativecommons.org/publicdomain/zero/1.0/ */
// Test that we can get the set of immediately dominated nodes for any given
// node and that this forms a tree.
function run_test() {
var 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.
var root = dominatorTree.root;
equal(dominatorTree.getImmediateDominator(root), null,
"The root should not have a parent");
var seen = new Set();
var stack = [root];
while (stack.length > 0) {
var 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);
}
var newNodes = dominatorTree.getImmediatelyDominated(top);
if (Object.prototype.toString.call(newNodes) !== "[object Array]") {
ok(false, "getImmediatelyDominated should return an array for known node ids");
}
var topSize = dominatorTree.getRetainedSize(top);
var lastSize = Infinity;
for (var 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");
}
var 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();
}
|
