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