Implement evictFrames() to support MSE's coded frame eviction algorithm.

media/filters/source_buffer_stream_unittest.cc

Index: media/filters/source_buffer_stream_unittest.cc
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index 3828d6c02ec74cfa7f45401a458f1d57b9639e57..343c517cee8c0396e395e9930f16fb0b4aede676 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -144,6 +144,14 @@ class SourceBufferStreamTest : public testing::Test {
     stream_->Seek(timestamp);
   }
 
+  void GarbageCollect_ExpectSuccess() {
+    EXPECT_TRUE(stream_->GarbageCollectIfNeeded(kNoDecodeTimestamp()));
+  }
+
+  void GarbageCollect_ExpectFull() {
+    EXPECT_FALSE(stream_->GarbageCollectIfNeeded(kNoDecodeTimestamp()));
+  }
+
   void RemoveInMs(int start, int end, int duration) {
     Remove(base::TimeDelta::FromMilliseconds(start),
            base::TimeDelta::FromMilliseconds(end),
@@ -2329,6 +2337,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFront) {
   for (int i = 1; i < 20; i++)
     AppendBuffers(i, 1, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // None of the buffers should trigger garbage collection, so all data should
   // be there as expected.
   CheckExpectedRanges("{ [0,19) }");
@@ -2341,6 +2351,9 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFront) {
   // Append 5 buffers to the end of the stream.
   AppendBuffers(20, 5, &kDataA);
 
+  // Run garbage collection
+  GarbageCollect_ExpectSuccess();
+
   // GC should have deleted the first 5 buffers.
   CheckExpectedRanges("{ [5,24) }");
   CheckExpectedBuffers(10, 24, &kDataA);
@@ -2361,6 +2374,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontGOPsAtATime) {
   // Add one buffer to put the memory over the cap.
   AppendBuffers(20, 1, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // GC should have deleted the first 5 buffers so that the range still begins
   // with a keyframe.
   CheckExpectedRanges("{ [5,20) }");
@@ -2370,18 +2385,37 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontGOPsAtATime) {
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteBack) {
-  // Set memory limit to 5 buffers.
-  SetMemoryLimit(5);
+  // Set memory limit to 10 buffers.
+  SetMemoryLimit(10);
 
   // Seek to position 0.
   Seek(0);
 
   // Append 20 buffers at positions 0 through 19.
-  NewSegmentAppend(0, 20, &kDataA);
+  NewSegmentAppend(0, 5, &kDataA);
+  NewSegmentAppend(10, 10, &kDataA);
+  // GC gaurantees we keep all buffers between current seek and last append.
+  // Therefore, append buffers at positions 5 to 9 last so that we are allowed
+  // to collect buffers 10 to 19 (since they are now after last append)
+  NewSegmentAppend(5, 5, &kDataA);
+
+  // Check we have all the buffers
+  CheckExpectedRanges("{ [0,19) }");
+
+  // Run garbage collection
+  GarbageCollect_ExpectSuccess();
 
   // Should leave the first 5 buffers from 0 to 4 and the last GOP appended.
-  CheckExpectedRanges("{ [0,4) [15,19) }");
-  CheckExpectedBuffers(0, 4, &kDataA);
+  CheckExpectedRanges("{ [0,9) }");
+
+  // Check that GC refuses to collect last append
+  SetMemoryLimit(5);
+  GarbageCollect_ExpectFull();
+
+  // Should leave the prior buffers untouched
+  CheckExpectedRanges("{ [0,9) }");
+  CheckExpectedBuffers(0, 9, &kDataA);
+  CheckNoNextBuffer();
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontAndBack) {
@@ -2391,13 +2425,24 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteFrontAndBack) {
   // Seek to position 15.
   Seek(15);
 
-  // Append 40 buffers at positions 0 through 39.
-  NewSegmentAppend(0, 40, &kDataA);
+  // Append 40 buffers at positions 0 through 39
+  NewSegmentAppend(0, 20, &kDataA);
+  NewSegmentAppend(25, 15, &kDataA);
+  // GC gaurantees we keep all buffers between current seek and last append.
+  // Therefore, append buffers at positions 20 to 24 last so that we are allowed
+  // to collect buffers after 24
+  NewSegmentAppend(20, 5, &kDataA);
+
+  // Check we have all the buffers
+  CheckExpectedRanges("{ [0,39) }");
+
+  // Garbage collect will fail, cannot reduce to 3 buffers
+  GarbageCollect_ExpectFull();
 
   // Should leave the GOP containing the seek position and the last GOP
   // appended.
-  CheckExpectedRanges("{ [15,19) [35,39) }");
-  CheckExpectedBuffers(15, 19, &kDataA);
+  CheckExpectedRanges("{ [15,24) }");
+  CheckExpectedBuffers(15, 24, &kDataA);
   CheckNoNextBuffer();
 }
 
@@ -2411,10 +2456,10 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteSeveralRanges) {
   // Append 5 buffers at positions 20 through 24.
   NewSegmentAppend(20, 5);
 
-  // Append 5 buffers at positions 30 through 34.
-  NewSegmentAppend(30, 5);
+  // Append 5 buffers at positions 40 through 44.
+  NewSegmentAppend(40, 5);
 
-  CheckExpectedRanges("{ [0,4) [10,14) [20,24) [30,34) }");
+  CheckExpectedRanges("{ [0,4) [10,14) [20,24) [40,44) }");
 
   // Seek to position 21.
   Seek(20);
@@ -2423,31 +2468,37 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteSeveralRanges) {
   // Set memory limit to 1 buffer.
   SetMemoryLimit(1);
 
-  // Append 5 buffers at positions 40 through 44. This will trigger GC.
-  NewSegmentAppend(40, 5);
+  // Append 5 buffers at positions 40 through 44.
+  NewSegmentAppend(30, 5);
 
-  // Should delete everything except the GOP containing the current buffer and
-  // the last GOP appended.
-  CheckExpectedRanges("{ [20,24) [40,44) }");
+  // We will have more than 1 buffer left, GC will fail
+  GarbageCollect_ExpectFull();
+
+  // Should have deleted all buffer ranges before the current buffer and after
+  // last GOP
+  CheckExpectedRanges("{ [20,24) [30,34) }");
   CheckExpectedBuffers(21, 24);
   CheckNoNextBuffer();
 
   // Continue appending into the last range to make sure it didn't break.
-  AppendBuffers(45, 10);
-  // Should only save last GOP appended.
-  CheckExpectedRanges("{ [20,24) [50,54) }");
+  AppendBuffers(35, 10);
+  GarbageCollect_ExpectFull();
+  // Should save everything between read head and last appended
+  CheckExpectedRanges("{ [20,24) [30,44) }");
 
   // Make sure appending before and after the ranges didn't somehow break.
   SetMemoryLimit(100);
   NewSegmentAppend(0, 10);
-  CheckExpectedRanges("{ [0,9) [20,24) [50,54) }");
+  GarbageCollect_ExpectSuccess();
+  CheckExpectedRanges("{ [0,9) [20,24) [30,44) }");
   Seek(0);
   CheckExpectedBuffers(0, 9);
 
   NewSegmentAppend(90, 10);
-  CheckExpectedRanges("{ [0,9) [20,24) [50,54) [90,99) }");
-  Seek(50);
-  CheckExpectedBuffers(50, 54);
+  GarbageCollect_ExpectSuccess();
+  CheckExpectedRanges("{ [0,9) [20,24) [30,44) [90,99) }");
+  Seek(30);
+  CheckExpectedBuffers(30, 44);
   CheckNoNextBuffer();
   Seek(90);
   CheckExpectedBuffers(90, 99);
@@ -2464,6 +2515,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteAfterLastAppend) {
   // Append 2 GOPs starting at 490ms, 30ms apart.
   NewSegmentAppend("490K 520 550 580K 610 640");
 
+  GarbageCollect_ExpectSuccess();
+
   CheckExpectedRangesByTimestamp("{ [310,400) [490,670) }");
 
   // Seek to the GOP at 580ms.
@@ -2473,6 +2526,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteAfterLastAppend) {
   // So the ranges before GC are "{ [100,280) [310,400) [490,670) }".
   NewSegmentAppend("100K 130 160 190K 220 250K");
 
+  GarbageCollect_ExpectSuccess();
+
   // Should save the newly appended GOPs.
   CheckExpectedRangesByTimestamp("{ [100,280) [580,670) }");
 }
@@ -2491,6 +2546,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_DeleteAfterLastAppendMerged) {
   // range.  So the range before GC is "{ [220,670) }".
   NewSegmentAppend("220K 250 280 310K 340 370");
 
+  GarbageCollect_ExpectSuccess();
+
   // Should save the newly appended GOPs.
   CheckExpectedRangesByTimestamp("{ [220,400) [580,670) }");
 }
@@ -2502,6 +2559,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_NoSeek) {
   // Append 25 buffers at positions 0 through 24.
   NewSegmentAppend(0, 25, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // GC deletes the first 5 buffers to keep the memory limit within cap.
   CheckExpectedRanges("{ [5,24) }");
   CheckNoNextBuffer();
@@ -2520,6 +2579,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_PendingSeek) {
   Seek(15);
   CheckNoNextBuffer();
 
+  GarbageCollect_ExpectSuccess();
+
   CheckExpectedRanges("{ [0,9) [25,29) }");
 
   // Set memory limit to 5 buffers.
@@ -2528,6 +2589,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_PendingSeek) {
   // Append 5 buffers as positions 30 to 34 to trigger GC.
   AppendBuffers(30, 5, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // The current algorithm will delete from the beginning until the memory is
   // under cap.
   CheckExpectedRanges("{ [30,34) }");
@@ -2538,6 +2601,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_PendingSeek) {
   // Append data to fulfill seek.
   NewSegmentAppend(15, 5, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // Check to make sure all is well.
   CheckExpectedRanges("{ [15,19) [30,34) }");
   CheckExpectedBuffers(15, 19, &kDataA);
@@ -2554,22 +2619,26 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_NeedsMoreData) {
 
   // Advance next buffer position to 10.
   Seek(0);
+  GarbageCollect_ExpectSuccess();
   CheckExpectedBuffers(0, 9, &kDataA);
   CheckNoNextBuffer();
 
   // Append 20 buffers at positions 15 through 34.
   NewSegmentAppend(15, 20, &kDataA);
 
-  // GC should have saved the keyframe before the current seek position and the
-  // data closest to the current seek position. It will also save the last GOP
-  // appended.
-  CheckExpectedRanges("{ [5,9) [15,19) [30,34) }");
+  // GC should save the keyframe before the current seek position and the data
+  // closest to the current seek position. It will also save all buffers from
+  // current seek to the last GOP appended, which overflows limit and leads to
+  // failure.
+  GarbageCollect_ExpectFull();
+  CheckExpectedRanges("{ [5,9) [15,34) }");
 
   // Now fulfill the seek at position 10. This will make GC delete the data
   // before position 10 to keep it within cap.
   NewSegmentAppend(10, 5, &kDataA);
-  CheckExpectedRanges("{ [10,19) [30,34) }");
-  CheckExpectedBuffers(10, 19, &kDataA);
+  GarbageCollect_ExpectSuccess();
+  CheckExpectedRanges("{ [10,24) }");
+  CheckExpectedBuffers(10, 24, &kDataA);
 }
 
 TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
@@ -2582,6 +2651,8 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
   // Append 18 buffers at positions 0 through 17.
   NewSegmentAppend(0, 18, &kDataA);
 
+  GarbageCollect_ExpectSuccess();
+
   // Should leave GOP containing seek position.
   CheckExpectedRanges("{ [15,17) }");
 
@@ -2591,6 +2662,10 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
   // Completely overlap the existing buffers.
   NewSegmentAppend(0, 20, &kDataB);
 
+  // 4 buffers in final GOP, which is more than 3 buffers left in buffer, so GC
+  // will fail
+  GarbageCollect_ExpectFull();
+
   // Because buffers 16 and 17 are not keyframes, they are moved to the track
   // buffer upon overlap. The source buffer (i.e. not the track buffer) is now
   // waiting for the next keyframe.
@@ -2601,6 +2676,9 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_TrackBuffer) {
   // Now add a keyframe at position 20.
   AppendBuffers(20, 5, &kDataB);
 
+  // 5 buffers in final GOP, GC will fail
+  GarbageCollect_ExpectFull();
+
   // Should garbage collect such that there are 5 frames remaining, starting at
   // the keyframe.
   CheckExpectedRanges("{ [20,24) }");
@@ -2614,33 +2692,34 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP) {
   // collected.
   SetMemoryLimit(3);
   NewSegmentAppend("0K 30 60 90");
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [0,120) }");
 
   // Make sure you can continue appending data to this GOP; again, GC should not
   // wipe out anything.
   AppendBuffers("120D30");
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [0,150) }");
 
-  // Set memory limit to 100 and append a 2nd range after this without
-  // triggering GC.
-  SetMemoryLimit(100);
+  // Append a 2nd range after this without triggering GC.
   NewSegmentAppend("200K 230 260 290K 320 350");
   CheckExpectedRangesByTimestamp("{ [0,150) [200,380) }");
 
   // Seek to 290ms.
   SeekToTimestamp(base::TimeDelta::FromMilliseconds(290));
 
-  // Now set memory limit to 3 and append a GOP in a separate range after the
-  // selected range. Because it is after 290ms, this tests that the GOP is saved
-  // when deleting from the back.
-  SetMemoryLimit(3);
+  // Now append a GOP in a separate range after the selected range and trigger
+  // GC. Because it is after 290ms, this tests that the GOP is saved when
+  // deleting from the back.
   NewSegmentAppend("500K 530 560 590");
+  GarbageCollect_ExpectFull();
 
-  // Should save GOP with 290ms and last GOP appended.
+  // Should save GOPs between 290ms and the last GOP appended.
   CheckExpectedRangesByTimestamp("{ [290,380) [500,620) }");
 
   // Continue appending to this GOP after GC.
   AppendBuffers("620D30");
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [290,380) [500,650) }");
 }
 
