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