debian/libwebkit-engine/usr/share/ewebkit-0/webinspector/BottomUpProfileDataGridTree.js

   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 WebInspector.BottomUpProfileDataGridNode = function(/*ProfileView*/ profileView, /*ProfileNode*/ profileNode, /*BottomUpProfileDataGridTree*/ owningTree)
  33 {
  34     WebInspector.ProfileDataGridNode.call(this, profileView, profileNode, owningTree, this._willHaveChildren(profileNode));
  35
  36     this._remainingNodeInfos = [];
  37 }
  38
  39 WebInspector.BottomUpProfileDataGridNode.prototype = {
  40     _takePropertiesFromProfileDataGridNode: function(/*ProfileDataGridNode*/ profileDataGridNode)
  41     {
  42         this._save();
  43
  44         this.selfTime = profileDataGridNode.selfTime;
  45         this.totalTime = profileDataGridNode.totalTime;
  46         this.numberOfCalls = profileDataGridNode.numberOfCalls;
  47     },
  48
  49     // When focusing, we keep just the members of the callstack.
  50     _keepOnlyChild: function(/*ProfileDataGridNode*/ child)
  51     {
  52         this._save();
  53
  54         this.removeChildren();
  55         this.appendChild(child);
  56     },
  57
  58     _exclude: function(aCallUID)
  59     {
  60         if (this._remainingNodeInfos)
  61             this._populate();
  62
  63         this._save();
  64
  65         var children = this.children;
  66         var index = this.children.length;
  67
  68         while (index--)
  69             children[index]._exclude(aCallUID);
  70
  71         var child = this.childrenByCallUID[aCallUID];
  72
  73         if (child)
  74             this._merge(child, true);
  75     },
  76
  77     _restore: function()
  78     {
  79         WebInspector.ProfileDataGridNode.prototype._restore();
  80
  81         if (!this.children.length)
  82             this.hasChildren = this._willHaveChildren();
  83     },
  84
  85     _merge: function(/*ProfileDataGridNode*/ child, /*Boolean*/ shouldAbsorb)
  86     {
  87         this.selfTime -= child.selfTime;
  88
  89         WebInspector.ProfileDataGridNode.prototype._merge.call(this, child, shouldAbsorb);
  90     },
  91
  92     _sharedPopulate: function()
  93     {
  94         var remainingNodeInfos = this._remainingNodeInfos;
  95         var count = remainingNodeInfos.length;
  96
  97         for (var index = 0; index < count; ++index) {
  98             var nodeInfo = remainingNodeInfos[index];
  99             var ancestor = nodeInfo.ancestor;
 100             var focusNode = nodeInfo.focusNode;
 101             var child = this.findChild(ancestor);
 102
 103             // If we already have this child, then merge the data together.
 104             if (child) {
 105                 var totalTimeAccountedFor = nodeInfo.totalTimeAccountedFor;
 106
 107                 child.selfTime += focusNode.selfTime;
 108                 child.numberOfCalls += focusNode.numberOfCalls;
 109
 110                 if (!totalTimeAccountedFor)
 111                     child.totalTime += focusNode.totalTime;
 112             } else {
 113                 // If not, add it as a true ancestor.
 114                 // In heavy mode, we take our visual identity from ancestor node...
 115                 var child = new WebInspector.BottomUpProfileDataGridNode(this.profileView, ancestor, this.tree);
 116
 117                 if (ancestor !== focusNode) {
 118                     // but the actual statistics from the "root" node (bottom of the callstack).
 119                     child.selfTime = focusNode.selfTime;
 120                     child.totalTime = focusNode.totalTime;
 121                     child.numberOfCalls = focusNode.numberOfCalls;
 122                 }
 123
 124                 this.appendChild(child);
 125             }
 126
 127             var parent = ancestor.parent;
 128             if (parent && parent.parent) {
 129                 nodeInfo.ancestor = parent;
 130                 child._remainingNodeInfos.push(nodeInfo);
 131             }
 132         }
 133
 134         delete this._remainingNodeInfos;
 135     },
 136
 137     _willHaveChildren: function(profileNode)
 138     {
 139         profileNode = profileNode || this.profileNode;
 140         // In bottom up mode, our parents are our children since we display an inverted tree.
 141         // However, we don't want to show the very top parent since it is redundant.
 142         return !!(profileNode.parent && profileNode.parent.parent);
 143     }
 144 }
 145
 146 WebInspector.BottomUpProfileDataGridNode.prototype.__proto__ = WebInspector.ProfileDataGridNode.prototype;
 147
 148 WebInspector.BottomUpProfileDataGridTree = function(/*ProfileView*/ aProfileView, /*ProfileNode*/ aProfileNode)
 149 {
 150     WebInspector.ProfileDataGridTree.call(this, aProfileView, aProfileNode);
 151
 152     // Iterate each node in pre-order.
 153     var profileNodeUIDs = 0;
 154     var profileNodeGroups = [[], [aProfileNode]];
 155     var visitedProfileNodesForCallUID = {};
 156
 157     this._remainingNodeInfos = [];
 158
 159     for (var profileNodeGroupIndex = 0; profileNodeGroupIndex < profileNodeGroups.length; ++profileNodeGroupIndex) {
 160         var parentProfileNodes = profileNodeGroups[profileNodeGroupIndex];
 161         var profileNodes = profileNodeGroups[++profileNodeGroupIndex];
 162         var count = profileNodes.length;
 163
 164         for (var index = 0; index < count; ++index) {
 165             var profileNode = profileNodes[index];
 166
 167             if (!profileNode.UID)
 168                 profileNode.UID = ++profileNodeUIDs;
 169
 170             if (profileNode.head && profileNode !== profileNode.head) {
 171                 // The total time of this ancestor is accounted for if we're in any form of recursive cycle.
 172                 var visitedNodes = visitedProfileNodesForCallUID[profileNode.callUID];
 173                 var totalTimeAccountedFor = false;
 174
 175                 if (!visitedNodes) {
 176                     visitedNodes = {}
 177                     visitedProfileNodesForCallUID[profileNode.callUID] = visitedNodes;
 178                 } else {
 179                     // The total time for this node has already been accounted for iff one of it's parents has already been visited.
 180                     // We can do this check in this style because we are traversing the tree in pre-order.
 181                     var parentCount = parentProfileNodes.length;
 182                     for (var parentIndex = 0; parentIndex < parentCount; ++parentIndex) {
 183                         if (visitedNodes[parentProfileNodes[parentIndex].UID]) {
 184                             totalTimeAccountedFor = true;
 185                             break;
 186                         }
 187                     }
 188                 }
 189
 190                 visitedNodes[profileNode.UID] = true;
 191
 192                 this._remainingNodeInfos.push({ ancestor:profileNode, focusNode:profileNode, totalTimeAccountedFor:totalTimeAccountedFor });
 193             }
 194
 195             var children = profileNode.children;
 196             if (children.length) {
 197                 profileNodeGroups.push(parentProfileNodes.concat([profileNode]))
 198                 profileNodeGroups.push(children);
 199             }
 200         }
 201     }
 202
 203     // Populate the top level nodes.
 204     WebInspector.BottomUpProfileDataGridNode.prototype._populate.call(this);
 205
 206     return this;
 207 }
 208
 209 WebInspector.BottomUpProfileDataGridTree.prototype = {
 210     // When focusing, we keep the entire callstack up to this ancestor.
 211     focus: function(/*ProfileDataGridNode*/ profileDataGridNode)
 212     {
 213         if (!profileDataGridNode)
 214             return;
 215
 216         this._save();
 217
 218         var currentNode = profileDataGridNode;
 219         var focusNode = profileDataGridNode;
 220
 221         while (currentNode.parent && (currentNode instanceof WebInspector.ProfileDataGridNode)) {
 222             currentNode._takePropertiesFromProfileDataGridNode(profileDataGridNode);
 223
 224             focusNode = currentNode;
 225             currentNode = currentNode.parent;
 226
 227             if (currentNode instanceof WebInspector.ProfileDataGridNode)
 228                 currentNode._keepOnlyChild(focusNode);
 229         }
 230
 231         this.children = [focusNode];
 232         this.totalTime = profileDataGridNode.totalTime;
 233     },
 234
 235     exclude: function(/*ProfileDataGridNode*/ profileDataGridNode)
 236     {
 237         if (!profileDataGridNode)
 238             return;
 239
 240         this._save();
 241
 242         var excludedCallUID = profileDataGridNode.callUID;
 243         var excludedTopLevelChild = this.childrenByCallUID[excludedCallUID];
 244
 245         // If we have a top level node that is excluded, get rid of it completely (not keeping children),
 246         // since bottom up data relies entirely on the root node.
 247         if (excludedTopLevelChild)
 248             this.children.remove(excludedTopLevelChild);
 249
 250         var children = this.children;
 251         var count = children.length;
 252
 253         for (var index = 0; index < count; ++index)
 254             children[index]._exclude(excludedCallUID);
 255
 256         if (this.lastComparator)
 257             this.sort(this.lastComparator, true);
 258     },
 259
 260     _sharedPopulate: WebInspector.BottomUpProfileDataGridNode.prototype._sharedPopulate
 261 }
 262
 263 WebInspector.BottomUpProfileDataGridTree.prototype.__proto__ = WebInspector.ProfileDataGridTree.prototype;
 264