@@ -2656,34 +2735,35 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Middle) {
   SetMemoryLimit(1);
   NewSegmentAppend("80K 110 140");
 
-  // This whole GOP should be saved, and should be able to continue appending
-  // data to it.
+  // This whole GOP should be saved after GC, which will fail due to GOP being
+  // larger than 1 buffer
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [80,170) }");
+  // We should still be able to continue appending data to GOP
   AppendBuffers("170D30");
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [80,200) }");
 
-  // Set memory limit to 100 and append a 2nd range after this without
-  // triggering GC.
-  SetMemoryLimit(100);
+  // Append a 2nd range after this range, without triggering GC.
   NewSegmentAppend("400K 430 460 490K 520 550 580K 610 640");
   CheckExpectedRangesByTimestamp("{ [80,200) [400,670) }");
 
   // Seek to 80ms to make the first range the selected range.
   SeekToTimestamp(base::TimeDelta::FromMilliseconds(80));
 
-  // Now set memory limit to 3 and append a GOP in the middle of the second
-  // range. Because it is after the selected range, this tests that the GOP is
-  // saved when deleting from the back.
-  SetMemoryLimit(3);
+  // Now append a GOP in the middle of the second range and trigger GC. Because
+  // it is after the selected range, this tests that the GOP is saved when
+  // deleting from the back.
   NewSegmentAppend("500K 530 560 590");
