third_party/WebKit/Source/core/html/track/CueTimeline.cpp

// 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.

#include "core/html/track/CueTimeline.h"

#include "core/events/Event.h"
#include "core/html/HTMLMediaElement.h"
#include "core/html/HTMLTrackElement.h"
#include "core/html/track/LoadableTextTrack.h"
#include "core/html/track/TextTrack.h"
#include "core/html/track/TextTrackCue.h"
#include "core/html/track/TextTrackCueList.h"
#include "wtf/NonCopyingSort.h"

namespace blink {

CueTimeline::CueTimeline(HTMLMediaElement& mediaElement)
    : m_mediaElement(&mediaElement), m_lastUpdateTime(-1), m_ignoreUpdate(0) {}

void CueTimeline::addCues(TextTrack* track, const TextTrackCueList* cues) {
  DCHECK_NE(track->mode(), TextTrack::disabledKeyword());
  for (size_t i = 0; i < cues->length(); ++i)
    addCueInternal(cues->anonymousIndexedGetter(i));
  updateActiveCues(mediaElement().currentTime());
}

void CueTimeline::addCue(TextTrack* track, TextTrackCue* cue) {
  DCHECK_NE(track->mode(), TextTrack::disabledKeyword());
  addCueInternal(cue);
  updateActiveCues(mediaElement().currentTime());
}

void CueTimeline::addCueInternal(TextTrackCue* cue) {
  // Negative duration cues need be treated in the interval tree as
  // zero-length cues.
  double endTime = std::max(cue->startTime(), cue->endTime());

  CueInterval interval =
      m_cueTree.createInterval(cue->startTime(), endTime, cue);
  if (!m_cueTree.contains(interval))
    m_cueTree.add(interval);
}

void CueTimeline::removeCues(TextTrack*, const TextTrackCueList* cues) {
  for (size_t i = 0; i < cues->length(); ++i)
    removeCueInternal(cues->anonymousIndexedGetter(i));
  updateActiveCues(mediaElement().currentTime());
}

void CueTimeline::removeCue(TextTrack*, TextTrackCue* cue) {
  removeCueInternal(cue);
  updateActiveCues(mediaElement().currentTime());
}

void CueTimeline::removeCueInternal(TextTrackCue* cue) {
  // Negative duration cues need to be treated in the interval tree as
  // zero-length cues.
  double endTime = std::max(cue->startTime(), cue->endTime());

  CueInterval interval =
      m_cueTree.createInterval(cue->startTime(), endTime, cue);
  m_cueTree.remove(interval);

  size_t index = m_currentlyActiveCues.find(interval);
  if (index != kNotFound) {
    DCHECK(cue->isActive());
    m_currentlyActiveCues.remove(index);
    cue->setIsActive(false);
    // Since the cue will be removed from the media element and likely the
    // TextTrack might also be destructed, notifying the region of the cue
    // removal shouldn't be done.
    cue->removeDisplayTree(TextTrackCue::DontNotifyRegion);
  }
}

void CueTimeline::hideCues(TextTrack*, const TextTrackCueList* cues) {
  for (size_t i = 0; i < cues->length(); ++i)
    cues->anonymousIndexedGetter(i)->removeDisplayTree();
}

static bool trackIndexCompare(TextTrack* a, TextTrack* b) {
  return a->trackIndex() - b->trackIndex() < 0;
}

static bool eventTimeCueCompare(const std::pair<double, TextTrackCue*>& a,
                                const std::pair<double, TextTrackCue*>& b) {
  // 12 - Sort the tasks in events in ascending time order (tasks with earlier
  // times first).
  if (a.first != b.first)
    return a.first - b.first < 0;

  // If the cues belong to different text tracks, it doesn't make sense to
  // compare the two tracks by the relative cue order, so return the relative
  // track order.
  if (a.second->track() != b.second->track())
    return trackIndexCompare(a.second->track(), b.second->track());

  // 12 - Further sort tasks in events that have the same time by the
  // relative text track cue order of the text track cues associated
  // with these tasks.
  return a.second->cueIndex() < b.second->cueIndex();
}

static Event* createEventWithTarget(const AtomicString& eventName,
                                    EventTarget* eventTarget) {
  Event* event = Event::create(eventName);
  event->setTarget(eventTarget);
  return event;
}

void CueTimeline::updateActiveCues(double movieTime) {
  // 4.8.10.8 Playing the media resource

  //  If the current playback position changes while the steps are running,
  //  then the user agent must wait for the steps to complete, and then must
  //  immediately rerun the steps.
  if (ignoreUpdateRequests())
    return;

  HTMLMediaElement& mediaElement = this->mediaElement();

  // Don't run the "time marches on" algorithm if the document has been
  // detached. This primarily guards against dispatch of events w/
  // HTMLTrackElement targets.
  if (mediaElement.document().isDetached())
    return;

  // https://html.spec.whatwg.org/#time-marches-on

  // 1 - Let current cues be a list of cues, initialized to contain all the
  // cues of all the hidden, showing, or showing by default text tracks of the
  // media element (not the disabled ones) whose start times are less than or
  // equal to the current playback position and whose end times are greater
  // than the current playback position.
  CueList currentCues;

  // The user agent must synchronously unset [the text track cue active] flag
  // whenever ... the media element's readyState is changed back to
  // kHaveNothing.
  if (mediaElement.getReadyState() != HTMLMediaElement::kHaveNothing &&
      mediaElement.webMediaPlayer())
    currentCues =
        m_cueTree.allOverlaps(m_cueTree.createInterval(movieTime, movieTime));

  CueList previousCues;
  CueList missedCues;

  // 2 - Let other cues be a list of cues, initialized to contain all the cues
  // of hidden, showing, and showing by default text tracks of the media
  // element that are not present in current cues.
  previousCues = m_currentlyActiveCues;

  // 3 - Let last time be the current playback position at the time this
  // algorithm was last run for this media element, if this is not the first
  // time it has run.
  double lastTime = m_lastUpdateTime;
  double lastSeekTime = mediaElement.lastSeekTime();

  // 4 - If the current playback position has, since the last time this
  // algorithm was run, only changed through its usual monotonic increase
  // during normal playback, then let missed cues be the list of cues in other
  // cues whose start times are greater than or equal to last time and whose
  // end times are less than or equal to the current playback position.
  // Otherwise, let missed cues be an empty list.
  if (lastTime >= 0 && lastSeekTime < movieTime) {
    CueList potentiallySkippedCues =
        m_cueTree.allOverlaps(m_cueTree.createInterval(lastTime, movieTime));

    for (CueInterval cue : potentiallySkippedCues) {
      // Consider cues that may have been missed since the last seek time.
      if (cue.low() > std::max(lastSeekTime, lastTime) &&
          cue.high() < movieTime)
        missedCues.append(cue);
    }
  }

  m_lastUpdateTime = movieTime;

  // 5 - If the time was reached through the usual monotonic increase of the
  // current playback position during normal playback, and if the user agent
  // has not fired a timeupdate event at the element in the past 15 to 250ms
  // and is not still running event handlers for such an event, then the user
  // agent must queue a task to fire a simple event named timeupdate at the
  // element. (In the other cases, such as explicit seeks, relevant events get
  // fired as part of the overall process of changing the current playback
  // position.)
  if (!mediaElement.seeking() && lastSeekTime < lastTime)
    mediaElement.scheduleTimeupdateEvent(true);

  // Explicitly cache vector sizes, as their content is constant from here.
  size_t currentCuesSize = currentCues.size();
  size_t missedCuesSize = missedCues.size();
  size_t previousCuesSize = previousCues.size();

  // 6 - If all of the cues in current cues have their text track cue active
  // flag set, none of the cues in other cues have their text track cue active
  // flag set, and missed cues is empty, then abort these steps.
  bool activeSetChanged = missedCuesSize;

  for (size_t i = 0; !activeSetChanged && i < previousCuesSize; ++i) {
    if (!currentCues.contains(previousCues[i]) &&
        previousCues[i].data()->isActive())
      activeSetChanged = true;
  }

  for (CueInterval currentCue : currentCues) {
    // Notify any cues that are already active of the current time to mark
    // past and future nodes. Any inactive cues have an empty display state;
    // they will be notified of the current time when the display state is
    // updated.
    if (currentCue.data()->isActive())
      currentCue.data()->updatePastAndFutureNodes(movieTime);
    else
      activeSetChanged = true;
  }

  if (!activeSetChanged)
    return;

  // 7 - If the time was reached through the usual monotonic increase of the
  // current playback position during normal playback, and there are cues in
  // other cues that have their text track cue pause-on-exi flag set and that
  // either have their text track cue active flag set or are also in missed
  // cues, then immediately pause the media element.
  for (size_t i = 0; !mediaElement.paused() && i < previousCuesSize; ++i) {
    if (previousCues[i].data()->pauseOnExit() &&
        previousCues[i].data()->isActive() &&
        !currentCues.contains(previousCues[i]))
      mediaElement.pause();
  }

  for (size_t i = 0; !mediaElement.paused() && i < missedCuesSize; ++i) {
    if (missedCues[i].data()->pauseOnExit())
      mediaElement.pause();
  }

  // 8 - Let events be a list of tasks, initially empty. Each task in this
  // list will be associated with a text track, a text track cue, and a time,
  // which are used to sort the list before the tasks are queued.
  HeapVector<std::pair<double, Member<TextTrackCue>>> eventTasks;

  // 8 - Let affected tracks be a list of text tracks, initially empty.
  HeapVector<Member<TextTrack>> affectedTracks;

  for (size_t i = 0; i < missedCuesSize; ++i) {
    // 9 - For each text track cue in missed cues, prepare an event named enter
    // for the TextTrackCue object with the text track cue start time.
    eventTasks.append(std::make_pair(missedCues[i].data()->startTime(),
                                     missedCues[i].data()));

    // 10 - For each text track [...] in missed cues, prepare an event
    // named exit for the TextTrackCue object with the  with the later of
    // the text track cue end time and the text track cue start time.

    // Note: An explicit task is added only if the cue is NOT a zero or
    // negative length cue. Otherwise, the need for an exit event is
    // checked when these tasks are actually queued below. This doesn't
    // affect sorting events before dispatch either, because the exit
    // event has the same time as the enter event.
    if (missedCues[i].data()->startTime() < missedCues[i].data()->endTime())
      eventTasks.append(std::make_pair(missedCues[i].data()->endTime(),
                                       missedCues[i].data()));
  }

  for (size_t i = 0; i < previousCuesSize; ++i) {
    // 10 - For each text track cue in other cues that has its text
    // track cue active flag set prepare an event named exit for the
    // TextTrackCue object with the text track cue end time.
    if (!currentCues.contains(previousCues[i]))
      eventTasks.append(std::make_pair(previousCues[i].data()->endTime(),
                                       previousCues[i].data()));
  }

  for (size_t i = 0; i < currentCuesSize; ++i) {
    // 11 - For each text track cue in current cues that does not have its
    // text track cue active flag set, prepare an event named enter for the
    // TextTrackCue object with the text track cue start time.
    if (!previousCues.contains(currentCues[i]))
      eventTasks.append(std::make_pair(currentCues[i].data()->startTime(),
                                       currentCues[i].data()));
  }

  // 12 - Sort the tasks in events in ascending time order (tasks with earlier
  // times first).
  nonCopyingSort(eventTasks.begin(), eventTasks.end(), eventTimeCueCompare);

  for (size_t i = 0; i < eventTasks.size(); ++i) {
    if (!affectedTracks.contains(eventTasks[i].second->track()))
      affectedTracks.append(eventTasks[i].second->track());

    // 13 - Queue each task in events, in list order.

    // Each event in eventTasks may be either an enterEvent or an exitEvent,
    // depending on the time that is associated with the event. This
    // correctly identifies the type of the event, if the startTime is
    // less than the endTime in the cue.
    if (eventTasks[i].second->startTime() >= eventTasks[i].second->endTime()) {
      mediaElement.scheduleEvent(createEventWithTarget(
          EventTypeNames::enter, eventTasks[i].second.get()));
      mediaElement.scheduleEvent(createEventWithTarget(
          EventTypeNames::exit, eventTasks[i].second.get()));
    } else {
      bool isEnterEvent =
          eventTasks[i].first == eventTasks[i].second->startTime();
      AtomicString eventName =
          isEnterEvent ? EventTypeNames::enter : EventTypeNames::exit;
      mediaElement.scheduleEvent(
          createEventWithTarget(eventName, eventTasks[i].second.get()));
    }
  }

  // 14 - Sort affected tracks in the same order as the text tracks appear in
  // the media element's list of text tracks, and remove duplicates.
  nonCopyingSort(affectedTracks.begin(), affectedTracks.end(),
                 trackIndexCompare);

  // 15 - For each text track in affected tracks, in the list order, queue a
  // task to fire a simple event named cuechange at the TextTrack object, and,
  // ...
  for (size_t i = 0; i < affectedTracks.size(); ++i) {
    mediaElement.scheduleEvent(createEventWithTarget(EventTypeNames::cuechange,
                                                     affectedTracks[i].get()));

    // ... if the text track has a corresponding track element, to then fire a
    // simple event named cuechange at the track element as well.
    if (affectedTracks[i]->trackType() == TextTrack::TrackElement) {
      HTMLTrackElement* trackElement =
          static_cast<LoadableTextTrack*>(affectedTracks[i].get())
              ->trackElement();
      DCHECK(trackElement);
      mediaElement.scheduleEvent(
          createEventWithTarget(EventTypeNames::cuechange, trackElement));
    }
  }

  // 16 - Set the text track cue active flag of all the cues in the current
  // cues, and unset the text track cue active flag of all the cues in the
  // other cues.
  for (size_t i = 0; i < currentCuesSize; ++i)
    currentCues[i].data()->setIsActive(true);

  for (size_t i = 0; i < previousCuesSize; ++i) {
    if (!currentCues.contains(previousCues[i])) {
      TextTrackCue* cue = previousCues[i].data();
      cue->setIsActive(false);
      cue->removeDisplayTree();
    }
  }

  // Update the current active cues.
  m_currentlyActiveCues = currentCues;
  mediaElement.updateTextTrackDisplay();
}

void CueTimeline::beginIgnoringUpdateRequests() {
  ++m_ignoreUpdate;
}

void CueTimeline::endIgnoringUpdateRequests() {
  DCHECK(m_ignoreUpdate);
  --m_ignoreUpdate;
  if (!m_ignoreUpdate)
    updateActiveCues(mediaElement().currentTime());
}

DEFINE_TRACE(CueTimeline) {
  visitor->trace(m_mediaElement);
}

}  // namespace blink