Refactor SourceBufferStream to fix DCHECK when overlapping the selected range

The bug was made possible because the return value for GetNextTimestamp() was used
incorrectly to check whether or not a range was seeked. This CL simplifies the
purpose of GetNextTimestamp() and adds HasNextBufferPosition().

BUG=132930
TEST=media_unittests

Review URL: https://chromiumcodereview.appspot.com/10573015

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@143734 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 313 insertions, 175 deletions

diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index ffe9602..0176aa9 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -60,18 +60,14 @@ class SourceBufferRange {
   // Resets |next_buffer_index_| if the buffer at |next_buffer_index_| was
   // deleted, and deletes the |keyframe_map_| entries for the buffers that
   // were removed.
-  // If |deleted_buffers| or |next_buffer| are null, they are ignored.
-  // Otherwise, |deleted_buffers| contains the buffers that were deleted from
-  // this range, and |next_buffer| points to the buffer in |deleted_buffers|
-  // that had been at |next_buffer_index_|. If |next_buffer_index_| did not
-  // point to any buffer added to |deleted_buffers|, then |next_buffer| points
-  // to |deleted_buffers.end()|.
+  // |deleted_buffers| contains the buffers that were deleted from this range,
+  // starting at the buffer that had been at |next_buffer_index_|.
+  // |deleted_buffers| is empty if the buffer at |next_buffer_index_| was not
+  // deleted.
   void DeleteAfter(scoped_refptr<StreamParserBuffer> buffer,
-                   BufferQueue* deleted_buffers,
-                   BufferQueue::iterator* next_buffer);
+                   BufferQueue* deleted_buffers);
   // Deletes all buffers in range.
-  void DeleteAll(BufferQueue* deleted_buffers,
-                 BufferQueue::iterator* next_buffer);
+  void DeleteAll(BufferQueue* deleted_buffers);
 
   // Updates |out_buffer| with the next buffer in presentation order. Seek()
   // must be called before calls to GetNextBuffer(), and buffers are returned
