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