<!DOCTYPE html>
<!--
Copyright (c) 2013 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="/core/trace_model/event_container.html">
<link rel="import" href="/core/filter.html">
<link rel="import" href="/base/ui/color_scheme.html">
<link rel="import" href="/base/guid.html">
<link rel="import" href="/base/sorted_array_utils.html">

<script>
'use strict';

/**
 * @fileoverview Provides the SliceGroup class.
 */
tv.exportTo('tv.c.trace_model', function() {
  var Slice = tv.c.trace_model.Slice;

  function getSliceLo(s) {
    return s.start;
  }

  function getSliceHi(s) {
    return s.end;
  }

  /**
   * A group of Slices, plus code to create them from B/E events, as
   * well as arrange them into subRows.
   *
   * Do not mutate the slices array directly. Modify it only by
   * SliceGroup mutation methods.
   *
   * @constructor
   * @param {function(new:Slice, category, title, colorId, start, args)=}
   *     opt_sliceConstructor The constructor to use when creating slices.
   * @extends {tv.c.trace_model.EventContainer}
   */
  function SliceGroup(parentThread, opt_sliceConstructor, opt_name) {
    this.guid_ = tv.b.GUID.allocate();

    this.parentThread_ = parentThread;

    var sliceConstructor = opt_sliceConstructor || Slice;
    this.sliceConstructor = sliceConstructor;

    this.openPartialSlices_ = [];

    this.slices = [];
    this.bounds = new tv.b.Range();
    this.topLevelSlices = [];
    this.haveTopLevelSlicesBeenBuilt = false;
    this.name_ = opt_name;
  }

  SliceGroup.prototype = {
    __proto__: tv.c.trace_model.EventContainer.prototype,

    get guid() {
      return this.guid_;
    },

    get parentThread() {
      return this.parentThread_;
    },

    get model() {
      return this.parentThread_.parent.model;
    },

    get stableId() {
      return this.parentThread_.stableId + '.SliceGroup';
    },

    getSettingsKey: function() {
      if (!this.name_)
        return undefined;
      var parentKey = this.parentThread_.getSettingsKey();
      if (!parentKey)
        return undefined;
      return parentKey + '.' + this.name;
    },

    /**
     * @return {Number} The number of slices in this group.
     */
    get length() {
      return this.slices.length;
    },

    /**
     * Helper function that pushes the provided slice onto the slices array.
     * @param {Slice} slice The slice to be added to the slices array.
     */
    pushSlice: function(slice) {
      this.haveTopLevelSlicesBeenBuilt = false;
      this.slices.push(slice);
      return slice;
    },

    /**
     * Helper function that pushes the provided slices onto the slices array.
     * @param {Array.<Slice>} slices An array of slices to be added.
     */
    pushSlices: function(slices) {
      this.haveTopLevelSlicesBeenBuilt = false;
      this.slices.push.apply(this.slices, slices);
    },

    /**
     * Opens a new slice in the group's slices.
     *
     * Calls to beginSlice and
     * endSlice must be made with non-monotonically-decreasing timestamps.
     *
     * @param {String} category Category name of the slice to add.
     * @param {String} title Title of the slice to add.
     * @param {Number} ts The timetsamp of the slice, in milliseconds.
     * @param {Object.<string, Object>=} opt_args Arguments associated with
     * the slice.
     */
    beginSlice: function(category, title, ts, opt_args, opt_tts) {
      if (this.openPartialSlices_.length) {
        var prevSlice = this.openPartialSlices_[
            this.openPartialSlices_.length - 1];
        if (ts < prevSlice.start)
          throw new Error('Slices must be added in increasing timestamp order');
      }

      var colorId = tv.b.ui.getColorIdForGeneralPurposeString(title);
      var slice = new this.sliceConstructor(category, title, colorId, ts,
                                            opt_args ? opt_args : {}, null,
                                            opt_tts);
      this.openPartialSlices_.push(slice);
      slice.didNotFinish = true;
      this.pushSlice(slice);

      return slice;
    },

    isTimestampValidForBeginOrEnd: function(ts) {
      if (!this.openPartialSlices_.length)
        return true;
      var top = this.openPartialSlices_[this.openPartialSlices_.length - 1];
      return ts >= top.start;
    },

    /**
     * @return {Number} The number of beginSlices for which an endSlice has not
     * been issued.
     */
    get openSliceCount() {
      return this.openPartialSlices_.length;
    },

    get mostRecentlyOpenedPartialSlice() {
      if (!this.openPartialSlices_.length)
        return undefined;
      return this.openPartialSlices_[this.openPartialSlices_.length - 1];
    },

    /**
     * Ends the last begun slice in this group and pushes it onto the slice
     * array.
     *
     * @param {Number} ts Timestamp when the slice ended.
     * @return {Slice} slice.
     */
    endSlice: function(ts, opt_tts) {
      if (!this.openSliceCount)
        throw new Error('endSlice called without an open slice');

      var slice = this.openPartialSlices_[this.openSliceCount - 1];
      this.openPartialSlices_.splice(this.openSliceCount - 1, 1);
      if (ts < slice.start)
        throw new Error('Slice ' + slice.title +
                        ' end time is before its start.');

      slice.duration = ts - slice.start;
      slice.didNotFinish = false;

      if (opt_tts && slice.cpuStart !== undefined)
        slice.cpuDuration = opt_tts - slice.cpuStart;

      return slice;
    },

    /**
     * Push a complete event as a Slice into the slice list.
     * The timestamp can be in any order.
     *
     * @param {String} category Category name of the slice to add.
     * @param {String} title Title of the slice to add.
     * @param {Number} ts The timetsamp of the slice, in milliseconds.
     * @param {Number} duration The duration of the slice, in milliseconds.
     * @param {Object.<string, Object>=} opt_args Arguments associated with
     * the slice.
     */
    pushCompleteSlice: function(category, title, ts, duration, tts,
                                cpuDuration, opt_args) {
      var colorId = tv.b.ui.getColorIdForGeneralPurposeString(title);
      var slice = new this.sliceConstructor(category, title, colorId, ts,
                                            opt_args ? opt_args : {},
                                            duration, tts, cpuDuration);
      if (duration === undefined)
        slice.didNotFinish = true;
      this.pushSlice(slice);
      return slice;
    },

    /**
     * Closes any open slices.
     * @param {Number=} opt_maxTimestamp The end time to use for the closed
     * slices. If not provided,
     * the max timestamp for this slice is provided.
     */
    autoCloseOpenSlices: function(opt_maxTimestamp) {
      if (!opt_maxTimestamp) {
        this.updateBounds();
        opt_maxTimestamp = this.bounds.max;
      }
      for (var sI = 0; sI < this.slices.length; sI++) {
        var slice = this.slices[sI];
        if (slice.didNotFinish)
          slice.duration = opt_maxTimestamp - slice.start;
      }
      this.openPartialSlices_ = [];
    },

    /**
     * Shifts all the timestamps inside this group forward by the amount
     * specified.
     */
    shiftTimestampsForward: function(amount) {
      for (var sI = 0; sI < this.slices.length; sI++) {
        var slice = this.slices[sI];
        slice.start = (slice.start + amount);
      }
    },

    /**
     * Updates the bounds for this group based on the slices it contains.
     */
    updateBounds: function() {
      this.bounds.reset();
      for (var i = 0; i < this.slices.length; i++) {
        this.bounds.addValue(this.slices[i].start);
        this.bounds.addValue(this.slices[i].end);
      }
    },

    copySlice: function(slice) {
      var newSlice = new this.sliceConstructor(slice.category, slice.title,
          slice.colorId, slice.start,
          slice.args, slice.duration, slice.cpuStart, slice.cpuDuration);
      newSlice.didNotFinish = slice.didNotFinish;
      return newSlice;
    },

    iterateAllEventsInThisContainer: function(eventTypePredicate,
                                              callback, opt_this) {
      if (eventTypePredicate.call(opt_this, this.sliceConstructor))
        this.slices.forEach(callback, opt_this);
    },

    iterateAllChildEventContainers: function(callback, opt_this) {
    },

    getSlicesOfName: function(title) {
      var slices = [];
      for (var i = 0; i < this.slices.length; i++) {
        if (this.slices[i].title == title) {
          slices.push(this.slices[i]);
        }
      }
      return slices;
    },

    iterSlicesInTimeRange: function(callback, start, end) {
      var ret = [];
      tv.b.iterateOverIntersectingIntervals(
        this.topLevelSlices,
        function(s) { return s.start; },
        function(s) { return s.duration; },
        start,
        end,
        function(topLevelSlice) {
          callback(topLevelSlice);
          topLevelSlice.iterateAllDescendents(callback);
        });
      return ret;
    },

    findSliceAtTs: function(ts) {
      if (!this.haveTopLevelSlicesBeenBuilt)
        throw new Error('Nope');
      var i = tv.b.findIndexInSortedClosedIntervals(
          this.topLevelSlices,
          getSliceLo, getSliceHi,
          ts);
      if (i == -1 || i == this.topLevelSlices.length)
        return undefined;

      var curSlice = this.topLevelSlices[i];

      // Now recurse on slice looking for subSlice of given ts.
      while (true) {
        var i = tv.b.findIndexInSortedClosedIntervals(
            curSlice.subSlices,
            getSliceLo, getSliceHi,
            ts);
        if (i == -1 || i == curSlice.subSlices.length)
          return curSlice;
        curSlice = curSlice.subSlices[i];
      }
    },

    findNextSliceAfter: function(ts, refGuid) {
      var i = tv.b.findLowIndexInSortedArray(
          this.slices, getSliceLo, ts);
      if (i === this.slices.length)
        return undefined;
      for (; i < this.slices.length; i++) {
        var slice = this.slices[i];
        if (slice.start > ts)
          return slice;
        if (slice.guid <= refGuid)
          continue;
        return slice;
      }
      return undefined;
    },

    /**
     * Construct subSlices for this group.
     * Populate the group topLevelSlices, parent slices get a subSlices[],
     * a selfThreadTime and a selfTime, child slices get a parentSlice
     * reference.
     */
    createSubSlices: function() {
      this.haveTopLevelSlicesBeenBuilt = true;
      this.createSubSlicesImpl_();
      if (this.parentThread.timeSlices)
        this.addCpuTimeToSubslices_(this.parentThread.timeSlices);
      this.slices.forEach(function(slice) {
        var selfTime = slice.duration;
        for (var i = 0; i < slice.subSlices.length; i++)
          selfTime -= slice.subSlices[i].duration;
        slice.selfTime = selfTime;

        if (slice.cpuDuration === undefined)
          return;

        var cpuSelfTime = slice.cpuDuration;
        for (var i = 0; i < slice.subSlices.length; i++) {
          if (slice.subSlices[i].cpuDuration !== undefined)
            cpuSelfTime -= slice.subSlices[i].cpuDuration;
        }
        slice.cpuSelfTime = cpuSelfTime;
      });
    },
    createSubSlicesImpl_: function() {
      function addSliceIfBounds(root, child) {
        // Because we know that the start time of child is >= the start time
        // of all other slices seen so far, we can just check the last slice
        // of each row for bounding.
        if (root.bounds(child)) {
          if (root.subSlices && root.subSlices.length > 0) {
            if (addSliceIfBounds(root.subSlices[root.subSlices.length - 1],
                                 child))
              return true;
          }
          child.parentSlice = root;
          if (root.subSlices === undefined)
            root.subSlices = [];
          root.subSlices.push(child);
          return true;
        }
        return false;
      }

      if (!this.slices.length)
        return;

      var ops = [];
      for (var i = 0; i < this.slices.length; i++) {
        if (this.slices[i].subSlices)
          this.slices[i].subSlices.splice(0,
                                          this.slices[i].subSlices.length);
        ops.push(i);
      }

      var originalSlices = this.slices;
      ops.sort(function(ix, iy) {
        var x = originalSlices[ix];
        var y = originalSlices[iy];
        if (x.start != y.start)
          return x.start - y.start;

        // Elements get inserted into the slices array in order of when the
        // slices start. Because slices must be properly nested, we break
        // start-time ties by assuming that the elements appearing earlier
        // in the slices array (and thus ending earlier) start earlier.
        return ix - iy;
      });

      var slices = new Array(this.slices.length);
      for (var i = 0; i < ops.length; i++) {
        slices[i] = originalSlices[ops[i]];
      }

      // Actually build the subrows.
      var rootSlice = slices[0];
      this.topLevelSlices = [];
      this.topLevelSlices.push(rootSlice);
      for (var i = 1; i < slices.length; i++) {
        var slice = slices[i];
        if (!addSliceIfBounds(rootSlice, slice)) {
          rootSlice = slice;
          this.topLevelSlices.push(rootSlice);
        }
      }

      // Keep the slices in sorted form.
      this.slices = slices;
    },
    addCpuTimeToSubslices_: function(timeSlices) {
      var SCHEDULING_STATE = tv.c.trace_model.SCHEDULING_STATE;
      var sliceIdx = 0;
      timeSlices.forEach(function(timeSlice) {
        if (timeSlice.schedulingState == SCHEDULING_STATE.RUNNING) {
          while (sliceIdx < this.topLevelSlices.length) {
            if (this.addCpuTimeToSubslice_(this.topLevelSlices[sliceIdx],
                timeSlice)) {
              // The current top-level slice and children are fully
              // accounted for, proceed to next top-level slice.
              sliceIdx++;
            } else {
              // The current top-level runs beyond the time slice, break out
              // so we can potentially add more time slices to it
              break;
            }
          }
        }
      }, this);
    },
    /* Add run-time of this timeSlice to the passed in slice
     * and all of it's children (recursively).
     * Returns whether the slice ends before or at the end of the
     * time slice, signaling we are done with this slice.
     */
    addCpuTimeToSubslice_: function(slice, timeSlice) {
      // Make sure they overlap
      if (slice.start > timeSlice.end || slice.end < timeSlice.start)
        return slice.end <= timeSlice.end;

      // Compute actual overlap
      var duration = timeSlice.duration;
      if (slice.start > timeSlice.start)
        duration -= slice.start - timeSlice.start;
      if (timeSlice.end > slice.end)
        duration -= timeSlice.end - slice.end;

      if (slice.cpuDuration) {
        slice.cpuDuration += duration;
      } else {
        slice.cpuDuration = duration;
      }

      for (var i = 0; i < slice.subSlices.length; i++) {
        this.addCpuTimeToSubslice_(slice.subSlices[i], timeSlice);
      }

      return slice.end <= timeSlice.end;
    }
  };

  /**
   * Merge two slice groups.
   *
   * If the two groups do not nest properly some of the slices of groupB will
   * be split to accomodate the improper nesting.  This is done to accomodate
   * combined kernel and userland call stacks on Android.  Because userland
   * tracing is done by writing to the trace_marker file, the kernel calls
   * that get invoked as part of that write may not be properly nested with
   * the userland call trace.  For example the following sequence may occur:
   *
   *     kernel enter sys_write        (the write to trace_marker)
   *     user   enter some_function
   *     kernel exit  sys_write
   *     ...
   *     kernel enter sys_write        (the write to trace_marker)
   *     user   exit  some_function
   *     kernel exit  sys_write
   *
   * This is handled by splitting the sys_write call into two slices as
   * follows:
   *
   *     | sys_write |            some_function            | sys_write (cont.) |
   *                 | sys_write (cont.) |     | sys_write |
   *
   * The colorId of both parts of the split slices are kept the same, and the
   * " (cont.)" suffix is appended to the later parts of a split slice.
   *
   * The two input SliceGroups are not modified by this, and the merged
   * SliceGroup will contain a copy of each of the input groups' slices (those
   * copies may be split).
   */
  SliceGroup.merge = function(groupA, groupB) {
    // This is implemented by traversing the two slice groups in reverse
    // order.  The slices in each group are sorted by ascending end-time, so
    // we must do the traversal from back to front in order to maintain the
    // sorting.
    //
    // We traverse the two groups simultaneously, merging as we go.  At each
    // iteration we choose the group from which to take the next slice based
    // on which group's next slice has the greater end-time.  During this
    // traversal we maintain a stack of currently "open" slices for each input
    // group.  A slice is considered "open" from the time it gets reached in
    // our input group traversal to the time we reach an slice in this
    // traversal with an end-time before the start time of the "open" slice.
    //
    // Each time a slice from groupA is opened or closed (events corresponding
    // to the end-time and start-time of the input slice, respectively) we
    // split all of the currently open slices from groupB.

    if (groupA.openPartialSlices_.length > 0)
      throw new Error('groupA has open partial slices');

    if (groupB.openPartialSlices_.length > 0)
      throw new Error('groupB has open partial slices');

    if (groupA.parentThread != groupB.parentThread)
      throw new Error('Different parent threads. Cannot merge');

    if (groupA.sliceConstructor != groupB.sliceConstructor)
      throw new Error('Different slice constructors. Cannot merge');

    var result = new SliceGroup(groupA.parentThread,
                                groupA.sliceConstructor,
                                groupA.name_);

    var slicesA = groupA.slices;
    var slicesB = groupB.slices;
    var idxA = 0;
    var idxB = 0;
    var openA = [];
    var openB = [];

    var splitOpenSlices = function(when) {
      for (var i = 0; i < openB.length; i++) {
        var oldSlice = openB[i];
        var oldEnd = oldSlice.end;
        if (when < oldSlice.start || oldEnd < when) {
          throw new Error('slice should not be split');
        }

        var newSlice = result.copySlice(oldSlice);
        newSlice.start = when;
        newSlice.duration = oldEnd - when;
        if (newSlice.title.indexOf(' (cont.)') == -1)
          newSlice.title += ' (cont.)';
        oldSlice.duration = when - oldSlice.start;
        openB[i] = newSlice;
        result.pushSlice(newSlice);
      }
    };

    var closeOpenSlices = function(upTo) {
      while (openA.length > 0 || openB.length > 0) {
        var nextA = openA[openA.length - 1];
        var nextB = openB[openB.length - 1];
        var endA = nextA && nextA.end;
        var endB = nextB && nextB.end;

        if ((endA === undefined || endA > upTo) &&
            (endB === undefined || endB > upTo)) {
          return;
        }

        if (endB === undefined || endA < endB) {
          splitOpenSlices(endA);
          openA.pop();
        } else {
          openB.pop();
        }
      }
    };

    while (idxA < slicesA.length || idxB < slicesB.length) {
      var sA = slicesA[idxA];
      var sB = slicesB[idxB];
      var nextSlice, isFromB;

      if (sA === undefined || (sB !== undefined && sA.start > sB.start)) {
        nextSlice = result.copySlice(sB);
        isFromB = true;
        idxB++;
      } else {
        nextSlice = result.copySlice(sA);
        isFromB = false;
        idxA++;
      }

      closeOpenSlices(nextSlice.start);

      result.pushSlice(nextSlice);

      if (isFromB) {
        openB.push(nextSlice);
      } else {
        splitOpenSlices(nextSlice.start);
        openA.push(nextSlice);
      }
    }

    closeOpenSlices();

    return result;
  };

  return {
    SliceGroup: SliceGroup
  };
});
</script>