+  GarbageCollect_ExpectFull();
 
-  // Should save the GOP containing the seek point and GOP that was last
-  // appended.
-  CheckExpectedRangesByTimestamp("{ [80,200) [500,620) }");
+  // Should save the GOPs between the seek point and GOP that was last appended
+  CheckExpectedRangesByTimestamp("{ [80,200) [400,620) }");
 
   // Continue appending to this GOP after GC.
   AppendBuffers("620D30");
-  CheckExpectedRangesByTimestamp("{ [80,200) [500,650) }");
+  GarbageCollect_ExpectFull();
+  CheckExpectedRangesByTimestamp("{ [80,200) [400,650) }");
 }
 
 // Test saving the last GOP appended when the GOP containing the next buffer is
@@ -2700,7 +2780,9 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected1) {
   SetMemoryLimit(1);
   NewSegmentAppend("0K 30 60");
 
-  // Should save the GOP at 0ms and 90ms.
+  // GC should save the GOP at 0ms and 90ms, and will fail since GOP larger
+  // than 1 buffer
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [0,180) }");
 
   // Seek to 0 and check all buffers.
@@ -2713,6 +2795,7 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected1) {
   NewSegmentAppend("180K 210 240");
 
   // Should save the GOP at 90ms and the GOP at 180ms.
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [90,270) }");
   CheckExpectedBuffers("90K 120 150 180K 210 240");
   CheckNoNextBuffer();
