TimeRanges* MediaSource::seekable() const
{
    // Implements MediaSource algorithm for HTMLMediaElement.seekable.
    // https://dvcs.w3.org/hg/html-media/raw-file/default/media-source/media-source.html#htmlmediaelement-extensions

    double sourceDuration = duration();
    // If duration equals NaN: Return an empty TimeRanges object.
    if (std::isnan(sourceDuration))
        return TimeRanges::create();

    // If duration equals positive Infinity:
    if (sourceDuration == std::numeric_limits<double>::infinity()) {
        TimeRanges* buffered = m_attachedElement->buffered();

        // 1. If the HTMLMediaElement.buffered attribute returns an empty TimeRanges object, then
        // return an empty TimeRanges object and abort these steps.
        if (buffered->length() == 0)
            return TimeRanges::create();

        // 2. Return a single range with a start time of 0 and an end time equal to the highest end
        // time reported by the HTMLMediaElement.buffered attribute.
        return TimeRanges::create(0, buffered->end(buffered->length() - 1, ASSERT_NO_EXCEPTION));
    }

    // 3. Otherwise: Return a single range with a start time of 0 and an end time equal to duration.
    return TimeRanges::create(0, sourceDuration);
}

TimeRanges* TimeRanges::copy() const {
  TimeRanges* newSession = TimeRanges::create();

  unsigned size = m_ranges.size();
  for (unsigned i = 0; i < size; i++)
    newSession->add(m_ranges[i].m_start, m_ranges[i].m_end);

  return newSession;
}

TimeRanges* TimeRanges::create(const blink::WebTimeRanges& webRanges) {
  TimeRanges* ranges = TimeRanges::create();

  unsigned size = webRanges.size();
  for (unsigned i = 0; i < size; ++i)
    ranges->add(webRanges[i].start, webRanges[i].end);

  return ranges;
}

void TimeRanges::unionWith(const TimeRanges* other) {
  DCHECK(other);
  TimeRanges* unioned = copy();
  for (size_t index = 0; index < other->m_ranges.size(); ++index) {
    const Range& range = other->m_ranges[index];
    unioned->add(range.m_start, range.m_end);
  }

  m_ranges.swap(unioned->m_ranges);
}

static std::string ToString(const TimeRanges& ranges)
{
    std::stringstream ss;
    ss << "{";
    for (unsigned i = 0; i < ranges.length(); ++i)
        ss << " [" << ranges.start(i, IGNORE_EXCEPTION) << "," << ranges.end(i, IGNORE_EXCEPTION) << ")";
    ss << " }";

    return ss.str();
}

static std::string ToString(const TimeRanges& ranges)
{
    std::stringstream ss;
    ss << "{";
    for (unsigned i = 0; i < ranges.length(); ++i)
        ss << " [" << ranges.start(i).releaseReturnValue() << "," << ranges.end(i).releaseReturnValue() << ")";
    ss << " }";

    return ss.str();
}

PassRefPtr<TimeRanges> MediaSource::buffered() const
{
    // Implements MediaSource algorithm for HTMLMediaElement.buffered.
    // https://dvcs.w3.org/hg/html-media/raw-file/default/media-source/media-source.html#htmlmediaelement-extensions
    Vector<RefPtr<TimeRanges> > ranges(m_activeSourceBuffers->length());
    for (size_t i = 0; i < m_activeSourceBuffers->length(); ++i)
        ranges[i] = m_activeSourceBuffers->item(i)->buffered(ASSERT_NO_EXCEPTION);

    // 1. If activeSourceBuffers.length equals 0 then return an empty TimeRanges object and abort these steps.
    if (ranges.isEmpty())
        return TimeRanges::create();

    // 2. Let active ranges be the ranges returned by buffered for each SourceBuffer object in activeSourceBuffers.
    // 3. Let highest end time be the largest range end time in the active ranges.
    double highestEndTime = -1;
    for (size_t i = 0; i < ranges.size(); ++i) {
        unsigned length = ranges[i]->length();
        if (length)
            highestEndTime = std::max(highestEndTime, ranges[i]->end(length - 1, ASSERT_NO_EXCEPTION));
    }

    // Return an empty range if all ranges are empty.
    if (highestEndTime < 0)
        return TimeRanges::create();

    // 4. Let intersection ranges equal a TimeRange object containing a single range from 0 to highest end time.
    RefPtr<TimeRanges> intersectionRanges = TimeRanges::create(0, highestEndTime);

    // 5. For each SourceBuffer object in activeSourceBuffers run the following steps:
    bool ended = readyState() == endedKeyword();
    for (size_t i = 0; i < ranges.size(); ++i) {
        // 5.1 Let source ranges equal the ranges returned by the buffered attribute on the current SourceBuffer.
        TimeRanges* sourceRanges = ranges[i].get();

        // 5.2 If readyState is "ended", then set the end time on the last range in source ranges to highest end time.
        if (ended && sourceRanges->length())
            sourceRanges->add(sourceRanges->start(sourceRanges->length() - 1, ASSERT_NO_EXCEPTION), highestEndTime);

        // 5.3 Let new intersection ranges equal the the intersection between the intersection ranges and the source ranges.
        // 5.4 Replace the ranges in intersection ranges with the new intersection ranges.
        intersectionRanges->intersectWith(sourceRanges);
    }

    return intersectionRanges.release();
}

