src/third_party/WebKit/Source/devtools/front_end/HeapSnapshotGridNodes.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 /**
  32  * @constructor
  33  * @extends {WebInspector.DataGridNode}
  34  * @param {!WebInspector.HeapSnapshotSortableDataGrid} tree
  35  * @param {boolean} hasChildren
  36  */
  37 WebInspector.HeapSnapshotGridNode = function(tree, hasChildren)
  38 {
  39     WebInspector.DataGridNode.call(this, null, hasChildren);
  40     this._dataGrid = tree;
  41     this._instanceCount = 0;
  42
  43     this._savedChildren = null;
  44     /**
  45      * List of position ranges for all visible nodes: [startPos1, endPos1),...,[startPosN, endPosN)
  46      * Position is an item position in the provider.
  47      */
  48     this._retrievedChildrenRanges = [];
  49 }
  50
  51 WebInspector.HeapSnapshotGridNode.Events = {
  52     PopulateComplete: "PopulateComplete"
  53 }
  54
  55 /**
  56  * @param {!Array.<string>} fieldNames
  57  * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
  58  */
  59 WebInspector.HeapSnapshotGridNode.createComparator = function(fieldNames)
  60 {
  61     return /** @type {!WebInspector.HeapSnapshotCommon.ComparatorConfig} */ ({fieldName1: fieldNames[0], ascending1: fieldNames[1], fieldName2: fieldNames[2], ascending2: fieldNames[3]});
  62 }
  63
  64 WebInspector.HeapSnapshotGridNode.prototype = {
  65     /**
  66      * @return {!WebInspector.HeapSnapshotProviderProxy}
  67      */
  68     createProvider: function()
  69     {
  70         throw new Error("Needs implemented.");
  71     },
  72
  73     /**
  74      * @return {!WebInspector.HeapSnapshotProviderProxy}
  75      */
  76     _provider: function()
  77     {
  78         if (!this._providerObject)
  79             this._providerObject = this.createProvider();
  80         return this._providerObject;
  81     },
  82
  83     /**
  84      * @param {string} columnIdentifier
  85      * @return {!Element}
  86      */
  87     createCell: function(columnIdentifier)
  88     {
  89         var cell = WebInspector.DataGridNode.prototype.createCell.call(this, columnIdentifier);
  90         if (this._searchMatched)
  91             cell.classList.add("highlight");
  92         return cell;
  93     },
  94
  95     collapse: function()
  96     {
  97         WebInspector.DataGridNode.prototype.collapse.call(this);
  98         this._dataGrid.updateVisibleNodes();
  99     },
 100
 101     dispose: function()
 102     {
 103         if (this._providerObject)
 104             this._providerObject.dispose();
 105         for (var node = this.children[0]; node; node = node.traverseNextNode(true, this, true))
 106             if (node.dispose)
 107                 node.dispose();
 108     },
 109
 110     _reachableFromWindow: false,
 111
 112     queryObjectContent: function(callback)
 113     {
 114     },
 115
 116     /**
 117      * @override
 118      */
 119     wasDetached: function()
 120     {
 121         this._dataGrid.nodeWasDetached(this);
 122     },
 123
 124     _toPercentString: function(num)
 125     {
 126         return num.toFixed(0) + "\u2009%"; // \u2009 is a thin space.
 127     },
 128
 129     /**
 130      * @param {number} nodePosition
 131      * @return {?WebInspector.DataGridNode}
 132      */
 133     childForPosition: function(nodePosition)
 134     {
 135         var indexOfFirsChildInRange = 0;
 136         for (var i = 0; i < this._retrievedChildrenRanges.length; i++) {
 137            var range = this._retrievedChildrenRanges[i];
 138            if (range.from <= nodePosition && nodePosition < range.to) {
 139                var childIndex = indexOfFirsChildInRange + nodePosition - range.from;
 140                return this.children[childIndex];
 141            }
 142            indexOfFirsChildInRange += range.to - range.from + 1;
 143         }
 144         return null;
 145     },
 146
 147     _createValueCell: function(columnIdentifier)
 148     {
 149         var cell = document.createElement("td");
 150         cell.className = columnIdentifier + "-column";
 151         if (this.dataGrid.snapshot.totalSize !== 0) {
 152             var div = document.createElement("div");
 153             var valueSpan = document.createElement("span");
 154             valueSpan.textContent = this.data[columnIdentifier];
 155             div.appendChild(valueSpan);
 156             var percentColumn = columnIdentifier + "-percent";
 157             if (percentColumn in this.data) {
 158                 var percentSpan = document.createElement("span");
 159                 percentSpan.className = "percent-column";
 160                 percentSpan.textContent = this.data[percentColumn];
 161                 div.appendChild(percentSpan);
 162                 div.classList.add("heap-snapshot-multiple-values");
 163             }
 164             cell.appendChild(div);
 165         }
 166         return cell;
 167     },
 168
 169     populate: function(event)
 170     {
 171         if (this._populated)
 172             return;
 173         this._populated = true;
 174
 175         /**
 176          * @this {WebInspector.HeapSnapshotGridNode}
 177          */
 178         function sorted()
 179         {
 180             this._populateChildren();
 181         }
 182         this._provider().sortAndRewind(this.comparator(), sorted.bind(this));
 183     },
 184
 185     expandWithoutPopulate: function(callback)
 186     {
 187         // Make sure default populate won't take action.
 188         this._populated = true;
 189         this.expand();
 190         this._provider().sortAndRewind(this.comparator(), callback);
 191     },
 192
 193     /**
 194      * @param {?number=} fromPosition
 195      * @param {?number=} toPosition
 196      * @param {function()=} afterPopulate
 197      */
 198     _populateChildren: function(fromPosition, toPosition, afterPopulate)
 199     {
 200         fromPosition = fromPosition || 0;
 201         toPosition = toPosition || fromPosition + this._dataGrid.defaultPopulateCount();
 202         var firstNotSerializedPosition = fromPosition;
 203
 204         /**
 205          * @this {WebInspector.HeapSnapshotGridNode}
 206          */
 207         function serializeNextChunk()
 208         {
 209             if (firstNotSerializedPosition >= toPosition)
 210                 return;
 211             var end = Math.min(firstNotSerializedPosition + this._dataGrid.defaultPopulateCount(), toPosition);
 212             this._provider().serializeItemsRange(firstNotSerializedPosition, end, childrenRetrieved.bind(this));
 213             firstNotSerializedPosition = end;
 214         }
 215
 216         /**
 217          * @this {WebInspector.HeapSnapshotGridNode}
 218          */
 219         function insertRetrievedChild(item, insertionIndex)
 220         {
 221             if (this._savedChildren) {
 222                 var hash = this._childHashForEntity(item);
 223                 if (hash in this._savedChildren) {
 224                     this.insertChild(this._savedChildren[hash], insertionIndex);
 225                     return;
 226                 }
 227             }
 228             this.insertChild(this._createChildNode(item), insertionIndex);
 229         }
 230
 231         /**
 232          * @this {WebInspector.HeapSnapshotGridNode}
 233          */
 234         function insertShowMoreButton(from, to, insertionIndex)
 235         {
 236             var button = new WebInspector.ShowMoreDataGridNode(this._populateChildren.bind(this), from, to, this._dataGrid.defaultPopulateCount());
 237             this.insertChild(button, insertionIndex);
 238         }
 239
 240         /**
 241          * @param {!WebInspector.HeapSnapshotCommon.ItemsRange} itemsRange
 242          * @this {WebInspector.HeapSnapshotGridNode}
 243          */
 244         function childrenRetrieved(itemsRange)
 245         {
 246             var itemIndex = 0;
 247             var itemPosition = itemsRange.startPosition;
 248             var items = itemsRange.items;
 249             var insertionIndex = 0;
 250
 251             if (!this._retrievedChildrenRanges.length) {
 252                 if (itemsRange.startPosition > 0) {
 253                     this._retrievedChildrenRanges.push({from: 0, to: 0});
 254                     insertShowMoreButton.call(this, 0, itemsRange.startPosition, insertionIndex++);
 255                 }
 256                 this._retrievedChildrenRanges.push({from: itemsRange.startPosition, to: itemsRange.endPosition});
 257                 for (var i = 0, l = items.length; i < l; ++i)
 258                     insertRetrievedChild.call(this, items[i], insertionIndex++);
 259                 if (itemsRange.endPosition < itemsRange.totalLength)
 260                     insertShowMoreButton.call(this, itemsRange.endPosition, itemsRange.totalLength, insertionIndex++);
 261             } else {
 262                 var rangeIndex = 0;
 263                 var found = false;
 264                 var range;
 265                 while (rangeIndex < this._retrievedChildrenRanges.length) {
 266                     range = this._retrievedChildrenRanges[rangeIndex];
 267                     if (range.to >= itemPosition) {
 268                         found = true;
 269                         break;
 270                     }
 271                     insertionIndex += range.to - range.from;
 272                     // Skip the button if there is one.
 273                     if (range.to < itemsRange.totalLength)
 274                         insertionIndex += 1;
 275                     ++rangeIndex;
 276                 }
 277
 278                 if (!found || itemsRange.startPosition < range.from) {
 279                     // Update previous button.
 280                     this.children[insertionIndex - 1].setEndPosition(itemsRange.startPosition);
 281                     insertShowMoreButton.call(this, itemsRange.startPosition, found ? range.from : itemsRange.totalLength, insertionIndex);
 282                     range = {from: itemsRange.startPosition, to: itemsRange.startPosition};
 283                     if (!found)
 284                         rangeIndex = this._retrievedChildrenRanges.length;
 285                     this._retrievedChildrenRanges.splice(rangeIndex, 0, range);
 286                 } else {
 287                     insertionIndex += itemPosition - range.from;
 288                 }
 289                 // At this point insertionIndex is always an index before button or between nodes.
 290                 // Also it is always true here that range.from <= itemPosition <= range.to
 291
 292                 // Stretch the range right bound to include all new items.
 293                 while (range.to < itemsRange.endPosition) {
 294                     // Skip already added nodes.
 295                     var skipCount = range.to - itemPosition;
 296                     insertionIndex += skipCount;
 297                     itemIndex += skipCount;
 298                     itemPosition = range.to;
 299
 300                     // We're at the position before button: ...<?node>x<button>
 301                     var nextRange = this._retrievedChildrenRanges[rangeIndex + 1];
 302                     var newEndOfRange = nextRange ? nextRange.from : itemsRange.totalLength;
 303                     if (newEndOfRange > itemsRange.endPosition)
 304                         newEndOfRange = itemsRange.endPosition;
 305                     while (itemPosition < newEndOfRange) {
 306                         insertRetrievedChild.call(this, items[itemIndex++], insertionIndex++);
 307                         ++itemPosition;
 308                     }
 309                     // Merge with the next range.
 310                     if (nextRange && newEndOfRange === nextRange.from) {
 311                         range.to = nextRange.to;
 312                         // Remove "show next" button if there is one.
 313                         this.removeChild(this.children[insertionIndex]);
 314                         this._retrievedChildrenRanges.splice(rangeIndex + 1, 1);
 315                     } else {
 316                         range.to = newEndOfRange;
 317                         // Remove or update next button.
 318                         if (newEndOfRange === itemsRange.totalLength)
 319                             this.removeChild(this.children[insertionIndex]);
 320                         else
 321                             this.children[insertionIndex].setStartPosition(itemsRange.endPosition);
 322                     }
 323                 }
 324             }
 325
 326             // TODO: fix this.
 327             this._instanceCount += items.length;
 328             if (firstNotSerializedPosition < toPosition) {
 329                 serializeNextChunk.call(this);
 330                 return;
 331             }
 332
 333             if (afterPopulate)
 334                 afterPopulate();
 335             this.dispatchEventToListeners(WebInspector.HeapSnapshotGridNode.Events.PopulateComplete);
 336         }
 337         serializeNextChunk.call(this);
 338     },
 339
 340     _saveChildren: function()
 341     {
 342         this._savedChildren = null;
 343         for (var i = 0, childrenCount = this.children.length; i < childrenCount; ++i) {
 344             var child = this.children[i];
 345             if (!child.expanded)
 346                 continue;
 347             if (!this._savedChildren)
 348                 this._savedChildren = {};
 349             this._savedChildren[this._childHashForNode(child)] = child;
 350         }
 351     },
 352
 353     sort: function()
 354     {
 355         this._dataGrid.recursiveSortingEnter();
 356
 357         /**
 358          * @this {WebInspector.HeapSnapshotGridNode}
 359          */
 360         function afterSort()
 361         {
 362             this._saveChildren();
 363             this.removeChildren();
 364             this._retrievedChildrenRanges = [];
 365
 366             /**
 367              * @this {WebInspector.HeapSnapshotGridNode}
 368              */
 369             function afterPopulate()
 370             {
 371                 for (var i = 0, l = this.children.length; i < l; ++i) {
 372                     var child = this.children[i];
 373                     if (child.expanded)
 374                         child.sort();
 375                 }
 376                 this._dataGrid.recursiveSortingLeave();
 377             }
 378             var instanceCount = this._instanceCount;
 379             this._instanceCount = 0;
 380             this._populateChildren(0, instanceCount, afterPopulate.bind(this));
 381         }
 382
 383         this._provider().sortAndRewind(this.comparator(), afterSort.bind(this));
 384     },
 385
 386     __proto__: WebInspector.DataGridNode.prototype
 387 }
 388
 389
 390 /**
 391  * @constructor
 392  * @extends {WebInspector.HeapSnapshotGridNode}
 393  * @param {!WebInspector.HeapSnapshotSortableDataGrid} tree
 394  */
 395 WebInspector.HeapSnapshotGenericObjectNode = function(tree, node)
 396 {
 397     this.snapshotNodeIndex = 0;
 398     WebInspector.HeapSnapshotGridNode.call(this, tree, false);
 399     // node is null for DataGrid root nodes.
 400     if (!node)
 401         return;
 402     this._name = node.name;
 403     this._type = node.type;
 404     this._distance = node.distance;
 405     this._shallowSize = node.selfSize;
 406     this._retainedSize = node.retainedSize;
 407     this.snapshotNodeId = node.id;
 408     this.snapshotNodeIndex = node.nodeIndex;
 409     if (this._type === "string")
 410         this._reachableFromWindow = true;
 411     else if (this._type === "object" && this._name.startsWith("Window")) {
 412         this._name = this.shortenWindowURL(this._name, false);
 413         this._reachableFromWindow = true;
 414     } else if (node.canBeQueried)
 415         this._reachableFromWindow = true;
 416     if (node.detachedDOMTreeNode)
 417         this.detachedDOMTreeNode = true;
 418 };
 419
 420 WebInspector.HeapSnapshotGenericObjectNode.prototype = {
 421     /**
 422      * @param {string} columnIdentifier
 423      * @return {!Element}
 424      */
 425     createCell: function(columnIdentifier)
 426     {
 427         var cell = columnIdentifier !== "object" ? this._createValueCell(columnIdentifier) : this._createObjectCell();
 428         if (this._searchMatched)
 429             cell.classList.add("highlight");
 430         return cell;
 431     },
 432
 433     _createObjectCell: function()
 434     {
 435         var cell = document.createElement("td");
 436         cell.className = "object-column";
 437         var div = document.createElement("div");
 438         div.className = "source-code event-properties";
 439         div.style.overflow = "visible";
 440
 441         var data = this.data["object"];
 442         if (this._prefixObjectCell)
 443             this._prefixObjectCell(div, data);
 444
 445         var valueSpan = document.createElement("span");
 446         valueSpan.className = "value console-formatted-" + data.valueStyle;
 447         valueSpan.textContent = data.value;
 448         div.appendChild(valueSpan);
 449
 450         var idSpan = document.createElement("span");
 451         idSpan.className = "console-formatted-id";
 452         idSpan.textContent = " @" + data["nodeId"];
 453         div.appendChild(idSpan);
 454
 455         if (this._postfixObjectCell)
 456             this._postfixObjectCell(div, data);
 457
 458         cell.appendChild(div);
 459         cell.classList.add("disclosure");
 460         if (this.depth)
 461             cell.style.setProperty("padding-left", (this.depth * this.dataGrid.indentWidth) + "px");
 462         cell.heapSnapshotNode = this;
 463         return cell;
 464     },
 465
 466     get data()
 467     {
 468         var data = this._emptyData();
 469
 470         var value = this._name;
 471         var valueStyle = "object";
 472         switch (this._type) {
 473         case "concatenated string":
 474         case "string":
 475             value = "\"" + value + "\"";
 476             valueStyle = "string";
 477             break;
 478         case "regexp":
 479             value = "/" + value + "/";
 480             valueStyle = "string";
 481             break;
 482         case "closure":
 483             value = "function" + (value ? " " : "") + value + "()";
 484             valueStyle = "function";
 485             break;
 486         case "number":
 487             valueStyle = "number";
 488             break;
 489         case "hidden":
 490             valueStyle = "null";
 491             break;
 492         case "array":
 493             if (!value)
 494                 value = "[]";
 495             else
 496                 value += "[]";
 497             break;
 498         };
 499         if (this._reachableFromWindow)
 500             valueStyle += " highlight";
 501         if (value === "Object")
 502             value = "";
 503         if (this.detachedDOMTreeNode)
 504             valueStyle += " detached-dom-tree-node";
 505         data["object"] = { valueStyle: valueStyle, value: value, nodeId: this.snapshotNodeId };
 506
 507         data["distance"] =  this._distance;
 508         data["shallowSize"] = Number.withThousandsSeparator(this._shallowSize);
 509         data["retainedSize"] = Number.withThousandsSeparator(this._retainedSize);
 510         data["shallowSize-percent"] = this._toPercentString(this._shallowSizePercent);
 511         data["retainedSize-percent"] = this._toPercentString(this._retainedSizePercent);
 512
 513         return this._enhanceData ? this._enhanceData(data) : data;
 514     },
 515
 516     queryObjectContent: function(callback, objectGroupName)
 517     {
 518         /**
 519          * @param {?Protocol.Error} error
 520          * @param {!RuntimeAgent.RemoteObject} object
 521          */
 522         function formatResult(error, object)
 523         {
 524             if (!error && object.type)
 525                 callback(WebInspector.RemoteObject.fromPayload(object), !!error);
 526             else
 527                 callback(WebInspector.RemoteObject.fromPrimitiveValue(WebInspector.UIString("Preview is not available")));
 528         }
 529
 530         if (this._type === "string")
 531             callback(WebInspector.RemoteObject.fromPrimitiveValue(this._name));
 532         else
 533             HeapProfilerAgent.getObjectByHeapObjectId(String(this.snapshotNodeId), objectGroupName, formatResult);
 534     },
 535
 536     get _retainedSizePercent()
 537     {
 538         return this._retainedSize / this.dataGrid.snapshot.totalSize * 100.0;
 539     },
 540
 541     get _shallowSizePercent()
 542     {
 543         return this._shallowSize / this.dataGrid.snapshot.totalSize * 100.0;
 544     },
 545
 546     updateHasChildren: function()
 547     {
 548         /**
 549          * @this {WebInspector.HeapSnapshotGenericObjectNode}
 550          */
 551         function isEmptyCallback(isEmpty)
 552         {
 553             this.hasChildren = !isEmpty;
 554         }
 555         this._provider().isEmpty(isEmptyCallback.bind(this));
 556     },
 557
 558     /**
 559      * @param {string} fullName
 560      * @param {boolean} hasObjectId
 561      * @return {string}
 562      */
 563     shortenWindowURL: function(fullName, hasObjectId)
 564     {
 565         var startPos = fullName.indexOf("/");
 566         var endPos = hasObjectId ? fullName.indexOf("@") : fullName.length;
 567         if (startPos !== -1 && endPos !== -1) {
 568             var fullURL = fullName.substring(startPos + 1, endPos).trimLeft();
 569             var url = fullURL.trimURL();
 570             if (url.length > 40)
 571                 url = url.trimMiddle(40);
 572             return fullName.substr(0, startPos + 2) + url + fullName.substr(endPos);
 573         } else
 574             return fullName;
 575     },
 576
 577     __proto__: WebInspector.HeapSnapshotGridNode.prototype
 578 }
 579
 580 /**
 581  * @constructor
 582  * @extends {WebInspector.HeapSnapshotGenericObjectNode}
 583  * @param {!WebInspector.HeapSnapshotSortableDataGrid} tree
 584  * @param {boolean} isFromBaseSnapshot
 585  */
 586 WebInspector.HeapSnapshotObjectNode = function(tree, isFromBaseSnapshot, edge, parentGridNode)
 587 {
 588     WebInspector.HeapSnapshotGenericObjectNode.call(this, tree, edge.node);
 589     this._referenceName = edge.name;
 590     this._referenceType = edge.type;
 591     this._distance = edge.distance;
 592     this.showRetainingEdges = tree.showRetainingEdges;
 593     this._isFromBaseSnapshot = isFromBaseSnapshot;
 594
 595     this._parentGridNode = parentGridNode;
 596     this._cycledWithAncestorGridNode = this._findAncestorWithSameSnapshotNodeId();
 597     if (!this._cycledWithAncestorGridNode)
 598         this.updateHasChildren();
 599 }
 600
 601 WebInspector.HeapSnapshotObjectNode.prototype = {
 602     /**
 603      * @return {!WebInspector.HeapSnapshotProviderProxy}
 604      */
 605     createProvider: function()
 606     {
 607         var tree = this._dataGrid;
 608         var showHiddenData = WebInspector.settings.showAdvancedHeapSnapshotProperties.get();
 609         var snapshot = this._isFromBaseSnapshot ? tree.baseSnapshot : tree.snapshot;
 610         if (this.showRetainingEdges)
 611             return snapshot.createRetainingEdgesProvider(this.snapshotNodeIndex, showHiddenData);
 612         else
 613             return snapshot.createEdgesProvider(this.snapshotNodeIndex, showHiddenData);
 614     },
 615
 616     _findAncestorWithSameSnapshotNodeId: function()
 617     {
 618         var ancestor = this._parentGridNode;
 619         while (ancestor) {
 620             if (ancestor.snapshotNodeId === this.snapshotNodeId)
 621                 return ancestor;
 622             ancestor = ancestor._parentGridNode;
 623         }
 624         return null;
 625     },
 626
 627     _createChildNode: function(item)
 628     {
 629         return new WebInspector.HeapSnapshotObjectNode(this._dataGrid, this._isFromBaseSnapshot, item, this);
 630     },
 631
 632     _childHashForEntity: function(edge)
 633     {
 634         var prefix = this.showRetainingEdges ? edge.node.id + "#" : "";
 635         return prefix + edge.type + "#" + edge.name;
 636     },
 637
 638     _childHashForNode: function(childNode)
 639     {
 640         var prefix = this.showRetainingEdges ? childNode.snapshotNodeId + "#" : "";
 641         return prefix + childNode._referenceType + "#" + childNode._referenceName;
 642     },
 643
 644     /**
 645      * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
 646      */
 647     comparator: function()
 648     {
 649         var sortAscending = this._dataGrid.isSortOrderAscending();
 650         var sortColumnIdentifier = this._dataGrid.sortColumnIdentifier();
 651         var sortFields = {
 652             object: ["!edgeName", sortAscending, "retainedSize", false],
 653             count: ["!edgeName", true, "retainedSize", false],
 654             shallowSize: ["selfSize", sortAscending, "!edgeName", true],
 655             retainedSize: ["retainedSize", sortAscending, "!edgeName", true],
 656             distance: ["distance", sortAscending, "_name", true]
 657         }[sortColumnIdentifier] || ["!edgeName", true, "retainedSize", false];
 658         return WebInspector.HeapSnapshotGridNode.createComparator(sortFields);
 659     },
 660
 661     _emptyData: function()
 662     {
 663         return { count: "", addedCount: "", removedCount: "", countDelta: "", addedSize: "", removedSize: "", sizeDelta: "" };
 664     },
 665
 666     _enhanceData: function(data)
 667     {
 668         var name = this._referenceName;
 669         if (name === "") name = "(empty)";
 670         var nameClass = "name";
 671         switch (this._referenceType) {
 672         case "context":
 673             nameClass = "console-formatted-number";
 674             break;
 675         case "internal":
 676         case "hidden":
 677         case "weak":
 678             nameClass = "console-formatted-null";
 679             break;
 680         case "element":
 681             name = "[" + name + "]";
 682             break;
 683         }
 684         data["object"].nameClass = nameClass;
 685         data["object"].name = name;
 686         data["distance"] = this._distance;
 687         return data;
 688     },
 689
 690     _prefixObjectCell: function(div, data)
 691     {
 692         if (this._cycledWithAncestorGridNode)
 693             div.className += " cycled-ancessor-node";
 694
 695         var nameSpan = document.createElement("span");
 696         nameSpan.className = data.nameClass;
 697         nameSpan.textContent = data.name;
 698         div.appendChild(nameSpan);
 699
 700         var separatorSpan = document.createElement("span");
 701         separatorSpan.className = "grayed";
 702         separatorSpan.textContent = this.showRetainingEdges ? " in " : " :: ";
 703         div.appendChild(separatorSpan);
 704     },
 705
 706     __proto__: WebInspector.HeapSnapshotGenericObjectNode.prototype
 707 }
 708
 709 /**
 710  * @constructor
 711  * @extends {WebInspector.HeapSnapshotGenericObjectNode}
 712  */
 713 WebInspector.HeapSnapshotInstanceNode = function(tree, baseSnapshot, snapshot, node)
 714 {
 715     WebInspector.HeapSnapshotGenericObjectNode.call(this, tree, node);
 716     this._baseSnapshotOrSnapshot = baseSnapshot || snapshot;
 717     this._isDeletedNode = !!baseSnapshot;
 718     this.updateHasChildren();
 719 };
 720
 721 WebInspector.HeapSnapshotInstanceNode.prototype = {
 722     /**
 723      * @return {!WebInspector.HeapSnapshotProviderProxy}
 724      */
 725     createProvider: function()
 726     {
 727         var showHiddenData = WebInspector.settings.showAdvancedHeapSnapshotProperties.get();
 728         return this._baseSnapshotOrSnapshot.createEdgesProvider(
 729             this.snapshotNodeIndex,
 730             showHiddenData);
 731     },
 732
 733     _createChildNode: function(item)
 734     {
 735         return new WebInspector.HeapSnapshotObjectNode(this._dataGrid, this._isDeletedNode, item, null);
 736     },
 737
 738     _childHashForEntity: function(edge)
 739     {
 740         return edge.type + "#" + edge.name;
 741     },
 742
 743     _childHashForNode: function(childNode)
 744     {
 745         return childNode._referenceType + "#" + childNode._referenceName;
 746     },
 747
 748     /**
 749      * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
 750      */
 751     comparator: function()
 752     {
 753         var sortAscending = this._dataGrid.isSortOrderAscending();
 754         var sortColumnIdentifier = this._dataGrid.sortColumnIdentifier();
 755         var sortFields = {
 756             object: ["!edgeName", sortAscending, "retainedSize", false],
 757             distance: ["distance", sortAscending, "retainedSize", false],
 758             count: ["!edgeName", true, "retainedSize", false],
 759             addedSize: ["selfSize", sortAscending, "!edgeName", true],
 760             removedSize: ["selfSize", sortAscending, "!edgeName", true],
 761             shallowSize: ["selfSize", sortAscending, "!edgeName", true],
 762             retainedSize: ["retainedSize", sortAscending, "!edgeName", true]
 763         }[sortColumnIdentifier] || ["!edgeName", true, "retainedSize", false];
 764         return WebInspector.HeapSnapshotGridNode.createComparator(sortFields);
 765     },
 766
 767     _emptyData: function()
 768     {
 769         return {count: "", countDelta: "", sizeDelta: ""};
 770     },
 771
 772     _enhanceData: function(data)
 773     {
 774         if (this._isDeletedNode) {
 775             data["addedCount"] = "";
 776             data["addedSize"] = "";
 777             data["removedCount"] = "\u2022";
 778             data["removedSize"] = Number.withThousandsSeparator(this._shallowSize);
 779         } else {
 780             data["addedCount"] = "\u2022";
 781             data["addedSize"] = Number.withThousandsSeparator(this._shallowSize);
 782             data["removedCount"] = "";
 783             data["removedSize"] = "";
 784         }
 785         return data;
 786     },
 787
 788     get isDeletedNode()
 789     {
 790         return this._isDeletedNode;
 791     },
 792
 793     __proto__: WebInspector.HeapSnapshotGenericObjectNode.prototype
 794 }
 795
 796 /**
 797  * @constructor
 798  * @param {string} className
 799  * @param {!WebInspector.HeapSnapshotCommon.Aggregate} aggregate
 800  * @param {string} aggregatesKey
 801  * @extends {WebInspector.HeapSnapshotGridNode}
 802  */
 803 WebInspector.HeapSnapshotConstructorNode = function(tree, className, aggregate, aggregatesKey)
 804 {
 805     WebInspector.HeapSnapshotGridNode.call(this, tree, aggregate.count > 0);
 806     this._name = className;
 807     this._aggregatesKey = aggregatesKey;
 808     this._distance = aggregate.distance;
 809     this._count = aggregate.count;
 810     this._shallowSize = aggregate.self;
 811     this._retainedSize = aggregate.maxRet;
 812 }
 813
 814 WebInspector.HeapSnapshotConstructorNode.prototype = {
 815     /**
 816      * @override
 817      * @return {!WebInspector.HeapSnapshotProviderProxy}
 818      */
 819     createProvider: function()
 820     {
 821         return this._dataGrid.snapshot.createNodesProviderForClass(this._name, this._aggregatesKey)
 822     },
 823
 824     /**
 825      * @param {number} snapshotObjectId
 826      * @param {function(boolean)} callback
 827      */
 828     revealNodeBySnapshotObjectId: function(snapshotObjectId, callback)
 829     {
 830         /**
 831          * @this {WebInspector.HeapSnapshotConstructorNode}
 832          */
 833         function didExpand()
 834         {
 835             this._provider().nodePosition(snapshotObjectId, didGetNodePosition.bind(this));
 836         }
 837
 838         /**
 839          * @this {WebInspector.HeapSnapshotConstructorNode}
 840          */
 841         function didGetNodePosition(nodePosition)
 842         {
 843             if (nodePosition === -1) {
 844                 this.collapse();
 845                 callback(false);
 846             } else {
 847                 this._populateChildren(nodePosition, null, didPopulateChildren.bind(this, nodePosition));
 848             }
 849         }
 850
 851         /**
 852          * @this {WebInspector.HeapSnapshotConstructorNode}
 853          */
 854         function didPopulateChildren(nodePosition)
 855         {
 856             var indexOfFirsChildInRange = 0;
 857             for (var i = 0; i < this._retrievedChildrenRanges.length; i++) {
 858                var range = this._retrievedChildrenRanges[i];
 859                if (range.from <= nodePosition && nodePosition < range.to) {
 860                    var childIndex = indexOfFirsChildInRange + nodePosition - range.from;
 861                    var instanceNode = this.children[childIndex];
 862                    this._dataGrid.highlightNode(/** @type {!WebInspector.HeapSnapshotGridNode} */ (instanceNode));
 863                    callback(true);
 864                    return;
 865                }
 866                indexOfFirsChildInRange += range.to - range.from + 1;
 867             }
 868             callback(false);
 869         }
 870
 871         this.expandWithoutPopulate(didExpand.bind(this));
 872     },
 873
 874     /**
 875      * @param {string} columnIdentifier
 876      * @return {!Element}
 877      */
 878     createCell: function(columnIdentifier)
 879     {
 880         var cell = columnIdentifier !== "object" ? this._createValueCell(columnIdentifier) : WebInspector.HeapSnapshotGridNode.prototype.createCell.call(this, columnIdentifier);
 881         if (this._searchMatched)
 882             cell.classList.add("highlight");
 883         return cell;
 884     },
 885
 886     _createChildNode: function(item)
 887     {
 888         return new WebInspector.HeapSnapshotInstanceNode(this._dataGrid, null, this._dataGrid.snapshot, item);
 889     },
 890
 891     /**
 892      * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
 893      */
 894     comparator: function()
 895     {
 896         var sortAscending = this._dataGrid.isSortOrderAscending();
 897         var sortColumnIdentifier = this._dataGrid.sortColumnIdentifier();
 898         var sortFields = {
 899             object: ["id", sortAscending, "retainedSize", false],
 900             distance: ["distance", sortAscending, "retainedSize", false],
 901             count: ["id", true, "retainedSize", false],
 902             shallowSize: ["selfSize", sortAscending, "id", true],
 903             retainedSize: ["retainedSize", sortAscending, "id", true]
 904         }[sortColumnIdentifier];
 905         return WebInspector.HeapSnapshotGridNode.createComparator(sortFields);
 906     },
 907
 908     _childHashForEntity: function(node)
 909     {
 910         return node.id;
 911     },
 912
 913     _childHashForNode: function(childNode)
 914     {
 915         return childNode.snapshotNodeId;
 916     },
 917
 918     get data()
 919     {
 920         var data = { object: this._name };
 921         data["count"] =  Number.withThousandsSeparator(this._count);
 922         data["distance"] =  this._distance;
 923         data["shallowSize"] = Number.withThousandsSeparator(this._shallowSize);
 924         data["retainedSize"] = Number.withThousandsSeparator(this._retainedSize);
 925         data["count-percent"] =  this._toPercentString(this._countPercent);
 926         data["shallowSize-percent"] = this._toPercentString(this._shallowSizePercent);
 927         data["retainedSize-percent"] = this._toPercentString(this._retainedSizePercent);
 928         return data;
 929     },
 930
 931     get _countPercent()
 932     {
 933         return this._count / this.dataGrid.snapshot.nodeCount * 100.0;
 934     },
 935
 936     get _retainedSizePercent()
 937     {
 938         return this._retainedSize / this.dataGrid.snapshot.totalSize * 100.0;
 939     },
 940
 941     get _shallowSizePercent()
 942     {
 943         return this._shallowSize / this.dataGrid.snapshot.totalSize * 100.0;
 944     },
 945
 946     __proto__: WebInspector.HeapSnapshotGridNode.prototype
 947 }
 948
 949
 950 /**
 951  * @constructor
 952  * @extends {WebInspector.HeapSnapshotProviderProxy}
 953  * @param {!WebInspector.HeapSnapshotProviderProxy} addedNodesProvider
 954  * @param {!WebInspector.HeapSnapshotProviderProxy} deletedNodesProvider
 955  */
 956 WebInspector.HeapSnapshotDiffNodesProvider = function(addedNodesProvider, deletedNodesProvider, addedCount, removedCount)
 957 {
 958     this._addedNodesProvider = addedNodesProvider;
 959     this._deletedNodesProvider = deletedNodesProvider;
 960     this._addedCount = addedCount;
 961     this._removedCount = removedCount;
 962 }
 963
 964 WebInspector.HeapSnapshotDiffNodesProvider.prototype = {
 965     dispose: function()
 966     {
 967         this._addedNodesProvider.dispose();
 968         this._deletedNodesProvider.dispose();
 969     },
 970
 971     isEmpty: function(callback)
 972     {
 973         callback(false);
 974     },
 975
 976     /**
 977      * @param {number} beginPosition
 978      * @param {number} endPosition
 979      * @param {!function(!WebInspector.HeapSnapshotCommon.ItemsRange)} callback
 980      */
 981     serializeItemsRange: function(beginPosition, endPosition, callback)
 982     {
 983         /**
 984          * @param {!WebInspector.HeapSnapshotCommon.ItemsRange} items
 985          * @this {WebInspector.HeapSnapshotDiffNodesProvider}
 986          */
 987         function didReceiveAllItems(items)
 988         {
 989             items.totalLength = this._addedCount + this._removedCount;
 990             callback(items);
 991         }
 992
 993         /**
 994          * @param {!WebInspector.HeapSnapshotCommon.ItemsRange} addedItems
 995          * @param {!WebInspector.HeapSnapshotCommon.ItemsRange} itemsRange
 996          * @this {WebInspector.HeapSnapshotDiffNodesProvider}
 997          */
 998         function didReceiveDeletedItems(addedItems, itemsRange)
 999         {
1000             var items = itemsRange.items;
1001             if (!addedItems.items.length)
1002                 addedItems.startPosition = this._addedCount + itemsRange.startPosition;
1003             for (var i = 0; i < items.length; i++) {
1004                 items[i].isAddedNotRemoved = false;
1005                 addedItems.items.push(items[i]);
1006             }
1007             addedItems.endPosition = this._addedCount + itemsRange.endPosition;
1008             didReceiveAllItems.call(this, addedItems);
1009         }
1010
1011         /**
1012          * @param {!WebInspector.HeapSnapshotCommon.ItemsRange} itemsRange
1013          * @this {WebInspector.HeapSnapshotDiffNodesProvider}
1014          */
1015         function didReceiveAddedItems(itemsRange)
1016         {
1017             var items = itemsRange.items;
1018             for (var i = 0; i < items.length; i++)
1019                 items[i].isAddedNotRemoved = true;
1020             if (itemsRange.endPosition < endPosition)
1021                 return this._deletedNodesProvider.serializeItemsRange(0, endPosition - itemsRange.endPosition, didReceiveDeletedItems.bind(this, itemsRange));
1022
1023             itemsRange.totalLength = this._addedCount + this._removedCount;
1024             didReceiveAllItems.call(this, itemsRange);
1025         }
1026
1027         if (beginPosition < this._addedCount) {
1028             this._addedNodesProvider.serializeItemsRange(beginPosition, endPosition, didReceiveAddedItems.bind(this));
1029         } else {
1030             var emptyRange = new WebInspector.HeapSnapshotCommon.ItemsRange(0, 0, 0, []);
1031             this._deletedNodesProvider.serializeItemsRange(beginPosition - this._addedCount, endPosition - this._addedCount, didReceiveDeletedItems.bind(this, emptyRange));
1032         }
1033     },
1034
1035     sortAndRewind: function(comparator, callback)
1036     {
1037         /**
1038          * @this {WebInspector.HeapSnapshotDiffNodesProvider}
1039          */
1040         function afterSort()
1041         {
1042             this._deletedNodesProvider.sortAndRewind(comparator, callback);
1043         }
1044         this._addedNodesProvider.sortAndRewind(comparator, afterSort.bind(this));
1045     },
1046
1047     __proto__: WebInspector.HeapSnapshotProviderProxy.prototype
1048 };
1049
1050 /**
1051  * @constructor
1052  * @param {string} className
1053  * @param {!WebInspector.HeapSnapshotCommon.DiffForClass} diffForClass
1054  * @extends {WebInspector.HeapSnapshotGridNode}
1055  */
1056 WebInspector.HeapSnapshotDiffNode = function(tree, className, diffForClass)
1057 {
1058     WebInspector.HeapSnapshotGridNode.call(this, tree, true);
1059     this._name = className;
1060
1061     this._addedCount = diffForClass.addedCount;
1062     this._removedCount = diffForClass.removedCount;
1063     this._countDelta = diffForClass.countDelta;
1064     this._addedSize = diffForClass.addedSize;
1065     this._removedSize = diffForClass.removedSize;
1066     this._sizeDelta = diffForClass.sizeDelta;
1067     this._deletedIndexes = diffForClass.deletedIndexes;
1068 }
1069
1070 WebInspector.HeapSnapshotDiffNode.prototype = {
1071     /**
1072      * @override
1073      * @return {!WebInspector.HeapSnapshotDiffNodesProvider}
1074      */
1075     createProvider: function()
1076     {
1077         var tree = this._dataGrid;
1078         return new WebInspector.HeapSnapshotDiffNodesProvider(
1079             tree.snapshot.createAddedNodesProvider(tree.baseSnapshot.uid, this._name),
1080             tree.baseSnapshot.createDeletedNodesProvider(this._deletedIndexes),
1081             this._addedCount,
1082             this._removedCount);
1083     },
1084
1085     _createChildNode: function(item)
1086     {
1087         if (item.isAddedNotRemoved)
1088             return new WebInspector.HeapSnapshotInstanceNode(this._dataGrid, null, this._dataGrid.snapshot, item);
1089         else
1090             return new WebInspector.HeapSnapshotInstanceNode(this._dataGrid, this._dataGrid.baseSnapshot, null, item);
1091     },
1092
1093     _childHashForEntity: function(node)
1094     {
1095         return node.id;
1096     },
1097
1098     _childHashForNode: function(childNode)
1099     {
1100         return childNode.snapshotNodeId;
1101     },
1102
1103     /**
1104      * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
1105      */
1106     comparator: function()
1107     {
1108         var sortAscending = this._dataGrid.isSortOrderAscending();
1109         var sortColumnIdentifier = this._dataGrid.sortColumnIdentifier();
1110         var sortFields = {
1111             object: ["id", sortAscending, "selfSize", false],
1112             addedCount: ["selfSize", sortAscending, "id", true],
1113             removedCount: ["selfSize", sortAscending, "id", true],
1114             countDelta: ["selfSize", sortAscending, "id", true],
1115             addedSize: ["selfSize", sortAscending, "id", true],
1116             removedSize: ["selfSize", sortAscending, "id", true],
1117             sizeDelta: ["selfSize", sortAscending, "id", true]
1118         }[sortColumnIdentifier];
1119         return WebInspector.HeapSnapshotGridNode.createComparator(sortFields);
1120     },
1121
1122     _signForDelta: function(delta)
1123     {
1124         if (delta === 0)
1125             return "";
1126         if (delta > 0)
1127             return "+";
1128         else
1129             return "\u2212";  // Math minus sign, same width as plus.
1130     },
1131
1132     get data()
1133     {
1134         var data = {object: this._name};
1135
1136         data["addedCount"] = Number.withThousandsSeparator(this._addedCount);
1137         data["removedCount"] = Number.withThousandsSeparator(this._removedCount);
1138         data["countDelta"] = this._signForDelta(this._countDelta) + Number.withThousandsSeparator(Math.abs(this._countDelta));
1139         data["addedSize"] = Number.withThousandsSeparator(this._addedSize);
1140         data["removedSize"] = Number.withThousandsSeparator(this._removedSize);
1141         data["sizeDelta"] = this._signForDelta(this._sizeDelta) + Number.withThousandsSeparator(Math.abs(this._sizeDelta));
1142
1143         return data;
1144     },
1145
1146     __proto__: WebInspector.HeapSnapshotGridNode.prototype
1147 }
1148
1149
1150 /**
1151  * @constructor
1152  * @extends {WebInspector.HeapSnapshotGenericObjectNode}
1153  */
1154 WebInspector.HeapSnapshotDominatorObjectNode = function(tree, node)
1155 {
1156     WebInspector.HeapSnapshotGenericObjectNode.call(this, tree, node);
1157     this.updateHasChildren();
1158 };
1159
1160 WebInspector.HeapSnapshotDominatorObjectNode.prototype = {
1161     /**
1162      * @override
1163      * @return {!WebInspector.HeapSnapshotProviderProxy}
1164      */
1165     createProvider: function()
1166     {
1167         return this._dataGrid.snapshot.createNodesProviderForDominator(this.snapshotNodeIndex);
1168     },
1169
1170     /**
1171      * @param {number} snapshotObjectId
1172      * @param {function(?WebInspector.DataGridNode)} callback
1173      */
1174     retrieveChildBySnapshotObjectId: function(snapshotObjectId, callback)
1175     {
1176         /**
1177          * @this {WebInspector.HeapSnapshotDominatorObjectNode}
1178          */
1179         function didExpand()
1180         {
1181             this._provider().nodePosition(snapshotObjectId, didGetNodePosition.bind(this));
1182         }
1183
1184         /**
1185          * @this {WebInspector.HeapSnapshotDominatorObjectNode}
1186          */
1187         function didGetNodePosition(nodePosition)
1188         {
1189             if (nodePosition === -1) {
1190                 this.collapse();
1191                 callback(null);
1192             } else
1193                 this._populateChildren(nodePosition, null, didPopulateChildren.bind(this, nodePosition));
1194         }
1195
1196         /**
1197          * @this {WebInspector.HeapSnapshotDominatorObjectNode}
1198          */
1199         function didPopulateChildren(nodePosition)
1200         {
1201             var child = this.childForPosition(nodePosition);
1202             callback(child);
1203         }
1204
1205         // Make sure hasChildren flag is updated before expanding this node as updateHasChildren response
1206         // may not have been received yet.
1207         this.hasChildren = true;
1208         this.expandWithoutPopulate(didExpand.bind(this));
1209     },
1210
1211     _createChildNode: function(item)
1212     {
1213         return new WebInspector.HeapSnapshotDominatorObjectNode(this._dataGrid, item);
1214     },
1215
1216     _childHashForEntity: function(node)
1217     {
1218         return node.id;
1219     },
1220
1221     _childHashForNode: function(childNode)
1222     {
1223         return childNode.snapshotNodeId;
1224     },
1225
1226     /**
1227      * @return {!WebInspector.HeapSnapshotCommon.ComparatorConfig}
1228      */
1229     comparator: function()
1230     {
1231         var sortAscending = this._dataGrid.isSortOrderAscending();
1232         var sortColumnIdentifier = this._dataGrid.sortColumnIdentifier();
1233         var sortFields = {
1234             object: ["id", sortAscending, "retainedSize", false],
1235             shallowSize: ["selfSize", sortAscending, "id", true],
1236             retainedSize: ["retainedSize", sortAscending, "id", true]
1237         }[sortColumnIdentifier];
1238         return WebInspector.HeapSnapshotGridNode.createComparator(sortFields);
1239     },
1240
1241     _emptyData: function()
1242     {
1243         return {};
1244     },
1245
1246     __proto__: WebInspector.HeapSnapshotGenericObjectNode.prototype
1247 }
1248