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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/* 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();
}
|
