Web Inspector: reuse edge_count field of heap snapshot to store retained size
[WebKit-https.git] / Source / WebCore / inspector / front-end / HeapSnapshot.js
1 /*
2  * Copyright (C) 2011 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are
6  * met:
7  *
8  *     * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *     * Redistributions in binary form must reproduce the above
11  * copyright notice, this list of conditions and the following disclaimer
12  * in the documentation and/or other materials provided with the
13  * distribution.
14  *     * Neither the name of Google Inc. nor the names of its
15  * contributors may be used to endorse or promote products derived from
16  * this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31 /**
32  * @constructor
33  */
34 WebInspector.HeapSnapshotArraySlice = function(array, start, end)
35 {
36     this._array = array;
37     this._start = start;
38     this.length = end - start;
39 }
40
41 WebInspector.HeapSnapshotArraySlice.prototype = {
42     item: function(index)
43     {
44         return this._array[this._start + index];
45     },
46
47     slice: function(start, end)
48     {
49         if (typeof end === "undefined")
50             end = this.length;
51         return this._array.subarray(this._start + start, this._start + end);
52     }
53 }
54
55 /**
56  * @constructor
57  * @param {number=} edgeIndex
58  */
59 WebInspector.HeapSnapshotEdge = function(snapshot, edges, edgeIndex)
60 {
61     this._snapshot = snapshot;
62     this._edges = edges;
63     this.edgeIndex = edgeIndex || 0;
64 }
65
66 WebInspector.HeapSnapshotEdge.prototype = {
67     clone: function()
68     {
69         return new WebInspector.HeapSnapshotEdge(this._snapshot, this._edges, this.edgeIndex);
70     },
71
72     hasStringName: function()
73     {
74         if (!this.isShortcut())
75             return this._hasStringName();
76         return isNaN(parseInt(this._name(), 10));
77     },
78
79     isElement: function()
80     {
81         return this._type() === this._snapshot._edgeElementType;
82     },
83
84     isHidden: function()
85     {
86         return this._type() === this._snapshot._edgeHiddenType;
87     },
88
89     isWeak: function()
90     {
91         return this._type() === this._snapshot._edgeWeakType;
92     },
93
94     isInternal: function()
95     {
96         return this._type() === this._snapshot._edgeInternalType;
97     },
98
99     isInvisible: function()
100     {
101         return this._type() === this._snapshot._edgeInvisibleType;
102     },
103
104     isShortcut: function()
105     {
106         return this._type() === this._snapshot._edgeShortcutType;
107     },
108
109     name: function()
110     {
111         if (!this.isShortcut())
112             return this._name();
113         var numName = parseInt(this._name(), 10);
114         return isNaN(numName) ? this._name() : numName;
115     },
116
117     node: function()
118     {
119         return new WebInspector.HeapSnapshotNode(this._snapshot, this.nodeIndex());
120     },
121
122     nodeIndex: function()
123     {
124         return this._edges.item(this.edgeIndex + this._snapshot._edgeToNodeOffset);
125     },
126
127     rawEdges: function()
128     {
129         return this._edges;
130     },
131
132     toString: function()
133     {
134         var name = this.name();
135         switch (this.type()) {
136         case "context": return "->" + name;
137         case "element": return "[" + name + "]";
138         case "weak": return "[[" + name + "]]";
139         case "property":
140             return name.indexOf(" ") === -1 ? "." + name : "[\"" + name + "\"]";
141         case "shortcut":
142             if (typeof name === "string")
143                 return name.indexOf(" ") === -1 ? "." + name : "[\"" + name + "\"]";
144             else
145                 return "[" + name + "]";
146         case "internal":
147         case "hidden":
148         case "invisible":
149             return "{" + name + "}";
150         };
151         return "?" + name + "?";
152     },
153
154     type: function()
155     {
156         return this._snapshot._edgeTypes[this._type()];
157     },
158
159     _hasStringName: function()
160     {
161         return !this.isElement() && !this.isHidden() && !this.isWeak();
162     },
163
164     _name: function()
165     {
166         return this._hasStringName() ? this._snapshot._strings[this._nameOrIndex()] : this._nameOrIndex();
167     },
168
169     _nameOrIndex: function()
170     {
171         return this._edges.item(this.edgeIndex + this._snapshot._edgeNameOffset);
172     },
173
174     _type: function()
175     {
176         return this._edges.item(this.edgeIndex + this._snapshot._edgeTypeOffset);
177     }
178 };
179
180 /**
181  * @constructor
182  */
183 WebInspector.HeapSnapshotEdgeIterator = function(edge)
184 {
185     this.edge = edge;
186 }
187
188 WebInspector.HeapSnapshotEdgeIterator.prototype = {
189     first: function()
190     {
191         this.edge.edgeIndex = 0;
192     },
193
194     hasNext: function()
195     {
196         return this.edge.edgeIndex < this.edge._edges.length;
197     },
198
199     index: function()
200     {
201         return this.edge.edgeIndex;
202     },
203
204     setIndex: function(newIndex)
205     {
206         this.edge.edgeIndex = newIndex;
207     },
208
209     item: function()
210     {
211         return this.edge;
212     },
213
214     next: function()
215     {
216         this.edge.edgeIndex += this.edge._snapshot._edgeFieldsCount;
217     }
218 };
219
220 /**
221  * @constructor
222  */
223 WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainedNodeIndex, retainerIndex)
224 {
225     this._snapshot = snapshot;
226     this._retainedNodeIndex = retainedNodeIndex;
227
228     var retainedNodeOrdinal = retainedNodeIndex / snapshot._nodeFieldCount;
229     this._firstRetainer = snapshot._firstRetainerIndex[retainedNodeOrdinal];
230     this._retainersCount = snapshot._firstRetainerIndex[retainedNodeOrdinal + 1] - this._firstRetainer;
231
232     this.setRetainerIndex(retainerIndex);
233 }
234
235 WebInspector.HeapSnapshotRetainerEdge.prototype = {
236     clone: function()
237     {
238         return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainedNodeIndex, this.retainerIndex());
239     },
240
241     hasStringName: function()
242     {
243         return this._edge().hasStringName();
244     },
245
246     isElement: function()
247     {
248         return this._edge().isElement();
249     },
250
251     isHidden: function()
252     {
253         return this._edge().isHidden();
254     },
255
256     isInternal: function()
257     {
258         return this._edge().isInternal();
259     },
260
261     isInvisible: function()
262     {
263         return this._edge().isInvisible();
264     },
265
266     isShortcut: function()
267     {
268         return this._edge().isShortcut();
269     },
270
271     isWeak: function()
272     {
273         return this._edge().isWeak();
274     },
275
276     name: function()
277     {
278         return this._edge().name();
279     },
280
281     node: function()
282     {
283         return this._node();
284     },
285
286     nodeIndex: function()
287     {
288         return this._nodeIndex;
289     },
290
291     retainerIndex: function()
292     {
293         return this._retainerIndex;
294     },
295
296     setRetainerIndex: function(newIndex)
297     {
298         if (newIndex !== this._retainerIndex) {
299             this._retainerIndex = newIndex;
300             this.edgeIndex = newIndex;
301         }
302     },
303
304     set edgeIndex(edgeIndex)
305     {
306         var retainerIndex = this._firstRetainer + edgeIndex;
307         this._globalEdgeIndex = this._snapshot._retainingEdges[retainerIndex];
308         this._nodeIndex = this._snapshot._retainingNodes[retainerIndex];
309         delete this._edgeInstance;
310         delete this._nodeInstance;
311     },
312
313     _node: function()
314     {
315         if (!this._nodeInstance)
316             this._nodeInstance = new WebInspector.HeapSnapshotNode(this._snapshot, this._nodeIndex);
317         return this._nodeInstance;
318     },
319
320     _edge: function()
321     {
322         if (!this._edgeInstance) {
323             var edgeIndex = this._globalEdgeIndex - this._node()._edgeIndexesStart();
324             this._edgeInstance = new WebInspector.HeapSnapshotEdge(this._snapshot, this._node().rawEdges(), edgeIndex);
325         }
326         return this._edgeInstance;
327     },
328
329     toString: function()
330     {
331         return this._edge().toString();
332     },
333
334     type: function()
335     {
336         return this._edge().type();
337     }
338 }
339
340 /**
341  * @constructor
342  */
343 WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainer)
344 {
345     this.retainer = retainer;
346 }
347
348 WebInspector.HeapSnapshotRetainerEdgeIterator.prototype = {
349     first: function()
350     {
351         this.retainer.setRetainerIndex(0);
352     },
353
354     hasNext: function()
355     {
356         return this.retainer.retainerIndex() < this.retainer._retainersCount;
357     },
358
359     index: function()
360     {
361         return this.retainer.retainerIndex();
362     },
363
364     setIndex: function(newIndex)
365     {
366         this.retainer.setRetainerIndex(newIndex);
367     },
368
369     item: function()
370     {
371         return this.retainer;
372     },
373
374     next: function()
375     {
376         this.retainer.setRetainerIndex(this.retainer.retainerIndex() + 1);
377     }
378 };
379
380 /**
381  * @constructor
382  * @param {number=} nodeIndex
383  */
384 WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex)
385 {
386     this._snapshot = snapshot;
387     this._firstNodeIndex = nodeIndex;
388     this.nodeIndex = nodeIndex;
389 }
390
391 WebInspector.HeapSnapshotNode.prototype = {
392     canBeQueried: function()
393     {
394         var flags = this._snapshot._flagsOfNode(this);
395         return !!(flags & this._snapshot._nodeFlags.canBeQueried);
396     },
397
398     isPageObject: function()
399     {
400         var flags = this._snapshot._flagsOfNode(this);
401         return !!(flags & this._snapshot._nodeFlags.pageObject);
402     },
403
404     distanceToWindow: function()
405     {
406         return this._snapshot._distancesToWindow[this.nodeIndex / this._snapshot._nodeFieldCount];
407     },
408
409     className: function()
410     {
411         var type = this.type();
412         switch (type) {
413         case "hidden":
414             return WebInspector.UIString("(system)");
415         case "object":
416         case "native":
417             return this.name();
418         case "code":
419             return WebInspector.UIString("(compiled code)");
420         default:
421             return "(" + type + ")";
422         }
423     },
424
425     classIndex: function()
426     {
427         var snapshot = this._snapshot;
428         var nodes = snapshot._nodes;
429         var type = nodes[this.nodeIndex + snapshot._nodeTypeOffset];;
430         if (type === snapshot._nodeObjectType || type === snapshot._nodeNativeType)
431             return nodes[this.nodeIndex + snapshot._nodeNameOffset];
432         return -1 - type;
433     },
434
435     dominatorIndex: function()
436     {
437         var nodeFieldCount = this._snapshot._nodeFieldCount;
438         return this._snapshot._dominatorsTree[this.nodeIndex / this._snapshot._nodeFieldCount] * nodeFieldCount;
439     },
440
441     edges: function()
442     {
443         return new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(this._snapshot, this.rawEdges()));
444     },
445
446     edgesCount: function()
447     {
448         return (this._edgeIndexesEnd() - this._edgeIndexesStart()) / this._snapshot._edgeFieldsCount;
449     },
450
451     flags: function()
452     {
453         return this._snapshot._flagsOfNode(this);
454     },
455
456     id: function()
457     {
458         var snapshot = this._snapshot;
459         return snapshot._nodes[this.nodeIndex + snapshot._nodeIdOffset];
460     },
461
462     isHidden: function()
463     {
464         return this._type() === this._snapshot._nodeHiddenType;
465     },
466
467     isNative: function()
468     {
469         return this._type() === this._snapshot._nodeNativeType;
470     },
471
472     isSynthetic: function()
473     {
474         return this._type() === this._snapshot._nodeSyntheticType;
475     },
476
477     isWindow: function()
478     {
479         const windowRE = /^Window/;
480         return windowRE.test(this.name());
481     },
482
483     isDetachedDOMTreesRoot: function()
484     {
485         return this.name() === "(Detached DOM trees)";
486     },
487
488     isDetachedDOMTree: function()
489     {
490         const detachedDOMTreeRE = /^Detached DOM tree/;
491         return detachedDOMTreeRE.test(this.className());
492     },
493
494     isRoot: function()
495     {
496         return this.nodeIndex === this._snapshot._rootNodeIndex;
497     },
498
499     name: function()
500     {
501         return this._snapshot._strings[this._name()];
502     },
503
504     rawEdges: function()
505     {
506         return new WebInspector.HeapSnapshotArraySlice(this._snapshot._containmentEdges, this._edgeIndexesStart(), this._edgeIndexesEnd());
507     },
508
509     retainedSize: function()
510     {
511         var snapshot = this._snapshot;
512         return snapshot._nodes[this.nodeIndex + snapshot._nodeRetainedSizeOffset];
513     },
514
515     retainers: function()
516     {
517         return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this.nodeIndex, 0));
518     },
519
520     selfSize: function()
521     {
522         var snapshot = this._snapshot;
523         return snapshot._nodes[this.nodeIndex + snapshot._nodeSelfSizeOffset];
524     },
525
526     type: function()
527     {
528         return this._snapshot._nodeTypes[this._type()];
529     },
530
531     _name: function()
532     {
533         var snapshot = this._snapshot;
534         return snapshot._nodes[this.nodeIndex + snapshot._nodeNameOffset];
535     },
536
537     _edgeIndexesStart: function()
538     {
539         return this._snapshot._firstEdgeIndexes[this._ordinal()];
540     },
541
542     _edgeIndexesEnd: function()
543     {
544         return this._snapshot._firstEdgeIndexes[this._ordinal() + 1];
545     },
546
547     _ordinal: function()
548     {
549         return this.nodeIndex / this._snapshot._nodeFieldCount;
550     },
551
552     _nextNodeIndex: function()
553     {
554         return this.nodeIndex + this._snapshot._nodeFieldCount;
555     },
556
557     _type: function()
558     {
559         var snapshot = this._snapshot;
560         return snapshot._nodes[this.nodeIndex + snapshot._nodeTypeOffset];
561     }
562 };
563
564 /**
565  * @constructor
566  */
567 WebInspector.HeapSnapshotNodeIterator = function(node)
568 {
569     this.node = node;
570     this._nodesLength = node._snapshot._nodes.length;
571 }
572
573 WebInspector.HeapSnapshotNodeIterator.prototype = {
574     first: function()
575     {
576         this.node.nodeIndex = this.node._firstNodeIndex;
577     },
578
579     hasNext: function()
580     {
581         return this.node.nodeIndex < this._nodesLength;
582     },
583
584     index: function()
585     {
586         return this.node.nodeIndex;
587     },
588
589     setIndex: function(newIndex)
590     {
591         this.node.nodeIndex = newIndex;
592     },
593
594     item: function()
595     {
596         return this.node;
597     },
598
599     next: function()
600     {
601         this.node.nodeIndex = this.node._nextNodeIndex();
602     }
603 }
604
605 /**
606  * @constructor
607  */
608 WebInspector.HeapSnapshot = function(profile)
609 {
610     this.uid = profile.snapshot.uid;
611     this._nodes = profile.nodes;
612     this._containmentEdges = profile.edges;
613     /** @type{HeapSnapshotMetainfo} */
614     this._metaNode = profile.snapshot.meta;
615     this._strings = profile.strings;
616
617     this._snapshotDiffs = {};
618     this._aggregatesForDiff = null;
619
620     this._init();
621 }
622
623 /**
624  * @constructor
625  */
626 function HeapSnapshotMetainfo()
627 {
628     // New format.
629     this.node_fields = [];
630     this.node_types = [];
631     this.edge_fields = [];
632     this.edge_types = [];
633
634     // Old format.
635     this.fields = [];
636     this.types = [];
637 }
638
639 /**
640  * @constructor
641  */
642 function HeapSnapshotHeader()
643 {
644     // New format.
645     this.title = "";
646     this.uid = 0;
647     this.meta = new HeapSnapshotMetainfo();
648     this.node_count = 0;
649     this.edge_count = 0;
650 }
651
652 WebInspector.HeapSnapshot.prototype = {
653     _init: function()
654     {
655         var meta = this._metaNode;
656         this._rootNodeIndex = 0;
657
658         this._nodeTypeOffset = meta.node_fields.indexOf("type");
659         this._nodeNameOffset = meta.node_fields.indexOf("name");
660         this._nodeIdOffset = meta.node_fields.indexOf("id");
661         this._nodeSelfSizeOffset = meta.node_fields.indexOf("self_size");
662         this._nodeEdgeCountOffset = meta.node_fields.indexOf("edge_count");
663         this._nodeFieldCount = meta.node_fields.length;
664
665         this._nodeTypes = meta.node_types[this._nodeTypeOffset];
666         this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
667         this._nodeObjectType = this._nodeTypes.indexOf("object");
668         this._nodeNativeType = this._nodeTypes.indexOf("native");
669         this._nodeCodeType = this._nodeTypes.indexOf("code");
670         this._nodeSyntheticType = this._nodeTypes.indexOf("synthetic");
671
672         this._edgeFieldsCount = meta.edge_fields.length;
673         this._edgeTypeOffset = meta.edge_fields.indexOf("type");
674         this._edgeNameOffset = meta.edge_fields.indexOf("name_or_index");
675         this._edgeToNodeOffset = meta.edge_fields.indexOf("to_node");
676
677         this._edgeTypes = meta.edge_types[this._edgeTypeOffset];
678         this._edgeTypes.push("invisible");
679         this._edgeElementType = this._edgeTypes.indexOf("element");
680         this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
681         this._edgeInternalType = this._edgeTypes.indexOf("internal");
682         this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
683         this._edgeWeakType = this._edgeTypes.indexOf("weak");
684         this._edgeInvisibleType = this._edgeTypes.indexOf("invisible");
685
686         this._nodeFlags = { // bit flags
687             canBeQueried: 1,
688             detachedDOMTreeNode: 2,
689             pageObject: 4, // The idea is to track separately the objects owned by the page and the objects owned by debugger.
690
691             visitedMarkerMask: 0x0ffff, // bits: 0,1111,1111,1111,1111
692             visitedMarker:     0x10000  // bits: 1,0000,0000,0000,0000
693         };
694
695         this.nodeCount = this._nodes.length / this._nodeFieldCount;
696         this._edgeCount = this._containmentEdges.length / this._edgeFieldsCount;
697
698         this._buildEdgeIndexes();
699         this._markInvisibleEdges();
700         this._buildRetainers();
701         this._calculateFlags();
702         this._calculateObjectToWindowDistance();
703         var result = this._buildPostOrderIndex();
704         // Actually it is array that maps node ordinal number to dominator node ordinal number.
705         this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex);
706         this._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal);
707         this._buildDominatedNodes();
708     },
709
710     _buildEdgeIndexes: function()
711     {
712         // Support for old serialization.
713         if (this._nodeEdgeCountOffset === -1) {
714             var nodes = this._nodes;
715             var nodeCount = this.nodeCount;
716             var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1);
717             var nodeFieldCount = this._nodeFieldCount;
718             var nodeEdgesIndexOffset = this._metaNode.node_fields.indexOf("edges_index");
719             firstEdgeIndexes[nodeCount] = this._containmentEdges.length;
720             for (var nodeOrdinal = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) {
721                 firstEdgeIndexes[nodeOrdinal] = nodes[nodeOrdinal * nodeFieldCount + nodeEdgesIndexOffset];
722             }
723             return;
724         }
725
726         var nodes = this._nodes;
727         var nodeCount = this.nodeCount;
728         var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1);
729         var nodeFieldCount = this._nodeFieldCount;
730         var edgeFieldsCount = this._edgeFieldsCount;
731         var nodeEdgeCountOffset = this._nodeEdgeCountOffset;
732         firstEdgeIndexes[nodeCount] = this._containmentEdges.length;
733         for (var nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) {
734             firstEdgeIndexes[nodeOrdinal] = edgeIndex;
735             edgeIndex += nodes[nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset] * edgeFieldsCount;
736         }
737     },
738
739     _buildRetainers: function()
740     {
741         var retainingNodes = this._retainingNodes = new Uint32Array(this._edgeCount);
742         var retainingEdges = this._retainingEdges = new Uint32Array(this._edgeCount);
743         // Index of the first retainer in the _retainingNodes and _retainingEdges
744         // arrays. Addressed by retained node index.
745         var firstRetainerIndex = this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1);
746
747         var containmentEdges = this._containmentEdges;
748         var edgeFieldsCount = this._edgeFieldsCount;
749         var nodeFieldCount = this._nodeFieldCount;
750         var edgeToNodeOffset = this._edgeToNodeOffset;
751         var nodes = this._nodes;
752         var firstEdgeIndexes = this._firstEdgeIndexes;
753         var nodeCount = this.nodeCount;
754
755         for (var toNodeFieldIndex = edgeToNodeOffset, l = containmentEdges.length; toNodeFieldIndex < l; toNodeFieldIndex += edgeFieldsCount) {
756             var toNodeIndex = containmentEdges[toNodeFieldIndex];
757             if (toNodeIndex % nodeFieldCount)
758                 throw new Error("Invalid toNodeIndex " + toNodeIndex);
759             ++firstRetainerIndex[toNodeIndex / nodeFieldCount];
760         }
761         for (var i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) {
762             var retainersCount = firstRetainerIndex[i];
763             firstRetainerIndex[i] = firstUnusedRetainerSlot;
764             retainingNodes[firstUnusedRetainerSlot] = retainersCount;
765             firstUnusedRetainerSlot += retainersCount;
766         }
767         firstRetainerIndex[nodeCount] = retainingNodes.length;
768
769         var nextNodeFirstEdgeIndex = firstEdgeIndexes[0];
770         for (var srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) {
771             var firstEdgeIndex = nextNodeFirstEdgeIndex;
772             nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1];
773             var srcNodeIndex = srcNodeOrdinal * nodeFieldCount;
774             for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) {
775                 var toNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
776                 if (toNodeIndex % nodeFieldCount)
777                     throw new Error("Invalid toNodeIndex " + toNodeIndex);
778                 var firstRetainerSlotIndex = firstRetainerIndex[toNodeIndex / nodeFieldCount];
779                 var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]);
780                 retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex;
781                 retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex;
782             }
783         }
784     },
785
786     dispose: function()
787     {
788         delete this._nodes;
789         delete this._strings;
790         delete this._retainingEdges;
791         delete this._retainingNodes;
792         delete this._firstRetainerIndex;
793         if (this._aggregates) {
794             delete this._aggregates;
795             delete this._aggregatesSortedFlags;
796         }
797         delete this._dominatedNodes;
798         delete this._firstDominatedNodeIndex;
799         delete this._flags;
800         delete this._distancesToWindow;
801         delete this._dominatorsTree;
802     },
803
804     _allNodes: function()
805     {
806         return new WebInspector.HeapSnapshotNodeIterator(this.rootNode());
807     },
808
809     rootNode: function()
810     {
811         return new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex);
812     },
813
814     get rootNodeIndex()
815     {
816         return this._rootNodeIndex;
817     },
818
819     get totalSize()
820     {
821         return this.rootNode().retainedSize();
822     },
823
824     _getDominatedIndex: function(nodeIndex)
825     {
826         if (nodeIndex % this._nodeFieldCount)
827             throw new Error("Invalid nodeIndex: " + nodeIndex);
828         return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount];
829     },
830
831     _dominatedNodesOfNode: function(node)
832     {
833         var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex);
834         var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex());
835         return new WebInspector.HeapSnapshotArraySlice(this._dominatedNodes, dominatedIndexFrom, dominatedIndexTo);
836     },
837
838     _flagsOfNode: function(node)
839     {
840         return this._flags[node.nodeIndex / this._nodeFieldCount];
841     },
842
843     /**
844      * @param {boolean} sortedIndexes
845      * @param {string} key
846      * @param {string=} filterString
847      */
848     aggregates: function(sortedIndexes, key, filterString)
849     {
850         if (!this._aggregates) {
851             this._aggregates = {};
852             this._aggregatesSortedFlags = {};
853         }
854
855         var aggregatesByClassName = this._aggregates[key];
856         if (aggregatesByClassName) {
857             if (sortedIndexes && !this._aggregatesSortedFlags[key]) {
858                 this._sortAggregateIndexes(aggregatesByClassName);
859                 this._aggregatesSortedFlags[key] = sortedIndexes;
860             }
861             return aggregatesByClassName;
862         }
863
864         var filter;
865         if (filterString)
866             filter = this._parseFilter(filterString);
867
868         var aggregates = this._buildAggregates(filter);
869         this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter);
870         aggregatesByClassName = aggregates.aggregatesByClassName;
871
872         if (sortedIndexes)
873             this._sortAggregateIndexes(aggregatesByClassName);
874
875         this._aggregatesSortedFlags[key] = sortedIndexes;
876         this._aggregates[key] = aggregatesByClassName;
877
878         return aggregatesByClassName;
879     },
880
881     aggregatesForDiff: function()
882     {
883         if (this._aggregatesForDiff)
884             return this._aggregatesForDiff;
885
886         var aggregatesByClassName = this.aggregates(true, "allObjects");
887         this._aggregatesForDiff  = {};
888
889         var node = new WebInspector.HeapSnapshotNode(this);
890         for (var className in aggregatesByClassName) {
891             var aggregate = aggregatesByClassName[className];
892             var indexes = aggregate.idxs;
893             var ids = new Array(indexes.length);
894             var selfSizes = new Array(indexes.length);
895             for (var i = 0; i < indexes.length; i++) {
896                 node.nodeIndex = indexes[i];
897                 ids[i] = node.id();
898                 selfSizes[i] = node.selfSize();
899             }
900
901             this._aggregatesForDiff[className] = {
902                 indexes: indexes,
903                 ids: ids,
904                 selfSizes: selfSizes
905             };
906         }
907         return this._aggregatesForDiff;
908     },
909
910     _calculateObjectToWindowDistance: function()
911     {
912         var nodeFieldCount = this._nodeFieldCount;
913         var distances = new Uint32Array(this.nodeCount);
914
915         // bfs for Window roots
916         var nodesToVisit = new Uint32Array(this.nodeCount);
917         var nodesToVisitLength = 0;
918         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
919             var node = iter.edge.node();
920             if (node.isWindow()) {
921                 nodesToVisit[nodesToVisitLength++] = node.nodeIndex;
922                 distances[node.nodeIndex / nodeFieldCount] = 0;
923             }
924         }
925         this._bfs(nodesToVisit, nodesToVisitLength, distances);
926
927         // bfs for root
928         nodesToVisitLength = 0;
929         nodesToVisit[nodesToVisitLength++] = this._rootNodeIndex;
930         distances[this._rootNodeIndex / nodeFieldCount] = 0;
931         this._bfs(nodesToVisit, nodesToVisitLength, distances);
932         this._distancesToWindow = distances;
933     },
934
935     _bfs: function(nodesToVisit, nodesToVisitLength, distances)
936     {
937         // Peload fields into local variables for better performance.
938         var edgeFieldsCount = this._edgeFieldsCount;
939         var nodeFieldCount = this._nodeFieldCount;
940         var containmentEdges = this._containmentEdges;
941         var firstEdgeIndexes = this._firstEdgeIndexes;
942         var edgeToNodeOffset = this._edgeToNodeOffset;
943         var nodes = this._nodes;
944         var nodeCount = this.nodeCount;
945         var containmentEdgesLength = containmentEdges.length;
946
947         var index = 0;
948         while (index < nodesToVisitLength) {
949             var nodeIndex = nodesToVisit[index++]; // shift generates too much garbage.
950             var nodeOrdinal = nodeIndex / nodeFieldCount;
951             var distance = distances[nodeOrdinal] + 1;
952             var firstEdgeIndex = firstEdgeIndexes[nodeOrdinal];
953             var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1];
954             for (var edgeToNodeIndex = firstEdgeIndex + edgeToNodeOffset; edgeToNodeIndex < edgesEnd; edgeToNodeIndex += edgeFieldsCount) {
955                 var childNodeIndex = containmentEdges[edgeToNodeIndex];
956                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
957                 if (distances[childNodeOrdinal])
958                     continue;
959                 distances[childNodeOrdinal] = distance;
960                 nodesToVisit[nodesToVisitLength++] = childNodeIndex;
961             }
962         }
963         if (nodesToVisitLength > nodeCount)
964             throw new Error("BFS failed. Nodes to visit (" + nodesToVisitLength + ") is more than nodes count (" + nodeCount + ")");
965     },
966
967     _buildAggregates: function(filter)
968     {
969         var aggregates = {};
970         var aggregatesByClassName = {};
971         var classIndexes = [];
972         var nodes = this._nodes;
973         var flags = this._flags;
974         var nodesLength = nodes.length;
975         var nodeNativeType = this._nodeNativeType;
976         var nodeFieldCount = this._nodeFieldCount;
977         var selfSizeOffset = this._nodeSelfSizeOffset;
978         var nodeTypeOffset = this._nodeTypeOffset;
979         var pageObjectFlag = this._nodeFlags.pageObject;
980         var node = new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex);
981         var distancesToWindow = this._distancesToWindow;
982
983         for (var nodeIndex = this._rootNodeIndex; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
984             var nodeOrdinal = nodeIndex / nodeFieldCount;
985             if (!(flags[nodeOrdinal] & pageObjectFlag))
986                 continue;
987             node.nodeIndex = nodeIndex;
988             if (filter && !filter(node))
989                 continue;
990             var selfSize = nodes[nodeIndex + selfSizeOffset];
991             if (!selfSize && nodes[nodeIndex + nodeTypeOffset] !== nodeNativeType)
992                 continue;
993             var classIndex = node.classIndex();
994             if (!(classIndex in aggregates)) {
995                 var nodeType = node.type();
996                 var nameMatters = nodeType === "object" || nodeType === "native";
997                 var value = {
998                     count: 1,
999                     distanceToWindow: distancesToWindow[nodeOrdinal],
1000                     self: selfSize,
1001                     maxRet: 0,
1002                     type: nodeType,
1003                     name: nameMatters ? node.name() : null,
1004                     idxs: [nodeIndex]
1005                 };
1006                 aggregates[classIndex] = value;
1007                 classIndexes.push(classIndex);
1008                 aggregatesByClassName[node.className()] = value;
1009             } else {
1010                 var clss = aggregates[classIndex];
1011                 clss.distanceToWindow = Math.min(clss.distanceToWindow, distancesToWindow[nodeOrdinal]);
1012                 ++clss.count;
1013                 clss.self += selfSize;
1014                 clss.idxs.push(nodeIndex);
1015             }
1016         }
1017
1018         // Shave off provisionally allocated space.
1019         for (var i = 0, l = classIndexes.length; i < l; ++i) {
1020             var classIndex = classIndexes[i];
1021             aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice();
1022         }
1023         return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates};
1024     },
1025
1026     _calculateClassesRetainedSize: function(aggregates, filter)
1027     {
1028         var rootNodeIndex = this._rootNodeIndex;
1029         var node = new WebInspector.HeapSnapshotNode(this, rootNodeIndex);
1030         var list = [rootNodeIndex];
1031         var sizes = [-1];
1032         var classes = [];
1033         var seenClassNameIndexes = {};
1034         var nodeFieldCount = this._nodeFieldCount;
1035         var nodeTypeOffset = this._nodeTypeOffset;
1036         var nodeNativeType = this._nodeNativeType;
1037         var dominatedNodes = this._dominatedNodes;
1038         var nodes = this._nodes;
1039         var flags = this._flags;
1040         var pageObjectFlag = this._nodeFlags.pageObject;
1041         var firstDominatedNodeIndex = this._firstDominatedNodeIndex;
1042
1043         while (list.length) {
1044             var nodeIndex = list.pop();
1045             node.nodeIndex = nodeIndex;
1046             var classIndex = node.classIndex();
1047             var seen = !!seenClassNameIndexes[classIndex];
1048             var nodeOrdinal = nodeIndex / nodeFieldCount;
1049             var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal];
1050             var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1];
1051
1052             if (!seen &&
1053                 (flags[nodeOrdinal] & pageObjectFlag) &&
1054                 (!filter || filter(node)) &&
1055                 (node.selfSize() || nodes[nodeIndex + nodeTypeOffset] === nodeNativeType)
1056                ) {
1057                 aggregates[classIndex].maxRet += node.retainedSize();
1058                 if (dominatedIndexFrom !== dominatedIndexTo) {
1059                     seenClassNameIndexes[classIndex] = true;
1060                     sizes.push(list.length);
1061                     classes.push(classIndex);
1062                 }
1063             }
1064             for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++)
1065                 list.push(dominatedNodes[i]);
1066
1067             var l = list.length;
1068             while (sizes[sizes.length - 1] === l) {
1069                 sizes.pop();
1070                 classIndex = classes.pop();
1071                 seenClassNameIndexes[classIndex] = false;
1072             }
1073         }
1074     },
1075
1076     _sortAggregateIndexes: function(aggregates)
1077     {
1078         var nodeA = new WebInspector.HeapSnapshotNode(this);
1079         var nodeB = new WebInspector.HeapSnapshotNode(this);
1080         for (var clss in aggregates)
1081             aggregates[clss].idxs.sort(
1082                 function(idxA, idxB) {
1083                     nodeA.nodeIndex = idxA;
1084                     nodeB.nodeIndex = idxB;
1085                     return nodeA.id() < nodeB.id() ? -1 : 1;
1086                 });
1087     },
1088
1089     _buildPostOrderIndex: function()
1090     {
1091         var nodeFieldCount = this._nodeFieldCount;
1092         var nodes = this._nodes;
1093         var nodeCount = this.nodeCount;
1094         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1095
1096         var edgeFieldsCount = this._edgeFieldsCount;
1097         var edgeTypeOffset = this._edgeTypeOffset;
1098         var edgeToNodeOffset = this._edgeToNodeOffset;
1099         var edgeShortcutType = this._edgeShortcutType;
1100         var firstEdgeIndexes = this._firstEdgeIndexes;
1101         var containmentEdges = this._containmentEdges;
1102         var containmentEdgesLength = this._containmentEdges.length;
1103
1104         var flags = this._flags;
1105         var flag = this._nodeFlags.pageObject;
1106
1107         var nodesToVisit = new Uint32Array(nodeCount);
1108         var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount);
1109         var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount);
1110         var painted = new Uint8Array(nodeCount);
1111         var nodesToVisitLength = 0;
1112         var postOrderIndex = 0;
1113         var grey = 1;
1114         var black = 2;
1115
1116         nodesToVisit[nodesToVisitLength++] = rootNodeOrdinal;
1117         painted[rootNodeOrdinal] = grey;
1118
1119         while (nodesToVisitLength) {
1120             var nodeOrdinal = nodesToVisit[nodesToVisitLength - 1];
1121             if (painted[nodeOrdinal] === grey) {
1122                 painted[nodeOrdinal] = black;
1123                 var nodeFlag = flags[nodeOrdinal] & flag;
1124                 var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1125                 var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
1126                 for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
1127                     if (nodeOrdinal !== rootNodeOrdinal && containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType)
1128                         continue;
1129                     var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1130                     var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1131                     var childNodeFlag = flags[childNodeOrdinal] & flag;
1132                     // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1133                     // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1134                     if (nodeOrdinal !== rootNodeOrdinal && childNodeFlag && !nodeFlag)
1135                         continue;
1136                     if (!painted[childNodeOrdinal]) {
1137                         painted[childNodeOrdinal] = grey;
1138                         nodesToVisit[nodesToVisitLength++] = childNodeOrdinal;
1139                     }
1140                 }
1141             } else {
1142                 nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex;
1143                 postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal;
1144                 --nodesToVisitLength;
1145             }
1146         }
1147
1148         if (postOrderIndex !== nodeCount)
1149             throw new Error("Postordering failed. " + (nodeCount - postOrderIndex) + " hanging nodes");
1150
1151         return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
1152     },
1153
1154     // The algorithm is based on the article:
1155     // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
1156     // Softw. Pract. Exper. 4 (2001), pp. 1-10.
1157     /**
1158      * @param {Array.<number>} postOrderIndex2NodeOrdinal
1159      * @param {Array.<number>} nodeOrdinal2PostOrderIndex
1160      */
1161     _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex)
1162     {
1163         var nodeFieldCount = this._nodeFieldCount;
1164         var nodes = this._nodes;
1165         var firstRetainerIndex = this._firstRetainerIndex;
1166         var retainingNodes = this._retainingNodes;
1167         var retainingEdges = this._retainingEdges;
1168         var edgeFieldsCount = this._edgeFieldsCount;
1169         var edgeTypeOffset = this._edgeTypeOffset;
1170         var edgeToNodeOffset = this._edgeToNodeOffset;
1171         var edgeShortcutType = this._edgeShortcutType;
1172         var firstEdgeIndexes = this._firstEdgeIndexes;
1173         var containmentEdges = this._containmentEdges;
1174         var containmentEdgesLength = this._containmentEdges.length;
1175         var rootNodeIndex = this._rootNodeIndex;
1176
1177         var flags = this._flags;
1178         var flag = this._nodeFlags.pageObject;
1179
1180         var nodesCount = postOrderIndex2NodeOrdinal.length;
1181         var rootPostOrderedIndex = nodesCount - 1;
1182         var noEntry = nodesCount;
1183         var dominators = new Uint32Array(nodesCount);
1184         for (var i = 0; i < rootPostOrderedIndex; ++i)
1185             dominators[i] = noEntry;
1186         dominators[rootPostOrderedIndex] = rootPostOrderedIndex;
1187
1188         // The affected array is used to mark entries which dominators
1189         // have to be racalculated because of changes in their retainers.
1190         var affected = new Uint8Array(nodesCount);
1191
1192         { // Mark the root direct children as affected.
1193             var nodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1194             var beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1195             var endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1196             for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1197                  toNodeFieldIndex < endEdgeToNodeFieldIndex;
1198                  toNodeFieldIndex += edgeFieldsCount) {
1199                 var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1200                 affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1201             }
1202         }
1203
1204         var changed = true;
1205         while (changed) {
1206             changed = false;
1207             for (var postOrderIndex = rootPostOrderedIndex - 1; postOrderIndex >= 0; --postOrderIndex) {
1208                 if (affected[postOrderIndex] === 0)
1209                     continue;
1210                 affected[postOrderIndex] = 0;
1211                 // If dominator of the entry has already been set to root,
1212                 // then it can't propagate any further.
1213                 if (dominators[postOrderIndex] === rootPostOrderedIndex)
1214                     continue;
1215                 var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1216                 var nodeFlag = !!(flags[nodeOrdinal] & flag);
1217                 var newDominatorIndex = noEntry;
1218                 var beginRetainerIndex = firstRetainerIndex[nodeOrdinal];
1219                 var endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1];
1220                 for (var retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) {
1221                     var retainerEdgeIndex = retainingEdges[retainerIndex];
1222                     var retainerEdgeType = containmentEdges[retainerEdgeIndex + edgeTypeOffset];
1223                     var retainerNodeIndex = retainingNodes[retainerIndex];
1224                     if (retainerNodeIndex !== rootNodeIndex && retainerEdgeType === edgeShortcutType)
1225                         continue;
1226                     var retainerNodeOrdinal = retainerNodeIndex / nodeFieldCount;
1227                     var retainerNodeFlag = !!(flags[retainerNodeOrdinal] & flag);
1228                     // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1229                     // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1230                     if (retainerNodeIndex !== rootNodeIndex && nodeFlag && !retainerNodeFlag)
1231                         continue;
1232                     var retanerPostOrderIndex = nodeOrdinal2PostOrderIndex[retainerNodeOrdinal];
1233                     if (dominators[retanerPostOrderIndex] !== noEntry) {
1234                         if (newDominatorIndex === noEntry)
1235                             newDominatorIndex = retanerPostOrderIndex;
1236                         else {
1237                             while (retanerPostOrderIndex !== newDominatorIndex) {
1238                                 while (retanerPostOrderIndex < newDominatorIndex)
1239                                     retanerPostOrderIndex = dominators[retanerPostOrderIndex];
1240                                 while (newDominatorIndex < retanerPostOrderIndex)
1241                                     newDominatorIndex = dominators[newDominatorIndex];
1242                             }
1243                         }
1244                         // If idom has already reached the root, it doesn't make sense
1245                         // to check other retainers.
1246                         if (newDominatorIndex === rootPostOrderedIndex)
1247                             break;
1248                     }
1249                 }
1250                 if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
1251                     dominators[postOrderIndex] = newDominatorIndex;
1252                     changed = true;
1253                     nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1254                     beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1255                     endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1256                     for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1257                          toNodeFieldIndex < endEdgeToNodeFieldIndex;
1258                          toNodeFieldIndex += edgeFieldsCount) {
1259                         var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1260                         affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1261                     }
1262                 }
1263             }
1264         }
1265
1266         var dominatorsTree = new Uint32Array(nodesCount);
1267         for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) {
1268             var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1269             dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]];
1270         }
1271         return dominatorsTree;
1272     },
1273
1274     _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal)
1275     {
1276         var nodeCount = this.nodeCount;
1277         var nodes = this._nodes;
1278         var nodeSelfSizeOffset = this._nodeSelfSizeOffset;
1279         var nodeFieldCount = this._nodeFieldCount;
1280         var dominatorsTree = this._dominatorsTree;
1281         // Reuse now unused edge_count field to store retained size.
1282         var nodeRetainedSizeOffset = this._nodeRetainedSizeOffset = this._nodeEdgeCountOffset;
1283         delete this._nodeEdgeCountOffset;
1284
1285         for (var nodeIndex = 0, l = nodes.length; nodeIndex < l; nodeIndex += nodeFieldCount)
1286             nodes[nodeIndex + nodeRetainedSizeOffset] = nodes[nodeIndex + nodeSelfSizeOffset];
1287
1288         // Propagate retained sizes for each node excluding root.
1289         for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) {
1290             var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1291             var nodeIndex = nodeOrdinal * nodeFieldCount;
1292             var dominatorIndex = dominatorsTree[nodeOrdinal] * nodeFieldCount;
1293             nodes[dominatorIndex + nodeRetainedSizeOffset] += nodes[nodeIndex + nodeRetainedSizeOffset];
1294         }
1295     },
1296
1297     _buildDominatedNodes: function()
1298     {
1299         // Builds up two arrays:
1300         //  - "dominatedNodes" is a continuous array, where each node owns an
1301         //    interval (can be empty) with corresponding dominated nodes.
1302         //  - "indexArray" is an array of indexes in the "dominatedNodes"
1303         //    with the same positions as in the _nodeIndex.
1304         var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1);
1305         // All nodes except the root have dominators.
1306         var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1);
1307
1308         // Count the number of dominated nodes for each node. Skip the root (node at
1309         // index 0) as it is the only node that dominates itself.
1310         var nodeFieldCount = this._nodeFieldCount;
1311         var dominatorsTree = this._dominatorsTree;
1312         for (var nodeOrdinal = 1, l = this.nodeCount; nodeOrdinal < l; ++nodeOrdinal)
1313             ++indexArray[dominatorsTree[nodeOrdinal]];
1314         // Put in the first slot of each dominatedNodes slice the count of entries
1315         // that will be filled.
1316         var firstDominatedNodeIndex = 0;
1317         for (var i = 0, l = this.nodeCount; i < l; ++i) {
1318             var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i];
1319             indexArray[i] = firstDominatedNodeIndex;
1320             firstDominatedNodeIndex += dominatedCount;
1321         }
1322         indexArray[this.nodeCount] = dominatedNodes.length;
1323         // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at
1324         // index 0) as it is the only node that dominates itself.
1325         for (var nodeOrdinal = 1, l = this.nodeCount; nodeOrdinal < l; ++nodeOrdinal) {
1326             var dominatorOrdinal = dominatorsTree[nodeOrdinal];
1327             var dominatedRefIndex = indexArray[dominatorOrdinal];
1328             dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
1329             dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount;
1330         }
1331     },
1332
1333     _markInvisibleEdges: function()
1334     {
1335         // Mark hidden edges of global objects as invisible.
1336         // FIXME: This is a temporary measure. Normally, we should
1337         // really hide all hidden nodes.
1338         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
1339             var edge = iter.edge;
1340             if (!edge.isShortcut())
1341                 continue;
1342             var node = edge.node();
1343             var propNames = {};
1344             for (var innerIter = node.edges(); innerIter.hasNext(); innerIter.next()) {
1345                 var globalObjEdge = innerIter.edge;
1346                 if (globalObjEdge.isShortcut())
1347                     propNames[globalObjEdge._nameOrIndex()] = true;
1348             }
1349             for (innerIter.first(); innerIter.hasNext(); innerIter.next()) {
1350                 var globalObjEdge = innerIter.edge;
1351                 if (!globalObjEdge.isShortcut()
1352                     && globalObjEdge.node().isHidden()
1353                     && globalObjEdge._hasStringName()
1354                     && (globalObjEdge._nameOrIndex() in propNames))
1355                     this._containmentEdges[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
1356             }
1357         }
1358     },
1359
1360     _numbersComparator: function(a, b)
1361     {
1362         return a < b ? -1 : (a > b ? 1 : 0);
1363     },
1364
1365     _markDetachedDOMTreeNodes: function()
1366     {
1367         var flag = this._nodeFlags.detachedDOMTreeNode;
1368         var detachedDOMTreesRoot;
1369         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
1370             var node = iter.edge.node();
1371             if (node.isDetachedDOMTreesRoot()) {
1372                 detachedDOMTreesRoot = node;
1373                 break;
1374             }
1375         }
1376
1377         if (!detachedDOMTreesRoot)
1378             return;
1379
1380         for (var iter = detachedDOMTreesRoot.edges(); iter.hasNext(); iter.next()) {
1381             var node = iter.edge.node();
1382             if (node.isDetachedDOMTree()) {
1383                 for (var edgesIter = node.edges(); edgesIter.hasNext(); edgesIter.next())
1384                     this._flags[edgesIter.edge.node().nodeIndex / this._nodeFieldCount] |= flag;
1385             }
1386         }
1387     },
1388
1389     _markPageOwnedNodes: function()
1390     {
1391         var edgeShortcutType = this._edgeShortcutType;
1392         var edgeToNodeOffset = this._edgeToNodeOffset;
1393         var edgeTypeOffset = this._edgeTypeOffset;
1394         var edgeFieldsCount = this._edgeFieldsCount;
1395         var edgeWeakType = this._edgeWeakType;
1396         var firstEdgeIndexes = this._firstEdgeIndexes;
1397         var containmentEdges = this._containmentEdges;
1398         var containmentEdgesLength = containmentEdges.length;
1399         var nodes = this._nodes;
1400         var nodeFieldCount = this._nodeFieldCount;
1401         var nodesCount = this.nodeCount;
1402
1403         var flags = this._flags;
1404         var flag = this._nodeFlags.pageObject;
1405         var visitedMarker = this._nodeFlags.visitedMarker;
1406         var visitedMarkerMask = this._nodeFlags.visitedMarkerMask;
1407         var markerAndFlag = visitedMarker | flag;
1408
1409         var nodesToVisit = new Uint32Array(nodesCount);
1410         var nodesToVisitLength = 0;
1411
1412         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1413         for (var edgeIndex = firstEdgeIndexes[rootNodeOrdinal], endEdgeIndex = firstEdgeIndexes[rootNodeOrdinal + 1];
1414              edgeIndex < endEdgeIndex;
1415              edgeIndex += edgeFieldsCount) {
1416             if (containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType) {
1417                 var nodeOrdinal = containmentEdges[edgeIndex + edgeToNodeOffset] / nodeFieldCount;
1418                 nodesToVisit[nodesToVisitLength++] = nodeOrdinal;
1419                 flags[nodeOrdinal] |= visitedMarker;
1420             }
1421         }
1422
1423         while (nodesToVisitLength) {
1424             var nodeOrdinal = nodesToVisit[--nodesToVisitLength];
1425             flags[nodeOrdinal] |= flag;
1426             flags[nodeOrdinal] &= visitedMarkerMask;
1427             var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1428             var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
1429             for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
1430                 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1431                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1432                 if (flags[childNodeOrdinal] & markerAndFlag)
1433                     continue;
1434                 var type = containmentEdges[edgeIndex + edgeTypeOffset];
1435                 if (type === edgeWeakType)
1436                     continue;
1437                 nodesToVisit[nodesToVisitLength++] = childNodeOrdinal;
1438                 flags[childNodeOrdinal] |= visitedMarker;
1439             }
1440         }
1441     },
1442
1443     _markQueriableHeapObjects: function()
1444     {
1445         // Allow runtime properties query for objects accessible from Window objects
1446         // via regular properties, and for DOM wrappers. Trying to access random objects
1447         // can cause a crash due to insonsistent state of internal properties of wrappers.
1448         var flag = this._nodeFlags.canBeQueried;
1449         var hiddenEdgeType = this._edgeHiddenType;
1450         var internalEdgeType = this._edgeInternalType;
1451         var invisibleEdgeType = this._edgeInvisibleType;
1452         var edgeToNodeOffset = this._edgeToNodeOffset;
1453         var edgeTypeOffset = this._edgeTypeOffset;
1454         var edgeFieldsCount = this._edgeFieldsCount;
1455         var containmentEdges = this._containmentEdges;
1456         var nodes = this._nodes;
1457         var nodeCount = this.nodeCount;
1458         var nodeFieldCount = this._nodeFieldCount;
1459         var firstEdgeIndexes = this._firstEdgeIndexes;
1460
1461         var flags = this._flags;
1462         var list = [];
1463
1464         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
1465             if (iter.edge.node().isWindow())
1466                 list.push(iter.edge.node().nodeIndex / nodeFieldCount);
1467         }
1468
1469         while (list.length) {
1470             var nodeOrdinal = list.pop();
1471             if (flags[nodeOrdinal] & flag)
1472                 continue;
1473             flags[nodeOrdinal] |= flag;
1474             var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1475             var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
1476             for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
1477                 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1478                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1479                 if (flags[childNodeOrdinal] & flag)
1480                     continue;
1481                 var type = containmentEdges[edgeIndex + edgeTypeOffset];
1482                 if (type === hiddenEdgeType || type === invisibleEdgeType || type === internalEdgeType)
1483                     continue;
1484                 list.push(childNodeOrdinal);
1485             }
1486         }
1487     },
1488
1489     _calculateFlags: function()
1490     {
1491         this._flags = new Uint32Array(this.nodeCount);
1492         this._markDetachedDOMTreeNodes();
1493         this._markQueriableHeapObjects();
1494         this._markPageOwnedNodes();
1495     },
1496
1497     calculateSnapshotDiff: function(baseSnapshotId, baseSnapshotAggregates)
1498     {
1499         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1500         if (snapshotDiff)
1501             return snapshotDiff;
1502         snapshotDiff = {};
1503
1504         var aggregates = this.aggregates(true, "allObjects");
1505         for (var className in baseSnapshotAggregates) {
1506             var baseAggregate = baseSnapshotAggregates[className];
1507             var diff = this._calculateDiffForClass(baseAggregate, aggregates[className]);
1508             if (diff)
1509                 snapshotDiff[className] = diff;
1510         }
1511         var emptyBaseAggregate = { ids: [], indexes: [], selfSizes: [] };
1512         for (var className in aggregates) {
1513             if (className in baseSnapshotAggregates)
1514                 continue;
1515             snapshotDiff[className] = this._calculateDiffForClass(emptyBaseAggregate, aggregates[className]);
1516         }
1517
1518         this._snapshotDiffs[baseSnapshotId] = snapshotDiff;
1519         return snapshotDiff;
1520     },
1521
1522     _calculateDiffForClass: function(baseAggregate, aggregate)
1523     {
1524         var baseIds = baseAggregate.ids;
1525         var baseIndexes = baseAggregate.indexes;
1526         var baseSelfSizes = baseAggregate.selfSizes;
1527
1528         var indexes = aggregate ? aggregate.idxs : [];
1529
1530         var i = 0, l = baseIds.length;
1531         var j = 0, m = indexes.length;
1532         var diff = { addedCount: 0,
1533                      removedCount: 0,
1534                      addedSize: 0,
1535                      removedSize: 0,
1536                      deletedIndexes: [],
1537                      addedIndexes: [] };
1538
1539         var nodeB = new WebInspector.HeapSnapshotNode(this, indexes[j]);
1540         while (i < l && j < m) {
1541             var nodeAId = baseIds[i];
1542             if (nodeAId < nodeB.id()) {
1543                 diff.deletedIndexes.push(baseIndexes[i]);
1544                 diff.removedCount++;
1545                 diff.removedSize += baseSelfSizes[i];
1546                 ++i;
1547             } else if (nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot
1548                 diff.addedIndexes.push(indexes[j]);
1549                 diff.addedCount++;
1550                 diff.addedSize += nodeB.selfSize();
1551                 nodeB.nodeIndex = indexes[++j];
1552             } else { // nodeAId === nodeB.id()
1553                 ++i;
1554                 nodeB.nodeIndex = indexes[++j];
1555             }
1556         }
1557         while (i < l) {
1558             diff.deletedIndexes.push(baseIndexes[i]);
1559             diff.removedCount++;
1560             diff.removedSize += baseSelfSizes[i];
1561             ++i;
1562         }
1563         while (j < m) {
1564             diff.addedIndexes.push(indexes[j]);
1565             diff.addedCount++;
1566             diff.addedSize += nodeB.selfSize();
1567             nodeB.nodeIndex = indexes[++j];
1568         }
1569         diff.countDelta = diff.addedCount - diff.removedCount;
1570         diff.sizeDelta = diff.addedSize - diff.removedSize;
1571         if (!diff.addedCount && !diff.removedCount)
1572             return null;
1573         return diff;
1574     },
1575
1576     _nodeForSnapshotObjectId: function(snapshotObjectId)
1577     {
1578         for (var it = this._allNodes(); it.hasNext(); it.next()) {
1579             if (it.node.id() === snapshotObjectId)
1580                 return it.node;
1581         }
1582         return null;
1583     },
1584
1585     nodeClassName: function(snapshotObjectId)
1586     {
1587         var node = this._nodeForSnapshotObjectId(snapshotObjectId);
1588         if (node)
1589             return node.className();
1590         return null;
1591     },
1592
1593     dominatorIdsForNode: function(snapshotObjectId)
1594     {
1595         var node = this._nodeForSnapshotObjectId(snapshotObjectId);
1596         if (!node)
1597             return null;
1598         var result = [];
1599         while (!node.isRoot()) {
1600             result.push(node.id());
1601             node.nodeIndex = node.dominatorIndex();
1602         }
1603         return result;
1604     },
1605
1606     _parseFilter: function(filter)
1607     {
1608         if (!filter)
1609             return null;
1610         var parsedFilter = eval("(function(){return " + filter + "})()");
1611         return parsedFilter.bind(this);
1612     },
1613
1614     createEdgesProvider: function(nodeIndex, filter)
1615     {
1616         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1617         return new WebInspector.HeapSnapshotEdgesProvider(this, this._parseFilter(filter), node.edges());
1618     },
1619
1620     createRetainingEdgesProvider: function(nodeIndex, filter)
1621     {
1622         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1623         return new WebInspector.HeapSnapshotEdgesProvider(this, this._parseFilter(filter), node.retainers());
1624     },
1625
1626     createAddedNodesProvider: function(baseSnapshotId, className)
1627     {
1628         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1629         var diffForClass = snapshotDiff[className];
1630         return new WebInspector.HeapSnapshotNodesProvider(this, null, diffForClass.addedIndexes);
1631     },
1632
1633     createDeletedNodesProvider: function(nodeIndexes)
1634     {
1635         return new WebInspector.HeapSnapshotNodesProvider(this, null, nodeIndexes);
1636     },
1637
1638     createNodesProviderForClass: function(className, aggregatesKey)
1639     {
1640         function filter(node) {
1641             return node.isPageObject();
1642         }
1643         return new WebInspector.HeapSnapshotNodesProvider(this, filter, this.aggregates(false, aggregatesKey)[className].idxs);
1644     },
1645
1646     createNodesProviderForDominator: function(nodeIndex)
1647     {
1648         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1649         return new WebInspector.HeapSnapshotNodesProvider(this, null, this._dominatedNodesOfNode(node));
1650     },
1651
1652     updateStaticData: function()
1653     {
1654         return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid, nodeFlags: this._nodeFlags};
1655     }
1656 };
1657
1658 /**
1659  * @constructor
1660  * @param {Array.<number>=} unfilteredIterationOrder
1661  */
1662 WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder)
1663 {
1664     this._filter = filter;
1665     this._iterator = iterator;
1666     this._unfilteredIterationOrder = unfilteredIterationOrder;
1667     this._iterationOrder = null;
1668     this._position = 0;
1669     this._currentComparator = null;
1670     this._sortedPrefixLength = 0;
1671 }
1672
1673 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = {
1674     _createIterationOrder: function()
1675     {
1676         if (this._iterationOrder)
1677             return;
1678         if (this._unfilteredIterationOrder && !this._filter) {
1679             this._iterationOrder = this._unfilteredIterationOrder.slice(0);
1680             this._unfilteredIterationOrder = null;
1681             return;
1682         }
1683         this._iterationOrder = [];
1684         var iterator = this._iterator;
1685         if (!this._unfilteredIterationOrder && !this._filter) {
1686             for (iterator.first(); iterator.hasNext(); iterator.next())
1687                 this._iterationOrder.push(iterator.index());
1688         } else if (!this._unfilteredIterationOrder) {
1689             for (iterator.first(); iterator.hasNext(); iterator.next()) {
1690                 if (this._filter(iterator.item()))
1691                     this._iterationOrder.push(iterator.index());
1692             }
1693         } else {
1694             var order = this._unfilteredIterationOrder.constructor === Array ?
1695                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1696             for (var i = 0, l = order.length; i < l; ++i) {
1697                 iterator.setIndex(order[i]);
1698                 if (this._filter(iterator.item()))
1699                     this._iterationOrder.push(iterator.index());
1700             }
1701             this._unfilteredIterationOrder = null;
1702         }
1703     },
1704
1705     first: function()
1706     {
1707         this._position = 0;
1708     },
1709
1710     hasNext: function()
1711     {
1712         return this._position < this._iterationOrder.length;
1713     },
1714
1715     isEmpty: function()
1716     {
1717         if (this._iterationOrder)
1718             return !this._iterationOrder.length;
1719         if (this._unfilteredIterationOrder && !this._filter)
1720             return !this._unfilteredIterationOrder.length;
1721         var iterator = this._iterator;
1722         if (!this._unfilteredIterationOrder && !this._filter) {
1723             iterator.first();
1724             return !iterator.hasNext();
1725         } else if (!this._unfilteredIterationOrder) {
1726             for (iterator.first(); iterator.hasNext(); iterator.next())
1727                 if (this._filter(iterator.item()))
1728                     return false;
1729         } else {
1730             var order = this._unfilteredIterationOrder.constructor === Array ?
1731                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1732             for (var i = 0, l = order.length; i < l; ++i) {
1733                 iterator.setIndex(order[i]);
1734                 if (this._filter(iterator.item()))
1735                     return false;
1736             }
1737         }
1738         return true;
1739     },
1740
1741     item: function()
1742     {
1743         this._iterator.setIndex(this._iterationOrder[this._position]);
1744         return this._iterator.item();
1745     },
1746
1747     get length()
1748     {
1749         this._createIterationOrder();
1750         return this._iterationOrder.length;
1751     },
1752
1753     next: function()
1754     {
1755         ++this._position;
1756     },
1757
1758     /**
1759      * @param {number} begin
1760      * @param {number} end
1761      */
1762     serializeItemsRange: function(begin, end)
1763     {
1764         this._createIterationOrder();
1765         if (begin > end)
1766             throw new Error("Start position > end position: " + begin + " > " + end);
1767         if (end >= this._iterationOrder.length)
1768             end = this._iterationOrder.length;
1769         if (this._sortedPrefixLength < end) {
1770             this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, end - this._sortedPrefixLength);
1771             this._sortedPrefixLength = end;
1772         }
1773
1774         this._position = begin;
1775         var startPosition = this._position;
1776         var count = end - begin;
1777         var result = new Array(count);
1778         for (var i = 0 ; i < count && this.hasNext(); ++i, this.next())
1779             result[i] = this.serializeItem(this.item());
1780         result.length = i;
1781         result.totalLength = this._iterationOrder.length;
1782
1783         result.startPosition = startPosition;
1784         result.endPosition = this._position;
1785         return result;
1786     },
1787
1788     sortAll: function()
1789     {
1790         this._createIterationOrder();
1791         if (this._sortedPrefixLength === this._iterationOrder.length)
1792             return;
1793         this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, this._iterationOrder.length);
1794         this._sortedPrefixLength = this._iterationOrder.length;
1795     },
1796
1797     sortAndRewind: function(comparator)
1798     {
1799         this._currentComparator = comparator;
1800         this._sortedPrefixLength = 0;
1801         this.first();
1802     }
1803 }
1804
1805 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
1806 {
1807     return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
1808 }
1809
1810 /**
1811  * @constructor
1812  * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator}
1813  */
1814 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, filter, edgesIter)
1815 {
1816     this.snapshot = snapshot;
1817     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, edgesIter, filter);
1818 }
1819
1820 WebInspector.HeapSnapshotEdgesProvider.prototype = {
1821     serializeItem: function(edge)
1822     {
1823         return {
1824             name: edge.name(),
1825             propertyAccessor: edge.toString(),
1826             node: WebInspector.HeapSnapshotNodesProvider.prototype.serializeItem(edge.node()),
1827             nodeIndex: edge.nodeIndex(),
1828             type: edge.type(),
1829             distanceToWindow: edge.node().distanceToWindow()
1830         };
1831     },
1832
1833     sort: function(comparator, leftBound, rightBound, count)
1834     {
1835         var fieldName1 = comparator.fieldName1;
1836         var fieldName2 = comparator.fieldName2;
1837         var ascending1 = comparator.ascending1;
1838         var ascending2 = comparator.ascending2;
1839
1840         var edgeA = this._iterator.item().clone();
1841         var edgeB = edgeA.clone();
1842         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1843         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1844
1845         function compareEdgeFieldName(ascending, indexA, indexB)
1846         {
1847             edgeA.edgeIndex = indexA;
1848             edgeB.edgeIndex = indexB;
1849             if (edgeB.name() === "__proto__") return -1;
1850             if (edgeA.name() === "__proto__") return 1;
1851             var result =
1852                 edgeA.hasStringName() === edgeB.hasStringName() ?
1853                 (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) :
1854                 (edgeA.hasStringName() ? -1 : 1);
1855             return ascending ? result : -result;
1856         }
1857
1858         function compareNodeField(fieldName, ascending, indexA, indexB)
1859         {
1860             edgeA.edgeIndex = indexA;
1861             nodeA.nodeIndex = edgeA.nodeIndex();
1862             var valueA = nodeA[fieldName];
1863
1864             edgeB.edgeIndex = indexB;
1865             nodeB.nodeIndex = edgeB.nodeIndex();
1866             var valueB = nodeB[fieldName];
1867
1868             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1869             return ascending ? result : -result;
1870         }
1871
1872         function compareEdgeAndNode(indexA, indexB) {
1873             var result = compareEdgeFieldName(ascending1, indexA, indexB);
1874             if (result === 0)
1875                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
1876             return result;
1877         }
1878
1879         function compareNodeAndEdge(indexA, indexB) {
1880             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
1881             if (result === 0)
1882                 result = compareEdgeFieldName(ascending2, indexA, indexB);
1883             return result;
1884         }
1885
1886         function compareNodeAndNode(indexA, indexB) {
1887             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
1888             if (result === 0)
1889                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
1890             return result;
1891         }
1892
1893         if (fieldName1 === "!edgeName")
1894             this._iterationOrder.sortRange(compareEdgeAndNode, leftBound, rightBound, count);
1895         else if (fieldName2 === "!edgeName")
1896             this._iterationOrder.sortRange(compareNodeAndEdge, leftBound, rightBound, count);
1897         else
1898             this._iterationOrder.sortRange(compareNodeAndNode, leftBound, rightBound, count);
1899     }
1900 };
1901
1902 WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1903
1904 /**
1905  * @constructor
1906  * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator}
1907  * @param {Array.<number>=} nodeIndexes
1908  */
1909 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
1910 {
1911     this.snapshot = snapshot;
1912     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes(), filter, nodeIndexes);
1913 }
1914
1915 WebInspector.HeapSnapshotNodesProvider.prototype = {
1916     nodePosition: function(snapshotObjectId)
1917     {
1918         this._createIterationOrder();
1919         if (this.isEmpty())
1920             return -1;
1921         this.sortAll();
1922
1923         var node = new WebInspector.HeapSnapshotNode(this.snapshot);
1924         for (var i = 0; i < this._iterationOrder.length; i++) {
1925             node.nodeIndex = this._iterationOrder[i];
1926             if (node.id() === snapshotObjectId)
1927                 return i;
1928         }
1929         return -1;
1930     },
1931
1932     serializeItem: function(node)
1933     {
1934         return {
1935             id: node.id(),
1936             name: node.name(),
1937             distanceToWindow: node.distanceToWindow(),
1938             nodeIndex: node.nodeIndex,
1939             retainedSize: node.retainedSize(),
1940             selfSize: node.selfSize(),
1941             type: node.type(),
1942             flags: node.flags()
1943         };
1944     },
1945
1946     sort: function(comparator, leftBound, rightBound, count)
1947     {
1948         var fieldName1 = comparator.fieldName1;
1949         var fieldName2 = comparator.fieldName2;
1950         var ascending1 = comparator.ascending1;
1951         var ascending2 = comparator.ascending2;
1952
1953         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1954         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1955
1956         function sortByNodeField(fieldName, ascending)
1957         {
1958             var valueOrFunctionA = nodeA[fieldName];
1959             var valueA = typeof valueOrFunctionA !== "function" ? valueOrFunctionA : valueOrFunctionA.call(nodeA);
1960             var valueOrFunctionB = nodeB[fieldName];
1961             var valueB = typeof valueOrFunctionB !== "function" ? valueOrFunctionB : valueOrFunctionB.call(nodeB);
1962             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1963             return ascending ? result : -result;
1964         }
1965
1966         function sortByComparator(indexA, indexB) {
1967             nodeA.nodeIndex = indexA;
1968             nodeB.nodeIndex = indexB;
1969             var result = sortByNodeField(fieldName1, ascending1);
1970             if (result === 0)
1971                 result = sortByNodeField(fieldName2, ascending2);
1972             return result;
1973         }
1974
1975         this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count);
1976     }
1977 };
1978
1979 WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;