src/third_party/WebKit/Source/devtools/front_end/HeapSnapshot.js

   1 /*
   2  * Copyright (C) 2011 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /**
  32  * @interface
  33  */
  34 WebInspector.HeapSnapshotItem = function() { }
  35
  36 WebInspector.HeapSnapshotItem.prototype = {
  37     /**
  38      * @return {number}
  39      */
  40     itemIndex: function() { },
  41
  42     /**
  43      * @return {!Object}
  44      */
  45     serialize: function() { }
  46 };
  47
  48 /**
  49  * @constructor
  50  * @implements {WebInspector.HeapSnapshotItem}
  51  * @param {!WebInspector.HeapSnapshot} snapshot
  52  * @param {number=} edgeIndex
  53  */
  54 WebInspector.HeapSnapshotEdge = function(snapshot, edgeIndex)
  55 {
  56     this._snapshot = snapshot;
  57     this._edges = snapshot._containmentEdges;
  58     this.edgeIndex = edgeIndex || 0;
  59 }
  60
  61 /**
  62  * @constructor
  63  * @param {string} name
  64  * @param {!WebInspector.HeapSnapshotNode.Serialized} node
  65  * @param {number} nodeIndex
  66  * @param {string} type
  67  */
  68 WebInspector.HeapSnapshotEdge.Serialized = function(name, node, nodeIndex, type)
  69 {
  70     this.name = name;
  71     this.node = node;
  72     this.nodeIndex = nodeIndex;
  73     this.type = type;
  74 };
  75
  76 WebInspector.HeapSnapshotEdge.prototype = {
  77     /**
  78      * @return {!WebInspector.HeapSnapshotEdge}
  79      */
  80     clone: function()
  81     {
  82         return new WebInspector.HeapSnapshotEdge(this._snapshot, this.edgeIndex);
  83     },
  84
  85     /**
  86      * @return {boolean}
  87      */
  88     hasStringName: function()
  89     {
  90         throw new Error("Not implemented");
  91     },
  92
  93     /**
  94      * @return {string}
  95      */
  96     name: function()
  97     {
  98         throw new Error("Not implemented");
  99     },
 100
 101     /**
 102      * @return {!WebInspector.HeapSnapshotNode}
 103      */
 104     node: function()
 105     {
 106         return this._snapshot.createNode(this.nodeIndex());
 107     },
 108
 109     /**
 110      * @return {number}
 111      */
 112     nodeIndex: function()
 113     {
 114         return this._edges[this.edgeIndex + this._snapshot._edgeToNodeOffset];
 115     },
 116
 117     /**
 118      * @return {string}
 119      */
 120     toString: function()
 121     {
 122         return "HeapSnapshotEdge: " + this.name();
 123     },
 124
 125     /**
 126      * @return {string}
 127      */
 128     type: function()
 129     {
 130         return this._snapshot._edgeTypes[this._type()];
 131     },
 132
 133     /**
 134      * @override
 135      * @return {number}
 136      */
 137     itemIndex: function()
 138     {
 139         return this.edgeIndex;
 140     },
 141
 142     /**
 143      * @override
 144      * @return {!WebInspector.HeapSnapshotEdge.Serialized}
 145      */
 146     serialize: function()
 147     {
 148         var node = this.node();
 149         return new WebInspector.HeapSnapshotEdge.Serialized(this.name(), node.serialize(), this.nodeIndex(), this.type());
 150     },
 151
 152     _type: function()
 153     {
 154         return this._edges[this.edgeIndex + this._snapshot._edgeTypeOffset];
 155     }
 156 };
 157
 158
 159 /**
 160  * @interface
 161  */
 162 WebInspector.HeapSnapshotItemIterator = function() { }
 163
 164 WebInspector.HeapSnapshotItemIterator.prototype = {
 165     /**
 166      * @return {boolean}
 167      */
 168     hasNext: function() { },
 169
 170     /**
 171      * @return {!WebInspector.HeapSnapshotItem}
 172      */
 173     item: function() { },
 174
 175     next: function() { }
 176 };
 177
 178
 179 /**
 180  * @interface
 181  */
 182 WebInspector.HeapSnapshotItemIndexProvider = function() { }
 183
 184 WebInspector.HeapSnapshotItemIndexProvider.prototype = {
 185     /**
 186      * @param {number} newIndex
 187      * @return {!WebInspector.HeapSnapshotItem}
 188      */
 189     itemForIndex: function(newIndex) { },
 190 };
 191
 192 /**
 193  * @constructor
 194  * @implements {WebInspector.HeapSnapshotItemIndexProvider}
 195  * @param {!WebInspector.HeapSnapshot} snapshot
 196  */
 197 WebInspector.HeapSnapshotNodeIndexProvider = function(snapshot)
 198 {
 199     this._node = snapshot.createNode();
 200 }
 201
 202 WebInspector.HeapSnapshotNodeIndexProvider.prototype = {
 203     /**
 204      * @param {number} index
 205      * @return {!WebInspector.HeapSnapshotNode}
 206      */
 207     itemForIndex: function(index)
 208     {
 209         this._node.nodeIndex = index;
 210         return this._node;
 211     }
 212 };
 213
 214
 215 /**
 216  * @constructor
 217  * @implements {WebInspector.HeapSnapshotItemIndexProvider}
 218  * @param {!WebInspector.HeapSnapshot} snapshot
 219  */
 220 WebInspector.HeapSnapshotEdgeIndexProvider = function(snapshot)
 221 {
 222     this._edge = snapshot.createEdge(0);
 223 }
 224
 225 WebInspector.HeapSnapshotEdgeIndexProvider.prototype = {
 226     /**
 227      * @param {number} index
 228      * @return {!WebInspector.HeapSnapshotEdge}
 229      */
 230     itemForIndex: function(index)
 231     {
 232         this._edge.edgeIndex = index;
 233         return this._edge;
 234     }
 235 };
 236
 237
 238 /**
 239  * @constructor
 240  * @implements {WebInspector.HeapSnapshotItemIndexProvider}
 241  * @param {!WebInspector.HeapSnapshot} snapshot
 242  */
 243 WebInspector.HeapSnapshotRetainerEdgeIndexProvider = function(snapshot)
 244 {
 245     this._retainerEdge = snapshot.createRetainingEdge(0);
 246 }
 247
 248 WebInspector.HeapSnapshotRetainerEdgeIndexProvider.prototype = {
 249     /**
 250      * @param {number} index
 251      * @return {!WebInspector.HeapSnapshotRetainerEdge}
 252      */
 253     itemForIndex: function(index)
 254     {
 255         this._retainerEdge.setRetainerIndex(index);
 256         return this._retainerEdge;
 257     }
 258 };
 259
 260
 261 /**
 262  * @constructor
 263  * @implements {WebInspector.HeapSnapshotItemIterator}
 264  * @param {!WebInspector.HeapSnapshotNode} node
 265  */
 266 WebInspector.HeapSnapshotEdgeIterator = function(node)
 267 {
 268     this._sourceNode = node;
 269     this.edge = node._snapshot.createEdge(node._edgeIndexesStart());
 270 }
 271
 272 WebInspector.HeapSnapshotEdgeIterator.prototype = {
 273     /**
 274      * @return {boolean}
 275      */
 276     hasNext: function()
 277     {
 278         return this.edge.edgeIndex < this._sourceNode._edgeIndexesEnd();
 279     },
 280
 281     /**
 282      * @return {!WebInspector.HeapSnapshotEdge}
 283      */
 284     item: function()
 285     {
 286         return this.edge;
 287     },
 288
 289     next: function()
 290     {
 291         this.edge.edgeIndex += this.edge._snapshot._edgeFieldsCount;
 292     }
 293 };
 294
 295 /**
 296  * @constructor
 297  * @implements {WebInspector.HeapSnapshotItem}
 298  * @param {!WebInspector.HeapSnapshot} snapshot
 299  * @param {number} retainerIndex
 300  */
 301 WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainerIndex)
 302 {
 303     this._snapshot = snapshot;
 304     this.setRetainerIndex(retainerIndex);
 305 }
 306
 307 /**
 308  * @constructor
 309  * @param {string} name
 310  * @param {!WebInspector.HeapSnapshotNode.Serialized} node
 311  * @param {number} nodeIndex
 312  * @param {string} type
 313  */
 314 WebInspector.HeapSnapshotRetainerEdge.Serialized = function(name, node, nodeIndex, type) {
 315     this.name = name;
 316     this.node = node;
 317     this.nodeIndex = nodeIndex;
 318     this.type = type;
 319 }
 320
 321 WebInspector.HeapSnapshotRetainerEdge.prototype = {
 322     /**
 323      * @return {!WebInspector.HeapSnapshotRetainerEdge}
 324      */
 325     clone: function()
 326     {
 327         return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this.retainerIndex());
 328     },
 329
 330     /**
 331      * @return {boolean}
 332      */
 333     hasStringName: function()
 334     {
 335         return this._edge().hasStringName();
 336     },
 337
 338     /**
 339      * @return {string}
 340      */
 341     name: function()
 342     {
 343         return this._edge().name();
 344     },
 345
 346     /**
 347      * @return {!WebInspector.HeapSnapshotNode}
 348      */
 349     node: function()
 350     {
 351         return this._node();
 352     },
 353
 354     /**
 355      * @return {number}
 356      */
 357     nodeIndex: function()
 358     {
 359         return this._retainingNodeIndex;
 360     },
 361
 362     /**
 363      * @return {number}
 364      */
 365     retainerIndex: function()
 366     {
 367         return this._retainerIndex;
 368     },
 369
 370     /**
 371      * @param {number} retainerIndex
 372      */
 373     setRetainerIndex: function(retainerIndex)
 374     {
 375         if (retainerIndex === this._retainerIndex)
 376             return;
 377         this._retainerIndex = retainerIndex;
 378         this._globalEdgeIndex = this._snapshot._retainingEdges[retainerIndex];
 379         this._retainingNodeIndex = this._snapshot._retainingNodes[retainerIndex];
 380         this._edgeInstance = null;
 381         this._nodeInstance = null;
 382     },
 383
 384     /**
 385      * @param {number} edgeIndex
 386      */
 387     set edgeIndex(edgeIndex)
 388     {
 389         this.setRetainerIndex(edgeIndex);
 390     },
 391
 392     _node: function()
 393     {
 394         if (!this._nodeInstance)
 395             this._nodeInstance = this._snapshot.createNode(this._retainingNodeIndex);
 396         return this._nodeInstance;
 397     },
 398
 399     _edge: function()
 400     {
 401         if (!this._edgeInstance)
 402             this._edgeInstance = this._snapshot.createEdge(this._globalEdgeIndex);
 403         return this._edgeInstance;
 404     },
 405
 406     /**
 407      * @return {string}
 408      */
 409     toString: function()
 410     {
 411         return this._edge().toString();
 412     },
 413
 414     /**
 415      * @override
 416      * @return {number}
 417      */
 418     itemIndex: function()
 419     {
 420         return this._retainerIndex;
 421     },
 422
 423     /**
 424      * @override
 425      * @return {!WebInspector.HeapSnapshotRetainerEdge.Serialized}
 426      */
 427     serialize: function()
 428     {
 429         var node = this.node();
 430         return new WebInspector.HeapSnapshotRetainerEdge.Serialized(this.name(), node.serialize(), this.nodeIndex(), this.type());
 431     },
 432
 433     /**
 434      * @return {string}
 435      */
 436     type: function()
 437     {
 438         return this._edge().type();
 439     }
 440 }
 441
 442 /**
 443  * @constructor
 444  * @implements {WebInspector.HeapSnapshotItemIterator}
 445  * @param {!WebInspector.HeapSnapshotNode} retainedNode
 446  */
 447 WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainedNode)
 448 {
 449     var snapshot = retainedNode._snapshot;
 450     var retainedNodeOrdinal = retainedNode._ordinal();
 451     var retainerIndex = snapshot._firstRetainerIndex[retainedNodeOrdinal];
 452     this._retainersEnd = snapshot._firstRetainerIndex[retainedNodeOrdinal + 1];
 453     this.retainer = snapshot.createRetainingEdge(retainerIndex);
 454 }
 455
 456 WebInspector.HeapSnapshotRetainerEdgeIterator.prototype = {
 457     /**
 458      * @return {boolean}
 459      */
 460     hasNext: function()
 461     {
 462         return this.retainer.retainerIndex() < this._retainersEnd;
 463     },
 464
 465     /**
 466      * @return {!WebInspector.HeapSnapshotRetainerEdge}
 467      */
 468     item: function()
 469     {
 470         return this.retainer;
 471     },
 472
 473     next: function()
 474     {
 475         this.retainer.setRetainerIndex(this.retainer.retainerIndex() + 1);
 476     }
 477 };
 478
 479 /**
 480  * @constructor
 481  * @implements {WebInspector.HeapSnapshotItem}
 482  * @param {!WebInspector.HeapSnapshot} snapshot
 483  * @param {number=} nodeIndex
 484  */
 485 WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex)
 486 {
 487     this._snapshot = snapshot;
 488     this.nodeIndex = nodeIndex || 0;
 489 }
 490
 491 /**
 492  * @constructor
 493  * @param {string} id
 494  * @param {string} name
 495  * @param {number} distance
 496  * @param {number|undefined} nodeIndex
 497  * @param {number} retainedSize
 498  * @param {number} selfSize
 499  * @param {string} type
 500  */
 501 WebInspector.HeapSnapshotNode.Serialized = function(id, name, distance, nodeIndex, retainedSize, selfSize, type) {
 502     this.id = id;
 503     this.name = name;
 504     this.distance = distance;
 505     this.nodeIndex = nodeIndex;
 506     this.retainedSize = retainedSize;
 507     this.selfSize = selfSize;
 508     this.type = type;
 509 }
 510
 511 WebInspector.HeapSnapshotNode.prototype = {
 512     /**
 513      * @return {number}
 514      */
 515     distance: function()
 516     {
 517         return this._snapshot._nodeDistances[this.nodeIndex / this._snapshot._nodeFieldCount];
 518     },
 519
 520     /**
 521      * @return {string}
 522      */
 523     className: function()
 524     {
 525         throw new Error("Not implemented");
 526     },
 527
 528     /**
 529      * @return {number}
 530      */
 531     classIndex: function()
 532     {
 533         throw new Error("Not implemented");
 534     },
 535
 536     /**
 537      * @return {number}
 538      */
 539     dominatorIndex: function()
 540     {
 541         var nodeFieldCount = this._snapshot._nodeFieldCount;
 542         return this._snapshot._dominatorsTree[this.nodeIndex / this._snapshot._nodeFieldCount] * nodeFieldCount;
 543     },
 544
 545     /**
 546      * @return {!WebInspector.HeapSnapshotEdgeIterator}
 547      */
 548     edges: function()
 549     {
 550         return new WebInspector.HeapSnapshotEdgeIterator(this);
 551     },
 552
 553     /**
 554      * @return {number}
 555      */
 556     edgesCount: function()
 557     {
 558         return (this._edgeIndexesEnd() - this._edgeIndexesStart()) / this._snapshot._edgeFieldsCount;
 559     },
 560
 561     id: function()
 562     {
 563         throw new Error("Not implemented");
 564     },
 565
 566     /**
 567      * @return {boolean}
 568      */
 569     isRoot: function()
 570     {
 571         return this.nodeIndex === this._snapshot._rootNodeIndex;
 572     },
 573
 574     /**
 575      * @return {string}
 576      */
 577     name: function()
 578     {
 579         return this._snapshot._strings[this._name()];
 580     },
 581
 582     /**
 583      * @return {number}
 584      */
 585     retainedSize: function()
 586     {
 587         return this._snapshot._retainedSizes[this._ordinal()];
 588     },
 589
 590     /**
 591      * @return {!WebInspector.HeapSnapshotRetainerEdgeIterator}
 592      */
 593     retainers: function()
 594     {
 595         return new WebInspector.HeapSnapshotRetainerEdgeIterator(this);
 596     },
 597
 598     /**
 599      * @return {number}
 600      */
 601     retainersCount: function()
 602     {
 603         var snapshot = this._snapshot;
 604         var ordinal = this._ordinal();
 605         return snapshot._firstRetainerIndex[ordinal + 1] - snapshot._firstRetainerIndex[ordinal];
 606     },
 607
 608     /**
 609      * @return {number}
 610      */
 611     selfSize: function()
 612     {
 613         var snapshot = this._snapshot;
 614         return snapshot._nodes[this.nodeIndex + snapshot._nodeSelfSizeOffset];
 615     },
 616
 617     /**
 618      * @return {string}
 619      */
 620     type: function()
 621     {
 622         return this._snapshot._nodeTypes[this._type()];
 623     },
 624
 625     /**
 626      * @return {number}
 627      */
 628     traceNodeId: function()
 629     {
 630         var snapshot = this._snapshot;
 631         return snapshot._nodes[this.nodeIndex + snapshot._nodeTraceNodeIdOffset];
 632     },
 633
 634     /**
 635      * @override
 636      * @return {number}
 637      */
 638     itemIndex: function()
 639     {
 640         return this.nodeIndex;
 641     },
 642
 643     /**
 644      * @override
 645      * @return {!WebInspector.HeapSnapshotNode.Serialized}
 646      */
 647     serialize: function()
 648     {
 649         return new WebInspector.HeapSnapshotNode.Serialized(this.id(), this.name(), this.distance(), this.nodeIndex, this.retainedSize(), this.selfSize(), this.type());
 650     },
 651
 652     /**
 653      * @return {number}
 654      */
 655     _name: function()
 656     {
 657         var snapshot = this._snapshot;
 658         return snapshot._nodes[this.nodeIndex + snapshot._nodeNameOffset];
 659     },
 660
 661     /**
 662      * @return {number}
 663      */
 664     _edgeIndexesStart: function()
 665     {
 666         return this._snapshot._firstEdgeIndexes[this._ordinal()];
 667     },
 668
 669     /**
 670      * @return {number}
 671      */
 672     _edgeIndexesEnd: function()
 673     {
 674         return this._snapshot._firstEdgeIndexes[this._ordinal() + 1];
 675     },
 676
 677     /**
 678      * @return {number}
 679      */
 680     _ordinal: function()
 681     {
 682         return this.nodeIndex / this._snapshot._nodeFieldCount;
 683     },
 684
 685     /**
 686      * @return {number}
 687      */
 688     _nextNodeIndex: function()
 689     {
 690         return this.nodeIndex + this._snapshot._nodeFieldCount;
 691     },
 692
 693     /**
 694      * @return {number}
 695      */
 696     _type: function()
 697     {
 698         var snapshot = this._snapshot;
 699         return snapshot._nodes[this.nodeIndex + snapshot._nodeTypeOffset];
 700     }
 701 };
 702
 703 /**
 704  * @constructor
 705  * @implements {WebInspector.HeapSnapshotItemIterator}
 706  * @param {!WebInspector.HeapSnapshotNode} node
 707  */
 708 WebInspector.HeapSnapshotNodeIterator = function(node)
 709 {
 710     this.node = node;
 711     this._nodesLength = node._snapshot._nodes.length;
 712 }
 713
 714 WebInspector.HeapSnapshotNodeIterator.prototype = {
 715     /**
 716      * @return {boolean}
 717      */
 718     hasNext: function()
 719     {
 720         return this.node.nodeIndex < this._nodesLength;
 721     },
 722
 723     /**
 724      * @return {!WebInspector.HeapSnapshotNode}
 725      */
 726     item: function()
 727     {
 728         return this.node;
 729     },
 730
 731     next: function()
 732     {
 733         this.node.nodeIndex = this.node._nextNodeIndex();
 734     }
 735 }
 736
 737
 738 /**
 739  * @constructor
 740  * @implements {WebInspector.HeapSnapshotItemIterator}
 741  * @param {!WebInspector.HeapSnapshotItemIndexProvider} itemProvider
 742  * @param {!Array.<number>|!Uint32Array} indexes
 743  */
 744 WebInspector.HeapSnapshotIndexRangeIterator = function(itemProvider, indexes)
 745 {
 746     this._itemProvider = itemProvider;
 747     this._indexes = indexes;
 748     this._position = 0;
 749 }
 750
 751 WebInspector.HeapSnapshotIndexRangeIterator.prototype = {
 752     /**
 753      * @return {boolean}
 754      */
 755     hasNext: function()
 756     {
 757         return this._position < this._indexes.length
 758     },
 759
 760     /**
 761      * @return {!WebInspector.HeapSnapshotItem}
 762      */
 763     item: function()
 764     {
 765         var index = this._indexes[this._position];
 766         return this._itemProvider.itemForIndex(index);
 767     },
 768
 769     next: function()
 770     {
 771         ++this._position;
 772     }
 773 }
 774
 775
 776 /**
 777  * @constructor
 778  * @implements {WebInspector.HeapSnapshotItemIterator}
 779  * @param {!WebInspector.HeapSnapshotItemIterator} iterator
 780  */
 781 WebInspector.HeapSnapshotFilteredIterator = function(iterator, filter)
 782 {
 783     this._iterator = iterator;
 784     this._filter = filter;
 785     this._skipFilteredItems();
 786 }
 787
 788 WebInspector.HeapSnapshotFilteredIterator.prototype = {
 789     /**
 790      * @return {boolean}
 791      */
 792     hasNext: function()
 793     {
 794         return this._iterator.hasNext();
 795     },
 796
 797     /**
 798      * @return {!WebInspector.HeapSnapshotItem}
 799      */
 800     item: function()
 801     {
 802         return this._iterator.item();
 803     },
 804
 805     next: function()
 806     {
 807         this._iterator.next();
 808         this._skipFilteredItems();
 809     },
 810
 811     _skipFilteredItems: function()
 812     {
 813         while (this._iterator.hasNext() && !this._filter(this._iterator.item())) {
 814             this._iterator.next();
 815         }
 816     }
 817 }
 818
 819
 820 /**
 821  * @param {!WebInspector.HeapSnapshotWorkerDispatcher=} dispatcher
 822  * @constructor
 823  */
 824 WebInspector.HeapSnapshotProgress = function(dispatcher)
 825 {
 826     this._dispatcher = dispatcher;
 827 }
 828
 829 WebInspector.HeapSnapshotProgress.prototype = {
 830     /**
 831      * @param {string} status
 832      */
 833     updateStatus: function(status)
 834     {
 835         this._sendUpdateEvent(WebInspector.UIString(status));
 836     },
 837
 838     /**
 839      * @param {string} title
 840      * @param {number} value
 841      * @param {number} total
 842      */
 843     updateProgress: function(title, value, total)
 844     {
 845         var percentValue = ((total ? (value / total) : 0) * 100).toFixed(0);
 846         this._sendUpdateEvent(WebInspector.UIString(title, percentValue));
 847     },
 848
 849     /**
 850      * @param {string} text
 851      */
 852     _sendUpdateEvent: function(text)
 853     {
 854         // May be undefined in tests.
 855         if (this._dispatcher)
 856             this._dispatcher.sendEvent(WebInspector.HeapSnapshotProgressEvent.Update, text);
 857     }
 858 }
 859
 860
 861 /**
 862  * @param {!WebInspector.HeapSnapshotProgress} progress
 863  * @param {boolean} showHiddenData
 864  * @constructor
 865  */
 866 WebInspector.HeapSnapshot = function(profile, progress, showHiddenData)
 867 {
 868     this._nodes = profile.nodes;
 869     this._containmentEdges = profile.edges;
 870     /** @type {!HeapSnapshotMetainfo} */
 871     this._metaNode = profile.snapshot.meta;
 872     this._strings = profile.strings;
 873     this._progress = progress;
 874
 875     this._noDistance = -5;
 876     this._rootNodeIndex = 0;
 877     if (profile.snapshot.root_index)
 878         this._rootNodeIndex = profile.snapshot.root_index;
 879
 880     this._snapshotDiffs = {};
 881     this._aggregatesForDiff = null;
 882     this._aggregates = {};
 883     this._aggregatesSortedFlags = {};
 884     this._showHiddenData = showHiddenData;
 885
 886     this._init();
 887
 888     if (profile.snapshot.trace_function_count) {
 889         this._progress.updateStatus("Buiding allocation statistics\u2026");
 890         var nodes = this._nodes;
 891         var nodesLength = nodes.length;
 892         var nodeFieldCount = this._nodeFieldCount;
 893         var node = this.rootNode();
 894         var liveObjects = {};
 895         for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
 896             node.nodeIndex = nodeIndex;
 897             var traceNodeId = node.traceNodeId();
 898             var stats = liveObjects[traceNodeId];
 899             if (!stats) {
 900                 liveObjects[traceNodeId] = stats = { count: 0, size: 0, ids: []};
 901             }
 902             stats.count++;
 903             stats.size += node.selfSize();
 904             stats.ids.push(node.id());
 905         }
 906         this._allocationProfile = new WebInspector.AllocationProfile(profile, liveObjects);
 907         this._progress.updateStatus("Done");
 908     }
 909 }
 910
 911 /**
 912  * @constructor
 913  */
 914 function HeapSnapshotMetainfo()
 915 {
 916     // New format.
 917     this.node_fields = [];
 918     this.node_types = [];
 919     this.edge_fields = [];
 920     this.edge_types = [];
 921     this.trace_function_info_fields = [];
 922     this.trace_node_fields = [];
 923     this.type_strings = {};
 924 }
 925
 926 /**
 927  * @constructor
 928  */
 929 function HeapSnapshotHeader()
 930 {
 931     // New format.
 932     this.title = "";
 933     this.meta = new HeapSnapshotMetainfo();
 934     this.node_count = 0;
 935     this.edge_count = 0;
 936 }
 937
 938 WebInspector.HeapSnapshot.prototype = {
 939     _init: function()
 940     {
 941         var meta = this._metaNode;
 942
 943         this._nodeTypeOffset = meta.node_fields.indexOf("type");
 944         this._nodeNameOffset = meta.node_fields.indexOf("name");
 945         this._nodeIdOffset = meta.node_fields.indexOf("id");
 946         this._nodeSelfSizeOffset = meta.node_fields.indexOf("self_size");
 947         this._nodeEdgeCountOffset = meta.node_fields.indexOf("edge_count");
 948         this._nodeTraceNodeIdOffset = meta.node_fields.indexOf("trace_node_id");
 949         this._nodeFieldCount = meta.node_fields.length;
 950
 951         this._nodeTypes = meta.node_types[this._nodeTypeOffset];
 952         this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
 953         this._nodeObjectType = this._nodeTypes.indexOf("object");
 954         this._nodeNativeType = this._nodeTypes.indexOf("native");
 955         this._nodeConsStringType = this._nodeTypes.indexOf("concatenated string");
 956         this._nodeSlicedStringType = this._nodeTypes.indexOf("sliced string");
 957         this._nodeCodeType = this._nodeTypes.indexOf("code");
 958         this._nodeSyntheticType = this._nodeTypes.indexOf("synthetic");
 959
 960         this._edgeFieldsCount = meta.edge_fields.length;
 961         this._edgeTypeOffset = meta.edge_fields.indexOf("type");
 962         this._edgeNameOffset = meta.edge_fields.indexOf("name_or_index");
 963         this._edgeToNodeOffset = meta.edge_fields.indexOf("to_node");
 964
 965         this._edgeTypes = meta.edge_types[this._edgeTypeOffset];
 966         this._edgeTypes.push("invisible");
 967         this._edgeElementType = this._edgeTypes.indexOf("element");
 968         this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
 969         this._edgeInternalType = this._edgeTypes.indexOf("internal");
 970         this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
 971         this._edgeWeakType = this._edgeTypes.indexOf("weak");
 972         this._edgeInvisibleType = this._edgeTypes.indexOf("invisible");
 973
 974         this.nodeCount = this._nodes.length / this._nodeFieldCount;
 975         this._edgeCount = this._containmentEdges.length / this._edgeFieldsCount;
 976
 977         this._progress.updateStatus("Building edge indexes\u2026");
 978         this._buildEdgeIndexes();
 979         this._progress.updateStatus("Building retainers\u2026");
 980         this._buildRetainers();
 981         this._progress.updateStatus("Calculating node flags\u2026");
 982         this._calculateFlags();
 983         this._progress.updateStatus("Calculating distances\u2026");
 984         this._calculateDistances();
 985         this._progress.updateStatus("Building postorder index\u2026");
 986         var result = this._buildPostOrderIndex();
 987         // Actually it is array that maps node ordinal number to dominator node ordinal number.
 988         this._progress.updateStatus("Building dominator tree\u2026");
 989         this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex);
 990         this._progress.updateStatus("Calculating retained sizes\u2026");
 991         this._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal);
 992         this._progress.updateStatus("Buiding dominated nodes\u2026");
 993         this._buildDominatedNodes();
 994         this._progress.updateStatus("Calculating statistics\u2026");
 995         this._calculateStatistics();
 996         this._progress.updateStatus("Finished processing.");
 997     },
 998
 999     _buildEdgeIndexes: function()