@@ -2733,22 +2816,22 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected2) {
   SetMemoryLimit(1);
   NewSegmentAppend("90K 120 150");
 
-  // Should save the GOP at 90ms and the GOP at 270ms.
+  // GC should save the GOP at 90ms and 270ms, and will fail since GOP larger
+  // than 1 buffer
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [90,180) [270,360) }");
 
-  // Set memory limit to 100 and add 3 GOPs to the end of the selected range
-  // at 360ms, 450ms, and 540ms.
-  SetMemoryLimit(100);
+  // Add 3 GOPs to the end of the selected range at 360ms, 450ms, and 540ms.
   NewSegmentAppend("360K 390 420 450K 480 510 540K 570 600");
   CheckExpectedRangesByTimestamp("{ [90,180) [270,630) }");
 
-  // Constrain the memory limit again and overlap the GOP at 450ms to test
-  // deleting from the back.
-  SetMemoryLimit(1);
+  // Overlap the GOP at 450ms and garbage collect to test deleting from the
+  // back.
   NewSegmentAppend("450K 480 510");
+  GarbageCollect_ExpectFull();
 
-  // Should save GOP at 270ms and the GOP at 450ms.
-  CheckExpectedRangesByTimestamp("{ [270,360) [450,540) }");
+  // Should save GOPs from GOP at 270ms to GOP at 450ms.
+  CheckExpectedRangesByTimestamp("{ [270,540) }");
 }
 
 // Test saving the last GOP appended when it is the same as the GOP containing
@@ -2766,8 +2849,9 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected3) {
   SetMemoryLimit(1);
   NewSegmentAppend("0K 30");
 
-  // Should save the newly appended GOP, which is also the next GOP that will be
-  // returned from the seek request.
+  // GC should save the newly appended GOP, which is also the next GOP that
+  // will be returned from the seek request.
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [0,60) }");
 
   // Check the buffers in the range.
@@ -2777,8 +2861,9 @@ TEST_F(SourceBufferStreamTest, GarbageCollection_SaveAppendGOP_Selected3) {
   // Continue appending to this buffer.
   AppendBuffers("60 90");
 
-  // Should still save the rest of this GOP and should be able to fulfill the
-  // read.
+  // GC should still save the rest of this GOP and should be able to fulfill
+  // the read.
+  GarbageCollect_ExpectFull();
   CheckExpectedRangesByTimestamp("{ [0,120) }");
   CheckExpectedBuffers("60 90");
   CheckNoNextBuffer();