src/model/slice_group.js

// Copyright (c) 2012 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.

'use strict';

/**
 * @fileoverview Provides the SliceGroup class.
 */
base.require('range');
base.require('model.slice');
base.require('color_scheme');
base.require('filter');

base.exportTo('tracing.model', function() {
  var Slice = tracing.model.Slice;

  /**
   * 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.
   */
  function SliceGroup(opt_sliceConstructor) {
    var sliceConstructor = opt_sliceConstructor || Slice;
    this.sliceConstructor = sliceConstructor;

    this.openPartialSlices_ = [];

    this.slices = [];
    this.bounds = new base.Range();
  }

  SliceGroup.prototype = {
    __proto__: Object.prototype,

    /**
     * @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.slices.push(slice);
      return slice;
    },

    /**
     * Helper function that pushes the provided slice onto the slices array.
     * @param {Array.<Slice>} slices An array of slices to be added.
     */
    pushSlices: function(slices) {
      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} 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) {
      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 = tracing.getStringColorId(title);
      var slice = new this.sliceConstructor(category, title, colorId, ts,
                                            opt_args ? opt_args : {});
      this.openPartialSlices_.push(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;
    },

    /**
     * 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) {
      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;
      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;
      }
      while (this.openSliceCount > 0) {
        var slice = this.endSlice(opt_maxTimestamp);
        slice.didNotFinish = true;
      }
    },

    /**
     * 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);
      }
      for (var sI = 0; sI < this.openPartialSlices_.length; sI++) {
        var slice = this.openPartialSlices_[i];
        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);
      }

      if (this.openPartialSlices_.length) {
        this.bounds.addValue(this.openPartialSlices_[0].start);
        this.bounds.addValue(
            this.openPartialSlices_[this.openPartialSlices_.length - 1].start);
      }
    },

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

  /**
   * 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');
    }

    var result = new SliceGroup();

    var slicesA = groupA.slices;
    var slicesB = groupB.slices;
    var idxA = slicesA.length - 1;
    var idxB = slicesB.length - 1;
    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);
        oldSlice.start = when;
        oldSlice.duration = oldEnd - when;
        oldSlice.title += ' (cont.)';
        newSlice.duration = when - newSlice.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 startA = nextA && nextA.start;
        var startB = nextB && nextB.start;

        if ((startA === undefined || startA < upTo) &&
            (startB === undefined || startB < upTo)) {
          return;
        }

        if (startB === undefined || startA > startB) {
          splitOpenSlices(startA);
          openA.pop();
        } else {
          openB.pop();
        }
      }
    }

    while (idxA >= 0 || idxB >= 0) {
      var sA = slicesA[idxA];
      var sB = slicesB[idxB];
      var nextSlice, isFromB;

      if (sA === undefined || (sB !== undefined && sA.end < sB.end)) {
        nextSlice = result.copySlice(sB);
        isFromB = true;
        idxB--;
      } else {
        nextSlice = result.copySlice(sA);
        isFromB = false;
        idxA--;
      }

      closeOpenSlices(nextSlice.end);

      result.pushSlice(nextSlice);

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

    closeOpenSlices();

    result.slices.reverse();

    return result;
  };

  return {
    SliceGroup: SliceGroup
  };
});