/* * Copyright (C) 2011 Google Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following disclaimer * in the documentation and/or other materials provided with the * distribution. * * Neither the name of Google Inc. nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** * @constructor */ WebInspector.HeapSnapshotArraySlice = function(array, start, end) { this._array = array; this._start = start; this.length = end - start; } WebInspector.HeapSnapshotArraySlice.prototype = { item: function(index) { return this._array[this._start + index]; }, slice: function(start, end) { if (typeof end === "undefined") end = this.length; return this._array.subarray(this._start + start, this._start + end); } } /** * @constructor * @param {number=} edgeIndex */ WebInspector.HeapSnapshotEdge = function(snapshot, edges, edgeIndex) { this._snapshot = snapshot; this._edges = edges; this.edgeIndex = edgeIndex || 0; } WebInspector.HeapSnapshotEdge.prototype = { clone: function() { return new WebInspector.HeapSnapshotEdge(this._snapshot, this._edges, this.edgeIndex); }, hasStringName: function() { throw new Error("Not implemented"); }, name: function() { throw new Error("Not implemented"); }, node: function() { return this._snapshot.createNode(this.nodeIndex()); }, nodeIndex: function() { return this._edges.item(this.edgeIndex + this._snapshot._edgeToNodeOffset); }, rawEdges: function() { return this._edges; }, toString: function() { return "HeapSnapshotEdge: " + this.name(); }, type: function() { return this._snapshot._edgeTypes[this._type()]; }, serialize: function() { var node = this.node(); return { name: this.name(), node: node.serialize(), nodeIndex: this.nodeIndex(), type: this.type(), distance: node.distance() }; }, _type: function() { return this._edges.item(this.edgeIndex + this._snapshot._edgeTypeOffset); } }; /** * @constructor */ WebInspector.HeapSnapshotEdgeIterator = function(edge) { this.edge = edge; } WebInspector.HeapSnapshotEdgeIterator.prototype = { rewind: function() { this.edge.edgeIndex = 0; }, hasNext: function() { return this.edge.edgeIndex < this.edge._edges.length; }, index: function() { return this.edge.edgeIndex; }, setIndex: function(newIndex) { this.edge.edgeIndex = newIndex; }, item: function() { return this.edge; }, next: function() { this.edge.edgeIndex += this.edge._snapshot._edgeFieldsCount; } }; /** * @constructor */ WebInspector.HeapSnapshotRetainerEdge = function(snapshot, retainedNodeIndex, retainerIndex) { this._snapshot = snapshot; this._retainedNodeIndex = retainedNodeIndex; var retainedNodeOrdinal = retainedNodeIndex / snapshot._nodeFieldCount; this._firstRetainer = snapshot._firstRetainerIndex[retainedNodeOrdinal]; this._retainersCount = snapshot._firstRetainerIndex[retainedNodeOrdinal + 1] - this._firstRetainer; this.setRetainerIndex(retainerIndex); } WebInspector.HeapSnapshotRetainerEdge.prototype = { clone: function() { return new WebInspector.HeapSnapshotRetainerEdge(this._snapshot, this._retainedNodeIndex, this.retainerIndex()); }, hasStringName: function() { return this._edge().hasStringName(); }, name: function() { return this._edge().name(); }, node: function() { return this._node(); }, nodeIndex: function() { return this._nodeIndex; }, retainerIndex: function() { return this._retainerIndex; }, setRetainerIndex: function(newIndex) { if (newIndex !== this._retainerIndex) { this._retainerIndex = newIndex; this.edgeIndex = newIndex; } }, set edgeIndex(edgeIndex) { var retainerIndex = this._firstRetainer + edgeIndex; this._globalEdgeIndex = this._snapshot._retainingEdges[retainerIndex]; this._nodeIndex = this._snapshot._retainingNodes[retainerIndex]; delete this._edgeInstance; delete this._nodeInstance; }, _node: function() { if (!this._nodeInstance) this._nodeInstance = this._snapshot.createNode(this._nodeIndex); return this._nodeInstance; }, _edge: function() { if (!this._edgeInstance) { var edgeIndex = this._globalEdgeIndex - this._node()._edgeIndexesStart(); this._edgeInstance = this._snapshot.createEdge(this._node().rawEdges(), edgeIndex); } return this._edgeInstance; }, toString: function() { return this._edge().toString(); }, serialize: function() { var node = this.node(); return { name: this.name(), node: node.serialize(), nodeIndex: this.nodeIndex(), type: this.type(), distance: node.distance() }; }, type: function() { return this._edge().type(); } } /** * @constructor */ WebInspector.HeapSnapshotRetainerEdgeIterator = function(retainer) { this.retainer = retainer; } WebInspector.HeapSnapshotRetainerEdgeIterator.prototype = { rewind: function() { this.retainer.setRetainerIndex(0); }, hasNext: function() { return this.retainer.retainerIndex() < this.retainer._retainersCount; }, index: function() { return this.retainer.retainerIndex(); }, setIndex: function(newIndex) { this.retainer.setRetainerIndex(newIndex); }, item: function() { return this.retainer; }, next: function() { this.retainer.setRetainerIndex(this.retainer.retainerIndex() + 1); } }; /** * @constructor * @param {number=} nodeIndex */ WebInspector.HeapSnapshotNode = function(snapshot, nodeIndex) { this._snapshot = snapshot; this._firstNodeIndex = nodeIndex; this.nodeIndex = nodeIndex; } WebInspector.HeapSnapshotNode.prototype = { distance: function() { return this._snapshot._nodeDistances[this.nodeIndex / this._snapshot._nodeFieldCount]; }, className: function() { throw new Error("Not implemented"); }, classIndex: function() { throw new Error("Not implemented"); }, dominatorIndex: function() { var nodeFieldCount = this._snapshot._nodeFieldCount; return this._snapshot._dominatorsTree[this.nodeIndex / this._snapshot._nodeFieldCount] * nodeFieldCount; }, edges: function() { return new WebInspector.HeapSnapshotEdgeIterator(this._snapshot.createEdge(this.rawEdges(), 0)); }, edgesCount: function() { return (this._edgeIndexesEnd() - this._edgeIndexesStart()) / this._snapshot._edgeFieldsCount; }, id: function() { throw new Error("Not implemented"); }, isRoot: function() { return this.nodeIndex === this._snapshot._rootNodeIndex; }, name: function() { return this._snapshot._strings[this._name()]; }, rawEdges: function() { return new WebInspector.HeapSnapshotArraySlice(this._snapshot._containmentEdges, this._edgeIndexesStart(), this._edgeIndexesEnd()); }, retainedSize: function() { var snapshot = this._snapshot; return snapshot._nodes[this.nodeIndex + snapshot._nodeRetainedSizeOffset]; }, retainers: function() { return new WebInspector.HeapSnapshotRetainerEdgeIterator(this._snapshot.createRetainingEdge(this.nodeIndex, 0)); }, selfSize: function() { var snapshot = this._snapshot; return snapshot._nodes[this.nodeIndex + snapshot._nodeSelfSizeOffset]; }, type: function() { return this._snapshot._nodeTypes[this._type()]; }, serialize: function() { return { id: this.id(), name: this.name(), distance: this.distance(), nodeIndex: this.nodeIndex, retainedSize: this.retainedSize(), selfSize: this.selfSize(), type: this.type(), }; }, _name: function() { var snapshot = this._snapshot; return snapshot._nodes[this.nodeIndex + snapshot._nodeNameOffset]; }, _edgeIndexesStart: function() { return this._snapshot._firstEdgeIndexes[this._ordinal()]; }, _edgeIndexesEnd: function() { return this._snapshot._firstEdgeIndexes[this._ordinal() + 1]; }, _ordinal: function() { return this.nodeIndex / this._snapshot._nodeFieldCount; }, _nextNodeIndex: function() { return this.nodeIndex + this._snapshot._nodeFieldCount; }, _type: function() { var snapshot = this._snapshot; return snapshot._nodes[this.nodeIndex + snapshot._nodeTypeOffset]; } }; /** * @constructor */ WebInspector.HeapSnapshotNodeIterator = function(node) { this.node = node; this._nodesLength = node._snapshot._nodes.length; } WebInspector.HeapSnapshotNodeIterator.prototype = { rewind: function() { this.node.nodeIndex = this.node._firstNodeIndex; }, hasNext: function() { return this.node.nodeIndex < this._nodesLength; }, index: function() { return this.node.nodeIndex; }, setIndex: function(newIndex) { this.node.nodeIndex = newIndex; }, item: function() { return this.node; }, next: function() { this.node.nodeIndex = this.node._nextNodeIndex(); } } /** * @param{WebInspector.HeapSnapshotWorkerDispatcher=} dispatcher * @constructor */ WebInspector.HeapSnapshotProgress = function(dispatcher) { this._dispatcher = dispatcher; } WebInspector.HeapSnapshotProgress.Event = { Update: "ProgressUpdate" }; WebInspector.HeapSnapshotProgress.prototype = { /** * @param{string} status */ updateStatus: function(status) { this._sendUpdateEvent(WebInspector.UIString(status)); }, /** * @param{string} title * @param{number} value * @param{number} total */ updateProgress: function(title, value, total) { var percentValue = ((total ? (value / total) : 0) * 100).toFixed(0); this._sendUpdateEvent(WebInspector.UIString(title, percentValue)); }, /** * @param{string} text */ _sendUpdateEvent: function(text) { // May be undefined in tests. if (this._dispatcher) this._dispatcher.sendEvent(WebInspector.HeapSnapshotProgress.Event.Update, text); } } /** * @param{WebInspector.HeapSnapshotProgress} progress * @constructor */ WebInspector.HeapSnapshot = function(profile, progress) { this.uid = profile.snapshot.uid; this._nodes = profile.nodes; this._containmentEdges = profile.edges; /** @type{HeapSnapshotMetainfo} */ this._metaNode = profile.snapshot.meta; this._strings = profile.strings; this._progress = progress; this._noDistance = -5; this._rootNodeIndex = 0; if (profile.snapshot.root_index) this._rootNodeIndex = profile.snapshot.root_index; this._snapshotDiffs = {}; this._aggregatesForDiff = null; this._init(); } /** * @constructor */ function HeapSnapshotMetainfo() { // New format. this.node_fields = []; this.node_types = []; this.edge_fields = []; this.edge_types = []; this.type_strings = {}; // Old format. this.fields = []; this.types = []; } /** * @constructor */ function HeapSnapshotHeader() { // New format. this.title = ""; this.uid = 0; this.meta = new HeapSnapshotMetainfo(); this.node_count = 0; this.edge_count = 0; } WebInspector.HeapSnapshot.prototype = { _init: function() { var meta = this._metaNode; this._nodeTypeOffset = meta.node_fields.indexOf("type"); this._nodeNameOffset = meta.node_fields.indexOf("name"); this._nodeIdOffset = meta.node_fields.indexOf("id"); this._nodeSelfSizeOffset = meta.node_fields.indexOf("self_size"); this._nodeEdgeCountOffset = meta.node_fields.indexOf("edge_count"); this._nodeFieldCount = meta.node_fields.length; this._nodeTypes = meta.node_types[this._nodeTypeOffset]; this._nodeHiddenType = this._nodeTypes.indexOf("hidden"); this._nodeObjectType = this._nodeTypes.indexOf("object"); this._nodeNativeType = this._nodeTypes.indexOf("native"); this._nodeCodeType = this._nodeTypes.indexOf("code"); this._nodeSyntheticType = this._nodeTypes.indexOf("synthetic"); this._edgeFieldsCount = meta.edge_fields.length; this._edgeTypeOffset = meta.edge_fields.indexOf("type"); this._edgeNameOffset = meta.edge_fields.indexOf("name_or_index"); this._edgeToNodeOffset = meta.edge_fields.indexOf("to_node"); this._edgeTypes = meta.edge_types[this._edgeTypeOffset]; this._edgeTypes.push("invisible"); this._edgeElementType = this._edgeTypes.indexOf("element"); this._edgeHiddenType = this._edgeTypes.indexOf("hidden"); this._edgeInternalType = this._edgeTypes.indexOf("internal"); this._edgeShortcutType = this._edgeTypes.indexOf("shortcut"); this._edgeWeakType = this._edgeTypes.indexOf("weak"); this._edgeInvisibleType = this._edgeTypes.indexOf("invisible"); this.nodeCount = this._nodes.length / this._nodeFieldCount; this._edgeCount = this._containmentEdges.length / this._edgeFieldsCount; this._progress.updateStatus("Building edge indexes\u2026"); this._buildEdgeIndexes(); this._progress.updateStatus("Marking invisible edges\u2026"); this._markInvisibleEdges(); this._progress.updateStatus("Building retainers\u2026"); this._buildRetainers(); this._progress.updateStatus("Calculating node flags\u2026"); this._calculateFlags(); this._progress.updateStatus("Calculating distances\u2026"); this._calculateDistances(); this._progress.updateStatus("Building postorder index\u2026"); var result = this._buildPostOrderIndex(); // Actually it is array that maps node ordinal number to dominator node ordinal number. this._progress.updateStatus("Building dominator tree\u2026"); this._dominatorsTree = this._buildDominatorTree(result.postOrderIndex2NodeOrdinal, result.nodeOrdinal2PostOrderIndex); this._progress.updateStatus("Calculating retained sizes\u2026"); this._calculateRetainedSizes(result.postOrderIndex2NodeOrdinal); this._progress.updateStatus("Buiding dominated nodes\u2026"); this._buildDominatedNodes(); this._progress.updateStatus("Finished processing."); }, _buildEdgeIndexes: function() { var nodes = this._nodes; var nodeCount = this.nodeCount; var firstEdgeIndexes = this._firstEdgeIndexes = new Uint32Array(nodeCount + 1); var nodeFieldCount = this._nodeFieldCount; var edgeFieldsCount = this._edgeFieldsCount; var nodeEdgeCountOffset = this._nodeEdgeCountOffset; firstEdgeIndexes[nodeCount] = this._containmentEdges.length; for (var nodeOrdinal = 0, edgeIndex = 0; nodeOrdinal < nodeCount; ++nodeOrdinal) { firstEdgeIndexes[nodeOrdinal] = edgeIndex; edgeIndex += nodes[nodeOrdinal * nodeFieldCount + nodeEdgeCountOffset] * edgeFieldsCount; } }, _buildRetainers: function() { var retainingNodes = this._retainingNodes = new Uint32Array(this._edgeCount); var retainingEdges = this._retainingEdges = new Uint32Array(this._edgeCount); // Index of the first retainer in the _retainingNodes and _retainingEdges // arrays. Addressed by retained node index. var firstRetainerIndex = this._firstRetainerIndex = new Uint32Array(this.nodeCount + 1); var containmentEdges = this._containmentEdges; var edgeFieldsCount = this._edgeFieldsCount; var nodeFieldCount = this._nodeFieldCount; var edgeToNodeOffset = this._edgeToNodeOffset; var nodes = this._nodes; var firstEdgeIndexes = this._firstEdgeIndexes; var nodeCount = this.nodeCount; for (var toNodeFieldIndex = edgeToNodeOffset, l = containmentEdges.length; toNodeFieldIndex < l; toNodeFieldIndex += edgeFieldsCount) { var toNodeIndex = containmentEdges[toNodeFieldIndex]; if (toNodeIndex % nodeFieldCount) throw new Error("Invalid toNodeIndex " + toNodeIndex); ++firstRetainerIndex[toNodeIndex / nodeFieldCount]; } for (var i = 0, firstUnusedRetainerSlot = 0; i < nodeCount; i++) { var retainersCount = firstRetainerIndex[i]; firstRetainerIndex[i] = firstUnusedRetainerSlot; retainingNodes[firstUnusedRetainerSlot] = retainersCount; firstUnusedRetainerSlot += retainersCount; } firstRetainerIndex[nodeCount] = retainingNodes.length; var nextNodeFirstEdgeIndex = firstEdgeIndexes[0]; for (var srcNodeOrdinal = 0; srcNodeOrdinal < nodeCount; ++srcNodeOrdinal) { var firstEdgeIndex = nextNodeFirstEdgeIndex; nextNodeFirstEdgeIndex = firstEdgeIndexes[srcNodeOrdinal + 1]; var srcNodeIndex = srcNodeOrdinal * nodeFieldCount; for (var edgeIndex = firstEdgeIndex; edgeIndex < nextNodeFirstEdgeIndex; edgeIndex += edgeFieldsCount) { var toNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; if (toNodeIndex % nodeFieldCount) throw new Error("Invalid toNodeIndex " + toNodeIndex); var firstRetainerSlotIndex = firstRetainerIndex[toNodeIndex / nodeFieldCount]; var nextUnusedRetainerSlotIndex = firstRetainerSlotIndex + (--retainingNodes[firstRetainerSlotIndex]); retainingNodes[nextUnusedRetainerSlotIndex] = srcNodeIndex; retainingEdges[nextUnusedRetainerSlotIndex] = edgeIndex; } } }, /** * @param {number=} nodeIndex */ createNode: function(nodeIndex) { throw new Error("Not implemented"); }, createEdge: function(edges, edgeIndex) { throw new Error("Not implemented"); }, createRetainingEdge: function(retainedNodeIndex, retainerIndex) { throw new Error("Not implemented"); }, dispose: function() { delete this._nodes; delete this._strings; delete this._retainingEdges; delete this._retainingNodes; delete this._firstRetainerIndex; if (this._aggregates) { delete this._aggregates; delete this._aggregatesSortedFlags; } delete this._dominatedNodes; delete this._firstDominatedNodeIndex; delete this._nodeDistances; delete this._dominatorsTree; }, _allNodes: function() { return new WebInspector.HeapSnapshotNodeIterator(this.rootNode()); }, rootNode: function() { return this.createNode(this._rootNodeIndex); }, get rootNodeIndex() { return this._rootNodeIndex; }, get totalSize() { return this.rootNode().retainedSize(); }, _getDominatedIndex: function(nodeIndex) { if (nodeIndex % this._nodeFieldCount) throw new Error("Invalid nodeIndex: " + nodeIndex); return this._firstDominatedNodeIndex[nodeIndex / this._nodeFieldCount]; }, _dominatedNodesOfNode: function(node) { var dominatedIndexFrom = this._getDominatedIndex(node.nodeIndex); var dominatedIndexTo = this._getDominatedIndex(node._nextNodeIndex()); return new WebInspector.HeapSnapshotArraySlice(this._dominatedNodes, dominatedIndexFrom, dominatedIndexTo); }, /** * @param {boolean} sortedIndexes * @param {string} key * @param {string=} filterString */ aggregates: function(sortedIndexes, key, filterString) { if (!this._aggregates) { this._aggregates = {}; this._aggregatesSortedFlags = {}; } var aggregatesByClassName = this._aggregates[key]; if (aggregatesByClassName) { if (sortedIndexes && !this._aggregatesSortedFlags[key]) { this._sortAggregateIndexes(aggregatesByClassName); this._aggregatesSortedFlags[key] = sortedIndexes; } return aggregatesByClassName; } var filter; if (filterString) filter = this._parseFilter(filterString); var aggregates = this._buildAggregates(filter); this._calculateClassesRetainedSize(aggregates.aggregatesByClassIndex, filter); aggregatesByClassName = aggregates.aggregatesByClassName; if (sortedIndexes) this._sortAggregateIndexes(aggregatesByClassName); this._aggregatesSortedFlags[key] = sortedIndexes; this._aggregates[key] = aggregatesByClassName; return aggregatesByClassName; }, aggregatesForDiff: function() { if (this._aggregatesForDiff) return this._aggregatesForDiff; var aggregatesByClassName = this.aggregates(true, "allObjects"); this._aggregatesForDiff = {}; var node = this.createNode(); for (var className in aggregatesByClassName) { var aggregate = aggregatesByClassName[className]; var indexes = aggregate.idxs; var ids = new Array(indexes.length); var selfSizes = new Array(indexes.length); for (var i = 0; i < indexes.length; i++) { node.nodeIndex = indexes[i]; ids[i] = node.id(); selfSizes[i] = node.selfSize(); } this._aggregatesForDiff[className] = { indexes: indexes, ids: ids, selfSizes: selfSizes }; } return this._aggregatesForDiff; }, /** * @param {!WebInspector.HeapSnapshotNode} node * @return {!boolean} */ _isUserRoot: function(node) { return true; }, /** * @param {function(!WebInspector.HeapSnapshotNode)} action * @param {boolean=} userRootsOnly */ forEachRoot: function(action, userRootsOnly) { for (var iter = this.rootNode().edges(); iter.hasNext(); iter.next()) { var node = iter.edge.node(); if (!userRootsOnly || this._isUserRoot(node)) action(node); } }, _calculateDistances: function() { var nodeFieldCount = this._nodeFieldCount; var nodeCount = this.nodeCount; var distances = new Int32Array(nodeCount); var noDistance = this._noDistance; for (var i = 0; i < nodeCount; ++i) distances[i] = noDistance; var nodesToVisit = new Uint32Array(this.nodeCount); var nodesToVisitLength = 0; /** * @param {!WebInspector.HeapSnapshotNode} node */ function enqueueNode(node) { var ordinal = node._ordinal(); if (distances[ordinal] !== noDistance) return; distances[ordinal] = 0; nodesToVisit[nodesToVisitLength++] = node.nodeIndex; } this.forEachRoot(enqueueNode, true); this._bfs(nodesToVisit, nodesToVisitLength, distances); // bfs for the rest of objects nodesToVisitLength = 0; this.forEachRoot(enqueueNode); this._bfs(nodesToVisit, nodesToVisitLength, distances); this._nodeDistances = distances; }, /** * @param {!Uint32Array} nodesToVisit * @param {!number} nodesToVisitLength * @param {!Int32Array} distances */ _bfs: function(nodesToVisit, nodesToVisitLength, distances) { // Preload fields into local variables for better performance. var edgeFieldsCount = this._edgeFieldsCount; var nodeFieldCount = this._nodeFieldCount; var containmentEdges = this._containmentEdges; var firstEdgeIndexes = this._firstEdgeIndexes; var edgeToNodeOffset = this._edgeToNodeOffset; var edgeTypeOffset = this._edgeTypeOffset; var nodes = this._nodes; var nodeCount = this.nodeCount; var containmentEdgesLength = containmentEdges.length; var edgeWeakType = this._edgeWeakType; var noDistance = this._noDistance; var index = 0; while (index < nodesToVisitLength) { var nodeIndex = nodesToVisit[index++]; // shift generates too much garbage. var nodeOrdinal = nodeIndex / nodeFieldCount; var distance = distances[nodeOrdinal] + 1; var firstEdgeIndex = firstEdgeIndexes[nodeOrdinal]; var edgesEnd = firstEdgeIndexes[nodeOrdinal + 1]; for (var edgeIndex = firstEdgeIndex; edgeIndex < edgesEnd; edgeIndex += edgeFieldsCount) { var edgeType = containmentEdges[edgeIndex + edgeTypeOffset]; if (edgeType == edgeWeakType) continue; var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; var childNodeOrdinal = childNodeIndex / nodeFieldCount; if (distances[childNodeOrdinal] !== noDistance) continue; distances[childNodeOrdinal] = distance; nodesToVisit[nodesToVisitLength++] = childNodeIndex; } } if (nodesToVisitLength > nodeCount) throw new Error("BFS failed. Nodes to visit (" + nodesToVisitLength + ") is more than nodes count (" + nodeCount + ")"); }, _buildAggregates: function(filter) { var aggregates = {}; var aggregatesByClassName = {}; var classIndexes = []; var nodes = this._nodes; var mapAndFlag = this.userObjectsMapAndFlag(); var flags = mapAndFlag ? mapAndFlag.map : null; var flag = mapAndFlag ? mapAndFlag.flag : 0; var nodesLength = nodes.length; var nodeNativeType = this._nodeNativeType; var nodeFieldCount = this._nodeFieldCount; var selfSizeOffset = this._nodeSelfSizeOffset; var nodeTypeOffset = this._nodeTypeOffset; var node = this.rootNode(); var nodeDistances = this._nodeDistances; for (var nodeIndex = 0; nodeIndex < nodesLength; nodeIndex += nodeFieldCount) { var nodeOrdinal = nodeIndex / nodeFieldCount; if (flags && !(flags[nodeOrdinal] & flag)) continue; node.nodeIndex = nodeIndex; if (filter && !filter(node)) continue; var selfSize = nodes[nodeIndex + selfSizeOffset]; if (!selfSize && nodes[nodeIndex + nodeTypeOffset] !== nodeNativeType) continue; var classIndex = node.classIndex(); if (!(classIndex in aggregates)) { var nodeType = node.type(); var nameMatters = nodeType === "object" || nodeType === "native"; var value = { count: 1, distance: nodeDistances[nodeOrdinal], self: selfSize, maxRet: 0, type: nodeType, name: nameMatters ? node.name() : null, idxs: [nodeIndex] }; aggregates[classIndex] = value; classIndexes.push(classIndex); aggregatesByClassName[node.className()] = value; } else { var clss = aggregates[classIndex]; clss.distance = Math.min(clss.distance, nodeDistances[nodeOrdinal]); ++clss.count; clss.self += selfSize; clss.idxs.push(nodeIndex); } } // Shave off provisionally allocated space. for (var i = 0, l = classIndexes.length; i < l; ++i) { var classIndex = classIndexes[i]; aggregates[classIndex].idxs = aggregates[classIndex].idxs.slice(); } return {aggregatesByClassName: aggregatesByClassName, aggregatesByClassIndex: aggregates}; }, _calculateClassesRetainedSize: function(aggregates, filter) { var rootNodeIndex = this._rootNodeIndex; var node = this.createNode(rootNodeIndex); var list = [rootNodeIndex]; var sizes = [-1]; var classes = []; var seenClassNameIndexes = {}; var nodeFieldCount = this._nodeFieldCount; var nodeTypeOffset = this._nodeTypeOffset; var nodeNativeType = this._nodeNativeType; var dominatedNodes = this._dominatedNodes; var nodes = this._nodes; var mapAndFlag = this.userObjectsMapAndFlag(); var flags = mapAndFlag ? mapAndFlag.map : null; var flag = mapAndFlag ? mapAndFlag.flag : 0; var firstDominatedNodeIndex = this._firstDominatedNodeIndex; while (list.length) { var nodeIndex = list.pop(); node.nodeIndex = nodeIndex; var classIndex = node.classIndex(); var seen = !!seenClassNameIndexes[classIndex]; var nodeOrdinal = nodeIndex / nodeFieldCount; var dominatedIndexFrom = firstDominatedNodeIndex[nodeOrdinal]; var dominatedIndexTo = firstDominatedNodeIndex[nodeOrdinal + 1]; if (!seen && (!flags || (flags[nodeOrdinal] & flag)) && (!filter || filter(node)) && (node.selfSize() || nodes[nodeIndex + nodeTypeOffset] === nodeNativeType) ) { aggregates[classIndex].maxRet += node.retainedSize(); if (dominatedIndexFrom !== dominatedIndexTo) { seenClassNameIndexes[classIndex] = true; sizes.push(list.length); classes.push(classIndex); } } for (var i = dominatedIndexFrom; i < dominatedIndexTo; i++) list.push(dominatedNodes[i]); var l = list.length; while (sizes[sizes.length - 1] === l) { sizes.pop(); classIndex = classes.pop(); seenClassNameIndexes[classIndex] = false; } } }, _sortAggregateIndexes: function(aggregates) { var nodeA = this.createNode(); var nodeB = this.createNode(); for (var clss in aggregates) aggregates[clss].idxs.sort( function(idxA, idxB) { nodeA.nodeIndex = idxA; nodeB.nodeIndex = idxB; return nodeA.id() < nodeB.id() ? -1 : 1; }); }, _buildPostOrderIndex: function() { var nodeFieldCount = this._nodeFieldCount; var nodes = this._nodes; var nodeCount = this.nodeCount; var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount; var edgeFieldsCount = this._edgeFieldsCount; var edgeTypeOffset = this._edgeTypeOffset; var edgeToNodeOffset = this._edgeToNodeOffset; var edgeShortcutType = this._edgeShortcutType; var firstEdgeIndexes = this._firstEdgeIndexes; var containmentEdges = this._containmentEdges; var containmentEdgesLength = this._containmentEdges.length; var mapAndFlag = this.userObjectsMapAndFlag(); var flags = mapAndFlag ? mapAndFlag.map : null; var flag = mapAndFlag ? mapAndFlag.flag : 0; var nodesToVisit = new Uint32Array(nodeCount); var postOrderIndex2NodeOrdinal = new Uint32Array(nodeCount); var nodeOrdinal2PostOrderIndex = new Uint32Array(nodeCount); var painted = new Uint8Array(nodeCount); var nodesToVisitLength = 0; var postOrderIndex = 0; var grey = 1; var black = 2; nodesToVisit[nodesToVisitLength++] = rootNodeOrdinal; painted[rootNodeOrdinal] = grey; while (nodesToVisitLength) { var nodeOrdinal = nodesToVisit[nodesToVisitLength - 1]; if (painted[nodeOrdinal] === grey) { painted[nodeOrdinal] = black; var nodeFlag = !flags || (flags[nodeOrdinal] & flag); var beginEdgeIndex = firstEdgeIndexes[nodeOrdinal]; var endEdgeIndex = firstEdgeIndexes[nodeOrdinal + 1]; for (var edgeIndex = beginEdgeIndex; edgeIndex < endEdgeIndex; edgeIndex += edgeFieldsCount) { if (nodeOrdinal !== rootNodeOrdinal && containmentEdges[edgeIndex + edgeTypeOffset] === edgeShortcutType) continue; var childNodeIndex = containmentEdges[edgeIndex + edgeToNodeOffset]; var childNodeOrdinal = childNodeIndex / nodeFieldCount; var childNodeFlag = !flags || (flags[childNodeOrdinal] & flag); // We are skipping the edges from non-page-owned nodes to page-owned nodes. // Otherwise the dominators for the objects that also were retained by debugger would be affected. if (nodeOrdinal !== rootNodeOrdinal && childNodeFlag && !nodeFlag) continue; if (!painted[childNodeOrdinal]) { painted[childNodeOrdinal] = grey; nodesToVisit[nodesToVisitLength++] = childNodeOrdinal; } } } else { nodeOrdinal2PostOrderIndex[nodeOrdinal] = postOrderIndex; postOrderIndex2NodeOrdinal[postOrderIndex++] = nodeOrdinal; --nodesToVisitLength; } } if (postOrderIndex !== nodeCount) { console.log("Error: Corrupted snapshot. " + (nodeCount - postOrderIndex) + " nodes are unreachable from the root:"); var dumpNode = this.rootNode(); for (var i = 0; i < nodeCount; ++i) { if (painted[i] !== black) { // Fix it by giving the node a postorder index anyway. nodeOrdinal2PostOrderIndex[i] = postOrderIndex; postOrderIndex2NodeOrdinal[postOrderIndex++] = i; dumpNode.nodeIndex = i * nodeFieldCount; console.log(JSON.stringify(dumpNode.serialize())); for (var retainers = dumpNode.retainers(); retainers.hasNext(); retainers = retainers.item().node().retainers()) console.log(" edgeName: " + retainers.item().name() + " nodeClassName: " + retainers.item().node().className()); } } } return {postOrderIndex2NodeOrdinal: postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex: nodeOrdinal2PostOrderIndex}; }, // The algorithm is based on the article: // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm" // Softw. Pract. Exper. 4 (2001), pp. 1-10. /** * @param {Array.} postOrderIndex2NodeOrdinal * @param {Array.} nodeOrdinal2PostOrderIndex */ _buildDominatorTree: function(postOrderIndex2NodeOrdinal, nodeOrdinal2PostOrderIndex) { var nodeFieldCount = this._nodeFieldCount; var nodes = this._nodes; var firstRetainerIndex = this._firstRetainerIndex; var retainingNodes = this._retainingNodes; var retainingEdges = this._retainingEdges; var edgeFieldsCount = this._edgeFieldsCount; var edgeTypeOffset = this._edgeTypeOffset; var edgeToNodeOffset = this._edgeToNodeOffset; var edgeShortcutType = this._edgeShortcutType; var firstEdgeIndexes = this._firstEdgeIndexes; var containmentEdges = this._containmentEdges; var containmentEdgesLength = this._containmentEdges.length; var rootNodeIndex = this._rootNodeIndex; var mapAndFlag = this.userObjectsMapAndFlag(); var flags = mapAndFlag ? mapAndFlag.map : null; var flag = mapAndFlag ? mapAndFlag.flag : 0; var nodesCount = postOrderIndex2NodeOrdinal.length; var rootPostOrderedIndex = nodesCount - 1; var noEntry = nodesCount; var dominators = new Uint32Array(nodesCount); for (var i = 0; i < rootPostOrderedIndex; ++i) dominators[i] = noEntry; dominators[rootPostOrderedIndex] = rootPostOrderedIndex; // The affected array is used to mark entries which dominators // have to be racalculated because of changes in their retainers. var affected = new Uint8Array(nodesCount); var nodeOrdinal; { // Mark the root direct children as affected. nodeOrdinal = this._rootNodeIndex / nodeFieldCount; var beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset; var endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1]; for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex; toNodeFieldIndex < endEdgeToNodeFieldIndex; toNodeFieldIndex += edgeFieldsCount) { var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount; affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1; } } var changed = true; while (changed) { changed = false; for (var postOrderIndex = rootPostOrderedIndex - 1; postOrderIndex >= 0; --postOrderIndex) { if (affected[postOrderIndex] === 0) continue; affected[postOrderIndex] = 0; // If dominator of the entry has already been set to root, // then it can't propagate any further. if (dominators[postOrderIndex] === rootPostOrderedIndex) continue; nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; var nodeFlag = !flags || (flags[nodeOrdinal] & flag); var newDominatorIndex = noEntry; var beginRetainerIndex = firstRetainerIndex[nodeOrdinal]; var endRetainerIndex = firstRetainerIndex[nodeOrdinal + 1]; for (var retainerIndex = beginRetainerIndex; retainerIndex < endRetainerIndex; ++retainerIndex) { var retainerEdgeIndex = retainingEdges[retainerIndex]; var retainerEdgeType = containmentEdges[retainerEdgeIndex + edgeTypeOffset]; var retainerNodeIndex = retainingNodes[retainerIndex]; if (retainerNodeIndex !== rootNodeIndex && retainerEdgeType === edgeShortcutType) continue; var retainerNodeOrdinal = retainerNodeIndex / nodeFieldCount; var retainerNodeFlag = !flags || (flags[retainerNodeOrdinal] & flag); // We are skipping the edges from non-page-owned nodes to page-owned nodes. // Otherwise the dominators for the objects that also were retained by debugger would be affected. if (retainerNodeIndex !== rootNodeIndex && nodeFlag && !retainerNodeFlag) continue; var retanerPostOrderIndex = nodeOrdinal2PostOrderIndex[retainerNodeOrdinal]; if (dominators[retanerPostOrderIndex] !== noEntry) { if (newDominatorIndex === noEntry) newDominatorIndex = retanerPostOrderIndex; else { while (retanerPostOrderIndex !== newDominatorIndex) { while (retanerPostOrderIndex < newDominatorIndex) retanerPostOrderIndex = dominators[retanerPostOrderIndex]; while (newDominatorIndex < retanerPostOrderIndex) newDominatorIndex = dominators[newDominatorIndex]; } } // If idom has already reached the root, it doesn't make sense // to check other retainers. if (newDominatorIndex === rootPostOrderedIndex) break; } } if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) { dominators[postOrderIndex] = newDominatorIndex; changed = true; nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; beginEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal] + edgeToNodeOffset; endEdgeToNodeFieldIndex = firstEdgeIndexes[nodeOrdinal + 1]; for (var toNodeFieldIndex = beginEdgeToNodeFieldIndex; toNodeFieldIndex < endEdgeToNodeFieldIndex; toNodeFieldIndex += edgeFieldsCount) { var childNodeOrdinal = containmentEdges[toNodeFieldIndex] / nodeFieldCount; affected[nodeOrdinal2PostOrderIndex[childNodeOrdinal]] = 1; } } } } var dominatorsTree = new Uint32Array(nodesCount); for (var postOrderIndex = 0, l = dominators.length; postOrderIndex < l; ++postOrderIndex) { nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; dominatorsTree[nodeOrdinal] = postOrderIndex2NodeOrdinal[dominators[postOrderIndex]]; } return dominatorsTree; }, _calculateRetainedSizes: function(postOrderIndex2NodeOrdinal) { var nodeCount = this.nodeCount; var nodes = this._nodes; var nodeSelfSizeOffset = this._nodeSelfSizeOffset; var nodeFieldCount = this._nodeFieldCount; var dominatorsTree = this._dominatorsTree; // Reuse now unused edge_count field to store retained size. var nodeRetainedSizeOffset = this._nodeRetainedSizeOffset = this._nodeEdgeCountOffset; delete this._nodeEdgeCountOffset; for (var nodeIndex = 0, l = nodes.length; nodeIndex < l; nodeIndex += nodeFieldCount) nodes[nodeIndex + nodeRetainedSizeOffset] = nodes[nodeIndex + nodeSelfSizeOffset]; // Propagate retained sizes for each node excluding root. for (var postOrderIndex = 0; postOrderIndex < nodeCount - 1; ++postOrderIndex) { var nodeOrdinal = postOrderIndex2NodeOrdinal[postOrderIndex]; var nodeIndex = nodeOrdinal * nodeFieldCount; var dominatorIndex = dominatorsTree[nodeOrdinal] * nodeFieldCount; nodes[dominatorIndex + nodeRetainedSizeOffset] += nodes[nodeIndex + nodeRetainedSizeOffset]; } }, _buildDominatedNodes: function() { // Builds up two arrays: // - "dominatedNodes" is a continuous array, where each node owns an // interval (can be empty) with corresponding dominated nodes. // - "indexArray" is an array of indexes in the "dominatedNodes" // with the same positions as in the _nodeIndex. var indexArray = this._firstDominatedNodeIndex = new Uint32Array(this.nodeCount + 1); // All nodes except the root have dominators. var dominatedNodes = this._dominatedNodes = new Uint32Array(this.nodeCount - 1); // Count the number of dominated nodes for each node. Skip the root (node at // index 0) as it is the only node that dominates itself. var nodeFieldCount = this._nodeFieldCount; var dominatorsTree = this._dominatorsTree; var fromNodeOrdinal = 0; var toNodeOrdinal = this.nodeCount; var rootNodeOrdinal = this._rootNodeIndex / nodeFieldCount; if (rootNodeOrdinal === fromNodeOrdinal) fromNodeOrdinal = 1; else if (rootNodeOrdinal === toNodeOrdinal - 1) toNodeOrdinal = toNodeOrdinal - 1; else throw new Error("Root node is expected to be either first or last"); for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) ++indexArray[dominatorsTree[nodeOrdinal]]; // Put in the first slot of each dominatedNodes slice the count of entries // that will be filled. var firstDominatedNodeIndex = 0; for (var i = 0, l = this.nodeCount; i < l; ++i) { var dominatedCount = dominatedNodes[firstDominatedNodeIndex] = indexArray[i]; indexArray[i] = firstDominatedNodeIndex; firstDominatedNodeIndex += dominatedCount; } indexArray[this.nodeCount] = dominatedNodes.length; // Fill up the dominatedNodes array with indexes of dominated nodes. Skip the root (node at // index 0) as it is the only node that dominates itself. for (var nodeOrdinal = fromNodeOrdinal; nodeOrdinal < toNodeOrdinal; ++nodeOrdinal) { var dominatorOrdinal = dominatorsTree[nodeOrdinal]; var dominatedRefIndex = indexArray[dominatorOrdinal]; dominatedRefIndex += (--dominatedNodes[dominatedRefIndex]); dominatedNodes[dominatedRefIndex] = nodeOrdinal * nodeFieldCount; } }, _markInvisibleEdges: function() { throw new Error("Not implemented"); }, _calculateFlags: function() { throw new Error("Not implemented"); }, userObjectsMapAndFlag: function() { throw new Error("Not implemented"); }, calculateSnapshotDiff: function(baseSnapshotId, baseSnapshotAggregates) { var snapshotDiff = this._snapshotDiffs[baseSnapshotId]; if (snapshotDiff) return snapshotDiff; snapshotDiff = {}; var aggregates = this.aggregates(true, "allObjects"); for (var className in baseSnapshotAggregates) { var baseAggregate = baseSnapshotAggregates[className]; var diff = this._calculateDiffForClass(baseAggregate, aggregates[className]); if (diff) snapshotDiff[className] = diff; } var emptyBaseAggregate = { ids: [], indexes: [], selfSizes: [] }; for (var className in aggregates) { if (className in baseSnapshotAggregates) continue; snapshotDiff[className] = this._calculateDiffForClass(emptyBaseAggregate, aggregates[className]); } this._snapshotDiffs[baseSnapshotId] = snapshotDiff; return snapshotDiff; }, _calculateDiffForClass: function(baseAggregate, aggregate) { var baseIds = baseAggregate.ids; var baseIndexes = baseAggregate.indexes; var baseSelfSizes = baseAggregate.selfSizes; var indexes = aggregate ? aggregate.idxs : []; var i = 0, l = baseIds.length; var j = 0, m = indexes.length; var diff = { addedCount: 0, removedCount: 0, addedSize: 0, removedSize: 0, deletedIndexes: [], addedIndexes: [] }; var nodeB = this.createNode(indexes[j]); while (i < l && j < m) { var nodeAId = baseIds[i]; if (nodeAId < nodeB.id()) { diff.deletedIndexes.push(baseIndexes[i]); diff.removedCount++; diff.removedSize += baseSelfSizes[i]; ++i; } else if (nodeAId > nodeB.id()) { // Native nodes(e.g. dom groups) may have ids less than max JS object id in the base snapshot diff.addedIndexes.push(indexes[j]); diff.addedCount++; diff.addedSize += nodeB.selfSize(); nodeB.nodeIndex = indexes[++j]; } else { // nodeAId === nodeB.id() ++i; nodeB.nodeIndex = indexes[++j]; } } while (i < l) { diff.deletedIndexes.push(baseIndexes[i]); diff.removedCount++; diff.removedSize += baseSelfSizes[i]; ++i; } while (j < m) { diff.addedIndexes.push(indexes[j]); diff.addedCount++; diff.addedSize += nodeB.selfSize(); nodeB.nodeIndex = indexes[++j]; } diff.countDelta = diff.addedCount - diff.removedCount; diff.sizeDelta = diff.addedSize - diff.removedSize; if (!diff.addedCount && !diff.removedCount) return null; return diff; }, _nodeForSnapshotObjectId: function(snapshotObjectId) { for (var it = this._allNodes(); it.hasNext(); it.next()) { if (it.node.id() === snapshotObjectId) return it.node; } return null; }, nodeClassName: function(snapshotObjectId) { var node = this._nodeForSnapshotObjectId(snapshotObjectId); if (node) return node.className(); return null; }, dominatorIdsForNode: function(snapshotObjectId) { var node = this._nodeForSnapshotObjectId(snapshotObjectId); if (!node) return null; var result = []; while (!node.isRoot()) { result.push(node.id()); node.nodeIndex = node.dominatorIndex(); } return result; }, _parseFilter: function(filter) { if (!filter) return null; var parsedFilter = eval("(function(){return " + filter + "})()"); return parsedFilter.bind(this); }, createEdgesProvider: function(nodeIndex, showHiddenData) { var node = this.createNode(nodeIndex); var filter = this.containmentEdgesFilter(showHiddenData); return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges()); }, createEdgesProviderForTest: function(nodeIndex, filter) { var node = this.createNode(nodeIndex); return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.edges()); }, retainingEdgesFilter: function(showHiddenData) { return null; }, containmentEdgesFilter: function(showHiddenData) { return null; }, createRetainingEdgesProvider: function(nodeIndex, showHiddenData) { var node = this.createNode(nodeIndex); var filter = this.retainingEdgesFilter(showHiddenData); return new WebInspector.HeapSnapshotEdgesProvider(this, filter, node.retainers()); }, createAddedNodesProvider: function(baseSnapshotId, className) { var snapshotDiff = this._snapshotDiffs[baseSnapshotId]; var diffForClass = snapshotDiff[className]; return new WebInspector.HeapSnapshotNodesProvider(this, null, diffForClass.addedIndexes); }, createDeletedNodesProvider: function(nodeIndexes) { return new WebInspector.HeapSnapshotNodesProvider(this, null, nodeIndexes); }, classNodesFilter: function() { return null; }, createNodesProviderForClass: function(className, aggregatesKey) { return new WebInspector.HeapSnapshotNodesProvider(this, this.classNodesFilter(), this.aggregates(false, aggregatesKey)[className].idxs); }, createNodesProviderForDominator: function(nodeIndex) { var node = this.createNode(nodeIndex); return new WebInspector.HeapSnapshotNodesProvider(this, null, this._dominatedNodesOfNode(node)); }, updateStaticData: function() { return {nodeCount: this.nodeCount, rootNodeIndex: this._rootNodeIndex, totalSize: this.totalSize, uid: this.uid}; } }; /** * @constructor * @param {Array.=} unfilteredIterationOrder */ WebInspector.HeapSnapshotFilteredOrderedIterator = function(iterator, filter, unfilteredIterationOrder) { this._filter = filter; this._iterator = iterator; this._unfilteredIterationOrder = unfilteredIterationOrder; this._iterationOrder = null; this._position = 0; this._currentComparator = null; this._sortedPrefixLength = 0; } WebInspector.HeapSnapshotFilteredOrderedIterator.prototype = { _createIterationOrder: function() { if (this._iterationOrder) return; if (this._unfilteredIterationOrder && !this._filter) { this._iterationOrder = this._unfilteredIterationOrder.slice(0); this._unfilteredIterationOrder = null; return; } this._iterationOrder = []; var iterator = this._iterator; if (!this._unfilteredIterationOrder && !this._filter) { for (iterator.rewind(); iterator.hasNext(); iterator.next()) this._iterationOrder.push(iterator.index()); } else if (!this._unfilteredIterationOrder) { for (iterator.rewind(); iterator.hasNext(); iterator.next()) { if (this._filter(iterator.item())) this._iterationOrder.push(iterator.index()); } } else { var order = this._unfilteredIterationOrder.constructor === Array ? this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0); for (var i = 0, l = order.length; i < l; ++i) { iterator.setIndex(order[i]); if (this._filter(iterator.item())) this._iterationOrder.push(iterator.index()); } this._unfilteredIterationOrder = null; } }, rewind: function() { this._position = 0; }, hasNext: function() { return this._position < this._iterationOrder.length; }, isEmpty: function() { if (this._iterationOrder) return !this._iterationOrder.length; if (this._unfilteredIterationOrder && !this._filter) return !this._unfilteredIterationOrder.length; var iterator = this._iterator; if (!this._unfilteredIterationOrder && !this._filter) { iterator.rewind(); return !iterator.hasNext(); } else if (!this._unfilteredIterationOrder) { for (iterator.rewind(); iterator.hasNext(); iterator.next()) if (this._filter(iterator.item())) return false; } else { var order = this._unfilteredIterationOrder.constructor === Array ? this._unfilteredIterationOrder : this._unfilteredIterationOrder.slice(0); for (var i = 0, l = order.length; i < l; ++i) { iterator.setIndex(order[i]); if (this._filter(iterator.item())) return false; } } return true; }, item: function() { this._iterator.setIndex(this._iterationOrder[this._position]); return this._iterator.item(); }, get length() { this._createIterationOrder(); return this._iterationOrder.length; }, next: function() { ++this._position; }, /** * @param {number} begin * @param {number} end */ serializeItemsRange: function(begin, end) { this._createIterationOrder(); if (begin > end) throw new Error("Start position > end position: " + begin + " > " + end); if (end >= this._iterationOrder.length) end = this._iterationOrder.length; if (this._sortedPrefixLength < end) { this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, end - this._sortedPrefixLength); this._sortedPrefixLength = end; } this._position = begin; var startPosition = this._position; var count = end - begin; var result = new Array(count); for (var i = 0 ; i < count && this.hasNext(); ++i, this.next()) result[i] = this.item().serialize(); result.length = i; result.totalLength = this._iterationOrder.length; result.startPosition = startPosition; result.endPosition = this._position; return result; }, sortAll: function() { this._createIterationOrder(); if (this._sortedPrefixLength === this._iterationOrder.length) return; this.sort(this._currentComparator, this._sortedPrefixLength, this._iterationOrder.length - 1, this._iterationOrder.length); this._sortedPrefixLength = this._iterationOrder.length; }, sortAndRewind: function(comparator) { this._currentComparator = comparator; this._sortedPrefixLength = 0; this.rewind(); } } WebInspector.HeapSnapshotFilteredOrderedIterator.prototype.createComparator = function(fieldNames) { return {fieldName1: fieldNames[0], ascending1: fieldNames[1], fieldName2: fieldNames[2], ascending2: fieldNames[3]}; } /** * @constructor * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator} */ WebInspector.HeapSnapshotEdgesProvider = function(snapshot, filter, edgesIter) { this.snapshot = snapshot; WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, edgesIter, filter); } WebInspector.HeapSnapshotEdgesProvider.prototype = { sort: function(comparator, leftBound, rightBound, count) { var fieldName1 = comparator.fieldName1; var fieldName2 = comparator.fieldName2; var ascending1 = comparator.ascending1; var ascending2 = comparator.ascending2; var edgeA = this._iterator.item().clone(); var edgeB = edgeA.clone(); var nodeA = this.snapshot.createNode(); var nodeB = this.snapshot.createNode(); function compareEdgeFieldName(ascending, indexA, indexB) { edgeA.edgeIndex = indexA; edgeB.edgeIndex = indexB; if (edgeB.name() === "__proto__") return -1; if (edgeA.name() === "__proto__") return 1; var result = edgeA.hasStringName() === edgeB.hasStringName() ? (edgeA.name() < edgeB.name() ? -1 : (edgeA.name() > edgeB.name() ? 1 : 0)) : (edgeA.hasStringName() ? -1 : 1); return ascending ? result : -result; } function compareNodeField(fieldName, ascending, indexA, indexB) { edgeA.edgeIndex = indexA; nodeA.nodeIndex = edgeA.nodeIndex(); var valueA = nodeA[fieldName](); edgeB.edgeIndex = indexB; nodeB.nodeIndex = edgeB.nodeIndex(); var valueB = nodeB[fieldName](); var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0); return ascending ? result : -result; } function compareEdgeAndNode(indexA, indexB) { var result = compareEdgeFieldName(ascending1, indexA, indexB); if (result === 0) result = compareNodeField(fieldName2, ascending2, indexA, indexB); return result; } function compareNodeAndEdge(indexA, indexB) { var result = compareNodeField(fieldName1, ascending1, indexA, indexB); if (result === 0) result = compareEdgeFieldName(ascending2, indexA, indexB); return result; } function compareNodeAndNode(indexA, indexB) { var result = compareNodeField(fieldName1, ascending1, indexA, indexB); if (result === 0) result = compareNodeField(fieldName2, ascending2, indexA, indexB); return result; } if (fieldName1 === "!edgeName") this._iterationOrder.sortRange(compareEdgeAndNode, leftBound, rightBound, count); else if (fieldName2 === "!edgeName") this._iterationOrder.sortRange(compareNodeAndEdge, leftBound, rightBound, count); else this._iterationOrder.sortRange(compareNodeAndNode, leftBound, rightBound, count); }, __proto__: WebInspector.HeapSnapshotFilteredOrderedIterator.prototype } /** * @constructor * @extends {WebInspector.HeapSnapshotFilteredOrderedIterator} * @param {Array.=} nodeIndexes */ WebInspector.HeapSnapshotNodesProvider = function(snapshot, filter, nodeIndexes) { this.snapshot = snapshot; WebInspector.HeapSnapshotFilteredOrderedIterator.call(this, snapshot._allNodes(), filter, nodeIndexes); } WebInspector.HeapSnapshotNodesProvider.prototype = { nodePosition: function(snapshotObjectId) { this._createIterationOrder(); if (this.isEmpty()) return -1; this.sortAll(); var node = this.snapshot.createNode(); for (var i = 0; i < this._iterationOrder.length; i++) { node.nodeIndex = this._iterationOrder[i]; if (node.id() === snapshotObjectId) return i; } return -1; }, sort: function(comparator, leftBound, rightBound, count) { var fieldName1 = comparator.fieldName1; var fieldName2 = comparator.fieldName2; var ascending1 = comparator.ascending1; var ascending2 = comparator.ascending2; var nodeA = this.snapshot.createNode(); var nodeB = this.snapshot.createNode(); function sortByNodeField(fieldName, ascending) { var valueOrFunctionA = nodeA[fieldName]; var valueA = typeof valueOrFunctionA !== "function" ? valueOrFunctionA : valueOrFunctionA.call(nodeA); var valueOrFunctionB = nodeB[fieldName]; var valueB = typeof valueOrFunctionB !== "function" ? valueOrFunctionB : valueOrFunctionB.call(nodeB); var result = valueA < valueB ? -1 : (valueA > valueB ? 1 : 0); return ascending ? result : -result; } function sortByComparator(indexA, indexB) { nodeA.nodeIndex = indexA; nodeB.nodeIndex = indexB; var result = sortByNodeField(fieldName1, ascending1); if (result === 0) result = sortByNodeField(fieldName2, ascending2); return result; } this._iterationOrder.sortRange(sortByComparator, leftBound, rightBound, count); }, __proto__: WebInspector.HeapSnapshotFilteredOrderedIterator.prototype }