a7880eb64c4fc4610caeb777da6c188a77017cb8
[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 nameMatters = node.type === "object" || node.type === "native";
913             var className = node.className;
914             if (!aggregates.hasOwnProperty(className))
915                 aggregates[className] = { count: 0, self: 0, maxRet: 0, type: node.type, name: nameMatters ? node.name : null, idxs: [] };
916             var clss = aggregates[className];
917             ++clss.count;
918             clss.self += node.selfSize;
919             if (node.retainedSize > clss.maxRet)
920                 clss.maxRet = node.retainedSize;
921             clss.idxs.push(node.nodeIndex);
922         }
923         // Shave off provisionally allocated space.
924         for (var className in aggregates)
925             aggregates[className].idxs = aggregates[className].idxs.slice(0);
926         return aggregates;
927     },
928
929     _sortAggregateIndexes: function(aggregates)
930     {
931         var nodeA = new WebInspector.HeapSnapshotNode(this);
932         var nodeB = new WebInspector.HeapSnapshotNode(this);
933         for (var clss in aggregates)
934             aggregates[clss].idxs.sort(
935                 function(idxA, idxB) {
936                     nodeA.nodeIndex = idxA;
937                     nodeB.nodeIndex = idxB;
938                     return nodeA.id < nodeB.id ? -1 : 1;
939                 });
940     },
941
942     _buildNodeIndex: function()
943     {
944         var count = this.nodeCount;
945         this._nodeIndex = new Array(count + 1);
946         count = 0;
947         for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count)
948             this._nodeIndex[count] = nodesIter.index;
949         this._nodeIndex[count] = this._nodes.length;
950     },
951
952     _findNodePositionInIndex: function(index)
953     {
954         return binarySearch(index, this._nodeIndex, this._numbersComparator);
955     },
956
957     _findNearestNodeIndex: function(index)
958     {
959         var result = this._findNodePositionInIndex(index);
960         if (result < 0) {
961             result = -result - 1;
962             nodeIndex = this._nodeIndex[result];
963             // Binary search can return either maximum lower value, or minimum higher value.
964             if (nodeIndex > index)
965                 nodeIndex = this._nodeIndex[result - 1];
966         } else
967             var nodeIndex = this._nodeIndex[result];
968         return nodeIndex;
969     },
970
971     _getRetainerIndex: function(nodeIndex)
972     {
973         var nodePosition = this._findNodePositionInIndex(nodeIndex);
974         return this._retainerIndex[nodePosition];
975     },
976
977     _buildDominatedNodes: function()
978     {
979         this._buildReverseIndex(
980             "_dominatedIndex",
981             "_dominatedNodes",
982             (function (node, callback)
983              {
984                  var dominatorIndex = node.dominatorIndex;
985                  if (dominatorIndex !== node.nodeIndex)
986                      callback(this._findNodePositionInIndex(dominatorIndex));
987              }).bind(this),
988             (function (node, indexCallback, dataCallback)
989              {
990                  var dominatorIndex = node.dominatorIndex;
991                  if (dominatorIndex !== node.nodeIndex) {
992                      var dominatedIndex = this._getDominatedIndex(dominatorIndex);
993                      dataCallback(indexCallback(dominatedIndex), node.nodeIndex);
994                  }
995              }).bind(this));
996     },
997
998     _getDominatedIndex: function(nodeIndex)
999     {
1000         var nodePosition = this._findNodePositionInIndex(nodeIndex);
1001         return this._dominatedIndex[nodePosition];
1002     },
1003
1004     _markInvisibleEdges: function()
1005     {
1006         // Mark hidden edges of global objects as invisible.
1007         // FIXME: This is a temporary measure. Normally, we should
1008         // really hide all hidden nodes.
1009         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1010             var edge = iter.edge;
1011             if (!edge.isShortcut)
1012                 continue;
1013             var node = edge.node;
1014             var propNames = {};
1015             for (var innerIter = node.edges; innerIter.hasNext(); innerIter.next()) {
1016                 var globalObjEdge = innerIter.edge;
1017                 if (globalObjEdge.isShortcut)
1018                     propNames[globalObjEdge._nameOrIndex] = true;
1019             }
1020             for (innerIter.first(); innerIter.hasNext(); innerIter.next()) {
1021                 var globalObjEdge = innerIter.edge;
1022                 if (!globalObjEdge.isShortcut
1023                     && globalObjEdge.node.isHidden
1024                     && globalObjEdge._hasStringName
1025                     && (globalObjEdge._nameOrIndex in propNames))
1026                     this._nodes[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
1027             }
1028         }
1029     },
1030
1031     _numbersComparator: function(a, b)
1032     {
1033         return a < b ? -1 : (a > b ? 1 : 0);
1034     },
1035
1036     _calculateFlags: function()
1037     {
1038         var flag = this._nodeFlags.canBeQueried;
1039         this._flags = new Array(this.nodeCount);
1040         // Allow runtime properties query for objects accessible from DOMWindow objects
1041         // via regular properties, and for DOM wrappers. Trying to access random objects
1042         // can cause a crash due to insonsistent state of internal properties of wrappers.
1043         var list = [];
1044         for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
1045             if (iter.edge.node.isDOMWindow)
1046                 list.push(iter.edge.node);
1047         }
1048
1049         while (list.length) {
1050             var node = list.pop();
1051             if (this._flags[node.nodeIndex])
1052                 continue;
1053             this._flags[node.nodeIndex] = flag;
1054             for (var iter = node.edges; iter.hasNext(); iter.next()) {
1055                 var edge = iter.edge;
1056                 var node = edge.node;
1057                 if (this._flags[node.nodeIndex])
1058                     continue;
1059                 if (edge.isHidden || edge.isInvisible)
1060                     continue;
1061                 var name = edge.name;
1062                 if (!name)
1063                     continue;
1064                 if (edge.isInternal && name !== "native")
1065                     continue;
1066                 list.push(node);
1067             }
1068         }
1069     },
1070
1071     baseSnapshotHasNode: function(baseSnapshotId, className, nodeId)
1072     {
1073         return this._baseNodeIds[baseSnapshotId][className].binaryIndexOf(nodeId, this._numbersComparator) !== -1;
1074     },
1075
1076     pushBaseIds: function(baseSnapshotId, className, nodeIds)
1077     {
1078         if (!this._baseNodeIds)
1079             this._baseNodeIds = [];
1080         if (!this._baseNodeIds[baseSnapshotId])
1081             this._baseNodeIds[baseSnapshotId] = {};
1082         this._baseNodeIds[baseSnapshotId][className] = nodeIds;
1083     },
1084
1085     createDiff: function(className)
1086     {
1087         return new WebInspector.HeapSnapshotsDiff(this, className);
1088     },
1089
1090     _parseFilter: function(filter)
1091     {
1092         if (!filter)
1093             return null;
1094         var parsedFilter = eval("(function(){return " + filter + "})()");
1095         return parsedFilter.bind(this);
1096     },
1097
1098     createEdgesProvider: function(nodeIndex, filter)
1099     {
1100         return new WebInspector.HeapSnapshotEdgesProvider(this, nodeIndex, this._parseFilter(filter));
1101     },
1102
1103     createNodesProvider: function(filter)
1104     {
1105         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter));
1106     },
1107
1108     createNodesProviderForClass: function(className, aggregatesKey)
1109     {
1110         return new WebInspector.HeapSnapshotNodesProvider(this, null, this.aggregates(false, aggregatesKey)[className].idxs);
1111     },
1112
1113     createNodesProviderForDominator: function(nodeIndex, filter)
1114     {
1115         var node = new WebInspector.HeapSnapshotNode(this, nodeIndex);
1116         return new WebInspector.HeapSnapshotNodesProvider(this, this._parseFilter(filter), this._dominatedNodesOfNode(node));
1117     },
1118
1119     createPathFinder: function(targetNodeIndex, skipHidden)
1120     {
1121         return new WebInspector.HeapSnapshotPathFinder(this, targetNodeIndex, skipHidden);
1122     },
1123
1124     updateStaticData: function()
1125     {
1126         return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid, nodeFlags: this._nodeFlags, maxNodeId: this.maxNodeId};
1127     }
1128 };
1129
1130 WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder)
1131 {
1132     this._filter = filter;
1133     this._iterator = iterator;
1134     this._unfilteredIterationOrder = unfilteredIterationOrder;
1135     this._iterationOrder = null;
1136     this._position = 0;
1137     this._currentComparator = null;
1138     this._lastComparator = null;
1139 }
1140
1141 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = {
1142     _createIterationOrder: function()
1143     {
1144         if (this._iterationOrder)
1145             return;
1146         if (this._unfilteredIterationOrder && !this._filter) {
1147             this._iterationOrder = this._unfilteredIterationOrder.slice(0);
1148             this._unfilteredIterationOrder = null;
1149             return;
1150         }
1151         this._iterationOrder = [];
1152         var iterator = this._iterator;
1153         if (!this._unfilteredIterationOrder && !this._filter) {
1154             for (iterator.first(); iterator.hasNext(); iterator.next())
1155                 this._iterationOrder.push(iterator.index);
1156         } else if (!this._unfilteredIterationOrder) {
1157             for (iterator.first(); iterator.hasNext(); iterator.next()) {
1158                 if (this._filter(iterator.item))
1159                     this._iterationOrder.push(iterator.index);
1160             }
1161         } else {
1162             var order = this._unfilteredIterationOrder.constructor === Array ?
1163                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1164             for (var i = 0, l = order.length; i < l; ++i) {
1165                 iterator.index = order[i];
1166                 if (this._filter(iterator.item))
1167                     this._iterationOrder.push(iterator.index);
1168             }
1169             this._unfilteredIterationOrder = null;
1170         }
1171     },
1172
1173     first: function()
1174     {
1175         this._position = 0;
1176     },
1177
1178     hasNext: function()
1179     {
1180         return this._position < this._iterationOrder.length;
1181     },
1182
1183     get isEmpty()
1184     {
1185         if (this._iterationOrder)
1186             return !this._iterationOrder.length;
1187         if (this._unfilteredIterationOrder && !this._filter)
1188             return !this._unfilteredIterationOrder.length;
1189         var iterator = this._iterator;
1190         if (!this._unfilteredIterationOrder && !this._filter) {
1191             iterator.first();
1192             return !iterator.hasNext();
1193         } else if (!this._unfilteredIterationOrder) {
1194             for (iterator.first(); iterator.hasNext(); iterator.next())
1195                 if (this._filter(iterator.item))
1196                     return false;
1197         } else {
1198             var order = this._unfilteredIterationOrder.constructor === Array ?
1199                 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0);
1200             for (var i = 0, l = order.length; i < l; ++i) {
1201                 iterator.index = order[i];
1202                 if (this._filter(iterator.item))
1203                     return false;
1204             }
1205         }
1206         return true;
1207     },
1208
1209     get item()
1210     {
1211         this._iterator.index = this._iterationOrder[this._position];
1212         return this._iterator.item;
1213     },
1214
1215     get length()
1216     {
1217         this._createIterationOrder();
1218         return this._iterationOrder.length;
1219     },
1220
1221     next: function()
1222     {
1223         ++this._position;
1224     },
1225
1226     serializeNextItems: function(count)
1227     {
1228         this._createIterationOrder();
1229         var result = new Array(count);
1230         if (this._lastComparator !== this._currentComparator)
1231             this.sort(this._currentComparator, this._position, this._iterationOrder.length - 1, count);
1232         for (var i = 0 ; i < count && this.hasNext(); ++i, this.next())
1233             result[i] = this._serialize(this.item);
1234         result.length = i;
1235         result.hasNext = this.hasNext();
1236         result.totalLength = this._iterationOrder.length;
1237         return result;
1238     },
1239
1240     sortAndRewind: function(comparator)
1241     {
1242         this._lastComparator = this._currentComparator;
1243         this._currentComparator = comparator;
1244         var result = this._lastComparator !== this._currentComparator;
1245         if (result)
1246             this.first();
1247         return result;
1248     }
1249 }
1250
1251 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
1252 {
1253     return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
1254 }
1255
1256 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, nodeIndex, filter)
1257 {
1258     this.snapshot = snapshot;
1259     var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex);
1260     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(snapshot, node.rawEdges)), filter);
1261 }
1262
1263 WebInspector.HeapSnapshotEdgesProvider.prototype = {
1264     _serialize: function(edge)
1265     {
1266         return {name: edge.name, node: WebInspector.HeapSnapshotNodesProvider.prototype._serialize(edge.node), nodeIndex: edge.nodeIndex, type: edge.type};
1267     },
1268
1269     sort: function(comparator, leftBound, rightBound, count)
1270     {
1271         var fieldName1 = comparator.fieldName1;
1272         var fieldName2 = comparator.fieldName2;
1273         var ascending1 = comparator.ascending1;
1274         var ascending2 = comparator.ascending2;
1275
1276         var edgeA = this._iterator.item.clone();
1277         var edgeB = edgeA.clone();
1278         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1279         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1280
1281         function sortByEdgeFieldName(ascending, indexA, indexB)
1282         {
1283             edgeA.edgeIndex = indexA;
1284             edgeB.edgeIndex = indexB;
1285             if (edgeB.name === "__proto__") return -1;
1286             if (edgeA.name === "__proto__") return 1;
1287             var result =
1288                 edgeA.hasStringName === edgeB.hasStringName ?
1289                 (edgeA.name < edgeB.name ? -1 : (edgeA.name > edgeB.name ? 1 : 0)) :
1290                 (edgeA.hasStringName ? -1 : 1);
1291             return ascending ? result : -result;
1292         }
1293
1294         function sortByNodeField(fieldName, ascending, indexA, indexB)
1295         {
1296             edgeA.edgeIndex = indexA;
1297             edgeB.edgeIndex = indexB;
1298             nodeA.nodeIndex = edgeA.nodeIndex;
1299             nodeB.nodeIndex = edgeB.nodeIndex;
1300             var valueA = nodeA[fieldName];
1301             var valueB = nodeB[fieldName];
1302             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1303             return ascending ? result : -result;
1304         }
1305
1306         function sortByEdgeAndNode(indexA, indexB) {
1307             var result = sortByEdgeFieldName(ascending1, indexA, indexB);
1308             if (result === 0)
1309                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1310             return result;
1311         }
1312
1313         function sortByNodeAndEdge(indexA, indexB) {
1314             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1315             if (result === 0)
1316                 result = sortByEdgeFieldName(ascending2, indexA, indexB);
1317             return result;
1318         }
1319
1320         function sortByNodeAndNode(indexA, indexB) {
1321             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1322             if (result === 0)
1323                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1324             return result;
1325         }
1326
1327         if (fieldName1 === "!edgeName")
1328             this._iterationOrder.sortRange(sortByEdgeAndNode, leftBound, rightBound, count);
1329         else if (fieldName2 === "!edgeName")
1330             this._iterationOrder.sortRange(sortByNodeAndEdge, leftBound, rightBound, count);
1331         else
1332             this._iterationOrder.sortRange(sortByNodeAndNode, leftBound, rightBound, count);
1333     }
1334 };
1335
1336 WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1337
1338 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
1339 {
1340     this.snapshot = snapshot;
1341     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes, filter, nodeIndexes);
1342 }
1343
1344 WebInspector.HeapSnapshotNodesProvider.prototype = {
1345     _serialize: function(node)
1346     {
1347         return {id: node.id, name: node.name, nodeIndex: node.nodeIndex, retainedSize: node.retainedSize, selfSize: node.selfSize, type: node.type, flags: node.flags};
1348     },
1349
1350     sort: function(comparator, leftBound, rightBound, count)
1351     {
1352         var fieldName1 = comparator.fieldName1;
1353         var fieldName2 = comparator.fieldName2;
1354         var ascending1 = comparator.ascending1;
1355         var ascending2 = comparator.ascending2;
1356
1357         var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
1358         var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
1359
1360         function sortByNodeField(fieldName, ascending, indexA, indexB)
1361         {
1362             nodeA.nodeIndex = indexA;
1363             nodeB.nodeIndex = indexB;
1364             var valueA = nodeA[fieldName];
1365             var valueB = nodeB[fieldName];
1366             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
1367             return ascending ? result : -result;
1368         }
1369
1370         function sortByComparator(indexA, indexB) {
1371             var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
1372             if (result === 0)
1373                 result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
1374             return result;
1375         }
1376
1377         this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count);
1378     }
1379 };
1380
1381 WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
1382
1383 WebInspector.HeapSnapshotPathFinder = function(snapshot, targetNodeIndex, skipHidden)
1384 {
1385     this._snapshot = snapshot;
1386     this._maxLength = 1;
1387     this._lengthLimit = 15;
1388     this._targetNodeIndex = targetNodeIndex;
1389     this._currentPath = null;
1390     this._skipHidden = skipHidden;
1391     this._rootChildren = this._fillRootChildren();
1392 }
1393
1394 WebInspector.HeapSnapshotPathFinder.prototype = {
1395     findNext: function()
1396     {
1397         for (var i = 0; i < 100000; ++i) {
1398             if (!this._buildNextPath()) {
1399                 if (++this._maxLength >= this._lengthLimit)
1400                     return null;
1401                 this._currentPath = null;
1402                 if (!this._buildNextPath())
1403                     return null;
1404             }
1405             if (this._isPathFound())
1406                 return {path:this._pathToString(this._currentPath), route:this._pathToRoute(this._currentPath), len:this._currentPath.length};
1407         }
1408
1409         return false;
1410     },
1411
1412     updateRoots: function(filter)
1413     {
1414         if (filter)
1415             filter = eval("(function(){return " + filter + "})()");
1416         this._rootChildren = this._fillRootChildren(filter);
1417         this._reset();
1418     },
1419
1420     _reset: function()
1421     {
1422         this._maxLength = 1;
1423         this._currentPath = null;
1424     },
1425
1426     _fillRootChildren: function(filter)
1427     {
1428         var result = [];
1429         for (var iter = this._snapshot.rootNode.edges; iter.hasNext(); iter.next()) {
1430             if (!filter) {
1431                 if (!iter.edge.isShortcut)
1432                     result[iter.edge.nodeIndex] = true;
1433             } else if (filter(iter.edge.node)) {
1434                 result[iter.edge.nodeIndex] = true;
1435             }
1436         }
1437         return result;
1438     },
1439
1440     _appendToCurrentPath: function(iter)
1441     {
1442         this._currentPath._cache[this._lastEdge.nodeIndex] = true;
1443         this._currentPath.push(iter);
1444     },
1445
1446     _removeLastFromCurrentPath: function()
1447     {
1448         this._currentPath.pop();
1449         delete this._currentPath._cache[this._lastEdge.nodeIndex];
1450     },
1451
1452     _hasInPath: function(nodeIndex)
1453     {
1454         return this._targetNodeIndex === nodeIndex
1455             || !!this._currentPath._cache[nodeIndex];
1456     },
1457
1458     _isPathFound: function()
1459     {
1460         return this._currentPath.length === this._maxLength
1461             && this._lastEdge.nodeIndex in this._rootChildren;
1462     },
1463
1464     get _lastEdgeIter()
1465     {
1466         return this._currentPath[this._currentPath.length - 1];
1467     },
1468
1469     get _lastEdge()
1470     {
1471         return this._lastEdgeIter.item;
1472     },
1473
1474     _skipEdge: function(edge)
1475     {
1476         return edge.isInvisible
1477             || (this._skipHidden && (edge.isHidden || edge.node.isHidden))
1478             || edge.isWeak
1479             || this._hasInPath(edge.nodeIndex);
1480     },
1481
1482     _nextEdgeIter: function()
1483     {
1484         var iter = this._lastEdgeIter;
1485         while (iter.hasNext() && this._skipEdge(iter.item))
1486             iter.next();
1487         return iter;
1488     },
1489
1490     _buildNextPath: function()
1491     {
1492         if (this._currentPath !== null) {
1493             var iter = this._lastEdgeIter;
1494             while (true) {
1495                 iter.next();
1496                 iter = this._nextEdgeIter();
1497                 if (iter.hasNext())
1498                     return true;
1499                 while (true) {
1500                     if (this._currentPath.length > 1) {
1501                         this._removeLastFromCurrentPath();
1502                         iter = this._lastEdgeIter;
1503                         iter.next();
1504                         iter = this._nextEdgeIter();
1505                         if (iter.hasNext()) {
1506                             while (this._currentPath.length < this._maxLength) {
1507                                 iter = this._nextEdgeIter();
1508                                 if (iter.hasNext())
1509                                     this._appendToCurrentPath(iter.item.node.retainers);
1510                                 else
1511                                     return true;
1512                             }
1513                             return true;
1514                         }
1515                     } else
1516                         return false;
1517                 }
1518             }
1519         } else {
1520             var node = new WebInspector.HeapSnapshotNode(this._snapshot, this._targetNodeIndex);
1521             this._currentPath = [node.retainers];
1522             this._currentPath._cache = {};
1523             while (this._currentPath.length < this._maxLength) {
1524                 var iter = this._nextEdgeIter();
1525                 if (iter.hasNext())
1526                     this._appendToCurrentPath(iter.item.node.retainers);
1527                 else
1528                     break;
1529             }
1530             return true;
1531         }
1532     },
1533
1534     _nodeToString: function(node)
1535     {
1536         if (node.id === 1)
1537             return node.name;
1538         else
1539             return node.name + "@" + node.id;
1540     },
1541
1542     _pathToString: function(path)
1543     {
1544         if (!path)
1545             return "";
1546         var sPath = [];
1547         for (var j = 0; j < path.length; ++j)
1548             sPath.push(path[j].item.toString());
1549         sPath.push(this._nodeToString(path[path.length - 1].item.node));
1550         sPath.reverse();
1551         return sPath.join("");
1552     },
1553
1554     _pathToRoute: function(path)
1555     {
1556         if (!path)
1557            return [];
1558         var route = [];
1559         route.push(this._targetNodeIndex);
1560         for (var i = 0; i < path.length; ++i)
1561             route.push(path[i].item.nodeIndex);
1562         route.reverse();
1563         return route;
1564     }
1565 };
1566
1567 WebInspector.HeapSnapshotsDiff = function(snapshot, className)
1568 {
1569     this._snapshot = snapshot;
1570     this._className = className;
1571 };
1572
1573 WebInspector.HeapSnapshotsDiff.prototype = {
1574     calculate: function()
1575     {
1576         var aggregates = this._snapshot.aggregates(true)[this._className];
1577         var indexes = aggregates ? aggregates.idxs : [];
1578         var i = 0, l = this._baseIds.length;
1579         var j = 0, m = indexes.length;
1580         var diff = { addedCount: 0, removedCount: 0, addedSize: 0, removedSize: 0 };
1581
1582         var nodeB = new WebInspector.HeapSnapshotNode(this._snapshot, indexes[j]);
1583         while (i < l && j < m) {
1584             var nodeAId = this._baseIds[i];
1585             if (nodeAId < nodeB.id) {
1586                 diff.removedCount++;
1587                 diff.removedSize += this._baseSelfSizes[i];
1588                 ++i;
1589             } else if (nodeAId > nodeB.id) {
1590                 diff.addedCount++;
1591                 diff.addedSize += nodeB.selfSize;
1592                 nodeB.nodeIndex = indexes[++j];
1593             } else {
1594                 ++i;
1595                 nodeB.nodeIndex = indexes[++j];
1596             }
1597         }
1598         while (i < l) {
1599             diff.removedCount++;
1600             diff.removedSize += this._baseSelfSizes[i];
1601             ++i;
1602         }
1603         while (j < m) {
1604             diff.addedCount++;
1605             diff.addedSize += nodeB.selfSize;
1606             nodeB.nodeIndex = indexes[++j];
1607         }
1608         diff.countDelta = diff.addedCount - diff.removedCount;
1609         diff.sizeDelta = diff.addedSize - diff.removedSize;
1610         return diff;
1611     },
1612
1613     pushBaseIds: function(baseIds)
1614     {
1615         this._baseIds = baseIds;
1616     },
1617
1618     pushBaseSelfSizes: function(baseSelfSizes)
1619     {
1620         this._baseSelfSizes = baseSelfSizes;
1621     }
1622 };