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 */ 38 WebInspector.BottomUpProfileDataGridNode = function(profileNode, owningTree) 39 { 40 WebInspector.ProfileDataGridNode.call(this, profileNode, owningTree, this._willHaveChildren(profileNode)); 41 42 this._remainingNodeInfos = []; 43 } 44 45 WebInspector.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 }, 56 57 /** 58 * When focusing, we keep just the members of the callstack. 59 * @param {!WebInspector.ProfileDataGridNode} child 60 */ 61 _keepOnlyChild: function(child) 62 { 63 this.save(); 64 65 this.removeChildren(); 66 this.appendChild(child); 67 }, 68 69 /** 70 * @param {number} aCallUID 71 */ 72 _exclude: function(aCallUID) 73 { 74 if (this._remainingNodeInfos) 75 this.populate(); 76 77 this.save(); 78 79 var children = this.children; 80 var index = this.children.length; 81 82 while (index--) 83 children[index]._exclude(aCallUID); 84 85 var child = this.childrenByCallUID[aCallUID]; 86 87 if (child) 88 this.merge(child, true); 89 }, 90 91 /** 92 * @override 93 */ 94 restore: function() 95 { 96 WebInspector.ProfileDataGridNode.prototype.restore.call(this); 97 98 if (!this.children.length) 99 this.hasChildren = this._willHaveChildren(this.profileNode); 100 }, 101 102 /** 103 * @override 104 * @param {!WebInspector.ProfileDataGridNode} child 105 * @param {boolean} shouldAbsorb 106 */ 107 merge: function(child, shouldAbsorb) 108 { 109 this.selfTime -= child.selfTime; 110 111 WebInspector.ProfileDataGridNode.prototype.merge.call(this, child, shouldAbsorb); 112 }, 113 114 /** 115 * @override 116 */ 117 populateChildren: function() 118 { 119 WebInspector.BottomUpProfileDataGridNode._sharedPopulate(this); 120 }, 121 122 _willHaveChildren: function(profileNode) 123 { 124 // In bottom up mode, our parents are our children since we display an inverted tree. 125 // However, we don't want to show the very top parent since it is redundant. 126 return !!(profileNode.parent && profileNode.parent.parent); 127 }, 128 129 __proto__: WebInspector.ProfileDataGridNode.prototype 130 } 131 132 /** 133 * @param {!WebInspector.BottomUpProfileDataGridNode|!WebInspector.BottomUpProfileDataGridTree} container 134 */ 135 WebInspector.BottomUpProfileDataGridNode._sharedPopulate = function(container) 136 { 137 var remainingNodeInfos = container._remainingNodeInfos; 138 var count = remainingNodeInfos.length; 139 140 for (var index = 0; index < count; ++index) { 141 var nodeInfo = remainingNodeInfos[index]; 142 var ancestor = nodeInfo.ancestor; 143 var focusNode = nodeInfo.focusNode; 144 var child = container.findChild(ancestor); 145 146 // If we already have this child, then merge the data together. 147 if (child) { 148 var totalTimeAccountedFor = nodeInfo.totalTimeAccountedFor; 149 150 child.selfTime += focusNode.selfTime; 151 152 if (!totalTimeAccountedFor) 153 child.totalTime += focusNode.totalTime; 154 } else { 155 // If not, add it as a true ancestor. 156 // In heavy mode, we take our visual identity from ancestor node... 157 child = new WebInspector.BottomUpProfileDataGridNode(ancestor, /** @type {!WebInspector.TopDownProfileDataGridTree} */ (container.tree)); 158 159 if (ancestor !== focusNode) { 160 // But the actual statistics from the "root" node (bottom of the callstack). 161 child.selfTime = focusNode.selfTime; 162 child.totalTime = focusNode.totalTime; 163 } 164 165 container.appendChild(child); 166 } 167 168 var parent = ancestor.parent; 169 if (parent && parent.parent) { 170 nodeInfo.ancestor = parent; 171 child._remainingNodeInfos.push(nodeInfo); 172 } 173 } 174 175 for (var i = 0; i < container.children.length; ++i) 176 container.children[i].buildData(); 177 178 delete container._remainingNodeInfos; 179 } 180 181 /** 182 * @constructor 183 * @extends {WebInspector.ProfileDataGridTree} 184 * @param {!WebInspector.CPUProfileView} profileView 185 * @param {!ProfilerAgent.CPUProfileNode} rootProfileNode 186 */ 187 WebInspector.BottomUpProfileDataGridTree = function(profileView, rootProfileNode) 188 { 189 WebInspector.ProfileDataGridTree.call(this, profileView, rootProfileNode); 190 191 // Iterate each node in pre-order. 192 var profileNodeUIDs = 0; 193 var profileNodeGroups = [[], [rootProfileNode]]; 194 var visitedProfileNodesForCallUID = {}; 195 196 this._remainingNodeInfos = []; 197 198 for (var profileNodeGroupIndex = 0; profileNodeGroupIndex < profileNodeGroups.length; ++profileNodeGroupIndex) { 199 var parentProfileNodes = profileNodeGroups[profileNodeGroupIndex]; 200 var profileNodes = profileNodeGroups[++profileNodeGroupIndex]; 201 var count = profileNodes.length; 202 203 for (var index = 0; index < count; ++index) { 204 var profileNode = profileNodes[index]; 205 206 if (!profileNode.UID) 207 profileNode.UID = ++profileNodeUIDs; 208 209 if (profileNode.parent) { 210 // The total time of this ancestor is accounted for if we're in any form of recursive cycle. 211 var visitedNodes = visitedProfileNodesForCallUID[profileNode.callUID]; 212 var totalTimeAccountedFor = false; 213 214 if (!visitedNodes) { 215 visitedNodes = {} 216 visitedProfileNodesForCallUID[profileNode.callUID] = visitedNodes; 217 } else { 218 // The total time for this node has already been accounted for iff one of it's parents has already been visited. 219 // We can do this check in this style because we are traversing the tree in pre-order. 220 var parentCount = parentProfileNodes.length; 221 for (var parentIndex = 0; parentIndex < parentCount; ++parentIndex) { 222 if (visitedNodes[parentProfileNodes[parentIndex].UID]) { 223 totalTimeAccountedFor = true; 224 break; 225 } 226 } 227 } 228 229 visitedNodes[profileNode.UID] = true; 230 231 this._remainingNodeInfos.push({ ancestor:profileNode, focusNode:profileNode, totalTimeAccountedFor:totalTimeAccountedFor }); 232 } 233 234 var children = profileNode.children; 235 if (children.length) { 236 profileNodeGroups.push(parentProfileNodes.concat([profileNode])) 237 profileNodeGroups.push(children); 238 } 239 } 240 } 241 242 // Populate the top level nodes. 243 WebInspector.ProfileDataGridNode.populate(this); 244 245 return this; 246 } 247 248 WebInspector.BottomUpProfileDataGridTree.prototype = { 249 /** 250 * When focusing, we keep the entire callstack up to this ancestor. 251 * @param {!WebInspector.ProfileDataGridNode} profileDataGridNode 252 */ 253 focus: function(profileDataGridNode) 254 { 255 if (!profileDataGridNode) 256 return; 257 258 this.save(); 259 260 var currentNode = profileDataGridNode; 261 var focusNode = profileDataGridNode; 262 263 while (currentNode.parent && (currentNode instanceof WebInspector.ProfileDataGridNode)) { 264 currentNode._takePropertiesFromProfileDataGridNode(profileDataGridNode); 265 266 focusNode = currentNode; 267 currentNode = currentNode.parent; 268 269 if (currentNode instanceof WebInspector.ProfileDataGridNode) 270 currentNode._keepOnlyChild(focusNode); 271 } 272 273 this.children = [focusNode]; 274 this.totalTime = profileDataGridNode.totalTime; 275 }, 276 277 /** 278 * @param {!WebInspector.ProfileDataGridNode} profileDataGridNode 279 */ 280 exclude: function(profileDataGridNode) 281 { 282 if (!profileDataGridNode) 283 return; 284 285 this.save(); 286 287 var excludedCallUID = profileDataGridNode.callUID; 288 var excludedTopLevelChild = this.childrenByCallUID[excludedCallUID]; 289 290 // If we have a top level node that is excluded, get rid of it completely (not keeping children), 291 // since bottom up data relies entirely on the root node. 292 if (excludedTopLevelChild) 293 this.children.remove(excludedTopLevelChild); 294 295 var children = this.children; 296 var count = children.length; 297 298 for (var index = 0; index < count; ++index) 299 children[index]._exclude(excludedCallUID); 300 301 if (this.lastComparator) 302 this.sort(this.lastComparator, true); 303 }, 304 305 buildData: function() 306 { 307 }, 308 309 /** 310 * @override 311 */ 312 populateChildren: function() 313 { 314 WebInspector.BottomUpProfileDataGridNode._sharedPopulate(this); 315 }, 316 317 __proto__: WebInspector.ProfileDataGridTree.prototype 318 } 319