catapult/tracing/tracing/ui/analysis/stack_frame_tree.html - platform/external/chromium-trace - Git at Google

 <!DOCTYPE html>
 <!--
 Copyright 2015 The Chromium Authors. All rights reserved.
 Use of this source code is governed by a BSD-style license that can be
 found in the LICENSE file.
 -->

 <link rel="import" href="/tracing/base/base.html">

 <script>
 'use strict';

 tr.exportTo('tr.ui.analysis', function() {

   /**
    * Z-function: Given a list (or a string) of length n, for each index i from
    * 1 to n - 1, find the length z[i] of the longest substring starting at
    * position i which is also a prefix of the list. This function returns the
    * list of maximum lengths z.
    *
    * Mathematically, for each i from 1 to n - 1, z[i] is the maximum value such
    * that [list[0], ..., list[i - 1]] = [list[i], ..., list[i + z[i] - 1]].
    * z[0] is defined to be zero for convenience.
    *
    * Example:
    *
    *   Input (list): ['A', 'B', 'A', 'C', 'A', 'B', 'A']
    *   Output (z):   [ 0 ,  0 ,  1 ,  0 ,  3 ,  0 ,  1 ]
    *
    * Unlike the brute-force approach (which is O(n^2) in the worst case), the
    * complexity of this implementation is linear in the size of the list, i.e.
    * O(n).
    *
    * Source: http://e-maxx-eng.github.io/string/z-function.html
    */
   function zFunction(list) {
     var n = list.length;
     if (n === 0)
       return [];

     var z = new Array(n);
     z[0] = 0;

     for (var i = 1, left = 0, right = 0; i < n; ++i) {
       var maxLength;
       if (i <= right)
         maxLength = Math.min(right - i + 1, z[i - left]);
       else
         maxLength = 0;

       while (i + maxLength < n && list[maxLength] === list[i + maxLength])
         ++maxLength;

       if (i + maxLength - 1 > right) {
         left = i;
         right = i + maxLength - 1;
       }

       z[i] = maxLength;
     }

     return z;
   }

   /**
    * Node of a stack frame hierarchy representation for tree (top down) and
    * heavy (bottom up) views.
    *
    * To build a top-down view of a set of stack traces, you simply create a
    * root node and than add the stack traces to it:
    *
    *   var topDownRoot = new StackFrameTreeNode('root', undefined);
    *   topDownRoot.addStackTrace(trace1, size1);
    *   topDownRoot.addStackTrace(trace2, size2);
    *   ...
    *   topDownRoot.addStackTrace(traceN, sizeN);
    *
    * The corresponding bottom-up view is constructed indirectly by converting
    * the top-down view:
    *
    *   var bottomUpRoot = topDownRoot.convertToBottomUpView();
    *
    * @{constructor}
    */
   function StackFrameTreeNode(title, opt_frame) {
     this.title = title;
     this.frame = opt_frame;

     this.parent = undefined;
     this.children = [];
     this.childMap = new Map();

     this.total = 0;
     this.self = 0;
   }

   StackFrameTreeNode.prototype = {
     /** Duck type <tr-ui-b-table> rows. */
     get subRows() {
       return this.children;
     },

     /**
      * Returns the list of titles of this node and all its ancestors (including
      * the root). The title of this node is first in the list.
      *
      * Note that this method does not use
      * tr.model.StackFrame.prototype.getUserFriendlyStackTrace because some
      * nodes don't have frames (e.g. the root).
      */
     get stackTraceTitles() {
       var titles = [];
       for (var currentNode = this; currentNode !== undefined;
         currentNode = currentNode.parent) {
         titles.push(currentNode.title);
       }
       return titles;
     },

     getOrCreateChild: function(title, opt_frame) {
       var childNode = this.childMap.get(title);
       if (childNode !== undefined)
         return childNode;

       childNode = new StackFrameTreeNode(title, opt_frame);
       childNode.parent = this;
       this.children.push(childNode);
       this.childMap.set(title, childNode);

       return childNode;
     },

     /**
      * Add a stack trace to the stack frame tree. The first element of the
      * trace is expected to be the leaf stack frame (so that
      * tr.model.StackFrame.prototype.stackTrace could be used as the parameter
      * without any modification).
      *
      * For example, the following code snippet:
      *
      *   var frameA = new StackFrame(undefined, tr.b.GUID.allocate(), 'A');
      *   var frameB = new StackFrame(frameA, tr.b.GUID.allocate(), 'B');
      *   var frameC = new StackFrame(frameB, tr.b.GUID.allocate(), 'C');
      *   root.addStackTrace(frameC.stackTrace, 42)
      *
      * will add the path root -> A -> B -> C to the tree (if necessary), add 42
      * to the total value of all the nodes on the path (root, A, B, C), and add
      * 42 to the self value of the leaf node (C).
      *
      * Important: No stack traces should be added to a bottom-up view (once it
      * has been converted). Doing so will not update the structure and values
      * of the view correctly!
      */
     addStackTrace: function(trace, value, opt_traceContainsRootFrame) {
       var currentNode = this;
       var startIndex = trace.length - (opt_traceContainsRootFrame ? 2 : 1);
       for (var i = startIndex; i >= 0; i--) {
         currentNode.total += value;
         var stackFrame = trace[i];
         currentNode =
             currentNode.getOrCreateChild(stackFrame.title, stackFrame);
       }
       currentNode.total += value;
       currentNode.self += value;
     },

     /**
      * Converts this stack frame tree from top-down view to the corresponding
      * bottom-up view. This method returns the root of the tree representing
      * the bottom-up view.
      *
      * Note that there is no connection between the two representations after
      * the conversion (modifying the structure and/or values of one of them
      * will not affect the other one).
      */
     convertToBottomUpView: function() {
       var bottomUpViewRoot = new StackFrameTreeNode(this.title, this.frame);
       bottomUpViewRoot.total = this.total;
       bottomUpViewRoot.self = this.self;

       this.addChildrenToBottomUpViewRecursively_(bottomUpViewRoot);

       return bottomUpViewRoot;
     },

     addChildrenToBottomUpViewRecursively_: function(bottomUpViewRoot) {
       this.children.forEach(function(child) {
         child.addToBottomUpViewRecursively_(bottomUpViewRoot);
       });
     },

     /**
      * Add this node and all its children to the provided bottom-up view.
      *
      * This code was inspired by
      * third_party/WebKit/Source/devtools/front_end/profiler/CPUProfileBottomUpDataGrid.js
      * in the Chromium tree.
      */
     addToBottomUpViewRecursively_: function(bottomUpViewRoot) {
       // Determine the length of the suffix of the trace associated with this
       // node whose total should *not* be added to the corresponding bottom-up
       // view node. This is to avoid double-counting recursive calls. Note that
       // this does not affect self size.
       //
       // For example, if this node corresponds to the leaf stack frame (B) of
       // root -> A -> B -> C -> A -> B, then the length of the suffix will be
       // 2. This means that the total size of this node will only be added to
       // nodes marked with * in the resulting bottom-up representation
       // root -> B -> A -> C* -> B* -> A*. The reason for this is that the
       // total would already have been included when the root -> A -> B prefix
       // of the trace was added to the bottom-up view (when the great
       // grandparent (A) of this node was visited by this recursive method).
       var remainingRecursiveSuffixLength =
           this.calculateRecursiveSuffixLength_();

       // Construct the bottom-up view counterpart of this top-down view node.
       //
       // For example, if this node corresponds to the leaf stack frame (C) of
       // the stack trace root -> A -> B -> C, the bottom-up view will be
       // updated with root -> C -> B -> A.
       var bottomUpParentNode = bottomUpViewRoot;
       for (var topDownNode = this;
            topDownNode.parent !== undefined /* don't include the root node */;
            topDownNode = topDownNode.parent) {
         var bottomUpChildNode = bottomUpParentNode.getOrCreateChild(
             topDownNode.title, topDownNode.frame);
         bottomUpChildNode.self += this.self;
         if (remainingRecursiveSuffixLength > 0)
           remainingRecursiveSuffixLength--;
         else
           bottomUpChildNode.total += this.total;
         bottomUpParentNode = bottomUpChildNode;
       }

       this.addChildrenToBottomUpViewRecursively_(bottomUpViewRoot);
     },

     /**
      * Determine the length of the longest suffix of the stack trace associated
      * with this node which is repeated in the trace.
      *
      * For example, if this node corresponds to the leaf stack frame (C) of the
      * stack trace root -> A -> B -> C -> A -> B -> B -> C, then this method
      * will return 2 because the suffix B -> C is repeated in the trace.
      */
     calculateRecursiveSuffixLength_: function() {
       var maxLengths = zFunction(this.stackTraceTitles);
       var recursiveSuffixLength = 0;
       for (var i = 0; i < maxLengths.length; i++)
         recursiveSuffixLength = Math.max(recursiveSuffixLength, maxLengths[i]);
       return recursiveSuffixLength;
     }
   };

   return {
     StackFrameTreeNode: StackFrameTreeNode,
     zFunction: zFunction  // Exported for testing.
   };
 });
 </script>
	<!DOCTYPE html>
	<!--
	Copyright 2015 The Chromium Authors. All rights reserved.
	Use of this source code is governed by a BSD-style license that can be
	found in the LICENSE file.
	-->

	<link rel="import" href="/tracing/base/base.html">

	<script>
	'use strict';

	tr.exportTo('tr.ui.analysis', function() {

	/**
	* Z-function: Given a list (or a string) of length n, for each index i from
	* 1 to n - 1, find the length z[i] of the longest substring starting at
	* position i which is also a prefix of the list. This function returns the
	* list of maximum lengths z.
	*
	* Mathematically, for each i from 1 to n - 1, z[i] is the maximum value such
	* that [list[0], ..., list[i - 1]] = [list[i], ..., list[i + z[i] - 1]].
	* z[0] is defined to be zero for convenience.
	*
	* Example:
	*
	* Input (list): ['A', 'B', 'A', 'C', 'A', 'B', 'A']
	* Output (z): [ 0 , 0 , 1 , 0 , 3 , 0 , 1 ]
	*
	* Unlike the brute-force approach (which is O(n^2) in the worst case), the
	* complexity of this implementation is linear in the size of the list, i.e.
	* O(n).
	*
	* Source: http://e-maxx-eng.github.io/string/z-function.html
	*/
	function zFunction(list) {
	var n = list.length;
	if (n === 0)
	return [];

	var z = new Array(n);
	z[0] = 0;

	for (var i = 1, left = 0, right = 0; i < n; ++i) {
	var maxLength;
	if (i <= right)
	maxLength = Math.min(right - i + 1, z[i - left]);
	else
	maxLength = 0;

	while (i + maxLength < n && list[maxLength] === list[i + maxLength])
	++maxLength;

	if (i + maxLength - 1 > right) {
	left = i;
	right = i + maxLength - 1;
	}

	z[i] = maxLength;
	}

	return z;
	}

	/**
	* Node of a stack frame hierarchy representation for tree (top down) and
	* heavy (bottom up) views.
	*
	* To build a top-down view of a set of stack traces, you simply create a
	* root node and than add the stack traces to it:
	*
	* var topDownRoot = new StackFrameTreeNode('root', undefined);
	* topDownRoot.addStackTrace(trace1, size1);
	* topDownRoot.addStackTrace(trace2, size2);
	* ...
	* topDownRoot.addStackTrace(traceN, sizeN);
	*
	* The corresponding bottom-up view is constructed indirectly by converting
	* the top-down view:
	*
	* var bottomUpRoot = topDownRoot.convertToBottomUpView();
	*
	* @{constructor}
	*/
	function StackFrameTreeNode(title, opt_frame) {
	this.title = title;
	this.frame = opt_frame;

	this.parent = undefined;
	this.children = [];
	this.childMap = new Map();

	this.total = 0;
	this.self = 0;
	}

	StackFrameTreeNode.prototype = {
	/** Duck type <tr-ui-b-table> rows. */
	get subRows() {
	return this.children;
	},

	/**
	* Returns the list of titles of this node and all its ancestors (including
	* the root). The title of this node is first in the list.
	*
	* Note that this method does not use
	* tr.model.StackFrame.prototype.getUserFriendlyStackTrace because some
	* nodes don't have frames (e.g. the root).
	*/
	get stackTraceTitles() {
	var titles = [];
	for (var currentNode = this; currentNode !== undefined;
	currentNode = currentNode.parent) {
	titles.push(currentNode.title);
	}
	return titles;
	},

	getOrCreateChild: function(title, opt_frame) {
	var childNode = this.childMap.get(title);
	if (childNode !== undefined)
	return childNode;

	childNode = new StackFrameTreeNode(title, opt_frame);
	childNode.parent = this;
	this.children.push(childNode);
	this.childMap.set(title, childNode);

	return childNode;
	},

	/**
	* Add a stack trace to the stack frame tree. The first element of the
	* trace is expected to be the leaf stack frame (so that
	* tr.model.StackFrame.prototype.stackTrace could be used as the parameter
	* without any modification).
	*
	* For example, the following code snippet:
	*
	* var frameA = new StackFrame(undefined, tr.b.GUID.allocate(), 'A');
	* var frameB = new StackFrame(frameA, tr.b.GUID.allocate(), 'B');
	* var frameC = new StackFrame(frameB, tr.b.GUID.allocate(), 'C');
	* root.addStackTrace(frameC.stackTrace, 42)
	*
	* will add the path root -> A -> B -> C to the tree (if necessary), add 42
	* to the total value of all the nodes on the path (root, A, B, C), and add
	* 42 to the self value of the leaf node (C).
	*
	* Important: No stack traces should be added to a bottom-up view (once it
	* has been converted). Doing so will not update the structure and values
	* of the view correctly!
	*/
	addStackTrace: function(trace, value, opt_traceContainsRootFrame) {
	var currentNode = this;
	var startIndex = trace.length - (opt_traceContainsRootFrame ? 2 : 1);
	for (var i = startIndex; i >= 0; i--) {
	currentNode.total += value;
	var stackFrame = trace[i];
	currentNode =
	currentNode.getOrCreateChild(stackFrame.title, stackFrame);
	}
	currentNode.total += value;
	currentNode.self += value;
	},

	/**
	* Converts this stack frame tree from top-down view to the corresponding
	* bottom-up view. This method returns the root of the tree representing
	* the bottom-up view.
	*
	* Note that there is no connection between the two representations after
	* the conversion (modifying the structure and/or values of one of them
	* will not affect the other one).
	*/
	convertToBottomUpView: function() {
	var bottomUpViewRoot = new StackFrameTreeNode(this.title, this.frame);
	bottomUpViewRoot.total = this.total;
	bottomUpViewRoot.self = this.self;

	this.addChildrenToBottomUpViewRecursively_(bottomUpViewRoot);

	return bottomUpViewRoot;
	},

	addChildrenToBottomUpViewRecursively_: function(bottomUpViewRoot) {
	this.children.forEach(function(child) {
	child.addToBottomUpViewRecursively_(bottomUpViewRoot);
	});
	},

	/**
	* Add this node and all its children to the provided bottom-up view.
	*
	* This code was inspired by
	* third_party/WebKit/Source/devtools/front_end/profiler/CPUProfileBottomUpDataGrid.js
	* in the Chromium tree.
	*/
	addToBottomUpViewRecursively_: function(bottomUpViewRoot) {
	// Determine the length of the suffix of the trace associated with this
	// node whose total should not be added to the corresponding bottom-up
	// view node. This is to avoid double-counting recursive calls. Note that
	// this does not affect self size.
	//
	// For example, if this node corresponds to the leaf stack frame (B) of
	// root -> A -> B -> C -> A -> B, then the length of the suffix will be
	// 2. This means that the total size of this node will only be added to
	// nodes marked with * in the resulting bottom-up representation
	// root -> B -> A -> C* -> B* -> A*. The reason for this is that the
	// total would already have been included when the root -> A -> B prefix
	// of the trace was added to the bottom-up view (when the great
	// grandparent (A) of this node was visited by this recursive method).
	var remainingRecursiveSuffixLength =
	this.calculateRecursiveSuffixLength_();

	// Construct the bottom-up view counterpart of this top-down view node.
	//
	// For example, if this node corresponds to the leaf stack frame (C) of
	// the stack trace root -> A -> B -> C, the bottom-up view will be
	// updated with root -> C -> B -> A.
	var bottomUpParentNode = bottomUpViewRoot;
	for (var topDownNode = this;
	topDownNode.parent !== undefined /* don't include the root node */;
	topDownNode = topDownNode.parent) {
	var bottomUpChildNode = bottomUpParentNode.getOrCreateChild(
	topDownNode.title, topDownNode.frame);
	bottomUpChildNode.self += this.self;
	if (remainingRecursiveSuffixLength > 0)
	remainingRecursiveSuffixLength--;
	else
	bottomUpChildNode.total += this.total;
	bottomUpParentNode = bottomUpChildNode;
	}

	this.addChildrenToBottomUpViewRecursively_(bottomUpViewRoot);
	},

	/**
	* Determine the length of the longest suffix of the stack trace associated
	* with this node which is repeated in the trace.
	*
	* For example, if this node corresponds to the leaf stack frame (C) of the
	* stack trace root -> A -> B -> C -> A -> B -> B -> C, then this method
	* will return 2 because the suffix B -> C is repeated in the trace.
	*/
	calculateRecursiveSuffixLength_: function() {
	var maxLengths = zFunction(this.stackTraceTitles);
	var recursiveSuffixLength = 0;
	for (var i = 0; i < maxLengths.length; i++)
	recursiveSuffixLength = Math.max(recursiveSuffixLength, maxLengths[i]);
	return recursiveSuffixLength;
	}
	};

	return {
	StackFrameTreeNode: StackFrameTreeNode,
	zFunction: zFunction // Exported for testing.
	};
	});
	</script>