1000     {
1001         var nodes = this._nodes;
1002         var nodeCount = this.nodeCount;
1003         var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1);
1004         var nodeFieldCount = this._nodeFieldCount;
1005         var edgeFieldsCount = this._edgeFieldsCount;
1006         var nodeEdgeCountOffset = this._nodeEdgeCountOffset;
1007         firstEdgeIndexes[nodeCount] = this._containmentEdges.length;
1008         for (var nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) {
1009             firstEdgeIndexes[nodeOrdinal] = edgeIndex;
1010             edgeIndex += nodes[nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset] * edgeFieldsCount;
1011         }
1012     },
1013
1014     _buildRetainers: function()
1015     {
1016         var retainingNodes = this._retainingNodes = new Uint32Array(this._edgeCount);
1017         var retainingEdges = this._retainingEdges = new Uint32Array(this._edgeCount);
1018         // Index of the first retainer in the _retainingNodes and _retainingEdges
1019         // arrays. Addressed by retained node index.
1020         var firstRetainerIndex = this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1);
1021
1022         var containmentEdges = this._containmentEdges;
1023         var edgeFieldsCount = this._edgeFieldsCount;
1024         var nodeFieldCount = this._nodeFieldCount;
1025         var edgeToNodeOffset = this._edgeToNodeOffset;
1026         var firstEdgeIndexes = this._firstEdgeIndexes;
1027         var nodeCount = this.nodeCount;
1028
1029         for (var toNodeFieldIndex = edgeToNodeOffset, l = containmentEdges.length; toNodeFieldIndex < l; toNodeFieldIndex += edgeFieldsCount) {
1030             var toNodeIndex = containmentEdges[toNodeFieldIndex];
1031             if (toNodeIndex % nodeFieldCount)
1032                 throw new Error("Invalid toNodeIndex " + toNodeIndex);
1033             ++firstRetainerIndex[toNodeIndex / nodeFieldCount];
1034         }
1035         for (var i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) {
1036             var retainersCount = firstRetainerIndex[i];
1037             firstRetainerIndex[i] = firstUnusedRetainerSlot;
1038             retainingNodes[firstUnusedRetainerSlot] = retainersCount;
1039             firstUnusedRetainerSlot += retainersCount;
1040         }
1041         firstRetainerIndex[nodeCount] = retainingNodes.length;
1042
1043         var nextNodeFirstEdgeIndex = firstEdgeIndexes[0];
1044         for (var srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) {
1045             var firstEdgeIndex = nextNodeFirstEdgeIndex;
1046             nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1];
1047             var srcNodeIndex = srcNodeOrdinal * nodeFieldCount;
1048             for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) {
1049                 var toNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1050                 if (toNodeIndex % nodeFieldCount)
1051                     throw new Error("Invalid toNodeIndex " + toNodeIndex);
1052                 var firstRetainerSlotIndex = firstRetainerIndex[toNodeIndex / nodeFieldCount];
1053                 var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]);
1054                 retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex;
1055                 retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex;
1056             }
1057         }
1058     },
1059
1060     /**
1061      * @param {number=} nodeIndex
1062      */
1063     createNode: function(nodeIndex)
1064     {
1065         throw new Error("Not implemented");
1066     },
1067
1068     /**
1069      * @param {number} edgeIndex
1070      * @return {!WebInspector.JSHeapSnapshotEdge}
1071      */
1072     createEdge: function(edgeIndex)
1073     {
1074         throw new Error("Not implemented");
1075     },
1076
1077     /**
1078      * @param {number} retainerIndex
1079      * @return {!WebInspector.JSHeapSnapshotRetainerEdge}
1080      */
1081     createRetainingEdge: function(retainerIndex)
1082     {
1083         throw new Error("Not implemented");
1084     },
1085
1086     dispose: function()
1087     {
1088         delete this._nodes;
1089         delete this._strings;
1090         delete this._retainingEdges;
1091         delete this._retainingNodes;
1092         delete this._firstRetainerIndex;
1093         delete this._aggregates;
1094         delete this._aggregatesSortedFlags;
1095         delete this._dominatedNodes;
1096         delete this._firstDominatedNodeIndex;
1097         delete this._nodeDistances;
1098         delete this._dominatorsTree;
1099     },
1100
1101     _allNodes: function()
1102     {
1103         return new WebInspector.HeapSnapshotNodeIterator(this.rootNode());
1104     },
1105
1106     /**
1107      * @return {!WebInspector.HeapSnapshotNode}
1108      */
1109     rootNode: function()
1110     {
1111         return this.createNode(this._rootNodeIndex);
1112     },
1113
1114     get rootNodeIndex()
1115     {
1116         return this._rootNodeIndex;
1117     },
1118
1119     get totalSize()
1120     {
1121         return this.rootNode().retainedSize();
1122     },
1123
1124     _getDominatedIndex: function(nodeIndex)
1125     {
1126         if (nodeIndex % this._nodeFieldCount)
1127             throw new Error("Invalid nodeIndex: " + nodeIndex);
1128         return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount];
1129     },
1130
1131     /**
1132      * @param {!WebInspector.HeapSnapshotNode} node
1133      * @return {!Uint32Array}
1134      */
1135     _dominatedNodesOfNode: function(node)
1136     {
1137         var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex);
1138         var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex());
1139         return this._dominatedNodes.subarray(dominatedIndexFrom, dominatedIndexTo);
1140     },
1141
1142     /**
1143      * @param {!WebInspector.HeapSnapshotCommon.NodeFilter} nodeFilter
1144      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Aggregate>}
1145      */
1146     aggregatesWithFilter: function(nodeFilter)
1147     {
1148         var minNodeId = nodeFilter.minNodeId;
1149         var maxNodeId = nodeFilter.maxNodeId;
1150         var allocationNodeId = nodeFilter.allocationNodeId;
1151         var key;
1152         var filter;
1153         if (typeof allocationNodeId === "number") {
1154             filter = this._createAllocationStackFilter(allocationNodeId);
1155         } else if (typeof minNodeId === "number" && typeof maxNodeId === "number") {
1156             key = minNodeId + ".." + maxNodeId;
1157             filter = this._createNodeIdFilter(minNodeId, maxNodeId);
1158         } else {
1159             key = "allObjects";
1160         }
1161         return this.aggregates(false, key, filter);
1162     },
1163
1164     /**
1165      * @param {number} minNodeId
1166      * @param {number} maxNodeId
1167      * @return {function(!WebInspector.HeapSnapshotNode):boolean}
1168      */
1169     _createNodeIdFilter: function(minNodeId, maxNodeId)
1170     {
1171         /**
1172          * @param {!WebInspector.HeapSnapshotNode} node
1173          * @return boolean
1174          */
1175         function nodeIdFilter(node)
1176         {
1177             var id = node.id();
1178             return id > minNodeId && id <= maxNodeId;
1179         }
1180         return nodeIdFilter;
1181     },
1182
1183     /**
1184      * @param {number} bottomUpAllocationNodeId
1185      * @return {function(!WebInspector.HeapSnapshotNode):boolean|undefined}
1186      */
1187     _createAllocationStackFilter: function(bottomUpAllocationNodeId)
1188     {
1189         var traceIds = this._allocationProfile.traceIds(bottomUpAllocationNodeId);
1190         if (!traceIds.length)
1191             return undefined;
1192         var set = {};
1193         for (var i = 0; i < traceIds.length; i++)
1194             set[traceIds[i]] = true;
1195         /**
1196          * @param {!WebInspector.HeapSnapshotNode} node
1197          * @return boolean
1198          */
1199         function traceIdFilter(node)
1200         {
1201             return !!set[node.traceNodeId()];
1202         };
1203         return traceIdFilter;
1204     },
1205
1206     /**
1207      * @param {boolean} sortedIndexes
1208      * @param {string=} key
1209      * @param {function(!WebInspector.HeapSnapshotNode):boolean=} filter
1210      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Aggregate>}
1211      */
1212     aggregates: function(sortedIndexes, key, filter)
1213     {
1214         var aggregatesByClassName = key && this._aggregates[key];
1215         if (!aggregatesByClassName) {
1216             var aggregates = this._buildAggregates(filter);
1217             this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter);
1218             aggregatesByClassName = aggregates.aggregatesByClassName;
1219             if (key)
1220                 this._aggregates[key] = aggregatesByClassName;
1221         }
1222
1223         if (sortedIndexes && (!key || !this._aggregatesSortedFlags[key])) {
1224             this._sortAggregateIndexes(aggregatesByClassName);
1225             if (key)
1226                 this._aggregatesSortedFlags[key] = sortedIndexes;
1227         }
1228         return aggregatesByClassName;
1229     },
1230
1231     /**
1232      * @return {!Array.<!WebInspector.HeapSnapshotCommon.SerializedAllocationNode>}
1233      */
1234     allocationTracesTops: function()
1235     {
1236         return this._allocationProfile.serializeTraceTops();
1237     },
1238
1239     /**
1240      * @param {number} nodeId
1241      * @return {!WebInspector.HeapSnapshotCommon.AllocationNodeCallers}
1242      */
1243     allocationNodeCallers: function(nodeId)
1244     {
1245         return this._allocationProfile.serializeCallers(nodeId);
1246     },
1247
1248     /**
1249      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.AggregateForDiff>}
1250      */
1251     aggregatesForDiff: function()
1252     {
1253         if (this._aggregatesForDiff)
1254             return this._aggregatesForDiff;
1255
1256         var aggregatesByClassName = this.aggregates(true, "allObjects");
1257         this._aggregatesForDiff  = {};
1258
1259         var node = this.createNode();
1260         for (var className in aggregatesByClassName) {
1261             var aggregate = aggregatesByClassName[className];
1262             var indexes = aggregate.idxs;
1263             var ids = new Array(indexes.length);
1264             var selfSizes = new Array(indexes.length);
1265             for (var i = 0; i < indexes.length; i++) {
1266                 node.nodeIndex = indexes[i];
1267                 ids[i] = node.id();
1268                 selfSizes[i] = node.selfSize();
1269             }
1270
1271             this._aggregatesForDiff[className] = {
1272                 indexes: indexes,
1273                 ids: ids,
1274                 selfSizes: selfSizes
1275             };
1276         }
1277         return this._aggregatesForDiff;
1278     },
1279
1280     /**
1281      * @param {!WebInspector.HeapSnapshotNode} node
1282      * @return {!boolean}
1283      */
1284     _isUserRoot: function(node)
1285     {
1286         return true;
1287     },
1288
1289     /**
1290      * @param {function(!WebInspector.HeapSnapshotNode)} action
1291      * @param {boolean=} userRootsOnly
1292      */
1293     forEachRoot: function(action, userRootsOnly)
1294     {
1295         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
1296             var node = iter.edge.node();
1297             if (!userRootsOnly || this._isUserRoot(node))
1298                 action(node);
1299         }
1300     },
1301
1302     _calculateDistances: function()
1303     {
1304         var nodeFieldCount = this._nodeFieldCount;
1305         var nodeCount = this.nodeCount;
1306         var distances = this._nodeDistances = new Int32Array(nodeCount);
1307         var noDistance = this._noDistance;
1308         for (var i = 0; i < nodeCount; ++i)
1309             distances[i] = noDistance;
1310
1311         var nodesToVisit = new Uint32Array(this.nodeCount);
1312         var nodesToVisitLength = 0;
1313
1314         /**
1315          * @param {number} distance
1316          * @param {!WebInspector.HeapSnapshotNode} node
1317          */
1318         function enqueueNode(distance, node)
1319         {
1320             var ordinal = node._ordinal();
1321             if (distances[ordinal] !== noDistance)
1322                 return;
1323             distances[ordinal] = distance;
1324             nodesToVisit[nodesToVisitLength++] = node.nodeIndex;
1325         }
1326
1327         this.forEachRoot(enqueueNode.bind(null, 1), true);
1328         this._bfs(nodesToVisit, nodesToVisitLength, distances);
1329
1330         // bfs for the rest of objects
1331         nodesToVisitLength = 0;
1332         this.forEachRoot(enqueueNode.bind(null, 0), false);
1333         this._bfs(nodesToVisit, nodesToVisitLength, distances);
1334     },
1335
1336     /**
1337      * @param {!Uint32Array} nodesToVisit
1338      * @param {!number} nodesToVisitLength
1339      * @param {!Int32Array} distances
1340      */
1341     _bfs: function(nodesToVisit, nodesToVisitLength, distances)
1342     {
1343         // Preload fields into local variables for better performance.
1344         var edgeFieldsCount = this._edgeFieldsCount;
1345         var nodeFieldCount = this._nodeFieldCount;
1346         var containmentEdges = this._containmentEdges;
1347         var firstEdgeIndexes = this._firstEdgeIndexes;
1348         var edgeToNodeOffset = this._edgeToNodeOffset;
1349         var edgeTypeOffset = this._edgeTypeOffset;
1350         var nodeCount = this.nodeCount;
1351         var containmentEdgesLength = containmentEdges.length;
1352         var edgeWeakType = this._edgeWeakType;
1353         var noDistance = this._noDistance;
1354
1355         var index = 0;
1356         while (index < nodesToVisitLength) {
1357             var nodeIndex = nodesToVisit[index++]; // shift generates too much garbage.
1358             var nodeOrdinal = nodeIndex / nodeFieldCount;
1359             var distance = distances[nodeOrdinal] + 1;
1360             var firstEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1361             var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1];
1362             for (var edgeIndex = firstEdgeIndex; edgeIndex < edgesEnd; edgeIndex += edgeFieldsCount) {
1363                 var edgeType = containmentEdges[edgeIndex + edgeTypeOffset];
1364                 if (edgeType == edgeWeakType)
1365                     continue;
1366                 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1367                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1368                 if (distances[childNodeOrdinal] !== noDistance)
1369                     continue;
1370                 distances[childNodeOrdinal] = distance;
1371                 nodesToVisit[nodesToVisitLength++] = childNodeIndex;
1372             }
1373         }
1374         if (nodesToVisitLength > nodeCount)
1375             throw new Error("BFS failed. Nodes to visit (" + nodesToVisitLength + ") is more than nodes count (" + nodeCount + ")");
1376     },
1377
1378     _buildAggregates: function(filter)
1379     {
1380         var aggregates = {};
1381         var aggregatesByClassName = {};
1382         var classIndexes = [];
1383         var nodes = this._nodes;
1384         var mapAndFlag = this.userObjectsMapAndFlag();
1385         var flags = mapAndFlag ? mapAndFlag.map : null;
1386         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1387         var nodesLength = nodes.length;
1388         var nodeNativeType = this._nodeNativeType;
1389         var nodeFieldCount = this._nodeFieldCount;
1390         var selfSizeOffset = this._nodeSelfSizeOffset;
1391         var nodeTypeOffset = this._nodeTypeOffset;
1392         var node = this.rootNode();
1393         var nodeDistances = this._nodeDistances;
1394
1395         for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
1396             var nodeOrdinal = nodeIndex / nodeFieldCount;
1397             if (flags && !(flags[nodeOrdinal] & flag))
1398                 continue;
1399             node.nodeIndex = nodeIndex;
1400             if (filter && !filter(node))
1401                 continue;
1402             var selfSize = nodes[nodeIndex + selfSizeOffset];
1403             if (!selfSize && nodes[nodeIndex + nodeTypeOffset] !== nodeNativeType)
1404                 continue;
1405             var classIndex = node.classIndex();
1406             if (!(classIndex in aggregates)) {
1407                 var nodeType = node.type();
1408                 var nameMatters = nodeType === "object" || nodeType === "native";
1409                 var value = {
1410                     count: 1,
1411                     distance: nodeDistances[nodeOrdinal],
1412                     self: selfSize,
1413                     maxRet: 0,
1414                     type: nodeType,
1415                     name: nameMatters ? node.name() : null,
1416                     idxs: [nodeIndex]
1417                 };
1418                 aggregates[classIndex] = value;
1419                 classIndexes.push(classIndex);
1420                 aggregatesByClassName[node.className()] = value;
1421             } else {
1422                 var clss = aggregates[classIndex];
1423                 clss.distance = Math.min(clss.distance, nodeDistances[nodeOrdinal]);
1424                 ++clss.count;
1425                 clss.self += selfSize;
1426                 clss.idxs.push(nodeIndex);
1427             }
1428         }
1429
1430         // Shave off provisionally allocated space.
1431         for (var i = 0, l = classIndexes.length; i < l; ++i) {
1432             var classIndex = classIndexes[i];
1433             aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice();
1434         }
1435         return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates};
1436     },
1437
1438     _calculateClassesRetainedSize: function(aggregates, filter)
1439     {
1440         var rootNodeIndex = this._rootNodeIndex;
1441         var node = this.createNode(rootNodeIndex);
1442         var list = [rootNodeIndex];
1443         var sizes = [-1];
1444         var classes = [];
1445         var seenClassNameIndexes = {};
1446         var nodeFieldCount = this._nodeFieldCount;
1447         var nodeTypeOffset = this._nodeTypeOffset;
1448         var nodeNativeType = this._nodeNativeType;
1449         var dominatedNodes = this._dominatedNodes;
1450         var nodes = this._nodes;
1451         var mapAndFlag = this.userObjectsMapAndFlag();
1452         var flags = mapAndFlag ? mapAndFlag.map : null;
1453         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1454         var firstDominatedNodeIndex = this._firstDominatedNodeIndex;
1455
1456         while (list.length) {
1457             var nodeIndex = list.pop();
1458             node.nodeIndex = nodeIndex;
1459             var classIndex = node.classIndex();
1460             var seen = !!seenClassNameIndexes[classIndex];
1461             var nodeOrdinal = nodeIndex / nodeFieldCount;
1462             var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal];
1463             var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1];
1464
1465             if (!seen &&
1466                 (!flags || (flags[nodeOrdinal] & flag)) &&
1467                 (!filter || filter(node)) &&
1468                 (node.selfSize() || nodes[nodeIndex + nodeTypeOffset] === nodeNativeType)
1469                ) {
1470                 aggregates[classIndex].maxRet += node.retainedSize();
1471                 if (dominatedIndexFrom !== dominatedIndexTo) {
1472                     seenClassNameIndexes[classIndex] = true;
1473                     sizes.push(list.length);
1474                     classes.push(classIndex);
1475                 }
1476             }
1477             for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++)
1478                 list.push(dominatedNodes[i]);
1479
1480             var l = list.length;
1481             while (sizes[sizes.length - 1] === l) {
1482                 sizes.pop();
1483                 classIndex = classes.pop();
1484                 seenClassNameIndexes[classIndex] = false;
1485             }
1486         }
1487     },
1488
1489     _sortAggregateIndexes: function(aggregates)
1490     {
1491         var nodeA = this.createNode();
1492         var nodeB = this.createNode();
1493         for (var clss in aggregates)
1494             aggregates[clss].idxs.sort(
1495                 function(idxA, idxB) {
1496                     nodeA.nodeIndex = idxA;
1497                     nodeB.nodeIndex = idxB;
1498                     return nodeA.id() < nodeB.id() ? -1 : 1;
1499                 });
1500     },
1501
1502     _buildPostOrderIndex: function()
1503     {
1504         var nodeFieldCount = this._nodeFieldCount;
1505         var nodes = this._nodes;
1506         var nodeCount = this.nodeCount;
1507         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1508
1509         var edgeFieldsCount = this._edgeFieldsCount;
1510         var edgeTypeOffset = this._edgeTypeOffset;
1511         var edgeToNodeOffset = this._edgeToNodeOffset;
1512         var edgeShortcutType = this._edgeShortcutType;
1513         var firstEdgeIndexes = this._firstEdgeIndexes;
1514         var containmentEdges = this._containmentEdges;
1515         var containmentEdgesLength = this._containmentEdges.length;
1516
1517         var mapAndFlag = this.userObjectsMapAndFlag();
1518         var flags = mapAndFlag ? mapAndFlag.map : null;
1519         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1520
1521         var nodesToVisit = new Uint32Array(nodeCount);
1522         var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount);
1523         var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount);
1524         var painted = new Uint8Array(nodeCount);
1525         var nodesToVisitLength = 0;
1526         var postOrderIndex = 0;
1527         var grey = 1;
1528         var black = 2;
1529
1530         nodesToVisit[nodesToVisitLength++] = rootNodeOrdinal;
1531         painted[rootNodeOrdinal] = grey;
1532
1533         while (nodesToVisitLength) {
1534             var nodeOrdinal = nodesToVisit[nodesToVisitLength - 1];
1535
1536             if (painted[nodeOrdinal] === grey) {
1537                 painted[nodeOrdinal] = black;
1538                 var nodeFlag = !flags || (flags[nodeOrdinal] & flag);
1539                 var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1540                 var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1];
1541                 for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) {
1542                     if (nodeOrdinal !== rootNodeOrdinal && containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType)
1543                         continue;
1544                     var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1545                     var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1546                     var childNodeFlag = !flags || (flags[childNodeOrdinal] & flag);
1547                     // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1548                     // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1549                     if (nodeOrdinal !== rootNodeOrdinal && childNodeFlag && !nodeFlag)
1550                         continue;
1551                     if (!painted[childNodeOrdinal]) {
1552                         painted[childNodeOrdinal] = grey;
1553                         nodesToVisit[nodesToVisitLength++] = childNodeOrdinal;
1554                     }
1555                 }
1556             } else {
1557                 nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex;
1558                 postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal;
1559                 --nodesToVisitLength;
1560             }
1561         }
1562
1563         if (postOrderIndex !== nodeCount) {
1564             console.log("Error: Corrupted snapshot. " + (nodeCount - postOrderIndex) + " nodes are unreachable from the root:");
1565             var dumpNode = this.rootNode();
1566             for (var i = 0; i < nodeCount; ++i) {
1567                 if (painted[i] !== black) {
1568                     // Fix it by giving the node a postorder index anyway.
1569                     nodeOrdinal2PostOrderIndex[i] = postOrderIndex;
1570                     postOrderIndex2NodeOrdinal[postOrderIndex++] = i;
1571                     dumpNode.nodeIndex = i * nodeFieldCount;
1572                     console.log(JSON.stringify(dumpNode.serialize()));
1573                     for (var retainers = dumpNode.retainers(); retainers.hasNext(); retainers = retainers.item().node().retainers())
1574                         console.log("  edgeName: " + retainers.item().name() + " nodeClassName: " + retainers.item().node().className());
1575                 }
1576             }
1577         }
1578
1579         return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
1580     },
1581
1582     // The algorithm is based on the article:
1583     // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
1584     // Softw. Pract. Exper. 4 (2001), pp. 1-10.
1585     /**
1586      * @param {!Array.<number>} postOrderIndex2NodeOrdinal
1587      * @param {!Array.<number>} nodeOrdinal2PostOrderIndex
1588      */
1589     _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex)
1590     {
1591         var nodeFieldCount = this._nodeFieldCount;
1592         var nodes = this._nodes;
1593         var firstRetainerIndex = this._firstRetainerIndex;
1594         var retainingNodes = this._retainingNodes;
1595         var retainingEdges = this._retainingEdges;
1596         var edgeFieldsCount = this._edgeFieldsCount;
1597         var edgeTypeOffset = this._edgeTypeOffset;
1598         var edgeToNodeOffset = this._edgeToNodeOffset;
1599         var edgeShortcutType = this._edgeShortcutType;
1600         var firstEdgeIndexes = this._firstEdgeIndexes;
1601         var containmentEdges = this._containmentEdges;
1602         var containmentEdgesLength = this._containmentEdges.length;
1603         var rootNodeIndex = this._rootNodeIndex;
1604
1605         var mapAndFlag = this.userObjectsMapAndFlag();
1606         var flags = mapAndFlag ? mapAndFlag.map : null;
1607         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1608
1609         var nodesCount = postOrderIndex2NodeOrdinal.length;
1610         var rootPostOrderedIndex = nodesCount - 1;
1611         var noEntry = nodesCount;
1612         var dominators = new Uint32Array(nodesCount);
1613         for (var i = 0; i < rootPostOrderedIndex; ++i)
1614             dominators[i] = noEntry;
1615         dominators[rootPostOrderedIndex] = rootPostOrderedIndex;
1616
1617         // The affected array is used to mark entries which dominators
1618         // have to be racalculated because of changes in their retainers.
1619         var affected = new Uint8Array(nodesCount);
1620         var nodeOrdinal;
1621
1622         { // Mark the root direct children as affected.
1623             nodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1624             var beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1625             var endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1626             for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1627                  toNodeFieldIndex < endEdgeToNodeFieldIndex;
1628                  toNodeFieldIndex += edgeFieldsCount) {
1629                 var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1630                 affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1631             }
1632         }
1633
1634         var changed = true;
1635         while (changed) {
1636             changed = false;
1637             for (var postOrderIndex = rootPostOrderedIndex - 1; postOrderIndex >= 0; --postOrderIndex) {
1638                 if (affected[postOrderIndex] === 0)
1639                     continue;
1640                 affected[postOrderIndex] = 0;
1641                 // If dominator of the entry has already been set to root,
1642                 // then it can't propagate any further.
1643                 if (dominators[postOrderIndex] === rootPostOrderedIndex)
1644                     continue;
1645                 nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1646                 var nodeFlag = !flags || (flags[nodeOrdinal] & flag);
1647                 var newDominatorIndex = noEntry;
1648                 var beginRetainerIndex = firstRetainerIndex[nodeOrdinal];
1649                 var endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1];
1650                 for (var retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) {
1651                     var retainerEdgeIndex = retainingEdges[retainerIndex];
1652                     var retainerEdgeType = containmentEdges[retainerEdgeIndex + edgeTypeOffset];
1653                     var retainerNodeIndex = retainingNodes[retainerIndex];
1654                     if (retainerNodeIndex !== rootNodeIndex && retainerEdgeType === edgeShortcutType)
1655                         continue;
1656                     var retainerNodeOrdinal = retainerNodeIndex / nodeFieldCount;
1657                     var retainerNodeFlag = !flags || (flags[retainerNodeOrdinal] & flag);
1658                     // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1659                     // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1660                     if (retainerNodeIndex !== rootNodeIndex && nodeFlag && !retainerNodeFlag)
1661                         continue;
1662                     var retanerPostOrderIndex = nodeOrdinal2PostOrderIndex[retainerNodeOrdinal];
1663                     if (dominators[retanerPostOrderIndex] !== noEntry) {
1664                         if (newDominatorIndex === noEntry)
1665                             newDominatorIndex = retanerPostOrderIndex;
1666                         else {
1667                             while (retanerPostOrderIndex !== newDominatorIndex) {
1668                                 while (retanerPostOrderIndex < newDominatorIndex)
1669                                     retanerPostOrderIndex = dominators[retanerPostOrderIndex];
1670                                 while (newDominatorIndex < retanerPostOrderIndex)
1671                                     newDominatorIndex = dominators[newDominatorIndex];
1672                             }
1673                         }
1674                         // If idom has already reached the root, it doesn't make sense
1675                         // to check other retainers.
1676                         if (newDominatorIndex === rootPostOrderedIndex)
1677                             break;
1678                     }
1679                 }
1680                 if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
1681                     dominators[postOrderIndex] = newDominatorIndex;
1682                     changed = true;
1683                     nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1684                     beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1685                     endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1686                     for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1687                          toNodeFieldIndex < endEdgeToNodeFieldIndex;
1688                          toNodeFieldIndex += edgeFieldsCount) {
1689                         var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1690                         affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1691                     }
1692                 }
1693             }
1694         }
1695
1696         var dominatorsTree = new Uint32Array(nodesCount);
1697         for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) {
1698             nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1699             dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]];
1700         }
1701         return dominatorsTree;
1702     },
1703
1704     _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal)
1705     {
1706         var nodeCount = this.nodeCount;
1707         var nodes = this._nodes;
1708         var nodeSelfSizeOffset = this._nodeSelfSizeOffset;
1709         var nodeFieldCount = this._nodeFieldCount;
1710         var dominatorsTree = this._dominatorsTree;
1711         var retainedSizes = this._retainedSizes = new Float64Array(nodeCount);
1712
1713         for (var nodeOrdinal = 0; nodeOrdinal < nodeCount; ++nodeOrdinal)
1714             retainedSizes[nodeOrdinal] = nodes[nodeOrdinal * nodeFieldCount + nodeSelfSizeOffset];
1715
1716         // Propagate retained sizes for each node excluding root.
1717         for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) {
1718             var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1719             var dominatorOrdinal = dominatorsTree[nodeOrdinal];
1720             retainedSizes[dominatorOrdinal] += retainedSizes[nodeOrdinal];
1721         }
1722     },
1723
1724     _buildDominatedNodes: function()
1725     {
1726         // Builds up two arrays:
1727         //  - "dominatedNodes" is a continuous array, where each node owns an
1728         //    interval (can be empty) with corresponding dominated nodes.
1729         //  - "indexArray" is an array of indexes in the "dominatedNodes"
1730         //    with the same positions as in the _nodeIndex.
1731         var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1);
1732         // All nodes except the root have dominators.
1733         var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1);
1734
1735         // Count the number of dominated nodes for each node. Skip the root (node at
1736         // index 0) as it is the only node that dominates itself.
1737         var nodeFieldCount = this._nodeFieldCount;
1738         var dominatorsTree = this._dominatorsTree;
1739
1740         var fromNodeOrdinal = 0;
1741         var toNodeOrdinal = this.nodeCount;
1742         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1743         if (rootNodeOrdinal === fromNodeOrdinal)
1744             fromNodeOrdinal = 1;
1745         else if (rootNodeOrdinal === toNodeOrdinal - 1)
1746             toNodeOrdinal = toNodeOrdinal - 1;
1747         else
1748             throw new Error("Root node is expected to be either first or last");
1749         for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal)
1750             ++indexArray[dominatorsTree[nodeOrdinal]];
1751         // Put in the first slot of each dominatedNodes slice the count of entries
1752         // that will be filled.
1753         var firstDominatedNodeIndex = 0;
1754         for (var i = 0, l = this.nodeCount; i < l; ++i) {
1755             var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i];
1756             indexArray[i] = firstDominatedNodeIndex;
1757             firstDominatedNodeIndex += dominatedCount;
1758         }
1759         indexArray[this.nodeCount] = dominatedNodes.length;
1760         // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at
1761         // index 0) as it is the only node that dominates itself.
1762         for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) {
1763             var dominatorOrdinal = dominatorsTree[nodeOrdinal];
1764             var dominatedRefIndex = indexArray[dominatorOrdinal];
1765             dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
1766             dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount;
1767         }
1768     },
1769
1770     _calculateFlags: function()
1771     {
1772         throw new Error("Not implemented");
1773     },
1774
1775     _calculateStatistics: function()
1776     {
1777         throw new Error("Not implemented");
1778     },
1779
1780     userObjectsMapAndFlag: function()
1781     {
1782         throw new Error("Not implemented");
1783     },
1784
1785     /**
1786      * @param {string} baseSnapshotId
1787      * @param {!Object.<string, !WebInspector.HeapSnapshotCommon.AggregateForDiff>} baseSnapshotAggregates
1788      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Diff>}
1789      */
1790     calculateSnapshotDiff: function(baseSnapshotId, baseSnapshotAggregates)
1791     {
1792         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1793         if (snapshotDiff)
1794             return snapshotDiff;
1795         snapshotDiff = {};
1796
1797         var aggregates = this.aggregates(true, "allObjects");
1798         for (var className in baseSnapshotAggregates) {
1799             var baseAggregate = baseSnapshotAggregates[className];
1800             var diff = this._calculateDiffForClass(baseAggregate, aggregates[className]);
1801             if (diff)
1802                 snapshotDiff[className] = diff;
1803         }
1804         var emptyBaseAggregate = new WebInspector.HeapSnapshotCommon.AggregateForDiff();
1805         for (var className in aggregates) {
1806             if (className in baseSnapshotAggregates)
1807                 continue;
1808             snapshotDiff[className] = this._calculateDiffForClass(emptyBaseAggregate, aggregates[className]);
1809         }
1810
1811         this._snapshotDiffs[baseSnapshotId] = snapshotDiff;
1812         return snapshotDiff;
1813     },
1814
1815     /**
1816      * @param {!WebInspector.HeapSnapshotCommon.AggregateForDiff} baseAggregate
1817      * @param {!WebInspector.HeapSnapshotCommon.Aggregate} aggregate
1818      * @return {?WebInspector.HeapSnapshotCommon.Diff}
1819      */
1820     _calculateDiffForClass: function(baseAggregate, aggregate)
1821     {
1822         var baseIds = baseAggregate.ids;
1823         var baseIndexes = baseAggregate.indexes;
1824         var baseSelfSizes = baseAggregate.selfSizes;
1825
1826         var indexes = aggregate ? aggregate.idxs : [];
1827
1828         var i = 0, l = baseIds.length;
1829         var j = 0, m = indexes.length;
1830         var diff = new WebInspector.HeapSnapshotCommon.Diff();
1831
1832         var nodeB = this.createNode(indexes[j]);
1833         while (i < l && j < m) {
1834             var nodeAId = baseIds[i];
1835             if (nodeAId < nodeB.id()) {
1836                 diff.deletedIndexes.push(baseIndexes[i]);
1837                 diff.removedCount++;
1838                 diff.removedSize += baseSelfSizes[i];
1839                 ++i;
1840             } else if (nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot
1841                 diff.addedIndexes.push(indexes[j]);
1842                 diff.addedCount++;
1843                 diff.addedSize += nodeB.selfSize();
1844                 nodeB.nodeIndex = indexes[++j];
1845             } else { // nodeAId === nodeB.id()
1846                 ++i;
1847                 nodeB.nodeIndex = indexes[++j];
1848             }
1849         }
1850         while (i < l) {
1851             diff.deletedIndexes.push(baseIndexes[i]);
1852             diff.removedCount++;
1853             diff.removedSize += baseSelfSizes[i];
1854             ++i;
1855         }
1856         while (j < m) {
1857             diff.addedIndexes.push(indexes[j]);
1858             diff.addedCount++;
1859             diff.addedSize += nodeB.selfSize();
1860             nodeB.nodeIndex = indexes[++j];
1861         }
1862         diff.countDelta = diff.addedCount - diff.removedCount;
1863         diff.sizeDelta = diff.addedSize - diff.removedSize;
1864         if (!diff.addedCount && !diff.removedCount)
1865             return null;
1866         return diff;
1867     },
1868
1869     _nodeForSnapshotObjectId: function(snapshotObjectId)
1870     {
1871         for (var it = this._allNodes(); it.hasNext(); it.next()) {
1872             if (it.node.id() === snapshotObjectId)
1873                 return it.node;
1874         }
1875         return null;
1876     },
1877
1878     /**
1879      * @param {string} snapshotObjectId
1880      * @return {?string}
1881      */
1882     nodeClassName: function(snapshotObjectId)
1883     {
1884         var node = this._nodeForSnapshotObjectId(snapshotObjectId);
1885         if (node)
1886             return node.className();
1887         return null;
1888     },
1889
1890     /**
1891      * @param {string} name
1892      * @return {!Array.<number>}
1893      */
1894     idsOfObjectsWithName: function(name)
1895     {
1896         var ids = [];
1897         for (var it = this._allNodes(); it.hasNext(); it.next()) {
1898             if (it.item().name() === name)
1899                 ids.push(it.item().id());
1900         }
1901         return ids;
1902     },
1903
1904     /**
1905      * @param {string} snapshotObjectId
1906      * @return {?Array.<string>}
1907      */
1908     dominatorIdsForNode: function(snapshotObjectId)
1909     {
1910         var node = this._nodeForSnapshotObjectId(snapshotObjectId);
1911         if (!node)
1912             return null;
1913         var result = [];
1914         while (!node.isRoot()) {
1915             result.push(node.id());
1916             node.nodeIndex = node.dominatorIndex();
1917         }
1918         return result;
1919     },
1920
1921     /**
1922      * @param {number} nodeIndex
1923      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1924      */
1925     createEdgesProvider: function(nodeIndex)
1926     {
1927         var node = this.createNode(nodeIndex);
1928         var filter = this.containmentEdgesFilter();
1929         var indexProvider = new WebInspector.HeapSnapshotEdgeIndexProvider(this);
1930         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider);
1931     },
1932
1933     /**
1934      * @param {number} nodeIndex
1935      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1936      */
1937     createEdgesProviderForTest: function(nodeIndex, filter)
1938     {
1939         var node = this.createNode(nodeIndex);
1940         var indexProvider = new WebInspector.HeapSnapshotEdgeIndexProvider(this);
1941         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider);
1942     },
1943
1944     /**
1945      * @return {?function(!WebInspector.HeapSnapshotEdge):boolean}
1946      */
1947     retainingEdgesFilter: function()
1948     {
1949         return null;
1950     },
1951
1952     /**
1953      * @return {?function(!WebInspector.HeapSnapshotEdge):boolean}
1954      */
1955     containmentEdgesFilter: function()
1956     {
1957         return null;
1958     },
1959
1960     /**
1961      * @param {number} nodeIndex
1962      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1963      */
1964     createRetainingEdgesProvider: function(nodeIndex)
1965     {
1966         var node = this.createNode(nodeIndex);
1967         var filter = this.retainingEdgesFilter();
1968         var indexProvider = new WebInspector.HeapSnapshotRetainerEdgeIndexProvider(this);
1969         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.retainers(), indexProvider);
1970     },
1971
1972     /**
1973      * @param {string} baseSnapshotId
1974      * @param {string} className
1975      * @return {!WebInspector.HeapSnapshotNodesProvider}
1976      */
1977     createAddedNodesProvider: function(baseSnapshotId, className)
1978     {
1979         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1980         var diffForClass = snapshotDiff[className];
1981         return new WebInspector.HeapSnapshotNodesProvider(this, null, diffForClass.addedIndexes);
1982     },
1983
1984     /**
1985      * @param {!Array.<number>} nodeIndexes
1986      * @return {!WebInspector.HeapSnapshotNodesProvider}
1987      */
1988     createDeletedNodesProvider: function(nodeIndexes)
1989     {
1990         return new WebInspector.HeapSnapshotNodesProvider(this, null, nodeIndexes);
1991     },
1992
1993     /**
1994      * @return {?function(!WebInspector.HeapSnapshotNode):boolean}
1995      */
1996     classNodesFilter: function()
1997     {
1998         return null;
1999     },
2000
2001     /**
2002      * @param {string} className
2003      * @param {!WebInspector.HeapSnapshotCommon.NodeFilter} nodeFilter
2004      * @return {!WebInspector.HeapSnapshotNodesProvider}
2005      */
2006     createNodesProviderForClass: function(className, nodeFilter)
2007     {
2008         return new WebInspector.HeapSnapshotNodesProvider(this, this.classNodesFilter(), this.aggregatesWithFilter(nodeFilter)[className].idxs);
2009     },
2010
2011     /**
2012      * @param {number} nodeIndex
2013      * @return {!WebInspector.HeapSnapshotNodesProvider}
2014      */
2015     createNodesProviderForDominator: function(nodeIndex)
2016     {
2017         var node = this.createNode(nodeIndex);
2018         return new WebInspector.HeapSnapshotNodesProvider(this, null, this._dominatedNodesOfNode(node));
2019     },
2020
2021     /**
2022      * @return {number}
2023      */
2024     _maxJsNodeId: function()
2025     {
2026         var nodeFieldCount = this._nodeFieldCount;
2027         var nodes = this._nodes;
2028         var nodesLength = nodes.length;
2029         var id = 0;
2030         for (var nodeIndex = this._nodeIdOffset; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
2031             var nextId = nodes[nodeIndex];
2032             // JS objects have odd ids, skip native objects.
2033             if (nextId % 2 === 0)
2034                 continue;
2035             if (id < nextId)
2036                 id = nextId;
2037         }
2038         return id;
2039     },
2040
2041     /**
2042      * @return {!WebInspector.HeapSnapshotCommon.StaticData}
2043      */
2044     updateStaticData: function()
2045     {
2046         return new WebInspector.HeapSnapshotCommon.StaticData(this.nodeCount, this._rootNodeIndex, this.totalSize, this._maxJsNodeId());
2047     }
2048 };
2049
2050 /**
2051  * @constructor
2052  * @param {!WebInspector.HeapSnapshotItemIterator} iterator
2053  * @param {!WebInspector.HeapSnapshotItemIndexProvider} indexProvider
2054  */
2055 WebInspector.HeapSnapshotItemProvider = function(iterator, indexProvider)
2056 {
2057     this._iterator = iterator;
2058     this._indexProvider = indexProvider;
2059     this._isEmpty = !iterator.hasNext();
2060     /** @type {?Array.<number>} */
2061     this._iterationOrder = null;
2062     this._currentComparator = null;
2063     this._sortedPrefixLength = 0;
2064     this._sortedSuffixLength = 0;
2065 }
2066
2067 WebInspector.HeapSnapshotItemProvider.prototype = {
2068     _createIterationOrder: function()
2069     {
2070         if (this._iterationOrder)
2071             return;
2072         this._iterationOrder = [];
2073         for (var iterator = this._iterator; iterator.hasNext(); iterator.next())
2074             this._iterationOrder.push(iterator.item().itemIndex());
2075     },
2076
2077     /**
2078      * @return {boolean}
2079      */
2080     isEmpty: function()
2081     {
2082         return this._isEmpty;
2083     },
2084
2085     /**
2086      * @param {number} begin
2087      * @param {number} end
2088      * @return {!WebInspector.HeapSnapshotCommon.ItemsRange}
2089      */
2090     serializeItemsRange: function(begin, end)
2091     {
2092         this._createIterationOrder();
2093         if (begin > end)
2094             throw new Error("Start position > end position: " + begin + " > " + end);
2095         if (end > this._iterationOrder.length)
2096             end = this._iterationOrder.length;
2097         if (this._sortedPrefixLength < end && begin < this._iterationOrder.length - this._sortedSuffixLength) {
2098             this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1 - this._sortedSuffixLength, begin, end - 1);
2099             if (begin <= this._sortedPrefixLength)
2100                 this._sortedPrefixLength = end;
2101             if (end >= this._iterationOrder.length - this._sortedSuffixLength)
2102                 this._sortedSuffixLength = this._iterationOrder.length - begin;
2103         }
2104         var position = begin;
2105         var count = end - begin;
2106         var result = new Array(count);
2107         var iterator = this._iterator;
2108         for (var i = 0 ; i < count; ++i) {
2109             var itemIndex = this._iterationOrder[position++];
2110             var item = this._indexProvider.itemForIndex(itemIndex);
2111             result[i] = item.serialize();
2112         }
2113         return new WebInspector.HeapSnapshotCommon.ItemsRange(begin, end, this._iterationOrder.length, result);
2114     },
2115
2116     sortAndRewind: function(comparator)
2117     {
2118         this._currentComparator = comparator;
2119         this._sortedPrefixLength = 0;
2120         this._sortedSuffixLength = 0;
2121     }
2122 }
2123
2124 /**
2125  * @constructor
2126  * @extends {WebInspector.HeapSnapshotItemProvider}
2127  * @param {!WebInspector.HeapSnapshotItemIndexProvider} indexProvider
2128  */
2129 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, filter, edgesIter, indexProvider)
2130 {
2131     this.snapshot = snapshot;
2132     if (filter)
2133         edgesIter = new WebInspector.HeapSnapshotFilteredIterator(edgesIter, filter);
2134     WebInspector.HeapSnapshotItemProvider.call(this, edgesIter, indexProvider);
2135 }
2136
2137 WebInspector.HeapSnapshotEdgesProvider.prototype = {
2138     /**
2139      * @param {!WebInspector.HeapSnapshotCommon.ComparatorConfig} comparator
2140      * @param {number} leftBound
2141      * @param {number} rightBound
2142      * @param {number} windowLeft
2143      * @param {number} windowRight
2144      */
2145     sort: function(comparator, leftBound, rightBound, windowLeft, windowRight)
2146     {
2147         var fieldName1 = comparator.fieldName1;
2148         var fieldName2 = comparator.fieldName2;
2149         var ascending1 = comparator.ascending1;
2150         var ascending2 = comparator.ascending2;
2151
2152         var edgeA = this._iterator.item().clone();
2153         var edgeB = edgeA.clone();
2154         var nodeA = this.snapshot.createNode();
2155         var nodeB = this.snapshot.createNode();
2156
2157         function compareEdgeFieldName(ascending, indexA, indexB)
2158         {
2159             edgeA.edgeIndex = indexA;
2160             edgeB.edgeIndex = indexB;
2161             if (edgeB.name() === "__proto__") return -1;
2162             if (edgeA.name() === "__proto__") return 1;
2163             var result =
2164                 edgeA.hasStringName() === edgeB.hasStringName() ?
2165                 (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) :
2166                 (edgeA.hasStringName() ? -1 : 1);
2167             return ascending ? result : -result;
2168         }
2169
2170         function compareNodeField(fieldName, ascending, indexA, indexB)
2171         {
2172             edgeA.edgeIndex = indexA;
2173             nodeA.nodeIndex = edgeA.nodeIndex();
2174             var valueA = nodeA[fieldName]();
2175
2176             edgeB.edgeIndex = indexB;
2177             nodeB.nodeIndex = edgeB.nodeIndex();
2178             var valueB = nodeB[fieldName]();
2179
2180             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
2181             return ascending ? result : -result;
2182         }
2183
2184         function compareEdgeAndNode(indexA, indexB) {
2185             var result = compareEdgeFieldName(ascending1, indexA, indexB);
2186             if (result === 0)
2187                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
2188             if (result === 0)
2189                 return indexA - indexB;
2190             return result;
2191         }
2192
2193         function compareNodeAndEdge(indexA, indexB) {
2194             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
2195             if (result === 0)
2196                 result = compareEdgeFieldName(ascending2, indexA, indexB);
2197             if (result === 0)
2198                 return indexA - indexB;
2199             return result;
2200         }
2201
2202         function compareNodeAndNode(indexA, indexB) {
2203             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
2204             if (result === 0)
2205                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
2206             if (result === 0)
2207                 return indexA - indexB;
2208             return result;
2209         }
2210
2211         if (fieldName1 === "!edgeName")
2212             this._iterationOrder.sortRange(compareEdgeAndNode, leftBound, rightBound, windowLeft, windowRight);
2213         else if (fieldName2 === "!edgeName")
2214             this._iterationOrder.sortRange(compareNodeAndEdge, leftBound, rightBound, windowLeft, windowRight);
2215         else
2216             this._iterationOrder.sortRange(compareNodeAndNode, leftBound, rightBound, windowLeft, windowRight);
2217     },
2218
2219     __proto__: WebInspector.HeapSnapshotItemProvider.prototype
2220 }
2221
2222
2223 /**
2224  * @constructor
2225  * @extends {WebInspector.HeapSnapshotItemProvider}
2226  * @param {?function(!WebInspector.HeapSnapshotNode):boolean} filter
2227  * @param {(!Array.<number>|!Uint32Array)} nodeIndexes
2228  */
2229 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
2230 {
2231     this.snapshot = snapshot;
2232     var indexProvider = new WebInspector.HeapSnapshotNodeIndexProvider(snapshot);
2233     var it = new WebInspector.HeapSnapshotIndexRangeIterator(indexProvider, nodeIndexes);
2234     if (filter)
2235         it = new WebInspector.HeapSnapshotFilteredIterator(it, filter);
2236     WebInspector.HeapSnapshotItemProvider.call(this, it, indexProvider);
2237 }
2238
2239 WebInspector.HeapSnapshotNodesProvider.prototype = {
2240     /**
2241      * @param {string} snapshotObjectId
2242      * @return {number}
2243      */
2244     nodePosition: function(snapshotObjectId)
2245     {
2246         this._createIterationOrder();
2247         var node = this.snapshot.createNode();
2248         for (var i = 0; i < this._iterationOrder.length; i++) {
2249             node.nodeIndex = this._iterationOrder[i];
2250             if (node.id() === snapshotObjectId)
2251                 break;
2252         }
2253         if (i === this._iterationOrder.length)
2254             return -1;
2255         var targetNodeIndex = this._iterationOrder[i];
2256         var smallerCount = 0;
2257         var compare = this._buildCompareFunction(this._currentComparator);
2258         for (var i = 0; i < this._iterationOrder.length; i++) {
2259             if (compare(this._iterationOrder[i], targetNodeIndex) < 0)
2260                 ++smallerCount;
2261         }
2262         return smallerCount;
2263     },
2264
2265     /**
2266      * @return {function(number,number):number}
2267      */
2268     _buildCompareFunction: function(comparator)
2269     {
2270         var nodeA = this.snapshot.createNode();
2271         var nodeB = this.snapshot.createNode();
2272         var fieldAccessor1 = nodeA[comparator.fieldName1];
2273         var fieldAccessor2 = nodeA[comparator.fieldName2];
2274         var ascending1 = comparator.ascending1 ? 1 : -1;
2275         var ascending2 = comparator.ascending2 ? 1 : -1;
2276
2277         /**
2278          * @param {function():*} fieldAccessor
2279          * @param {number} ascending
2280          * @return {number}
2281          */
2282         function sortByNodeField(fieldAccessor, ascending)
2283         {
2284             var valueA = fieldAccessor.call(nodeA);
2285             var valueB = fieldAccessor.call(nodeB);
2286             return valueA < valueB ? -ascending : (valueA > valueB ? ascending : 0);
2287         }
2288
2289         /**
2290          * @param {number} indexA
2291          * @param {number} indexB
2292          * @return {number}
2293          */
2294         function sortByComparator(indexA, indexB)
2295         {
2296             nodeA.nodeIndex = indexA;
2297             nodeB.nodeIndex = indexB;
2298             var result = sortByNodeField(fieldAccessor1, ascending1);
2299             if (result === 0)
2300                 result = sortByNodeField(fieldAccessor2, ascending2);
2301             return result || indexA - indexB;
2302         }
2303
2304         return sortByComparator;
2305     },
2306
2307     /**
2308      * @param {number} leftBound
2309      * @param {number} rightBound
2310      * @param {number} windowLeft
2311      * @param {number} windowRight
2312      */
2313     sort: function(comparator, leftBound, rightBound, windowLeft, windowRight)
2314     {
2315         this._iterationOrder.sortRange(this._buildCompareFunction(comparator), leftBound, rightBound, windowLeft, windowRight);
2316     },
2317
2318     __proto__: WebInspector.HeapSnapshotItemProvider.prototype
2319 }
2320