/**
 * Returns true if aValue is inside a range of aRanges, and put the range
 * index in aIntervalIndex if it is not null.
 * If aValue is not inside a range, false is returned, and aIntervalIndex, if
 * not null, is set to the index of the range which ends immediately before aValue
 * (and can be -1 if aValue is before aRanges.Start(0)).
 */
static bool
IsInRanges(TimeRanges& aRanges, double aValue, int32_t& aIntervalIndex)
{
  uint32_t length;
  aRanges.GetLength(&length);
  for (uint32_t i = 0; i < length; i++) {
    double start, end;
    aRanges.Start(i, &start);
    if (start > aValue) {
      aIntervalIndex = i - 1;
      return false;
    }
    aRanges.End(i, &end);
    if (aValue <= end) {
      aIntervalIndex = i;
      return true;
    }
  }
  aIntervalIndex = length - 1;
  return false;
}

void TimeRanges::invert() {
  TimeRanges* inverted = TimeRanges::create();
  double posInf = std::numeric_limits<double>::infinity();
  double negInf = -std::numeric_limits<double>::infinity();

  if (!m_ranges.size()) {
    inverted->add(negInf, posInf);
  } else {
    double start = m_ranges.first().m_start;
    if (start != negInf)
      inverted->add(negInf, start);

    for (size_t index = 0; index + 1 < m_ranges.size(); ++index)
      inverted->add(m_ranges[index].m_end, m_ranges[index + 1].m_start);

    double end = m_ranges.last().m_end;
    if (end != posInf)
      inverted->add(end, posInf);
  }

  m_ranges.swap(inverted->m_ranges);
}

TimeRanges* MediaSource::seekable() const {
  // Implements MediaSource algorithm for HTMLMediaElement.seekable.
  // http://w3c.github.io/media-source/#htmlmediaelement-extensions

  double sourceDuration = duration();
  // If duration equals NaN: Return an empty TimeRanges object.
  if (std::isnan(sourceDuration))
    return TimeRanges::create();

  // If duration equals positive Infinity:
  if (sourceDuration == std::numeric_limits<double>::infinity()) {
    TimeRanges* buffered = m_attachedElement->buffered();

    // 1. If live seekable range is not empty:
    if (m_liveSeekableRange->length() != 0) {
      // 1.1. Let union ranges be the union of live seekable range and the
      //      HTMLMediaElement.buffered attribute.
      // 1.2. Return a single range with a start time equal to the
      //      earliest start time in union ranges and an end time equal to
      //      the highest end time in union ranges and abort these steps.
      if (buffered->length() == 0) {
        return TimeRanges::create(
            m_liveSeekableRange->start(0, ASSERT_NO_EXCEPTION),
            m_liveSeekableRange->end(0, ASSERT_NO_EXCEPTION));
      }

      return TimeRanges::create(
          std::min(m_liveSeekableRange->start(0, ASSERT_NO_EXCEPTION),
                   buffered->start(0, ASSERT_NO_EXCEPTION)),
          std::max(m_liveSeekableRange->end(0, ASSERT_NO_EXCEPTION),
                   buffered->end(buffered->length() - 1, ASSERT_NO_EXCEPTION)));
    }
    // 2. If the HTMLMediaElement.buffered attribute returns an empty TimeRanges
    //    object, then return an empty TimeRanges object and abort these steps.
    if (buffered->length() == 0)
      return TimeRanges::create();

    // 3. Return a single range with a start time of 0 and an end time equal to
    //    the highest end time reported by the HTMLMediaElement.buffered
    //    attribute.
    return TimeRanges::create(
        0, buffered->end(buffered->length() - 1, ASSERT_NO_EXCEPTION));
  }

  // 3. Otherwise: Return a single range with a start time of 0 and an end time
  //    equal to duration.
  return TimeRanges::create(0, sourceDuration);
}

