--- a/dom/media/mediasource/TrackBuffersManager.cpp
+++ b/dom/media/mediasource/TrackBuffersManager.cpp
@@ -299,16 +299,17 @@ TrackBuffersManager::CompleteResetParser
     track->mHighestEndTimestamp.reset();
     // 5. Set the need random access point flag on all track buffers to true.
     track->mNeedRandomAccessPoint = true;
 
     // if we have been aborted, we may have pending frames that we are going
     // to discard now.
     track->mQueuedSamples.Clear();
     track->mLongestFrameDuration.reset();
+    track->mNextInsertionIndex.reset();
   }
   // 6. Remove all bytes from the input buffer.
   mIncomingBuffers.Clear();
   mInputBuffer = nullptr;
   if (mCurrentInputBuffer) {
     mCurrentInputBuffer->EvictAll();
     mCurrentInputBuffer = new SourceBufferResource(mType);
   }
@@ -451,40 +452,40 @@ TrackBuffersManager::CodedFrameRemoval(T
           removeEndTimestamp = TimeUnit::FromMicroseconds(frame->mTime);
           break;
         }
       }
     }
     // 3. Remove all media data, from this track buffer, that contain starting
     // timestamps greater than or equal to start and less than the remove end timestamp.
     TimeInterval removedInterval;