@@ -81,9 +77,14 @@ class SourceBufferRange {
   bool GetNextBuffer(scoped_refptr<StreamParserBuffer>* out_buffer);
   bool HasNextBuffer() const;
 
+  // Returns true if the range knows the position of the next buffer it should
+  // return, i.e. it has been Seek()ed. This does not necessarily mean that it
+  // has the next buffer yet.
+  bool HasNextBufferPosition() const;
+
   // Returns the timestamp of the next buffer that will be returned from
-  // GetNextBuffer(). Returns kNoTimestamp() if Seek() has never been called or
-  // if this range does not have the next buffer yet.
+  // GetNextBuffer(). This may be an approximation if the range does not have
+  // next buffer buffered.
   base::TimeDelta GetNextTimestamp() const;
 
   // Returns the start timestamp of the range.
@@ -96,9 +97,7 @@ class SourceBufferRange {
   // Returns whether a buffer with a starting timestamp of |timestamp| would
   // belong in this range. This includes a buffer that would be appended to
   // the end of the range.
-  // Returns 0 if |timestamp| is in this range, -1 if |timestamp| appears
-  // before this range, or 1 if |timestamp| appears after this range.
-  int BelongsToRange(base::TimeDelta timestamp) const;
+  bool BelongsToRange(base::TimeDelta timestamp) const;
 
   // Returns true if the range has enough data to seek to the specified
   // |timestamp|, false otherwise.
@@ -116,8 +115,7 @@ class SourceBufferRange {
   // Helper method to delete buffers in |buffers_| starting from
   // |starting_point|, an iterator in |buffers_|.
   void DeleteAfter(const BufferQueue::iterator& starting_point,
-                   BufferQueue* deleted_buffers,
-                   BufferQueue::iterator* next_buffer);
+                   BufferQueue* deleted_buffers);
 
   // An ordered list of buffers in this range.
   BufferQueue buffers_;
@@ -232,33 +230,19 @@ bool SourceBufferStream::Append(
   DCHECK(!buffers.empty());
   DCHECK(media_segment_start_time != kNoTimestamp());
 
-  RangeList::iterator range_for_new_buffers = ranges_.end();
-  RangeList::iterator itr = ranges_.end();
-  base::TimeDelta start_timestamp = buffers.front()->GetTimestamp();
-  for (itr = ranges_.begin(); itr != ranges_.end(); itr++) {
-    int range_value = (*itr)->BelongsToRange(start_timestamp);
-    // |start_timestamp| is before the current range in this loop. Because
-    // |ranges_| is sorted, this means that we need to create a new range and
-    // should be placed before |itr|.
-    if (range_value < 0)
-      break;
+  // Find a range into which we'll append |buffers|.
+  RangeList::iterator range_for_new_buffers = FindExistingRangeFor(buffers);
 
-    if (range_value == 0) {
-      // Found an existing range into which we can append buffers.
-      range_for_new_buffers = itr;
-      break;
-    }
-  }
-
-  if (range_for_new_buffers == ranges_.end()) {
+  // If there's a range for |buffers|, insert |buffers| accordingly. Otherwise,
+  // create a new range with |buffers|.
+  if (range_for_new_buffers != ranges_.end()) {
+    InsertIntoExistingRange(range_for_new_buffers, buffers);
+  } else {
     // Ranges must begin with a keyframe.
     if (!buffers.front()->IsKeyframe())
       return false;
     range_for_new_buffers =
-        ranges_.insert(itr, new SourceBufferRange(
-            buffers, media_segment_start_time));
-  } else {
-    InsertIntoExistingRange(range_for_new_buffers, buffers);
+        AddToRanges(new SourceBufferRange(buffers, media_segment_start_time));
   }
 
   // Resolve overlaps.
@@ -271,7 +255,7 @@ bool SourceBufferStream::Append(
   // TODO(vrk): This should be done by ChunkDemuxer. (crbug.com/132815)
   if (!seek_pending_ && !selected_range_) {
     selected_range_ = *range_for_new_buffers;
-    selected_range_->Seek(start_timestamp);
+    selected_range_->Seek(buffers.front()->GetTimestamp());
   }
 
   // Finally, try to complete pending seek if one exists.
@@ -286,34 +270,51 @@ void SourceBufferStream::InsertIntoExistingRange(
     const RangeList::iterator& range_for_new_buffers_itr,
     const BufferQueue& new_buffers) {
   SourceBufferRange* range_for_new_buffers = *range_for_new_buffers_itr;
-  RangeList::iterator next_range_itr = range_for_new_buffers_itr;
-  next_range_itr++;
+
+  // If this is a simple case where we can just append to the end of the range,
+  // do so and return.
+  if (range_for_new_buffers->CanAppendToEnd(new_buffers)) {
+    range_for_new_buffers->AppendToEnd(new_buffers);
+    return;
+  }
+
+  // Otherwise, this is either a start overlap or an middle overlap.
 
   // In case this is a middle overlap, save the buffers that come after the end
   // of |new_buffers|, and add them into a new range.
-  SourceBufferRange* new_portion =
+  base::TimeDelta next_buffer_timestamp = GetNextBufferTimestamp();
+  bool had_next_buffer = range_for_new_buffers->HasNextBuffer();
+  SourceBufferRange* new_next_range =
       range_for_new_buffers->SplitRange(new_buffers.back()->GetEndTimestamp());
 
-  if (new_portion) {
-    next_range_itr = ranges_.insert(next_range_itr, new_portion);
-    // If |range_for_new_buffers| was selected and the next buffer was in the
-    // |new_portion| half, update |selected_range_|.
-    if (selected_range_ == range_for_new_buffers &&
-        new_portion->GetNextTimestamp() != kNoTimestamp()) {
-      selected_range_ = new_portion;
-    }
-  }
+  if (new_next_range)
+    AddToRanges(new_next_range);
 
+  // Delete the buffers that are overlapped by |new_buffers|, then append
+  // |new_buffers| to the end of the range.
   BufferQueue deleted_buffers;
-  BufferQueue::iterator next_buffer;
-  range_for_new_buffers->DeleteAfter(
-      new_buffers.front(), &deleted_buffers, &next_buffer);
+  range_for_new_buffers->DeleteAfter(new_buffers.front(), &deleted_buffers);
   range_for_new_buffers->AppendToEnd(new_buffers);
 
-  if (selected_range_ == range_for_new_buffers &&
-      !deleted_buffers.empty() && next_buffer != deleted_buffers.end()) {
-    UpdateTrackBuffer(range_for_new_buffers_itr, deleted_buffers, next_buffer);
+  // If |new_buffers| doesn't overlap the selected range, no need to do anything
+  // more.
+  if (selected_range_ != range_for_new_buffers || !had_next_buffer ||
+      next_buffer_timestamp < new_buffers.front()->GetTimestamp()) {
+    return;
+  }
+
+  // If this was a middle overlap resulting in a new range, and the next buffer
+  // position has been transferred to the newly created range, update the
+  // |selected_range_| accordingly.
+  if (new_next_range && new_next_range->HasNextBufferPosition()) {
+    DCHECK(!range_for_new_buffers->HasNextBufferPosition());
+    selected_range_ = new_next_range;
+    return;
   }
+
+  selected_range_ = range_for_new_buffers;
+  selected_range_->SeekAfter(next_buffer_timestamp);
+  UpdateTrackBuffer(deleted_buffers);
 }
 
 void SourceBufferStream::ResolveCompleteOverlaps(
@@ -321,18 +322,21 @@ void SourceBufferStream::ResolveCompleteOverlaps(
   SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
   RangeList::iterator next_range_itr = range_with_new_buffers_itr;
   next_range_itr++;
+  base::TimeDelta next_buffer_timestamp = GetNextBufferTimestamp();
 
   while (next_range_itr != ranges_.end() &&
          range_with_new_buffers->CompletelyOverlaps(**next_range_itr)) {
     if (*next_range_itr == selected_range_) {
-      // Delete everything from the selected range that |new_range| overlaps,
-      // and save the next buffers.
+      // Transfer the next buffer position from the old selected range to the
+      // range with the new buffers.
+      selected_range_ = range_with_new_buffers;
+      selected_range_->SeekAfter(next_buffer_timestamp);
+
+      // Delete everything from the old selected range and save the next
+      // buffers.
       BufferQueue deleted_buffers;
-      BufferQueue::iterator next_buffer;
-      (*next_range_itr)->DeleteAll(&deleted_buffers, &next_buffer);
-      UpdateTrackBuffer(range_with_new_buffers_itr, deleted_buffers,
-                        next_buffer);
-      DCHECK_NE(selected_range_, *next_range_itr);
+      (*next_range_itr)->DeleteAll(&deleted_buffers);
+      UpdateTrackBuffer(deleted_buffers);
     }
     delete *next_range_itr;
     next_range_itr = ranges_.erase(next_range_itr);
@@ -344,6 +348,7 @@ void SourceBufferStream::ResolveEndOverlap(
   SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
   RangeList::iterator next_range_itr = range_with_new_buffers_itr;
   next_range_itr++;
+  base::TimeDelta next_buffer_timestamp = GetNextBufferTimestamp();
 
   if (next_range_itr == ranges_.end() ||
       !range_with_new_buffers->EndOverlaps(**next_range_itr)) {
@@ -362,75 +367,76 @@ void SourceBufferStream::ResolveEndOverlap(
 
   // If there were non-overlapped buffers, add the new range to |ranges_|.
   if (new_next_range)
-    ranges_.insert(next_range_itr, new_next_range);
+    AddToRanges(new_next_range);
 
   // If we didn't overlap a selected range, return.
   if (selected_range_ != overlapped_range.get())
     return;
 
-  // If the next buffer was in the |new_next_range| half of the overlapped
-  // range, then the |selected_range_| is now |new_next_range|.
-  if (new_next_range &&
-      new_next_range->GetNextTimestamp() != kNoTimestamp()) {
+  // If the |overlapped_range| transfers its next buffer position to
+  // |new_next_range|, make |new_next_range| the |selected_range_|.
+  if (new_next_range && new_next_range->HasNextBufferPosition()) {
+    DCHECK(!overlapped_range->HasNextBufferPosition());
     selected_range_ = new_next_range;
     return;
   }
 
-  // Otherwise, update track buffer with overlapped buffers.
+  // Transfer the next buffer position from the old range to the range with
+  // the new buffers.
+  selected_range_ = range_with_new_buffers;
+  selected_range_->SeekAfter(next_buffer_timestamp);
+
+  // Update track buffer with overlapped buffers.
   BufferQueue deleted_buffers;
   scoped_refptr<StreamParserBuffer> buffer;
   while (overlapped_range->GetNextBuffer(&buffer)) {
     deleted_buffers.push_back(buffer);
   }
-  BufferQueue::iterator next_buffer = deleted_buffers.begin();
-
-  // This will update |selected_range_| to no longer point to
-  // |overlapped_range|.
-  UpdateTrackBuffer(range_with_new_buffers_itr, deleted_buffers, next_buffer);
-  DCHECK_NE(selected_range_, overlapped_range.get());
+  UpdateTrackBuffer(deleted_buffers);
 }
 
-void SourceBufferStream::UpdateTrackBuffer(
-    const RangeList::iterator& range_with_new_buffers_itr,
-    const BufferQueue& deleted_buffers,
-    const BufferQueue::iterator& next_buffer) {
-  DCHECK(!deleted_buffers.empty() && next_buffer != deleted_buffers.end());
+void SourceBufferStream::UpdateTrackBuffer(const BufferQueue& deleted_buffers) {
+  if (!track_buffer_.empty() || deleted_buffers.empty())
+    return;
 
-  SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
+  DCHECK(selected_range_);
+  DCHECK(selected_range_->HasNextBufferPosition());
 
-  // Seek to the next keyframe after (or equal to) the timestamp of the next
-  // buffer being overlapped.
-  range_with_new_buffers->SeekAfter((*next_buffer)->GetTimestamp());
-  selected_range_ = range_with_new_buffers;
+  base::TimeDelta next_keyframe_timestamp = selected_range_->GetNextTimestamp();
+
+  // If there is no gap between what was deleted and what was added, nothing
+  // should be added to the track buffer.
+  if (selected_range_->HasNextBuffer() &&
+      next_keyframe_timestamp == deleted_buffers.front()->GetTimestamp()) {
+    return;
+  }
+
+  DCHECK(next_keyframe_timestamp >= deleted_buffers.front()->GetTimestamp());
 
-  base::TimeDelta next_keyframe_timestamp =
-      range_with_new_buffers->GetNextTimestamp();
-
-  if (track_buffer_.empty()) {
-    // Add all the old buffers up until |next_keyframe_timestamp| into
-    // |track_buffer_|. If there was no next keyframe, then we add all buffers
-    // into |track_buffer_|.
-    BufferQueue::iterator next_buffer_itr = next_buffer;
-    while (next_buffer_itr != deleted_buffers.end() &&
-           (next_keyframe_timestamp == kNoTimestamp() ||
-            (*next_buffer_itr)->GetTimestamp() < next_keyframe_timestamp)) {
-      track_buffer_.push_back(*next_buffer_itr);
-      next_buffer_itr++;
+  // If the |selected_range_| is ready to return data, fill the track buffer
+  // with all buffers that come before |next_keyframe_timestamp| and return.
+  if (selected_range_->HasNextBuffer()) {
+    for (BufferQueue::const_iterator itr = deleted_buffers.begin();
+         itr != deleted_buffers.end() &&
+         (*itr)->GetTimestamp() < next_keyframe_timestamp; ++itr) {
+      track_buffer_.push_back(*itr);
     }
+    return;
   }
 
+  // Otherwise, the |selected_range_| is not ready to return data, so add all
+  // the deleted buffers into the |track_buffer_|.
+  track_buffer_ = deleted_buffers;
+
   // See if the next range contains the keyframe after the end of the
   // |track_buffer_|, and if so, change |selected_range_|.
-  if (next_keyframe_timestamp == kNoTimestamp()) {
-    DCHECK(!track_buffer_.empty());
-    RangeList::iterator next_range_itr = range_with_new_buffers_itr;
-    next_range_itr++;
-    if (next_range_itr != ranges_.end()) {
-      (*next_range_itr)->SeekAfter(track_buffer_.back()->GetEndTimestamp());
-      if (IsNextInSequence(track_buffer_.back(),
-                           (*next_range_itr)->GetNextTimestamp())) {
-        selected_range_ = *next_range_itr;
-      }
+  RangeList::iterator next_range_itr = ++(GetSelectedRangeItr());
+  if (next_range_itr != ranges_.end()) {
+    (*next_range_itr)->SeekAfter(track_buffer_.back()->GetEndTimestamp());
+    if ((*next_range_itr)->HasNextBuffer() &&
+        IsNextInSequence(track_buffer_.back(),
+                         (*next_range_itr)->GetNextTimestamp())) {
+      selected_range_ = *next_range_itr;
     }
   }
 }
@@ -499,6 +505,48 @@ bool SourceBufferStream::GetNextBuffer(
   return selected_range_ && selected_range_->GetNextBuffer(out_buffer);
 }
 
+base::TimeDelta SourceBufferStream::GetNextBufferTimestamp() {
+  if (!selected_range_)
+    return kNoTimestamp();
+
+  DCHECK(selected_range_->HasNextBufferPosition());
+  return selected_range_->GetNextTimestamp();
+}
+
+SourceBufferStream::RangeList::iterator
+SourceBufferStream::FindExistingRangeFor(const BufferQueue& new_buffers) {
+  DCHECK(!new_buffers.empty());
+  base::TimeDelta start_timestamp = new_buffers.front()->GetTimestamp();
+  for (RangeList::iterator itr = ranges_.begin(); itr != ranges_.end(); itr++) {
+    if ((*itr)->BelongsToRange(start_timestamp))
+      return itr;
+  }
+  return ranges_.end();
+}
+
+SourceBufferStream::RangeList::iterator
+SourceBufferStream::AddToRanges(SourceBufferRange* new_range) {
+  base::TimeDelta start_timestamp = new_range->GetStartTimestamp();
+  RangeList::iterator itr = ranges_.end();
+  for (itr = ranges_.begin(); itr != ranges_.end(); itr++) {
+    if ((*itr)->GetStartTimestamp() > start_timestamp)
+      break;
+  }
+  return ranges_.insert(itr, new_range);
+}
+
+SourceBufferStream::RangeList::iterator
+SourceBufferStream::GetSelectedRangeItr() {
+  DCHECK(selected_range_);
+  RangeList::iterator itr = ranges_.end();
+  for (itr = ranges_.begin(); itr != ranges_.end(); itr++) {
+    if (*itr == selected_range_)
+      break;
+  }
+  DCHECK(itr != ranges_.end());
+  return itr;
+}
+
 Ranges<base::TimeDelta> SourceBufferStream::GetBufferedTime() const {
   Ranges<base::TimeDelta> ranges;
   for (RangeList::const_iterator itr = ranges_.begin();
@@ -596,74 +644,65 @@ SourceBufferRange* SourceBufferRange::SplitRange(base::TimeDelta timestamp) {
   if (new_beginning_keyframe == keyframe_map_.end())
     return NULL;
 
+  // Remove the data beginning at |keyframe_index| from |buffers_| and save it
+  // into |removed_buffers|.
   int keyframe_index = new_beginning_keyframe->second;
   DCHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
+  BufferQueue::iterator starting_point = buffers_.begin() + keyframe_index;
+  BufferQueue removed_buffers(starting_point, buffers_.end());
+  keyframe_map_.erase(new_beginning_keyframe, keyframe_map_.end());
+  buffers_.erase(starting_point, buffers_.end());
 
-  BufferQueue removed_buffers;
-  BufferQueue::iterator next_buffer;
-  DeleteAfter(
-      buffers_.begin() + keyframe_index, &removed_buffers, &next_buffer);
-
+  // Create a new range with |removed_buffers|.
   SourceBufferRange* split_range =
       new SourceBufferRange(removed_buffers, kNoTimestamp());
-  if (next_buffer != removed_buffers.end()) {
-    split_range->next_buffer_index_ = next_buffer - removed_buffers.begin();
+
+  // If |next_buffer_index_| points to a buffer in |split_range|, update the
+  // |next_buffer_index_| of this range and |split_range| accordingly.
+  if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
+    split_range->next_buffer_index_ = next_buffer_index_ - keyframe_index;
+    next_buffer_index_ = -1;
   }
   return split_range;
 }
 
-void SourceBufferRange::DeleteAll(BufferQueue* removed_buffers,
-                                  BufferQueue::iterator* next_buffer) {
-  DeleteAfter(buffers_.begin(), removed_buffers, next_buffer);
+void SourceBufferRange::DeleteAll(BufferQueue* removed_buffers) {
+  DeleteAfter(buffers_.begin(), removed_buffers);
 }
 
 void SourceBufferRange::DeleteAfter(
-    scoped_refptr<StreamParserBuffer> buffer,
-    BufferQueue* removed_buffers,
-    BufferQueue::iterator* next_buffer) {
+    scoped_refptr<StreamParserBuffer> buffer, BufferQueue* removed_buffers) {
   // Find the place in |buffers_| where we will begin deleting data.
   BufferQueue::iterator starting_point =
       std::lower_bound(buffers_.begin(), buffers_.end(),
                        buffer,
                        BufferComparator);
-  DeleteAfter(starting_point, removed_buffers, next_buffer);
+  DeleteAfter(starting_point, removed_buffers);
 }
 
 void SourceBufferRange::DeleteAfter(
-    const BufferQueue::iterator& starting_point,
-    BufferQueue* removed_buffers,
-    BufferQueue::iterator* next_buffer) {
+    const BufferQueue::iterator& starting_point, BufferQueue* removed_buffers) {
+  DCHECK(removed_buffers);
   // Return if we're not deleting anything.
   if (starting_point == buffers_.end())
     return;
 
-  // Find the first keyframe after |starting_point|.
-  KeyframeMap::iterator starting_point_keyframe =
-      keyframe_map_.lower_bound((*starting_point)->GetTimestamp());
-
-  // Save the buffers we're about to delete.
-  if (removed_buffers) {
-    BufferQueue saved(starting_point, buffers_.end());
-    removed_buffers->swap(saved);
-    if (next_buffer)
-      *next_buffer = removed_buffers->end();
-  }
-
   // Reset the next buffer index if we will be deleting the buffer that's next
   // in sequence.
-  base::TimeDelta next_buffer_timestamp = GetNextTimestamp();
-  if (next_buffer_timestamp != kNoTimestamp() &&
-      next_buffer_timestamp >= (*starting_point)->GetTimestamp()) {
-    if (removed_buffers && next_buffer) {
-      int starting_offset = starting_point - buffers_.begin();
-      int next_buffer_offset = next_buffer_index_ - starting_offset;
-      DCHECK_GE(next_buffer_offset, 0);
-      *next_buffer = removed_buffers->begin() + next_buffer_offset;
-    }
+  if (HasNextBuffer() &&
+      GetNextTimestamp() >= (*starting_point)->GetTimestamp()) {
+    // Save the buffers we're about to delete if the output parameter is valid.
+    int starting_offset = starting_point - buffers_.begin();
+    int next_buffer_offset = next_buffer_index_ - starting_offset;
+    DCHECK_GE(next_buffer_offset, 0);
+    BufferQueue saved(starting_point + next_buffer_offset, buffers_.end());
+    removed_buffers->swap(saved);
     next_buffer_index_ = -1;
   }
 
   // Remove keyframes from |starting_point| onward.
+  KeyframeMap::iterator starting_point_keyframe =
+      keyframe_map_.lower_bound((*starting_point)->GetTimestamp());
   keyframe_map_.erase(starting_point_keyframe, keyframe_map_.end());
 
   // Remove everything from |starting_point| onward.
@@ -690,15 +729,21 @@ bool SourceBufferRange::HasNextBuffer() const {
 
 base::TimeDelta SourceBufferRange::GetNextTimestamp() const {
   DCHECK(!buffers_.empty());
+  DCHECK(HasNextBufferPosition());
 
-  if (next_buffer_index_ >= static_cast<int>(buffers_.size()) ||
-      next_buffer_index_ < 0 || waiting_for_keyframe_) {
-    return kNoTimestamp();
-  }
+  if (waiting_for_keyframe_)
+    return next_keyframe_timestamp_;
+
+  if (next_buffer_index_ >= static_cast<int>(buffers_.size()))
+    return buffers_.back()->GetEndTimestamp();
 
   return buffers_.at(next_buffer_index_)->GetTimestamp();
 }
 
+bool SourceBufferRange::HasNextBufferPosition() const {
+  return next_buffer_index_ >= 0 || waiting_for_keyframe_;
+}
+
 void SourceBufferRange::AppendToEnd(const SourceBufferRange& range,
                                     bool transfer_current_position) {
   DCHECK(CanAppendToEnd(range));
@@ -719,19 +764,11 @@ bool SourceBufferRange::CanAppendToEnd(const BufferQueue& buffers) const {
   return IsNextInSequence(buffers_.back(), buffers.front()->GetTimestamp());
 }
 
-int SourceBufferRange::BelongsToRange(base::TimeDelta timestamp) const {
+bool SourceBufferRange::BelongsToRange(base::TimeDelta timestamp) const {
   DCHECK(!buffers_.empty());
 
-  if (IsNextInSequence(buffers_.back(), timestamp) ||
-      (GetEndTimestamp() >= timestamp && GetStartTimestamp() <= timestamp)) {
-    return 0;
-  }
-
-  if (GetStartTimestamp() > timestamp)
-    return -1;
-
-  // |timestamp| must be after this range.
-  return 1;
+  return (IsNextInSequence(buffers_.back(), timestamp) ||
+          (GetStartTimestamp() <= timestamp && timestamp <= GetEndTimestamp()));
 }
 
 bool SourceBufferRange::CanSeekTo(base::TimeDelta timestamp) const {
diff --git a/media/filters/source_buffer_stream.h b/media/filters/source_buffer_stream.h
index 5bc4ba0..db2a92f 100644
--- a/media/filters/source_buffer_stream.h
+++ b/media/filters/source_buffer_stream.h
@@ -98,25 +98,40 @@ class MEDIA_EXPORT SourceBufferStream {
       const RangeList::iterator& range_with_new_buffers_itr);
   void ResolveEndOverlap(const RangeList::iterator& range_with_new_buffers_itr);
 
-  // Adds buffers to |track_buffer_| and updates |selected_range_| accordingly.
-  // |range_with_new_buffers_itr| points to the range containing the newly
-  // appended buffers.
-  // |deleted_buffers| contains all the buffers that were deleted as a result
-  // of appending new buffers into |range_with_new_buffers_itr|. |next_buffer|
-  // points to the buffer in |deleted_buffers| that should be returned by the
-  // next call to GetNextBuffer(). Assumes |deleted_buffers| and |next_buffer|
-  // are valid.
+  // This method is a bit tricky to describe. When what would have been the
+  // next buffer returned from |selected_range_| is overlapped by new data,
+  // the |selected_range_| seeks forward to the next keyframe after (or at) the
+  // next buffer timestamp and the overlapped buffers are deleted. But for
+  // smooth playback between the old data to the new data's keyframe, some of
+  // these |deleted_buffers| may be temporarily saved into |track_buffer_|.
+  // UpdateTrackBuffer() takes these |deleted_buffers| and decides whether it
+  // wants to save any buffers into |track_buffer_|.
   // TODO(vrk): This is a little crazy! Ideas for cleanup in crbug.com/129623.
-  void UpdateTrackBuffer(
-      const RangeList::iterator& range_with_new_buffers_itr,
-      const BufferQueue& deleted_buffers,
-      const BufferQueue::iterator& next_buffer);
+  void UpdateTrackBuffer(const BufferQueue& deleted_buffers);
 
   // Checks to see if |range_with_new_buffers_itr| can be merged with the range
   // next to it, and merges them if so.
   void MergeWithAdjacentRangeIfNecessary(
       const RangeList::iterator& range_with_new_buffers_itr);
 
+  // Helper method that returns the timestamp for the next buffer that
+  // |selected_range_| will return from GetNextBuffer() call, or kNoTimestamp()
+  // if in between seeking (i.e. |selected_range_| is null).
+  base::TimeDelta GetNextBufferTimestamp();
+
+  // Finds the range into which |new_buffers| should be inserted and returns the
+  // iterator pointing to it. Returns |ranges_.end()| if no existing range
+  // should contain |new_buffers|.
+  RangeList::iterator FindExistingRangeFor(const BufferQueue& new_buffers);
+
+  // Inserts |new_range| into |ranges_| preserving sorted order. Returns an
+  // iterator in |ranges_| that points to |new_range|.
+  RangeList::iterator AddToRanges(SourceBufferRange* new_range);
+
+  // Returns an iterator that points to the place in |ranges_| where
+  // |selected_range_| lives.
+  RangeList::iterator GetSelectedRangeItr();
+
   // List of disjoint buffered ranges, ordered by start time.
   RangeList ranges_;
 
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index a89eec5..7ec3f9d 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -1120,6 +1120,89 @@ TEST_F(SourceBufferStreamTest, GetNextBuffer_ExhaustThenAppend) {
   CheckExpectedBuffers(4, 5);
 }
 
+// This test covers the case where new buffers start-overlap a range whose next
+// buffer is not buffered.
+TEST_F(SourceBufferStreamTest, GetNextBuffer_ExhaustThenStartOverlap) {
+  // Append 10 buffers at positions 0 through 9 and exhaust the buffers.
+  AppendBuffers(0, 10, &kDataA);
+  CheckExpectedBuffers(0, 9, &kDataA);
+
+  // Next buffer is at position 10, so should not be able to fulfill request.
+  CheckNoNextBuffer();
+
+  // Append 6 buffers at positons 5 through 10. This is to test that doing a
+  // start-overlap successfully fulfills the read at position 10, even though
+  // position 10 was unbuffered.
+  AppendBuffers(5, 6, &kDataB);
+  CheckExpectedBuffers(10, 10, &kDataB);
+
+  // Then add 5 buffers from positions 11 though 15.
+  AppendBuffers(11, 5, &kDataB);
+
+  // Check the next 4 buffers are correct, which also effectively seeks to
+  // position 15.
+  CheckExpectedBuffers(11, 14, &kDataB);
+
+  // Replace the next buffer at position 15 with another start overlap.
+  AppendBuffers(15, 2, &kDataA);
+  CheckExpectedBuffers(15, 16, &kDataA);
+}
+
+// This test covers the case where new buffers completely overlap a range
+// whose next buffer is not buffered.
+TEST_F(SourceBufferStreamTest, GetNextBuffer_ExhaustThenCompeteOverlap) {
+  // Append 5 buffers at positions 10 through 14 and exhaust the buffers.
+  AppendBuffers(10, 5, &kDataA);
+  CheckExpectedBuffers(10, 14, &kDataA);
+
+  // Next buffer is at position 15, so should not be able to fulfill request.
+  CheckNoNextBuffer();
+
+  // Do a complete overlap and test that this successfully fulfills the read
+  // at position 15.
+  AppendBuffers(5, 11, &kDataB);
+  CheckExpectedBuffers(15, 15, &kDataB);
+
+  // Then add 5 buffers from positions 16 though 20.
+  AppendBuffers(16, 5, &kDataB);
+
+  // Check the next 4 buffers are correct, which also effectively seeks to
+  // position 20.
+  CheckExpectedBuffers(16, 19, &kDataB);
+
+  // Do a complete overlap and replace the buffer at position 20.
+  AppendBuffers(0, 21, &kDataA);
+  CheckExpectedBuffers(20, 20, &kDataA);
+}
+
+// This test covers the case where a range is stalled waiting for its next
+// buffer, then an end-overlap causes the end of the range to be deleted.
+TEST_F(SourceBufferStreamTest, GetNextBuffer_ExhaustThenEndOverlap) {
+  // Append 5 buffers at positions 10 through 14 and exhaust the buffers.
+  AppendBuffers(10, 5, &kDataA);
+  CheckExpectedBuffers(10, 14, &kDataA);
+  CheckExpectedRanges("{ [10,14) }");
+
+  // Next buffer is at position 15, so should not be able to fulfill request.
+  CheckNoNextBuffer();
+
+  // Do an end overlap that causes the latter half of the range to be deleted.
+  AppendBuffers(5, 6, &kDataB);
+  CheckNoNextBuffer();
+  CheckExpectedRanges("{ [5,10) }");
+
+  // Fill in the gap. Getting the next buffer should still stall at position 15.
+  for (int i = 11; i <= 14; i++) {
+    AppendBuffers(i, 1, &kDataB);
+    CheckNoNextBuffer();
+  }
+
+  // Append the buffer at position 15 and check to make sure all is correct.
+  AppendBuffers(15, 1);
+  CheckExpectedBuffers(15, 15);
+  CheckExpectedRanges("{ [5,15) }");
+}
+
 // This test is testing the "next buffer" logic after a complete overlap. In
 // this scenario, when the track buffer is exhausted, there is no buffered data
 // to fulfill the request. The SourceBufferStream should be able to fulfill the
@@ -1156,4 +1239,7 @@ TEST_F(SourceBufferStreamTest, GetNextBuffer_NoSeek) {
   CheckExpectedBuffers(5, 5);
 }
 
+// TODO(vrk): Add unit tests where keyframes are unaligned between streams.
+// (crbug.com/133557)
+
 }  // namespace media