1/* 2 * Copyright (C) 2009 280 North 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 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26// Bottom Up Profiling shows the entire callstack backwards: 27// The root node is a representation of each individual function called, and each child of that node represents 28// a reverse-callstack showing how many of those calls came from it. So, unlike top-down, the statistics in 29// each child still represent the root node. We have to be particularly careful of recursion with this mode 30// because a root node can represent itself AND an ancestor. 31 32/** 33 * @constructor 34 * @extends {WebInspector.ProfileDataGridNode} 35 * @param {!ProfilerAgent.CPUProfileNode} profileNode 36 * @param {!WebInspector.TopDownProfileDataGridTree} owningTree 37 */ 38WebInspector.BottomUpProfileDataGridNode = function(profileNode, owningTree) 39{ 40 WebInspector.ProfileDataGridNode.call(this, profileNode, owningTree, this._willHaveChildren(profileNode)); 41 42 this._remainingNodeInfos = []; 43} 44 45WebInspector.BottomUpProfileDataGridNode.prototype = { 46 /** 47 * @param {!WebInspector.ProfileDataGridNode} profileDataGridNode 48 */ 49 _takePropertiesFromProfileDataGridNode: function(profileDataGridNode) 50 { 51 this._save(); 52 53 this.selfTime = profileDataGridNode.selfTime; 54 this.totalTime = profileDataGridNode.totalTime; 55 this.numberOfCalls = profileDataGridNode.numberOfCalls; 56 }, 57 58 /** 59 * When focusing, we keep just the members of the callstack. 60 * @param {!WebInspector.ProfileDataGridNode} child 61 */ 62 _keepOnlyChild: function(child) 63 { 64 this._save(); 65 66 this.removeChildren(); 67 this.appendChild(child); 68 }, 69 70 _exclude: function(aCallUID) 71 { 72 if (this._remainingNodeInfos) 73 this.populate(); 74 75 this._save(); 76 77 var children = this.children; 78 var index = this.children.length; 79 80 while (index--) 81 children[index]._exclude(aCallUID); 82 83 var child = this.childrenByCallUID[aCallUID]; 84 85 if (child) 86 this._merge(child, true); 87 }, 88 89 _restore: function() 90 { 91 WebInspector.ProfileDataGridNode.prototype._restore(); 92 93 if (!this.children.length) 94 this.hasChildren = this._willHaveChildren(this.profileNode); 95 }, 96 97 /** 98 * @param {!WebInspector.ProfileDataGridNode} child 99 * @param {boolean} shouldAbsorb 100 */ 101 _merge: function(child, shouldAbsorb) 102 { 103 this.selfTime -= child.selfTime; 104 105 WebInspector.ProfileDataGridNode.prototype._merge.call(this, child, shouldAbsorb); 106 }, 107 108 _sharedPopulate: function() 109 { 110 var remainingNodeInfos = this._remainingNodeInfos; 111 var count = remainingNodeInfos.length; 112 113 for (var index = 0; index < count; ++index) { 114 var nodeInfo = remainingNodeInfos[index]; 115 var ancestor = nodeInfo.ancestor; 116 var focusNode = nodeInfo.focusNode; 117 var child = this.findChild(ancestor); 118 119 // If we already have this child, then merge the data together. 120 if (child) { 121 var totalTimeAccountedFor = nodeInfo.totalTimeAccountedFor; 122 123 child.selfTime += focusNode.selfTime; 124 child.numberOfCalls += focusNode.numberOfCalls; 125 126 if (!totalTimeAccountedFor) 127 child.totalTime += focusNode.totalTime; 128 } else { 129 // If not, add it as a true ancestor. 130 // In heavy mode, we take our visual identity from ancestor node... 131 child = new WebInspector.BottomUpProfileDataGridNode(ancestor, this.tree); 132 133 if (ancestor !== focusNode) { 134 // but the actual statistics from the "root" node (bottom of the callstack). 135 child.selfTime = focusNode.selfTime; 136 child.totalTime = focusNode.totalTime; 137 child.numberOfCalls = focusNode.numberOfCalls; 138 } 139 140 this.appendChild(child); 141 } 142 143 var parent = ancestor.parent; 144 if (parent && parent.parent) { 145 nodeInfo.ancestor = parent; 146 child._remainingNodeInfos.push(nodeInfo); 147 } 148 } 149 150 delete this._remainingNodeInfos; 151 }, 152 153 _willHaveChildren: function(profileNode) 154 { 155 // In bottom up mode, our parents are our children since we display an inverted tree. 156 // However, we don't want to show the very top parent since it is redundant. 157 return !!(profileNode.parent && profileNode.parent.parent); 158 }, 159 160 __proto__: WebInspector.ProfileDataGridNode.prototype 161} 162 163/** 164 * @constructor 165 * @extends {WebInspector.ProfileDataGridTree} 166 * @param {WebInspector.CPUProfileView} profileView 167 * @param {ProfilerAgent.CPUProfileNode} rootProfileNode 168 */ 169WebInspector.BottomUpProfileDataGridTree = function(profileView, rootProfileNode) 170{ 171 WebInspector.ProfileDataGridTree.call(this, profileView, rootProfileNode); 172 173 // Iterate each node in pre-order. 174 var profileNodeUIDs = 0; 175 var profileNodeGroups = [[], [rootProfileNode]]; 176 var visitedProfileNodesForCallUID = {}; 177 178 this._remainingNodeInfos = []; 179 180 for (var profileNodeGroupIndex = 0; profileNodeGroupIndex < profileNodeGroups.length; ++profileNodeGroupIndex) { 181 var parentProfileNodes = profileNodeGroups[profileNodeGroupIndex]; 182 var profileNodes = profileNodeGroups[++profileNodeGroupIndex]; 183 var count = profileNodes.length; 184 185 for (var index = 0; index < count; ++index) { 186 var profileNode = profileNodes[index]; 187 188 if (!profileNode.UID) 189 profileNode.UID = ++profileNodeUIDs; 190 191 if (profileNode.head && profileNode !== profileNode.head) { 192 // The total time of this ancestor is accounted for if we're in any form of recursive cycle. 193 var visitedNodes = visitedProfileNodesForCallUID[profileNode.callUID]; 194 var totalTimeAccountedFor = false; 195 196 if (!visitedNodes) { 197 visitedNodes = {} 198 visitedProfileNodesForCallUID[profileNode.callUID] = visitedNodes; 199 } else { 200 // The total time for this node has already been accounted for iff one of it's parents has already been visited. 201 // We can do this check in this style because we are traversing the tree in pre-order. 202 var parentCount = parentProfileNodes.length; 203 for (var parentIndex = 0; parentIndex < parentCount; ++parentIndex) { 204 if (visitedNodes[parentProfileNodes[parentIndex].UID]) { 205 totalTimeAccountedFor = true; 206 break; 207 } 208 } 209 } 210 211 visitedNodes[profileNode.UID] = true; 212 213 this._remainingNodeInfos.push({ ancestor:profileNode, focusNode:profileNode, totalTimeAccountedFor:totalTimeAccountedFor }); 214 } 215 216 var children = profileNode.children; 217 if (children.length) { 218 profileNodeGroups.push(parentProfileNodes.concat([profileNode])) 219 profileNodeGroups.push(children); 220 } 221 } 222 } 223 224 // Populate the top level nodes. 225 var any = /** @type{*} */(this); 226 var node = /** @type{WebInspector.ProfileDataGridNode} */(any); 227 WebInspector.BottomUpProfileDataGridNode.prototype.populate.call(node); 228 229 return this; 230} 231 232WebInspector.BottomUpProfileDataGridTree.prototype = { 233 /** 234 * When focusing, we keep the entire callstack up to this ancestor. 235 * @param {!WebInspector.ProfileDataGridNode} profileDataGridNode 236 */ 237 focus: function(profileDataGridNode) 238 { 239 if (!profileDataGridNode) 240 return; 241 242 this._save(); 243 244 var currentNode = profileDataGridNode; 245 var focusNode = profileDataGridNode; 246 247 while (currentNode.parent && (currentNode instanceof WebInspector.ProfileDataGridNode)) { 248 currentNode._takePropertiesFromProfileDataGridNode(profileDataGridNode); 249 250 focusNode = currentNode; 251 currentNode = currentNode.parent; 252 253 if (currentNode instanceof WebInspector.ProfileDataGridNode) 254 currentNode._keepOnlyChild(focusNode); 255 } 256 257 this.children = [focusNode]; 258 this.totalTime = profileDataGridNode.totalTime; 259 }, 260 261 /** 262 * @param {!WebInspector.ProfileDataGridNode} profileDataGridNode 263 */ 264 exclude: function(profileDataGridNode) 265 { 266 if (!profileDataGridNode) 267 return; 268 269 this._save(); 270 271 var excludedCallUID = profileDataGridNode.callUID; 272 var excludedTopLevelChild = this.childrenByCallUID[excludedCallUID]; 273 274 // If we have a top level node that is excluded, get rid of it completely (not keeping children), 275 // since bottom up data relies entirely on the root node. 276 if (excludedTopLevelChild) 277 this.children.remove(excludedTopLevelChild); 278 279 var children = this.children; 280 var count = children.length; 281 282 for (var index = 0; index < count; ++index) 283 children[index]._exclude(excludedCallUID); 284 285 if (this.lastComparator) 286 this.sort(this.lastComparator, true); 287 }, 288 289 _sharedPopulate: WebInspector.BottomUpProfileDataGridNode.prototype._sharedPopulate, 290 291 __proto__: WebInspector.ProfileDataGridTree.prototype 292} 293