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