-    int32_t firstRemovedIndex = -1;
+    Maybe<uint32_t> firstRemovedIndex;
     TrackBuffer& data = track->mBuffers.LastElement();
     for (uint32_t i = 0; i < data.Length(); i++) {
       const auto& frame = data[i];
       if (frame->mTime >= start.ToMicroseconds() &&
           frame->mTime < removeEndTimestamp.ToMicroseconds()) {
-        if (firstRemovedIndex < 0) {
+        if (firstRemovedIndex.isNothing()) {
           removedInterval =
             TimeInterval(TimeUnit::FromMicroseconds(frame->mTime),
                          TimeUnit::FromMicroseconds(frame->mTime + frame->mDuration));
-          firstRemovedIndex = i;
+          firstRemovedIndex = Some(i);
         } else {
           removedInterval = removedInterval.Span(
             TimeInterval(TimeUnit::FromMicroseconds(frame->mTime),
                          TimeUnit::FromMicroseconds(frame->mTime + frame->mDuration)));
         }
         track->mSizeBuffer -= sizeof(*frame) + frame->mSize;
         data.RemoveElementAt(i);
       }
     }
     // 4. Remove decoding dependencies of the coded frames removed in the previous step:
     // Remove all coded frames between the coded frames removed in the previous step and the next random access point after those removed frames.
-    if (firstRemovedIndex >= 0) {
-      for (uint32_t i = firstRemovedIndex; i < data.Length(); i++) {
+    if (firstRemovedIndex.isSome()) {
+      for (uint32_t i = firstRemovedIndex.ref(); i < data.Length(); i++) {
         const auto& frame = data[i];
         if (frame->mKeyframe) {
           break;
         }
         removedInterval = removedInterval.Span(
           TimeInterval(TimeUnit::FromMicroseconds(frame->mTime),
                        TimeUnit::FromMicroseconds(frame->mTime + frame->mDuration)));
         track->mSizeBuffer -= sizeof(*frame) + frame->mSize;
@@ -517,16 +518,20 @@ TrackBuffersManager::CodedFrameRemoval(T
   if (HasVideo()) {
     MSE_DEBUG("after audio ranges=%s",
               DumpTimeRanges(mAudioTracks.mBufferedRanges).get());
   }
 
   // Update our reported total size.
   mSizeSourceBuffer = mVideoTracks.mSizeBuffer + mAudioTracks.mSizeBuffer;
 
+  // Reset our insertion indexes as they are now invalid.
+  mAudioTracks.mNextInsertionIndex.reset();
+  mVideoTracks.mNextInsertionIndex.reset();
+
   // Tell our demuxer that data was removed.
   mMediaSourceDemuxer->NotifyTimeRangesChanged();
 
   return dataRemoved;
 }
 
 nsRefPtr<TrackBuffersManager::AppendPromise>
 TrackBuffersManager::InitSegmentParserLoop()
@@ -1056,25 +1061,45 @@ TrackBuffersManager::CompleteCodedFrameP
   for (auto& sample : mVideoTracks.mQueuedSamples) {
     while (true) {
       if (!ProcessFrame(sample, mVideoTracks)) {
         break;
       }
     }
   }
   mVideoTracks.mQueuedSamples.Clear();
+#if defined(DEBUG)
+  if (HasVideo()) {
+    const auto& track = mVideoTracks.mBuffers.LastElement();
+    MOZ_ASSERT(track.IsEmpty() || track[0]->mKeyframe);
+    for (uint32_t i = 1; i < track.Length(); i++) {
+      MOZ_ASSERT((track[i-1]->mTrackInfo->GetID() == track[i]->mTrackInfo->GetID() && track[i-1]->mTimecode < track[i]->mTimecode) ||
+                 track[i]->mKeyframe);
+    }
+  }
+#endif
 
   for (auto& sample : mAudioTracks.mQueuedSamples) {
     while (true) {
       if (!ProcessFrame(sample, mAudioTracks)) {
         break;
       }
     }
   }
   mAudioTracks.mQueuedSamples.Clear();
+#if defined(DEBUG)
+  if (HasAudio()) {
+    const auto& track = mAudioTracks.mBuffers.LastElement();
+    MOZ_ASSERT(track.IsEmpty() || track[0]->mKeyframe);
+    for (uint32_t i = 1; i < track.Length(); i++) {
+      MOZ_ASSERT((track[i-1]->mTrackInfo->GetID() == track[i]->mTrackInfo->GetID() && track[i-1]->mTimecode < track[i]->mTimecode) ||
+                 track[i]->mKeyframe);
+    }
+  }
+#endif
 
   {
     MonitorAutoLock mon(mMonitor);
 
     // Save our final tracks buffered ranges.
     mVideoBufferedRanges = mVideoTracks.mBufferedRanges;
     mAudioBufferedRanges = mAudioTracks.mBufferedRanges;
     if (HasAudio()) {
@@ -1216,19 +1241,21 @@ TrackBuffersManager::ProcessFrame(MediaR
       track->mLastDecodeTimestamp.reset();
       // 3. Unset the last frame duration on all track buffers.
       track->mLastFrameDuration.reset();
       // 4. Unset the highest end timestamp on all track buffers.
       track->mHighestEndTimestamp.reset();
       // 5. Set the need random access point flag on all track buffers to true.
       track->mNeedRandomAccessPoint = true;
 
-      trackBuffer.mLongestFrameDuration.reset();
+      track->mLongestFrameDuration.reset();
+      track->mNextInsertionIndex.reset();
     }
-    MSE_DEBUG("Detected discontinuity. Restarting process");
+
+    MSE_DEBUG("Discontinuity detected. Restarting process");
     // 6. Jump to the Loop Top step above to restart processing of the current coded frame.
     return true;
   }
 
   // 7. Let frame end timestamp equal the sum of presentation timestamp and frame duration.
   TimeUnit frameEndTimestamp = presentationTimestamp + frameDuration;
 
   // 8. If presentation timestamp is less than appendWindowStart, then set the need random access point flag to true, drop the coded frame, and jump to the top of the loop to start processing the next coded frame.
@@ -1261,102 +1288,131 @@ TrackBuffersManager::ProcessFrame(MediaR
   // 11. Let spliced audio frame be an unset variable for holding audio splice information
   // 12. Let spliced timed text frame be an unset variable for holding timed text splice information
 
   // 13. If last decode timestamp for track buffer is unset and presentation timestamp falls within the presentation interval of a coded frame in track buffer,then run the following steps:
   // For now we only handle replacing existing frames with the new ones. So we
   // skip this step.
 
   // 14. Remove existing coded frames in track buffer:
+  //   a) If highest end timestamp for track buffer is not set:
+  //      Remove all coded frames from track buffer that have a presentation timestamp greater than or equal to presentation timestamp and less than frame end timestamp.
+  //   b) If highest end timestamp for track buffer is set and less than or equal to presentation timestamp:
+  //      Remove all coded frames from track buffer that have a presentation timestamp greater than or equal to highest end timestamp and less than frame end timestamp
 
   // There is an ambiguity on how to remove frames, which was lodged with:
   // https://www.w3.org/Bugs/Public/show_bug.cgi?id=28710, implementing as per
   // bug description.
-  int firstRemovedIndex = -1;
+  Maybe<uint32_t> firstRemovedIndex;
   TimeInterval removedInterval;
   TrackBuffer& data = trackBuffer.mBuffers.LastElement();
-  if (trackBuffer.mBufferedRanges.Contains(presentationTimestamp)) {
-    if (trackBuffer.mHighestEndTimestamp.isNothing()) {
-      for (uint32_t i = 0; i < data.Length(); i++) {
-        MediaRawData* sample = data[i].get();
-        if (sample->mTime >= presentationTimestamp.ToMicroseconds() &&
-            sample->mTime < frameEndTimestamp.ToMicroseconds()) {
-          if (firstRemovedIndex < 0) {
-            removedInterval =
-              TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
-                           TimeUnit::FromMicroseconds(sample->mTime + sample->mDuration));
-            firstRemovedIndex = i;
-          } else {
-            removedInterval = removedInterval.Span(
-              TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
-                           TimeUnit::FromMicroseconds(sample->mTime + sample->mDuration)));
-          }
-          trackBuffer.mSizeBuffer -= sizeof(*sample) + sample->mSize;
-          data.RemoveElementAt(i);
+  if (trackBuffer.mBufferedRanges.ContainsStrict(presentationTimestamp)) {
+    TimeUnit lowerBound =
+      trackBuffer.mHighestEndTimestamp.valueOr(presentationTimestamp);
+    for (uint32_t i = 0; i < data.Length();) {
+      MediaRawData* sample = data[i].get();
+      if (sample->mTime >= lowerBound.ToMicroseconds() &&
+          sample->mTime < frameEndTimestamp.ToMicroseconds()) {
+        if (firstRemovedIndex.isNothing()) {
+          removedInterval =
+            TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
+                         TimeUnit::FromMicroseconds(sample->GetEndTime()));
+          firstRemovedIndex = Some(i);
+        } else {
+          removedInterval = removedInterval.Span(
+            TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
+                         TimeUnit::FromMicroseconds(sample->GetEndTime())));
         }
-      }
-    } else if (trackBuffer.mHighestEndTimestamp.ref() <= presentationTimestamp) {
-      for (uint32_t i = 0; i < data.Length(); i++) {
-        MediaRawData* sample = data[i].get();
-        if (sample->mTime >= trackBuffer.mHighestEndTimestamp.ref().ToMicroseconds() &&
-            sample->mTime < frameEndTimestamp.ToMicroseconds()) {
-          if (firstRemovedIndex < 0) {
-            removedInterval =
-              TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
-                           TimeUnit::FromMicroseconds(sample->mTime + sample->mDuration));
-            firstRemovedIndex = i;
-          } else {
-            removedInterval = removedInterval.Span(
-              TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
-                           TimeUnit::FromMicroseconds(sample->mTime + sample->mDuration)));
-          }
-          trackBuffer.mSizeBuffer -= sizeof(*sample) + sample->mSize;
-          data.RemoveElementAt(i);
-        }
+        trackBuffer.mSizeBuffer -= sizeof(*sample) + sample->mSize;
+        MSE_DEBUGV("Overlapping frame:%u ([%f, %f))",
+                  i,
+                  TimeUnit::FromMicroseconds(sample->mTime).ToSeconds(),
+                  TimeUnit::FromMicroseconds(sample->GetEndTime()).ToSeconds());
+        data.RemoveElementAt(i);
+      } else {
+        i++;
       }
     }
   }
   // 15. Remove decoding dependencies of the coded frames removed in the previous step:
   // Remove all coded frames between the coded frames removed in the previous step and the next random access point after those removed frames.
-  if (firstRemovedIndex >= 0) {
-    for (uint32_t i = firstRemovedIndex; i < data.Length(); i++) {
-      MediaRawData* sample = data[i].get();
+  if (firstRemovedIndex.isSome()) {
+    uint32_t start = firstRemovedIndex.ref();
+    uint32_t end = start;
+    for (;end < data.Length(); end++) {
+      MediaRawData* sample = data[end].get();
       if (sample->mKeyframe) {
         break;
       }
       removedInterval = removedInterval.Span(
         TimeInterval(TimeUnit::FromMicroseconds(sample->mTime),
-                     TimeUnit::FromMicroseconds(sample->mTime + sample->mDuration)));
-      trackBuffer.mSizeBuffer -= sizeof(*aSample) + sample->mSize;
-      data.RemoveElementAt(i);
+                     TimeUnit::FromMicroseconds(sample->GetEndTime())));
+      trackBuffer.mSizeBuffer -= sizeof(*sample) + sample->mSize;
     }
+    data.RemoveElementsAt(start, end - start);
+
+    MSE_DEBUG("Removing undecodable frames from:%u (frames:%u) ([%f, %f))",
+              start, end - start,
+              removedInterval.mStart.ToSeconds(), removedInterval.mEnd.ToSeconds());
+
     // Update our buffered range to exclude the range just removed.
     trackBuffer.mBufferedRanges -= removedInterval;
+    MOZ_ASSERT(trackBuffer.mNextInsertionIndex.isNothing() ||
+               trackBuffer.mNextInsertionIndex.ref() <= start);
   }
 
   // 16. Add the coded frame with the presentation timestamp, decode timestamp, and frame duration to the track buffer.
   aSample->mTime = presentationTimestamp.ToMicroseconds();
   aSample->mTimecode = decodeTimestamp.ToMicroseconds();
   aSample->mTrackInfo = trackBuffer.mLastInfo;
 
-  if (firstRemovedIndex >= 0) {
-    data.InsertElementAt(firstRemovedIndex, aSample);
+  if (data.IsEmpty()) {
+    data.AppendElement(aSample);
+    MOZ_ASSERT(aSample->mKeyframe);
+    trackBuffer.mNextInsertionIndex = Some(data.Length());
+  } else if (trackBuffer.mNextInsertionIndex.isSome()) {
+    data.InsertElementAt(trackBuffer.mNextInsertionIndex.ref(), aSample);
+    MOZ_ASSERT(trackBuffer.mNextInsertionIndex.ref() == 0 ||
+               data[trackBuffer.mNextInsertionIndex.ref()]->mTrackInfo->GetID() == data[trackBuffer.mNextInsertionIndex.ref()-1]->mTrackInfo->GetID() ||
+               data[trackBuffer.mNextInsertionIndex.ref()]->mKeyframe);
+    trackBuffer.mNextInsertionIndex.ref()++;
+  } else if (presentationTimestamp < trackBuffer.mBufferedRanges.GetStart()) {
+    data.InsertElementAt(0, aSample);
+    MOZ_ASSERT(aSample->mKeyframe);
+    trackBuffer.mNextInsertionIndex = Some(size_t(1));
+  } else if (presentationTimestamp >= trackBuffer.mBufferedRanges.GetEnd()) {
+    data.AppendElement(aSample);
+    MOZ_ASSERT(data.Length() <= 2 ||
+               data[data.Length()-1]->mTrackInfo->GetID() == data[data.Length()-2]->mTrackInfo->GetID() ||
+               data[data.Length()-1]->mKeyframe);
+    trackBuffer.mNextInsertionIndex = Some(data.Length());
   } else {
-    if (data.IsEmpty() || aSample->mTimecode > data.LastElement()->mTimecode) {
-      data.AppendElement(aSample);
-    } else {
-      // Find where to insert frame.
-      for (uint32_t i = 0; i < data.Length(); i++) {
-        const auto& sample = data[i];
-        if (sample->mTimecode > aSample->mTimecode) {
-          data.InsertElementAt(i, aSample);
-          break;
-        }
+    // Find which discontinuity we should insert the frame before.
+    TimeInterval target;
+    for (const auto& interval : trackBuffer.mBufferedRanges) {
+      if (presentationTimestamp < interval.mStart) {
+        target = interval;
+        break;
       }
     }
+    for (uint32_t i = 0; i < data.Length(); i++) {
+      const nsRefPtr<MediaRawData>& sample = data[i];
+      TimeInterval sampleInterval{
+        TimeUnit::FromMicroseconds(sample->mTime),
+        TimeUnit::FromMicroseconds(sample->GetEndTime())};
+      if (target.Intersects(sampleInterval)) {
+        data.InsertElementAt(i, aSample);
+        MOZ_ASSERT(i != 0 &&
+                   (data[i]->mTrackInfo->GetID() == data[i-1]->mTrackInfo->GetID() ||
+                    data[i]->mKeyframe));
+        trackBuffer.mNextInsertionIndex = Some(size_t(i) + 1);
+        break;
+      }
+    }
+    MOZ_ASSERT(aSample->mKeyframe);
   }
   trackBuffer.mSizeBuffer += sizeof(*aSample) + aSample->mSize;
 
   // 17. Set last decode timestamp for track buffer to decode timestamp.
   trackBuffer.mLastDecodeTimestamp = Some(decodeTimestamp);
   // 18. Set last frame duration for track buffer to frame duration.
   trackBuffer.mLastFrameDuration =
     Some(TimeUnit::FromMicroseconds(aSample->mDuration));

--- a/dom/media/mediasource/TrackBuffersManager.h
+++ b/dom/media/mediasource/TrackBuffersManager.h
@@ -203,16 +203,20 @@ private:
     // Need random access point flag variable that keeps track of whether the
     // track buffer is waiting for a random access point coded frame.
     // The variable is initially set to true to indicate that random access
     // point coded frame is needed before anything can be added to the track
     // buffer.
     bool mNeedRandomAccessPoint;
     nsRefPtr<MediaTrackDemuxer> mDemuxer;
     MediaPromiseRequestHolder<MediaTrackDemuxer::SamplesPromise> mDemuxRequest;
+    // If set, position where the next contiguous frame will be inserted.
+    // If a discontinuity is detected, it will be unset and recalculated upon
+    // the next insertion.
+    Maybe<size_t> mNextInsertionIndex;
     // Samples just demuxed, but not yet parsed.
     TrackBuffer mQueuedSamples;
     // We only manage a single track of each type at this time.
     nsTArray<TrackBuffer> mBuffers;
     // Track buffer ranges variable that represents the presentation time ranges
     // occupied by the coded frames currently stored in the track buffer.
     TimeIntervals mBufferedRanges;
     // Byte size of all samples contained in this track buffer.