Web Inspector: get rid of artificial heap snapshot nodes from the retaining tree.
[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 WebInspector.HeapSnapshotLoader = function()
32 {
33     this._json = "";
34     this._state = "find-snapshot-info";
35     this._snapshot = {};
36 }
37
38 WebInspector.HeapSnapshotLoader.prototype = {
39     _findBalancedCurlyBrackets: function()
40     {
41         var counter = 0;
42         var openingBracket = "{".charCodeAt(0), closingBracket = "}".charCodeAt(0);
43         for (var i = 0, l = this._json.length; i < l; ++i) {
44             var character = this._json.charCodeAt(i);
45             if (character === openingBracket)
46                 ++counter;
47             else if (character === closingBracket) {
48                 if (--counter === 0)
49                     return i + 1;
50             }
51         }
52         return -1;
53     },
54
55     finishLoading: function()
56     {
57         if (!this._json)
58             return null;
59         this._parseStringsArray();
60         this._json = "";
61         var result = new WebInspector.HeapSnapshot(this._snapshot);
62         this._json = "";
63         this._snapshot = {};
64         return result;
65     },
66
67     _parseNodes: function()
68     {
69         var index = 0;
70         var char0 = "0".charCodeAt(0), char9 = "9".charCodeAt(0), closingBracket = "]".charCodeAt(0);
71         var length = this._json.length;
72         while (true) {
73             while (index < length) {
74                 var code = this._json.charCodeAt(index);
75                 if (char0 <= code && code <= char9)
76                     break;
77                 else if (code === closingBracket) {
78                     this._json = this._json.slice(index + 1);
79                     // Shave off provisionally allocated space.
80                     this._snapshot.nodes = this._snapshot.nodes.slice(0);
81                     return false;
82                 }
83                 ++index;
84             }
85             if (index === length) {
86                 this._json = "";
87                 return true;
88             }
89             var startIndex = index;
90             while (index < length) {
91                 var code = this._json.charCodeAt(index);
92                 if (char0 > code || code > char9)
93                     break;
94                 ++index;
95             }
96             if (index === length) {
97                 this._json = this._json.slice(startIndex);
98                 return true;
99             }
100             this._snapshot.nodes.push(parseInt(this._json.slice(startIndex, index)));
101         }
102     },
103
104     _parseStringsArray: function()
105     {
106         var closingBracketIndex = this._json.lastIndexOf("]");
107         if (closingBracketIndex === -1)
108             throw new Error("Incomplete JSON");
109         this._json = this._json.slice(0, closingBracketIndex + 1);
110         this._snapshot.strings = JSON.parse(this._json);
111     },
112
113     pushJSONChunk: function(chunk)
114     {
115         this._json += chunk;
116         switch (this._state) {
117         case "find-snapshot-info": {
118             var snapshotToken = "\"snapshot\"";
119             var snapshotTokenIndex = this._json.indexOf(snapshotToken);
120             if (snapshotTokenIndex === -1)
121                 throw new Error("Snapshot token not found");
122             this._json = this._json.slice(snapshotTokenIndex + snapshotToken.length + 1);
123             this._state = "parse-snapshot-info";
124             this.pushJSONChunk("");
125             break;
126         }
127         case "parse-snapshot-info": {
128             var closingBracketIndex = this._findBalancedCurlyBrackets();
129             if (closingBracketIndex === -1)
130                 return;
131             this._snapshot.snapshot = JSON.parse(this._json.slice(0, closingBracketIndex));
132             this._json = this._json.slice(closingBracketIndex);
133             this._state = "find-nodes";
134             this.pushJSONChunk("");
135             break;
136         }
137         case "find-nodes": {
138             var nodesToken = "\"nodes\"";
139             var nodesTokenIndex = this._json.indexOf(nodesToken);
140             if (nodesTokenIndex === -1)
141                 return;
142             var bracketIndex = this._json.indexOf("[", nodesTokenIndex);
143             if (bracketIndex === -1)
144                 return;
145             this._json = this._json.slice(bracketIndex + 1);
146             this._state = "parse-nodes-meta-info";
147             this.pushJSONChunk("");
148             break;
149         }
150         case "parse-nodes-meta-info": {
151             var closingBracketIndex = this._findBalancedCurlyBrackets();
152             if (closingBracketIndex === -1)
153                 return;
154             this._snapshot.nodes = [JSON.parse(this._json.slice(0, closingBracketIndex))];
155             this._json = this._json.slice(closingBracketIndex);
156             this._state = "parse-nodes";
157             this.pushJSONChunk("");
158             break;
159         }
160         case "parse-nodes": {
161             if (this._parseNodes())
162                 return;
163             this._state = "find-strings";
164             this.pushJSONChunk("");
165             break;
166         }
167         case "find-strings": {
168             var stringsToken = "\"strings\"";
169             var stringsTokenIndex = this._json.indexOf(stringsToken);
170             if (stringsTokenIndex === -1)
171                 return;
172             var bracketIndex = this._json.indexOf("[", stringsTokenIndex);
173             if (bracketIndex === -1)
174                 return;
175             this._json = this._json.slice(bracketIndex);
176             this._state = "accumulate-strings";
177             break;
178         }
179         case "accumulate-strings":
180             break;
181         }
182     }
183 };
184
185 WebInspector.HeapSnapshotArraySlice = function(snapshot, arrayName, start, end)
186 {
187     // Note: we don't reference snapshot contents directly to avoid
188     // holding references to big chunks of data.
189     this._snapshot = snapshot;
190     this._arrayName = arrayName;
191     this._start = start;
192     this.length = end - start;
193 }
194
195 WebInspector.HeapSnapshotArraySlice.prototype = {
196     item: function(index)
197     {
198         return this._snapshot[this._arrayName][this._start + index];
199     },
200
201     slice: function(start, end)
202     {
203         if (typeof end === "undefined")
204             end = start + this._start + this.length;
205         return this._snapshot[this._arrayName].slice(this._start + start, end);
206     }
207 }
208
209 WebInspector.HeapSnapshotEdge = function(snapshot, edges, edgeIndex)
210 {
211     this._snapshot = snapshot;
212     this._edges = edges;
213     this.edgeIndex = edgeIndex || 0;
214 }
215
216 WebInspector.HeapSnapshotEdge.prototype = {
217     clone: function()
218     {
219         return new WebInspector.HeapSnapshotEdge(this._snapshot, this._edges, this.edgeIndex);
220     },
221
222     get hasStringName()
223     {
224         if (!this.isShortcut)
225             return this._hasStringName;
226         return isNaN(parseInt(this._name, 10));
227     },
228
229     get isElement()
230     {
231         return this._type() === this._snapshot._edgeElementType;
232     },
233
234     get isHidden()
235     {
236         return this._type() === this._snapshot._edgeHiddenType;
237     },
238
239     get isWeak()
240     {
241         return this._type() === this._snapshot._edgeWeakType;
242     },
243
244     get isInternal()
245     {
246         return this._type() === this._snapshot._edgeInternalType;
247     },
248
249     get isInvisible()
250     {
251         return this._type() === this._snapshot._edgeInvisibleType;
252     },
253
254     get isShortcut()
255     {
256         return this._type() === this._snapshot._edgeShortcutType;
257     },
258
259     get name()
260     {
261         if (!this.isShortcut)
262             return this._name;
263         var numName = parseInt(this._name, 10);
264         return isNaN(numName) ? this._name : numName;
265     },
266
267     get node()
268     {
269         return new WebInspector.HeapSnapshotNode(this._snapshot, this.nodeIndex);
270     },
271
272     get nodeIndex()
273     {
274         return this._edges.item(this.edgeIndex + this._snapshot._edgeToNodeOffset);
275     },
276
277     get rawEdges()
278     {
279         return this._edges;
280     },
281
282     toString: function()
283     {
284         switch (this.type) {
285         case "context": return "->" + this.name;
286         case "element": return "[" + this.name + "]";
287         case "weak": return "[[" + this.name + "]]";
288         case "property":
289             return this.name.indexOf(" ") === -1 ? "." + this.name : "[\"" + this.name + "\"]";
290         case "shortcut":
291             var name = this.name;
292             if (typeof name === "string")
293                 return this.name.indexOf(" ") === -1 ? "." + this.name : "[\"" + this.name + "\"]";
294             else
295                 return "[" + this.name + "]";
296         case "internal":
297         case "hidden":
298         case "invisible":
299             return "{" + this.name + "}";
300         };
301         return "?" + this.name + "?";
302     },
303
304     get type()
305     {
306         return this._snapshot._edgeTypes[this._type()];
307     },
308
309     get _hasStringName()
310     {
311         return !this.isElement && !this.isHidden && !this.isWeak;
312     },
313
314     get _name()
315     {
316         return this._hasStringName ? this._snapshot._strings[this._nameOrIndex] : this._nameOrIndex;
317     },
318
319     get _nameOrIndex()
320     {
321         return this._edges.item(this.edgeIndex + this._snapshot._edgeNameOffset);
322     },
323
324     _type: function()
325     {
326         return this._edges.item(this.edgeIndex + this._snapshot._edgeTypeOffset);
327     }
328 };
329
330 WebInspector.HeapSnapshotEdgeIterator = function(edge)
331 {
332     this.edge = edge;
333 }
334
335 WebInspector.HeapSnapshotEdgeIterator.prototype = {
336     first: function()
337     {
338         this.edge.edgeIndex = 0;
339     },
340
341     hasNext: function()
342     {
343         return this.edge.edgeIndex < this.edge._edges.length;
344     },
345
346     get index()
347     {
348         return this.edge.edgeIndex;
349     },
350
351     set index(newIndex)
352     {
353         this.edge.edgeIndex = newIndex;
354     },
355
356     get item()
357     {
358         return this.edge;
359     },
360
361     next: function()
362     {
363         this.edge.edgeIndex += this.edge._snapshot._edgeFieldsCount;
364     }
365 };
366
367 WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainers, retainerIndex)
368 {
369     this._snapshot = snapshot;
370     this._retainers = retainers;
371     this.retainerIndex = retainerIndex || 0;
372 }
373
374 WebInspector.HeapSnapshotRetainerEdge.prototype = {
375     clone: function()
376     {
377         return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainers, this.retainerIndex);
378     },
379
380     get hasStringName()
381     {
382         return this._edge.hasStringName;
383     },
384
385     get isElement()
386     {
387         return this._edge.isElement;
388     },
389
390     get isHidden()
391     {
392         return this._edge.isHidden;
393     },
394
395     get isInternal()
396     {
397         return this._edge.isInternal;
398     },
399
400     get isInvisible()
401     {
402         return this._edge.isInvisible;
403     },
404
405     get isShortcut()
406     {
407         return this._edge.isShortcut;
408     },
409
410     get isWeak()
411     {
412         return this._edge.isWeak;
413     },
414
415     get name()
416     {
417         return this._edge.name;
418     },
419
420     get node()
421     {
422         return this._node;
423     },
424
425     get nodeIndex()
426     {
427         return this._nodeIndex;
428     },
429
430     get retainerIndex()
431     {
432         return this._retainerIndex;
433     },
434
435     set retainerIndex(newIndex)
436     {
437         if (newIndex !== this._retainerIndex) {
438             this._retainerIndex = newIndex;
439             this._setupEdge();
440         }
441     },
442
443     _setupEdge: function()
444     {
445         var globalEdgeIndex = this._retainers.item(this._retainerIndex);
446         this._nodeIndex = this._snapshot._findNearestNodeIndex(globalEdgeIndex);
447         this._node = new WebInspector.HeapSnapshotNode(this._snapshot, this._nodeIndex);
448         var edgeIndex = globalEdgeIndex - this._nodeIndex - this._snapshot._firstEdgeOffset;
449         this._edge = new WebInspector.HeapSnapshotEdge(this._snapshot, this._node.rawEdges, edgeIndex);
450     },
451
452     toString: function()
453     {
454         return this._edge.toString();
455     },
456
457     get type()
458     {
459         return this._edge.type;
460     }
461 }
462
463 WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainer)
464 {
465     this.retainer = retainer;
466 }
467
468 WebInspector.HeapSnapshotRetainerEdgeIterator.prototype = {
469     first: function()
470     {
471         this.retainer.retainerIndex = 0;
472     },
473
474     hasNext: function()
475     {
476         return this.retainer.retainerIndex < this.retainer._retainers.length;
477     },
478
479     get index()
480     {
481         return this.retainer.retainerIndex;
482     },
483
484     set index(newIndex)
485     {
486         this.retainer.retainerIndex = newIndex;
487     },
488
489     get item()
490     {
491         return this.retainer;
492     },
493
494     next: function()
495     {
496         ++this.retainer.retainerIndex;
497     }
498 };
499
500 WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex)
501 {
502     this._snapshot = snapshot;
503     this._firstNodeIndex = nodeIndex;
504     this.nodeIndex = nodeIndex;
505 }
506
507 WebInspector.HeapSnapshotNode.prototype = {
508     get canBeQueried()
509     {
510         var flags = this._snapshot._flagsOfNode(this);
511         return !!(flags & this._snapshot._nodeFlags.canBeQueried);
512     },
513
514     get className()
515     {
516         switch (this.type) {
517         case "hidden":
518             return WebInspector.UIString("(system)");
519         case "object": {
520             var commentPos = this.name.indexOf("/");
521             return commentPos !== -1 ? this.name.substring(0, commentPos).trimRight() : this.name;
522         }
523         case "native": {
524             var entitiesCountPos = this.name.indexOf("/");
525             return entitiesCountPos !== -1 ? this.name.substring(0, entitiesCountPos).trimRight() : this.name;
526         }
527         case "code":
528             return WebInspector.UIString("(compiled code)");
529         default:
530             return "(" + this.type + ")";
531         }
532     },
533
534     get dominatorIndex()
535     {
536         return this._nodes[this.nodeIndex + this._snapshot._dominatorOffset];
537     },
538
539     get edges()
540     {
541         return new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(this._snapshot, this.rawEdges));
542     },
543
544     get edgesCount()
545     {
546         return this._nodes[this.nodeIndex + this._snapshot._edgesCountOffset];
547     },
548
549     get flags()
550     {
551         return this._snapshot._flagsOfNode(this);
552     },
553
554     get id()
555     {
556         return this._nodes[this.nodeIndex + this._snapshot._nodeIdOffset];
557     },
558
559     get instancesCount()
560     {
561         return this._nodes[this.nodeIndex + this._snapshot._nodeInstancesCountOffset];
562     },
563
564     get isHidden()
565     {
566         return this._type() === this._snapshot._nodeHiddenType;
567     },
568
569     get isArtificial()
570     {
571         return this._type() === this._snapshot._nodeArtificialType;
572     },
573
574     get isDOMWindow()
575     {
576         return this.name.substr(0, 9) === "DOMWindow";
577     },
578
579     get isNativeRoot()
580     {
581         return this.name === "(Native objects)";
582     },
583
584     get isDetachedDOMTree()
585     {
586         return this.className === "Detached DOM tree";
587     },
588
589     get isRoot()
590     {
591         return this.nodeIndex === this._snapshot._rootNodeIndex;
592     },
593
594     get name()
595     {
596         return this._snapshot._strings[this._name()];
597     },
598
599     get rawEdges()
600     {
601         var firstEdgeIndex = this._firstEdgeIndex();
602         return new WebInspector.HeapSnapshotArraySlice(this._snapshot, "_nodes", firstEdgeIndex, firstEdgeIndex + this.edgesCount * this._snapshot._edgeFieldsCount);
603     },
604
605     get retainedSize()
606     {
607         return this._nodes[this.nodeIndex + this._snapshot._nodeRetainedSizeOffset];
608     },
609
610     get retainers()
611     {
612         return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._snapshot._retainersForNode(this)));
613     },
614
615     get selfSize()
616     {
617         return this._nodes[this.nodeIndex + this._snapshot._nodeSelfSizeOffset];
618     },
619
620     get type()
621     {
622         return this._snapshot._nodeTypes[this._type()];
623     },
624
625     _name: function()
626     {
627         return this._nodes[this.nodeIndex + this._snapshot._nodeNameOffset];
628     },
629
630     get _nodes()
631     {
632         return this._snapshot._nodes;
633     },
634
635     _firstEdgeIndex: function()
636     {
637         return this.nodeIndex + this._snapshot._firstEdgeOffset;
638     },
639
640     get _nextNodeIndex()
641     {
642         return this._firstEdgeIndex() + this.edgesCount * this._snapshot._edgeFieldsCount;
643     },
644
645     _type: function()
646     {
647         return this._nodes[this.nodeIndex + this._snapshot._nodeTypeOffset];
648     }
649 };
650
651 WebInspector.HeapSnapshotNodeIterator = function(node)
652 {
653     this.node = node;
654 }
655
656 WebInspector.HeapSnapshotNodeIterator.prototype = {
657     first: function()
658     {
659         this.node.nodeIndex = this.node._firstNodeIndex;
660     },
661
662     hasNext: function()
663     {
664         return this.node.nodeIndex < this.node._nodes.length;
665     },
666
667     get index()
668     {
669         return this.node.nodeIndex;
670     },
671
672     set index(newIndex)
673     {
674         this.node.nodeIndex = newIndex;
675     },
676
677     get item()
678     {
679         return this.node;
680     },
681
682     next: function()
683     {
684         this.node.nodeIndex = this.node._nextNodeIndex;
685     }
686 }
687
688 WebInspector.HeapSnapshot = function(profile)
689 {
690     this.uid = profile.snapshot.uid;
691     this._nodes = profile.nodes;
692     this._strings = profile.strings;
693
694     this._init();
695 }
696
697 WebInspector.HeapSnapshot.prototype = {
698     _init: function()
699     {
700         this._metaNodeIndex = 0;
701         this._rootNodeIndex = 1;
702         var meta = this._nodes[this._metaNodeIndex];
703         this._nodeTypeOffset = meta.fields.indexOf("type");
704         this._nodeNameOffset = meta.fields.indexOf("name");
705         this._nodeIdOffset = meta.fields.indexOf("id");
706         this._nodeInstancesCountOffset = this._nodeIdOffset;
707         this._nodeSelfSizeOffset = meta.fields.indexOf("self_size");
708         this._nodeRetainedSizeOffset = meta.fields.indexOf("retained_size");
709         this._dominatorOffset = meta.fields.indexOf("dominator");
710         this._edgesCountOffset = meta.fields.indexOf("children_count");
711         this._firstEdgeOffset = meta.fields.indexOf("children");
712         this._nodeTypes = meta.types[this._nodeTypeOffset];
713         this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
714         this._nodeArtificialType = this._nodeTypes.indexOf("artificial");
715         var edgesMeta = meta.types[this._firstEdgeOffset];
716         this._edgeFieldsCount = edgesMeta.fields.length;
717         this._edgeTypeOffset = edgesMeta.fields.indexOf("type");
718         this._edgeNameOffset = edgesMeta.fields.indexOf("name_or_index");
719         this._edgeToNodeOffset = edgesMeta.fields.indexOf("to_node");
720         this._edgeTypes = edgesMeta.types[this._edgeTypeOffset];
721         this._edgeElementType = this._edgeTypes.indexOf("element");
722         this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
723         this._edgeInternalType = this._edgeTypes.indexOf("internal");
724         this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
725         this._edgeWeakType = this._edgeTypes.indexOf("weak");
726         this._edgeInvisibleType = this._edgeTypes.length;
727         this._edgeTypes.push("invisible");
728
729         this._nodeFlags = { // bit flags
730             canBeQueried: 1,
731             detachedDOMTreeNode: 2,
732         };
733
734         this._markInvisibleEdges();
735     },
736
737     dispose: function()
738     {
739         delete this._nodes;
740         delete this._strings;
741         delete this._retainers;
742         delete this._retainerIndex;
743         delete this._nodeIndex;
744         if (this._aggregates) {
745             delete this._aggregates;
746             delete this._aggregatesSortedFlags;
747         }
748         delete this._baseNodeIds;
749         delete this._dominatedNodes;
750         delete this._dominatedIndex;
751         delete this._flags;
752     },
753
754     get _allNodes()
755     {
756         return new WebInspector.HeapSnapshotNodeIterator(this.rootNode);
757     },
758
759     get nodeCount()
760     {
761         if (this._nodeCount)
762             return this._nodeCount;
763
764         this._nodeCount = 0;
765         for (var iter = this._allNodes; iter.hasNext(); iter.next())
766             ++this._nodeCount;
767         return this._nodeCount;
768     },
769
770     nodeFieldValuesByIndex: function(fieldName, indexes)
771     {
772         var node = new WebInspector.HeapSnapshotNode(this);
773         var result = new Array(indexes.length);
774         for (var i = 0, l = indexes.length; i < l; ++i) {
775             node.nodeIndex = indexes[i];
776             result[i] = node[fieldName];
777         }
778         return result;
779     },
780
781     get rootNode()
782     {
783         return new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex);
784     },
785
786     get maxNodeId()
787     {
788         if (typeof this._maxNodeId === "number")
789             return this._maxNodeId;
790         this._maxNodeId = 0;
791         for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
792             var id = iter.node.id;
793             if ((id % 2) && id > this._maxNodeId)
794                 this._maxNodeId = id;
795         }
796         return this._maxNodeId;
797     },
798
799     get rootNodeIndex()
800     {
801         return this._rootNodeIndex;
802     },
803
804     get totalSize()
805     {
806         return this.rootNode.retainedSize;
807     },
808
809     _retainersForNode: function(node)
810     {
811         if (!this._retainers)
812             this._buildRetainers();
813
814         var retIndexFrom = this._getRetainerIndex(node.nodeIndex);
815         var retIndexTo = this._getRetainerIndex(node._nextNodeIndex);
816         return new WebInspector.HeapSnapshotArraySlice(this, "_retainers", retIndexFrom, retIndexTo);
817     },
818
819     _dominatedNodesOfNode: function(node)
820     {
821         if (!this._dominatedNodes)
822             this._buildDominatedNodes();
823
824         var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex);
825         var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex);
826         return new WebInspector.HeapSnapshotArraySlice(this, "_dominatedNodes", dominatedIndexFrom, dominatedIndexTo);
827     },
828
829     _flagsOfNode: function(node)
830     {
831         if (!this._flags)
832             this._calculateFlags();
833         return this._flags[node.nodeIndex];
834     },
835
836     aggregates: function(sortedIndexes, key, filterString)
837     {
838         if (!this._aggregates) {
839             this._aggregates = {};
840             this._aggregatesSortedFlags = {};
841         }
842
843         var aggregates = this._aggregates[key];
844         if (aggregates) {
845             if (sortedIndexes && !this._aggregatesSortedFlags[key]) {
846                 this._sortAggregateIndexes(aggregates);
847                 this._aggregatesSortedFlags[key] = sortedIndexes;
848             }
849             return aggregates;
850         }
851
852         var filter;
853         if (filterString)
854             filter = this._parseFilter(filterString);
855
856         aggregates = this._buildAggregates(filter);
857
858         if (sortedIndexes)
859             this._sortAggregateIndexes(aggregates);
860
861         this._aggregatesSortedFlags[key] = sortedIndexes;
862         this._aggregates[key] = aggregates;
863
864         return aggregates;
865     },
866
867     _buildReverseIndex: function(indexArrayName, backRefsArrayName, indexCallback, dataCallback)
868     {
869         if (!this._nodeIndex)
870             this._buildNodeIndex();
871
872         // Builds up two arrays:
873         //  - "backRefsArray" is a continuous array, where each node owns an
874         //    interval (can be empty) with corresponding back references.
875         //  - "indexArray" is an array of indexes in the "backRefsArray"
876         //    with the same positions as in the _nodeIndex.
877         var indexArray = this[indexArrayName] = new Array(this._nodeIndex.length);
878         for (var i = 0, l = indexArray.length; i < l; ++i)
879             indexArray[i] = 0;
880         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
881             indexCallback(nodesIter.node, function (position) { ++indexArray[position]; });
882         }
883         var backRefsCount = 0;
884         for (i = 0, l = indexArray.length; i < l; ++i)
885             backRefsCount += indexArray[i];
886         var backRefsArray = this[backRefsArrayName] = new Array(backRefsCount + 1);
887         // Put in the first slot of each backRefsArray slice the count of entries
888         // that will be filled.
889         var backRefsPosition = 0;
890         for (i = 0, l = indexArray.length; i < l; ++i) {
891             backRefsCount = backRefsArray[backRefsPosition] = indexArray[i];
892             indexArray[i] = backRefsPosition;
893             backRefsPosition += backRefsCount;
894         }
895         for (nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
896             dataCallback(nodesIter.node,
897                          function (backRefIndex) { return backRefIndex + (--backRefsArray[backRefIndex]); },
898                          function (backRefIndex, destIndex) { backRefsArray[backRefIndex] = destIndex; });
899         }
900     },
901
902     _buildRetainers: function()
903     {
904         this._buildReverseIndex(
905             "_retainerIndex",
906             "_retainers",
907             (function (node, callback)
908              {
909                  for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next())
910                      callback(this._findNodePositionInIndex(edgesIter.edge.nodeIndex));
911              }).bind(this),
912             (function (node, indexCallback, dataCallback)
913              {
914                  for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next()) {
915                      var edge = edgesIter.edge;
916                      var retIndex = this._getRetainerIndex(edge.nodeIndex);
917                      dataCallback(indexCallback(retIndex), node.nodeIndex + this._firstEdgeOffset + edge.edgeIndex);
918                  }
919              }).bind(this));
920     },
921
922     _buildAggregates: function(filter)
923     {
924         function shouldSkip(node)
925         {
926             if (filter && !filter(node))
927                 return true;
928             if (node.type !== "native" && node.selfSize === 0)
929                 return true;
930             var className = node.className;
931             if (className === "Document DOM tree")
932                 return true;
933             if (className === "Detached DOM tree")
934                 return true;
935             return false;
936         }
937
938         var aggregates = {};
939         for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
940             var node = iter.node;
941             if (shouldSkip(node))
942                 continue;
943             var className = node.className;
944             var nameMatters = node.type === "object" || node.type === "native";
945             if (!aggregates.hasOwnProperty(className))
946                 aggregates[className] = { count: 0, self: 0, maxRet: 0, type: node.type, name: nameMatters ? node.name : null, idxs: [] };
947             var clss = aggregates[className];
948             ++clss.count;
949             clss.self += node.selfSize;
950             clss.idxs.push(node.nodeIndex);
951         }
952
953         // Recursively visit dominators tree and sum up retained sizes
954         // of topmost objects in each class.
955         // This gives us retained sizes for classes.
956         var seenClasses = {};
957         var snapshot = this;
958         function forDominatedNodes(nodeIndex)
959         {
960             var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex);
961             var className = node.className;
962             var seen = !!seenClasses[className];
963             if (!seen && className in aggregates && !shouldSkip(node)) {
964                 aggregates[className].maxRet += node.retainedSize;
965                 seenClasses[className] = true;
966             }
967             var dominatedNodes = snapshot._dominatedNodesOfNode(node);
968             for (var i = 0; i < dominatedNodes.length; i++)
969                 forDominatedNodes(dominatedNodes.item(i));
970             seenClasses[className] = seen;
971         }
972         forDominatedNodes(this._rootNodeIndex);
973
974         // Shave off provisionally allocated space.
975         for (var className in aggregates)
976             aggregates[className].idxs = aggregates[className].idxs.slice(0);
977         return aggregates;
978     },
979
980     _sortAggregateIndexes: function(aggregates)
981     {
982         var nodeA = new WebInspector.HeapSnapshotNode(this);
983         var nodeB = new WebInspector.HeapSnapshotNode(this);
984         for (var clss in aggregates)
985             aggregates[clss].idxs.sort(
986                 function(idxA, idxB) {
987                     nodeA.nodeIndex = idxA;
988                     nodeB.nodeIndex = idxB;
989                     return nodeA.id < nodeB.id ? -1 : 1;
990                 });
991     },
992
993     _buildNodeIndex: function()
994     {
995         var count = this.nodeCount;
996         this._nodeIndex = new Array(count + 1);
997         count = 0;
998         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count)
999             this._nodeIndex[count] = nodesIter.index;
1000         this._nodeIndex[count] = this._nodes.length;
1001     },
1002
1003     _findNodePositionInIndex: function(index)
1004     {
1005         return binarySearch(index, this._nodeIndex, this._numbersComparator);
1006     },
1007
1008     _findNearestNodeIndex: function(index)
1009     {
1010         var result = this._findNodePositionInIndex(index);
1011         if (result < 0) {
1012             result = -result - 1;
1013             nodeIndex = this._nodeIndex[result];
1014             // Binary search can return either maximum lower value, or minimum higher value.
1015             if (nodeIndex > index)
1016                 nodeIndex = this._nodeIndex[result - 1];
1017         } else
1018             var nodeIndex = this._nodeIndex[result];
1019         return nodeIndex;
1020     },
1021
1022     _getRetainerIndex: function(nodeIndex)
1023     {
1024         var nodePosition = this._findNodePositionInIndex(nodeIndex);
1025         return this._retainerIndex[nodePosition];
1026     },
1027
1028     _buildDominatedNodes: function()
1029     {
1030         this._buildReverseIndex(
1031             "_dominatedIndex",
1032             "_dominatedNodes",
1033             (function (node, callback)
1034              {
1035                  var dominatorIndex = node.dominatorIndex;
1036                  if (dominatorIndex !== node.nodeIndex)
1037                      callback(this._findNodePositionInIndex(dominatorIndex));
1038              }).bind(this),
1039             (function (node, indexCallback, dataCallback)
1040              {
1041                  var dominatorIndex = node.dominatorIndex;
1042                  if (dominatorIndex !== node.nodeIndex) {
1043                      var dominatedIndex = this._getDominatedIndex(dominatorIndex);
1044                      dataCallback(indexCallback(dominatedIndex), node.nodeIndex);
1045                  }
1046              }).bind(this));
1047     },
1048
1049     _getDominatedIndex: function(nodeIndex)
1050     {
1051         var nodePosition = this._findNodePositionInIndex(nodeIndex);
1052         return this._dominatedIndex[nodePosition];
1053     },
1054
1055     _markInvisibleEdges: function()
1056     {
1057         // Mark hidden edges of global objects as invisible.
1058         // FIXME: This is a temporary measure. Normally, we should
1059         // really hide all hidden nodes.
1060         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1061             var edge = iter.edge;
1062             if (!edge.isShortcut)
1063                 continue;
1064             var node = edge.node;
1065             var propNames = {};
1066             for (var innerIter = node.edges; innerIter.hasNext(); innerIter.next()) {
1067                 var globalObjEdge = innerIter.edge;
1068                 if (globalObjEdge.isShortcut)
1069                     propNames[globalObjEdge._nameOrIndex] = true;
1070             }
1071             for (innerIter.first(); innerIter.hasNext(); innerIter.next()) {
1072                 var globalObjEdge = innerIter.edge;
1073                 if (!globalObjEdge.isShortcut
1074                     && globalObjEdge.node.isHidden
1075                     && globalObjEdge._hasStringName
1076                     && (globalObjEdge._nameOrIndex in propNames))
1077                     this._nodes[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
1078             }
1079         }
1080     },
1081
1082     _numbersComparator: function(a, b)
1083     {
1084         return a < b ? -1 : (a > b ? 1 : 0);
1085     },
1086
1087     _markDetachedDOMTreeNodes: function()
1088     {
1089         var flag = this._nodeFlags.detachedDOMTreeNode;
1090         var nativeRoot;
1091         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1092             var node = iter.edge.node;
1093             if (node.isNativeRoot) {
1094                 nativeRoot = node;
1095                 break;
1096             }
1097         }
1098
1099         if (!nativeRoot)
1100             return;
1101
1102         for (var iter = nativeRoot.edges; iter.hasNext(); iter.next()) {
1103             var node = iter.edge.node;
1104             if (node.isDetachedDOMTree) {
1105                 for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next())
1106                     this._flags[edgesIter.edge.node.nodeIndex] |= flag;
1107             }
1108         }
1109     },
1110
1111     _markQueriableHeapObjects: function()
1112     {
1113         // Allow runtime properties query for objects accessible from DOMWindow objects
1114         // via regular properties, and for DOM wrappers. Trying to access random objects
1115         // can cause a crash due to insonsistent state of internal properties of wrappers.
1116         var flag = this._nodeFlags.canBeQueried;
1117
1118         var list = [];
1119         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1120             if (iter.edge.node.isDOMWindow)
1121                 list.push(iter.edge.node);
1122         }
1123
1124         while (list.length) {
1125             var node = list.pop();
1126             if (this._flags[node.nodeIndex] & flag)
1127                 continue;
1128             this._flags[node.nodeIndex] |= flag;
1129             for (var iter = node.edges; iter.hasNext(); iter.next()) {
1130                 var edge = iter.edge;
1131                 var node = edge.node;
1132                 if (this._flags[node.nodeIndex])
1133                     continue;
1134                 if (edge.isHidden || edge.isInvisible)
1135                     continue;
1136                 var name = edge.name;
1137                 if (!name)
1138                     continue;
1139                 if (edge.isInternal && name !== "native")
1140                     continue;
1141                 list.push(node);
1142             }
1143         }
1144     },
1145
1146     _calculateFlags: function()
1147     {
1148         this._flags = new Array(this.nodeCount);
1149         this._markDetachedDOMTreeNodes();
1150         this._markQueriableHeapObjects();
1151     },
1152
1153     baseSnapshotHasNode: function(baseSnapshotId, className, nodeId)
1154     {
1155         return this._baseNodeIds[baseSnapshotId][className].binaryIndexOf(nodeId, this._numbersComparator) !== -1;
1156     },
1157
1158     pushBaseIds: function(baseSnapshotId, className, nodeIds)
1159     {
1160         if (!this._baseNodeIds)
1161             this._baseNodeIds = [];
1162         if (!this._baseNodeIds[baseSnapshotId])
1163             this._baseNodeIds[baseSnapshotId] = {};
1164         this._baseNodeIds[baseSnapshotId][className] = nodeIds;
1165     },
1166
1167     createDiff: function(className)
1168     {
1169         return new WebInspector.HeapSnapshotsDiff(this, className);
1170     },
1171
1172     _parseFilter: function(filter)
1173     {
1174         if (!filter)
1175             return null;
1176         var parsedFilter = eval("(function(){return " + filter + "})()");
1177         return parsedFilter.bind(this);
1178     },
1179
1180     createEdgesProvider: function(nodeIndex, filter)
1181     {
1182         return new WebInspector.HeapSnapshotEdgesProvider(this, nodeIndex, this._parseFilter(filter));
1183     },
1184
1185     createRetainingEdgesProvider: function(nodeIndex, filter)
1186     {
1187         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1188         return new WebInspector.HeapSnapshotEdgesProvider(this, nodeIndex, this._parseFilter(filter), node.retainers);
1189     },
1190
1191     createNodesProvider: function(filter)
1192     {
1193         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter));
1194     },
1195
1196     createNodesProviderForClass: function(className, aggregatesKey)
1197     {
1198         return new WebInspector.HeapSnapshotNodesProvider(this, null, this.aggregates(false, aggregatesKey)[className].idxs);
1199     },
1200
1201     createNodesProviderForDominator: function(nodeIndex, filter)
1202     {
1203         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1204         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter), this._dominatedNodesOfNode(node));
1205     },
1206
1207     createPathFinder: function(targetNodeIndex, skipHidden)
1208     {
1209         return new WebInspector.HeapSnapshotPathFinder(this, targetNodeIndex, skipHidden);
1210     },
1211
1212     updateStaticData: function()
1213     {
1214         return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid, nodeFlags: this._nodeFlags, maxNodeId: this.maxNodeId};
1215     }
1216 };
1217
1218 WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder)
1219 {
1220     this._filter = filter;
1221     this._iterator = iterator;
1222     this._unfilteredIterationOrder = unfilteredIterationOrder;
1223     this._iterationOrder = null;
1224     this._position = 0;
1225     this._currentComparator = null;
1226     this._lastComparator = null;
1227 }
1228
1229 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = {
1230     _createIterationOrder: function()
1231     {
1232         if (this._iterationOrder)
1233             return;
1234         if (this._unfilteredIterationOrder && !this._filter) {
1235             this._iterationOrder = this._unfilteredIterationOrder.slice(0);
1236             this._unfilteredIterationOrder = null;
1237             return;
1238         }
1239         this._iterationOrder = [];
1240         var iterator = this._iterator;
1241         if (!this._unfilteredIterationOrder && !this._filter) {
1242             for (iterator.first(); iterator.hasNext(); iterator.next())
1243                 this._iterationOrder.push(iterator.index);
1244         } else if (!this._unfilteredIterationOrder) {
1245             for (iterator.first(); iterator.hasNext(); iterator.next()) {
1246                 if (this._filter(iterator.item))
1247                     this._iterationOrder.push(iterator.index);
1248             }
1249         } else {
1250             var order = this._unfilteredIterationOrder.constructor === Array ?
1251                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1252             for (var i = 0, l = order.length; i < l; ++i) {
1253                 iterator.index = order[i];
1254                 if (this._filter(iterator.item))
1255                     this._iterationOrder.push(iterator.index);
1256             }
1257             this._unfilteredIterationOrder = null;
1258         }
1259     },
1260
1261     first: function()
1262     {
1263         this._position = 0;
1264     },
1265
1266     hasNext: function()
1267     {
1268         return this._position < this._iterationOrder.length;
1269     },
1270
1271     get isEmpty()
1272     {
1273         if (this._iterationOrder)
1274             return !this._iterationOrder.length;
1275         if (this._unfilteredIterationOrder && !this._filter)
1276             return !this._unfilteredIterationOrder.length;
1277         var iterator = this._iterator;
1278         if (!this._unfilteredIterationOrder && !this._filter) {
1279             iterator.first();
1280             return !iterator.hasNext();
1281         } else if (!this._unfilteredIterationOrder) {
1282             for (iterator.first(); iterator.hasNext(); iterator.next())
1283                 if (this._filter(iterator.item))
1284                     return false;
1285         } else {
1286             var order = this._unfilteredIterationOrder.constructor === Array ?
1287                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1288             for (var i = 0, l = order.length; i < l; ++i) {
1289                 iterator.index = order[i];
1290                 if (this._filter(iterator.item))
1291                     return false;
1292             }
1293         }
1294         return true;
1295     },
1296
1297     get item()
1298     {
1299         this._iterator.index = this._iterationOrder[this._position];
1300         return this._iterator.item;
1301     },
1302
1303     get length()
1304     {
1305         this._createIterationOrder();
1306         return this._iterationOrder.length;
1307     },
1308
1309     next: function()
1310     {
1311         ++this._position;
1312     },
1313
1314     serializeNextItems: function(count)
1315     {
1316         this._createIterationOrder();
1317         var result = new Array(count);
1318         if (this._lastComparator !== this._currentComparator)
1319             this.sort(this._currentComparator, this._position, this._iterationOrder.length - 1, count);
1320         for (var i = 0 ; i < count && this.hasNext(); ++i, this.next())
1321             result[i] = this._serialize(this.item);
1322         result.length = i;
1323         result.hasNext = this.hasNext();
1324         result.totalLength = this._iterationOrder.length;
1325         return result;
1326     },
1327
1328     sortAndRewind: function(comparator)
1329     {
1330         this._lastComparator = this._currentComparator;
1331         this._currentComparator = comparator;
1332         var result = this._lastComparator !== this._currentComparator;
1333         if (result)
1334             this.first();
1335         return result;
1336     }
1337 }
1338
1339 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
1340 {
1341     return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
1342 }
1343
1344 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, nodeIndex, filter, iter)
1345 {
1346     this.snapshot = snapshot;
1347     var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex);
1348     var edgesIter = iter || new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(snapshot, node.rawEdges));
1349     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, edgesIter, filter);
1350 }
1351
1352 WebInspector.HeapSnapshotEdgesProvider.prototype = {
1353     _serialize: function(edge)
1354     {
1355         return {name: edge.name, propertyAccessor: edge.toString(), node: WebInspector.HeapSnapshotNodesProvider.prototype._serialize(edge.node), nodeIndex: edge.nodeIndex, type: edge.type};
1356     },
1357
1358     sort: function(comparator, leftBound, rightBound, count)
1359     {
1360         var fieldName1 = comparator.fieldName1;
1361         var fieldName2 = comparator.fieldName2;
1362         var ascending1 = comparator.ascending1;
1363         var ascending2 = comparator.ascending2;
1364
1365         var edgeA = this._iterator.item.clone();
1366         var edgeB = edgeA.clone();
1367         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1368         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1369
1370         function sortByEdgeFieldName(ascending, indexA, indexB)
1371         {
1372             edgeA.edgeIndex = indexA;
1373             edgeB.edgeIndex = indexB;
1374             if (edgeB.name === "__proto__") return -1;
1375             if (edgeA.name === "__proto__") return 1;
1376             var result =
1377                 edgeA.hasStringName === edgeB.hasStringName ?
1378                 (edgeA.name < edgeB.name ? -1 : (edgeA.name > edgeB.name ? 1 : 0)) :
1379                 (edgeA.hasStringName ? -1 : 1);
1380             return ascending ? result : -result;
1381         }
1382
1383         function sortByNodeField(fieldName, ascending, indexA, indexB)
1384         {
1385             edgeA.edgeIndex = indexA;
1386             edgeB.edgeIndex = indexB;
1387             nodeA.nodeIndex = edgeA.nodeIndex;
1388             nodeB.nodeIndex = edgeB.nodeIndex;
1389             var valueA = nodeA[fieldName];
1390             var valueB = nodeB[fieldName];
1391             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1392             return ascending ? result : -result;
1393         }
1394
1395         function sortByEdgeAndNode(indexA, indexB) {
1396             var result = sortByEdgeFieldName(ascending1, indexA, indexB);
1397             if (result === 0)
1398                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1399             return result;
1400         }
1401
1402         function sortByNodeAndEdge(indexA, indexB) {
1403             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1404             if (result === 0)
1405                 result = sortByEdgeFieldName(ascending2, indexA, indexB);
1406             return result;
1407         }
1408
1409         function sortByNodeAndNode(indexA, indexB) {
1410             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1411             if (result === 0)
1412                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1413             return result;
1414         }
1415
1416         if (fieldName1 === "!edgeName")
1417             this._iterationOrder.sortRange(sortByEdgeAndNode, leftBound, rightBound, count);
1418         else if (fieldName2 === "!edgeName")
1419             this._iterationOrder.sortRange(sortByNodeAndEdge, leftBound, rightBound, count);
1420         else
1421             this._iterationOrder.sortRange(sortByNodeAndNode, leftBound, rightBound, count);
1422     }
1423 };
1424
1425 WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1426
1427 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
1428 {
1429     this.snapshot = snapshot;
1430     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes, filter, nodeIndexes);
1431 }
1432
1433 WebInspector.HeapSnapshotNodesProvider.prototype = {
1434     _serialize: function(node)
1435     {
1436         return {id: node.id, name: node.name, nodeIndex: node.nodeIndex, retainedSize: node.retainedSize, selfSize: node.selfSize, type: node.type, flags: node.flags};
1437     },
1438
1439     sort: function(comparator, leftBound, rightBound, count)
1440     {
1441         var fieldName1 = comparator.fieldName1;
1442         var fieldName2 = comparator.fieldName2;
1443         var ascending1 = comparator.ascending1;
1444         var ascending2 = comparator.ascending2;
1445
1446         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1447         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1448
1449         function sortByNodeField(fieldName, ascending, indexA, indexB)
1450         {
1451             nodeA.nodeIndex = indexA;
1452             nodeB.nodeIndex = indexB;
1453             var valueA = nodeA[fieldName];
1454             var valueB = nodeB[fieldName];
1455             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1456             return ascending ? result : -result;
1457         }
1458
1459         function sortByComparator(indexA, indexB) {
1460             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1461             if (result === 0)
1462                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1463             return result;
1464         }
1465
1466         this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count);
1467     }
1468 };
1469
1470 WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1471
1472 WebInspector.HeapSnapshotPathFinder = function(snapshot, targetNodeIndex, skipHidden)
1473 {
1474     this._snapshot = snapshot;
1475     this._maxLength = 1;
1476     this._lengthLimit = 15;
1477     this._targetNodeIndex = targetNodeIndex;
1478     this._currentPath = null;
1479     this._skipHidden = skipHidden;
1480     this._rootChildren = this._fillRootChildren();
1481 }
1482
1483 WebInspector.HeapSnapshotPathFinder.prototype = {
1484     findNext: function()
1485     {
1486         for (var i = 0; i < 100000; ++i) {
1487             if (!this._buildNextPath()) {
1488                 if (++this._maxLength >= this._lengthLimit)
1489                     return null;
1490                 this._currentPath = null;
1491                 if (!this._buildNextPath())
1492                     return null;
1493             }
1494             if (this._isPathFound())
1495                 return {path:this._pathToString(this._currentPath), route:this._pathToRoute(this._currentPath), len:this._currentPath.length};
1496         }
1497
1498         return false;
1499     },
1500
1501     updateRoots: function(filter)
1502     {
1503         if (filter)
1504             filter = eval("(function(){return " + filter + "})()");
1505         this._rootChildren = this._fillRootChildren(filter);
1506         this._reset();
1507     },
1508
1509     _reset: function()
1510     {
1511         this._maxLength = 1;
1512         this._currentPath = null;
1513     },
1514
1515     _fillRootChildren: function(filter)
1516     {
1517         var result = [];
1518         for (var iter = this._snapshot.rootNode.edges; iter.hasNext(); iter.next()) {
1519             if (!filter) {
1520                 if (!iter.edge.isShortcut)
1521                     result[iter.edge.nodeIndex] = true;
1522             } else if (filter(iter.edge.node)) {
1523                 result[iter.edge.nodeIndex] = true;
1524             }
1525         }
1526         return result;
1527     },
1528
1529     _appendToCurrentPath: function(iter)
1530     {
1531         this._currentPath._cache[this._lastEdge.nodeIndex] = true;
1532         this._currentPath.push(iter);
1533     },
1534
1535     _removeLastFromCurrentPath: function()
1536     {
1537         this._currentPath.pop();
1538         delete this._currentPath._cache[this._lastEdge.nodeIndex];
1539     },
1540
1541     _hasInPath: function(nodeIndex)
1542     {
1543         return this._targetNodeIndex === nodeIndex
1544             || !!this._currentPath._cache[nodeIndex];
1545     },
1546
1547     _isPathFound: function()
1548     {
1549         return this._currentPath.length === this._maxLength
1550             && this._lastEdge.nodeIndex in this._rootChildren;
1551     },
1552
1553     get _lastEdgeIter()
1554     {
1555         return this._currentPath[this._currentPath.length - 1];
1556     },
1557
1558     get _lastEdge()
1559     {
1560         return this._lastEdgeIter.item;
1561     },
1562
1563     _skipEdge: function(edge)
1564     {
1565         return edge.isInvisible
1566             || (this._skipHidden && (edge.isHidden || edge.node.isHidden))
1567             || edge.isWeak
1568             || this._hasInPath(edge.nodeIndex);
1569     },
1570
1571     _nextEdgeIter: function()
1572     {
1573         var iter = this._lastEdgeIter;
1574         while (iter.hasNext() && this._skipEdge(iter.item))
1575             iter.next();
1576         return iter;
1577     },
1578
1579     _buildNextPath: function()
1580     {
1581         if (this._currentPath !== null) {
1582             var iter = this._lastEdgeIter;
1583             while (true) {
1584                 iter.next();
1585                 iter = this._nextEdgeIter();
1586                 if (iter.hasNext())
1587                     return true;
1588                 while (true) {
1589                     if (this._currentPath.length > 1) {
1590                         this._removeLastFromCurrentPath();
1591                         iter = this._lastEdgeIter;
1592                         iter.next();
1593                         iter = this._nextEdgeIter();
1594                         if (iter.hasNext()) {
1595                             while (this._currentPath.length < this._maxLength) {
1596                                 iter = this._nextEdgeIter();
1597                                 if (iter.hasNext())
1598                                     this._appendToCurrentPath(iter.item.node.retainers);
1599                                 else
1600                                     return true;
1601                             }
1602                             return true;
1603                         }
1604                     } else
1605                         return false;
1606                 }
1607             }
1608         } else {
1609             var node = new WebInspector.HeapSnapshotNode(this._snapshot, this._targetNodeIndex);
1610             this._currentPath = [node.retainers];
1611             this._currentPath._cache = {};
1612             while (this._currentPath.length < this._maxLength) {
1613                 var iter = this._nextEdgeIter();
1614                 if (iter.hasNext())
1615                     this._appendToCurrentPath(iter.item.node.retainers);
1616                 else
1617                     break;
1618             }
1619             return true;
1620         }
1621     },
1622
1623     _nodeToString: function(node)
1624     {
1625         if (node.id === 1)
1626             return node.name;
1627         else
1628             return node.name + "@" + node.id;
1629     },
1630
1631     _pathToString: function(path)
1632     {
1633         if (!path)
1634             return "";
1635         var sPath = [];
1636         for (var j = 0; j < path.length; ++j)
1637             sPath.push(path[j].item.toString());
1638         sPath.push(this._nodeToString(path[path.length - 1].item.node));
1639         sPath.reverse();
1640         return sPath.join("");
1641     },
1642
1643     _pathToRoute: function(path)
1644     {
1645         if (!path)
1646            return [];
1647         var route = [];
1648         route.push(this._targetNodeIndex);
1649         for (var i = 0; i < path.length; ++i)
1650             route.push(path[i].item.nodeIndex);
1651         route.reverse();
1652         return route;
1653     }
1654 };
1655
1656 WebInspector.HeapSnapshotsDiff = function(snapshot, className)
1657 {
1658     this._snapshot = snapshot;
1659     this._className = className;
1660 };
1661
1662 WebInspector.HeapSnapshotsDiff.prototype = {
1663     calculate: function()
1664     {
1665         var aggregates = this._snapshot.aggregates(true)[this._className];
1666         var indexes = aggregates ? aggregates.idxs : [];
1667         var i = 0, l = this._baseIds.length;
1668         var j = 0, m = indexes.length;
1669         var diff = { addedCount: 0, removedCount: 0, addedSize: 0, removedSize: 0 };
1670
1671         var nodeB = new WebInspector.HeapSnapshotNode(this._snapshot, indexes[j]);
1672         while (i < l && j < m) {
1673             var nodeAId = this._baseIds[i];
1674             if (nodeAId < nodeB.id) {
1675                 diff.removedCount++;
1676                 diff.removedSize += this._baseSelfSizes[i];
1677                 ++i;
1678             } else if (nodeAId > nodeB.id) {
1679                 diff.addedCount++;
1680                 diff.addedSize += nodeB.selfSize;
1681                 nodeB.nodeIndex = indexes[++j];
1682             } else {
1683                 ++i;
1684                 nodeB.nodeIndex = indexes[++j];
1685             }
1686         }
1687         while (i < l) {
1688             diff.removedCount++;
1689             diff.removedSize += this._baseSelfSizes[i];
1690             ++i;
1691         }
1692         while (j < m) {
1693             diff.addedCount++;
1694             diff.addedSize += nodeB.selfSize;
1695             nodeB.nodeIndex = indexes[++j];
1696         }
1697         diff.countDelta = diff.addedCount - diff.removedCount;
1698         diff.sizeDelta = diff.addedSize - diff.removedSize;
1699         return diff;
1700     },
1701
1702     pushBaseIds: function(baseIds)
1703     {
1704         this._baseIds = baseIds;
1705     },
1706
1707     pushBaseSelfSizes: function(baseSelfSizes)
1708     {
1709         this._baseSelfSizes = baseSelfSizes;
1710     }
1711 };