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