16b45044d3c63ee9d6658ff91c859e84d79b46d8
[WebKit-https.git] / Source / WebInspectorUI / UserInterface / Workers / HeapSnapshot / HeapSnapshot.js
1 /*
2  * Copyright (C) 2011 Google Inc. All rights reserved.
3  * Copyright (C) 2016 Apple Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  *     * Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *     * Redistributions in binary form must reproduce the above
12  * copyright notice, this list of conditions and the following disclaimer
13  * in the documentation and/or other materials provided with the
14  * distribution.
15  *     * Neither the name of Google Inc. nor the names of its
16  * contributors may be used to endorse or promote products derived from
17  * this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 // nodes
33 // [<0:id>, <1:size>, <2:classNameTableIndex>, <3:flags>]
34 const nodeFieldCount = 4;
35 const nodeIdOffset = 0;
36 const nodeSizeOffset = 1;
37 const nodeClassNameOffset = 2;
38 const nodeFlagsOffset = 3;
39 const gcDebuggingNodeFieldCount = 7;
40
41 // node flags
42 const internalFlagsMask = (1 << 0);
43 const objectTypeMask = (1 << 1);
44
45 // edges
46 // [<0:fromId>, <1:toId>, <2:typeTableIndex>, <3:edgeDataIndexOrEdgeNameIndex>]
47 const edgeFieldCount = 4;
48 const edgeFromIdOffset = 0;
49 const edgeToIdOffset = 1;
50 const edgeTypeOffset = 2;
51 const edgeDataOffset = 3;
52
53 // Other constants.
54 const rootNodeIndex = 0;
55 const rootNodeOrdinal = 0;
56 const rootNodeIdentifier = 0;
57
58 // Version Differences:
59 //   - In Version 1, node[3] now named <flags> was the value 0 or 1 indicating not-internal or internal.
60 //   - In Version 2, this became a bitmask so multiple flags could be included without modifying the size.
61 //
62 // Terminology:
63 //   - `nodeIndex` is an index into the `nodes` list.
64 //   - `nodeOrdinal` is the order of the node in the `nodes` list. (nodeIndex / nodeFieldCount).
65 //   - `nodeIdentifier` is the node's id value. (nodes[nodeIndex + nodeIdOffset]).
66 //   - `edgeIndex` is an index into the `edges` list.
67 //
68 // Lists:
69 //   - _nodeOrdinalToFirstOutgoingEdge - `nodeOrdinal` to `edgeIndex` in `edges`.
70 //     Iterate edges by walking `edges` (edgeFieldCount) and checking if fromIdentifier is current.
71 //   - _nodeOrdinalToFirstIncomingEdge - `nodeOrdinal` to `incomingEdgeIndex` in `incomingEdges`.
72 //     Iterate edges by walking `incomingEdges` until `nodeOrdinal+1`'s first incoming edge index.
73 //   - _nodeOrdinalToDominatorNodeOrdinal - `nodeOrdinal` to `nodeOrdinal` of dominator.
74 //   - _nodeOrdinalToRetainedSizes - `nodeOrdinal` to retain size value.
75 //   - _nodeOrdinalIsDead - `nodeOrdinal` is dead or alive.
76 //
77 // Temporary Lists:
78 //   - nodeOrdinalToPostOrderIndex - `nodeOrdinal` to a `postOrderIndex`.
79 //   - postOrderIndexToNodeOrdinal - `postOrderIndex` to a `nodeOrdinal`.
80
81 let nextSnapshotIdentifier = 1;
82
83 HeapSnapshot = class HeapSnapshot
84 {
85     constructor(objectId, snapshotDataString, title = null, imported = false)
86     {
87         this._identifier = nextSnapshotIdentifier++;
88         this._objectId = objectId;
89         this._title = title;
90         this._imported = imported;
91
92         let json = JSON.parse(snapshotDataString);
93         snapshotDataString = null;
94
95         let {version, type, nodes, nodeClassNames, edges, edgeTypes, edgeNames} = json;
96         console.assert(version === 1 || version === 2, "Expect JavaScriptCore Heap Snapshot version 1 or 2");
97         console.assert(!type || (type === "Inspector" || type === "GCDebugging"), "Expect an Inspector / GCDebugging Heap Snapshot");
98
99         this._nodeFieldCount = type === "GCDebugging" ? gcDebuggingNodeFieldCount : nodeFieldCount;
100
101         this._nodes = nodes;
102         this._nodeCount = nodes.length / this._nodeFieldCount;
103
104         this._edges = edges;
105         this._edgeCount = edges.length / edgeFieldCount;
106
107         this._edgeTypesTable = edgeTypes;
108         this._edgeNamesTable = edgeNames;
109         this._nodeClassNamesTable = nodeClassNames;
110
111         this._totalSize = 0;
112         this._nodeIdentifierToOrdinal = new Map; // <node identifier> => nodeOrdinal
113         this._lastNodeIdentifier = 0;
114         for (let nodeIndex = 0; nodeIndex < nodes.length; nodeIndex += this._nodeFieldCount) {
115             let nodeOrdinal = nodeIndex / this._nodeFieldCount;
116             let nodeIdentifier = nodes[nodeIndex + nodeIdOffset];
117             this._nodeIdentifierToOrdinal.set(nodeIdentifier, nodeOrdinal);
118             this._totalSize += nodes[nodeIndex + nodeSizeOffset];
119             if (nodeIdentifier > this._lastNodeIdentifier)
120                 this._lastNodeIdentifier = nodeIdentifier;
121         }
122
123         // FIXME: Replace toIdentifier and fromIdentifier in edges with nodeIndex to reduce hash lookups?
124
125         this._nodeOrdinalToFirstOutgoingEdge = new Uint32Array(this._nodeCount); // nodeOrdinal => edgeIndex
126         this._buildOutgoingEdges();
127
128         this._nodeOrdinalToFirstIncomingEdge = new Uint32Array(this._nodeCount + 1); // nodeOrdinal => incomingNodes/incomingEdges index
129         this._incomingNodes = new Uint32Array(this._edgeCount); // from nodeOrdinals.
130         this._incomingEdges = new Uint32Array(this._edgeCount); // edgeIndex.
131         this._buildIncomingEdges();
132
133         let {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal} = this._buildPostOrderIndexes();
134
135         this._nodeOrdinalToDominatorNodeOrdinal = new Uint32Array(this._nodeCount);
136         this._nodeOrdinalIsGCRoot = new Uint8Array(this._nodeCount);
137         this._buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal);
138
139         nodeOrdinalToPostOrderIndex = null;
140
141         this._nodeOrdinalToRetainedSizes = new Uint32Array(this._nodeCount);
142         this._buildRetainedSizes(postOrderIndexToNodeOrdinal);
143
144         postOrderIndexToNodeOrdinal = null;
145
146         this._nodeOrdinalIsDead = new Uint8Array(this._nodeCount);
147
148         let {liveSize, categories} = HeapSnapshot.updateCategoriesAndMetadata(this);
149         this._liveSize = liveSize;
150         this._categories = categories;
151     }
152
153     // Static
154
155     static updateCategoriesAndMetadata(snapshot, allowNodeIdentifierCallback)
156     {
157         let liveSize = 0;
158         let categories = {};
159
160         let nodes = snapshot._nodes;
161         let nodeClassNamesTable = snapshot._nodeClassNamesTable;
162         let nodeOrdinalToRetainedSizes = snapshot._nodeOrdinalToRetainedSizes;
163         let nodeOrdinalIsDead = snapshot._nodeOrdinalIsDead;
164
165         // Skip the <root> node.
166         let firstNodeIndex = snapshot._nodeFieldCount;
167         let firstNodeOrdinal = 1;
168         for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += snapshot._nodeFieldCount, nodeOrdinal++) {
169             if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
170                 continue;
171
172             let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset];
173             let className = nodeClassNamesTable[classNameTableIndex];
174             let size = nodes[nodeIndex + nodeSizeOffset];
175             let retainedSize = nodeOrdinalToRetainedSizes[nodeOrdinal];
176             let flags = nodes[nodeIndex + nodeFlagsOffset];
177             let dead = nodeOrdinalIsDead[nodeOrdinal] ? true : false;
178
179             let category = categories[className];
180             if (!category)
181                 category = categories[className] = {className, size: 0, retainedSize: 0, count: 0, internalCount: 0, deadCount: 0, objectCount: 0};
182
183             category.size += size;
184             category.retainedSize += retainedSize;
185             category.count += 1;
186             if (flags & internalFlagsMask)
187                 category.internalCount += 1;
188             if (flags & objectTypeMask)
189                 category.objectCount += 1;
190             if (dead)
191                 category.deadCount += 1;
192             else
193                 liveSize += size;
194         }
195
196         return {liveSize, categories};
197     }
198
199     static allocationBucketCounts(snapshot, bucketSizes, allowNodeIdentifierCallback)
200     {
201         let counts = new Array(bucketSizes.length + 1);
202         let remainderBucket = counts.length - 1;
203         counts.fill(0);
204
205         let nodes = snapshot._nodes;
206
207         // Skip the <root> node.
208         let firstNodeIndex = snapshot._nodeFieldCount;
209
210     outer:
211         for (let nodeIndex = firstNodeIndex; nodeIndex < nodes.length; nodeIndex += snapshot._nodeFieldCount) {
212             if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
213                 continue;
214
215             let size = nodes[nodeIndex + nodeSizeOffset];
216             for (let i = 0; i < bucketSizes.length; ++i) {
217                 if (size < bucketSizes[i]) {
218                     counts[i]++;
219                     continue outer;
220                 }
221             }
222             counts[remainderBucket]++;
223         }
224
225         return counts;
226     }
227
228     static instancesWithClassName(snapshot, className, allowNodeIdentifierCallback)
229     {
230         let instances = [];
231
232         let nodes = snapshot._nodes;
233         let nodeClassNamesTable = snapshot._nodeClassNamesTable;
234
235         // Skip the <root> node.
236         let firstNodeIndex = snapshot._nodeFieldCount;
237         let firstNodeOrdinal = 1;
238         for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += snapshot._nodeFieldCount, nodeOrdinal++) {
239             if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
240                 continue;
241
242             let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset];
243             if (nodeClassNamesTable[classNameTableIndex] === className)
244                 instances.push(nodeIndex);
245         }
246
247         return instances.map(snapshot.serializeNode, snapshot);
248     }
249
250     // Worker Methods
251
252     allocationBucketCounts(bucketSizes)
253     {
254         return HeapSnapshot.allocationBucketCounts(this, bucketSizes);
255     }
256
257     instancesWithClassName(className)
258     {
259         return HeapSnapshot.instancesWithClassName(this, className);
260     }
261
262     update()
263     {
264         return HeapSnapshot.updateCategoriesAndMetadata(this);
265     }
266
267     nodeWithIdentifier(nodeIdentifier)
268     {
269         let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
270         let nodeIndex = nodeOrdinal * this._nodeFieldCount;
271         return this.serializeNode(nodeIndex);
272     }
273
274     shortestGCRootPath(nodeIdentifier)
275     {
276         // Returns an array from this node to a gcRoot node.
277         // E.g. [Node (target), Edge, Node, Edge, Node (root)].
278         // Internal nodes are avoided, so if the path is empty this
279         // node is either a gcRoot or only reachable via Internal nodes.
280
281         let paths = this._gcRootPathes(nodeIdentifier);
282         if (!paths.length)
283             return [];
284
285         paths.sort((a, b) => a.length - b.length);
286
287         let shortestPathWithGlobalObject = null;
288         for (let path of paths) {
289             let lastNodeIndex = path[path.length - 1].node;
290             if (this._isNodeGlobalObject(lastNodeIndex)) {
291                 shortestPathWithGlobalObject = path;
292                 break;
293             }
294         }
295
296         let shortestPath = shortestPathWithGlobalObject || paths[0];
297         console.assert("node" in shortestPath[0], "Path should start with a node");
298         console.assert("node" in shortestPath[shortestPath.length - 1], "Path should end with a node");
299
300         return shortestPath.map((component) => {
301             if (component.node)
302                 return this.serializeNode(component.node);
303             return this.serializeEdge(component.edge);
304         });
305     }
306
307     dominatedNodes(nodeIdentifier)
308     {
309         let dominatedNodes = [];
310
311         let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
312         for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
313             if (this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] === targetNodeOrdinal)
314                 dominatedNodes.push(nodeOrdinal * this._nodeFieldCount);
315         }
316
317         return dominatedNodes.map(this.serializeNode, this);
318     }
319
320     retainedNodes(nodeIdentifier)
321     {
322         let retainedNodes = [];
323         let edges = [];
324
325         let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
326         let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
327         for (; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) {
328             let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset];
329             let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier);
330             let toNodeIndex = toNodeOrdinal * this._nodeFieldCount;
331             retainedNodes.push(toNodeIndex);
332             edges.push(edgeIndex);
333         }
334
335         return {
336             retainedNodes: retainedNodes.map(this.serializeNode, this),
337             edges: edges.map(this.serializeEdge, this),
338         };
339     }
340
341     retainers(nodeIdentifier)
342     {
343         let retainers = [];
344         let edges = [];
345
346         let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
347         let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
348         let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
349         for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) {
350             let fromNodeOrdinal = this._incomingNodes[edgeIndex];
351             let fromNodeIndex = fromNodeOrdinal * this._nodeFieldCount;
352             retainers.push(fromNodeIndex);
353             edges.push(this._incomingEdges[edgeIndex]);
354         }
355
356         return {
357             retainers: retainers.map(this.serializeNode, this),
358             edges: edges.map(this.serializeEdge, this),
359         };
360     }
361
362     updateDeadNodesAndGatherCollectionData(snapshots)
363     {
364         console.assert(!this._imported, "Should never use an imported snapshot to modify snapshots");
365         console.assert(snapshots.every((x) => !x._imported), "Should never modify nodes of imported snapshots");
366
367         let previousSnapshotIndex = snapshots.indexOf(this) - 1;
368         let previousSnapshot = snapshots[previousSnapshotIndex];
369         if (!previousSnapshot)
370             return null;
371
372         let lastNodeIdentifier = previousSnapshot._lastNodeIdentifier;
373
374         // All of the node identifiers that could have existed prior to this snapshot.
375         let known = new Map;
376         for (let nodeIndex = 0; nodeIndex < this._nodes.length; nodeIndex += this._nodeFieldCount) {
377             let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset];
378             if (nodeIdentifier > lastNodeIdentifier)
379                 continue;
380             known.set(nodeIdentifier, nodeIndex);
381         }
382
383         // Determine which node identifiers have since been deleted.
384         let collectedNodesList = [];
385         for (let nodeIndex = 0; nodeIndex < previousSnapshot._nodes.length; nodeIndex += this._nodeFieldCount) {
386             let nodeIdentifier = previousSnapshot._nodes[nodeIndex + nodeIdOffset];
387             let wasDeleted = !known.has(nodeIdentifier);
388             if (wasDeleted)
389                 collectedNodesList.push(nodeIdentifier);
390         }
391
392         // Update dead nodes in previous snapshots.
393         let affectedSnapshots = [];
394         for (let snapshot of snapshots) {
395             if (snapshot === this)
396                 break;
397             if (snapshot._markDeadNodes(collectedNodesList))
398                 affectedSnapshots.push(snapshot._identifier);
399         }
400
401         // Convert list to a map.
402         let collectedNodes = {};
403         for (let i = 0; i < collectedNodesList.length; ++i)
404             collectedNodes[collectedNodesList[i]] = true;
405
406         return {
407             collectedNodes,
408             affectedSnapshots,
409         };
410     }
411
412     // Public
413
414     serialize()
415     {
416         return {
417             identifier: this._identifier,
418             title: this._title,
419             totalSize: this._totalSize,
420             totalObjectCount: this._nodeCount - 1, // <root>.
421             liveSize: this._liveSize,
422             categories: this._categories,
423             imported: this._imported,
424         };
425     }
426
427     serializeNode(nodeIndex)
428     {
429         console.assert((nodeIndex % this._nodeFieldCount) === 0, "Invalid nodeIndex to serialize");
430
431         let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset];
432         let nodeOrdinal = nodeIndex / this._nodeFieldCount;
433         let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
434         let hasChildren = this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier;
435         let nodeFlags = this._nodes[nodeIndex + nodeFlagsOffset];
436
437         let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal];
438         let dominatorNodeIndex = dominatorNodeOrdinal * this._nodeFieldCount;
439         let dominatorNodeIdentifier = this._nodes[dominatorNodeIndex + nodeIdOffset];
440
441         return {
442             id: nodeIdentifier,
443             className: this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]],
444             size: this._nodes[nodeIndex + nodeSizeOffset],
445             retainedSize: this._nodeOrdinalToRetainedSizes[nodeOrdinal],
446             internal: nodeFlags & internalFlagsMask ? true : false,
447             isObjectType: nodeFlags & objectTypeMask ? true : false,
448             gcRoot: this._nodeOrdinalIsGCRoot[nodeOrdinal] ? true : false,
449             dead: this._nodeOrdinalIsDead[nodeOrdinal] ? true : false,
450             dominatorNodeIdentifier,
451             hasChildren,
452         };
453     }
454
455     serializeEdge(edgeIndex)
456     {
457         console.assert((edgeIndex % edgeFieldCount) === 0, "Invalid edgeIndex to serialize");
458
459         let edgeType = this._edgeTypesTable[this._edges[edgeIndex + edgeTypeOffset]];
460         let edgeData = this._edges[edgeIndex + edgeDataOffset];
461         switch (edgeType) {
462         case "Internal":
463             // edgeData can be ignored.
464             break;
465         case "Property":
466         case "Variable":
467             // edgeData is a table index.
468             edgeData = this._edgeNamesTable[edgeData];
469             break;
470         case "Index":
471             // edgeData is the index.
472             break;
473         default:
474             console.error("Unexpected edge type: " + edgeType);
475             break;
476         }
477
478         return {
479             from: this._edges[edgeIndex + edgeFromIdOffset],
480             to: this._edges[edgeIndex + edgeToIdOffset],
481             type: edgeType,
482             data: edgeData,
483         };
484     }
485
486     // Private
487
488     _buildOutgoingEdges()
489     {
490         let lastFromIdentifier = -1;
491         for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
492             let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset];
493             console.assert(lastFromIdentifier <= fromIdentifier, "Edge list should be ordered by from node identifier");
494             if (fromIdentifier !== lastFromIdentifier) {
495                 let nodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier);
496                 this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal] = edgeIndex;
497                 lastFromIdentifier = fromIdentifier;
498             }
499         }
500     }
501
502     _buildIncomingEdges()
503     {
504         // First calculate the count of incoming edges for each node.
505         for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
506             let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
507             let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
508             this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal]++;
509         }
510
511         // Replace the counts with what will be the resulting index by running up the counts.
512         // Store the counts in what will be the edges list to use when placing edges in the list.
513         let runningFirstIndex = 0;
514         for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
515             let count = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
516             this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal] = runningFirstIndex;
517             this._incomingNodes[runningFirstIndex] = count;
518             runningFirstIndex += count;
519         }
520
521         // Fill in the incoming edges list. Use the count as an offset when placing edges in the list.
522         for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
523             let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset];
524             let fromNodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier);
525             let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
526             let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
527
528             let firstIncomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal];
529             console.assert(this._incomingNodes[firstIncomingEdgeIndex] > 0, "Should be expecting edges for this node");
530             let countAsOffset = this._incomingNodes[firstIncomingEdgeIndex]--;
531             let index = firstIncomingEdgeIndex + countAsOffset - 1;
532             this._incomingNodes[index] = fromNodeOrdinal;
533             this._incomingEdges[index] = edgeIndex;
534         }
535
536         // Duplicate value on the end. Incoming edge iteration walks firstIncomingEdge(ordinal) to firstIncomingEdge(ordinal+1).
537         this._nodeOrdinalToFirstIncomingEdge[this._nodeCount] = this._nodeOrdinalToFirstIncomingEdge[this._nodeCount - 1];
538     }
539
540     _buildPostOrderIndexes()
541     {
542         let postOrderIndex = 0;
543         let nodeOrdinalToPostOrderIndex = new Uint32Array(this._nodeCount);
544         let postOrderIndexToNodeOrdinal = new Uint32Array(this._nodeCount);
545
546         let stackNodes = new Uint32Array(this._nodeCount); // nodeOrdinal.
547         let stackEdges = new Uint32Array(this._nodeCount); // edgeIndex.
548         let visited = new Uint8Array(this._nodeCount);
549
550         let stackTop = 0;
551         stackNodes[stackTop] = rootNodeOrdinal;
552         stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal];
553
554         while (stackTop >= 0) {
555             let nodeOrdinal = stackNodes[stackTop];
556             let nodeIdentifier = this._nodes[(nodeOrdinal * this._nodeFieldCount) + nodeIdOffset];
557             let edgeIndex = stackEdges[stackTop];
558
559             if (this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier) {
560                 // Prepare the next child for the current node.
561                 stackEdges[stackTop] += edgeFieldCount;
562
563                 let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
564                 let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
565                 if (visited[toNodeOrdinal])
566                     continue;
567
568                 // Child.
569                 stackTop++;
570                 stackNodes[stackTop] = toNodeOrdinal;
571                 stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[toNodeOrdinal];
572                 visited[toNodeOrdinal] = 1;
573             } else {
574                 // Self.
575                 nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex;
576                 postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal;
577                 postOrderIndex++;
578                 stackTop--;
579             }
580         }
581
582         // Unvisited nodes.
583         // This can happen if the parent node was disallowed on the backend, but other nodes
584         // that were only referenced from that disallowed node were eventually allowed because
585         // they may be generic system objects. Give these nodes a postOrderIndex anyways.
586         if (postOrderIndex !== this._nodeCount) {
587             // Root was the last node visited. Revert assigning it an index, add it back at the end.
588             postOrderIndex--;
589
590             // Visit unvisited nodes.
591             for (let nodeOrdinal = 1; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
592                 if (visited[nodeOrdinal])
593                     continue;
594                 nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex;
595                 postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal;
596                 postOrderIndex++;
597             }
598
599             // Visit root again.
600             nodeOrdinalToPostOrderIndex[rootNodeOrdinal] = postOrderIndex;
601             postOrderIndexToNodeOrdinal[postOrderIndex] = rootNodeOrdinal;
602             postOrderIndex++;
603         }
604
605         console.assert(postOrderIndex === this._nodeCount, "All nodes were visited");
606         console.assert(nodeOrdinalToPostOrderIndex[rootNodeOrdinal] === this._nodeCount - 1, "Root node should have the last possible postOrderIndex");
607
608         return {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal};
609     }
610
611     _buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal)
612     {
613         // The algorithm is based on the article:
614         // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
615
616         let rootPostOrderIndex = this._nodeCount - 1;
617         let noEntry = this._nodeCount;
618
619         let affected = new Uint8Array(this._nodeCount);
620         let dominators = new Uint32Array(this._nodeCount);
621
622         // Initialize with unset value.
623         dominators.fill(noEntry);
624
625         // Mark the root's dominator value.
626         dominators[rootPostOrderIndex] = rootPostOrderIndex;
627
628         // Affect the root's children. Also use this opportunity to mark them as GC roots.
629         let rootEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal];
630         for (let edgeIndex = rootEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === rootNodeIdentifier; edgeIndex += edgeFieldCount) {
631             let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
632             let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
633             let toPostOrderIndex = nodeOrdinalToPostOrderIndex[toNodeOrdinal];
634             affected[toPostOrderIndex] = 1;
635             this._nodeOrdinalIsGCRoot[toNodeOrdinal] = 1;
636         }
637
638         let changed = true;
639         while (changed) {
640             changed = false;
641
642             for (let postOrderIndex = rootPostOrderIndex - 1; postOrderIndex >= 0; --postOrderIndex) {
643                 if (!affected[postOrderIndex])
644                     continue;
645                 affected[postOrderIndex] = 0;
646
647                 // The dominator is already the root, nothing to do.
648                 if (dominators[postOrderIndex] === rootPostOrderIndex)
649                     continue;
650
651                 let newDominatorIndex = noEntry;
652                 let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
653                 let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
654                 let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
655                 for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) {
656                     let fromNodeOrdinal = this._incomingNodes[edgeIndex];
657                     let fromPostOrderIndex = nodeOrdinalToPostOrderIndex[fromNodeOrdinal];
658                     if (dominators[fromPostOrderIndex] !== noEntry) {
659                         if (newDominatorIndex === noEntry)
660                             newDominatorIndex = fromPostOrderIndex;
661                         else {
662                             while (fromPostOrderIndex !== newDominatorIndex) {
663                                 while (fromPostOrderIndex < newDominatorIndex)
664                                     fromPostOrderIndex = dominators[fromPostOrderIndex];
665                                 while (newDominatorIndex < fromPostOrderIndex)
666                                     newDominatorIndex = dominators[newDominatorIndex];
667                             }
668                         }
669                     }
670                     if (newDominatorIndex === rootPostOrderIndex)
671                         break;
672                 }
673
674                 // Changed. Affect children.
675                 if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
676                     dominators[postOrderIndex] = newDominatorIndex;
677                     changed = true;
678
679                     let outgoingEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
680                     let nodeIdentifier = this._nodes[(nodeOrdinal * this._nodeFieldCount) + nodeIdOffset];
681                     for (let edgeIndex = outgoingEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) {
682                         let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset];
683                         let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier);
684                         let toNodePostOrder = nodeOrdinalToPostOrderIndex[toNodeOrdinal];
685                         affected[toNodePostOrder] = 1;
686                     }
687                 }
688             }
689         }
690
691         for (let postOrderIndex = 0; postOrderIndex < this._nodeCount; ++postOrderIndex) {
692             let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
693             let dominatorNodeOrdinal = postOrderIndexToNodeOrdinal[dominators[postOrderIndex]];
694             this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] = dominatorNodeOrdinal;
695         }
696     }
697
698     _buildRetainedSizes(postOrderIndexToNodeOrdinal)
699     {
700         // Self size.
701         for (let nodeIndex = 0, nodeOrdinal = 0; nodeOrdinal < this._nodeCount; nodeIndex += this._nodeFieldCount, nodeOrdinal++)
702             this._nodeOrdinalToRetainedSizes[nodeOrdinal] = this._nodes[nodeIndex + nodeSizeOffset];
703
704         // Attribute size to dominator.
705         for (let postOrderIndex = 0; postOrderIndex < this._nodeCount - 1; ++postOrderIndex) {
706             let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
707             let nodeRetainedSize = this._nodeOrdinalToRetainedSizes[nodeOrdinal];
708             let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal];
709             this._nodeOrdinalToRetainedSizes[dominatorNodeOrdinal] += nodeRetainedSize;
710         }
711     }
712
713     _markDeadNodes(collectedNodesList)
714     {
715         let affected = false;
716
717         for (let i = 0; i < collectedNodesList.length; ++i) {
718             let nodeIdentifier = collectedNodesList[i];
719             if (nodeIdentifier > this._lastNodeIdentifier)
720                 continue;
721             let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
722             this._nodeOrdinalIsDead[nodeOrdinal] = 1;
723             affected = true;
724         }
725
726         return affected;
727     }
728
729     _isNodeGlobalObject(nodeIndex)
730     {
731         let className = this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]];
732         return className === "Window"
733             || className === "JSWindowProxy"
734             || className === "GlobalObject";
735     }
736
737     _gcRootPathes(nodeIdentifier)
738     {
739         let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
740
741         if (this._nodeOrdinalIsGCRoot[targetNodeOrdinal])
742             return [];
743
744         // FIXME: Array push/pop can affect performance here, but in practice it hasn't been an issue.
745
746         let paths = [];
747         let currentPath = [];
748         let visited = new Uint8Array(this._nodeCount);
749
750         function visitNode(nodeOrdinal)
751         {
752             if (this._nodeOrdinalIsGCRoot[nodeOrdinal]) {
753                 let fullPath = currentPath.slice();
754                 let nodeIndex = nodeOrdinal * this._nodeFieldCount;
755                 fullPath.push({node: nodeIndex});
756                 paths.push(fullPath);
757                 return;
758             }
759
760             if (visited[nodeOrdinal])
761                 return;
762             visited[nodeOrdinal] = 1;
763
764             let nodeIndex = nodeOrdinal * this._nodeFieldCount;
765             currentPath.push({node: nodeIndex});
766
767             // Loop in reverse order because edges were added in reverse order.
768             // It doesn't particularly matter other then consistency with previous code.
769             let incomingEdgeIndexStart = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
770             let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
771             for (let incomingEdgeIndex = incomingEdgeIndexEnd - 1; incomingEdgeIndex >= incomingEdgeIndexStart; --incomingEdgeIndex) {
772                 let fromNodeOrdinal = this._incomingNodes[incomingEdgeIndex];
773                 let fromNodeIndex = fromNodeOrdinal * this._nodeFieldCount;
774                 let fromNodeIsInternal = this._nodes[fromNodeIndex + nodeFlagsOffset] & internalFlagsMask;
775                 if (fromNodeIsInternal)
776                     continue;
777
778                 let edgeIndex = this._incomingEdges[incomingEdgeIndex];
779                 currentPath.push({edge: edgeIndex});
780                 visitNode.call(this, fromNodeOrdinal);
781                 currentPath.pop();
782             }
783
784             currentPath.pop();
785         }
786
787         visitNode.call(this, targetNodeOrdinal);
788
789         return paths;
790     }
791 };
792
793 HeapSnapshotDiff = class HeapSnapshotDiff
794 {
795     constructor(objectId, snapshot1, snapshot2)
796     {
797         this._objectId = objectId;
798
799         this._snapshot1 = snapshot1;
800         this._snapshot2 = snapshot2;
801
802         this._totalSize = 0;
803         this._addedNodeIdentifiers = new Set;
804
805         let known = new Map;
806         for (let nodeIndex = 0; nodeIndex < this._snapshot1._nodes.length; nodeIndex += nodeFieldCount) {
807             let nodeIdentifier = this._snapshot1._nodes[nodeIndex + nodeIdOffset];
808             known.set(nodeIdentifier, nodeIndex);
809         }
810
811         for (let nodeIndex = 0; nodeIndex < this._snapshot2._nodes.length; nodeIndex += nodeFieldCount) {
812             let nodeIdentifier = this._snapshot2._nodes[nodeIndex + nodeIdOffset];
813             let existed = known.delete(nodeIdentifier);
814             if (!existed) {
815                 this._addedNodeIdentifiers.add(nodeIdentifier);
816                 this._totalSize += this._snapshot2._nodes[nodeIndex + nodeSizeOffset];
817             }
818         }
819
820         let {liveSize, categories} = HeapSnapshot.updateCategoriesAndMetadata(this._snapshot2, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier));
821         this._categories = categories;
822     }
823
824     // Worker Methods
825
826     allocationBucketCounts(bucketSizes)
827     {
828         return HeapSnapshot.allocationBucketCounts(this._snapshot2, bucketSizes, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier));
829     }
830
831     instancesWithClassName(className)
832     {
833         return HeapSnapshot.instancesWithClassName(this._snapshot2, className, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier));
834     }
835
836     update()
837     {
838         return HeapSnapshot.updateCategoriesAndMetadata(this._snapshot2, (nodeIdentifier) => this._addedNodeIdentifiers.has(nodeIdentifier));
839     }
840
841     nodeWithIdentifier(nodeIdentifier) { return this._snapshot2.nodeWithIdentifier(nodeIdentifier); }
842     shortestGCRootPath(nodeIdentifier) { return this._snapshot2.shortestGCRootPath(nodeIdentifier); }
843     dominatedNodes(nodeIdentifier) { return this._snapshot2.dominatedNodes(nodeIdentifier); }
844     retainedNodes(nodeIdentifier) { return this._snapshot2.retainedNodes(nodeIdentifier); }
845     retainers(nodeIdentifier) { return this._snapshot2.retainers(nodeIdentifier); }
846
847     // Public
848
849     serialize()
850     {
851         return {
852             snapshot1: this._snapshot1.serialize(),
853             snapshot2: this._snapshot2.serialize(),
854             totalSize: this._totalSize,
855             totalObjectCount: this._addedNodeIdentifiers.size,
856             categories: this._categories,
857         };
858     }
859 };