<!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>