void
MediaSource::GetBuffered(TimeRanges* aBuffered)
{
  MOZ_ASSERT(aBuffered->Length() == 0);
  if (mActiveSourceBuffers->IsEmpty()) {
    return;
  }

  double highestEndTime = 0;

  nsTArray<nsRefPtr<TimeRanges>> activeRanges;
  for (uint32_t i = 0; i < mActiveSourceBuffers->Length(); ++i) {
    bool found;
    SourceBuffer* sourceBuffer = mActiveSourceBuffers->IndexedGetter(i, found);

    ErrorResult dummy;
    *activeRanges.AppendElement() = sourceBuffer->GetBuffered(dummy);

    highestEndTime = std::max(highestEndTime, activeRanges.LastElement()->GetEndTime());
  }

  TimeRanges* intersectionRanges = aBuffered;
  intersectionRanges->Add(0, highestEndTime);

  for (uint32_t i = 0; i < activeRanges.Length(); ++i) {
    TimeRanges* sourceRanges = activeRanges[i];

    if (mReadyState == MediaSourceReadyState::Ended) {
      // Set the end time on the last range to highestEndTime by adding a
      // new range spanning the current end time to highestEndTime, which
      // Normalize() will then merge with the old last range.
      sourceRanges->Add(sourceRanges->GetEndTime(), highestEndTime);
      sourceRanges->Normalize();
    }

    intersectionRanges->Intersection(sourceRanges);
  }

  MSE_DEBUG("MediaSource(%p)::GetBuffered ranges=%s", this, DumpTimeRanges(intersectionRanges).get());
}

nsresult
MediaSourceReader::GetBuffered(dom::TimeRanges* aBuffered)
{
  ReentrantMonitorAutoEnter mon(mDecoder->GetReentrantMonitor());
  MOZ_ASSERT(aBuffered->Length() == 0);
  if (mTrackBuffers.IsEmpty()) {
    return NS_OK;
  }

  double highestEndTime = 0;

  nsTArray<nsRefPtr<TimeRanges>> activeRanges;
  for (uint32_t i = 0; i < mTrackBuffers.Length(); ++i) {
    nsRefPtr<TimeRanges> r = new TimeRanges();
    mTrackBuffers[i]->Buffered(r);
    activeRanges.AppendElement(r);
    highestEndTime = std::max(highestEndTime, activeRanges.LastElement()->GetEndTime());
  }

  TimeRanges* intersectionRanges = aBuffered;
  intersectionRanges->Add(0, highestEndTime);

  for (uint32_t i = 0; i < activeRanges.Length(); ++i) {
    TimeRanges* sourceRanges = activeRanges[i];

    if (IsEnded()) {
      // Set the end time on the last range to highestEndTime by adding a
      // new range spanning the current end time to highestEndTime, which
      // Normalize() will then merge with the old last range.
      sourceRanges->Add(sourceRanges->GetEndTime(), highestEndTime);
      sourceRanges->Normalize();
    }

    intersectionRanges->Intersection(sourceRanges);
  }

  MSE_DEBUG("ranges=%s", DumpTimeRanges(intersectionRanges).get());
  return NS_OK;
}

nsresult MediaDecoder::Seek(double aTime)
{
  MOZ_ASSERT(NS_IsMainThread());
  ReentrantMonitorAutoEnter mon(GetReentrantMonitor());

  NS_ABORT_IF_FALSE(aTime >= 0.0, "Cannot seek to a negative value.");

  TimeRanges seekable;
  nsresult res;
  uint32_t length = 0;
  res = GetSeekable(&seekable);
  NS_ENSURE_SUCCESS(res, NS_OK);

  seekable.GetLength(&length);
  if (!length) {
    return NS_OK;
  }

  // If the position we want to seek to is not in a seekable range, we seek
  // to the closest position in the seekable ranges instead. If two positions
  // are equally close, we seek to the closest position from the currentTime.
  // See seeking spec, point 7 :
  // http://www.whatwg.org/specs/web-apps/current-work/multipage/the-video-element.html#seeking
  int32_t range = 0;
  if (!IsInRanges(seekable, aTime, range)) {
    if (range != -1) {
      // |range + 1| can't be negative, because the only possible negative value
      // for |range| is -1.
      if (uint32_t(range + 1) < length) {
        double leftBound, rightBound;
        res = seekable.End(range, &leftBound);
        NS_ENSURE_SUCCESS(res, NS_OK);
        res = seekable.Start(range + 1, &rightBound);
        NS_ENSURE_SUCCESS(res, NS_OK);
        double distanceLeft = Abs(leftBound - aTime);
        double distanceRight = Abs(rightBound - aTime);
        if (distanceLeft == distanceRight) {
          distanceLeft = Abs(leftBound - mCurrentTime);
          distanceRight = Abs(rightBound - mCurrentTime);
        } 
        aTime = (distanceLeft < distanceRight) ? leftBound : rightBound;
      } else {
        // Seek target is after the end last range in seekable data.
        // Clamp the seek target to the end of the last seekable range.
        res = seekable.End(length - 1, &aTime);
        NS_ENSURE_SUCCESS(res, NS_OK);
      }
    } else {
      // aTime is before the first range in |seekable|, the closest point we can
      // seek to is the start of the first range.
      seekable.Start(0, &aTime);
    }
  }

  mRequestedSeekTime = aTime;
  mCurrentTime = aTime;

  // If we are already in the seeking state, then setting mRequestedSeekTime
  // above will result in the new seek occurring when the current seek
  // completes.
  if (mPlayState != PLAY_STATE_SEEKING) {
    bool paused = false;
    if (mOwner) {
      paused = mOwner->GetPaused();
    }
    mNextState = paused ? PLAY_STATE_PAUSED : PLAY_STATE_PLAYING;
    PinForSeek();
    ChangeState(PLAY_STATE_SEEKING);
  }

  return ScheduleStateMachineThread();
}

