TextRenderer only pushes new cues downstream

The TextTrack subsystem in Blink unconditionally satisfies a request
to add a new text cue to the text track cue list, relying on the
upstream demuxers to filter out cues that have already been added to
that list.

The TextRenderer now manages a map of time range objects, to keep
track of which cues (based on their start times) have already been
pushed downstream prior to the current seek.

BUG=230708

Review URL: https://codereview.chromium.org/151103005

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

6 files changed, 397 insertions, 5 deletions

diff --git a/media/base/text_ranges.cc b/media/base/text_ranges.cc
new file mode 100644
index 0000000..41bc7d0
--- /dev/null
+++ b/media/base/text_ranges.cc
@@ -0,0 +1,141 @@
+// Copyright 2014 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 "media/base/text_ranges.h"
+
+#include "base/logging.h"
+
+namespace media {
+
+TextRanges::TextRanges() {
+  Reset();
+}
+
+TextRanges::~TextRanges() {
+}
+
+void TextRanges::Reset() {
+  curr_range_itr_ = range_map_.end();
+}
+
+bool TextRanges::AddCue(base::TimeDelta start_time) {
+  typedef RangeMap::iterator Itr;
+
+  if (curr_range_itr_ == range_map_.end()) {
+    // There is no active time range, so this is the first AddCue()
+    // attempt that follows a Reset().
+
+    if (range_map_.empty()) {
+      NewRange(start_time);
+      return true;
+    }
+
+    if (start_time < range_map_.begin()->first) {
+      NewRange(start_time);
+      return true;
+    }
+
+    const Itr itr = --Itr(range_map_.upper_bound(start_time));
+    DCHECK(start_time >= itr->first);
+
+    Range& range = itr->second;
+
+    if (start_time > range.last_time()) {
+      NewRange(start_time);
+      return true;
+    }
+
+    range.ResetCount(start_time);
+    curr_range_itr_ = itr;
+    return false;
+  }
+
+  DCHECK(start_time >= curr_range_itr_->first);
+
+  Range& curr_range = curr_range_itr_->second;
+
+  if (start_time <= curr_range.last_time())
+    return curr_range.AddCue(start_time);
+
+  const Itr next_range_itr = ++Itr(curr_range_itr_);
+
+  if (next_range_itr != range_map_.end()) {
+    DCHECK(next_range_itr->first > curr_range.last_time());
+    DCHECK(start_time <= next_range_itr->first);
+
+    if (start_time == next_range_itr->first) {
+      // We have walked off the current range, and onto the next one.
+      // There is now no ambiguity about where the current time range
+      // ends, and so we coalesce the current and next ranges.
+
+      Merge(curr_range, next_range_itr);
+      return false;
+    }
+  }
+
+  // Either |curr_range| is the last range in the map, or there is a
+  // next range beyond |curr_range|, but its start time is ahead of
+  // this cue's start time.  In either case, this cue becomes the new
+  // last_time for |curr_range|.  Eventually we will see a cue whose
+  // time matches the start time of the next range, in which case we
+  // coalesce the current and next ranges.
+
+  curr_range.SetLastTime(start_time);
+  return true;
+}
+
+size_t TextRanges::RangeCountForTesting() const {
+  return range_map_.size();
+}
+
+void TextRanges::NewRange(base::TimeDelta start_time) {
+  Range range;
+  range.SetLastTime(start_time);
+
+  std::pair<RangeMap::iterator, bool> result =
+      range_map_.insert(std::make_pair(start_time, range));
+  DCHECK(result.second);
+
+  curr_range_itr_ = result.first;
+}
+
+void TextRanges::Merge(
+    Range& curr_range,
+    const RangeMap::iterator& next_range_itr) {
+  curr_range = next_range_itr->second;
+  curr_range.ResetCount(next_range_itr->first);
+  range_map_.erase(next_range_itr);
+}
+
+void TextRanges::Range::ResetCount(base::TimeDelta start_time) {
+  count_ = (start_time < last_time_) ? 0 : 1;
+}
+
+void TextRanges::Range::SetLastTime(base::TimeDelta last_time) {
+  last_time_ = last_time;
+  count_ = 1;
+  max_count_ = 1;
+}
+
+bool TextRanges::Range::AddCue(base::TimeDelta start_time) {
+  if (start_time < last_time_) {
+    DCHECK_EQ(count_, 0);
+    return false;
+  }
+
+  DCHECK(start_time == last_time_);
+
+  ++count_;
+  if (count_ <= max_count_)
+    return false;
+
+  ++max_count_;
+  return true;
+}
+
+base::TimeDelta TextRanges::Range::last_time() const {
+  return last_time_;
+}
+
+}  // namespace media
diff --git a/media/base/text_ranges.h b/media/base/text_ranges.h
new file mode 100644
index 0000000..adb1750
--- /dev/null
+++ b/media/base/text_ranges.h
@@ -0,0 +1,95 @@
+// Copyright 2014 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.
+
+#ifndef MEDIA_BASE_TEXT_RANGES_H_
+#define MEDIA_BASE_TEXT_RANGES_H_
+
+#include <map>
+
+#include "base/macros.h"
+#include "base/time/time.h"
+#include "media/base/media_export.h"
+
+namespace media {
+
+// Helper class used by the TextRenderer to filter out text cues that
+// have already been passed downstream.
+class MEDIA_EXPORT TextRanges {
+ public:
+  TextRanges();
+  ~TextRanges();
+
+  // Reset the current range pointer, such that we bind to a new range
+  // (either one that exists already, or one that is freshly-created)
+  // during the next AddCue().
+  void Reset();
+
+  // Given a cue with starting timestamp |start_time|, add its start
+  // time to the time ranges. (Note that following a Reset(), cue
+  // times are assumed to be monotonically increasing.) If this time
+  // has already been added to the time ranges, then AddCue() returns
+  // false and clients should not push the cue downstream. Otherwise,
+  // the time is added to the time ranges and AddCue() returns true,
+  // meaning that the cue should be pushed downstream.
+  bool AddCue(base::TimeDelta start_time);
+
+  // Returns a count of the number of time ranges, intended for use by
+  // the unit test module to vet proper time range merge behavior.
+  size_t RangeCountForTesting() const;
+
+ private:
+  // Describes a range of times for cues that have already been
+  // pushed downstream.
+  class Range {
+   public:
+    // Initialize last_time count.
+    void ResetCount(base::TimeDelta start_time);
+
+    // Set last_time and associated counts.
+    void SetLastTime(base::TimeDelta last_time);
+
+    // Adjust time range state to mark the cue as having been seen,
+    // returning true if we have not seen |start_time| already and
+    // false otherwise.
+    bool AddCue(base::TimeDelta start_time);
+
+    // Returns the value of the last time in the range.
+    base::TimeDelta last_time() const;
+
+   private:
+    // The last timestamp of this range.
+    base::TimeDelta last_time_;
+
+    // The number of cues we have detected so far, for this range,
+    // whose timestamp matches last_time.
+    int max_count_;
+
+    // The number of cues we have seen since the most recent Reset(),
+    // whose timestamp matches last_time.
+    int count_;
+  };
+
+  typedef std::map<base::TimeDelta, Range> RangeMap;
+
+  // NewRange() is used to create a new time range when AddCue() is
+  // called immediately following a Reset(), and no existing time
+  // range contains the indicated |start_time| of the cue.
+  void NewRange(base::TimeDelta start_time);
+
+  // Coalesce curr_range with the range that immediately follows.
+  void Merge(Range& curr_range, const RangeMap::iterator& next_range_itr);
+
+  // The collection of time ranges, each of which is bounded
+  // (inclusive) by the key and Range::last_time.
+  RangeMap range_map_;
+
+  // The time range to which we bind following a Reset().
+  RangeMap::iterator curr_range_itr_;
+
+  DISALLOW_COPY_AND_ASSIGN(TextRanges);
+};
+
+}  // namespace media
+
+#endif  // MEDIA_BASE_TEXT_RANGES_H_
diff --git a/media/base/text_ranges_unittest.cc b/media/base/text_ranges_unittest.cc
new file mode 100644
index 0000000..7de0514
--- /dev/null
+++ b/media/base/text_ranges_unittest.cc
@@ -0,0 +1,147 @@
+// Copyright 2014 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 "media/base/text_ranges.h"
+
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace media {
+
+class TextRangesTest : public ::testing::Test {
+ protected:
+  bool AddCue(int seconds) {
+    return ranges_.AddCue(base::TimeDelta::FromSeconds(seconds));
+  }
+
+  void Reset() {
+    ranges_.Reset();
+  }
+
+  size_t RangeCount() {
+    return ranges_.RangeCountForTesting();
+  }
+
+  TextRanges ranges_;
+};
+
+TEST_F(TextRangesTest, TestEmptyRanges) {
+  // Create a new active range, with t=5.
+  EXPECT_TRUE(AddCue(5));
+
+  // Create a new active range, with t=2.
+  Reset();
+  EXPECT_TRUE(AddCue(2));
+
+  // Create a new active range, with t=8.
+  Reset();
+  EXPECT_TRUE(AddCue(8));
+
+  Reset();
+
+  // Make range [2, 2] active.
+  EXPECT_FALSE(AddCue(2));
+  EXPECT_EQ(RangeCount(), 3U);
+
+  // Coalesce first two ranges: [2, 5].
+  EXPECT_FALSE(AddCue(5));
+  EXPECT_EQ(RangeCount(), 2U);
+
+  // Coalesce first two ranges: [2, 8].
+  EXPECT_FALSE(AddCue(8));
+  EXPECT_EQ(RangeCount(), 1U);
+
+  // Add new cue to end of (only) range.
+  EXPECT_TRUE(AddCue(9));
+  EXPECT_EQ(RangeCount(), 1U);
+}
+
+TEST_F(TextRangesTest, TestOneRange) {
+  // Create a new active range, with t=0.
+  EXPECT_TRUE(AddCue(0));
+
+  // Add cues to end of existing range.
+  EXPECT_TRUE(AddCue(1));
+  EXPECT_TRUE(AddCue(4));
+
+  Reset();
+  EXPECT_FALSE(AddCue(2));
+  EXPECT_FALSE(AddCue(3));
+  EXPECT_FALSE(AddCue(4));
+}
+
+TEST_F(TextRangesTest, TestDuplicateLast) {
+  // Create a new active range, with t=0.
+  EXPECT_TRUE(AddCue(0));
+  EXPECT_TRUE(AddCue(1));
+
+  Reset();
+  EXPECT_FALSE(AddCue(1));
+  EXPECT_TRUE(AddCue(1));
+}
+
+TEST_F(TextRangesTest, TestTwoRanges) {
+  // Create a new active range, with t=0.
+  EXPECT_TRUE(AddCue(0));
+
+  // Add cue to end of existing range.
+  EXPECT_TRUE(AddCue(2));
+
+  Reset();
+
+  // Create a new active range, with t=4.
+  EXPECT_TRUE(AddCue(4));
+
+  // Add a new cue to end of last (active) range.
+  EXPECT_TRUE(AddCue(5));
+
+  Reset();
+
+  // Make first range active.
+  EXPECT_FALSE(AddCue(0));
+  EXPECT_FALSE(AddCue(2));
+
+  // Expand first range.
+  EXPECT_TRUE(AddCue(3));
+
+  // Coalesce first and second ranges.
+  EXPECT_FALSE(AddCue(4));
+  EXPECT_EQ(RangeCount(), 1U);
+}
+
+TEST_F(TextRangesTest, TestThreeRanges) {
+  // Create a new active range, with t=0.
+  EXPECT_TRUE(AddCue(0));
+
+  // Add cue to end of existing range.
+  EXPECT_TRUE(AddCue(2));
+
+  Reset();
+
+  // Create a new active range, with t=4.
+  EXPECT_TRUE(AddCue(4));
+
+  // Add a new cue to end of last (active) range.
+  EXPECT_TRUE(AddCue(5));
+
+  Reset();
+
+  // Create a new active range, in between the other two.
+  EXPECT_TRUE(AddCue(3));
+
+  // Coalesce middle and last ranges.
+  EXPECT_FALSE(AddCue(4));
+
+  Reset();
+
+  // Make first range active.
+  EXPECT_FALSE(AddCue(0));
+  EXPECT_FALSE(AddCue(2));
+
+  // Coalesce first and last ranges.
+  EXPECT_FALSE(AddCue(3));
+  EXPECT_EQ(RangeCount(), 1U);
+}
+
+}  // namespace media
diff --git a/media/base/text_renderer.cc b/media/base/text_renderer.cc
index 63ad27a..45f61b4 100644
--- a/media/base/text_renderer.cc
+++ b/media/base/text_renderer.cc
@@ -90,6 +90,7 @@ void TextRenderer::Flush(const base::Closure& callback) {
   for (TextTrackStateMap::iterator itr = text_track_state_map_.begin();
        itr != text_track_state_map_.end(); ++itr) {
     pending_eos_set_.insert(itr->first);
+    itr->second->text_ranges_.Reset();
   }
   DCHECK_EQ(pending_eos_set_.size(), text_track_state_map_.size());
   callback.Run();
@@ -306,12 +307,15 @@ void TextRenderer::CueReady(
   }
 
   base::TimeDelta start = text_cue->timestamp();
-  base::TimeDelta end = start + text_cue->duration();
 
-  state->text_track->addWebVTTCue(start, end,
-                                  text_cue->id(),
-                                  text_cue->text(),
-                                  text_cue->settings());
+  if (state->text_ranges_.AddCue(start)) {
+    base::TimeDelta end = start + text_cue->duration();
+
+    state->text_track->addWebVTTCue(start, end,
+                                    text_cue->id(),
+                                    text_cue->text(),
+                                    text_cue->settings());
+  }
 
   if (state_ == kPlaying) {
     Read(state, text_stream);
diff --git a/media/base/text_renderer.h b/media/base/text_renderer.h
index 3916ef6..dab18e6 100644
--- a/media/base/text_renderer.h
+++ b/media/base/text_renderer.h
@@ -14,6 +14,7 @@
 #include "media/base/demuxer_stream.h"
 #include "media/base/media_export.h"
 #include "media/base/pipeline_status.h"
+#include "media/base/text_ranges.h"
 #include "media/base/text_track.h"
 
 namespace base {
@@ -82,6 +83,7 @@ class MEDIA_EXPORT TextRenderer {
 
     ReadState read_state;
     scoped_ptr<TextTrack> text_track;
+    TextRanges text_ranges_;
   };
 
   // Callback delivered by the demuxer |text_stream| when
diff --git a/media/media.gyp b/media/media.gyp
index 3bf503f..baeb378 100644
--- a/media/media.gyp
+++ b/media/media.gyp
@@ -317,6 +317,8 @@
         'base/stream_parser_buffer.h',
         'base/text_cue.cc',
         'base/text_cue.h',
+        'base/text_ranges.cc',
+        'base/text_ranges.h',
         'base/text_renderer.cc',
         'base/text_renderer.h',
         'base/text_track.h',
@@ -980,6 +982,7 @@
         'base/stream_parser_unittest.cc',
         'base/test_data_util.cc',
         'base/test_data_util.h',
+        'base/text_ranges_unittest.cc',
         'base/text_renderer_unittest.cc',
         'base/user_input_monitor_unittest.cc',
         'base/vector_math_testing.h',