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 * @constructor 481 */ 482 WebInspector.HeapSnapshot = function(profile) 483 { 484 this.uid = profile.snapshot.uid; 485 this._nodes = profile.nodes; 486 this._containmentEdges = profile.edges; 487 /** @type{HeapSnapshotMetainfo} */ 488 this._metaNode = profile.snapshot.meta; 489 this._strings = profile.strings; 490 491 this._noDistance = -5; 492 this._rootNodeIndex = 0; 493 if (profile.snapshot.root_index) 494 this._rootNodeIndex = profile.snapshot.root_index; 495 496 this._snapshotDiffs = {}; 497 this._aggregatesForDiff = null; 498 499 this._init(); 500 } 501 502 /** 503 * @constructor 504 */ 505 function HeapSnapshotMetainfo() 506 { 507 // New format. 508 this.node_fields = []; 509 this.node_types = []; 510 this.edge_fields = []; 511 this.edge_types = []; 512 this.type_strings = {}; 513 514 // Old format. 515 this.fields = []; 516 this.types = []; 517 } 518 519 /** 520 * @constructor 521 */ 522 function HeapSnapshotHeader() 523 { 524 // New format. 525 this.title = ""; 526 this.uid = 0; 527 this.meta = new HeapSnapshotMetainfo(); 528 this.node_count = 0; 529 this.edge_count = 0; 530 } 531 532 WebInspector.HeapSnapshot.prototype = { 533 _init: function() 534 { 535 var meta = this._metaNode; 536 537 this._nodeTypeOffset = meta.node_fields.indexOf("type"); 538 this._nodeNameOffset = meta.node_fields.indexOf("name"); 539 this._nodeIdOffset = meta.node_fields.indexOf("id"); 540 this._nodeSelfSizeOffset = meta.node_fields.indexOf("self_size"); 541 this._nodeEdgeCountOffset = meta.node_fields.indexOf("edge_count"); 542 this._nodeFieldCount = meta.node_fields.length; 543 544 this._nodeTypes = meta.node_types[this._nodeTypeOffset]; 545 this._nodeHiddenType = this._nodeTypes.indexOf("hidden"); 546 this._nodeObjectType = this._nodeTypes.indexOf("object"); 547 this._nodeNativeType = this._nodeTypes.indexOf("native"); 548 this._nodeCodeType = this._nodeTypes.indexOf("code"); 549 this._nodeSyntheticType = this._nodeTypes.indexOf("synthetic"); 550 551 this._edgeFieldsCount = meta.edge_fields.length; 552 this._edgeTypeOffset = meta.edge_fields.indexOf("type"); 553 this._edgeNameOffset = meta.edge_fields.indexOf("name_or_index"); 554 this._edgeToNodeOffset = meta.edge_fields.indexOf("to_node"); 555 556 this._edgeTypes = meta.edge_types[this._edgeTypeOffset]; 557 this._edgeTypes.push("invisible"); 558 this._edgeElementType = this._edgeTypes.indexOf("element"); 559 this._edgeHiddenType = this._edgeTypes.indexOf("hidden"); 560 this._edgeInternalType = this._edgeTypes.indexOf("internal"); 561 this._edgeShortcutType = this._edgeTypes.indexOf("shortcut"); 562 this._edgeWeakType = this._edgeTypes.indexOf("weak"); 563 this._edgeInvisibleType = this._edgeTypes.indexOf("invisible"); 564 565 this.nodeCount = this._nodes.length / this._nodeFieldCount; 566 this._edgeCount = this._containmentEdges.length / this._edgeFieldsCount; 567 568 this._buildEdgeIndexes(); 569 this._markInvisibleEdges(); 570 this._buildRetainers(); 571 this._calculateFlags(); 572 this._calculateDistances(); 573 var result = this._buildPostOrderIndex(); 574 // Actually it is array that maps node ordinal number to dominator node ordinal number. 575 this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex); 576 this._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal); 577 this._buildDominatedNodes(); 578 }, 579 580 _buildEdgeIndexes: function() 581 { 582 var nodes = this._nodes; 583 var nodeCount = this.nodeCount; 584 var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1); 585 var nodeFieldCount = this._nodeFieldCount; 586 var edgeFieldsCount = this._edgeFieldsCount; 587 var nodeEdgeCountOffset = this._nodeEdgeCountOffset; 588 firstEdgeIndexes[nodeCount] = this._containmentEdges.length; 589 for (var nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) { 590 firstEdgeIndexes[nodeOrdinal] = edgeIndex; 591 edgeIndex += nodes[nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset] * edgeFieldsCount; 592 } 593 }, 594 595 _buildRetainers: function() 596 { 597 var retainingNodes = this._retainingNodes = new Uint32Array(this._edgeCount); 598 var retainingEdges = this._retainingEdges = new Uint32Array(this._edgeCount); 599 // Index of the first retainer in the _retainingNodes and _retainingEdges 600 // arrays. Addressed by retained node index. 601 var firstRetainerIndex = this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1); 602 603 var containmentEdges = this._containmentEdges; 604 var edgeFieldsCount = this._edgeFieldsCount; 605 var nodeFieldCount = this._nodeFieldCount; 606 var edgeToNodeOffset = this._edgeToNodeOffset; 607 var nodes = this._nodes; 608 var firstEdgeIndexes = this._firstEdgeIndexes; 609 var nodeCount = this.nodeCount; 610 611 for (var toNodeFieldIndex = edgeToNodeOffset, l = containmentEdges.length; toNodeFieldIndex < l; toNodeFieldIndex += edgeFieldsCount) { 612 var toNodeIndex = containmentEdges[toNodeFieldIndex]; 613 if (toNodeIndex % nodeFieldCount) 614 throw new Error("Invalid toNodeIndex " + toNodeIndex); 615 ++firstRetainerIndex[toNodeIndex / nodeFieldCount]; 616 } 617 for (var i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) { 618 var retainersCount = firstRetainerIndex[i]; 619 firstRetainerIndex[i] = firstUnusedRetainerSlot; 620 retainingNodes[firstUnusedRetainerSlot] = retainersCount; 621 firstUnusedRetainerSlot += retainersCount; 622 } 623 firstRetainerIndex[nodeCount] = retainingNodes.length; 624 625 var nextNodeFirstEdgeIndex = firstEdgeIndexes[0]; 626 for (var srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) { 627 var firstEdgeIndex = nextNodeFirstEdgeIndex; 628 nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1]; 629 var srcNodeIndex = srcNodeOrdinal * nodeFieldCount; 630 for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) { 631 var toNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; 632 if (toNodeIndex % nodeFieldCount) 633 throw new Error("Invalid toNodeIndex " + toNodeIndex); 634 var firstRetainerSlotIndex = firstRetainerIndex[toNodeIndex / nodeFieldCount]; 635 var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]); 636 retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex; 637 retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex; 638 } 639 } 640 }, 641 642 /** 643 * @param {number=} nodeIndex 644 */ 645 createNode: function(nodeIndex) 646 { 647 throw new Error("Not implemented"); 648 }, 649 650 createEdge: function(edges, edgeIndex) 651 { 652 throw new Error("Not implemented"); 653 }, 654 655 createRetainingEdge: function(retainedNodeIndex, retainerIndex) 656 { 657 throw new Error("Not implemented"); 658 }, 659 660 dispose: function() 661 { 662 delete this._nodes; 663 delete this._strings; 664 delete this._retainingEdges; 665 delete this._retainingNodes; 666 delete this._firstRetainerIndex; 667 if (this._aggregates) { 668 delete this._aggregates; 669 delete this._aggregatesSortedFlags; 670 } 671 delete this._dominatedNodes; 672 delete this._firstDominatedNodeIndex; 673 delete this._nodeDistances; 674 delete this._dominatorsTree; 675 }, 676 677 _allNodes: function() 678 { 679 return new WebInspector.HeapSnapshotNodeIterator(this.rootNode()); 680 }, 681 682 rootNode: function() 683 { 684 return this.createNode(this._rootNodeIndex); 685 }, 686 687 get rootNodeIndex() 688 { 689 return this._rootNodeIndex; 690 }, 691 692 get totalSize() 693 { 694 return this.rootNode().retainedSize(); 695 }, 696 697 _getDominatedIndex: function(nodeIndex) 698 { 699 if (nodeIndex % this._nodeFieldCount) 700 throw new Error("Invalid nodeIndex: " + nodeIndex); 701 return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount]; 702 }, 703 704 _dominatedNodesOfNode: function(node) 705 { 706 var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex); 707 var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex()); 708 return new WebInspector.HeapSnapshotArraySlice(this._dominatedNodes, dominatedIndexFrom, dominatedIndexTo); 709 }, 710 711 /** 712 * @param {boolean} sortedIndexes 713 * @param {string} key 714 * @param {string=} filterString 715 */ 716 aggregates: function(sortedIndexes, key, filterString) 717 { 718 if (!this._aggregates) { 719 this._aggregates = {}; 720 this._aggregatesSortedFlags = {}; 721 } 722 723 var aggregatesByClassName = this._aggregates[key]; 724 if (aggregatesByClassName) { 725 if (sortedIndexes && !this._aggregatesSortedFlags[key]) { 726 this._sortAggregateIndexes(aggregatesByClassName); 727 this._aggregatesSortedFlags[key] = sortedIndexes; 728 } 729 return aggregatesByClassName; 730 } 731 732 var filter; 733 if (filterString) 734 filter = this._parseFilter(filterString); 735 736 var aggregates = this._buildAggregates(filter); 737 this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter); 738 aggregatesByClassName = aggregates.aggregatesByClassName; 739 740 if (sortedIndexes) 741 this._sortAggregateIndexes(aggregatesByClassName); 742 743 this._aggregatesSortedFlags[key] = sortedIndexes; 744 this._aggregates[key] = aggregatesByClassName; 745 746 return aggregatesByClassName; 747 }, 748 749 aggregatesForDiff: function() 750 { 751 if (this._aggregatesForDiff) 752 return this._aggregatesForDiff; 753 754 var aggregatesByClassName = this.aggregates(true, "allObjects"); 755 this._aggregatesForDiff = {}; 756 757 var node = this.createNode(); 758 for (var className in aggregatesByClassName) { 759 var aggregate = aggregatesByClassName[className]; 760 var indexes = aggregate.idxs; 761 var ids = new Array(indexes.length); 762 var selfSizes = new Array(indexes.length); 763 for (var i = 0; i < indexes.length; i++) { 764 node.nodeIndex = indexes[i]; 765 ids[i] = node.id(); 766 selfSizes[i] = node.selfSize(); 767 } 768 769 this._aggregatesForDiff[className] = { 770 indexes: indexes, 771 ids: ids, 772 selfSizes: selfSizes 773 }; 774 } 775 return this._aggregatesForDiff; 776 }, 777 778 /** 779 * @param {!WebInspector.HeapSnapshotNode} node 780 * @return {!boolean} 781 */ 782 _isUserRoot: function(node) 783 { 784 return true; 785 }, 786 787 /** 788 * @param {function(!WebInspector.HeapSnapshotNode)} action 789 * @param {boolean=} userRootsOnly 790 */ 791 forEachRoot: function(action, userRootsOnly) 792 { 793 for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) { 794 var node = iter.edge.node(); 795 if (!userRootsOnly || this._isUserRoot(node)) 796 action(node); 797 } 798 }, 799 800 _calculateDistances: function() 801 { 802 var nodeFieldCount = this._nodeFieldCount; 803 var nodeCount = this.nodeCount; 804 var distances = new Int32Array(nodeCount); 805 var noDistance = this._noDistance; 806 for (var i = 0; i < nodeCount; ++i) 807 distances[i] = noDistance; 808 809 var nodesToVisit = new Uint32Array(this.nodeCount); 810 var nodesToVisitLength = 0; 811 812 /** 813 * @param {!WebInspector.HeapSnapshotNode} node 814 */ 815 function enqueueNode(node) 816 { 817 var ordinal = node._ordinal(); 818 if (distances[ordinal] !== noDistance) 819 return; 820 distances[ordinal] = 0; 821 nodesToVisit[nodesToVisitLength++] = node.nodeIndex; 822 } 823 824 this.forEachRoot(enqueueNode, true); 825 this._bfs(nodesToVisit, nodesToVisitLength, distances); 826 827 // bfs for the rest of objects 828 nodesToVisitLength = 0; 829 this.forEachRoot(enqueueNode); 830 this._bfs(nodesToVisit, nodesToVisitLength, distances); 831 832 this._nodeDistances = distances; 833 }, 834 835 /** 836 * @param {!Uint32Array} nodesToVisit 837 * @param {!number} nodesToVisitLength 838 * @param {!Int32Array} distances 839 */ 840 _bfs: function(nodesToVisit, nodesToVisitLength, distances) 841 { 842 // Preload fields into local variables for better performance. 843 var edgeFieldsCount = this._edgeFieldsCount; 844 var nodeFieldCount = this._nodeFieldCount; 845 var containmentEdges = this._containmentEdges; 846 var firstEdgeIndexes = this._firstEdgeIndexes; 847 var edgeToNodeOffset = this._edgeToNodeOffset; 848 var edgeTypeOffset = this._edgeTypeOffset; 849 var nodes = this._nodes; 850 var nodeCount = this.nodeCount; 851 var containmentEdgesLength = containmentEdges.length; 852 var edgeWeakType = this._edgeWeakType; 853 var noDistance = this._noDistance; 854 855 var index = 0; 856 while (index < nodesToVisitLength) { 857 var nodeIndex = nodesToVisit[index++]; // shift generates too much garbage. 858 var nodeOrdinal = nodeIndex / nodeFieldCount; 859 var distance = distances[nodeOrdinal] + 1; 860 var firstEdgeIndex = firstEdgeIndexes[nodeOrdinal]; 861 var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1]; 862 for (var edgeIndex = firstEdgeIndex; edgeIndex < edgesEnd; edgeIndex += edgeFieldsCount) { 863 var edgeType = containmentEdges[edgeIndex + edgeTypeOffset]; 864 if (edgeType == edgeWeakType) 865 continue; 866 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; 867 var childNodeOrdinal = childNodeIndex / nodeFieldCount; 868 if (distances[childNodeOrdinal] !== noDistance) 869 continue; 870 distances[childNodeOrdinal] = distance; 871 nodesToVisit[nodesToVisitLength++] = childNodeIndex; 872 } 873 } 874 if (nodesToVisitLength > nodeCount) 875 throw new Error("BFS failed. Nodes to visit (" + nodesToVisitLength + ") is more than nodes count (" + nodeCount + ")"); 876 }, 877 878 _buildAggregates: function(filter) 879 { 880 var aggregates = {}; 881 var aggregatesByClassName = {}; 882 var classIndexes = []; 883 var nodes = this._nodes; 884 var mapAndFlag = this.userObjectsMapAndFlag(); 885 var flags = mapAndFlag ? mapAndFlag.map : null; 886 var flag = mapAndFlag ? mapAndFlag.flag : 0; 887 var nodesLength = nodes.length; 888 var nodeNativeType = this._nodeNativeType; 889 var nodeFieldCount = this._nodeFieldCount; 890 var selfSizeOffset = this._nodeSelfSizeOffset; 891 var nodeTypeOffset = this._nodeTypeOffset; 892 var node = this.rootNode(); 893 var nodeDistances = this._nodeDistances; 894 895 for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { 896 var nodeOrdinal = nodeIndex / nodeFieldCount; 897 if (flags && !(flags[nodeOrdinal] & flag)) 898 continue; 899 node.nodeIndex = nodeIndex; 900 if (filter && !filter(node)) 901 continue; 902 var selfSize = nodes[nodeIndex + selfSizeOffset]; 903 if (!selfSize && nodes[nodeIndex + nodeTypeOffset] !== nodeNativeType) 904 continue; 905 var classIndex = node.classIndex(); 906 if (!(classIndex in aggregates)) { 907 var nodeType = node.type(); 908 var nameMatters = nodeType === "object" || nodeType === "native"; 909 var value = { 910 count: 1, 911 distance: nodeDistances[nodeOrdinal], 912 self: selfSize, 913 maxRet: 0, 914 type: nodeType, 915 name: nameMatters ? node.name() : null, 916 idxs: [nodeIndex] 917 }; 918 aggregates[classIndex] = value; 919 classIndexes.push(classIndex); 920 aggregatesByClassName[node.className()] = value; 921 } else { 922 var clss = aggregates[classIndex]; 923 clss.distance = Math.min(clss.distance, nodeDistances[nodeOrdinal]); 924 ++clss.count; 925 clss.self += selfSize; 926 clss.idxs.push(nodeIndex); 927 } 928 } 929 930 // Shave off provisionally allocated space. 931 for (var i = 0, l = classIndexes.length; i < l; ++i) { 932 var classIndex = classIndexes[i]; 933 aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice(); 934 } 935 return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates}; 936 }, 937 938 _calculateClassesRetainedSize: function(aggregates, filter) 939 { 940 var rootNodeIndex = this._rootNodeIndex; 941 var node = this.createNode(rootNodeIndex); 942 var list = [rootNodeIndex]; 943 var sizes = [-1]; 944 var classes = []; 945 var seenClassNameIndexes = {}; 946 var nodeFieldCount = this._nodeFieldCount; 947 var nodeTypeOffset = this._nodeTypeOffset; 948 var nodeNativeType = this._nodeNativeType; 949 var dominatedNodes = this._dominatedNodes; 950 var nodes = this._nodes; 951 var mapAndFlag = this.userObjectsMapAndFlag(); 952 var flags = mapAndFlag ? mapAndFlag.map : null; 953 var flag = mapAndFlag ? mapAndFlag.flag : 0; 954 var firstDominatedNodeIndex = this._firstDominatedNodeIndex; 955 956 while (list.length) { 957 var nodeIndex = list.pop(); 958 node.nodeIndex = nodeIndex; 959 var classIndex = node.classIndex(); 960 var seen = !!seenClassNameIndexes[classIndex]; 961 var nodeOrdinal = nodeIndex / nodeFieldCount; 962 var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal]; 963 var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1]; 964 965 if (!seen && 966 (!flags || (flags[nodeOrdinal] & flag)) && 967 (!filter || filter(node)) && 968 (node.selfSize() || nodes[nodeIndex + nodeTypeOffset] === nodeNativeType) 969 ) { 970 aggregates[classIndex].maxRet += node.retainedSize(); 971 if (dominatedIndexFrom !== dominatedIndexTo) { 972 seenClassNameIndexes[classIndex] = true; 973 sizes.push(list.length); 974 classes.push(classIndex); 975 } 976 } 977 for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++) 978 list.push(dominatedNodes[i]); 979 980 var l = list.length; 981 while (sizes[sizes.length - 1] === l) { 982 sizes.pop(); 983 classIndex = classes.pop(); 984 seenClassNameIndexes[classIndex] = false; 985 } 986 } 987 }, 988 989 _sortAggregateIndexes: function(aggregates) 990 { 991 var nodeA = this.createNode(); 992 var nodeB = this.createNode(); 993 for (var clss in aggregates) 994 aggregates[clss].idxs.sort( 995 function(idxA, idxB) { 996 nodeA.nodeIndex = idxA; 997 nodeB.nodeIndex = idxB; 998 return nodeA.id() < nodeB.id() ? -1 : 1; 999 }); 1000 }, 1001 1002 _buildPostOrderIndex: function() 1003 { 1004 var nodeFieldCount = this._nodeFieldCount; 1005 var nodes = this._nodes; 1006 var nodeCount = this.nodeCount; 1007 var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount; 1008 1009 var edgeFieldsCount = this._edgeFieldsCount; 1010 var edgeTypeOffset = this._edgeTypeOffset; 1011 var edgeToNodeOffset = this._edgeToNodeOffset; 1012 var edgeShortcutType = this._edgeShortcutType; 1013 var firstEdgeIndexes = this._firstEdgeIndexes; 1014 var containmentEdges = this._containmentEdges; 1015 var containmentEdgesLength = this._containmentEdges.length; 1016 1017 var mapAndFlag = this.userObjectsMapAndFlag(); 1018 var flags = mapAndFlag ? mapAndFlag.map : null; 1019 var flag = mapAndFlag ? mapAndFlag.flag : 0; 1020 1021 var nodesToVisit = new Uint32Array(nodeCount); 1022 var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount); 1023 var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount); 1024 var painted = new Uint8Array(nodeCount); 1025 var nodesToVisitLength = 0; 1026 var postOrderIndex = 0; 1027 var grey = 1; 1028 var black = 2; 1029 1030 nodesToVisit[nodesToVisitLength++] = rootNodeOrdinal; 1031 painted[rootNodeOrdinal] = grey; 1032 1033 while (nodesToVisitLength) { 1034 var nodeOrdinal = nodesToVisit[nodesToVisitLength - 1]; 1035 1036 if (painted[nodeOrdinal] === grey) { 1037 painted[nodeOrdinal] = black; 1038 var nodeFlag = !flags || (flags[nodeOrdinal] & flag); 1039 var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal]; 1040 var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1]; 1041 for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { 1042 if (nodeOrdinal !== rootNodeOrdinal && containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType) 1043 continue; 1044 var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; 1045 var childNodeOrdinal = childNodeIndex / nodeFieldCount; 1046 var childNodeFlag = !flags || (flags[childNodeOrdinal] & flag); 1047 // We are skipping the edges from non-page-owned nodes to page-owned nodes. 1048 // Otherwise the dominators for the objects that also were retained by debugger would be affected. 1049 if (nodeOrdinal !== rootNodeOrdinal && childNodeFlag && !nodeFlag) 1050 continue; 1051 if (!painted[childNodeOrdinal]) { 1052 painted[childNodeOrdinal] = grey; 1053 nodesToVisit[nodesToVisitLength++] = childNodeOrdinal; 1054 } 1055 } 1056 } else { 1057 nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex; 1058 postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal; 1059 --nodesToVisitLength; 1060 } 1061 } 1062 1063 if (postOrderIndex !== nodeCount) { 1064 console.log("Error: Corrupted snapshot. " + (nodeCount - postOrderIndex) + " nodes are unreachable from the root:"); 1065 var dumpNode = this.rootNode(); 1066 for (var i = 0; i < nodeCount; ++i) { 1067 if (painted[i] !== black) { 1068 // Fix it by giving the node a postorder index anyway. 1069 nodeOrdinal2PostOrderIndex[i] = postOrderIndex; 1070 postOrderIndex2NodeOrdinal[postOrderIndex++] = i; 1071 dumpNode.nodeIndex = i * nodeFieldCount; 1072 console.log(JSON.stringify(dumpNode.serialize())); 1073 for (var retainers = dumpNode.retainers(); retainers.hasNext(); retainers = retainers.item().node().retainers()) 1074 console.log(" edgeName: " + retainers.item().name() + " nodeClassName: " + retainers.item().node().className()); 1075 } 1076 } 1077 } 1078 1079 return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex}; 1080 }, 1081 1082 // The algorithm is based on the article: 1083 // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm" 1084 // Softw. Pract. Exper. 4 (2001), pp. 1-10. 1085 /** 1086 * @param {Array.<number>} postOrderIndex2NodeOrdinal 1087 * @param {Array.<number>} nodeOrdinal2PostOrderIndex 1088 */ 1089 _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex) 1090 { 1091 var nodeFieldCount = this._nodeFieldCount; 1092 var nodes = this._nodes; 1093 var firstRetainerIndex = this._firstRetainerIndex; 1094 var retainingNodes = this._retainingNodes; 1095 var retainingEdges = this._retainingEdges; 1096 var edgeFieldsCount = this._edgeFieldsCount; 1097 var edgeTypeOffset = this._edgeTypeOffset; 1098 var edgeToNodeOffset = this._edgeToNodeOffset; 1099 var edgeShortcutType = this._edgeShortcutType; 1100 var firstEdgeIndexes = this._firstEdgeIndexes; 1101 var containmentEdges = this._containmentEdges; 1102 var containmentEdgesLength = this._containmentEdges.length; 1103 var rootNodeIndex = this._rootNodeIndex; 1104 1105 var mapAndFlag = this.userObjectsMapAndFlag(); 1106 var flags = mapAndFlag ? mapAndFlag.map : null; 1107 var flag = mapAndFlag ? mapAndFlag.flag : 0; 1108 1109 var nodesCount = postOrderIndex2NodeOrdinal.length; 1110 var rootPostOrderedIndex = nodesCount - 1; 1111 var noEntry = nodesCount; 1112 var dominators = new Uint32Array(nodesCount); 1113 for (var i = 0; i < rootPostOrderedIndex; ++i) 1114 dominators[i] = noEntry; 1115 dominators[rootPostOrderedIndex] = rootPostOrderedIndex; 1116 1117 // The affected array is used to mark entries which dominators 1118 // have to be racalculated because of changes in their retainers. 1119 var affected = new Uint8Array(nodesCount); 1120 var nodeOrdinal; 1121 1122 { // Mark the root direct children as affected. 1123 nodeOrdinal = this._rootNodeIndex / nodeFieldCount; 1124 var beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset; 1125 var endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1]; 1126 for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex; 1127 toNodeFieldIndex < endEdgeToNodeFieldIndex; 1128 toNodeFieldIndex += edgeFieldsCount) { 1129 var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount; 1130 affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1; 1131 } 1132 } 1133 1134 var changed = true; 1135 while (changed) { 1136 changed = false; 1137 for (var postOrderIndex = rootPostOrderedIndex - 1; postOrderIndex >= 0; --postOrderIndex) { 1138 if (affected[postOrderIndex] === 0) 1139 continue; 1140 affected[postOrderIndex] = 0; 1141 // If dominator of the entry has already been set to root, 1142 // then it can't propagate any further. 1143 if (dominators[postOrderIndex] === rootPostOrderedIndex) 1144 continue; 1145 nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; 1146 var nodeFlag = !flags || (flags[nodeOrdinal] & flag); 1147 var newDominatorIndex = noEntry; 1148 var beginRetainerIndex = firstRetainerIndex[nodeOrdinal]; 1149 var endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1]; 1150 for (var retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) { 1151 var retainerEdgeIndex = retainingEdges[retainerIndex]; 1152 var retainerEdgeType = containmentEdges[retainerEdgeIndex + edgeTypeOffset]; 1153 var retainerNodeIndex = retainingNodes[retainerIndex]; 1154 if (retainerNodeIndex !== rootNodeIndex && retainerEdgeType === edgeShortcutType) 1155 continue; 1156 var retainerNodeOrdinal = retainerNodeIndex / nodeFieldCount; 1157 var retainerNodeFlag = !flags || (flags[retainerNodeOrdinal] & flag); 1158 // We are skipping the edges from non-page-owned nodes to page-owned nodes. 1159 // Otherwise the dominators for the objects that also were retained by debugger would be affected. 1160 if (retainerNodeIndex !== rootNodeIndex && nodeFlag && !retainerNodeFlag) 1161 continue; 1162 var retanerPostOrderIndex = nodeOrdinal2PostOrderIndex[retainerNodeOrdinal]; 1163 if (dominators[retanerPostOrderIndex] !== noEntry) { 1164 if (newDominatorIndex === noEntry) 1165 newDominatorIndex = retanerPostOrderIndex; 1166 else { 1167 while (retanerPostOrderIndex !== newDominatorIndex) { 1168 while (retanerPostOrderIndex < newDominatorIndex) 1169 retanerPostOrderIndex = dominators[retanerPostOrderIndex]; 1170 while (newDominatorIndex < retanerPostOrderIndex) 1171 newDominatorIndex = dominators[newDominatorIndex]; 1172 } 1173 } 1174 // If idom has already reached the root, it doesn't make sense 1175 // to check other retainers. 1176 if (newDominatorIndex === rootPostOrderedIndex) 1177 break; 1178 } 1179 } 1180 if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) { 1181 dominators[postOrderIndex] = newDominatorIndex; 1182 changed = true; 1183 nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; 1184 beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset; 1185 endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1]; 1186 for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex; 1187 toNodeFieldIndex < endEdgeToNodeFieldIndex; 1188 toNodeFieldIndex += edgeFieldsCount) { 1189 var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount; 1190 affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1; 1191 } 1192 } 1193 } 1194 } 1195 1196 var dominatorsTree = new Uint32Array(nodesCount); 1197 for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) { 1198 nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; 1199 dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]]; 1200 } 1201 return dominatorsTree; 1202 }, 1203 1204 _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal) 1205 { 1206 var nodeCount = this.nodeCount; 1207 var nodes = this._nodes; 1208 var nodeSelfSizeOffset = this._nodeSelfSizeOffset; 1209 var nodeFieldCount = this._nodeFieldCount; 1210 var dominatorsTree = this._dominatorsTree; 1211 // Reuse now unused edge_count field to store retained size. 1212 var nodeRetainedSizeOffset = this._nodeRetainedSizeOffset = this._nodeEdgeCountOffset; 1213 delete this._nodeEdgeCountOffset; 1214 1215 for (var nodeIndex = 0, l = nodes.length; nodeIndex < l; nodeIndex += nodeFieldCount) 1216 nodes[nodeIndex + nodeRetainedSizeOffset] = nodes[nodeIndex + nodeSelfSizeOffset]; 1217 1218 // Propagate retained sizes for each node excluding root. 1219 for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) { 1220 var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; 1221 var nodeIndex = nodeOrdinal * nodeFieldCount; 1222 var dominatorIndex = dominatorsTree[nodeOrdinal] * nodeFieldCount; 1223 nodes[dominatorIndex + nodeRetainedSizeOffset] += nodes[nodeIndex + nodeRetainedSizeOffset]; 1224 } 1225 }, 1226 1227 _buildDominatedNodes: function() 1228 { 1229 // Builds up two arrays: 1230 // - "dominatedNodes" is a continuous array, where each node owns an 1231 // interval (can be empty) with corresponding dominated nodes. 1232 // - "indexArray" is an array of indexes in the "dominatedNodes" 1233 // with the same positions as in the _nodeIndex. 1234 var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1); 1235 // All nodes except the root have dominators. 1236 var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1); 1237 1238 // Count the number of dominated nodes for each node. Skip the root (node at 1239 // index 0) as it is the only node that dominates itself. 1240 var nodeFieldCount = this._nodeFieldCount; 1241 var dominatorsTree = this._dominatorsTree; 1242 1243 var fromNodeOrdinal = 0; 1244 var toNodeOrdinal = this.nodeCount; 1245 var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount; 1246 if (rootNodeOrdinal === fromNodeOrdinal) 1247 fromNodeOrdinal = 1; 1248 else if (rootNodeOrdinal === toNodeOrdinal - 1) 1249 toNodeOrdinal = toNodeOrdinal - 1; 1250 else 1251 throw new Error("Root node is expected to be either first or last"); 1252 for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) 1253 ++indexArray[dominatorsTree[nodeOrdinal]]; 1254 // Put in the first slot of each dominatedNodes slice the count of entries 1255 // that will be filled. 1256 var firstDominatedNodeIndex = 0; 1257 for (var i = 0, l = this.nodeCount; i < l; ++i) { 1258 var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i]; 1259 indexArray[i] = firstDominatedNodeIndex; 1260 firstDominatedNodeIndex += dominatedCount; 1261 } 1262 indexArray[this.nodeCount] = dominatedNodes.length; 1263 // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at 1264 // index 0) as it is the only node that dominates itself. 1265 for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) { 1266 var dominatorOrdinal = dominatorsTree[nodeOrdinal]; 1267 var dominatedRefIndex = indexArray[dominatorOrdinal]; 1268 dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]); 1269 dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount; 1270 } 1271 }, 1272 1273 _markInvisibleEdges: function() 1274 { 1275 throw new Error("Not implemented"); 1276 }, 1277 1278 _calculateFlags: function() 1279 { 1280 throw new Error("Not implemented"); 1281 }, 1282 1283 userObjectsMapAndFlag: function() 1284 { 1285 throw new Error("Not implemented"); 1286 }, 1287 1288 calculateSnapshotDiff: function(baseSnapshotId, baseSnapshotAggregates) 1289 { 1290 var snapshotDiff = this._snapshotDiffs[baseSnapshotId]; 1291 if (snapshotDiff) 1292 return snapshotDiff; 1293 snapshotDiff = {}; 1294 1295 var aggregates = this.aggregates(true, "allObjects"); 1296 for (var className in baseSnapshotAggregates) { 1297 var baseAggregate = baseSnapshotAggregates[className]; 1298 var diff = this._calculateDiffForClass(baseAggregate, aggregates[className]); 1299 if (diff) 1300 snapshotDiff[className] = diff; 1301 } 1302 var emptyBaseAggregate = { ids: [], indexes: [], selfSizes: [] }; 1303 for (var className in aggregates) { 1304 if (className in baseSnapshotAggregates) 1305 continue; 1306 snapshotDiff[className] = this._calculateDiffForClass(emptyBaseAggregate, aggregates[className]); 1307 } 1308 1309 this._snapshotDiffs[baseSnapshotId] = snapshotDiff; 1310 return snapshotDiff; 1311 }, 1312 1313 _calculateDiffForClass: function(baseAggregate, aggregate) 1314 { 1315 var baseIds = baseAggregate.ids; 1316 var baseIndexes = baseAggregate.indexes; 1317 var baseSelfSizes = baseAggregate.selfSizes; 1318 1319 var indexes = aggregate ? aggregate.idxs : []; 1320 1321 var i = 0, l = baseIds.length; 1322 var j = 0, m = indexes.length; 1323 var diff = { addedCount: 0, 1324 removedCount: 0, 1325 addedSize: 0, 1326 removedSize: 0, 1327 deletedIndexes: [], 1328 addedIndexes: [] }; 1329 1330 var nodeB = this.createNode(indexes[j]); 1331 while (i < l && j < m) { 1332 var nodeAId = baseIds[i]; 1333 if (nodeAId < nodeB.id()) { 1334 diff.deletedIndexes.push(baseIndexes[i]); 1335 diff.removedCount++; 1336 diff.removedSize += baseSelfSizes[i]; 1337 ++i; 1338 } else if (nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot 1339 diff.addedIndexes.push(indexes[j]); 1340 diff.addedCount++; 1341 diff.addedSize += nodeB.selfSize(); 1342 nodeB.nodeIndex = indexes[++j]; 1343 } else { // nodeAId === nodeB.id() 1344 ++i; 1345 nodeB.nodeIndex = indexes[++j]; 1346 } 1347 } 1348 while (i < l) { 1349 diff.deletedIndexes.push(baseIndexes[i]); 1350 diff.removedCount++; 1351 diff.removedSize += baseSelfSizes[i]; 1352 ++i; 1353 } 1354 while (j < m) { 1355 diff.addedIndexes.push(indexes[j]); 1356 diff.addedCount++; 1357 diff.addedSize += nodeB.selfSize(); 1358 nodeB.nodeIndex = indexes[++j]; 1359 } 1360 diff.countDelta = diff.addedCount - diff.removedCount; 1361 diff.sizeDelta = diff.addedSize - diff.removedSize; 1362 if (!diff.addedCount && !diff.removedCount) 1363 return null; 1364 return diff; 1365 }, 1366 1367 _nodeForSnapshotObjectId: function(snapshotObjectId) 1368 { 1369 for (var it = this._allNodes(); it.hasNext(); it.next()) { 1370 if (it.node.id() === snapshotObjectId) 1371 return it.node; 1372 } 1373 return null; 1374 }, 1375 1376 nodeClassName: function(snapshotObjectId) 1377 { 1378 var node = this._nodeForSnapshotObjectId(snapshotObjectId); 1379 if (node) 1380 return node.className(); 1381 return null; 1382 }, 1383 1384 dominatorIdsForNode: function(snapshotObjectId) 1385 { 1386 var node = this._nodeForSnapshotObjectId(snapshotObjectId); 1387 if (!node) 1388 return null; 1389 var result = []; 1390 while (!node.isRoot()) { 1391 result.push(node.id()); 1392 node.nodeIndex = node.dominatorIndex(); 1393 } 1394 return result; 1395 }, 1396 1397 _parseFilter: function(filter) 1398 { 1399 if (!filter) 1400 return null; 1401 var parsedFilter = eval("(function(){return " + filter + "})()"); 1402 return parsedFilter.bind(this); 1403 }, 1404 1405 createEdgesProvider: function(nodeIndex, showHiddenData) 1406 { 1407 var node = this.createNode(nodeIndex); 1408 var filter = this.containmentEdgesFilter(showHiddenData); 1409 return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges()); 1410 }, 1411 1412 createEdgesProviderForTest: function(nodeIndex, filter) 1413 { 1414 var node = this.createNode(nodeIndex); 1415 return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges()); 1416 }, 1417 1418 retainingEdgesFilter: function(showHiddenData) 1419 { 1420 return null; 1421 }, 1422 1423 containmentEdgesFilter: function(showHiddenData) 1424 { 1425 return null; 1426 }, 1427 1428 createRetainingEdgesProvider: function(nodeIndex, showHiddenData) 1429 { 1430 var node = this.createNode(nodeIndex); 1431 var filter = this.retainingEdgesFilter(showHiddenData); 1432 return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.retainers()); 1433 }, 1434 1435 createAddedNodesProvider: function(baseSnapshotId, className) 1436 { 1437 var snapshotDiff = this._snapshotDiffs[baseSnapshotId]; 1438 var diffForClass = snapshotDiff[className]; 1439 return new WebInspector.HeapSnapshotNodesProvider(this, null, diffForClass.addedIndexes); 1440 }, 1441 1442 createDeletedNodesProvider: function(nodeIndexes) 1443 { 1444 return new WebInspector.HeapSnapshotNodesProvider(this, null, nodeIndexes); 1445 }, 1446 1447 classNodesFilter: function() 1448 { 1449 return null; 1450 }, 1451 1452 createNodesProviderForClass: function(className, aggregatesKey) 1453 { 1454 return new WebInspector.HeapSnapshotNodesProvider(this, this.classNodesFilter(), this.aggregates(false, aggregatesKey)[className].idxs); 1455 }, 1456 1457 createNodesProviderForDominator: function(nodeIndex) 1458 { 1459 var node = this.createNode(nodeIndex); 1460 return new WebInspector.HeapSnapshotNodesProvider(this, null, this._dominatedNodesOfNode(node)); 1461 }, 1462 1463 updateStaticData: function() 1464 { 1465 return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid}; 1466 } 1467 }; 1468 1469 /** 1470 * @constructor 1471 * @param {Array.<number>=} unfilteredIterationOrder 1472 */ 1473 WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder) 1474 { 1475 this._filter = filter; 1476 this._iterator = iterator; 1477 this._unfilteredIterationOrder = unfilteredIterationOrder; 1478 this._iterationOrder = null; 1479 this._position = 0; 1480 this._currentComparator = null; 1481 this._sortedPrefixLength = 0; 1482 } 1483 1484 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = { 1485 _createIterationOrder: function() 1486 { 1487 if (this._iterationOrder) 1488 return; 1489 if (this._unfilteredIterationOrder && !this._filter) { 1490 this._iterationOrder = this._unfilteredIterationOrder.slice(0); 1491 this._unfilteredIterationOrder = null; 1492 return; 1493 } 1494 this._iterationOrder = []; 1495 var iterator = this._iterator; 1496 if (!this._unfilteredIterationOrder && !this._filter) { 1497 for (iterator.rewind(); iterator.hasNext(); iterator.next()) 1498 this._iterationOrder.push(iterator.index()); 1499 } else if (!this._unfilteredIterationOrder) { 1500 for (iterator.rewind(); iterator.hasNext(); iterator.next()) { 1501 if (this._filter(iterator.item())) 1502 this._iterationOrder.push(iterator.index()); 1503 } 1504 } else { 1505 var order = this._unfilteredIterationOrder.constructor === Array ? 1506 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0); 1507 for (var i = 0, l = order.length; i < l; ++i) { 1508 iterator.setIndex(order[i]); 1509 if (this._filter(iterator.item())) 1510 this._iterationOrder.push(iterator.index()); 1511 } 1512 this._unfilteredIterationOrder = null; 1513 } 1514 }, 1515 1516 rewind: function() 1517 { 1518 this._position = 0; 1519 }, 1520 1521 hasNext: function() 1522 { 1523 return this._position < this._iterationOrder.length; 1524 }, 1525 1526 isEmpty: function() 1527 { 1528 if (this._iterationOrder) 1529 return !this._iterationOrder.length; 1530 if (this._unfilteredIterationOrder && !this._filter) 1531 return !this._unfilteredIterationOrder.length; 1532 var iterator = this._iterator; 1533 if (!this._unfilteredIterationOrder && !this._filter) { 1534 iterator.rewind(); 1535 return !iterator.hasNext(); 1536 } else if (!this._unfilteredIterationOrder) { 1537 for (iterator.rewind(); iterator.hasNext(); iterator.next()) 1538 if (this._filter(iterator.item())) 1539 return false; 1540 } else { 1541 var order = this._unfilteredIterationOrder.constructor === Array ? 1542 this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0); 1543 for (var i = 0, l = order.length; i < l; ++i) { 1544 iterator.setIndex(order[i]); 1545 if (this._filter(iterator.item())) 1546 return false; 1547 } 1548 } 1549 return true; 1550 }, 1551 1552 item: function() 1553 { 1554 this._iterator.setIndex(this._iterationOrder[this._position]); 1555 return this._iterator.item(); 1556 }, 1557 1558 get length() 1559 { 1560 this._createIterationOrder(); 1561 return this._iterationOrder.length; 1562 }, 1563 1564 next: function() 1565 { 1566 ++this._position; 1567 }, 1568 1569 /** 1570 * @param {number} begin 1571 * @param {number} end 1572 */ 1573 serializeItemsRange: function(begin, end) 1574 { 1575 this._createIterationOrder(); 1576 if (begin > end) 1577 throw new Error("Start position > end position: " + begin + " > " + end); 1578 if (end >= this._iterationOrder.length) 1579 end = this._iterationOrder.length; 1580 if (this._sortedPrefixLength < end) { 1581 this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, end - this._sortedPrefixLength); 1582 this._sortedPrefixLength = end; 1583 } 1584 1585 this._position = begin; 1586 var startPosition = this._position; 1587 var count = end - begin; 1588 var result = new Array(count); 1589 for (var i = 0 ; i < count && this.hasNext(); ++i, this.next()) 1590 result[i] = this.item().serialize(); 1591 result.length = i; 1592 result.totalLength = this._iterationOrder.length; 1593 1594 result.startPosition = startPosition; 1595 result.endPosition = this._position; 1596 return result; 1597 }, 1598 1599 sortAll: function() 1600 { 1601 this._createIterationOrder(); 1602 if (this._sortedPrefixLength === this._iterationOrder.length) 1603 return; 1604 this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, this._iterationOrder.length); 1605 this._sortedPrefixLength = this._iterationOrder.length; 1606 }, 1607 1608 sortAndRewind: function(comparator) 1609 { 1610 this._currentComparator = comparator; 1611 this._sortedPrefixLength = 0; 1612 this.rewind(); 1613 } 1614 } 1615 1616 WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames) 1617 { 1618 return {fieldName1: fieldNames[0], ascending1: fieldNames[1], fieldName2: fieldNames[2], ascending2: fieldNames[3]}; 1619 } 1620 1621 /** 1622 * @constructor 1623 * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator} 1624 */ 1625 WebInspector.HeapSnapshotEdgesProvider = function(snapshot, filter, edgesIter) 1626 { 1627 this.snapshot = snapshot; 1628 WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, edgesIter, filter); 1629 } 1630 1631 WebInspector.HeapSnapshotEdgesProvider.prototype = { 1632 sort: function(comparator, leftBound, rightBound, count) 1633 { 1634 var fieldName1 = comparator.fieldName1; 1635 var fieldName2 = comparator.fieldName2; 1636 var ascending1 = comparator.ascending1; 1637 var ascending2 = comparator.ascending2; 1638 1639 var edgeA = this._iterator.item().clone(); 1640 var edgeB = edgeA.clone(); 1641 var nodeA = this.snapshot.createNode(); 1642 var nodeB = this.snapshot.createNode(); 1643 1644 function compareEdgeFieldName(ascending, indexA, indexB) 1645 { 1646 edgeA.edgeIndex = indexA; 1647 edgeB.edgeIndex = indexB; 1648 if (edgeB.name() === "__proto__") return -1; 1649 if (edgeA.name() === "__proto__") return 1; 1650 var result = 1651 edgeA.hasStringName() === edgeB.hasStringName() ? 1652 (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) : 1653 (edgeA.hasStringName() ? -1 : 1); 1654 return ascending ? result : -result; 1655 } 1656 1657 function compareNodeField(fieldName, ascending, indexA, indexB) 1658 { 1659 edgeA.edgeIndex = indexA; 1660 nodeA.nodeIndex = edgeA.nodeIndex(); 1661 var valueA = nodeA[fieldName](); 1662 1663 edgeB.edgeIndex = indexB; 1664 nodeB.nodeIndex = edgeB.nodeIndex(); 1665 var valueB = nodeB[fieldName](); 1666 1667 var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0); 1668 return ascending ? result : -result; 1669 } 1670 1671 function compareEdgeAndNode(indexA, indexB) { 1672 var result = compareEdgeFieldName(ascending1, indexA, indexB); 1673 if (result === 0) 1674 result = compareNodeField(fieldName2, ascending2, indexA, indexB); 1675 return result; 1676 } 1677 1678 function compareNodeAndEdge(indexA, indexB) { 1679 var result = compareNodeField(fieldName1, ascending1, indexA, indexB); 1680 if (result === 0) 1681 result = compareEdgeFieldName(ascending2, indexA, indexB); 1682 return result; 1683 } 1684 1685 function compareNodeAndNode(indexA, indexB) { 1686 var result = compareNodeField(fieldName1, ascending1, indexA, indexB); 1687 if (result === 0) 1688 result = compareNodeField(fieldName2, ascending2, indexA, indexB); 1689 return result; 1690 } 1691 1692 if (fieldName1 === "!edgeName") 1693 this._iterationOrder.sortRange(compareEdgeAndNode, leftBound, rightBound, count); 1694 else if (fieldName2 === "!edgeName") 1695 this._iterationOrder.sortRange(compareNodeAndEdge, leftBound, rightBound, count); 1696 else 1697 this._iterationOrder.sortRange(compareNodeAndNode, leftBound, rightBound, count); 1698 }, 1699 1700 __proto__: WebInspector.HeapSnapshotFilteredOrderedIterator.prototype 1701 } 1702 1703 1704 /** 1705 * @constructor 1706 * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator} 1707 * @param {Array.<number>=} nodeIndexes 1708 */ 1709 WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes) 1710 { 1711 this.snapshot = snapshot; 1712 WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes(), filter, nodeIndexes); 1713 } 1714 1715 WebInspector.HeapSnapshotNodesProvider.prototype = { 1716 nodePosition: function(snapshotObjectId) 1717 { 1718 this._createIterationOrder(); 1719 if (this.isEmpty()) 1720 return -1; 1721 this.sortAll(); 1722 1723 var node = this.snapshot.createNode(); 1724 for (var i = 0; i < this._iterationOrder.length; i++) { 1725 node.nodeIndex = this._iterationOrder[i]; 1726 if (node.id() === snapshotObjectId) 1727 return i; 1728 } 1729 return -1; 1730 }, 1731 1732 sort: function(comparator, leftBound, rightBound, count) 1733 { 1734 var fieldName1 = comparator.fieldName1; 1735 var fieldName2 = comparator.fieldName2; 1736 var ascending1 = comparator.ascending1; 1737 var ascending2 = comparator.ascending2; 1738 1739 var nodeA = this.snapshot.createNode(); 1740 var nodeB = this.snapshot.createNode(); 1741 1742 function sortByNodeField(fieldName, ascending) 1743 { 1744 var valueOrFunctionA = nodeA[fieldName]; 1745 var valueA = typeof valueOrFunctionA !== "function" ? valueOrFunctionA : valueOrFunctionA.call(nodeA); 1746 var valueOrFunctionB = nodeB[fieldName]; 1747 var valueB = typeof valueOrFunctionB !== "function" ? valueOrFunctionB : valueOrFunctionB.call(nodeB); 1748 var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0); 1749 return ascending ? result : -result; 1750 } 1751 1752 function sortByComparator(indexA, indexB) { 1753 nodeA.nodeIndex = indexA; 1754 nodeB.nodeIndex = indexB; 1755 var result = sortByNodeField(fieldName1, ascending1); 1756 if (result === 0) 1757 result = sortByNodeField(fieldName2, ascending2); 1758 return result; 1759 } 1760 1761 this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count); 1762 }, 1763 1764 __proto__: WebInspector.HeapSnapshotFilteredOrderedIterator.prototype 1765 } 1766 1767
