[Chromium] Web Inspector: remove "Document DOM tree" class and "Detached DOM 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 isDOMWindow()
570     {
571         return this.name.substr(0, 9) === "DOMWindow";
572     },
573
574     get isRoot()
575     {
576         return this.nodeIndex === this._snapshot._rootNodeIndex;
577     },
578
579     get name()
580     {
581         return this._snapshot._strings[this._name()];
582     },
583
584     get rawEdges()
585     {
586         var firstEdgeIndex = this._firstEdgeIndex();
587         return new WebInspector.HeapSnapshotArraySlice(this._snapshot, "_nodes", firstEdgeIndex, firstEdgeIndex + this.edgesCount * this._snapshot._edgeFieldsCount);
588     },
589
590     get retainedSize()
591     {
592         return this._nodes[this.nodeIndex + this._snapshot._nodeRetainedSizeOffset];
593     },
594
595     get retainers()
596     {
597         return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._snapshot._retainersForNode(this)));
598     },
599
600     get selfSize()
601     {
602         return this._nodes[this.nodeIndex + this._snapshot._nodeSelfSizeOffset];
603     },
604
605     get type()
606     {
607         return this._snapshot._nodeTypes[this._type()];
608     },
609
610     _name: function()
611     {
612         return this._nodes[this.nodeIndex + this._snapshot._nodeNameOffset];
613     },
614
615     get _nodes()
616     {
617         return this._snapshot._nodes;
618     },
619
620     _firstEdgeIndex: function()
621     {
622         return this.nodeIndex + this._snapshot._firstEdgeOffset;
623     },
624
625     get _nextNodeIndex()
626     {
627         return this._firstEdgeIndex() + this.edgesCount * this._snapshot._edgeFieldsCount;
628     },
629
630     _type: function()
631     {
632         return this._nodes[this.nodeIndex + this._snapshot._nodeTypeOffset];
633     }
634 };
635
636 WebInspector.HeapSnapshotNodeIterator = function(node)
637 {
638     this.node = node;
639 }
640
641 WebInspector.HeapSnapshotNodeIterator.prototype = {
642     first: function()
643     {
644         this.node.nodeIndex = this.node._firstNodeIndex;
645     },
646
647     hasNext: function()
648     {
649         return this.node.nodeIndex < this.node._nodes.length;
650     },
651
652     get index()
653     {
654         return this.node.nodeIndex;
655     },
656
657     set index(newIndex)
658     {
659         this.node.nodeIndex = newIndex;
660     },
661
662     get item()
663     {
664         return this.node;
665     },
666
667     next: function()
668     {
669         this.node.nodeIndex = this.node._nextNodeIndex;
670     }
671 }
672
673 WebInspector.HeapSnapshot = function(profile)
674 {
675     this.uid = profile.snapshot.uid;
676     this._nodes = profile.nodes;
677     this._strings = profile.strings;
678
679     this._init();
680 }
681
682 WebInspector.HeapSnapshot.prototype = {
683     _init: function()
684     {
685         this._metaNodeIndex = 0;
686         this._rootNodeIndex = 1;
687         var meta = this._nodes[this._metaNodeIndex];
688         this._nodeTypeOffset = meta.fields.indexOf("type");
689         this._nodeNameOffset = meta.fields.indexOf("name");
690         this._nodeIdOffset = meta.fields.indexOf("id");
691         this._nodeInstancesCountOffset = this._nodeIdOffset;
692         this._nodeSelfSizeOffset = meta.fields.indexOf("self_size");
693         this._nodeRetainedSizeOffset = meta.fields.indexOf("retained_size");
694         this._dominatorOffset = meta.fields.indexOf("dominator");
695         this._edgesCountOffset = meta.fields.indexOf("children_count");
696         this._firstEdgeOffset = meta.fields.indexOf("children");
697         this._nodeTypes = meta.types[this._nodeTypeOffset];
698         this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
699         var edgesMeta = meta.types[this._firstEdgeOffset];
700         this._edgeFieldsCount = edgesMeta.fields.length;
701         this._edgeTypeOffset = edgesMeta.fields.indexOf("type");
702         this._edgeNameOffset = edgesMeta.fields.indexOf("name_or_index");
703         this._edgeToNodeOffset = edgesMeta.fields.indexOf("to_node");
704         this._edgeTypes = edgesMeta.types[this._edgeTypeOffset];
705         this._edgeElementType = this._edgeTypes.indexOf("element");
706         this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
707         this._edgeInternalType = this._edgeTypes.indexOf("internal");
708         this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
709         this._edgeWeakType = this._edgeTypes.indexOf("weak");
710         this._edgeInvisibleType = this._edgeTypes.length;
711         this._edgeTypes.push("invisible");
712
713         this._nodeFlags = { canBeQueried: 1 };
714
715         this._markInvisibleEdges();
716     },
717
718     dispose: function()
719     {
720         delete this._nodes;
721         delete this._strings;
722         delete this._retainers;
723         delete this._retainerIndex;
724         delete this._nodeIndex;
725         if (this._aggregates) {
726             delete this._aggregates;
727             delete this._aggregatesSortedFlags;
728         }
729         delete this._baseNodeIds;
730         delete this._dominatedNodes;
731         delete this._dominatedIndex;
732         delete this._flags;
733     },
734
735     get _allNodes()
736     {
737         return new WebInspector.HeapSnapshotNodeIterator(this.rootNode);
738     },
739
740     get nodeCount()
741     {
742         if (this._nodeCount)
743             return this._nodeCount;
744
745         this._nodeCount = 0;
746         for (var iter = this._allNodes; iter.hasNext(); iter.next())
747             ++this._nodeCount;
748         return this._nodeCount;
749     },
750
751     nodeFieldValuesByIndex: function(fieldName, indexes)
752     {
753         var node = new WebInspector.HeapSnapshotNode(this);
754         var result = new Array(indexes.length);
755         for (var i = 0, l = indexes.length; i < l; ++i) {
756             node.nodeIndex = indexes[i];
757             result[i] = node[fieldName];
758         }
759         return result;
760     },
761
762     get rootNode()
763     {
764         return new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex);
765     },
766
767     get maxNodeId()
768     {
769         if (typeof this._maxNodeId === "number")
770             return this._maxNodeId;
771         this._maxNodeId = 0;
772         for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
773             var id = iter.node.id;
774             if ((id % 2) && id > this._maxNodeId)
775                 this._maxNodeId = id;
776         }
777         return this._maxNodeId;
778     },
779
780     get rootNodeIndex()
781     {
782         return this._rootNodeIndex;
783     },
784
785     get totalSize()
786     {
787         return this.rootNode.retainedSize;
788     },
789
790     _retainersForNode: function(node)
791     {
792         if (!this._retainers)
793             this._buildRetainers();
794
795         var retIndexFrom = this._getRetainerIndex(node.nodeIndex);
796         var retIndexTo = this._getRetainerIndex(node._nextNodeIndex);
797         return new WebInspector.HeapSnapshotArraySlice(this, "_retainers", retIndexFrom, retIndexTo);
798     },
799
800     _dominatedNodesOfNode: function(node)
801     {
802         if (!this._dominatedNodes)
803             this._buildDominatedNodes();
804
805         var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex);
806         var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex);
807         return new WebInspector.HeapSnapshotArraySlice(this, "_dominatedNodes", dominatedIndexFrom, dominatedIndexTo);
808     },
809
810     _flagsOfNode: function(node)
811     {
812         if (!this._flags)
813             this._calculateFlags();
814         return this._flags[node.nodeIndex];
815     },
816
817     aggregates: function(sortedIndexes, key, filterString)
818     {
819         if (!this._aggregates) {
820             this._aggregates = {};
821             this._aggregatesSortedFlags = {};
822         }
823
824         var aggregates = this._aggregates[key];
825         if (aggregates) {
826             if (sortedIndexes && !this._aggregatesSortedFlags[key]) {
827                 this._sortAggregateIndexes(aggregates);
828                 this._aggregatesSortedFlags[key] = sortedIndexes;
829             }
830             return aggregates;
831         }
832
833         var filter;
834         if (filterString)
835             filter = this._parseFilter(filterString);
836
837         aggregates = this._buildAggregates(filter);
838
839         if (sortedIndexes)
840             this._sortAggregateIndexes(aggregates);
841
842         this._aggregatesSortedFlags[key] = sortedIndexes;
843         this._aggregates[key] = aggregates;
844
845         return aggregates;
846     },
847
848     _buildReverseIndex: function(indexArrayName, backRefsArrayName, indexCallback, dataCallback)
849     {
850         if (!this._nodeIndex)
851             this._buildNodeIndex();
852
853         // Builds up two arrays:
854         //  - "backRefsArray" is a continuous array, where each node owns an
855         //    interval (can be empty) with corresponding back references.
856         //  - "indexArray" is an array of indexes in the "backRefsArray"
857         //    with the same positions as in the _nodeIndex.
858         var indexArray = this[indexArrayName] = new Array(this._nodeIndex.length);
859         for (var i = 0, l = indexArray.length; i < l; ++i)
860             indexArray[i] = 0;
861         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
862             indexCallback(nodesIter.node, function (position) { ++indexArray[position]; });
863         }
864         var backRefsCount = 0;
865         for (i = 0, l = indexArray.length; i < l; ++i)
866             backRefsCount += indexArray[i];
867         var backRefsArray = this[backRefsArrayName] = new Array(backRefsCount + 1);
868         // Put in the first slot of each backRefsArray slice the count of entries
869         // that will be filled.
870         var backRefsPosition = 0;
871         for (i = 0, l = indexArray.length; i < l; ++i) {
872             backRefsCount = backRefsArray[backRefsPosition] = indexArray[i];
873             indexArray[i] = backRefsPosition;
874             backRefsPosition += backRefsCount;
875         }
876         for (nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
877             dataCallback(nodesIter.node,
878                          function (backRefIndex) { return backRefIndex + (--backRefsArray[backRefIndex]); },
879                          function (backRefIndex, destIndex) { backRefsArray[backRefIndex] = destIndex; });
880         }
881     },
882
883     _buildRetainers: function()
884     {
885         this._buildReverseIndex(
886             "_retainerIndex",
887             "_retainers",
888             (function (node, callback)
889              {
890                  for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next())
891                      callback(this._findNodePositionInIndex(edgesIter.edge.nodeIndex));
892              }).bind(this),
893             (function (node, indexCallback, dataCallback)
894              {
895                  for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next()) {
896                      var edge = edgesIter.edge;
897                      var retIndex = this._getRetainerIndex(edge.nodeIndex);
898                      dataCallback(indexCallback(retIndex), node.nodeIndex + this._firstEdgeOffset + edge.edgeIndex);
899                  }
900              }).bind(this));
901     },
902
903     _buildAggregates: function(filter)
904     {
905         var aggregates = {};
906         for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
907             var node = iter.node;
908             if (filter && !filter(node))
909                 continue;
910             if (node.type !== "native" && node.selfSize === 0)
911                 continue;
912             var className = node.className;
913             if (className === "Document DOM tree")
914                 continue;
915             if (className === "Detached DOM tree")
916                 continue;
917             var nameMatters = node.type === "object" || node.type === "native";
918             if (!aggregates.hasOwnProperty(className))
919                 aggregates[className] = { count: 0, self: 0, maxRet: 0, type: node.type, name: nameMatters ? node.name : null, idxs: [] };
920             var clss = aggregates[className];
921             ++clss.count;
922             clss.self += node.selfSize;
923             if (node.retainedSize > clss.maxRet)
924                 clss.maxRet = node.retainedSize;
925             clss.idxs.push(node.nodeIndex);
926         }
927         // Shave off provisionally allocated space.
928         for (var className in aggregates)
929             aggregates[className].idxs = aggregates[className].idxs.slice(0);
930         return aggregates;
931     },
932
933     _sortAggregateIndexes: function(aggregates)
934     {
935         var nodeA = new WebInspector.HeapSnapshotNode(this);
936         var nodeB = new WebInspector.HeapSnapshotNode(this);
937         for (var clss in aggregates)
938             aggregates[clss].idxs.sort(
939                 function(idxA, idxB) {
940                     nodeA.nodeIndex = idxA;
941                     nodeB.nodeIndex = idxB;
942                     return nodeA.id < nodeB.id ? -1 : 1;
943                 });
944     },
945
946     _buildNodeIndex: function()
947     {
948         var count = this.nodeCount;
949         this._nodeIndex = new Array(count + 1);
950         count = 0;
951         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count)
952             this._nodeIndex[count] = nodesIter.index;
953         this._nodeIndex[count] = this._nodes.length;
954     },
955
956     _findNodePositionInIndex: function(index)
957     {
958         return binarySearch(index, this._nodeIndex, this._numbersComparator);
959     },
960
961     _findNearestNodeIndex: function(index)
962     {
963         var result = this._findNodePositionInIndex(index);
964         if (result < 0) {
965             result = -result - 1;
966             nodeIndex = this._nodeIndex[result];
967             // Binary search can return either maximum lower value, or minimum higher value.
968             if (nodeIndex > index)
969                 nodeIndex = this._nodeIndex[result - 1];
970         } else
971             var nodeIndex = this._nodeIndex[result];
972         return nodeIndex;
973     },
974
975     _getRetainerIndex: function(nodeIndex)
976     {
977         var nodePosition = this._findNodePositionInIndex(nodeIndex);
978         return this._retainerIndex[nodePosition];
979     },
980
981     _buildDominatedNodes: function()
982     {
983         this._buildReverseIndex(
984             "_dominatedIndex",
985             "_dominatedNodes",
986             (function (node, callback)
987              {
988                  var dominatorIndex = node.dominatorIndex;
989                  if (dominatorIndex !== node.nodeIndex)
990                      callback(this._findNodePositionInIndex(dominatorIndex));
991              }).bind(this),
992             (function (node, indexCallback, dataCallback)
993              {
994                  var dominatorIndex = node.dominatorIndex;
995                  if (dominatorIndex !== node.nodeIndex) {
996                      var dominatedIndex = this._getDominatedIndex(dominatorIndex);
997                      dataCallback(indexCallback(dominatedIndex), node.nodeIndex);
998                  }
999              }).bind(this));
1000     },
1001
1002     _getDominatedIndex: function(nodeIndex)
1003     {
1004         var nodePosition = this._findNodePositionInIndex(nodeIndex);
1005         return this._dominatedIndex[nodePosition];
1006     },
1007
1008     _markInvisibleEdges: function()
1009     {
1010         // Mark hidden edges of global objects as invisible.
1011         // FIXME: This is a temporary measure. Normally, we should
1012         // really hide all hidden nodes.
1013         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1014             var edge = iter.edge;
1015             if (!edge.isShortcut)
1016                 continue;
1017             var node = edge.node;
1018             var propNames = {};
1019             for (var innerIter = node.edges; innerIter.hasNext(); innerIter.next()) {
1020                 var globalObjEdge = innerIter.edge;
1021                 if (globalObjEdge.isShortcut)
1022                     propNames[globalObjEdge._nameOrIndex] = true;
1023             }
1024             for (innerIter.first(); innerIter.hasNext(); innerIter.next()) {
1025                 var globalObjEdge = innerIter.edge;
1026                 if (!globalObjEdge.isShortcut
1027                     && globalObjEdge.node.isHidden
1028                     && globalObjEdge._hasStringName
1029                     && (globalObjEdge._nameOrIndex in propNames))
1030                     this._nodes[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
1031             }
1032         }
1033     },
1034
1035     _numbersComparator: function(a, b)
1036     {
1037         return a < b ? -1 : (a > b ? 1 : 0);
1038     },
1039
1040     _calculateFlags: function()
1041     {
1042         var flag = this._nodeFlags.canBeQueried;
1043         this._flags = new Array(this.nodeCount);
1044         // Allow runtime properties query for objects accessible from DOMWindow objects
1045         // via regular properties, and for DOM wrappers. Trying to access random objects
1046         // can cause a crash due to insonsistent state of internal properties of wrappers.
1047         var list = [];
1048         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1049             if (iter.edge.node.isDOMWindow)
1050                 list.push(iter.edge.node);
1051         }
1052
1053         while (list.length) {
1054             var node = list.pop();
1055             if (this._flags[node.nodeIndex])
1056                 continue;
1057             this._flags[node.nodeIndex] = flag;
1058             for (var iter = node.edges; iter.hasNext(); iter.next()) {
1059                 var edge = iter.edge;
1060                 var node = edge.node;
1061                 if (this._flags[node.nodeIndex])
1062                     continue;
1063                 if (edge.isHidden || edge.isInvisible)
1064                     continue;
1065                 var name = edge.name;
1066                 if (!name)
1067                     continue;
1068                 if (edge.isInternal && name !== "native")
1069                     continue;
1070                 list.push(node);
1071             }
1072         }
1073     },
1074
1075     baseSnapshotHasNode: function(baseSnapshotId, className, nodeId)
1076     {
1077         return this._baseNodeIds[baseSnapshotId][className].binaryIndexOf(nodeId, this._numbersComparator) !== -1;
1078     },
1079
1080     pushBaseIds: function(baseSnapshotId, className, nodeIds)
1081     {
1082         if (!this._baseNodeIds)
1083             this._baseNodeIds = [];
1084         if (!this._baseNodeIds[baseSnapshotId])
1085             this._baseNodeIds[baseSnapshotId] = {};
1086         this._baseNodeIds[baseSnapshotId][className] = nodeIds;
1087     },
1088
1089     createDiff: function(className)
1090     {
1091         return new WebInspector.HeapSnapshotsDiff(this, className);
1092     },
1093
1094     _parseFilter: function(filter)
1095     {
1096         if (!filter)
1097             return null;
1098         var parsedFilter = eval("(function(){return " + filter + "})()");
1099         return parsedFilter.bind(this);
1100     },
1101
1102     createEdgesProvider: function(nodeIndex, filter)
1103     {
1104         return new WebInspector.HeapSnapshotEdgesProvider(this, nodeIndex, this._parseFilter(filter));
1105     },
1106
1107     createNodesProvider: function(filter)
1108     {
1109         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter));
1110     },
1111
1112     createNodesProviderForClass: function(className, aggregatesKey)
1113     {
1114         return new WebInspector.HeapSnapshotNodesProvider(this, null, this.aggregates(false, aggregatesKey)[className].idxs);
1115     },
1116
1117     createNodesProviderForDominator: function(nodeIndex, filter)
1118     {
1119         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1120         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter), this._dominatedNodesOfNode(node));
1121     },
1122
1123     createPathFinder: function(targetNodeIndex, skipHidden)
1124     {
1125         return new WebInspector.HeapSnapshotPathFinder(this, targetNodeIndex, skipHidden);
1126     },
1127
1128     updateStaticData: function()
1129     {
1130         return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid, nodeFlags: this._nodeFlags, maxNodeId: this.maxNodeId};
1131     }
1132 };
1133
1134 WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder)
1135 {
1136     this._filter = filter;
1137     this._iterator = iterator;
1138     this._unfilteredIterationOrder = unfilteredIterationOrder;
1139     this._iterationOrder = null;
1140     this._position = 0;
1141     this._currentComparator = null;
1142     this._lastComparator = null;
1143 }
1144
1145 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = {
1146     _createIterationOrder: function()
1147     {
1148         if (this._iterationOrder)
1149             return;
1150         if (this._unfilteredIterationOrder && !this._filter) {
1151             this._iterationOrder = this._unfilteredIterationOrder.slice(0);
1152             this._unfilteredIterationOrder = null;
1153             return;
1154         }
1155         this._iterationOrder = [];
1156         var iterator = this._iterator;
1157         if (!this._unfilteredIterationOrder && !this._filter) {
1158             for (iterator.first(); iterator.hasNext(); iterator.next())
1159                 this._iterationOrder.push(iterator.index);
1160         } else if (!this._unfilteredIterationOrder) {
1161             for (iterator.first(); iterator.hasNext(); iterator.next()) {
1162                 if (this._filter(iterator.item))
1163                     this._iterationOrder.push(iterator.index);
1164             }
1165         } else {
1166             var order = this._unfilteredIterationOrder.constructor === Array ?
1167                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1168             for (var i = 0, l = order.length; i < l; ++i) {
1169                 iterator.index = order[i];
1170                 if (this._filter(iterator.item))
1171                     this._iterationOrder.push(iterator.index);
1172             }
1173             this._unfilteredIterationOrder = null;
1174         }
1175     },
1176
1177     first: function()
1178     {
1179         this._position = 0;
1180     },
1181
1182     hasNext: function()
1183     {
1184         return this._position < this._iterationOrder.length;
1185     },
1186
1187     get isEmpty()
1188     {
1189         if (this._iterationOrder)
1190             return !this._iterationOrder.length;
1191         if (this._unfilteredIterationOrder && !this._filter)
1192             return !this._unfilteredIterationOrder.length;
1193         var iterator = this._iterator;
1194         if (!this._unfilteredIterationOrder && !this._filter) {
1195             iterator.first();
1196             return !iterator.hasNext();
1197         } else if (!this._unfilteredIterationOrder) {
1198             for (iterator.first(); iterator.hasNext(); iterator.next())
1199                 if (this._filter(iterator.item))
1200                     return false;
1201         } else {
1202             var order = this._unfilteredIterationOrder.constructor === Array ?
1203                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1204             for (var i = 0, l = order.length; i < l; ++i) {
1205                 iterator.index = order[i];
1206                 if (this._filter(iterator.item))
1207                     return false;
1208             }
1209         }
1210         return true;
1211     },
1212
1213     get item()
1214     {
1215         this._iterator.index = this._iterationOrder[this._position];
1216         return this._iterator.item;
1217     },
1218
1219     get length()
1220     {
1221         this._createIterationOrder();
1222         return this._iterationOrder.length;
1223     },
1224
1225     next: function()
1226     {
1227         ++this._position;
1228     },
1229
1230     serializeNextItems: function(count)
1231     {
1232         this._createIterationOrder();
1233         var result = new Array(count);
1234         if (this._lastComparator !== this._currentComparator)
1235             this.sort(this._currentComparator, this._position, this._iterationOrder.length - 1, count);
1236         for (var i = 0 ; i < count && this.hasNext(); ++i, this.next())
1237             result[i] = this._serialize(this.item);
1238         result.length = i;
1239         result.hasNext = this.hasNext();
1240         result.totalLength = this._iterationOrder.length;
1241         return result;
1242     },
1243
1244     sortAndRewind: function(comparator)
1245     {
1246         this._lastComparator = this._currentComparator;
1247         this._currentComparator = comparator;
1248         var result = this._lastComparator !== this._currentComparator;
1249         if (result)
1250             this.first();
1251         return result;
1252     }
1253 }
1254
1255 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
1256 {
1257     return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
1258 }
1259
1260 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, nodeIndex, filter)
1261 {
1262     this.snapshot = snapshot;
1263     var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex);
1264     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(snapshot, node.rawEdges)), filter);
1265 }
1266
1267 WebInspector.HeapSnapshotEdgesProvider.prototype = {
1268     _serialize: function(edge)
1269     {
1270         return {name: edge.name, node: WebInspector.HeapSnapshotNodesProvider.prototype._serialize(edge.node), nodeIndex: edge.nodeIndex, type: edge.type};
1271     },
1272
1273     sort: function(comparator, leftBound, rightBound, count)
1274     {
1275         var fieldName1 = comparator.fieldName1;
1276         var fieldName2 = comparator.fieldName2;
1277         var ascending1 = comparator.ascending1;
1278         var ascending2 = comparator.ascending2;
1279
1280         var edgeA = this._iterator.item.clone();
1281         var edgeB = edgeA.clone();
1282         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1283         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1284
1285         function sortByEdgeFieldName(ascending, indexA, indexB)
1286         {
1287             edgeA.edgeIndex = indexA;
1288             edgeB.edgeIndex = indexB;
1289             if (edgeB.name === "__proto__") return -1;
1290             if (edgeA.name === "__proto__") return 1;
1291             var result =
1292                 edgeA.hasStringName === edgeB.hasStringName ?
1293                 (edgeA.name < edgeB.name ? -1 : (edgeA.name > edgeB.name ? 1 : 0)) :
1294                 (edgeA.hasStringName ? -1 : 1);
1295             return ascending ? result : -result;
1296         }
1297
1298         function sortByNodeField(fieldName, ascending, indexA, indexB)
1299         {
1300             edgeA.edgeIndex = indexA;
1301             edgeB.edgeIndex = indexB;
1302             nodeA.nodeIndex = edgeA.nodeIndex;
1303             nodeB.nodeIndex = edgeB.nodeIndex;
1304             var valueA = nodeA[fieldName];
1305             var valueB = nodeB[fieldName];
1306             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1307             return ascending ? result : -result;
1308         }
1309
1310         function sortByEdgeAndNode(indexA, indexB) {
1311             var result = sortByEdgeFieldName(ascending1, indexA, indexB);
1312             if (result === 0)
1313                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1314             return result;
1315         }
1316
1317         function sortByNodeAndEdge(indexA, indexB) {
1318             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1319             if (result === 0)
1320                 result = sortByEdgeFieldName(ascending2, indexA, indexB);
1321             return result;
1322         }
1323
1324         function sortByNodeAndNode(indexA, indexB) {
1325             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1326             if (result === 0)
1327                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1328             return result;
1329         }
1330
1331         if (fieldName1 === "!edgeName")
1332             this._iterationOrder.sortRange(sortByEdgeAndNode, leftBound, rightBound, count);
1333         else if (fieldName2 === "!edgeName")
1334             this._iterationOrder.sortRange(sortByNodeAndEdge, leftBound, rightBound, count);
1335         else
1336             this._iterationOrder.sortRange(sortByNodeAndNode, leftBound, rightBound, count);
1337     }
1338 };
1339
1340 WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1341
1342 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
1343 {
1344     this.snapshot = snapshot;
1345     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes, filter, nodeIndexes);
1346 }
1347
1348 WebInspector.HeapSnapshotNodesProvider.prototype = {
1349     _serialize: function(node)
1350     {
1351         return {id: node.id, name: node.name, nodeIndex: node.nodeIndex, retainedSize: node.retainedSize, selfSize: node.selfSize, type: node.type, flags: node.flags};
1352     },
1353
1354     sort: function(comparator, leftBound, rightBound, count)
1355     {
1356         var fieldName1 = comparator.fieldName1;
1357         var fieldName2 = comparator.fieldName2;
1358         var ascending1 = comparator.ascending1;
1359         var ascending2 = comparator.ascending2;
1360
1361         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1362         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1363
1364         function sortByNodeField(fieldName, ascending, indexA, indexB)
1365         {
1366             nodeA.nodeIndex = indexA;
1367             nodeB.nodeIndex = indexB;
1368             var valueA = nodeA[fieldName];
1369             var valueB = nodeB[fieldName];
1370             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1371             return ascending ? result : -result;
1372         }
1373
1374         function sortByComparator(indexA, indexB) {
1375             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1376             if (result === 0)
1377                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1378             return result;
1379         }
1380
1381         this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count);
1382     }
1383 };
1384
1385 WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1386
1387 WebInspector.HeapSnapshotPathFinder = function(snapshot, targetNodeIndex, skipHidden)
1388 {
1389     this._snapshot = snapshot;
1390     this._maxLength = 1;
1391     this._lengthLimit = 15;
1392     this._targetNodeIndex = targetNodeIndex;
1393     this._currentPath = null;
1394     this._skipHidden = skipHidden;
1395     this._rootChildren = this._fillRootChildren();
1396 }
1397
1398 WebInspector.HeapSnapshotPathFinder.prototype = {
1399     findNext: function()
1400     {
1401         for (var i = 0; i < 100000; ++i) {
1402             if (!this._buildNextPath()) {
1403                 if (++this._maxLength >= this._lengthLimit)
1404                     return null;
1405                 this._currentPath = null;
1406                 if (!this._buildNextPath())
1407                     return null;
1408             }
1409             if (this._isPathFound())
1410                 return {path:this._pathToString(this._currentPath), route:this._pathToRoute(this._currentPath), len:this._currentPath.length};
1411         }
1412
1413         return false;
1414     },
1415
1416     updateRoots: function(filter)
1417     {
1418         if (filter)
1419             filter = eval("(function(){return " + filter + "})()");
1420         this._rootChildren = this._fillRootChildren(filter);
1421         this._reset();
1422     },
1423
1424     _reset: function()
1425     {
1426         this._maxLength = 1;
1427         this._currentPath = null;
1428     },
1429
1430     _fillRootChildren: function(filter)
1431     {
1432         var result = [];
1433         for (var iter = this._snapshot.rootNode.edges; iter.hasNext(); iter.next()) {
1434             if (!filter) {
1435                 if (!iter.edge.isShortcut)
1436                     result[iter.edge.nodeIndex] = true;
1437             } else if (filter(iter.edge.node)) {
1438                 result[iter.edge.nodeIndex] = true;
1439             }
1440         }
1441         return result;
1442     },
1443
1444     _appendToCurrentPath: function(iter)
1445     {
1446         this._currentPath._cache[this._lastEdge.nodeIndex] = true;
1447         this._currentPath.push(iter);
1448     },
1449
1450     _removeLastFromCurrentPath: function()
1451     {
1452         this._currentPath.pop();
1453         delete this._currentPath._cache[this._lastEdge.nodeIndex];
1454     },
1455
1456     _hasInPath: function(nodeIndex)
1457     {
1458         return this._targetNodeIndex === nodeIndex
1459             || !!this._currentPath._cache[nodeIndex];
1460     },
1461
1462     _isPathFound: function()
1463     {
1464         return this._currentPath.length === this._maxLength
1465             && this._lastEdge.nodeIndex in this._rootChildren;
1466     },
1467
1468     get _lastEdgeIter()
1469     {
1470         return this._currentPath[this._currentPath.length - 1];
1471     },
1472
1473     get _lastEdge()
1474     {
1475         return this._lastEdgeIter.item;
1476     },
1477
1478     _skipEdge: function(edge)
1479     {
1480         return edge.isInvisible
1481             || (this._skipHidden && (edge.isHidden || edge.node.isHidden))
1482             || edge.isWeak
1483             || this._hasInPath(edge.nodeIndex);
1484     },
1485
1486     _nextEdgeIter: function()
1487     {
1488         var iter = this._lastEdgeIter;
1489         while (iter.hasNext() && this._skipEdge(iter.item))
1490             iter.next();
1491         return iter;
1492     },
1493
1494     _buildNextPath: function()
1495     {
1496         if (this._currentPath !== null) {
1497             var iter = this._lastEdgeIter;
1498             while (true) {
1499                 iter.next();
1500                 iter = this._nextEdgeIter();
1501                 if (iter.hasNext())
1502                     return true;
1503                 while (true) {
1504                     if (this._currentPath.length > 1) {
1505                         this._removeLastFromCurrentPath();
1506                         iter = this._lastEdgeIter;
1507                         iter.next();
1508                         iter = this._nextEdgeIter();
1509                         if (iter.hasNext()) {
1510                             while (this._currentPath.length < this._maxLength) {
1511                                 iter = this._nextEdgeIter();
1512                                 if (iter.hasNext())
1513                                     this._appendToCurrentPath(iter.item.node.retainers);
1514                                 else
1515                                     return true;
1516                             }
1517                             return true;
1518                         }
1519                     } else
1520                         return false;
1521                 }
1522             }
1523         } else {
1524             var node = new WebInspector.HeapSnapshotNode(this._snapshot, this._targetNodeIndex);
1525             this._currentPath = [node.retainers];
1526             this._currentPath._cache = {};
1527             while (this._currentPath.length < this._maxLength) {
1528                 var iter = this._nextEdgeIter();
1529                 if (iter.hasNext())
1530                     this._appendToCurrentPath(iter.item.node.retainers);
1531                 else
1532                     break;
1533             }
1534             return true;
1535         }
1536     },
1537
1538     _nodeToString: function(node)
1539     {
1540         if (node.id === 1)
1541             return node.name;
1542         else
1543             return node.name + "@" + node.id;
1544     },
1545
1546     _pathToString: function(path)
1547     {
1548         if (!path)
1549             return "";
1550         var sPath = [];
1551         for (var j = 0; j < path.length; ++j)
1552             sPath.push(path[j].item.toString());
1553         sPath.push(this._nodeToString(path[path.length - 1].item.node));
1554         sPath.reverse();
1555         return sPath.join("");
1556     },
1557
1558     _pathToRoute: function(path)
1559     {
1560         if (!path)
1561            return [];
1562         var route = [];
1563         route.push(this._targetNodeIndex);
1564         for (var i = 0; i < path.length; ++i)
1565             route.push(path[i].item.nodeIndex);
1566         route.reverse();
1567         return route;
1568     }
1569 };
1570
1571 WebInspector.HeapSnapshotsDiff = function(snapshot, className)
1572 {
1573     this._snapshot = snapshot;
1574     this._className = className;
1575 };
1576
1577 WebInspector.HeapSnapshotsDiff.prototype = {
1578     calculate: function()
1579     {
1580         var aggregates = this._snapshot.aggregates(true)[this._className];
1581         var indexes = aggregates ? aggregates.idxs : [];
1582         var i = 0, l = this._baseIds.length;
1583         var j = 0, m = indexes.length;
1584         var diff = { addedCount: 0, removedCount: 0, addedSize: 0, removedSize: 0 };
1585
1586         var nodeB = new WebInspector.HeapSnapshotNode(this._snapshot, indexes[j]);
1587         while (i < l && j < m) {
1588             var nodeAId = this._baseIds[i];
1589             if (nodeAId < nodeB.id) {
1590                 diff.removedCount++;
1591                 diff.removedSize += this._baseSelfSizes[i];
1592                 ++i;
1593             } else if (nodeAId > nodeB.id) {
1594                 diff.addedCount++;
1595                 diff.addedSize += nodeB.selfSize;
1596                 nodeB.nodeIndex = indexes[++j];
1597             } else {
1598                 ++i;
1599                 nodeB.nodeIndex = indexes[++j];
1600             }
1601         }
1602         while (i < l) {
1603             diff.removedCount++;
1604             diff.removedSize += this._baseSelfSizes[i];
1605             ++i;
1606         }
1607         while (j < m) {
1608             diff.addedCount++;
1609             diff.addedSize += nodeB.selfSize;
1610             nodeB.nodeIndex = indexes[++j];
1611         }
1612         diff.countDelta = diff.addedCount - diff.removedCount;
1613         diff.sizeDelta = diff.addedSize - diff.removedSize;
1614         return diff;
1615     },
1616
1617     pushBaseIds: function(baseIds)
1618     {
1619         this._baseIds = baseIds;
1620     },
1621
1622     pushBaseSelfSizes: function(baseSelfSizes)
1623     {
1624         this._baseSelfSizes = baseSelfSizes;
1625     }
1626 };