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
31WebInspector.HeapSnapshotArraySlice = function(snapshot, arrayName, start, end)
32{
33    // Note: we don't reference snapshot contents directly to avoid
34    // holding references to big chunks of data.
35    this._snapshot = snapshot;
36    this._arrayName = arrayName;
37    this._start = start;
38    this.length = end - start;
39}
40
41WebInspector.HeapSnapshotArraySlice.prototype = {
42    item: function(index)
43    {
44        return this._snapshot[this._arrayName][this._start + index];
45    }
46}
47
48WebInspector.HeapSnapshotEdge = function(snapshot, edges, edgeIndex)
49{
50    this._snapshot = snapshot;
51    this._edges = edges;
52    this.edgeIndex = edgeIndex || 0;
53}
54
55WebInspector.HeapSnapshotEdge.prototype = {
56    clone: function()
57    {
58        return new WebInspector.HeapSnapshotEdge(this._snapshot, this._edges, this.edgeIndex);
59    },
60
61    get hasStringName()
62    {
63        if (!this.isShortcut)
64            return this._hasStringName;
65        return isNaN(parseInt(this._name, 10));
66    },
67
68    get isElement()
69    {
70        return this._type() === this._snapshot._edgeElementType;
71    },
72
73    get isHidden()
74    {
75        return this._type() === this._snapshot._edgeHiddenType;
76    },
77
78    get isInternal()
79    {
80        return this._type() === this._snapshot._edgeInternalType;
81    },
82
83    get isInvisible()
84    {
85        return this._type() === this._snapshot._edgeInvisibleType;
86    },
87
88    get isShortcut()
89    {
90        return this._type() === this._snapshot._edgeShortcutType;
91    },
92
93    get name()
94    {
95        if (!this.isShortcut)
96            return this._name;
97        var numName = parseInt(this._name, 10);
98        return isNaN(numName) ? this._name : numName;
99    },
100
101    get node()
102    {
103        return new WebInspector.HeapSnapshotNode(this._snapshot, this.nodeIndex);
104    },
105
106    get nodeIndex()
107    {
108        return this._edges.item(this.edgeIndex + this._snapshot._edgeToNodeOffset);
109    },
110
111    get rawEdges()
112    {
113        return this._edges;
114    },
115
116    toString: function()
117    {
118        switch (this.type) {
119        case "context": return "->" + this.name;
120        case "element": return "[" + this.name + "]";
121        case "property":
122            return this.name.indexOf(" ") === -1 ? "." + this.name : "[\"" + this.name + "\"]";
123        case "shortcut":
124            var name = this.name;
125            if (typeof name === "string")
126                return this.name.indexOf(" ") === -1 ? "." + this.name : "[\"" + this.name + "\"]";
127            else
128                return "[" + this.name + "]";
129        case "internal":
130        case "hidden":
131        case "invisible":
132            return "{" + this.name + "}";
133        };
134        return "?" + this.name + "?";
135    },
136
137    get type()
138    {
139        return this._snapshot._edgeTypes[this._type()];
140    },
141
142    get _hasStringName()
143    {
144        return !this.isElement && !this.isHidden;
145    },
146
147    get _name()
148    {
149        return this._hasStringName ? this._snapshot._strings[this._nameOrIndex] : this._nameOrIndex;
150    },
151
152    get _nameOrIndex()
153    {
154        return this._edges.item(this.edgeIndex + this._snapshot._edgeNameOffset);
155    },
156
157    _type: function()
158    {
159        return this._edges.item(this.edgeIndex + this._snapshot._edgeTypeOffset);
160    }
161};
162
163WebInspector.HeapSnapshotEdgeIterator = function(edge)
164{
165    this.edge = edge;
166}
167
168WebInspector.HeapSnapshotEdgeIterator.prototype = {
169    first: function()
170    {
171        this.edge.edgeIndex = 0;
172    },
173
174    hasNext: function()
175    {
176        return this.edge.edgeIndex < this.edge._edges.length;
177    },
178
179    get index()
180    {
181        return this.edge.edgeIndex;
182    },
183
184    set index(newIndex)
185    {
186        this.edge.edgeIndex = newIndex;
187    },
188
189    get item()
190    {
191        return this.edge;
192    },
193
194    next: function()
195    {
196        this.edge.edgeIndex += this.edge._snapshot._edgeFieldsCount;
197    }
198};
199
200WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainers, retainerIndex)
201{
202    this._snapshot = snapshot;
203    this._retainers = retainers;
204    this.retainerIndex = retainerIndex || 0;
205}
206
207WebInspector.HeapSnapshotRetainerEdge.prototype = {
208    clone: function()
209    {
210        return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainers, this.retainerIndex);
211    },
212
213    get hasStringName()
214    {
215        return this._edge.hasStringName;
216    },
217
218    get isElement()
219    {
220        return this._edge.isElement;
221    },
222
223    get isHidden()
224    {
225        return this._edge.isHidden;
226    },
227
228    get isInternal()
229    {
230        return this._edge.isInternal;
231    },
232
233    get isInvisible()
234    {
235        return this._edge.isInvisible;
236    },
237
238    get isShortcut()
239    {
240        return this._edge.isShortcut;
241    },
242
243    get name()
244    {
245        return this._edge.name;
246    },
247
248    get node()
249    {
250        return this._node;
251    },
252
253    get nodeIndex()
254    {
255        return this._nodeIndex;
256    },
257
258    get retainerIndex()
259    {
260        return this._retainerIndex;
261    },
262
263    set retainerIndex(newIndex)
264    {
265        if (newIndex !== this._retainerIndex) {
266            this._retainerIndex = newIndex;
267            this._setupEdge();
268        }
269    },
270
271    _setupEdge: function()
272    {
273        var globalEdgeIndex = this._retainers.item(this._retainerIndex);
274        this._nodeIndex = this._snapshot._findNearestNodeIndex(globalEdgeIndex);
275        this._node = new WebInspector.HeapSnapshotNode(this._snapshot, this._nodeIndex);
276        var edgeIndex = globalEdgeIndex - this._nodeIndex - this._snapshot._firstEdgeOffset;
277        this._edge = new WebInspector.HeapSnapshotEdge(this._snapshot, this._node.rawEdges, edgeIndex);
278    },
279
280    toString: function()
281    {
282        return this._edge.toString();
283    },
284
285    get type()
286    {
287        return this._edge.type;
288    }
289}
290
291WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainer)
292{
293    this.retainer = retainer;
294}
295
296WebInspector.HeapSnapshotRetainerEdgeIterator.prototype = {
297    first: function()
298    {
299        this.retainer.retainerIndex = 0;
300    },
301
302    hasNext: function()
303    {
304        return this.retainer.retainerIndex < this.retainer._retainers.length;
305    },
306
307    get index()
308    {
309        return this.retainer.retainerIndex;
310    },
311
312    set index(newIndex)
313    {
314        this.retainer.retainerIndex = newIndex;
315    },
316
317    get item()
318    {
319        return this.retainer;
320    },
321
322    next: function()
323    {
324        ++this.retainer.retainerIndex;
325    }
326};
327
328WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex)
329{
330    this._snapshot = snapshot;
331    this._firstNodeIndex = nodeIndex;
332    this.nodeIndex = nodeIndex;
333}
334
335WebInspector.HeapSnapshotNode.prototype = {
336    get className()
337    {
338        switch (this.type) {
339        case "hidden":
340            return WebInspector.UIString("(system)");
341        case "object":
342            return this.name;
343        case "native": {
344            var entitiesCountPos = this.name.indexOf("/");
345            return entitiesCountPos !== -1 ? this.name.substring(0, entitiesCountPos).trimRight() : this.name;
346        }
347        case "code":
348            return WebInspector.UIString("(compiled code)");
349        default:
350            return "(" + this.type + ")";
351        }
352    },
353
354    get dominatorIndex()
355    {
356        return this._nodes[this.nodeIndex + this._snapshot._dominatorOffset];
357    },
358
359    get edges()
360    {
361        return new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(this._snapshot, this.rawEdges));
362    },
363
364    get edgesCount()
365    {
366        return this._nodes[this.nodeIndex + this._snapshot._edgesCountOffset];
367    },
368
369    get id()
370    {
371        return this._nodes[this.nodeIndex + this._snapshot._nodeIdOffset];
372    },
373
374    get instancesCount()
375    {
376        return this._nodes[this.nodeIndex + this._snapshot._nodeInstancesCountOffset];
377    },
378
379    get isHidden()
380    {
381        return this._type() === this._snapshot._nodeHiddenType;
382    },
383
384    get isRoot()
385    {
386        return this.nodeIndex === this._snapshot._rootNodeIndex;
387    },
388
389    get name()
390    {
391        return this._snapshot._strings[this._name()];
392    },
393
394    get rawEdges()
395    {
396        var firstEdgeIndex = this._firstEdgeIndex();
397        return new WebInspector.HeapSnapshotArraySlice(this._snapshot, "_nodes", firstEdgeIndex, firstEdgeIndex + this.edgesCount * this._snapshot._edgeFieldsCount);
398    },
399
400    get retainedSize()
401    {
402        return this._nodes[this.nodeIndex + this._snapshot._nodeRetainedSizeOffset];
403    },
404
405    get retainers()
406    {
407        return new WebInspector.HeapSnapshotRetainerEdgeIterator(new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._snapshot._retainersForNode(this)));
408    },
409
410    get selfSize()
411    {
412        return this._nodes[this.nodeIndex + this._snapshot._nodeSelfSizeOffset];
413    },
414
415    get type()
416    {
417        return this._snapshot._nodeTypes[this._type()];
418    },
419
420    _name: function()
421    {
422        return this._nodes[this.nodeIndex + this._snapshot._nodeNameOffset];
423    },
424
425    get _nodes()
426    {
427        return this._snapshot._nodes;
428    },
429
430    _firstEdgeIndex: function()
431    {
432        return this.nodeIndex + this._snapshot._firstEdgeOffset;
433    },
434
435    get _nextNodeIndex()
436    {
437        return this._firstEdgeIndex() + this.edgesCount * this._snapshot._edgeFieldsCount;
438    },
439
440    _type: function()
441    {
442        return this._nodes[this.nodeIndex + this._snapshot._nodeTypeOffset];
443    }
444};
445
446WebInspector.HeapSnapshotNodeIterator = function(node)
447{
448    this.node = node;
449}
450
451WebInspector.HeapSnapshotNodeIterator.prototype = {
452    first: function()
453    {
454        this.node.nodeIndex = this.node._firstNodeIndex;
455    },
456
457    hasNext: function()
458    {
459        return this.node.nodeIndex < this.node._nodes.length;
460    },
461
462    get index()
463    {
464        return this.node.nodeIndex;
465    },
466
467    set index(newIndex)
468    {
469        this.node.nodeIndex = newIndex;
470    },
471
472    get item()
473    {
474        return this.node;
475    },
476
477    next: function()
478    {
479        this.node.nodeIndex = this.node._nextNodeIndex;
480    }
481}
482
483WebInspector.HeapSnapshot = function(profile)
484{
485    this.uid = profile.snapshot.uid;
486    this._nodes = profile.nodes;
487    this._strings = profile.strings;
488
489    this._init();
490}
491
492WebInspector.HeapSnapshot.prototype = {
493    _init: function()
494    {
495        this._metaNodeIndex = 0;
496        this._rootNodeIndex = 1;
497        var meta = this._nodes[this._metaNodeIndex];
498        this._nodeTypeOffset = meta.fields.indexOf("type");
499        this._nodeNameOffset = meta.fields.indexOf("name");
500        this._nodeIdOffset = meta.fields.indexOf("id");
501        this._nodeInstancesCountOffset = this._nodeIdOffset;
502        this._nodeSelfSizeOffset = meta.fields.indexOf("self_size");
503        this._nodeRetainedSizeOffset = meta.fields.indexOf("retained_size");
504        this._dominatorOffset = meta.fields.indexOf("dominator");
505        this._edgesCountOffset = meta.fields.indexOf("children_count");
506        this._firstEdgeOffset = meta.fields.indexOf("children");
507        this._nodeTypes = meta.types[this._nodeTypeOffset];
508        this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
509        var edgesMeta = meta.types[this._firstEdgeOffset];
510        this._edgeFieldsCount = edgesMeta.fields.length;
511        this._edgeTypeOffset = edgesMeta.fields.indexOf("type");
512        this._edgeNameOffset = edgesMeta.fields.indexOf("name_or_index");
513        this._edgeToNodeOffset = edgesMeta.fields.indexOf("to_node");
514        this._edgeTypes = edgesMeta.types[this._edgeTypeOffset];
515        this._edgeElementType = this._edgeTypes.indexOf("element");
516        this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
517        this._edgeInternalType = this._edgeTypes.indexOf("internal");
518        this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
519        this._edgeInvisibleType = this._edgeTypes.length;
520        this._edgeTypes.push("invisible");
521
522        this._markInvisibleEdges();
523    },
524
525    dispose: function()
526    {
527        delete this._nodes;
528        delete this._strings;
529        delete this._idsList;
530        delete this._retainers;
531        delete this._retainerIndex;
532        delete this._nodeIndex;
533        if (this._aggregates) {
534            delete this._aggregates;
535            this._aggregatesWithIndexes = false;
536        }
537        delete this._baseNodeIds;
538    },
539
540    get _allNodes()
541    {
542        return new WebInspector.HeapSnapshotNodeIterator(this.rootNode);
543    },
544
545    get nodeCount()
546    {
547        if (this._nodeCount)
548            return this._nodeCount;
549
550        this._nodeCount = 0;
551        for (var iter = this._allNodes; iter.hasNext(); iter.next())
552            ++this._nodeCount;
553        return this._nodeCount;
554    },
555
556    nodeFieldValuesByIndex: function(fieldName, indexes)
557    {
558        var node = new WebInspector.HeapSnapshotNode(this);
559        var result = new Array(indexes.length);
560        for (var i = 0, l = indexes.length; i < l; ++i) {
561            node.nodeIndex = indexes[i];
562            result[i] = node[fieldName];
563        }
564        return result;
565    },
566
567    get rootNode()
568    {
569        return new WebInspector.HeapSnapshotNode(this, this._rootNodeIndex);
570    },
571
572    get rootNodeIndex()
573    {
574        return this._rootNodeIndex;
575    },
576
577    get totalSize()
578    {
579        return this.rootNode.retainedSize;
580    },
581
582    hasId: function(id)
583    {
584        return this.nodeIds.binaryIndexOf(id, this._numbersComparator) >= 0;
585    },
586
587    get nodeIds()
588    {
589        if (!this._idsList)
590            this._buildIdsList();
591        return this._idsList;
592    },
593
594    _retainersForNode: function(node)
595    {
596        if (!this._retainers)
597            this._buildRetainers();
598
599        var retIndexFrom = this._getRetainerIndex(node.nodeIndex);
600        var retIndexTo = this._getRetainerIndex(node._nextNodeIndex);
601        return new WebInspector.HeapSnapshotArraySlice(this, "_retainers", retIndexFrom, retIndexTo);
602    },
603
604    aggregates: function(withNodeIndexes)
605    {
606        if (!this._aggregates)
607            this._buildAggregates();
608        if (withNodeIndexes && !this._aggregatesWithIndexes)
609            this._buildAggregatesIndexes();
610        return this._aggregates;
611    },
612
613    _buildRetainers: function()
614    {
615        if (!this._nodeIndex)
616            this._buildNodeIndex();
617
618        this._retainerIndex = new Array(this._nodeIndex.length);
619        for (var i = 0, l = this._retainerIndex.length; i < l; ++i)
620            this._retainerIndex[i] = 0;
621        for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
622            var node = nodesIter.node;
623            for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next()) {
624                var edge = edgesIter.edge;
625                var nodeIndex = edge.nodeIndex;
626                var position = this._findNodePositionInIndex(nodeIndex);
627                ++this._retainerIndex[position];
628            }
629        }
630        var retainerCount = 0;
631        for (i = 0, l = this._retainerIndex.length; i < l; ++i)
632            retainerCount += this._retainerIndex[i];
633        this._retainers = new Array(retainerCount + 1);
634        var retainerPosition = 0;
635        for (i = 0, l = this._retainerIndex.length; i < l; ++i) {
636            retainerCount = this._retainers[retainerPosition] = this._retainerIndex[i];
637            this._retainerIndex[i] = retainerPosition;
638            retainerPosition += retainerCount;
639        }
640        for (nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next()) {
641            var node = nodesIter.node;
642            for (var edgesIter = node.edges; edgesIter.hasNext(); edgesIter.next()) {
643                var edge = edgesIter.edge;
644                var nodeIndex = edge.nodeIndex;
645                var retIndex = this._getRetainerIndex(nodeIndex);
646                var idx = retIndex + (--this._retainers[retIndex]);
647                this._retainers[idx] = node.nodeIndex + this._firstEdgeOffset + edge.edgeIndex;
648            }
649        }
650    },
651
652    _buildAggregates: function()
653    {
654        this._aggregates = {};
655        for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
656            var node = iter.node;
657            var className = node.className;
658            var nameMatters = node.type === "object" || node.type === "native";
659            if (node.type !== "native" && node.selfSize === 0)
660                continue;
661            if (!(className in this._aggregates))
662                this._aggregates[className] = { count: 0, self: 0, maxRet: 0, type: node.type, name: nameMatters ? node.name : null, idxs: [] };
663            var clss = this._aggregates[className];
664            ++clss.count;
665            clss.self += node.selfSize;
666            if (node.retainedSize > clss.maxRet)
667                clss.maxRet = node.retainedSize;
668        }
669    },
670
671    _buildAggregatesIndexes: function()
672    {
673        for (var iter = this._allNodes; iter.hasNext(); iter.next()) {
674            var node = iter.node;
675            var className = node.className;
676            var clss = this._aggregates[className];
677            if (clss)
678                clss.idxs.push(node.nodeIndex);
679        }
680
681        var nodeA = new WebInspector.HeapSnapshotNode(this);
682        var nodeB = new WebInspector.HeapSnapshotNode(this);
683        for (var clss in this._aggregates)
684            this._aggregates[clss].idxs.sort(
685                function(idxA, idxB) {
686                    nodeA.nodeIndex = idxA;
687                    nodeB.nodeIndex = idxB;
688                    return nodeA.id < nodeB.id ? -1 : 1;
689                });
690
691        this._aggregatesWithIndexes = true;
692    },
693
694    _buildIdsList: function()
695    {
696        var count = 0;
697        for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count);
698        this._idsList = new Array(count);
699        count = 0;
700        for (nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count)
701            this._idsList[count] = nodesIter.node.id;
702        this._idsList.sort(this._numbersComparator);
703    },
704
705    _buildNodeIndex: function()
706    {
707        var count = 0;
708        for (var nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count);
709        this._nodeIndex = new Array(count + 1);
710        count = 0;
711        for (nodesIter = this._allNodes; nodesIter.hasNext(); nodesIter.next(), ++count)
712            this._nodeIndex[count] = nodesIter.index;
713        this._nodeIndex[count] = this._nodes.length;
714    },
715
716    _findNodePositionInIndex: function(index)
717    {
718        return binarySearch(index, this._nodeIndex, this._numbersComparator);
719    },
720
721    _findNearestNodeIndex: function(index)
722    {
723        var result = this._findNodePositionInIndex(index);
724        if (result < 0) {
725            result = -result - 1;
726            nodeIndex = this._nodeIndex[result];
727            // Binary search can return either maximum lower value, or minimum higher value.
728            if (nodeIndex > index)
729                nodeIndex = this._nodeIndex[result - 1];
730        } else
731            var nodeIndex = this._nodeIndex[result];
732        return nodeIndex;
733    },
734
735    _getRetainerIndex: function(nodeIndex)
736    {
737        var nodePosition = this._findNodePositionInIndex(nodeIndex);
738        return this._retainerIndex[nodePosition];
739    },
740
741    _markInvisibleEdges: function()
742    {
743        // Mark hidden edges of global objects as invisible.
744        // FIXME: This is a temporary measure. Normally, we should
745        // really hide all hidden nodes.
746        for (var iter = this.rootNode.edges; iter.hasNext(); iter.next()) {
747            var edge = iter.edge;
748            if (!edge.isShortcut)
749                continue;
750            var node = edge.node;
751            var propNames = {};
752            for (var innerIter = node.edges; innerIter.hasNext(); innerIter.next()) {
753                var globalObjEdge = innerIter.edge;
754                if (globalObjEdge.isShortcut)
755                    propNames[globalObjEdge._nameOrIndex] = true;
756            }
757            for (innerIter.first(); innerIter.hasNext(); innerIter.next()) {
758                var globalObjEdge = innerIter.edge;
759                if (!globalObjEdge.isShortcut
760                    && globalObjEdge.node.isHidden
761                    && globalObjEdge._hasStringName
762                    && (globalObjEdge._nameOrIndex in propNames))
763                    this._nodes[globalObjEdge._edges._start + globalObjEdge.edgeIndex + this._edgeTypeOffset] = this._edgeInvisibleType;
764            }
765        }
766    },
767
768    _numbersComparator: function(a, b)
769    {
770        return a < b ? -1 : (a > b ? 1 : 0);
771    },
772
773    baseSnapshotHasNode: function(baseSnapshotId, className, nodeId)
774    {
775        return this._baseNodeIds[baseSnapshotId][className].binaryIndexOf(nodeId, this._numbersComparator) !== -1;
776    },
777
778    updateBaseNodeIds: function(baseSnapshotId, className, nodeIds)
779    {
780        if (!this._baseNodeIds)
781            this._baseNodeIds = [];
782        if (!this._baseNodeIds[baseSnapshotId])
783            this._baseNodeIds[baseSnapshotId] = {};
784        this._baseNodeIds[baseSnapshotId][className] = nodeIds;
785    }
786};
787
788WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter)
789{
790    this._filter = filter;
791    this._iterator = iterator;
792    this._iterationOrder = null;
793    this._position = 0;
794    this._lastComparator = null;
795}
796
797WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = {
798    _createIterationOrder: function()
799    {
800        this._iterationOrder = [];
801        var iterator = this._iterator;
802        if (!this._filter) {
803            for (iterator.first(); iterator.hasNext(); iterator.next())
804                this._iterationOrder.push(iterator.index);
805        } else {
806            for (iterator.first(); iterator.hasNext(); iterator.next()) {
807                if (this._filter(iterator.item))
808                    this._iterationOrder.push(iterator.index);
809            }
810        }
811    },
812
813    first: function()
814    {
815        this._position = 0;
816    },
817
818    hasNext: function()
819    {
820        return this._position < this._iterationOrder.length;
821    },
822
823    get isEmpty()
824    {
825        if (this._iterationOrder)
826            return !this._iterationOrder.length;
827        var iterator = this._iterator;
828        if (!this._filter) {
829            iterator.first();
830            return !iterator.hasNext();
831        }
832        for (iterator.first(); iterator.hasNext(); iterator.next())
833            if (this._filter(iterator.item)) return false;
834        return true;
835    },
836
837    get item()
838    {
839        this._iterator.index = this._iterationOrder[this._position];
840        return this._iterator.item;
841    },
842
843    get length()
844    {
845        if (!this._iterationOrder)
846            this._createIterationOrder();
847        return this._iterationOrder.length;
848    },
849
850    next: function()
851    {
852        ++this._position;
853    },
854}
855
856WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
857{
858    return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
859}
860
861WebInspector.HeapSnapshotEdgesProvider = function(snapshot, nodeIndex, filter)
862{
863    this.snapshot = snapshot;
864    var node = new WebInspector.HeapSnapshotNode(snapshot, nodeIndex);
865    WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, new WebInspector.HeapSnapshotEdgeIterator(new WebInspector.HeapSnapshotEdge(snapshot, node.rawEdges)), filter);
866}
867
868WebInspector.HeapSnapshotEdgesProvider.prototype = {
869    sort: function(comparator)
870    {
871        if (this._lastComparator === comparator)
872            return false;
873        this._lastComparator = comparator;
874        var fieldName1 = comparator.fieldName1;
875        var fieldName2 = comparator.fieldName2;
876        var ascending1 = comparator.ascending1;
877        var ascending2 = comparator.ascending2;
878
879        var edgeA = this._iterator.item.clone();
880        var edgeB = edgeA.clone();
881        var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
882        var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
883
884        function sortByEdgeFieldName(ascending, indexA, indexB)
885        {
886            edgeA.edgeIndex = indexA;
887            edgeB.edgeIndex = indexB;
888            if (edgeB.name === "__proto__") return -1;
889            if (edgeA.name === "__proto__") return 1;
890            var result =
891                edgeA.hasStringName === edgeB.hasStringName ?
892                (edgeA.name < edgeB.name ? -1 : (edgeA.name > edgeB.name ? 1 : 0)) :
893                (edgeA.hasStringName ? -1 : 1);
894            return ascending ? result : -result;
895        }
896
897        function sortByNodeField(fieldName, ascending, indexA, indexB)
898        {
899            edgeA.edgeIndex = indexA;
900            edgeB.edgeIndex = indexB;
901            nodeA.nodeIndex = edgeA.nodeIndex;
902            nodeB.nodeIndex = edgeB.nodeIndex;
903            var valueA = nodeA[fieldName];
904            var valueB = nodeB[fieldName];
905            var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
906            return ascending ? result : -result;
907        }
908
909        if (!this._iterationOrder)
910            this._createIterationOrder();
911
912        function sortByEdgeAndNode(indexA, indexB) {
913            var result = sortByEdgeFieldName(ascending1, indexA, indexB);
914            if (result === 0)
915                result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
916            return result;
917        }
918
919        function sortByNodeAndEdge(indexA, indexB) {
920            var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
921            if (result === 0)
922                result = sortByEdgeFieldName(ascending2, indexA, indexB);
923            return result;
924        }
925
926        function sortByNodeAndNode(indexA, indexB) {
927            var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
928            if (result === 0)
929                result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
930            return result;
931        }
932
933        if (fieldName1 === "!edgeName")
934            this._iterationOrder.sort(sortByEdgeAndNode);
935        else if (fieldName2 === "!edgeName")
936            this._iterationOrder.sort(sortByNodeAndEdge);
937        else
938            this._iterationOrder.sort(sortByNodeAndNode);
939        return true;
940    }
941};
942
943WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
944
945WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter)
946{
947    this.snapshot = snapshot;
948    WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes, filter);
949}
950
951WebInspector.HeapSnapshotNodesProvider.prototype = {
952    sort: function(comparator)
953    {
954        if (this._lastComparator === comparator)
955            return false;
956        this._lastComparator = comparator;
957        var fieldName1 = comparator.fieldName1;
958        var fieldName2 = comparator.fieldName2;
959        var ascending1 = comparator.ascending1;
960        var ascending2 = comparator.ascending2;
961
962        var nodeA = new WebInspector.HeapSnapshotNode(this.snapshot);
963        var nodeB = new WebInspector.HeapSnapshotNode(this.snapshot);
964
965        function sortByNodeField(fieldName, ascending, indexA, indexB)
966        {
967            nodeA.nodeIndex = indexA;
968            nodeB.nodeIndex = indexB;
969            var valueA = nodeA[fieldName];
970            var valueB = nodeB[fieldName];
971            var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
972            return ascending ? result : -result;
973        }
974
975        if (!this._iterationOrder)
976            this._createIterationOrder();
977
978        function sortByComparator(indexA, indexB) {
979            var result = sortByNodeField(fieldName1, ascending1, indexA, indexB);
980            if (result === 0)
981                result = sortByNodeField(fieldName2, ascending2, indexA, indexB);
982            return result;
983        }
984
985        this._iterationOrder.sort(sortByComparator);
986        return true;
987    }
988};
989
990WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
991
992WebInspector.HeapSnapshotPathFinder = function(snapshot, targetNodeIndex)
993{
994    this._snapshot = snapshot;
995    this._maxLength = 1;
996    this._lengthLimit = 15;
997    this._targetNodeIndex = targetNodeIndex;
998    this._currentPath = null;
999    this._skipHidden = !WebInspector.DetailedHeapshotView.prototype.showHiddenData;
1000    this._rootChildren = this._fillRootChildren();
1001}
1002
1003WebInspector.HeapSnapshotPathFinder.prototype = {
1004    findNext: function()
1005    {
1006        for (var i = 0; i < 100000; ++i) {
1007            if (!this._buildNextPath()) {
1008                if (++this._maxLength >= this._lengthLimit)
1009                    return null;
1010                this._currentPath = null;
1011                if (!this._buildNextPath())
1012                    return null;
1013            }
1014            if (this._isPathFound())
1015                return {path:this._pathToString(this._currentPath), len:this._currentPath.length};
1016        }
1017
1018        return false;
1019    },
1020
1021    updateRoots: function(filter)
1022    {
1023        this._rootChildren = this._fillRootChildren(filter);
1024    },
1025
1026    _fillRootChildren: function(filter)
1027    {
1028        var result = [];
1029        for (var iter = this._snapshot.rootNode.edges; iter.hasNext(); iter.next()) {
1030            if (!filter || filter(iter.edge.node))
1031                result[iter.edge.nodeIndex] = true;
1032        }
1033        return result;
1034    },
1035
1036    _appendToCurrentPath: function(iter)
1037    {
1038        this._currentPath._cache[this._lastEdge.nodeIndex] = true;
1039        this._currentPath.push(iter);
1040    },
1041
1042    _removeLastFromCurrentPath: function()
1043    {
1044        this._currentPath.pop();
1045        delete this._currentPath._cache[this._lastEdge.nodeIndex];
1046    },
1047
1048    _hasInPath: function(nodeIndex)
1049    {
1050        return this._targetNodeIndex === nodeIndex
1051            || !!this._currentPath._cache[nodeIndex];
1052    },
1053
1054    _isPathFound: function()
1055    {
1056        return this._currentPath.length === this._maxLength
1057            && this._lastEdge.nodeIndex in this._rootChildren;
1058    },
1059
1060    get _lastEdgeIter()
1061    {
1062        return this._currentPath[this._currentPath.length - 1];
1063    },
1064
1065    get _lastEdge()
1066    {
1067        return this._lastEdgeIter.item;
1068    },
1069
1070    _skipEdge: function(edge)
1071    {
1072        return edge.isInvisible
1073            || (this._skipHidden && (edge.isHidden || edge.node.isHidden))
1074            || this._hasInPath(edge.nodeIndex);
1075    },
1076
1077    _nextEdgeIter: function()
1078    {
1079        var iter = this._lastEdgeIter;
1080        while (this._skipEdge(iter.item) && iter.hasNext())
1081            iter.next();
1082        return iter;
1083    },
1084
1085    _buildNextPath: function()
1086    {
1087        if (this._currentPath !== null) {
1088            var iter = this._lastEdgeIter;
1089            while (true) {
1090                iter.next();
1091                if (iter.hasNext())
1092                    return true;
1093                while (true) {
1094                    if (this._currentPath.length > 1) {
1095                        this._removeLastFromCurrentPath();
1096                        iter = this._lastEdgeIter;
1097                        iter.next();
1098                        iter = this._nextEdgeIter();
1099                        if (iter.hasNext()) {
1100                            while (this._currentPath.length < this._maxLength) {
1101                                iter = this._nextEdgeIter();
1102                                if (iter.hasNext())
1103                                    this._appendToCurrentPath(iter.item.node.retainers);
1104                                else
1105                                    return true;
1106                            }
1107                            return true;
1108                        }
1109                    } else
1110                        return false;
1111                }
1112            }
1113        } else {
1114            var node = new WebInspector.HeapSnapshotNode(this._snapshot, this._targetNodeIndex);
1115            this._currentPath = [node.retainers];
1116            this._currentPath._cache = {};
1117            while (this._currentPath.length < this._maxLength) {
1118                var iter = this._nextEdgeIter();
1119                if (iter.hasNext())
1120                    this._appendToCurrentPath(iter.item.node.retainers);
1121                else
1122                    break;
1123            }
1124            return true;
1125        }
1126    },
1127
1128    _nodeToString: function(node)
1129    {
1130        if (node.id === 1)
1131            return node.name;
1132        else
1133            return node.name + "@" + node.id;
1134    },
1135
1136    _pathToString: function(path)
1137    {
1138        if (!path)
1139            return "";
1140        var sPath = [];
1141        for (var j = 0; j < path.length; ++j)
1142            sPath.push(path[j].item.toString());
1143        sPath.push(this._nodeToString(path[path.length - 1].item.node));
1144        sPath.reverse();
1145        return sPath.join("");
1146    }
1147};
1148
1149WebInspector.HeapSnapshotsDiff = function(snapshot, className)
1150{
1151    this._snapshot = snapshot;
1152    this._className = className;
1153};
1154
1155WebInspector.HeapSnapshotsDiff.prototype = {
1156    set baseIds(baseIds)
1157    {
1158        this._baseIds = baseIds;
1159    },
1160
1161    set baseSelfSizes(baseSelfSizes)
1162    {
1163        this._baseSelfSizes = baseSelfSizes;
1164    },
1165
1166    calculate: function()
1167    {
1168        var indexes = this._snapshot.aggregates(true)[this._className].idxs;
1169        var i = 0, l = this._baseIds.length;
1170        var j = 0, m = indexes.length;
1171        var diff = { addedCount: 0, removedCount: 0, addedSize: 0, removedSize: 0 };
1172
1173        var nodeB = new WebInspector.HeapSnapshotNode(this._snapshot);
1174        while (i < l && j < m) {
1175            var nodeAId = this._baseIds[i];
1176            if (nodeAId < nodeB.id) {
1177                diff.removedCount++;
1178                diff.removedSize += this._baseSelfSizes[i];
1179                ++i;
1180            } else if (nodeAId > nodeB.id) {
1181                diff.addedCount++;
1182                diff.addedSize += nodeB.selfSize;
1183                nodeB.nodeIndex = indexes[++j];
1184            } else {
1185                ++i;
1186                nodeB.nodeIndex = indexes[++j];
1187            }
1188        }
1189        while (i < l) {
1190            diff.removedCount++;
1191            diff.removedSize += this._baseSelfSizes[i];
1192            ++i;
1193        }
1194        while (j < m) {
1195            diff.addedCount++;
1196            diff.addedSize += nodeB.selfSize;
1197            nodeB.nodeIndex = indexes[++j];
1198        }
1199        diff.countDelta = diff.addedCount - diff.removedCount;
1200        diff.sizeDelta = diff.addedSize - diff.removedSize;
1201        return diff;
1202    }
1203};
1204