src/third_party/WebKit/Source/devtools/front_end/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  * @param {function(!WebInspector.HeapSnapshotItem):boolean=} filter
 733  */
 734 WebInspector.HeapSnapshotFilteredIterator = function(iterator, filter)
 735 {
 736     this._iterator = iterator;
 737     this._filter = filter;
 738     this._skipFilteredItems();
 739 }
 740
 741 WebInspector.HeapSnapshotFilteredIterator.prototype = {
 742     /**
 743      * @return {boolean}
 744      */
 745     hasNext: function()
 746     {
 747         return this._iterator.hasNext();
 748     },
 749
 750     /**
 751      * @return {!WebInspector.HeapSnapshotItem}
 752      */
 753     item: function()
 754     {
 755         return this._iterator.item();
 756     },
 757
 758     next: function()
 759     {
 760         this._iterator.next();
 761         this._skipFilteredItems();
 762     },
 763
 764     _skipFilteredItems: function()
 765     {
 766         while (this._iterator.hasNext() && !this._filter(this._iterator.item())) {
 767             this._iterator.next();
 768         }
 769     }
 770 }
 771
 772
 773 /**
 774  * @param {!WebInspector.HeapSnapshotWorkerDispatcher=} dispatcher
 775  * @constructor
 776  */
 777 WebInspector.HeapSnapshotProgress = function(dispatcher)
 778 {
 779     this._dispatcher = dispatcher;
 780 }
 781
 782 WebInspector.HeapSnapshotProgress.prototype = {
 783     /**
 784      * @param {string} status
 785      */
 786     updateStatus: function(status)
 787     {
 788         this._sendUpdateEvent(WebInspector.UIString(status));
 789     },
 790
 791     /**
 792      * @param {string} title
 793      * @param {number} value
 794      * @param {number} total
 795      */
 796     updateProgress: function(title, value, total)
 797     {
 798         var percentValue = ((total ? (value / total) : 0) * 100).toFixed(0);
 799         this._sendUpdateEvent(WebInspector.UIString(title, percentValue));
 800     },
 801
 802     /**
 803      * @param {string} text
 804      */
 805     _sendUpdateEvent: function(text)
 806     {
 807         // May be undefined in tests.
 808         if (this._dispatcher)
 809             this._dispatcher.sendEvent(WebInspector.HeapSnapshotProgressEvent.Update, text);
 810     }
 811 }
 812
 813
 814 /**
 815  * @param {!Object} profile
 816  * @param {!WebInspector.HeapSnapshotProgress} progress
 817  * @constructor
 818  */
 819 WebInspector.HeapSnapshot = function(profile, progress)
 820 {
 821     /** @type {!Uint32Array} */
 822     this.nodes = profile.nodes;
 823     /** @type {!Uint32Array} */
 824     this.containmentEdges = profile.edges;
 825     /** @type {!HeapSnapshotMetainfo} */
 826     this._metaNode = profile.snapshot.meta;
 827     /** @type {!Array.<string>} */
 828     this.strings = profile.strings;
 829     this._progress = progress;
 830
 831     this._noDistance = -5;
 832     this._rootNodeIndex = 0;
 833     if (profile.snapshot.root_index)
 834         this._rootNodeIndex = profile.snapshot.root_index;
 835
 836     this._snapshotDiffs = {};
 837     this._aggregatesForDiff = null;
 838     this._aggregates = {};
 839     this._aggregatesSortedFlags = {};
 840
 841     this._init();
 842
 843     if (profile.snapshot.trace_function_count) {
 844         this._progress.updateStatus("Buiding allocation statistics\u2026");
 845         var nodes = this.nodes;
 846         var nodesLength = nodes.length;
 847         var nodeFieldCount = this._nodeFieldCount;
 848         var node = this.rootNode();
 849         var liveObjects = {};
 850         for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
 851             node.nodeIndex = nodeIndex;
 852             var traceNodeId = node.traceNodeId();
 853             var stats = liveObjects[traceNodeId];
 854             if (!stats) {
 855                 liveObjects[traceNodeId] = stats = { count: 0, size: 0, ids: []};
 856             }
 857             stats.count++;
 858             stats.size += node.selfSize();
 859             stats.ids.push(node.id());
 860         }
 861         this._allocationProfile = new WebInspector.AllocationProfile(profile, liveObjects);
 862         this._progress.updateStatus("Done");
 863     }
 864 }
 865
 866 /**
 867  * @constructor
 868  */
 869 function HeapSnapshotMetainfo()
 870 {
 871     // New format.
 872     this.node_fields = [];
 873     this.node_types = [];
 874     this.edge_fields = [];
 875     this.edge_types = [];
 876     this.trace_function_info_fields = [];
 877     this.trace_node_fields = [];
 878     this.type_strings = {};
 879 }
 880
 881 /**
 882  * @constructor
 883  */
 884 function HeapSnapshotHeader()
 885 {
 886     // New format.
 887     this.title = "";
 888     this.meta = new HeapSnapshotMetainfo();
 889     this.node_count = 0;
 890     this.edge_count = 0;
 891 }
 892
 893 WebInspector.HeapSnapshot.prototype = {
 894     _init: function()
 895     {
 896         var meta = this._metaNode;
 897
 898         this._nodeTypeOffset = meta.node_fields.indexOf("type");
 899         this._nodeNameOffset = meta.node_fields.indexOf("name");
 900         this._nodeIdOffset = meta.node_fields.indexOf("id");
 901         this._nodeSelfSizeOffset = meta.node_fields.indexOf("self_size");
 902         this._nodeEdgeCountOffset = meta.node_fields.indexOf("edge_count");
 903         this._nodeTraceNodeIdOffset = meta.node_fields.indexOf("trace_node_id");
 904         this._nodeFieldCount = meta.node_fields.length;
 905
 906         this._nodeTypes = meta.node_types[this._nodeTypeOffset];
 907         this._nodeHiddenType = this._nodeTypes.indexOf("hidden");
 908         this._nodeObjectType = this._nodeTypes.indexOf("object");
 909         this._nodeNativeType = this._nodeTypes.indexOf("native");
 910         this._nodeConsStringType = this._nodeTypes.indexOf("concatenated string");
 911         this._nodeSlicedStringType = this._nodeTypes.indexOf("sliced string");
 912         this._nodeCodeType = this._nodeTypes.indexOf("code");
 913         this._nodeSyntheticType = this._nodeTypes.indexOf("synthetic");
 914
 915         this._edgeFieldsCount = meta.edge_fields.length;
 916         this._edgeTypeOffset = meta.edge_fields.indexOf("type");
 917         this._edgeNameOffset = meta.edge_fields.indexOf("name_or_index");
 918         this._edgeToNodeOffset = meta.edge_fields.indexOf("to_node");
 919
 920         this._edgeTypes = meta.edge_types[this._edgeTypeOffset];
 921         this._edgeTypes.push("invisible");
 922         this._edgeElementType = this._edgeTypes.indexOf("element");
 923         this._edgeHiddenType = this._edgeTypes.indexOf("hidden");
 924         this._edgeInternalType = this._edgeTypes.indexOf("internal");
 925         this._edgeShortcutType = this._edgeTypes.indexOf("shortcut");
 926         this._edgeWeakType = this._edgeTypes.indexOf("weak");
 927         this._edgeInvisibleType = this._edgeTypes.indexOf("invisible");
 928
 929         this.nodeCount = this.nodes.length / this._nodeFieldCount;
 930         this._edgeCount = this.containmentEdges.length / this._edgeFieldsCount;
 931
 932         this._progress.updateStatus("Building edge indexes\u2026");
 933         this._buildEdgeIndexes();
 934         this._progress.updateStatus("Building retainers\u2026");
 935         this._buildRetainers();
 936         this._progress.updateStatus("Calculating node flags\u2026");
 937         this._calculateFlags();
 938         this._progress.updateStatus("Calculating distances\u2026");
 939         this._calculateDistances();
 940         this._progress.updateStatus("Building postorder index\u2026");
 941         var result = this._buildPostOrderIndex();
 942         // Actually it is array that maps node ordinal number to dominator node ordinal number.
 943         this._progress.updateStatus("Building dominator tree\u2026");
 944         this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex);
 945         this._progress.updateStatus("Calculating retained sizes\u2026");
 946         this._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal);
 947         this._progress.updateStatus("Buiding dominated nodes\u2026");
 948         this._buildDominatedNodes();
 949         this._progress.updateStatus("Calculating statistics\u2026");
 950         this._calculateStatistics();
 951         this._progress.updateStatus("Finished processing.");
 952     },
 953
 954     _buildEdgeIndexes: function()
 955     {
 956         var nodes = this.nodes;
 957         var nodeCount = this.nodeCount;
 958         var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1);
 959         var nodeFieldCount = this._nodeFieldCount;
 960         var edgeFieldsCount = this._edgeFieldsCount;
 961         var nodeEdgeCountOffset = this._nodeEdgeCountOffset;
 962         firstEdgeIndexes[nodeCount] = this.containmentEdges.length;
 963         for (var nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) {
 964             firstEdgeIndexes[nodeOrdinal] = edgeIndex;
 965             edgeIndex += nodes[nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset] * edgeFieldsCount;
 966         }
 967     },
 968
 969     _buildRetainers: function()
 970     {
 971         var retainingNodes = this._retainingNodes = new Uint32Array(this._edgeCount);
 972         var retainingEdges = this._retainingEdges = new Uint32Array(this._edgeCount);
 973         // Index of the first retainer in the _retainingNodes and _retainingEdges
 974         // arrays. Addressed by retained node index.
 975         var firstRetainerIndex = this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1);
 976
 977         var containmentEdges = this.containmentEdges;
 978         var edgeFieldsCount = this._edgeFieldsCount;
 979         var nodeFieldCount = this._nodeFieldCount;
 980         var edgeToNodeOffset = this._edgeToNodeOffset;
 981         var firstEdgeIndexes = this._firstEdgeIndexes;
 982         var nodeCount = this.nodeCount;
 983
 984         for (var toNodeFieldIndex = edgeToNodeOffset, l = containmentEdges.length; toNodeFieldIndex < l; toNodeFieldIndex += edgeFieldsCount) {
 985             var toNodeIndex = containmentEdges[toNodeFieldIndex];
 986             if (toNodeIndex % nodeFieldCount)
 987                 throw new Error("Invalid toNodeIndex " + toNodeIndex);
 988             ++firstRetainerIndex[toNodeIndex / nodeFieldCount];
 989         }
 990         for (var i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) {
 991             var retainersCount = firstRetainerIndex[i];
 992             firstRetainerIndex[i] = firstUnusedRetainerSlot;
 993             retainingNodes[firstUnusedRetainerSlot] = retainersCount;
 994             firstUnusedRetainerSlot += retainersCount;
 995         }
 996         firstRetainerIndex[nodeCount] = retainingNodes.length;
 997
 998         var nextNodeFirstEdgeIndex = firstEdgeIndexes[0];
 999         for (var srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) {
1000             var firstEdgeIndex = nextNodeFirstEdgeIndex;
1001             nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1];
1002             var srcNodeIndex = srcNodeOrdinal * nodeFieldCount;
1003             for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) {
1004                 var toNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1005                 if (toNodeIndex % nodeFieldCount)
1006                     throw new Error("Invalid toNodeIndex " + toNodeIndex);
1007                 var firstRetainerSlotIndex = firstRetainerIndex[toNodeIndex / nodeFieldCount];
1008                 var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]);
1009                 retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex;
1010                 retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex;
1011             }
1012         }
1013     },
1014
1015     /**
1016      * @param {number=} nodeIndex
1017      */
1018     createNode: function(nodeIndex)
1019     {
1020         throw new Error("Not implemented");
1021     },
1022
1023     /**
1024      * @param {number} edgeIndex
1025      * @return {!WebInspector.JSHeapSnapshotEdge}
1026      */
1027     createEdge: function(edgeIndex)
1028     {
1029         throw new Error("Not implemented");
1030     },
1031
1032     /**
1033      * @param {number} retainerIndex
1034      * @return {!WebInspector.JSHeapSnapshotRetainerEdge}
1035      */
1036     createRetainingEdge: function(retainerIndex)
1037     {
1038         throw new Error("Not implemented");
1039     },
1040
1041     _allNodes: function()
1042     {
1043         return new WebInspector.HeapSnapshotNodeIterator(this.rootNode());
1044     },
1045
1046     /**
1047      * @return {!WebInspector.HeapSnapshotNode}
1048      */
1049     rootNode: function()
1050     {
1051         return this.createNode(this._rootNodeIndex);
1052     },
1053
1054     get rootNodeIndex()
1055     {
1056         return this._rootNodeIndex;
1057     },
1058
1059     get totalSize()
1060     {
1061         return this.rootNode().retainedSize();
1062     },
1063
1064     _getDominatedIndex: function(nodeIndex)
1065     {
1066         if (nodeIndex % this._nodeFieldCount)
1067             throw new Error("Invalid nodeIndex: " + nodeIndex);
1068         return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount];
1069     },
1070
1071     /**
1072      * @param {!WebInspector.HeapSnapshotCommon.NodeFilter} nodeFilter
1073      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Aggregate>}
1074      */
1075     aggregatesWithFilter: function(nodeFilter)
1076     {
1077         var minNodeId = nodeFilter.minNodeId;
1078         var maxNodeId = nodeFilter.maxNodeId;
1079         var allocationNodeId = nodeFilter.allocationNodeId;
1080         var key;
1081         var filter;
1082         if (typeof allocationNodeId === "number") {
1083             filter = this._createAllocationStackFilter(allocationNodeId);
1084         } else if (typeof minNodeId === "number" && typeof maxNodeId === "number") {
1085             key = minNodeId + ".." + maxNodeId;
1086             filter = this._createNodeIdFilter(minNodeId, maxNodeId);
1087         } else {
1088             key = "allObjects";
1089         }
1090         return this.aggregates(false, key, filter);
1091     },
1092
1093     /**
1094      * @param {number} minNodeId
1095      * @param {number} maxNodeId
1096      * @return {function(!WebInspector.HeapSnapshotNode):boolean}
1097      */
1098     _createNodeIdFilter: function(minNodeId, maxNodeId)
1099     {
1100         /**
1101          * @param {!WebInspector.HeapSnapshotNode} node
1102          * @return {boolean}
1103          */
1104         function nodeIdFilter(node)
1105         {
1106             var id = node.id();
1107             return id > minNodeId && id <= maxNodeId;
1108         }
1109         return nodeIdFilter;
1110     },
1111
1112     /**
1113      * @param {number} bottomUpAllocationNodeId
1114      * @return {function(!WebInspector.HeapSnapshotNode):boolean|undefined}
1115      */
1116     _createAllocationStackFilter: function(bottomUpAllocationNodeId)
1117     {
1118         var traceIds = this._allocationProfile.traceIds(bottomUpAllocationNodeId);
1119         if (!traceIds.length)
1120             return undefined;
1121         var set = {};
1122         for (var i = 0; i < traceIds.length; i++)
1123             set[traceIds[i]] = true;
1124         /**
1125          * @param {!WebInspector.HeapSnapshotNode} node
1126          * @return {boolean}
1127          */
1128         function traceIdFilter(node)
1129         {
1130             return !!set[node.traceNodeId()];
1131         };
1132         return traceIdFilter;
1133     },
1134
1135     /**
1136      * @param {boolean} sortedIndexes
1137      * @param {string=} key
1138      * @param {function(!WebInspector.HeapSnapshotNode):boolean=} filter
1139      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Aggregate>}
1140      */
1141     aggregates: function(sortedIndexes, key, filter)
1142     {
1143         var aggregatesByClassName = key && this._aggregates[key];
1144         if (!aggregatesByClassName) {
1145             var aggregates = this._buildAggregates(filter);
1146             this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter);
1147             aggregatesByClassName = aggregates.aggregatesByClassName;
1148             if (key)
1149                 this._aggregates[key] = aggregatesByClassName;
1150         }
1151
1152         if (sortedIndexes && (!key || !this._aggregatesSortedFlags[key])) {
1153             this._sortAggregateIndexes(aggregatesByClassName);
1154             if (key)
1155                 this._aggregatesSortedFlags[key] = sortedIndexes;
1156         }
1157         return aggregatesByClassName;
1158     },
1159
1160     /**
1161      * @return {!Array.<!WebInspector.HeapSnapshotCommon.SerializedAllocationNode>}
1162      */
1163     allocationTracesTops: function()
1164     {
1165         return this._allocationProfile.serializeTraceTops();
1166     },
1167
1168     /**
1169      * @param {number} nodeId
1170      * @return {!WebInspector.HeapSnapshotCommon.AllocationNodeCallers}
1171      */
1172     allocationNodeCallers: function(nodeId)
1173     {
1174         return this._allocationProfile.serializeCallers(nodeId);
1175     },
1176
1177     /**
1178      * @param {number} nodeIndex
1179      * @return {?Array.<!WebInspector.HeapSnapshotCommon.AllocationStackFrame>}
1180      */
1181     allocationStack: function(nodeIndex)
1182     {
1183         var node = this.createNode(nodeIndex);
1184         var allocationNodeId = node.traceNodeId();
1185         if (!allocationNodeId)
1186             return null;
1187         return this._allocationProfile.serializeAllocationStack(allocationNodeId);
1188     },
1189
1190     /**
1191      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.AggregateForDiff>}
1192      */
1193     aggregatesForDiff: function()
1194     {
1195         if (this._aggregatesForDiff)
1196             return this._aggregatesForDiff;
1197
1198         var aggregatesByClassName = this.aggregates(true, "allObjects");
1199         this._aggregatesForDiff  = {};
1200
1201         var node = this.createNode();
1202         for (var className in aggregatesByClassName) {
1203             var aggregate = aggregatesByClassName[className];
1204             var indexes = aggregate.idxs;
1205             var ids = new Array(indexes.length);
1206             var selfSizes = new Array(indexes.length);
1207             for (var i = 0; i < indexes.length; i++) {
1208                 node.nodeIndex = indexes[i];
1209                 ids[i] = node.id();
1210                 selfSizes[i] = node.selfSize();
1211             }
1212
1213             this._aggregatesForDiff[className] = {
1214                 indexes: indexes,
1215                 ids: ids,
1216                 selfSizes: selfSizes
1217             };
1218         }
1219         return this._aggregatesForDiff;
1220     },
1221
1222     /**
1223      * @param {!WebInspector.HeapSnapshotNode} node
1224      * @return {!boolean}
1225      */
1226     _isUserRoot: function(node)
1227     {
1228         return true;
1229     },
1230
1231     /**
1232      * @param {function(!WebInspector.HeapSnapshotNode)} action
1233      * @param {boolean=} userRootsOnly
1234      */
1235     forEachRoot: function(action, userRootsOnly)
1236     {
1237         for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) {
1238             var node = iter.edge.node();
1239             if (!userRootsOnly || this._isUserRoot(node))
1240                 action(node);
1241         }
1242     },
1243
1244     _calculateDistances: function()
1245     {
1246         var nodeFieldCount = this._nodeFieldCount;
1247         var nodeCount = this.nodeCount;
1248         var distances = this._nodeDistances = new Int32Array(nodeCount);
1249         var noDistance = this._noDistance;
1250         for (var i = 0; i < nodeCount; ++i)
1251             distances[i] = noDistance;
1252
1253         var nodesToVisit = new Uint32Array(this.nodeCount);
1254         var nodesToVisitLength = 0;
1255
1256         /**
1257          * @param {number} distance
1258          * @param {!WebInspector.HeapSnapshotNode} node
1259          */
1260         function enqueueNode(distance, node)
1261         {
1262             var ordinal = node.ordinal();
1263             if (distances[ordinal] !== noDistance)
1264                 return;
1265             distances[ordinal] = distance;
1266             nodesToVisit[nodesToVisitLength++] = node.nodeIndex;
1267         }
1268
1269         this.forEachRoot(enqueueNode.bind(null, 1), true);
1270         this._bfs(nodesToVisit, nodesToVisitLength, distances);
1271
1272         // bfs for the rest of objects
1273         nodesToVisitLength = 0;
1274         this.forEachRoot(enqueueNode.bind(null, WebInspector.HeapSnapshotCommon.baseSystemDistance), false);
1275         this._bfs(nodesToVisit, nodesToVisitLength, distances);
1276     },
1277
1278     /**
1279      * @param {!Uint32Array} nodesToVisit
1280      * @param {!number} nodesToVisitLength
1281      * @param {!Int32Array} distances
1282      */
1283     _bfs: function(nodesToVisit, nodesToVisitLength, distances)
1284     {
1285         // Preload fields into local variables for better performance.
1286         var edgeFieldsCount = this._edgeFieldsCount;
1287         var nodeFieldCount = this._nodeFieldCount;
1288         var containmentEdges = this.containmentEdges;
1289         var firstEdgeIndexes = this._firstEdgeIndexes;
1290         var edgeToNodeOffset = this._edgeToNodeOffset;
1291         var edgeTypeOffset = this._edgeTypeOffset;
1292         var nodeCount = this.nodeCount;
1293         var containmentEdgesLength = containmentEdges.length;
1294         var edgeWeakType = this._edgeWeakType;
1295         var noDistance = this._noDistance;
1296
1297         var index = 0;
1298         while (index < nodesToVisitLength) {
1299             var nodeIndex = nodesToVisit[index++]; // shift generates too much garbage.
1300             var nodeOrdinal = nodeIndex / nodeFieldCount;
1301             var distance = distances[nodeOrdinal] + 1;
1302             var firstEdgeIndex = firstEdgeIndexes[nodeOrdinal];
1303             var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1];
1304             for (var edgeIndex = firstEdgeIndex; edgeIndex < edgesEnd; edgeIndex += edgeFieldsCount) {
1305                 var edgeType = containmentEdges[edgeIndex + edgeTypeOffset];
1306                 if (edgeType == edgeWeakType)
1307                     continue;
1308                 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1309                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1310                 if (distances[childNodeOrdinal] !== noDistance)
1311                     continue;
1312                 distances[childNodeOrdinal] = distance;
1313                 nodesToVisit[nodesToVisitLength++] = childNodeIndex;
1314             }
1315         }
1316         if (nodesToVisitLength > nodeCount)
1317             throw new Error("BFS failed. Nodes to visit (" + nodesToVisitLength + ") is more than nodes count (" + nodeCount + ")");
1318     },
1319
1320     _buildAggregates: function(filter)
1321     {
1322         var aggregates = {};
1323         var aggregatesByClassName = {};
1324         var classIndexes = [];
1325         var nodes = this.nodes;
1326         var mapAndFlag = this.userObjectsMapAndFlag();
1327         var flags = mapAndFlag ? mapAndFlag.map : null;
1328         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1329         var nodesLength = nodes.length;
1330         var nodeNativeType = this._nodeNativeType;
1331         var nodeFieldCount = this._nodeFieldCount;
1332         var selfSizeOffset = this._nodeSelfSizeOffset;
1333         var nodeTypeOffset = this._nodeTypeOffset;
1334         var node = this.rootNode();
1335         var nodeDistances = this._nodeDistances;
1336
1337         for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
1338             var nodeOrdinal = nodeIndex / nodeFieldCount;
1339             if (flags && !(flags[nodeOrdinal] & flag))
1340                 continue;
1341             node.nodeIndex = nodeIndex;
1342             if (filter && !filter(node))
1343                 continue;
1344             var selfSize = nodes[nodeIndex + selfSizeOffset];
1345             if (!selfSize && nodes[nodeIndex + nodeTypeOffset] !== nodeNativeType)
1346                 continue;
1347             var classIndex = node.classIndex();
1348             if (!(classIndex in aggregates)) {
1349                 var nodeType = node.type();
1350                 var nameMatters = nodeType === "object" || nodeType === "native";
1351                 var value = {
1352                     count: 1,
1353                     distance: nodeDistances[nodeOrdinal],
1354                     self: selfSize,
1355                     maxRet: 0,
1356                     type: nodeType,
1357                     name: nameMatters ? node.name() : null,
1358                     idxs: [nodeIndex]
1359                 };
1360                 aggregates[classIndex] = value;
1361                 classIndexes.push(classIndex);
1362                 aggregatesByClassName[node.className()] = value;
1363             } else {
1364                 var clss = aggregates[classIndex];
1365                 clss.distance = Math.min(clss.distance, nodeDistances[nodeOrdinal]);
1366                 ++clss.count;
1367                 clss.self += selfSize;
1368                 clss.idxs.push(nodeIndex);
1369             }
1370         }
1371
1372         // Shave off provisionally allocated space.
1373         for (var i = 0, l = classIndexes.length; i < l; ++i) {
1374             var classIndex = classIndexes[i];
1375             aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice();
1376         }
1377         return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates};
1378     },
1379
1380     _calculateClassesRetainedSize: function(aggregates, filter)
1381     {
1382         var rootNodeIndex = this._rootNodeIndex;
1383         var node = this.createNode(rootNodeIndex);
1384         var list = [rootNodeIndex];
1385         var sizes = [-1];
1386         var classes = [];
1387         var seenClassNameIndexes = {};
1388         var nodeFieldCount = this._nodeFieldCount;
1389         var nodeTypeOffset = this._nodeTypeOffset;
1390         var nodeNativeType = this._nodeNativeType;
1391         var dominatedNodes = this._dominatedNodes;
1392         var nodes = this.nodes;
1393         var mapAndFlag = this.userObjectsMapAndFlag();
1394         var flags = mapAndFlag ? mapAndFlag.map : null;
1395         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1396         var firstDominatedNodeIndex = this._firstDominatedNodeIndex;
1397
1398         while (list.length) {
1399             var nodeIndex = list.pop();
1400             node.nodeIndex = nodeIndex;
1401             var classIndex = node.classIndex();
1402             var seen = !!seenClassNameIndexes[classIndex];
1403             var nodeOrdinal = nodeIndex / nodeFieldCount;
1404             var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal];
1405             var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1];
1406
1407             if (!seen &&
1408                 (!flags || (flags[nodeOrdinal] & flag)) &&
1409                 (!filter || filter(node)) &&
1410                 (node.selfSize() || nodes[nodeIndex + nodeTypeOffset] === nodeNativeType)
1411                ) {
1412                 aggregates[classIndex].maxRet += node.retainedSize();
1413                 if (dominatedIndexFrom !== dominatedIndexTo) {
1414                     seenClassNameIndexes[classIndex] = true;
1415                     sizes.push(list.length);
1416                     classes.push(classIndex);
1417                 }
1418             }
1419             for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++)
1420                 list.push(dominatedNodes[i]);
1421
1422             var l = list.length;
1423             while (sizes[sizes.length - 1] === l) {
1424                 sizes.pop();
1425                 classIndex = classes.pop();
1426                 seenClassNameIndexes[classIndex] = false;
1427             }
1428         }
1429     },
1430
1431     _sortAggregateIndexes: function(aggregates)
1432     {
1433         var nodeA = this.createNode();
1434         var nodeB = this.createNode();
1435         for (var clss in aggregates)
1436             aggregates[clss].idxs.sort(
1437                 function(idxA, idxB) {
1438                     nodeA.nodeIndex = idxA;
1439                     nodeB.nodeIndex = idxB;
1440                     return nodeA.id() < nodeB.id() ? -1 : 1;
1441                 });
1442     },
1443
1444     _buildPostOrderIndex: function()
1445     {
1446         var nodeFieldCount = this._nodeFieldCount;
1447         var nodes = this.nodes;
1448         var nodeCount = this.nodeCount;
1449         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1450
1451         var edgeFieldsCount = this._edgeFieldsCount;
1452         var edgeTypeOffset = this._edgeTypeOffset;
1453         var edgeToNodeOffset = this._edgeToNodeOffset;
1454         var edgeShortcutType = this._edgeShortcutType;
1455         var firstEdgeIndexes = this._firstEdgeIndexes;
1456         var containmentEdges = this.containmentEdges;
1457
1458         var mapAndFlag = this.userObjectsMapAndFlag();
1459         var flags = mapAndFlag ? mapAndFlag.map : null;
1460         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1461
1462         var stackNodes = new Uint32Array(nodeCount);
1463         var stackCurrentEdge = new Uint32Array(nodeCount);
1464         var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount);
1465         var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount);
1466         var visited = new Uint8Array(nodeCount);
1467         var postOrderIndex = 0;
1468
1469         var stackTop = 0;
1470         stackNodes[0] = rootNodeOrdinal;
1471         stackCurrentEdge[0] = firstEdgeIndexes[rootNodeOrdinal];
1472         visited[rootNodeOrdinal] = 1;
1473
1474         while (stackTop >= 0) {
1475             var nodeOrdinal = stackNodes[stackTop];
1476             var edgeIndex = stackCurrentEdge[stackTop];
1477             var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1];
1478
1479             if (edgeIndex < edgesEnd) {
1480                 stackCurrentEdge[stackTop] += edgeFieldsCount;
1481                 if (nodeOrdinal !== rootNodeOrdinal && containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType)
1482                     continue;
1483                 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset];
1484                 var childNodeOrdinal = childNodeIndex / nodeFieldCount;
1485                 if (visited[childNodeOrdinal])
1486                     continue;
1487                 var nodeFlag = !flags || (flags[nodeOrdinal] & flag);
1488                 var childNodeFlag = !flags || (flags[childNodeOrdinal] & flag);
1489                 // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1490                 // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1491                 if (nodeOrdinal !== rootNodeOrdinal && childNodeFlag && !nodeFlag)
1492                     continue;
1493                 ++stackTop;
1494                 stackNodes[stackTop] = childNodeOrdinal;
1495                 stackCurrentEdge[stackTop] = firstEdgeIndexes[childNodeOrdinal];
1496                 visited[childNodeOrdinal] = 1;
1497             } else {
1498                 // Done with all the node children
1499                 nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex;
1500                 postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal;
1501                 --stackTop;
1502             }
1503         }
1504
1505         if (postOrderIndex !== nodeCount) {
1506             console.log("Error: Corrupted snapshot. " + (nodeCount - postOrderIndex) + " nodes are unreachable from the root:");
1507             var dumpNode = this.rootNode();
1508             for (var i = 0; i < nodeCount; ++i) {
1509                 if (!visited[i]) {
1510                     // Fix it by giving the node a postorder index anyway.
1511                     nodeOrdinal2PostOrderIndex[i] = postOrderIndex;
1512                     postOrderIndex2NodeOrdinal[postOrderIndex++] = i;
1513                     dumpNode.nodeIndex = i * nodeFieldCount;
1514                     console.log(JSON.stringify(dumpNode.serialize()));
1515                     for (var retainers = dumpNode.retainers(); retainers.hasNext(); retainers = retainers.item().node().retainers())
1516                         console.log("  edgeName: " + retainers.item().name() + " nodeClassName: " + retainers.item().node().className());
1517                 }
1518             }
1519         }
1520
1521         return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex};
1522     },
1523
1524     // The algorithm is based on the article:
1525     // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
1526     // Softw. Pract. Exper. 4 (2001), pp. 1-10.
1527     /**
1528      * @param {!Array.<number>} postOrderIndex2NodeOrdinal
1529      * @param {!Array.<number>} nodeOrdinal2PostOrderIndex
1530      */
1531     _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex)
1532     {
1533         var nodeFieldCount = this._nodeFieldCount;
1534         var nodes = this.nodes;
1535         var firstRetainerIndex = this._firstRetainerIndex;
1536         var retainingNodes = this._retainingNodes;
1537         var retainingEdges = this._retainingEdges;
1538         var edgeFieldsCount = this._edgeFieldsCount;
1539         var edgeTypeOffset = this._edgeTypeOffset;
1540         var edgeToNodeOffset = this._edgeToNodeOffset;
1541         var edgeShortcutType = this._edgeShortcutType;
1542         var firstEdgeIndexes = this._firstEdgeIndexes;
1543         var containmentEdges = this.containmentEdges;
1544         var containmentEdgesLength = this.containmentEdges.length;
1545         var rootNodeIndex = this._rootNodeIndex;
1546
1547         var mapAndFlag = this.userObjectsMapAndFlag();
1548         var flags = mapAndFlag ? mapAndFlag.map : null;
1549         var flag = mapAndFlag ? mapAndFlag.flag : 0;
1550
1551         var nodesCount = postOrderIndex2NodeOrdinal.length;
1552         var rootPostOrderedIndex = nodesCount - 1;
1553         var noEntry = nodesCount;
1554         var dominators = new Uint32Array(nodesCount);
1555         for (var i = 0; i < rootPostOrderedIndex; ++i)
1556             dominators[i] = noEntry;
1557         dominators[rootPostOrderedIndex] = rootPostOrderedIndex;
1558
1559         // The affected array is used to mark entries which dominators
1560         // have to be racalculated because of changes in their retainers.
1561         var affected = new Uint8Array(nodesCount);
1562         var nodeOrdinal;
1563
1564         { // Mark the root direct children as affected.
1565             nodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1566             var beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1567             var endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1568             for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1569                  toNodeFieldIndex < endEdgeToNodeFieldIndex;
1570                  toNodeFieldIndex += edgeFieldsCount) {
1571                 var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1572                 affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1573             }
1574         }
1575
1576         var changed = true;
1577         while (changed) {
1578             changed = false;
1579             for (var postOrderIndex = rootPostOrderedIndex - 1; postOrderIndex >= 0; --postOrderIndex) {
1580                 if (affected[postOrderIndex] === 0)
1581                     continue;
1582                 affected[postOrderIndex] = 0;
1583                 // If dominator of the entry has already been set to root,
1584                 // then it can't propagate any further.
1585                 if (dominators[postOrderIndex] === rootPostOrderedIndex)
1586                     continue;
1587                 nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1588                 var nodeFlag = !flags || (flags[nodeOrdinal] & flag);
1589                 var newDominatorIndex = noEntry;
1590                 var beginRetainerIndex = firstRetainerIndex[nodeOrdinal];
1591                 var endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1];
1592                 for (var retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) {
1593                     var retainerEdgeIndex = retainingEdges[retainerIndex];
1594                     var retainerEdgeType = containmentEdges[retainerEdgeIndex + edgeTypeOffset];
1595                     var retainerNodeIndex = retainingNodes[retainerIndex];
1596                     if (retainerNodeIndex !== rootNodeIndex && retainerEdgeType === edgeShortcutType)
1597                         continue;
1598                     var retainerNodeOrdinal = retainerNodeIndex / nodeFieldCount;
1599                     var retainerNodeFlag = !flags || (flags[retainerNodeOrdinal] & flag);
1600                     // We are skipping the edges from non-page-owned nodes to page-owned nodes.
1601                     // Otherwise the dominators for the objects that also were retained by debugger would be affected.
1602                     if (retainerNodeIndex !== rootNodeIndex && nodeFlag && !retainerNodeFlag)
1603                         continue;
1604                     var retanerPostOrderIndex = nodeOrdinal2PostOrderIndex[retainerNodeOrdinal];
1605                     if (dominators[retanerPostOrderIndex] !== noEntry) {
1606                         if (newDominatorIndex === noEntry)
1607                             newDominatorIndex = retanerPostOrderIndex;
1608                         else {
1609                             while (retanerPostOrderIndex !== newDominatorIndex) {
1610                                 while (retanerPostOrderIndex < newDominatorIndex)
1611                                     retanerPostOrderIndex = dominators[retanerPostOrderIndex];
1612                                 while (newDominatorIndex < retanerPostOrderIndex)
1613                                     newDominatorIndex = dominators[newDominatorIndex];
1614                             }
1615                         }
1616                         // If idom has already reached the root, it doesn't make sense
1617                         // to check other retainers.
1618                         if (newDominatorIndex === rootPostOrderedIndex)
1619                             break;
1620                     }
1621                 }
1622                 if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
1623                     dominators[postOrderIndex] = newDominatorIndex;
1624                     changed = true;
1625                     nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1626                     beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset;
1627                     endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1];
1628                     for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex;
1629                          toNodeFieldIndex < endEdgeToNodeFieldIndex;
1630                          toNodeFieldIndex += edgeFieldsCount) {
1631                         var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount;
1632                         affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1;
1633                     }
1634                 }
1635             }
1636         }
1637
1638         var dominatorsTree = new Uint32Array(nodesCount);
1639         for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) {
1640             nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1641             dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]];
1642         }
1643         return dominatorsTree;
1644     },
1645
1646     _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal)
1647     {
1648         var nodeCount = this.nodeCount;
1649         var nodes = this.nodes;
1650         var nodeSelfSizeOffset = this._nodeSelfSizeOffset;
1651         var nodeFieldCount = this._nodeFieldCount;
1652         var dominatorsTree = this._dominatorsTree;
1653         var retainedSizes = this._retainedSizes = new Float64Array(nodeCount);
1654
1655         for (var nodeOrdinal = 0; nodeOrdinal < nodeCount; ++nodeOrdinal)
1656             retainedSizes[nodeOrdinal] = nodes[nodeOrdinal * nodeFieldCount + nodeSelfSizeOffset];
1657
1658         // Propagate retained sizes for each node excluding root.
1659         for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) {
1660             var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex];
1661             var dominatorOrdinal = dominatorsTree[nodeOrdinal];
1662             retainedSizes[dominatorOrdinal] += retainedSizes[nodeOrdinal];
1663         }
1664     },
1665
1666     _buildDominatedNodes: function()
1667     {
1668         // Builds up two arrays:
1669         //  - "dominatedNodes" is a continuous array, where each node owns an
1670         //    interval (can be empty) with corresponding dominated nodes.
1671         //  - "indexArray" is an array of indexes in the "dominatedNodes"
1672         //    with the same positions as in the _nodeIndex.
1673         var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1);
1674         // All nodes except the root have dominators.
1675         var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1);
1676
1677         // Count the number of dominated nodes for each node. Skip the root (node at
1678         // index 0) as it is the only node that dominates itself.
1679         var nodeFieldCount = this._nodeFieldCount;
1680         var dominatorsTree = this._dominatorsTree;
1681
1682         var fromNodeOrdinal = 0;
1683         var toNodeOrdinal = this.nodeCount;
1684         var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount;
1685         if (rootNodeOrdinal === fromNodeOrdinal)
1686             fromNodeOrdinal = 1;
1687         else if (rootNodeOrdinal === toNodeOrdinal - 1)
1688             toNodeOrdinal = toNodeOrdinal - 1;
1689         else
1690             throw new Error("Root node is expected to be either first or last");
1691         for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal)
1692             ++indexArray[dominatorsTree[nodeOrdinal]];
1693         // Put in the first slot of each dominatedNodes slice the count of entries
1694         // that will be filled.
1695         var firstDominatedNodeIndex = 0;
1696         for (var i = 0, l = this.nodeCount; i < l; ++i) {
1697             var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i];
1698             indexArray[i] = firstDominatedNodeIndex;
1699             firstDominatedNodeIndex += dominatedCount;
1700         }
1701         indexArray[this.nodeCount] = dominatedNodes.length;
1702         // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at
1703         // index 0) as it is the only node that dominates itself.
1704         for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) {
1705             var dominatorOrdinal = dominatorsTree[nodeOrdinal];
1706             var dominatedRefIndex = indexArray[dominatorOrdinal];
1707             dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]);
1708             dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount;
1709         }
1710     },
1711
1712     _calculateFlags: function()
1713     {
1714         throw new Error("Not implemented");
1715     },
1716
1717     _calculateStatistics: function()
1718     {
1719         throw new Error("Not implemented");
1720     },
1721
1722     userObjectsMapAndFlag: function()
1723     {
1724         throw new Error("Not implemented");
1725     },
1726
1727     /**
1728      * @param {string} baseSnapshotId
1729      * @param {!Object.<string, !WebInspector.HeapSnapshotCommon.AggregateForDiff>} baseSnapshotAggregates
1730      * @return {!Object.<string, !WebInspector.HeapSnapshotCommon.Diff>}
1731      */
1732     calculateSnapshotDiff: function(baseSnapshotId, baseSnapshotAggregates)
1733     {
1734         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1735         if (snapshotDiff)
1736             return snapshotDiff;
1737         snapshotDiff = {};
1738
1739         var aggregates = this.aggregates(true, "allObjects");
1740         for (var className in baseSnapshotAggregates) {
1741             var baseAggregate = baseSnapshotAggregates[className];
1742             var diff = this._calculateDiffForClass(baseAggregate, aggregates[className]);
1743             if (diff)
1744                 snapshotDiff[className] = diff;
1745         }
1746         var emptyBaseAggregate = new WebInspector.HeapSnapshotCommon.AggregateForDiff();
1747         for (var className in aggregates) {
1748             if (className in baseSnapshotAggregates)
1749                 continue;
1750             snapshotDiff[className] = this._calculateDiffForClass(emptyBaseAggregate, aggregates[className]);
1751         }
1752
1753         this._snapshotDiffs[baseSnapshotId] = snapshotDiff;
1754         return snapshotDiff;
1755     },
1756
1757     /**
1758      * @param {!WebInspector.HeapSnapshotCommon.AggregateForDiff} baseAggregate
1759      * @param {!WebInspector.HeapSnapshotCommon.Aggregate} aggregate
1760      * @return {?WebInspector.HeapSnapshotCommon.Diff}
1761      */
1762     _calculateDiffForClass: function(baseAggregate, aggregate)
1763     {
1764         var baseIds = baseAggregate.ids;
1765         var baseIndexes = baseAggregate.indexes;
1766         var baseSelfSizes = baseAggregate.selfSizes;
1767
1768         var indexes = aggregate ? aggregate.idxs : [];
1769
1770         var i = 0, l = baseIds.length;
1771         var j = 0, m = indexes.length;
1772         var diff = new WebInspector.HeapSnapshotCommon.Diff();
1773
1774         var nodeB = this.createNode(indexes[j]);
1775         while (i < l && j < m) {
1776             var nodeAId = baseIds[i];
1777             if (nodeAId < nodeB.id()) {
1778                 diff.deletedIndexes.push(baseIndexes[i]);
1779                 diff.removedCount++;
1780                 diff.removedSize += baseSelfSizes[i];
1781                 ++i;
1782             } else if (nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot
1783                 diff.addedIndexes.push(indexes[j]);
1784                 diff.addedCount++;
1785                 diff.addedSize += nodeB.selfSize();
1786                 nodeB.nodeIndex = indexes[++j];
1787             } else { // nodeAId === nodeB.id()
1788                 ++i;
1789                 nodeB.nodeIndex = indexes[++j];
1790             }
1791         }
1792         while (i < l) {
1793             diff.deletedIndexes.push(baseIndexes[i]);
1794             diff.removedCount++;
1795             diff.removedSize += baseSelfSizes[i];
1796             ++i;
1797         }
1798         while (j < m) {
1799             diff.addedIndexes.push(indexes[j]);
1800             diff.addedCount++;
1801             diff.addedSize += nodeB.selfSize();
1802             nodeB.nodeIndex = indexes[++j];
1803         }
1804         diff.countDelta = diff.addedCount - diff.removedCount;
1805         diff.sizeDelta = diff.addedSize - diff.removedSize;
1806         if (!diff.addedCount && !diff.removedCount)
1807             return null;
1808         return diff;
1809     },
1810
1811     _nodeForSnapshotObjectId: function(snapshotObjectId)
1812     {
1813         for (var it = this._allNodes(); it.hasNext(); it.next()) {
1814             if (it.node.id() === snapshotObjectId)
1815                 return it.node;
1816         }
1817         return null;
1818     },
1819
1820     /**
1821      * @param {string} snapshotObjectId
1822      * @return {?string}
1823      */
1824     nodeClassName: function(snapshotObjectId)
1825     {
1826         var node = this._nodeForSnapshotObjectId(snapshotObjectId);
1827         if (node)
1828             return node.className();
1829         return null;
1830     },
1831
1832     /**
1833      * @param {string} name
1834      * @return {!Array.<number>}
1835      */
1836     idsOfObjectsWithName: function(name)
1837     {
1838         var ids = [];
1839         for (var it = this._allNodes(); it.hasNext(); it.next()) {
1840             if (it.item().name() === name)
1841                 ids.push(it.item().id());
1842         }
1843         return ids;
1844     },
1845
1846     /**
1847      * @param {number} nodeIndex
1848      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1849      */
1850     createEdgesProvider: function(nodeIndex)
1851     {
1852         var node = this.createNode(nodeIndex);
1853         var filter = this.containmentEdgesFilter();
1854         var indexProvider = new WebInspector.HeapSnapshotEdgeIndexProvider(this);
1855         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider);
1856     },
1857
1858     /**
1859      * @param {number} nodeIndex
1860      * @param {?function(!WebInspector.HeapSnapshotEdge):boolean} filter
1861      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1862      */
1863     createEdgesProviderForTest: function(nodeIndex, filter)
1864     {
1865         var node = this.createNode(nodeIndex);
1866         var indexProvider = new WebInspector.HeapSnapshotEdgeIndexProvider(this);
1867         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges(), indexProvider);
1868     },
1869
1870     /**
1871      * @return {?function(!WebInspector.HeapSnapshotEdge):boolean}
1872      */
1873     retainingEdgesFilter: function()
1874     {
1875         return null;
1876     },
1877
1878     /**
1879      * @return {?function(!WebInspector.HeapSnapshotEdge):boolean}
1880      */
1881     containmentEdgesFilter: function()
1882     {
1883         return null;
1884     },
1885
1886     /**
1887      * @param {number} nodeIndex
1888      * @return {!WebInspector.HeapSnapshotEdgesProvider}
1889      */
1890     createRetainingEdgesProvider: function(nodeIndex)
1891     {
1892         var node = this.createNode(nodeIndex);
1893         var filter = this.retainingEdgesFilter();
1894         var indexProvider = new WebInspector.HeapSnapshotRetainerEdgeIndexProvider(this);
1895         return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.retainers(), indexProvider);
1896     },
1897
1898     /**
1899      * @param {string} baseSnapshotId
1900      * @param {string} className
1901      * @return {!WebInspector.HeapSnapshotNodesProvider}
1902      */
1903     createAddedNodesProvider: function(baseSnapshotId, className)
1904     {
1905         var snapshotDiff = this._snapshotDiffs[baseSnapshotId];
1906         var diffForClass = snapshotDiff[className];
1907         return new WebInspector.HeapSnapshotNodesProvider(this, null, diffForClass.addedIndexes);
1908     },
1909
1910     /**
1911      * @param {!Array.<number>} nodeIndexes
1912      * @return {!WebInspector.HeapSnapshotNodesProvider}
1913      */
1914     createDeletedNodesProvider: function(nodeIndexes)
1915     {
1916         return new WebInspector.HeapSnapshotNodesProvider(this, null, nodeIndexes);
1917     },
1918
1919     /**
1920      * @return {?function(!WebInspector.HeapSnapshotNode):boolean}
1921      */
1922     classNodesFilter: function()
1923     {
1924         return null;
1925     },
1926
1927     /**
1928      * @param {string} className
1929      * @param {!WebInspector.HeapSnapshotCommon.NodeFilter} nodeFilter
1930      * @return {!WebInspector.HeapSnapshotNodesProvider}
1931      */
1932     createNodesProviderForClass: function(className, nodeFilter)
1933     {
1934         return new WebInspector.HeapSnapshotNodesProvider(this, this.classNodesFilter(), this.aggregatesWithFilter(nodeFilter)[className].idxs);
1935     },
1936
1937     /**
1938      * @return {number}
1939      */
1940     _maxJsNodeId: function()
1941     {
1942         var nodeFieldCount = this._nodeFieldCount;
1943         var nodes = this.nodes;
1944         var nodesLength = nodes.length;
1945         var id = 0;
1946         for (var nodeIndex = this._nodeIdOffset; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) {
1947             var nextId = nodes[nodeIndex];
1948             // JS objects have odd ids, skip native objects.
1949             if (nextId % 2 === 0)
1950                 continue;
1951             if (id < nextId)
1952                 id = nextId;
1953         }
1954         return id;
1955     },
1956
1957     /**
1958      * @return {!WebInspector.HeapSnapshotCommon.StaticData}
1959      */
1960     updateStaticData: function()
1961     {
1962         return new WebInspector.HeapSnapshotCommon.StaticData(this.nodeCount, this._rootNodeIndex, this.totalSize, this._maxJsNodeId());
1963     }
1964 };
1965
1966 /**
1967  * @constructor
1968  * @param {!WebInspector.HeapSnapshotItemIterator} iterator
1969  * @param {!WebInspector.HeapSnapshotItemIndexProvider} indexProvider
1970  */
1971 WebInspector.HeapSnapshotItemProvider = function(iterator, indexProvider)
1972 {
1973     this._iterator = iterator;
1974     this._indexProvider = indexProvider;
1975     this._isEmpty = !iterator.hasNext();
1976     /** @type {?Array.<number>} */
1977     this._iterationOrder = null;
1978     this._currentComparator = null;
1979     this._sortedPrefixLength = 0;
1980     this._sortedSuffixLength = 0;
1981 }
1982
1983 WebInspector.HeapSnapshotItemProvider.prototype = {
1984     _createIterationOrder: function()
1985     {
1986         if (this._iterationOrder)
1987             return;
1988         this._iterationOrder = [];
1989         for (var iterator = this._iterator; iterator.hasNext(); iterator.next())
1990             this._iterationOrder.push(iterator.item().itemIndex());
1991     },
1992
1993     /**
1994      * @return {boolean}
1995      */
1996     isEmpty: function()
1997     {
1998         return this._isEmpty;
1999     },
2000
2001     /**
2002      * @param {number} begin
2003      * @param {number} end
2004      * @return {!WebInspector.HeapSnapshotCommon.ItemsRange}
2005      */
2006     serializeItemsRange: function(begin, end)
2007     {
2008         this._createIterationOrder();
2009         if (begin > end)
2010             throw new Error("Start position > end position: " + begin + " > " + end);
2011         if (end > this._iterationOrder.length)
2012             end = this._iterationOrder.length;
2013         if (this._sortedPrefixLength < end && begin < this._iterationOrder.length - this._sortedSuffixLength) {
2014             this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1 - this._sortedSuffixLength, begin, end - 1);
2015             if (begin <= this._sortedPrefixLength)
2016                 this._sortedPrefixLength = end;
2017             if (end >= this._iterationOrder.length - this._sortedSuffixLength)
2018                 this._sortedSuffixLength = this._iterationOrder.length - begin;
2019         }
2020         var position = begin;
2021         var count = end - begin;
2022         var result = new Array(count);
2023         var iterator = this._iterator;
2024         for (var i = 0 ; i < count; ++i) {
2025             var itemIndex = this._iterationOrder[position++];
2026             var item = this._indexProvider.itemForIndex(itemIndex);
2027             result[i] = item.serialize();
2028         }
2029         return new WebInspector.HeapSnapshotCommon.ItemsRange(begin, end, this._iterationOrder.length, result);
2030     },
2031
2032     sortAndRewind: function(comparator)
2033     {
2034         this._currentComparator = comparator;
2035         this._sortedPrefixLength = 0;
2036         this._sortedSuffixLength = 0;
2037     }
2038 }
2039
2040 /**
2041  * @constructor
2042  * @extends {WebInspector.HeapSnapshotItemProvider}
2043  * @param {!WebInspector.HeapSnapshot} snapshot
2044  * @param {?function(!WebInspector.HeapSnapshotEdge):boolean} filter
2045  * @param {!WebInspector.HeapSnapshotEdgeIterator} edgesIter
2046  * @param {!WebInspector.HeapSnapshotItemIndexProvider} indexProvider
2047  */
2048 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, filter, edgesIter, indexProvider)
2049 {
2050     this.snapshot = snapshot;
2051     var iter = filter ? new WebInspector.HeapSnapshotFilteredIterator(edgesIter, /** @type {function(!WebInspector.HeapSnapshotItem):boolean} */ (filter)) : edgesIter;
2052     WebInspector.HeapSnapshotItemProvider.call(this, iter, indexProvider);
2053 }
2054
2055 WebInspector.HeapSnapshotEdgesProvider.prototype = {
2056     /**
2057      * @param {!WebInspector.HeapSnapshotCommon.ComparatorConfig} comparator
2058      * @param {number} leftBound
2059      * @param {number} rightBound
2060      * @param {number} windowLeft
2061      * @param {number} windowRight
2062      */
2063     sort: function(comparator, leftBound, rightBound, windowLeft, windowRight)
2064     {
2065         var fieldName1 = comparator.fieldName1;
2066         var fieldName2 = comparator.fieldName2;
2067         var ascending1 = comparator.ascending1;
2068         var ascending2 = comparator.ascending2;
2069
2070         var edgeA = this._iterator.item().clone();
2071         var edgeB = edgeA.clone();
2072         var nodeA = this.snapshot.createNode();
2073         var nodeB = this.snapshot.createNode();
2074
2075         function compareEdgeFieldName(ascending, indexA, indexB)
2076         {
2077             edgeA.edgeIndex = indexA;
2078             edgeB.edgeIndex = indexB;
2079             if (edgeB.name() === "__proto__") return -1;
2080             if (edgeA.name() === "__proto__") return 1;
2081             var result =
2082                 edgeA.hasStringName() === edgeB.hasStringName() ?
2083                 (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) :
2084                 (edgeA.hasStringName() ? -1 : 1);
2085             return ascending ? result : -result;
2086         }
2087
2088         function compareNodeField(fieldName, ascending, indexA, indexB)
2089         {
2090             edgeA.edgeIndex = indexA;
2091             nodeA.nodeIndex = edgeA.nodeIndex();
2092             var valueA = nodeA[fieldName]();
2093
2094             edgeB.edgeIndex = indexB;
2095             nodeB.nodeIndex = edgeB.nodeIndex();
2096             var valueB = nodeB[fieldName]();
2097
2098             var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0);
2099             return ascending ? result : -result;
2100         }
2101
2102         function compareEdgeAndNode(indexA, indexB) {
2103             var result = compareEdgeFieldName(ascending1, indexA, indexB);
2104             if (result === 0)
2105                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
2106             if (result === 0)
2107                 return indexA - indexB;
2108             return result;
2109         }
2110
2111         function compareNodeAndEdge(indexA, indexB) {
2112             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
2113             if (result === 0)
2114                 result = compareEdgeFieldName(ascending2, indexA, indexB);
2115             if (result === 0)
2116                 return indexA - indexB;
2117             return result;
2118         }
2119
2120         function compareNodeAndNode(indexA, indexB) {
2121             var result = compareNodeField(fieldName1, ascending1, indexA, indexB);
2122             if (result === 0)
2123                 result = compareNodeField(fieldName2, ascending2, indexA, indexB);
2124             if (result === 0)
2125                 return indexA - indexB;
2126             return result;
2127         }
2128
2129         if (fieldName1 === "!edgeName")
2130             this._iterationOrder.sortRange(compareEdgeAndNode, leftBound, rightBound, windowLeft, windowRight);
2131         else if (fieldName2 === "!edgeName")
2132             this._iterationOrder.sortRange(compareNodeAndEdge, leftBound, rightBound, windowLeft, windowRight);
2133         else
2134             this._iterationOrder.sortRange(compareNodeAndNode, leftBound, rightBound, windowLeft, windowRight);
2135     },
2136
2137     __proto__: WebInspector.HeapSnapshotItemProvider.prototype
2138 }
2139
2140
2141 /**
2142  * @constructor
2143  * @extends {WebInspector.HeapSnapshotItemProvider}
2144  * @param {!WebInspector.HeapSnapshot} snapshot
2145  * @param {?function(!WebInspector.HeapSnapshotNode):boolean} filter
2146  * @param {(!Array.<number>|!Uint32Array)} nodeIndexes
2147  */
2148 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes)
2149 {
2150     this.snapshot = snapshot;
2151     var indexProvider = new WebInspector.HeapSnapshotNodeIndexProvider(snapshot);
2152     var it = new WebInspector.HeapSnapshotIndexRangeIterator(indexProvider, nodeIndexes);
2153
2154     if (filter)
2155         it = new WebInspector.HeapSnapshotFilteredIterator(it, /** @type {function(!WebInspector.HeapSnapshotItem):boolean} */ (filter));
2156     WebInspector.HeapSnapshotItemProvider.call(this, it, indexProvider);
2157 }
2158
2159 WebInspector.HeapSnapshotNodesProvider.prototype = {
2160     /**
2161      * @param {string} snapshotObjectId
2162      * @return {number}
2163      */
2164     nodePosition: function(snapshotObjectId)
2165     {
2166         this._createIterationOrder();
2167         var node = this.snapshot.createNode();
2168         for (var i = 0; i < this._iterationOrder.length; i++) {
2169             node.nodeIndex = this._iterationOrder[i];
2170             if (node.id() === snapshotObjectId)
2171                 break;
2172         }
2173         if (i === this._iterationOrder.length)
2174             return -1;
2175         var targetNodeIndex = this._iterationOrder[i];
2176         var smallerCount = 0;
2177         var compare = this._buildCompareFunction(this._currentComparator);
2178         for (var i = 0; i < this._iterationOrder.length; i++) {
2179             if (compare(this._iterationOrder[i], targetNodeIndex) < 0)
2180                 ++smallerCount;
2181         }
2182         return smallerCount;
2183     },
2184
2185     /**
2186      * @return {function(number,number):number}
2187      */
2188     _buildCompareFunction: function(comparator)
2189     {
2190         var nodeA = this.snapshot.createNode();
2191         var nodeB = this.snapshot.createNode();
2192         var fieldAccessor1 = nodeA[comparator.fieldName1];
2193         var fieldAccessor2 = nodeA[comparator.fieldName2];
2194         var ascending1 = comparator.ascending1 ? 1 : -1;
2195         var ascending2 = comparator.ascending2 ? 1 : -1;
2196
2197         /**
2198          * @param {function():*} fieldAccessor
2199          * @param {number} ascending
2200          * @return {number}
2201          */
2202         function sortByNodeField(fieldAccessor, ascending)
2203         {
2204             var valueA = fieldAccessor.call(nodeA);
2205             var valueB = fieldAccessor.call(nodeB);
2206             return valueA < valueB ? -ascending : (valueA > valueB ? ascending : 0);
2207         }
2208
2209         /**
2210          * @param {number} indexA
2211          * @param {number} indexB
2212          * @return {number}
2213          */
2214         function sortByComparator(indexA, indexB)
2215         {
2216             nodeA.nodeIndex = indexA;
2217             nodeB.nodeIndex = indexB;
2218             var result = sortByNodeField(fieldAccessor1, ascending1);
2219             if (result === 0)
2220                 result = sortByNodeField(fieldAccessor2, ascending2);
2221             return result || indexA - indexB;
2222         }
2223
2224         return sortByComparator;
2225     },
2226
2227     /**
2228      * @param {!WebInspector.HeapSnapshotCommon.ComparatorConfig} comparator
2229      * @param {number} leftBound
2230      * @param {number} rightBound
2231      * @param {number} windowLeft
2232      * @param {number} windowRight
2233      */
2234     sort: function(comparator, leftBound, rightBound, windowLeft, windowRight)
2235     {
2236         this._iterationOrder.sortRange(this._buildCompareFunction(comparator), leftBound, rightBound, windowLeft, windowRight);
2237     },
2238
2239     __proto__: WebInspector.HeapSnapshotItemProvider.prototype
2240 }
2241