Frame continuity is now tested as soon as a frame is inserted into the FrameBuffer.

webrtc/modules/video_coding/frame_buffer2.h

Index: webrtc/modules/video_coding/frame_buffer2.h
diff --git a/webrtc/modules/video_coding/frame_buffer2.h b/webrtc/modules/video_coding/frame_buffer2.h
index d0f896133f116cecef7491070c1ebd6508ae28ff..19f5c5a95c01a6300583eae4b1fe5ea3ad887eaa 100644
--- a/webrtc/modules/video_coding/frame_buffer2.h
+++ b/webrtc/modules/video_coding/frame_buffer2.h
@@ -14,15 +14,16 @@
 #include <array>
 #include <map>
 #include <memory>
-#include <set>
 #include <utility>
 
 #include "webrtc/base/constructormagic.h"
 #include "webrtc/base/criticalsection.h"
 #include "webrtc/base/event.h"
 #include "webrtc/base/thread_annotations.h"
+#include "webrtc/modules/video_coding/frame_object.h"
 #include "webrtc/modules/video_coding/include/video_coding_defines.h"
 #include "webrtc/modules/video_coding/inter_frame_delay.h"
+#include "webrtc/modules/video_coding/sequence_number_util.h"
 
 namespace webrtc {
 
@@ -32,8 +33,6 @@ class VCMTiming;
 
 namespace video_coding {
 
-class FrameObject;
-
 class FrameBuffer {
  public:
   enum ReturnReason { kFrameFound, kTimeout, kStopped };
@@ -42,12 +41,13 @@ class FrameBuffer {
               VCMJitterEstimator* jitter_estimator,
               VCMTiming* timing);
 
-  // Insert a frame into the frame buffer.
-  void InsertFrame(std::unique_ptr<FrameObject> frame);
+  // Insert a frame into the frame buffer. Returns the picture id
+  // of the last continuous frame or -1 if there is no continuous frame.
+  int InsertFrame(std::unique_ptr<FrameObject> frame);
 
   // Get the next frame for decoding. Will return at latest after
   // |max_wait_time_ms|.
-  //  - If a frame is availiable within |max_wait_time_ms| it will return
+  //  - If a frame is available within |max_wait_time_ms| it will return
   //    kFrameFound and set |frame_out| to the resulting frame.
   //  - If no frame is available after |max_wait_time_ms| it will return
   //    kTimeout.
@@ -70,33 +70,83 @@ class FrameBuffer {
   void Stop();
 
  private:
-  // FrameKey is a pair of (picture id, spatial layer).
-  using FrameKey = std::pair<uint16_t, uint8_t>;
+  struct FrameKey {
+    FrameKey() : picture_id(0), spatial_layer(0) {}
+    FrameKey(uint16_t picture_id, uint8_t spatial_layer)
+        : picture_id(picture_id), spatial_layer(spatial_layer) {}
+
+    bool operator<(const FrameKey& other) const {

[stefan-webrtc, 2016/09/21 14:50:14]

I think rhs is a better name than other as it makes the side of the operator
more clear.

[philipel, 2016/09/22 11:18:39]

Done.

+      if (picture_id == other.picture_id)
+        return spatial_layer < other.spatial_layer;
+      return AheadOf(other.picture_id, picture_id);
+    }
+
+    bool operator<=(const FrameKey& other) const { return !(other < *this); }

[stefan-webrtc, 2016/09/21 14:50:14]

Same here.

[philipel, 2016/09/22 11:18:38]

Done.

+
+    uint16_t picture_id;
+    uint8_t spatial_layer;
+  };
+
+  struct FrameInfo {
+    static constexpr size_t kMaxNumDependentFrames = 5;
+
+    // Which other frames that have unfulfilled dependencies on this frame.
+    FrameKey dependent_frames[kMaxNumDependentFrames];

[stefan-webrtc, 2016/09/21 14:50:14]

Comment on if this array only contains direct dependencies or if it also
contains indirect dependencies. If the latter I guess 5 is way too little. Maybe
also mention why 5 was picked? Seems a bit low to me.

[philipel, 2016/09/22 11:18:38]

Updated comment, I think 5 should be enough but I increased it to 8.

+    size_t num_dependent_frames = 0;
+
+    // A frame is continiuous if have all its referenced/indirectly referenced

[stefan-webrtc, 2016/09/21 14:50:14]

continuous if it has

[philipel, 2016/09/22 11:18:39]

Done.

+    // frames.
+    //
+    // How many unfulfilled frames this frame have to become continuous.

[stefan-webrtc, 2016/09/21 14:50:14]

s/have/need?

[philipel, 2016/09/22 11:18:38]

this frame have until it becomes 

+    size_t num_missing_continuous = 0;

[stefan-webrtc, 2016/09/21 14:50:14]

num_missing_dependencies?

[philipel, 2016/09/22 11:18:39]

Not really, this hold how many referenced frames we are missing for this frame
to become continuous.

 
-  // Comparator used to sort frames, first on their picture id, and second
-  // on their spatial layer.
-  struct FrameComp {
-    bool operator()(const FrameKey& f1, const FrameKey& f2) const;
+    // A frame is decodable if all its referenced frames have been decoded.
+    //
+    // How many unfulfilled frames this frame have to become decodable.
+    size_t num_missing_decodable = 0;

[stefan-webrtc, 2016/09/21 14:50:14]

Not clear to me what the difference is between decodable and continuous

[philipel, 2016/09/22 11:18:38]

A frame is continuous if all frames this frame depend, either directly or
indirectly, has been received, or in other words, if we decode all of its
indireclty/directly referenced frames then this frame will become decodable.

A frame is decodable if it can be sent to the decoder now.

+
+    // If this frame is continuous or not.
+    bool continuous = false;

[stefan-webrtc, 2016/09/21 14:50:14]

Isn't this true whenever num_missing_continuous is 0?

[philipel, 2016/09/22 11:18:39]

No, since we create FrameInfos to hold backwards references for frames we have
not yet received it can be 0 even if it is not continuous. I guess this code be
encoded as |num_missing_continuous| = -1 instead.

+
+    // The actual FrameObject.
+    std::unique_ptr<FrameObject> frame;
   };
 
-  // Determines whether a frame is continuous.
-  bool IsContinuous(const FrameObject& frame) const
+  using FrameMap = std::map<FrameKey, FrameInfo>;
+
+  // Update all directly dependent and indirectly dependent frames and mark
+  // them as continuous if all their references has been fulfilled.
+  void PropagateContinuity(FrameMap::iterator start)
+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+  // Mark the frame as decoded and updates all directly dependent frames.

[stefan-webrtc, 2016/09/21 14:50:14]

"and update"

[philipel, 2016/09/22 11:18:38]

Done.

+  void PropagateDecodability(const FrameInfo& info)
+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+  // Advances |last_decoded_frame_it_| to |decoded| and remove old

[stefan-webrtc, 2016/09/21 14:50:14]

"and removes"

[philipel, 2016/09/22 11:18:39]

Done.

+  // frame info.

[stefan-webrtc, 2016/09/21 14:50:14]

FrameInfo

[philipel, 2016/09/22 11:18:38]

Done.

+  void AdvanceLastDecodedFrame(FrameMap::iterator decoded)
       EXCLUSIVE_LOCKS_REQUIRED(crit_);
 
-  // Keep track of decoded frames.
-  std::set<FrameKey, FrameComp> decoded_frames_ GUARDED_BY(crit_);
+  // Update the corresponding FrameInfo of |frame| and all FrameInfos that
+  // |frame| references.
+  // Return false if |frame| will never be decodable, true otherwise.
+  bool UpdateFrameInfoWithIncomingFrame(const FrameObject& frame,
+                                        FrameMap::iterator info)
+      EXCLUSIVE_LOCKS_REQUIRED(crit_);
 
-  // The actual buffer that holds the FrameObjects.
-  std::map<FrameKey, std::unique_ptr<FrameObject>, FrameComp> frames_
-      GUARDED_BY(crit_);
+  FrameMap frames_ GUARDED_BY(crit_);
 
   rtc::CriticalSection crit_;
   Clock* const clock_;
-  rtc::Event frame_inserted_event_;
+  rtc::Event new_countinuous_frame_event_;
   VCMJitterEstimator* const jitter_estimator_ GUARDED_BY(crit_);
   VCMTiming* const timing_ GUARDED_BY(crit_);
   VCMInterFrameDelay inter_frame_delay_ GUARDED_BY(crit_);
-  int newest_picture_id_ GUARDED_BY(crit_);
+  FrameMap::iterator last_decoded_frame_it_ GUARDED_BY(crit_);

[stefan-webrtc, 2016/09/21 14:50:14]

Does this mean we're always keeping the last decoded frame around until another
frame is decoded?

[philipel, 2016/09/22 11:18:38]

No, the actual FrameObject is passed to the decoder, but the FrameInfo remains
and this iterator keeps track of which frame that was.

+  FrameMap::iterator last_continuous_frame_it_ GUARDED_BY(crit_);
+  int num_frames_history_ GUARDED_BY(crit_);
+  int num_frames_buffered_ GUARDED_BY(crit_);
   bool stopped_ GUARDED_BY(crit_);
   VCMVideoProtection protection_mode_ GUARDED_BY(crit_);