src/third_party/WebKit/Source/devtools/front_end/CPUProfileView.js

   1 /*
   2  * Copyright (C) 2008 Apple 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 /**
  27  * @constructor
  28  * @extends {WebInspector.View}
  29  * @param {!WebInspector.CPUProfileHeader} profileHeader
  30  */
  31 WebInspector.CPUProfileView = function(profileHeader)
  32 {
  33     WebInspector.View.call(this);
  34
  35     this.element.classList.add("profile-view");
  36
  37     this.showSelfTimeAsPercent = WebInspector.settings.createSetting("cpuProfilerShowSelfTimeAsPercent", true);
  38     this.showTotalTimeAsPercent = WebInspector.settings.createSetting("cpuProfilerShowTotalTimeAsPercent", true);
  39     this.showAverageTimeAsPercent = WebInspector.settings.createSetting("cpuProfilerShowAverageTimeAsPercent", true);
  40     this._viewType = WebInspector.settings.createSetting("cpuProfilerView", WebInspector.CPUProfileView._TypeHeavy);
  41
  42     var columns = [];
  43     columns.push({id: "self", title: WebInspector.UIString("Self"), width: "72px", sort: WebInspector.DataGrid.Order.Descending, sortable: true});
  44     columns.push({id: "total", title: WebInspector.UIString("Total"), width: "72px", sortable: true});
  45     columns.push({id: "function", title: WebInspector.UIString("Function"), disclosure: true, sortable: true});
  46
  47     this.dataGrid = new WebInspector.DataGrid(columns);
  48     this.dataGrid.addEventListener(WebInspector.DataGrid.Events.SortingChanged, this._sortProfile, this);
  49     this.dataGrid.element.addEventListener("mousedown", this._mouseDownInDataGrid.bind(this), true);
  50     this.dataGrid.show(this.element);
  51
  52     this.viewSelectComboBox = new WebInspector.StatusBarComboBox(this._changeView.bind(this));
  53
  54     var options = {};
  55     options[WebInspector.CPUProfileView._TypeFlame] = this.viewSelectComboBox.createOption(WebInspector.UIString("Flame Chart"), "", WebInspector.CPUProfileView._TypeFlame);
  56     options[WebInspector.CPUProfileView._TypeHeavy] = this.viewSelectComboBox.createOption(WebInspector.UIString("Heavy (Bottom Up)"), "", WebInspector.CPUProfileView._TypeHeavy);
  57     options[WebInspector.CPUProfileView._TypeTree] = this.viewSelectComboBox.createOption(WebInspector.UIString("Tree (Top Down)"), "", WebInspector.CPUProfileView._TypeTree);
  58
  59     var optionName = this._viewType.get() || WebInspector.CPUProfileView._TypeFlame;
  60     var option = options[optionName] || options[WebInspector.CPUProfileView._TypeFlame];
  61     this.viewSelectComboBox.select(option);
  62
  63     this._statusBarButtonsElement = document.createElement("span");
  64
  65     this.percentButton = new WebInspector.StatusBarButton("", "percent-time-status-bar-item");
  66     this.percentButton.addEventListener("click", this._percentClicked, this);
  67     this._statusBarButtonsElement.appendChild(this.percentButton.element);
  68
  69     this.focusButton = new WebInspector.StatusBarButton(WebInspector.UIString("Focus selected function."), "focus-profile-node-status-bar-item");
  70     this.focusButton.setEnabled(false);
  71     this.focusButton.addEventListener("click", this._focusClicked, this);
  72     this._statusBarButtonsElement.appendChild(this.focusButton.element);
  73
  74     this.excludeButton = new WebInspector.StatusBarButton(WebInspector.UIString("Exclude selected function."), "exclude-profile-node-status-bar-item");
  75     this.excludeButton.setEnabled(false);
  76     this.excludeButton.addEventListener("click", this._excludeClicked, this);
  77     this._statusBarButtonsElement.appendChild(this.excludeButton.element);
  78
  79     this.resetButton = new WebInspector.StatusBarButton(WebInspector.UIString("Restore all functions."), "reset-profile-status-bar-item");
  80     this.resetButton.visible = false;
  81     this.resetButton.addEventListener("click", this._resetClicked, this);
  82     this._statusBarButtonsElement.appendChild(this.resetButton.element);
  83
  84     this.profileHead = /** @type {?ProfilerAgent.CPUProfileNode} */ (null);
  85     this.profile = profileHeader;
  86
  87     this._linkifier = new WebInspector.Linkifier(new WebInspector.Linkifier.DefaultFormatter(30));
  88
  89     if (this.profile._profile) // If the profile has been loaded from file then use it.
  90         this._processProfileData(this.profile._profile);
  91     else
  92         this._processProfileData(this.profile.protocolProfile());
  93 }
  94
  95 WebInspector.CPUProfileView._TypeFlame = "Flame";
  96 WebInspector.CPUProfileView._TypeTree = "Tree";
  97 WebInspector.CPUProfileView._TypeHeavy = "Heavy";
  98
  99 WebInspector.CPUProfileView.prototype = {
 100     /**
 101      * @param {!number} timeLeft
 102      * @param {!number} timeRight
 103      */
 104     selectRange: function(timeLeft, timeRight)
 105     {
 106         if (!this._flameChart)
 107             return;
 108         this._flameChart.selectRange(timeLeft, timeRight);
 109     },
 110
 111     _revealProfilerNode: function(event)
 112     {
 113         var current = this.profileDataGridTree.children[0];
 114
 115         while (current && current.profileNode !== event.data)
 116             current = current.traverseNextNode(false, null, false);
 117
 118         if (current)
 119             current.revealAndSelect();
 120     },
 121
 122     /**
 123      * @param {?ProfilerAgent.CPUProfile} profile
 124      */
 125     _processProfileData: function(profile)
 126     {
 127         this.profileHead = profile.head;
 128         this.samples = profile.samples;
 129
 130         this._calculateTimes(profile);
 131
 132         this._assignParentsInProfile();
 133         if (this.samples)
 134             this._buildIdToNodeMap();
 135         this._changeView();
 136         this._updatePercentButton();
 137         if (this._flameChart)
 138             this._flameChart.update();
 139     },
 140
 141     get statusBarItems()
 142     {
 143         return [this.viewSelectComboBox.element, this._statusBarButtonsElement];
 144     },
 145
 146     /**
 147      * @return {!WebInspector.ProfileDataGridTree}
 148      */
 149     _getBottomUpProfileDataGridTree: function()
 150     {
 151         if (!this._bottomUpProfileDataGridTree)
 152             this._bottomUpProfileDataGridTree = new WebInspector.BottomUpProfileDataGridTree(this, /** @type {!ProfilerAgent.CPUProfileNode} */ (this.profileHead));
 153         return this._bottomUpProfileDataGridTree;
 154     },
 155
 156     /**
 157      * @return {!WebInspector.ProfileDataGridTree}
 158      */
 159     _getTopDownProfileDataGridTree: function()
 160     {
 161         if (!this._topDownProfileDataGridTree)
 162             this._topDownProfileDataGridTree = new WebInspector.TopDownProfileDataGridTree(this, /** @type {!ProfilerAgent.CPUProfileNode} */ (this.profileHead));
 163         return this._topDownProfileDataGridTree;
 164     },
 165
 166     willHide: function()
 167     {
 168         this._currentSearchResultIndex = -1;
 169     },
 170
 171     refresh: function()
 172     {
 173         var selectedProfileNode = this.dataGrid.selectedNode ? this.dataGrid.selectedNode.profileNode : null;
 174
 175         this.dataGrid.rootNode().removeChildren();
 176
 177         var children = this.profileDataGridTree.children;
 178         var count = children.length;
 179
 180         for (var index = 0; index < count; ++index)
 181             this.dataGrid.rootNode().appendChild(children[index]);
 182
 183         if (selectedProfileNode)
 184             selectedProfileNode.selected = true;
 185     },
 186
 187     refreshVisibleData: function()
 188     {
 189         var child = this.dataGrid.rootNode().children[0];
 190         while (child) {
 191             child.refresh();
 192             child = child.traverseNextNode(false, null, true);
 193         }
 194     },
 195
 196     refreshShowAsPercents: function()
 197     {
 198         this._updatePercentButton();
 199         this.refreshVisibleData();
 200     },
 201
 202     searchCanceled: function()
 203     {
 204         if (this._searchResults) {
 205             for (var i = 0; i < this._searchResults.length; ++i) {
 206                 var profileNode = this._searchResults[i].profileNode;
 207
 208                 delete profileNode._searchMatchedSelfColumn;
 209                 delete profileNode._searchMatchedTotalColumn;
 210                 delete profileNode._searchMatchedFunctionColumn;
 211
 212                 profileNode.refresh();
 213             }
 214         }
 215
 216         delete this._searchFinishedCallback;
 217         this._currentSearchResultIndex = -1;
 218         this._searchResults = [];
 219     },
 220
 221     performSearch: function(query, finishedCallback)
 222     {
 223         // Call searchCanceled since it will reset everything we need before doing a new search.
 224         this.searchCanceled();
 225
 226         query = query.trim();
 227
 228         if (!query.length)
 229             return;
 230
 231         this._searchFinishedCallback = finishedCallback;
 232
 233         var greaterThan = (query.startsWith(">"));
 234         var lessThan = (query.startsWith("<"));
 235         var equalTo = (query.startsWith("=") || ((greaterThan || lessThan) && query.indexOf("=") === 1));
 236         var percentUnits = (query.lastIndexOf("%") === (query.length - 1));
 237         var millisecondsUnits = (query.length > 2 && query.lastIndexOf("ms") === (query.length - 2));
 238         var secondsUnits = (!millisecondsUnits && query.lastIndexOf("s") === (query.length - 1));
 239
 240         var queryNumber = parseFloat(query);
 241         if (greaterThan || lessThan || equalTo) {
 242             if (equalTo && (greaterThan || lessThan))
 243                 queryNumber = parseFloat(query.substring(2));
 244             else
 245                 queryNumber = parseFloat(query.substring(1));
 246         }
 247
 248         var queryNumberMilliseconds = (secondsUnits ? (queryNumber * 1000) : queryNumber);
 249
 250         // Make equalTo implicitly true if it wasn't specified there is no other operator.
 251         if (!isNaN(queryNumber) && !(greaterThan || lessThan))
 252             equalTo = true;
 253
 254         var matcher = createPlainTextSearchRegex(query, "i");
 255
 256         function matchesQuery(/*ProfileDataGridNode*/ profileDataGridNode)
 257         {
 258             delete profileDataGridNode._searchMatchedSelfColumn;
 259             delete profileDataGridNode._searchMatchedTotalColumn;
 260             delete profileDataGridNode._searchMatchedFunctionColumn;
 261
 262             if (percentUnits) {
 263                 if (lessThan) {
 264                     if (profileDataGridNode.selfPercent < queryNumber)
 265                         profileDataGridNode._searchMatchedSelfColumn = true;
 266                     if (profileDataGridNode.totalPercent < queryNumber)
 267                         profileDataGridNode._searchMatchedTotalColumn = true;
 268                 } else if (greaterThan) {
 269                     if (profileDataGridNode.selfPercent > queryNumber)
 270                         profileDataGridNode._searchMatchedSelfColumn = true;
 271                     if (profileDataGridNode.totalPercent > queryNumber)
 272                         profileDataGridNode._searchMatchedTotalColumn = true;
 273                 }
 274
 275                 if (equalTo) {
 276                     if (profileDataGridNode.selfPercent == queryNumber)
 277                         profileDataGridNode._searchMatchedSelfColumn = true;
 278                     if (profileDataGridNode.totalPercent == queryNumber)
 279                         profileDataGridNode._searchMatchedTotalColumn = true;
 280                 }
 281             } else if (millisecondsUnits || secondsUnits) {
 282                 if (lessThan) {
 283                     if (profileDataGridNode.selfTime < queryNumberMilliseconds)
 284                         profileDataGridNode._searchMatchedSelfColumn = true;
 285                     if (profileDataGridNode.totalTime < queryNumberMilliseconds)
 286                         profileDataGridNode._searchMatchedTotalColumn = true;
 287                 } else if (greaterThan) {
 288                     if (profileDataGridNode.selfTime > queryNumberMilliseconds)
 289                         profileDataGridNode._searchMatchedSelfColumn = true;
 290                     if (profileDataGridNode.totalTime > queryNumberMilliseconds)
 291                         profileDataGridNode._searchMatchedTotalColumn = true;
 292                 }
 293
 294                 if (equalTo) {
 295                     if (profileDataGridNode.selfTime == queryNumberMilliseconds)
 296                         profileDataGridNode._searchMatchedSelfColumn = true;
 297                     if (profileDataGridNode.totalTime == queryNumberMilliseconds)
 298                         profileDataGridNode._searchMatchedTotalColumn = true;
 299                 }
 300             }
 301
 302             if (profileDataGridNode.functionName.match(matcher) || (profileDataGridNode.url && profileDataGridNode.url.match(matcher)))
 303                 profileDataGridNode._searchMatchedFunctionColumn = true;
 304
 305             if (profileDataGridNode._searchMatchedSelfColumn ||
 306                 profileDataGridNode._searchMatchedTotalColumn ||
 307                 profileDataGridNode._searchMatchedFunctionColumn)
 308             {
 309                 profileDataGridNode.refresh();
 310                 return true;
 311             }
 312
 313             return false;
 314         }
 315
 316         var current = this.profileDataGridTree.children[0];
 317
 318         while (current) {
 319             if (matchesQuery(current)) {
 320                 this._searchResults.push({ profileNode: current });
 321             }
 322
 323             current = current.traverseNextNode(false, null, false);
 324         }
 325
 326         finishedCallback(this, this._searchResults.length);
 327     },
 328
 329     jumpToFirstSearchResult: function()
 330     {
 331         if (!this._searchResults || !this._searchResults.length)
 332             return;
 333         this._currentSearchResultIndex = 0;
 334         this._jumpToSearchResult(this._currentSearchResultIndex);
 335     },
 336
 337     jumpToLastSearchResult: function()
 338     {
 339         if (!this._searchResults || !this._searchResults.length)
 340             return;
 341         this._currentSearchResultIndex = (this._searchResults.length - 1);
 342         this._jumpToSearchResult(this._currentSearchResultIndex);
 343     },
 344
 345     jumpToNextSearchResult: function()
 346     {
 347         if (!this._searchResults || !this._searchResults.length)
 348             return;
 349         if (++this._currentSearchResultIndex >= this._searchResults.length)
 350             this._currentSearchResultIndex = 0;
 351         this._jumpToSearchResult(this._currentSearchResultIndex);
 352     },
 353
 354     jumpToPreviousSearchResult: function()
 355     {
 356         if (!this._searchResults || !this._searchResults.length)
 357             return;
 358         if (--this._currentSearchResultIndex < 0)
 359             this._currentSearchResultIndex = (this._searchResults.length - 1);
 360         this._jumpToSearchResult(this._currentSearchResultIndex);
 361     },
 362
 363     /**
 364      * @return {boolean}
 365      */
 366     showingFirstSearchResult: function()
 367     {
 368         return (this._currentSearchResultIndex === 0);
 369     },
 370
 371     /**
 372      * @return {boolean}
 373      */
 374     showingLastSearchResult: function()
 375     {
 376         return (this._searchResults && this._currentSearchResultIndex === (this._searchResults.length - 1));
 377     },
 378
 379     /**
 380      * @return {number}
 381      */
 382     currentSearchResultIndex: function() {
 383         return this._currentSearchResultIndex;
 384     },
 385
 386     _jumpToSearchResult: function(index)
 387     {
 388         var searchResult = this._searchResults[index];
 389         if (!searchResult)
 390             return;
 391
 392         var profileNode = searchResult.profileNode;
 393         profileNode.revealAndSelect();
 394     },
 395
 396     _ensureFlameChartCreated: function()
 397     {
 398         if (this._flameChart)
 399             return;
 400         var dataProvider = new WebInspector.CPUFlameChartDataProvider(this);
 401         this._flameChart = new WebInspector.FlameChart(dataProvider);
 402         this._flameChart.addEventListener(WebInspector.FlameChart.Events.EntrySelected, this._onEntrySelected.bind(this));
 403     },
 404
 405     /**
 406      * @param {!WebInspector.Event} event
 407      */
 408     _onEntrySelected: function(event)
 409     {
 410         var node = event.data;
 411         if (!node || !node.scriptId)
 412             return;
 413         var script = WebInspector.debuggerModel.scriptForId(node.scriptId)
 414         if (!script)
 415             return;
 416         var uiLocation = script.rawLocationToUILocation(node.lineNumber);
 417         if (uiLocation)
 418             uiLocation.reveal();
 419     },
 420
 421     _changeView: function()
 422     {
 423         if (!this.profile)
 424             return;
 425
 426         switch (this.viewSelectComboBox.selectedOption().value) {
 427         case WebInspector.CPUProfileView._TypeFlame:
 428             this._ensureFlameChartCreated();
 429             this.dataGrid.detach();
 430             this._flameChart.show(this.element);
 431             this._viewType.set(WebInspector.CPUProfileView._TypeFlame);
 432             this._statusBarButtonsElement.enableStyleClass("hidden", true);
 433             return;
 434         case WebInspector.CPUProfileView._TypeTree:
 435             this.profileDataGridTree = this._getTopDownProfileDataGridTree();
 436             this._sortProfile();
 437             this._viewType.set(WebInspector.CPUProfileView._TypeTree);
 438             break;
 439         case WebInspector.CPUProfileView._TypeHeavy:
 440             this.profileDataGridTree = this._getBottomUpProfileDataGridTree();
 441             this._sortProfile();
 442             this._viewType.set(WebInspector.CPUProfileView._TypeHeavy);
 443             break;
 444         }
 445
 446         this._statusBarButtonsElement.enableStyleClass("hidden", false);
 447
 448         if (this._flameChart)
 449             this._flameChart.detach();
 450         this.dataGrid.show(this.element);
 451
 452         if (!this.currentQuery || !this._searchFinishedCallback || !this._searchResults)
 453             return;
 454
 455         // The current search needs to be performed again. First negate out previous match
 456         // count by calling the search finished callback with a negative number of matches.
 457         // Then perform the search again the with same query and callback.
 458         this._searchFinishedCallback(this, -this._searchResults.length);
 459         this.performSearch(this.currentQuery, this._searchFinishedCallback);
 460     },
 461
 462     _percentClicked: function(event)
 463     {
 464         var currentState = this.showSelfTimeAsPercent.get() && this.showTotalTimeAsPercent.get() && this.showAverageTimeAsPercent.get();
 465         this.showSelfTimeAsPercent.set(!currentState);
 466         this.showTotalTimeAsPercent.set(!currentState);
 467         this.showAverageTimeAsPercent.set(!currentState);
 468         this.refreshShowAsPercents();
 469     },
 470
 471     _updatePercentButton: function()
 472     {
 473         if (this.showSelfTimeAsPercent.get() && this.showTotalTimeAsPercent.get() && this.showAverageTimeAsPercent.get()) {
 474             this.percentButton.title = WebInspector.UIString("Show absolute total and self times.");
 475             this.percentButton.toggled = true;
 476         } else {
 477             this.percentButton.title = WebInspector.UIString("Show total and self times as percentages.");
 478             this.percentButton.toggled = false;
 479         }
 480     },
 481
 482     _focusClicked: function(event)
 483     {
 484         if (!this.dataGrid.selectedNode)
 485             return;
 486
 487         this.resetButton.visible = true;
 488         this.profileDataGridTree.focus(this.dataGrid.selectedNode);
 489         this.refresh();
 490         this.refreshVisibleData();
 491     },
 492
 493     _excludeClicked: function(event)
 494     {
 495         var selectedNode = this.dataGrid.selectedNode
 496
 497         if (!selectedNode)
 498             return;
 499
 500         selectedNode.deselect();
 501
 502         this.resetButton.visible = true;
 503         this.profileDataGridTree.exclude(selectedNode);
 504         this.refresh();
 505         this.refreshVisibleData();
 506     },
 507
 508     _resetClicked: function(event)
 509     {
 510         this.resetButton.visible = false;
 511         this.profileDataGridTree.restore();
 512         this._linkifier.reset();
 513         this.refresh();
 514         this.refreshVisibleData();
 515     },
 516
 517     _dataGridNodeSelected: function(node)
 518     {
 519         this.focusButton.setEnabled(true);
 520         this.excludeButton.setEnabled(true);
 521     },
 522
 523     _dataGridNodeDeselected: function(node)
 524     {
 525         this.focusButton.setEnabled(false);
 526         this.excludeButton.setEnabled(false);
 527     },
 528
 529     _sortProfile: function()
 530     {
 531         var sortAscending = this.dataGrid.isSortOrderAscending();
 532         var sortColumnIdentifier = this.dataGrid.sortColumnIdentifier();
 533         var sortProperty = {
 534                 "self": "selfTime",
 535                 "total": "totalTime",
 536                 "function": "functionName"
 537             }[sortColumnIdentifier];
 538
 539         this.profileDataGridTree.sort(WebInspector.ProfileDataGridTree.propertyComparator(sortProperty, sortAscending));
 540
 541         this.refresh();
 542     },
 543
 544     _mouseDownInDataGrid: function(event)
 545     {
 546         if (event.detail < 2)
 547             return;
 548
 549         var cell = event.target.enclosingNodeOrSelfWithNodeName("td");
 550         if (!cell || (!cell.classList.contains("total-column") && !cell.classList.contains("self-column") && !cell.classList.contains("average-column")))
 551             return;
 552
 553         if (cell.classList.contains("total-column"))
 554             this.showTotalTimeAsPercent.set(!this.showTotalTimeAsPercent.get());
 555         else if (cell.classList.contains("self-column"))
 556             this.showSelfTimeAsPercent.set(!this.showSelfTimeAsPercent.get());
 557         else if (cell.classList.contains("average-column"))
 558             this.showAverageTimeAsPercent.set(!this.showAverageTimeAsPercent.get());
 559
 560         this.refreshShowAsPercents();
 561
 562         event.consume(true);
 563     },
 564
 565     _calculateTimes: function(profile)
 566     {
 567         function totalHitCount(node) {
 568             var result = node.hitCount;
 569             for (var i = 0; i < node.children.length; i++)
 570                 result += totalHitCount(node.children[i]);
 571             return result;
 572         }
 573         profile.totalHitCount = totalHitCount(profile.head);
 574
 575         var durationMs = 1000 * (profile.endTime - profile.startTime);
 576         var samplingInterval = durationMs / profile.totalHitCount;
 577         this.samplingIntervalMs = samplingInterval;
 578
 579         function calculateTimesForNode(node) {
 580             node.selfTime = node.hitCount * samplingInterval;
 581             var totalHitCount = node.hitCount;
 582             for (var i = 0; i < node.children.length; i++)
 583                 totalHitCount += calculateTimesForNode(node.children[i]);
 584             node.totalTime = totalHitCount * samplingInterval;
 585             return totalHitCount;
 586         }
 587         calculateTimesForNode(profile.head);
 588     },
 589
 590     _assignParentsInProfile: function()
 591     {
 592         var head = this.profileHead;
 593         head.parent = null;
 594         head.head = null;
 595         var nodesToTraverse = [ head ];
 596         while (nodesToTraverse.length) {
 597             var parent = nodesToTraverse.pop();
 598             var children = parent.children;
 599             var length = children.length;
 600             for (var i = 0; i < length; ++i) {
 601                 var child = children[i];
 602                 child.head = head;
 603                 child.parent = parent;
 604                 if (child.children.length)
 605                     nodesToTraverse.push(child);
 606             }
 607         }
 608     },
 609
 610     _buildIdToNodeMap: function()
 611     {
 612         var idToNode = this._idToNode = {};
 613         var stack = [this.profileHead];
 614         while (stack.length) {
 615             var node = stack.pop();
 616             idToNode[node.id] = node;
 617             for (var i = 0; i < node.children.length; i++)
 618                 stack.push(node.children[i]);
 619         }
 620
 621         var topLevelNodes = this.profileHead.children;
 622         for (var i = 0; i < topLevelNodes.length; i++) {
 623             var node = topLevelNodes[i];
 624             if (node.functionName === "(garbage collector)") {
 625                 this._gcNode = node;
 626                 break;
 627             }
 628         }
 629     },
 630
 631     __proto__: WebInspector.View.prototype
 632 }
 633
 634 /**
 635  * @constructor
 636  * @extends {WebInspector.ProfileType}
 637  * @implements {WebInspector.CPUProfilerModel.Delegate}
 638  */
 639 WebInspector.CPUProfileType = function()
 640 {
 641     WebInspector.ProfileType.call(this, WebInspector.CPUProfileType.TypeId, WebInspector.UIString("Collect JavaScript CPU Profile"));
 642     this._recording = false;
 643     this._nextProfileId = 1;
 644
 645     this._nextAnonymousConsoleProfileNumber = 1;
 646     this._anonymousConsoleProfileIdToTitle = {};
 647
 648     WebInspector.CPUProfileType.instance = this;
 649     WebInspector.cpuProfilerModel.setDelegate(this);
 650 }
 651
 652 WebInspector.CPUProfileType.TypeId = "CPU";
 653
 654 WebInspector.CPUProfileType.prototype = {
 655     /**
 656      * @override
 657      * @return {string}
 658      */
 659     fileExtension: function()
 660     {
 661         return ".cpuprofile";
 662     },
 663
 664     get buttonTooltip()
 665     {
 666         return this._recording ? WebInspector.UIString("Stop CPU profiling.") : WebInspector.UIString("Start CPU profiling.");
 667     },
 668
 669     /**
 670      * @override
 671      * @return {boolean}
 672      */
 673     buttonClicked: function()
 674     {
 675         if (this._recording) {
 676             this.stopRecordingProfile();
 677             return false;
 678         } else {
 679             this.startRecordingProfile();
 680             return true;
 681         }
 682     },
 683
 684     get treeItemTitle()
 685     {
 686         return WebInspector.UIString("CPU PROFILES");
 687     },
 688
 689     get description()
 690     {
 691         return WebInspector.UIString("CPU profiles show where the execution time is spent in your page's JavaScript functions.");
 692     },
 693
 694     /**
 695      * @param {string} id
 696      * @param {!DebuggerAgent.Location} scriptLocation
 697      * @param {string=} title
 698      */
 699     consoleProfileStarted: function(id, scriptLocation, title)
 700     {
 701         var resolvedTitle = title;
 702         if (!resolvedTitle) {
 703             resolvedTitle = WebInspector.UIString("Profile %s", this._nextAnonymousConsoleProfileNumber++);
 704             this._anonymousConsoleProfileIdToTitle[id] = resolvedTitle;
 705         }
 706         var messageElement = document.createTextNode(WebInspector.UIString("Profile '%s' started.", resolvedTitle));
 707         this._addMessageToConsole(WebInspector.ConsoleMessage.MessageType.Profile, scriptLocation, messageElement);
 708     },
 709
 710     /**
 711      * @param {string} protocolId
 712      * @param {!DebuggerAgent.Location} scriptLocation
 713      * @param {!ProfilerAgent.CPUProfile} cpuProfile
 714      * @param {string=} title
 715      */
 716     consoleProfileFinished: function(protocolId, scriptLocation, cpuProfile, title)
 717     {
 718         var resolvedTitle = title;
 719         if (typeof title === "undefined") {
 720             resolvedTitle = this._anonymousConsoleProfileIdToTitle[protocolId];
 721             delete this._anonymousConsoleProfileIdToTitle[protocolId];
 722         }
 723
 724         var id = this._nextProfileId++;
 725         var profile = new WebInspector.CPUProfileHeader(this, resolvedTitle, id);
 726         profile.setProtocolProfile(cpuProfile);
 727         this.addProfile(profile);
 728
 729         var messageElement = document.createElement("span");
 730         messageElement.createTextChild("Profile '");
 731         var a = messageElement.createChild("span", "link");
 732         a.title = resolvedTitle;
 733         a.textContent = resolvedTitle;
 734         a.addEventListener("click", onClick.bind(this), true);
 735         function onClick(event)
 736         {
 737             WebInspector.showPanel("profiles").showProfile(WebInspector.CPUProfileType.TypeId, id);
 738         }
 739         messageElement.createTextChild("' finished.");
 740
 741         this._addMessageToConsole(WebInspector.ConsoleMessage.MessageType.ProfileEnd, scriptLocation, messageElement);
 742     },
 743
 744     /**
 745      * @param {string} type
 746      * @param {!DebuggerAgent.Location} scriptLocation
 747      * @param {!Node} messageElement
 748      */
 749     _addMessageToConsole: function(type, scriptLocation, messageElement)
 750     {
 751         var rawLocation = new WebInspector.DebuggerModel.Location(scriptLocation.scriptId, scriptLocation.lineNumber, scriptLocation.columnNumber || 0);
 752         var uiLocation = WebInspector.debuggerModel.rawLocationToUILocation(rawLocation);
 753         var url;
 754         if (uiLocation)
 755             url = uiLocation.url();
 756         var message = WebInspector.ConsoleMessage.create(
 757             WebInspector.ConsoleMessage.MessageSource.ConsoleAPI,
 758             WebInspector.ConsoleMessage.MessageLevel.Debug,
 759             "",
 760             type,
 761             url || undefined,
 762             scriptLocation.lineNumber,
 763             scriptLocation.columnNumber);
 764
 765         message.setMessageElement(messageElement);
 766         WebInspector.console.addMessage(message);
 767     },
 768
 769     /**
 770      * @return {boolean}
 771      */
 772     isRecordingProfile: function()
 773     {
 774         return this._recording;
 775     },
 776
 777     startRecordingProfile: function()
 778     {
 779         if (this._profileBeingRecorded)
 780             return;
 781         var id = this._nextProfileId++;
 782         this._profileBeingRecorded = new WebInspector.CPUProfileHeader(this, WebInspector.UIString("Recording\u2026"), id);
 783         this.addProfile(this._profileBeingRecorded);
 784
 785         this._recording = true;
 786         WebInspector.cpuProfilerModel.setRecording(true);
 787         WebInspector.userMetrics.ProfilesCPUProfileTaken.record();
 788         ProfilerAgent.start();
 789     },
 790
 791     stopRecordingProfile: function()
 792     {
 793         this._recording = false;
 794         WebInspector.cpuProfilerModel.setRecording(false);
 795
 796         /**
 797          * @param {?string} error
 798          * @param {?ProfilerAgent.CPUProfile} profile
 799          * @this {WebInspector.CPUProfileType}
 800          */
 801         function didStopProfiling(error, profile)
 802         {
 803             if (!this._profileBeingRecorded)
 804                 return;
 805             this._profileBeingRecorded.setProtocolProfile(profile);
 806
 807             var title = WebInspector.UIString("Profile %d", this._profileBeingRecorded.uid);
 808             this._profileBeingRecorded.title = title;
 809             this._profileBeingRecorded.sidebarElement.mainTitle = title;
 810             var recordedProfile = this._profileBeingRecorded;
 811             this._profileBeingRecorded = null;
 812             WebInspector.panels.profiles._showProfile(recordedProfile);
 813         }
 814         ProfilerAgent.stop(didStopProfiling.bind(this));
 815     },
 816
 817     /**
 818      * @override
 819      * @param {string} title
 820      * @return {!WebInspector.ProfileHeader}
 821      */
 822     createProfileLoadedFromFile: function(title)
 823     {
 824         return new WebInspector.CPUProfileHeader(this, title);
 825     },
 826
 827     /**
 828      * @override
 829      */
 830     removeProfile: function(profile)
 831     {
 832         if (this._profileBeingRecorded === profile)
 833             this.stopRecordingProfile();
 834         WebInspector.ProfileType.prototype.removeProfile.call(this, profile);
 835     },
 836
 837     __proto__: WebInspector.ProfileType.prototype
 838 }
 839
 840 /**
 841  * @constructor
 842  * @extends {WebInspector.ProfileHeader}
 843  * @implements {WebInspector.OutputStream}
 844  * @implements {WebInspector.OutputStreamDelegate}
 845  * @param {!WebInspector.CPUProfileType} type
 846  * @param {string} title
 847  * @param {number=} uid
 848  */
 849 WebInspector.CPUProfileHeader = function(type, title, uid)
 850 {
 851     WebInspector.ProfileHeader.call(this, type, title, uid);
 852     this._tempFile = null;
 853 }
 854
 855 WebInspector.CPUProfileHeader.prototype = {
 856     onTransferStarted: function()
 857     {
 858         this._jsonifiedProfile = "";
 859         this.sidebarElement.subtitle = WebInspector.UIString("Loading\u2026 %s", Number.bytesToString(this._jsonifiedProfile.length));
 860     },
 861
 862     /**
 863      * @param {!WebInspector.ChunkedReader} reader
 864      */
 865     onChunkTransferred: function(reader)
 866     {
 867         this.sidebarElement.subtitle = WebInspector.UIString("Loading\u2026 %d\%", Number.bytesToString(this._jsonifiedProfile.length));
 868     },
 869
 870     onTransferFinished: function()
 871     {
 872         this.sidebarElement.subtitle = WebInspector.UIString("Parsing\u2026");
 873         this._profile = JSON.parse(this._jsonifiedProfile);
 874         this._jsonifiedProfile = null;
 875         this.sidebarElement.subtitle = WebInspector.UIString("Loaded");
 876
 877         if (this._profileType._profileBeingRecorded === this)
 878             this._profileType._profileBeingRecorded = null;
 879     },
 880
 881     /**
 882      * @param {!WebInspector.ChunkedReader} reader
 883      */
 884     onError: function(reader, e)
 885     {
 886         switch(e.target.error.code) {
 887         case e.target.error.NOT_FOUND_ERR:
 888             this.sidebarElement.subtitle = WebInspector.UIString("'%s' not found.", reader.fileName());
 889         break;
 890         case e.target.error.NOT_READABLE_ERR:
 891             this.sidebarElement.subtitle = WebInspector.UIString("'%s' is not readable", reader.fileName());
 892         break;
 893         case e.target.error.ABORT_ERR:
 894             break;
 895         default:
 896             this.sidebarElement.subtitle = WebInspector.UIString("'%s' error %d", reader.fileName(), e.target.error.code);
 897         }
 898     },
 899
 900     /**
 901      * @param {string} text
 902      */
 903     write: function(text)
 904     {
 905         this._jsonifiedProfile += text;
 906     },
 907
 908     close: function() { },
 909
 910     /**
 911      * @override
 912      */
 913     dispose: function()
 914     {
 915         this.removeTempFile();
 916     },
 917
 918     /**
 919      * @override
 920      * @return {!WebInspector.ProfileSidebarTreeElement}
 921      */
 922     createSidebarTreeElement: function()
 923     {
 924         return new WebInspector.ProfileSidebarTreeElement(this, "profile-sidebar-tree-item");
 925     },
 926
 927     /**
 928      * @override
 929      * @param {!WebInspector.ProfilesPanel} profilesPanel
 930      * @return {!WebInspector.CPUProfileView}
 931      */
 932     createView: function(profilesPanel)
 933     {
 934         return new WebInspector.CPUProfileView(this);
 935     },
 936
 937     /**
 938      * @override
 939      * @return {boolean}
 940      */
 941     canSaveToFile: function()
 942     {
 943         return !!this._tempFile;
 944     },
 945
 946     saveToFile: function()
 947     {
 948         var fileOutputStream = new WebInspector.FileOutputStream();
 949
 950         /**
 951          * @param {boolean} accepted
 952          * @this {WebInspector.CPUProfileHeader}
 953          */
 954         function onOpenForSave(accepted)
 955         {
 956             if (!accepted)
 957                 return;
 958             function didRead(data)
 959             {
 960                 if (data)
 961                     fileOutputStream.write(data, fileOutputStream.close.bind(fileOutputStream));
 962                 else
 963                     fileOutputStream.close();
 964             }
 965             this._tempFile.read(didRead.bind(this));
 966         }
 967         this._fileName = this._fileName || "CPU-" + new Date().toISO8601Compact() + this._profileType.fileExtension();
 968         fileOutputStream.open(this._fileName, onOpenForSave.bind(this));
 969     },
 970
 971     /**
 972      * @param {!File} file
 973      */
 974     loadFromFile: function(file)
 975     {
 976         this.sidebarElement.subtitle = WebInspector.UIString("Loading\u2026");
 977         this.sidebarElement.wait = true;
 978
 979         var fileReader = new WebInspector.ChunkedFileReader(file, 10000000, this);
 980         fileReader.start(this);
 981     },
 982
 983
 984     /**
 985      * @return {?ProfilerAgent.CPUProfile}
 986      */
 987     protocolProfile: function()
 988     {
 989         return this._protocolProfile;
 990     },
 991
 992     /**
 993      * @param {!ProfilerAgent.CPUProfile} cpuProfile
 994      */
 995     setProtocolProfile: function(cpuProfile)
 996     {
 997         this._protocolProfile = cpuProfile;
 998         this._saveProfileDataToTempFile(cpuProfile);
 999     },
1000
1001     /**
1002      * @param {!ProfilerAgent.CPUProfile} data
1003      */
1004     _saveProfileDataToTempFile: function(data)
1005     {
1006         var serializedData = JSON.stringify(data);
1007
1008         /**
1009          * @this {WebInspector.CPUProfileHeader}
1010          */
1011         function didCreateTempFile(tempFile)
1012         {
1013             this._writeToTempFile(tempFile, serializedData);
1014         }
1015         new WebInspector.TempFile("cpu-profiler", this.uid,  didCreateTempFile.bind(this));
1016     },
1017
1018     /**
1019      * @param {?WebInspector.TempFile} tempFile
1020      * @param {string} serializedData
1021      */
1022     _writeToTempFile: function(tempFile, serializedData)
1023     {
1024         this._tempFile = tempFile;
1025         if (tempFile)
1026             tempFile.write(serializedData, tempFile.finishWriting.bind(tempFile));
1027     },
1028
1029     __proto__: WebInspector.ProfileHeader.prototype
1030 }
1031
1032 /**
1033  * @constructor
1034  * @implements {WebInspector.FlameChartDataProvider}
1035  */
1036 WebInspector.CPUFlameChartDataProvider = function(cpuProfileView)
1037 {
1038     WebInspector.FlameChartDataProvider.call(this);
1039     this._cpuProfileView = cpuProfileView;
1040 }
1041
1042 WebInspector.CPUFlameChartDataProvider.prototype = {
1043     /**
1044      * @param {!WebInspector.FlameChart.ColorGenerator} colorGenerator
1045      * @return {!Object}
1046      */
1047     timelineData: function(colorGenerator)
1048     {
1049         return this._timelineData || this._calculateTimelineData(colorGenerator);
1050     },
1051
1052     /**
1053      * @param {!WebInspector.FlameChart.ColorGenerator} colorGenerator
1054      * @return {?Object}
1055      */
1056     _calculateTimelineData: function(colorGenerator)
1057     {
1058         if (!this._cpuProfileView.profileHead)
1059             return null;
1060
1061         var samples = this._cpuProfileView.samples;
1062         var idToNode = this._cpuProfileView._idToNode;
1063         var gcNode = this._cpuProfileView._gcNode;
1064         var samplesCount = samples.length;
1065         var samplingInterval = this._cpuProfileView.samplingIntervalMs;
1066
1067         var index = 0;
1068
1069         var openIntervals = [];
1070         var stackTrace = [];
1071         var colorEntryIndexes = [];
1072         var maxDepth = 5; // minimum stack depth for the case when we see no activity.
1073         var depth = 0;
1074
1075         /**
1076          * @constructor
1077          * @param {!Object} colorPair
1078          * @param {!number} depth
1079          * @param {!number} duration
1080          * @param {!number} startTime
1081          * @param {!Object} node
1082          */
1083         function ChartEntry(colorPair, depth, duration, startTime, node)
1084         {
1085             this.colorPair = colorPair;
1086             this.depth = depth;
1087             this.duration = duration;
1088             this.startTime = startTime;
1089             this.node = node;
1090             this.selfTime = 0;
1091         }
1092         var entries = /** @type {!Array.<!ChartEntry>} */ ([]);
1093
1094         for (var sampleIndex = 0; sampleIndex < samplesCount; sampleIndex++) {
1095             var node = idToNode[samples[sampleIndex]];
1096             stackTrace.length = 0;
1097             while (node) {
1098                 stackTrace.push(node);
1099                 node = node.parent;
1100             }
1101             stackTrace.pop(); // Remove (root) node
1102
1103             maxDepth = Math.max(maxDepth, depth);
1104             depth = 0;
1105             node = stackTrace.pop();
1106             var intervalIndex;
1107
1108             // GC samples have no stack, so we just put GC node on top of the last recoreded sample.
1109             if (node === gcNode) {
1110                 while (depth < openIntervals.length) {
1111                     intervalIndex = openIntervals[depth].index;
1112                     entries[intervalIndex].duration += samplingInterval;
1113                     ++depth;
1114                 }
1115                 // If previous stack is also GC then just continue.
1116                 if (openIntervals.length > 0 && openIntervals.peekLast().node === node) {
1117                     entries[intervalIndex].selfTime += samplingInterval;
1118                     continue;
1119                 }
1120             }
1121
1122             while (node && depth < openIntervals.length && node === openIntervals[depth].node) {
1123                 intervalIndex = openIntervals[depth].index;
1124                 entries[intervalIndex].duration += samplingInterval;
1125                 node = stackTrace.pop();
1126                 ++depth;
1127             }
1128             if (depth < openIntervals.length)
1129                 openIntervals.length = depth;
1130             if (!node) {
1131                 entries[intervalIndex].selfTime += samplingInterval;
1132                 continue;
1133             }
1134
1135             while (node) {
1136                 var colorPair = colorGenerator._colorPairForID(node.functionName + ":" + node.url + ":" + node.lineNumber);
1137                 var indexesForColor = colorEntryIndexes[colorPair.index];
1138                 if (!indexesForColor)
1139                     indexesForColor = colorEntryIndexes[colorPair.index] = [];
1140
1141                 var entry = new ChartEntry(colorPair, depth, samplingInterval, sampleIndex * samplingInterval, node);
1142                 indexesForColor.push(entries.length);
1143                 entries.push(entry);
1144                 openIntervals.push({node: node, index: index});
1145                 ++index;
1146
1147                 node = stackTrace.pop();
1148                 ++depth;
1149             }
1150             entries[entries.length - 1].selfTime += samplingInterval;
1151         }
1152
1153         var entryNodes = new Array(entries.length);
1154         var entryColorIndexes = new Uint16Array(entries.length);
1155         var entryLevels = new Uint8Array(entries.length);
1156         var entryTotalTimes = new Float32Array(entries.length);
1157         var entrySelfTimes = new Float32Array(entries.length);
1158         var entryOffsets = new Float32Array(entries.length);
1159         var entryTitles = new Array(entries.length);
1160         var entryDeoptFlags = new Uint8Array(entries.length);
1161
1162         for (var i = 0; i < entries.length; ++i) {
1163             var entry = entries[i];
1164             entryNodes[i] = entry.node;
1165             entryColorIndexes[i] = colorPair.index;
1166             entryLevels[i] = entry.depth;
1167             entryTotalTimes[i] = entry.duration;
1168             entrySelfTimes[i] = entry.selfTime;
1169             entryOffsets[i] = entry.startTime;
1170             entryTitles[i] = entry.node.functionName;
1171             var reason = entry.node.deoptReason;
1172             entryDeoptFlags[i] = (reason && reason !== "no reason");
1173         }
1174
1175         this._timelineData = {
1176             maxStackDepth: Math.max(maxDepth, depth),
1177             totalTime: this._cpuProfileView.profileHead.totalTime,
1178             entryNodes: entryNodes,
1179             entryColorIndexes: entryColorIndexes,
1180             entryLevels: entryLevels,
1181             entryTotalTimes: entryTotalTimes,
1182             entrySelfTimes: entrySelfTimes,
1183             entryOffsets: entryOffsets,
1184             colorEntryIndexes: colorEntryIndexes,
1185             entryTitles: entryTitles,
1186             entryDeoptFlags: entryDeoptFlags
1187         };
1188
1189         return this._timelineData;
1190     },
1191
1192     /**
1193      * @param {number} ms
1194      * @return {string}
1195      */
1196     _millisecondsToString: function(ms)
1197     {
1198         if (ms === 0)
1199             return "0";
1200         if (ms < 1000)
1201             return WebInspector.UIString("%.1f\u2009ms", ms);
1202         return Number.secondsToString(ms / 1000, true);
1203     },
1204
1205     /**
1206      * @param {number} entryIndex
1207      * @return {?Array.<!{title: string, text: string}>}
1208      */
1209     prepareHighlightedEntryInfo: function(entryIndex)
1210     {
1211         var timelineData = this._timelineData;
1212         var node = timelineData.entryNodes[entryIndex];
1213         if (!node)
1214             return null;
1215
1216         var entryInfo = [];
1217         function pushEntryInfoRow(title, text)
1218         {
1219             var row = {};
1220             row.title = title;
1221             row.text = text;
1222             entryInfo.push(row);
1223         }
1224
1225         pushEntryInfoRow(WebInspector.UIString("Name"), timelineData.entryTitles[entryIndex]);
1226         var selfTime = this._millisecondsToString(timelineData.entrySelfTimes[entryIndex]);
1227         var totalTime = this._millisecondsToString(timelineData.entryTotalTimes[entryIndex]);
1228         pushEntryInfoRow(WebInspector.UIString("Self time"), selfTime);
1229         pushEntryInfoRow(WebInspector.UIString("Total time"), totalTime);
1230         if (node.url)
1231             pushEntryInfoRow(WebInspector.UIString("URL"), node.url + ":" + node.lineNumber);
1232         pushEntryInfoRow(WebInspector.UIString("Aggregated self time"), Number.secondsToString(node.selfTime / 1000, true));
1233         pushEntryInfoRow(WebInspector.UIString("Aggregated total time"), Number.secondsToString(node.totalTime / 1000, true));
1234         if (node.deoptReason && node.deoptReason !== "no reason")
1235             pushEntryInfoRow(WebInspector.UIString("Not optimized"), node.deoptReason);
1236
1237         return entryInfo;
1238     },
1239
1240     /**
1241      * @param {number} entryIndex
1242      * @return {boolean}
1243      */
1244     canJumpToEntry: function(entryIndex)
1245     {
1246         return this._timelineData.entryNodes[entryIndex].scriptId !== "0";
1247     },
1248
1249     /**
1250      * @param {number} entryIndex
1251      * @return {!Object}
1252      */
1253     entryData: function(entryIndex)
1254     {
1255         return this._timelineData.entryNodes[entryIndex];
1256     }
1257 }
1258