<!DOCTYPE html>
<!--
Copyright (c) 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">
<link rel="import" href="/tracing/base/range_utils.html">
<link rel="import" href="/tracing/core/auditor.html">
<link rel="import" href="/tracing/extras/chrome/cc/input_latency_async_slice.html">
<link rel="import" href="/tracing/extras/chrome/chrome_model_helper.html">
<link rel="import" href="/tracing/extras/rail/idle_interaction_record.html">
<link rel="import" href="/tracing/extras/rail/load_interaction_record.html">
<link rel="import" href="/tracing/extras/rail/proto_ir.html">
<link rel="import" href="/tracing/model/event_info.html">
<link rel="import" href="/tracing/model/ir_coverage.html">

<script>
'use strict';

/**
 * @fileoverview Base class for trace data Auditors.
 */
tr.exportTo('tr.e.rail', function() {
  var INPUT_TYPE = tr.e.cc.INPUT_EVENT_TYPE_NAMES;
  var ProtoIR = tr.e.rail.ProtoIR;

  function compareEvents(x, y) {
    if (x.start !== y.start)
      return x.start - y.start;
    if (x.end !== y.end)
      return x.end - y.end;
    if (x.guid && y.guid)
      return x.guid - y.guid;
    return 0;
  }

  function causedFrame(event) {
    for (var i = 0; i < event.associatedEvents.length; ++i) {
      if (event.associatedEvents[i].title === tr.e.audits.IMPL_RENDERING_STATS)
        return true;
    }
    return false;
  }

  // If there's less than this much time between the end of one event and the
  // start of the next, then they might be merged.
  // There was not enough thought given to this value, so if you have any slight
  // reason to change it, then please do so. It might also be good to split this
  // into multiple values.
  var INPUT_MERGE_THRESHOLD_MS = 200;
  var ANIMATION_MERGE_THRESHOLD_MS = 1;

  // If two MouseWheel events begin this close together, then they're an
  // Animation, not two responses.
  var MOUSE_WHEEL_THRESHOLD_MS = 40;

  var INSIGNIFICANT_MS = 1;

  var KEYBOARD_TYPE_NAMES = [
    INPUT_TYPE.CHAR,
    INPUT_TYPE.KEY_DOWN_RAW,
    INPUT_TYPE.KEY_DOWN,
    INPUT_TYPE.KEY_UP
  ];
  var MOUSE_RESPONSE_TYPE_NAMES = [
    INPUT_TYPE.CLICK,
    INPUT_TYPE.CONTEXT_MENU
  ];
  var MOUSE_WHEEL_TYPE_NAMES = [
    INPUT_TYPE.MOUSE_WHEEL
  ];
  var MOUSE_DRAG_TYPE_NAMES = [
    INPUT_TYPE.MOUSE_DOWN,
    INPUT_TYPE.MOUSE_MOVE,
    INPUT_TYPE.MOUSE_UP
  ];
  var TAP_TYPE_NAMES = [
    INPUT_TYPE.TAP,
    INPUT_TYPE.TAP_CANCEL,
    INPUT_TYPE.TAP_DOWN
  ];
  var PINCH_TYPE_NAMES = [
    INPUT_TYPE.PINCH_BEGIN,
    INPUT_TYPE.PINCH_END,
    INPUT_TYPE.PINCH_UPDATE
  ];
  var FLING_TYPE_NAMES = [
    INPUT_TYPE.FLING_CANCEL,
    INPUT_TYPE.FLING_START
  ];
  var TOUCH_TYPE_NAMES = [
    INPUT_TYPE.TOUCH_END,
    INPUT_TYPE.TOUCH_MOVE,
    INPUT_TYPE.TOUCH_START
  ];
  var SCROLL_TYPE_NAMES = [
    INPUT_TYPE.SCROLL_BEGIN,
    INPUT_TYPE.SCROLL_END,
    INPUT_TYPE.SCROLL_UPDATE
  ];
  var ALL_HANDLED_TYPE_NAMES = [].concat(
    KEYBOARD_TYPE_NAMES,
    MOUSE_RESPONSE_TYPE_NAMES,
    MOUSE_WHEEL_TYPE_NAMES,
    MOUSE_DRAG_TYPE_NAMES,
    PINCH_TYPE_NAMES,
    TAP_TYPE_NAMES,
    FLING_TYPE_NAMES,
    TOUCH_TYPE_NAMES,
    SCROLL_TYPE_NAMES
  );

  var RENDERER_FLING_TITLE = 'InputHandlerProxy::HandleGestureFling::started';
  var CSS_ANIMATION_TITLE = 'Animation';

  function RAILIRFinder(model, modelHelper) {
    this.model = model;
    this.modelHelper = modelHelper;
  };

  RAILIRFinder.supportsModelHelper = function(modelHelper) {
    return modelHelper.browserHelper !== undefined;
  };

  RAILIRFinder.prototype = {
    findAllInteractionRecords: function() {
      var rirs = [];
      rirs.push.apply(rirs, this.findLoadInteractionRecords());
      rirs.push.apply(rirs, this.findInputInteractionRecords());
      // findIdleInteractionRecords must be called last!
      rirs.push.apply(rirs, this.findIdleInteractionRecords(rirs));
      this.collectUnassociatedEvents_(rirs);
      return rirs;
    },

    setIRNames_: function(name, irs) {
      irs.forEach(function(ir) {
        ir.name = name;
      });
    },

    // Find all unassociated top-level ThreadSlices. If they start during an
    // Idle or Load IR, then add their entire hierarchy to that IR.
    collectUnassociatedEvents_: function(rirs) {
      var vacuumIRs = [];
      rirs.forEach(function(ir) {
        if (ir instanceof tr.e.rail.LoadInteractionRecord ||
            ir instanceof tr.e.rail.IdleInteractionRecord)
          vacuumIRs.push(ir);
      });
      if (vacuumIRs.length === 0)
        return;

      var allAssociatedEvents = tr.model.getAssociatedEvents(rirs);
      var unassociatedEvents = tr.model.getUnassociatedEvents(
          this.model, allAssociatedEvents);

      unassociatedEvents.forEach(function(event) {
        if (!(event instanceof tr.model.ThreadSlice))
          return;

        if (!event.isTopLevel)
          return;

        for (var iri = 0; iri < vacuumIRs.length; ++iri) {
          var ir = vacuumIRs[iri];

          if ((event.start >= ir.start) &&
              (event.start < ir.end)) {
            ir.associatedEvents.addEventSet(event.entireHierarchy);
            return;
          }
        }
      });
    },

    // Fill in the empty space between IRs with IdleIRs.
    findIdleInteractionRecords: function(otherIRs) {
      if (this.model.bounds.isEmpty)
        return;
      var emptyRanges = tr.b.findEmptyRangesBetweenRanges(
          tr.b.convertEventsToRanges(otherIRs),
          this.model.bounds);
      var irs = [];
      emptyRanges.forEach(function(range) {
        // Ignore insignificantly tiny idle ranges.
        if (range.max < (range.min + INSIGNIFICANT_MS))
          return;
        irs.push(new tr.e.rail.IdleInteractionRecord(
            range.min, range.max - range.min));
      });
      return irs;
    },

    getAllFrameEvents: function() {
      var frameEvents = [];
      frameEvents.push.apply(frameEvents,
          this.modelHelper.browserHelper.getFrameEventsInRange(
              tr.e.audits.IMPL_FRAMETIME_TYPE, this.model.bounds));

      tr.b.iterItems(this.modelHelper.rendererHelpers, function(pid, renderer) {
        frameEvents.push.apply(frameEvents, renderer.getFrameEventsInRange(
            tr.e.audits.IMPL_FRAMETIME_TYPE, this.model.bounds));
      }, this);
      return frameEvents.sort(compareEvents);
    },

    getStartLoadEvents: function() {
      function isStartLoadSlice(slice) {
        return slice.title === 'RenderFrameImpl::didStartProvisionalLoad';
      }
      return this.modelHelper.browserHelper.getAllAsyncSlicesMatching(
          isStartLoadSlice).sort(compareEvents);
    },

    getFailLoadEvents: function() {
      function isFailLoadSlice(slice) {
        return slice.title === 'RenderFrameImpl::didFailProvisionalLoad';
      }
      return this.modelHelper.browserHelper.getAllAsyncSlicesMatching(
          isFailLoadSlice).sort(compareEvents);
    },

    // Main runner events are emitted very early on in the lifetime of browser
    // and renderer processes. It's emitted in the Initialize method of
    // ContentMainRunner as soon as TRACE_EVENT is available.
    getMainRunnerEvents: function() {
      function isMainRunnerSlice(slice) {
        return slice.title === 'ContentMainRunnerImpl::Initialize';
      }
      return this.modelHelper.browserHelper.getAllAsyncSlicesMatching(
          isMainRunnerSlice).sort(compareEvents);
    },

    // Match every event in |openingEvents| to the first following event from
    // |closingEvents| and return an array containing a load interaction record
    // for each pair.
    findLoadInteractionRecords_: function(openingEvents, closingEvents) {
      var lirs = [];
      openingEvents.forEach(function(openingEvent) {
        closingEvents.forEach(function(closingEvent) {
          // Ignore opening event thatalready have a closing event.
          if (openingEvent.closingEvent)
            return;

          // Ignore closing events that already belong to an opening event.
          if (closingEvent.openingEvent)
            return;

          // Ignore closing events before |openingEvent|.
          if (closingEvent.start <= openingEvent.start)
            return;

          // Ignore events from different threads.
          if (openingEvent.parentContainer.parent.pid !==
               closingEvent.parentContainer.parent.pid)
            return;

          // This is the first closing event for this opening event, record it.
          openingEvent.closingEvent = closingEvent;
          closingEvent.openingEvent = openingEvent;
          var lir = new tr.e.rail.LoadInteractionRecord(
              openingEvent.start, closingEvent.end - openingEvent.start);
          lir.associatedEvents.push(openingEvent);
          lir.associatedEvents.push(closingEvent);
          lirs.push(lir);
        });
      });
      return lirs;
    },

    // Match up RenderFrameImpl events with frame render events.
    findLoadInteractionRecords: function() {
      var mainRunnerEvents = this.getMainRunnerEvents();
      var commitLoadEvents =
          this.modelHelper.browserHelper.getCommitProvisionalLoadEventsInRange(
              this.model.bounds);
      var frameEvents = this.getAllFrameEvents();
      var startLoadEvents = this.getStartLoadEvents();
      var failLoadEvents = this.getFailLoadEvents();
      var lirs = [];

      // Attach frame events to every main runner events.
      var startupLIRs = this.findLoadInteractionRecords_(mainRunnerEvents,
          frameEvents);
      this.setIRNames_('Startup', startupLIRs);
      lirs.push.apply(lirs, startupLIRs);

      // Attach frame events to every commit load events.
      var succesfulLIRs = this.findLoadInteractionRecords_(commitLoadEvents,
          frameEvents);
      this.setIRNames_('Succeeded', succesfulLIRs);
      lirs.push.apply(lirs, succesfulLIRs);

      // Attach fail load events to every start load events.
      var failedLIRs = this.findLoadInteractionRecords_(startLoadEvents,
          failLoadEvents);
      this.setIRNames_('Failed', failedLIRs);
      lirs.push.apply(lirs, failedLIRs);

      return lirs;
    },

    // Find ProtoIRs, post-process them, convert them to real IRs.
    findInputInteractionRecords: function() {
      var protoIRs = this.findProtoIRs();
      protoIRs = this.postProcessProtoIRs(protoIRs);
      this.checkAllInputEventsHandled(protoIRs);

      var irs = [];
      protoIRs.forEach(function(protoIR) {
        var ir = protoIR.createInteractionRecord();
        if (ir)
          irs.push(ir);
      });
      return irs;
    },

    findProtoIRs: function() {
      var protoIRs = [];
      // This order is not important. Handlers are independent.
      protoIRs.push.apply(protoIRs, this.handleKeyboardEvents());
      protoIRs.push.apply(protoIRs, this.handleMouseResponseEvents());
      protoIRs.push.apply(protoIRs, this.handleMouseWheelEvents());
      protoIRs.push.apply(protoIRs, this.handleMouseDragEvents());
      protoIRs.push.apply(protoIRs, this.handleTapResponseEvents());
      protoIRs.push.apply(protoIRs, this.handlePinchEvents());
      protoIRs.push.apply(protoIRs, this.handleFlingEvents());
      protoIRs.push.apply(protoIRs, this.handleTouchEvents());
      protoIRs.push.apply(protoIRs, this.handleScrollEvents());
      protoIRs.push.apply(protoIRs, this.handleCSSAnimations());
      protoIRs.sort(compareEvents);
      return protoIRs;
    },

    getSortedInputEvents: function(typeNames) {
      function isMatchingSlice(slice) {
        if (!slice.isTopLevel)
          return false;

        if (!(slice instanceof tr.e.cc.InputLatencyAsyncSlice))
          return false;

        return typeNames.indexOf(slice.typeName) >= 0;
      }

      return this.modelHelper.browserHelper.getAllAsyncSlicesMatching(
          isMatchingSlice).sort(compareEvents);
    },

    // Every keyboard event is a Response.
    handleKeyboardEvents: function() {
      var protoIRs = [];
      this.getSortedInputEvents(KEYBOARD_TYPE_NAMES).forEach(function(event) {
        var pir = new ProtoIR(ProtoIR.RESPONSE_TYPE);
        pir.pushEvent(event);
        protoIRs.push(pir);
      });
      return protoIRs;
    },

    // Some mouse events can be translated directly into Responses.
    handleMouseResponseEvents: function() {
      var protoIRs = [];
      var mouseEvents = this.getSortedInputEvents(MOUSE_RESPONSE_TYPE_NAMES);
      mouseEvents.forEach(function(event) {
        var pir = new ProtoIR(ProtoIR.RESPONSE_TYPE);
        pir.pushEvent(event);
        protoIRs.push(pir);
      });
      return protoIRs;
    },

    // MouseWheel events are caused either by a physical wheel on a physical
    // mouse, or by a touch-drag gesture on a track-pad. The physical wheel
    // causes MouseWheel events that are much more spaced out, and have no
    // chance of hitting 60fps, so they are each turned into separate Response
    // IRs. The track-pad causes MouseWheel events that are much closer
    // together, and are expected to be 60fps, so the first event in a sequence
    // is turned into a Response, and the rest are merged into an Animation.
    // NB this threshold uses the two events' start times, unlike
    // ProtoIR.isNear, which compares the end time of the previous event with
    // the start time of the next.
    handleMouseWheelEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var prevEvent_ = undefined;
      var wheelEvents = this.getSortedInputEvents(MOUSE_WHEEL_TYPE_NAMES);
      wheelEvents.forEach(function(event) {
        // Switch prevEvent in one place so that we can early-return later.
        var prevEvent = prevEvent_;
        prevEvent_ = event;

        if (currentPIR &&
            (prevEvent.start + MOUSE_WHEEL_THRESHOLD_MS) >= event.start) {
          if (currentPIR.irType === ProtoIR.ANIMATION_TYPE) {
            currentPIR.pushEvent(event);
          } else {
            currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
            currentPIR.pushEvent(event);
            protoIRs.push(currentPIR);
          }
          return;
        }
        currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
        currentPIR.pushEvent(event);
        protoIRs.push(currentPIR);
      });
      return protoIRs;
    },

    // Down events followed closely by Up events are click Responses, but the
    // Response doesn't start until the Up event.
    //
    //     RRR
    // DDD UUU
    //
    // If there are any Move events in between a Down and an Up, then the Down
    // and the first Move are a Response, then the rest of the Moves are an
    // Animation:
    //
    // RRRRRRRAAAAAAAAAAAAAAAAAAAA
    // DDD MMM MMM MMM MMM MMM UUU
    //
    handleMouseDragEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var moveCount = 0;
      var mouseDownEvent = undefined;
      this.getSortedInputEvents(MOUSE_DRAG_TYPE_NAMES).forEach(function(event) {
        switch (event.typeName) {
          case INPUT_TYPE.MOUSE_DOWN:
            if (causedFrame(event)) {
              var pir = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
            } else {
              // Responses typically don't start until the mouse up event.
              // Add this MouseDown to the Response that starts at the MouseUp.
              mouseDownEvent = event;
              moveCount = 0;
            }
            break;
            // There may be more than 100ms between the start of the mouse down
            // and the start of the mouse up. Chrome and the web don't start to
            // respond until the mouse up. ResponseIRs start scoring "pain" at
            // 100ms duration. If more than that 100ms duration is burned
            // through while waiting for the user to release the
            // mouse button, then ResponseIR will unfairly start scoring pain
            // before Chrome even has a mouse up to respond to.
            // It is technically possible for a site to afford one response on
            // mouse down and another on mouse up, but that is an edge case. The
            // vast majority of mouse downs are not responses.

          case INPUT_TYPE.MOUSE_MOVE:
            if (!mouseDownEvent) {
              var pir = new ProtoIR(causedFrame(event) ? ProtoIR.RESPONSE_TYPE :
                  ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
              break;
            }

            moveCount++;
            if (moveCount === 1) {
              currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              currentPIR.pushEvent(event);
              if (mouseDownEvent)
                currentPIR.associatedEvents.push(mouseDownEvent);
              protoIRs.push(currentPIR);
            } else if (moveCount === 2) {
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            } else {
              currentPIR.pushEvent(event);
            }
            break;

          case INPUT_TYPE.MOUSE_UP:
            if (!mouseDownEvent) {
              var pir = new ProtoIR(causedFrame(event) ? ProtoIR.RESPONSE_TYPE :
                  ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
              break;
            }

            if (currentPIR) {
              currentPIR.pushEvent(event);
            } else {
              currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              if (mouseDownEvent)
                currentPIR.associatedEvents.push(mouseDownEvent);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            }
            mouseDownEvent = undefined;
            moveCount = 0;
            currentPIR = undefined;
            break;
        }
      });
      if (mouseDownEvent) {
        currentPIR = new ProtoIR(ProtoIR.IGNORED_TYPE);
        currentPIR.pushEvent(mouseDownEvent);
        protoIRs.push(currentPIR);
      }
      return protoIRs;
    },

    // Solitary Tap events are simple Responses:
    //
    // RRR
    // TTT
    //
    // TapDowns are part of Responses.
    //
    // RRRRRRR
    // DDD TTT
    //
    // TapCancels are part of Responses, which seems strange. They always go
    // with scrolls, so they'll probably be merged with scroll Responses.
    // TapCancels can take a significant amount of time and account for a
    // significant amount of work, which should be grouped with the scroll IRs
    // if possible.
    //
    // RRRRRRR
    // DDD CCC
    //
    handleTapResponseEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      this.getSortedInputEvents(TAP_TYPE_NAMES).forEach(function(event) {
        switch (event.typeName) {
          case INPUT_TYPE.TAP_DOWN:
            currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
            currentPIR.pushEvent(event);
            protoIRs.push(currentPIR);
            break;

          case INPUT_TYPE.TAP:
            if (currentPIR) {
              currentPIR.pushEvent(event);
            } else {
              // Sometimes we get Tap events with no TapDown, sometimes we get
              // TapDown events. Handle both.
              currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            }
            currentPIR = undefined;
            break;

          case INPUT_TYPE.TAP_CANCEL:
            if (!currentPIR) {
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
              break;
            }

            if (currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS)) {
              currentPIR.pushEvent(event);
            } else {
              currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            }
            currentPIR = undefined;
            break;
        }
      });
      return protoIRs;
    },

    // The PinchBegin and the first PinchUpdate comprise a Response, then the
    // rest of the PinchUpdates comprise an Animation.
    //
    // RRRRRRRAAAAAAAAAAAAAAAAAAAA
    // BBB UUU UUU UUU UUU UUU EEE
    //
    handlePinchEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var sawFirstUpdate = false;
      var modelBounds = this.model.bounds;
      this.getSortedInputEvents(PINCH_TYPE_NAMES).forEach(function(event) {
        switch (event.typeName) {
          case INPUT_TYPE.PINCH_BEGIN:
            if (currentPIR &&
                currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS)) {
              currentPIR.pushEvent(event);
              break;
            }
            currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
            currentPIR.pushEvent(event);
            protoIRs.push(currentPIR);
            sawFirstUpdate = false;
            break;

          case INPUT_TYPE.PINCH_UPDATE:
            // Like ScrollUpdates, the Begin and the first Update constitute a
            // Response, then the rest of the Updates constitute an Animation
            // that begins when the Response ends. If the user pauses in the
            // middle of an extended pinch gesture, then multiple Animations
            // will be created.
            if (!currentPIR ||
                ((currentPIR.irType === ProtoIR.RESPONSE_TYPE) &&
                 sawFirstUpdate) ||
                !currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS)) {
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            } else {
              currentPIR.pushEvent(event);
              sawFirstUpdate = true;
            }
            break;

          case INPUT_TYPE.PINCH_END:
            if (currentPIR) {
              currentPIR.pushEvent(event);
            } else {
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
            }
            currentPIR = undefined;
            break;
        }
      });
      return protoIRs;
    },

    // Flings are defined by 3 types of events: FlingStart, FlingCancel, and the
    // renderer fling event. Flings do not begin with a Response. Flings end
    // either at the beginning of a FlingCancel, or at the end of the renderer
    // fling event.
    //
    // AAAAAAAAAAAAAAAAAAAAAAAAAA
    // SSS
    //     RRRRRRRRRRRRRRRRRRRRRR
    //
    //
    // AAAAAAAAAAA
    // SSS        CCC
    //
    handleFlingEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var flingEvents = this.getSortedInputEvents(FLING_TYPE_NAMES);

      function isRendererFling(event) {
        return event.title === RENDERER_FLING_TITLE;
      }
      var browserHelper = this.modelHelper.browserHelper;
      flingEvents.push.apply(flingEvents,
          browserHelper.getAllAsyncSlicesMatching(isRendererFling));

      flingEvents.forEach(function(event) {
        if (event.title === RENDERER_FLING_TITLE) {
          if (currentPIR) {
            currentPIR.pushEvent(event);
          } else {
            currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
            currentPIR.pushEvent(event);
            protoIRs.push(currentPIR);
          }
          return;
        }

        switch (event.typeName) {
          case INPUT_TYPE.FLING_START:
            if (currentPIR) {
              console.error('Another FlingStart? File a bug with this trace!');
              currentPIR.pushEvent(event);
            } else {
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              // Set end to an invalid value so that it can be noticed and fixed
              // later.
              currentPIR.end = 0;
              protoIRs.push(currentPIR);
            }
            break;

          case INPUT_TYPE.FLING_CANCEL:
            if (currentPIR) {
              currentPIR.pushEvent(event);
              // FlingCancel events start when TouchStart events start, which is
              // typically when a Response starts. FlingCancel events end when
              // chrome acknowledges them, not when they update the screen. So
              // there might be one more frame during the FlingCancel, after
              // this Animation ends. That won't affect the scoring algorithms,
              // and it will make the IRs look more correct if they don't
              // overlap unnecessarily.
              currentPIR.end = event.start;
              currentPIR = undefined;
            } else {
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
            }
            break;
        }
      });
      // If there was neither a FLING_CANCEL nor a renderer fling after the
      // FLING_START, then assume that it ends at the end of the model, so set
      // the end of currentPIR to the end of the model.
      if (currentPIR && !currentPIR.end)
        currentPIR.end = this.model.bounds.max;
      return protoIRs;
    },

    // The TouchStart and the first TouchMove comprise a Response, then the
    // rest of the TouchMoves comprise an Animation.
    //
    // RRRRRRRAAAAAAAAAAAAAAAAAAAA
    // SSS MMM MMM MMM MMM MMM EEE
    //
    // If there are no TouchMove events in between a TouchStart and a TouchEnd,
    // then it's just a Response.
    //
    // RRRRRRR
    // SSS EEE
    //
    handleTouchEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var sawFirstMove = false;
      this.getSortedInputEvents(TOUCH_TYPE_NAMES).forEach(function(event) {
        switch (event.typeName) {
          case INPUT_TYPE.TOUCH_START:
            if (currentPIR) {
              // NB: currentPIR will probably be merged with something from
              // handlePinchEvents(). Multiple TouchStart events without an
              // intervening TouchEnd logically implies that multiple fingers
              // are on the screen, so this is probably a pinch gesture.
              currentPIR.pushEvent(event);
            } else {
              currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
              sawFirstMove = false;
            }
            break;

          case INPUT_TYPE.TOUCH_MOVE:
            if (!currentPIR) {
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
              break;
            }

            // Like Scrolls and Pinches, the Response is defined to be the
            // TouchStart plus the first TouchMove, then the rest of the
            // TouchMoves constitute an Animation.
            if ((sawFirstMove &&
                (currentPIR.irType === ProtoIR.RESPONSE_TYPE)) ||
                !currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS)) {
              // If there's already a touchmove in the currentPIR or it's not
              // near event, then finish it and start a new animation.
              var prevEnd = currentPIR.end;
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              // It's possible for there to be a gap between TouchMoves, but
              // that doesn't mean that there should be an Idle IR there.
              currentPIR.start = prevEnd;
              protoIRs.push(currentPIR);
            } else {
              currentPIR.pushEvent(event);
              sawFirstMove = true;
            }
            break;

          case INPUT_TYPE.TOUCH_END:
            if (!currentPIR) {
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
              break;
            }
            if (currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS)) {
              currentPIR.pushEvent(event);
            } else {
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
            }
            currentPIR = undefined;
            break;
        }
      });
      return protoIRs;
    },

    // The first ScrollBegin and the first ScrollUpdate comprise a Response,
    // then the rest comprise an Animation.
    //
    // RRRRRRRAAAAAAAAAAAAAAAAAAAA
    // BBB UUU UUU UUU UUU UUU EEE
    //
    handleScrollEvents: function() {
      var protoIRs = [];
      var currentPIR = undefined;
      var sawFirstUpdate = false;
      this.getSortedInputEvents(SCROLL_TYPE_NAMES).forEach(function(event) {
        switch (event.typeName) {
          case INPUT_TYPE.SCROLL_BEGIN:
            // Always begin a new PIR even if there already is one, unlike
            // PinchBegin.
            currentPIR = new ProtoIR(ProtoIR.RESPONSE_TYPE);
            currentPIR.pushEvent(event);
            protoIRs.push(currentPIR);
            sawFirstUpdate = false;
            break;

          case INPUT_TYPE.SCROLL_UPDATE:
            if (currentPIR) {
              if (currentPIR.isNear(event, INPUT_MERGE_THRESHOLD_MS) &&
                  ((currentPIR.irType === ProtoIR.ANIMATION_TYPE) ||
                  !sawFirstUpdate)) {
                currentPIR.pushEvent(event);
                sawFirstUpdate = true;
              } else {
                currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
                currentPIR.pushEvent(event);
                protoIRs.push(currentPIR);
              }
            } else {
              // ScrollUpdate without ScrollBegin.
              currentPIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
              currentPIR.pushEvent(event);
              protoIRs.push(currentPIR);
            }
            break;

          case INPUT_TYPE.SCROLL_END:
            if (!currentPIR) {
              console.error('ScrollEnd without ScrollUpdate? ' +
                            'File a bug with this trace!');
              var pir = new ProtoIR(ProtoIR.IGNORED_TYPE);
              pir.pushEvent(event);
              protoIRs.push(pir);
              break;
            }
            currentPIR.pushEvent(event);
            break;
        }
      });
      return protoIRs;
    },

    // CSS Animations are merged into Animations when they intersect.
    handleCSSAnimations: function() {
      var animationEvents = this.modelHelper.browserHelper.
          getAllAsyncSlicesMatching(function(event) {
            return event.title === CSS_ANIMATION_TITLE;
      });

      var animationRanges = [];
      animationEvents.forEach(function(event) {
        animationRanges.push({
          min: event.start,
          max: event.end,
          event: event
        });
      });

      function merge(ranges) {
        var protoIR = new ProtoIR(ProtoIR.ANIMATION_TYPE);
        ranges.forEach(function(range) {
          protoIR.pushEvent(range.event);
        });
        return protoIR;
      }

      return tr.b.mergeRanges(animationRanges,
                              ANIMATION_MERGE_THRESHOLD_MS,
                              merge);
    },

    postProcessProtoIRs: function(protoIRs) {
      // protoIRs is input only. Returns a modified set of ProtoIRs.
      // The order is important.
      protoIRs = this.mergeIntersectingResponses(protoIRs);
      protoIRs = this.mergeIntersectingAnimations(protoIRs);
      protoIRs = this.fixResponseAnimationStarts(protoIRs);
      return protoIRs;
    },

    // TouchStarts happen at the same time as ScrollBegins.
    // It's easier to let multiple handlers create multiple overlapping
    // Responses and then merge them, rather than make the handlers aware of the
    // other handlers' PIRs.
    //
    // For example:
    // RR
    //  RRR  -> RRRRR
    //    RR
    //
    // protoIRs is input only.
    // Returns a modified set of ProtoIRs.
    mergeIntersectingResponses: function(protoIRs) {
      var newPIRs = [];
      while (protoIRs.length) {
        var pir = protoIRs.shift();
        newPIRs.push(pir);

        // Only consider Responses for now.
        if (pir.irType !== ProtoIR.RESPONSE_TYPE)
          continue;

        for (var i = 0; i < protoIRs.length; ++i) {
          var otherPIR = protoIRs[i];

          if (otherPIR.irType !== pir.irType)
            continue;

          if (!otherPIR.intersects(pir))
            continue;

          // Don't merge together Responses of the same type.
          // If handleTouchEvents wanted two of its Responses to be merged, then
          // it would have made them that way to begin with.
          var typeNames = pir.associatedEvents.map(function(event) {
            return event.typeName;
          });
          if (otherPIR.containsTypeNames(typeNames))
            continue;

          pir.merge(otherPIR);
          protoIRs.splice(i, 1);
          // Don't skip the next otherPIR!
          --i;
        }
      }
      return newPIRs;
    },

    // An animation is simply an expectation of 60fps between start and end.
    // If two animations overlap, then merge them.
    //
    // For example:
    // AA
    //  AAA  -> AAAAA
    //    AA
    //
    // protoIRs is input only.
    // Returns a modified set of ProtoIRs.
    mergeIntersectingAnimations: function(protoIRs) {
      var newPIRs = [];
      while (protoIRs.length) {
        var pir = protoIRs.shift();
        newPIRs.push(pir);

        // Only consider Animations for now.
        if (pir.irType !== ProtoIR.ANIMATION_TYPE)
          continue;

        var isCSS = pir.containsSliceTitle(CSS_ANIMATION_TITLE);
        var isFling = pir.containsTypeNames([INPUT_TYPE.FLING_START]);

        for (var i = 0; i < protoIRs.length; ++i) {
          var otherPIR = protoIRs[i];

          if (otherPIR.irType !== pir.irType)
            continue;

          // Don't merge CSS Animations with any other types.
          if (isCSS != otherPIR.containsSliceTitle(CSS_ANIMATION_TITLE))
            continue;

          if (!otherPIR.intersects(pir))
            continue;

          // Don't merge Fling Animations with any other types.
          if (isFling != otherPIR.containsTypeNames([INPUT_TYPE.FLING_START]))
            continue;

          pir.merge(otherPIR);
          protoIRs.splice(i, 1);
          // Don't skip the next otherPIR!
          --i;
        }
      }
      return newPIRs;
    },

    // The ends of responses frequently overlap the starts of animations.
    // Fix the animations to reflect the fact that the user can only start to
    // expect 60fps after the response.
    //
    // For example:
    // RRR   -> RRRAA
    //  AAAA
    //
    // protoIRs is input only.
    // Returns a modified set of ProtoIRs.
    fixResponseAnimationStarts: function(protoIRs) {
      protoIRs.forEach(function(apir) {
        // Only consider animations for now.
        if (apir.irType !== ProtoIR.ANIMATION_TYPE)
          return;

        protoIRs.forEach(function(rpir) {
          // Only consider responses for now.
          if (rpir.irType !== ProtoIR.RESPONSE_TYPE)
            return;

          // Only consider responses that end during the animation.
          if (!apir.containsTimestampInclusive(rpir.end))
            return;

          // Ignore Responses that are entirely contained by the animation.
          if (apir.containsTimestampInclusive(rpir.start))
            return;

          // Move the animation start to the response end.
          apir.start = rpir.end;
        });
      });
      return protoIRs;
    },

    // Check that none of the handlers accidentally ignored an input event.
    checkAllInputEventsHandled: function(protoIRs) {
      var handledEvents = [];
      protoIRs.forEach(function(protoIR) {
        protoIR.associatedEvents.forEach(function(event) {
          if (handledEvents.indexOf(event) >= 0) {
            console.error('double-handled event', event.typeName,
                parseInt(event.start), parseInt(event.end), protoIR);
            return;
          }
          handledEvents.push(event);
        });
      });

      this.getSortedInputEvents(ALL_HANDLED_TYPE_NAMES).forEach(
          function(event) {
        if (handledEvents.indexOf(event) < 0) {
          console.error('UNHANDLED INPUT EVENT!',
              event.typeName, parseInt(event.start), parseInt(event.end));
        }
      });
    }
  };

  function createCustomizeModelLinesFromModel(model) {
    var modelLines = [];
    modelLines.push('      audits.addEvent(model.browserMain,');
    modelLines.push('          {title: \'model start\', start: 0, end: 1});');

    var typeNames = {};
    for (var typeName in tr.e.cc.INPUT_EVENT_TYPE_NAMES) {
      typeNames[tr.e.cc.INPUT_EVENT_TYPE_NAMES[typeName]] = typeName;
    }

    var modelEvents = new tr.model.EventSet();
    model.interaction_records.forEach(function(ir, index) {
      modelEvents.addEventSet(ir.sourceEvents);
    });
    modelEvents = modelEvents.toArray();
    modelEvents.sort(compareEvents);

    modelEvents.forEach(function(event) {
      var startAndEnd = 'start: ' + parseInt(event.start) + ', ' +
                        'end: ' + parseInt(event.end) + '});';
      if (event instanceof tr.e.cc.InputLatencyAsyncSlice) {
        modelLines.push('      audits.addInputEvent(model, INPUT_TYPE.' +
                        typeNames[event.typeName] + ',');
      } else if (event.title === 'RenderFrameImpl::didCommitProvisionalLoad') {
        modelLines.push('      audits.addCommitLoadEvent(model,');
      } else if (event.title ===
                 'InputHandlerProxy::HandleGestureFling::started') {
        modelLines.push('      audits.addFlingAnimationEvent(model,');
      } else if (event.title === tr.e.audits.IMPL_RENDERING_STATS) {
        modelLines.push('      audits.addFrameEvent(model,');
      } else if (event.title === CSS_ANIMATION_TITLE) {
        modelLines.push('      audits.addEvent(model.rendererMain, {');
        modelLines.push('        title: \'Animation\', ' + startAndEnd);
        return;
      } else {
        throw ('You must extend createCustomizeModelLinesFromModel()' +
               'to support this event:\n' + event.title + '\n');
      }
      modelLines.push('          {' + startAndEnd);
    });

    modelLines.push('      audits.addEvent(model.browserMain,');
    modelLines.push('          {' +
                    'title: \'model end\', ' +
                    'start: ' + (parseInt(model.bounds.max) - 1) + ', ' +
                    'end: ' + parseInt(model.bounds.max) + '});');
    return modelLines;
  }

  function createExpectedIRLinesFromModel(model) {
    var expectedLines = [];
    var irCount = model.interaction_records.length;
    model.interaction_records.forEach(function(ir, index) {
      var irString = '      {';
      irString += 'title: \'' + ir.title + '\', ';
      irString += 'start: ' + parseInt(ir.start) + ', ';
      irString += 'end: ' + parseInt(ir.end) + ', ';
      irString += 'eventCount: ' + ir.sourceEvents.length;
      irString += '}';
      if (index < (irCount - 1))
        irString += ',';
      expectedLines.push(irString);
    });
    return expectedLines;
  }

  function createIRFinderTestCaseStringFromModel(model) {
    var filename = window.location.hash.substr(1);
    var testName = filename.substr(filename.lastIndexOf('/') + 1);
    testName = testName.substr(0, testName.indexOf('.'));

    // createCustomizeModelLinesFromModel() throws an error if there's an
    // unsupported event.
    try {
      var testLines = [];
      testLines.push('  /*');
      testLines.push('    This test was generated from');
      testLines.push('    ' + filename + '');
      testLines.push('   */');
      testLines.push('  test(\'' + testName + '\', function() {');
      testLines.push('    var verifier = new IRVerifier();');
      testLines.push('    verifier.customizeModelCallback = function(model) {');
      testLines.push.apply(testLines,
          createCustomizeModelLinesFromModel(model));
      testLines.push('    };');
      testLines.push('    verifier.expectedIRs = [');
      testLines.push.apply(testLines, createExpectedIRLinesFromModel(model));
      testLines.push('    ];');
      testLines.push('    verifier.verify();');
      testLines.push('  });');
      return testLines.join('\n');
    } catch (error) {
      return error;
    }
  }

  return {
    RAILIRFinder: RAILIRFinder,
    createIRFinderTestCaseStringFromModel: createIRFinderTestCaseStringFromModel
  };
});
</script>