Home | History | Annotate | Download | only in front-end 
      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.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 
     41 WebInspector.HeapSnapshotArraySlice.prototype = {
     42     item: function(index)
     43     {
     44         return this._snapshot[this._arrayName][this._start + index];
     45     }
     46 }
     47 
     48 WebInspector.HeapSnapshotEdge = function(snapshot, edges, edgeIndex)
     49 {
     50     this._snapshot = snapshot;
     51     this._edges = edges;
     52     this.edgeIndex = edgeIndex || 0;
     53 }
     54 
     55 WebInspector.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 
    163 WebInspector.HeapSnapshotEdgeIterator = function(edge)
    164 {
    165     this.edge = edge;
    166 }
    167 
    168 WebInspector.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 
    200 WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainers, retainerIndex)
    201 {
    202     this._snapshot = snapshot;
    203     this._retainers = retainers;
    204     this.retainerIndex = retainerIndex || 0;
    205 }
    206 
    207 WebInspector.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 
    291 WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainer)
    292 {
    293     this.retainer = retainer;
    294 }
    295 
    296 WebInspector.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 
    328 WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex)
    329 {
    330     this._snapshot = snapshot;
    331     this._firstNodeIndex = nodeIndex;
    332     this.nodeIndex = nodeIndex;
    333 }
    334 
    335 WebInspector.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 
    446 WebInspector.HeapSnapshotNodeIterator = function(node)
    447 {
    448     this.node = node;
    449 }
    450 
    451 WebInspector.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 
    483 WebInspector.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 
    492 WebInspector.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 
    788 WebInspector.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 
    797 WebInspector.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 
    856 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames)
    857 {
    858     return {fieldName1:fieldNames[0], ascending1:fieldNames[1], fieldName2:fieldNames[2], ascending2:fieldNames[3]};
    859 }
    860 
    861 WebInspector.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 
    868 WebInspector.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 
    943 WebInspector.HeapSnapshotEdgesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
    944 
    945 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter)
    946 {
    947     this.snapshot = snapshot;
    948     WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes, filter);
    949 }
    950 
    951 WebInspector.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 
    990 WebInspector.HeapSnapshotNodesProvider.prototype.__proto__ = WebInspector.HeapSnapshotFilteredOrderedIterator.prototype;
    991 
    992 WebInspector.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 
   1003 WebInspector.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 
   1149 WebInspector.HeapSnapshotsDiff = function(snapshot, className)
   1150 {
   1151     this._snapshot = snapshot;
   1152     this._className = className;
   1153 };
   1154 
   1155 WebInspector.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