void MediaControlsPainter::paintMediaSliderInternal(const LayoutObject& object, const PaintInfo& paintInfo, const IntRect& rect)
{
    const bool useNewUi = RuntimeEnabledFeatures::newMediaPlaybackUiEnabled();
    const HTMLMediaElement* mediaElement = toParentMediaElement(object);
    if (!mediaElement)
        return;

    const ComputedStyle& style = object.styleRef();
    GraphicsContext* context = paintInfo.context;

    // Paint the slider bar in the "no data buffered" state.
    Color sliderBackgroundColor;
    if (!useNewUi)
        sliderBackgroundColor = Color(11, 11, 11);
    else
        sliderBackgroundColor = Color(0xda, 0xda, 0xda);

    paintRoundedSliderBackground(rect, style, context, sliderBackgroundColor);

    // Draw the buffered range. Since the element may have multiple buffered ranges and it'd be
    // distracting/'busy' to show all of them, show only the buffered range containing the current play head.
    TimeRanges* bufferedTimeRanges = mediaElement->buffered();
    float duration = mediaElement->duration();
    float currentTime = mediaElement->currentTime();
    if (std::isnan(duration) || std::isinf(duration) || !duration || std::isnan(currentTime))
        return;

    for (unsigned i = 0; i < bufferedTimeRanges->length(); ++i) {
        float start = bufferedTimeRanges->start(i, ASSERT_NO_EXCEPTION);
        float end = bufferedTimeRanges->end(i, ASSERT_NO_EXCEPTION);
        // The delta is there to avoid corner cases when buffered
        // ranges is out of sync with current time because of
        // asynchronous media pipeline and current time caching in
        // HTMLMediaElement.
        // This is related to https://www.w3.org/Bugs/Public/show_bug.cgi?id=28125
        // FIXME: Remove this workaround when WebMediaPlayer
        // has an asynchronous pause interface.
        if (std::isnan(start) || std::isnan(end)
            || start > currentTime + kCurrentTimeBufferedDelta || end < currentTime)
            continue;
        int startPosition = int(start * rect.width() / duration);
        int currentPosition = int(currentTime * rect.width() / duration);
        int endPosition = int(end * rect.width() / duration);

        if (!useNewUi) {
            // Add half the thumb width proportionally adjusted to the current painting position.
            int thumbCenter = mediaSliderThumbWidth / 2;
            int addWidth = thumbCenter * (1.0 - 2.0 * currentPosition / rect.width());
            currentPosition += addWidth;
        }

        // Draw highlight before current time.
        Color startColor;
        Color endColor;
        if (!useNewUi) {
            startColor = Color(195, 195, 195); // white-ish.
            endColor = Color(217, 217, 217);
        } else {
            startColor = endColor = Color(0x42, 0x85, 0xf4); // blue.
        }

        if (currentPosition > startPosition)
            paintSliderRangeHighlight(rect, style, context, startPosition, currentPosition, startColor, endColor);

        // Draw grey-ish highlight after current time.
        if (!useNewUi) {
            startColor = Color(60, 60, 60);
            endColor = Color(76, 76, 76);
        } else {
            startColor = endColor = Color(0x9f, 0x9f, 0x9f); // light grey.
        }

        if (endPosition > currentPosition)
            paintSliderRangeHighlight(rect, style, context, currentPosition, endPosition, startColor, endColor);

        return;
    }
}