Add UnackedInvalidationSet class

Add a class that holds all locally unacknowledged invalidations and
their state. It is not used anywhere outside of tests.

This class is part of an attempt to refactor the InvalidatorStorage
class. That class stores pieces of the invalidations component's state
in preferences. It currently has some simple getter and setter methods
for things like the client ID and bootstrat data, and some more
complicated methods that related to storing unacked invalidations.

The goal is to eventually move the complex logic related to
invalidations out of the InvalidationStorage class, and into the
UnackedInvalidationSet class. The UnackedInvalidationSet class can
be owned by the SyncInvalidationListener, and periodically passed back
to the InvalidationStorage class on a separate thread for serialization.

The motivation for this refactoring is not merely aesthetic. The
UnackedInvalidationSet handles certain trickles related use cases
that the current storage system can not. Extending the existing storage
system to support these features would have made the code much harder to
understand. This approach lets us add functionality and simplify the
code at the same time.

BUG=233437

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

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

12 files changed, 788 insertions, 27 deletions

diff --git a/sync/internal_api/public/base/DEPS b/sync/internal_api/public/base/DEPS
index 047cfd4..9d46a8a 100644
--- a/sync/internal_api/public/base/DEPS
+++ b/sync/internal_api/public/base/DEPS
@@ -6,6 +6,7 @@ include_rules = [
   "-sync",
   "+sync/base",
   "+sync/internal_api/public/base",
+  "+sync/internal_api/public/util",
+  "+sync/notifier",
   "+sync/protocol",
-  "+sync/notifier"
 ]
diff --git a/sync/internal_api/public/base/invalidation.cc b/sync/internal_api/public/base/invalidation.cc
index 55fdcc7..d60a324 100644
--- a/sync/internal_api/public/base/invalidation.cc
+++ b/sync/internal_api/public/base/invalidation.cc
@@ -19,6 +19,7 @@ const char kObjectIdKey[] = "objectId";
 const char kIsUnknownVersionKey[] = "isUnknownVersion";
 const char kVersionKey[] = "version";
 const char kPayloadKey[] = "payload";
+const int64 kInvalidVersion = -1;
 }
 
 Invalidation Invalidation::Init(
@@ -30,7 +31,14 @@ Invalidation Invalidation::Init(
 
 Invalidation Invalidation::InitUnknownVersion(
     const invalidation::ObjectId& id) {
-  return Invalidation(id, true, -1, std::string(), AckHandle::CreateUnique());
+  return Invalidation(id, true, kInvalidVersion,
+                      std::string(), AckHandle::CreateUnique());
+}
+
+Invalidation Invalidation::InitFromDroppedInvalidation(
+    const Invalidation& dropped) {
+  return Invalidation(dropped.id_, true, kInvalidVersion,
+                      std::string(), dropped.ack_handle_);
 }
 
 scoped_ptr<Invalidation> Invalidation::InitFromValue(
@@ -52,7 +60,7 @@ scoped_ptr<Invalidation> Invalidation::InitFromValue(
     return scoped_ptr<Invalidation>(new Invalidation(
         id,
         true,
-        -1,
+        kInvalidVersion,
         std::string(),
         AckHandle::CreateUnique()));
   } else {
@@ -105,6 +113,28 @@ void Invalidation::set_ack_handle(const AckHandle& ack_handle) {
   ack_handle_ = ack_handle;
 }
 
+void Invalidation::set_ack_handler(syncer::WeakHandle<AckHandler> handler) {
+  ack_handler_ = handler;
+}
+
+bool Invalidation::SupportsAcknowledgement() const {
+  return ack_handler_.IsInitialized();
+}
+
+// void Invalidation::Acknowledge() const {
+//   if (SupportsAcknowledgement()) {
+//     ack_handler_.Call(FROM_HERE,
+//                       &AckHandler::Acknowledge,
+//                       id_,
+//                       ack_handle_);
+//   }
+// }
+
+// void Invalidation::Drop(DroppedInvalidationTracker* tracker) const {
+//   DCHECK(tracker->object_id() == object_id());
+//   tracker->Drop(ack_handler_, ack_handle_);
+// }
+
 bool Invalidation::Equals(const Invalidation& other) const {
   return id_ == other.id_
       && is_unknown_version_ == other.is_unknown_version_
diff --git a/sync/internal_api/public/base/invalidation.h b/sync/internal_api/public/base/invalidation.h
index 2b83564b..4e157e0 100644
--- a/sync/internal_api/public/base/invalidation.h
+++ b/sync/internal_api/public/base/invalidation.h
@@ -13,6 +13,7 @@
 #include "google/cacheinvalidation/include/types.h"
 #include "sync/base/sync_export.h"
 #include "sync/internal_api/public/base/ack_handle.h"
+#include "sync/internal_api/public/util/weak_handle.h"
 
 namespace syncer {
 
@@ -30,6 +31,7 @@ class SYNC_EXPORT Invalidation {
       int64 version,
       const std::string& payload);
   static Invalidation InitUnknownVersion(const invalidation::ObjectId& id);
+  static Invalidation InitFromDroppedInvalidation(const Invalidation& dropped);
   static scoped_ptr<Invalidation> InitFromValue(
       const base::DictionaryValue& value);
 
@@ -48,8 +50,19 @@ class SYNC_EXPORT Invalidation {
   const std::string& payload() const;
 
   const AckHandle& ack_handle() const;
+
+  // TODO(rlarocque): Remove this method and use AckHandlers instead.
   void set_ack_handle(const AckHandle& ack_handle);
 
+  void set_ack_handler(syncer::WeakHandle<AckHandler> ack_handler);
+
+  // True if this class has a valid AckHandler.
+  bool SupportsAcknowledgement() const;
+
+  // TODO(rlarocque): Re-enable these when we switch to AckHandlers.
+  // void Acknowledge() const;
+  // void Drop(DroppedInvalidationTracker* tracker) const;
+
   scoped_ptr<base::DictionaryValue> ToValue() const;
   std::string ToString() const;
 
@@ -76,6 +89,7 @@ class SYNC_EXPORT Invalidation {
 
   // A locally generated unique ID used to manage local acknowledgements.
   AckHandle ack_handle_;
+  syncer::WeakHandle<AckHandler> ack_handler_;
 };
 
 }  // namespace syncer
diff --git a/sync/notifier/invalidation_util.cc b/sync/notifier/invalidation_util.cc
index 7cc80d2..27acd38 100644
--- a/sync/notifier/invalidation_util.cc
+++ b/sync/notifier/invalidation_util.cc
@@ -12,6 +12,7 @@
 #include "base/values.h"
 #include "google/cacheinvalidation/include/types.h"
 #include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/invalidation.h"
 
 namespace invalidation {
 void PrintTo(const invalidation::ObjectId& id, std::ostream* os) {
@@ -27,6 +28,25 @@ bool ObjectIdLessThan::operator()(const invalidation::ObjectId& lhs,
          (lhs.source() == rhs.source() && lhs.name() < rhs.name());
 }
 
+bool InvalidationVersionLessThan::operator()(
+    const Invalidation& a,
+    const Invalidation& b) const {
+  DCHECK(a.object_id() == b.object_id())
+      << "a: " << ObjectIdToString(a.object_id()) << ", "
+      << "b: " << ObjectIdToString(a.object_id());
+
+  if (a.is_unknown_version() && !b.is_unknown_version())
+    return true;
+
+  if (!a.is_unknown_version() && b.is_unknown_version())
+    return false;
+
+  if (a.is_unknown_version() && b.is_unknown_version())
+    return false;
+
+  return a.version() < b.version();
+}
+
 bool RealModelTypeToObjectId(ModelType model_type,
                              invalidation::ObjectId* object_id) {
   std::string notification_type;
diff --git a/sync/notifier/invalidation_util.h b/sync/notifier/invalidation_util.h
index 670f612..699550e 100644
--- a/sync/notifier/invalidation_util.h
+++ b/sync/notifier/invalidation_util.h
@@ -32,11 +32,18 @@ SYNC_EXPORT_PRIVATE void PrintTo(const invalidation::ObjectId& id,
 
 namespace syncer {
 
+class Invalidation;
+
 struct SYNC_EXPORT ObjectIdLessThan {
   bool operator()(const invalidation::ObjectId& lhs,
                   const invalidation::ObjectId& rhs) const;
 };
 
+struct InvalidationVersionLessThan {
+  bool operator()(const syncer::Invalidation& a,
+                  const syncer::Invalidation& b) const;
+};
+
 typedef std::set<invalidation::ObjectId, ObjectIdLessThan> ObjectIdSet;
 
 SYNC_EXPORT bool RealModelTypeToObjectId(ModelType model_type,
diff --git a/sync/notifier/single_object_invalidation_set.cc b/sync/notifier/single_object_invalidation_set.cc
index 55202bb..6da3972 100644
--- a/sync/notifier/single_object_invalidation_set.cc
+++ b/sync/notifier/single_object_invalidation_set.cc
@@ -9,25 +9,6 @@
 
 namespace syncer {
 
-bool InvalidationVersionLessThan::operator()(
-    const Invalidation& a,
-    const Invalidation& b) {
-  DCHECK(a.object_id() == b.object_id())
-      << "a: " << ObjectIdToString(a.object_id()) << ", "
-      << "b: " << ObjectIdToString(a.object_id());
-
-  if (a.is_unknown_version() && !b.is_unknown_version())
-    return true;
-
-  if (!a.is_unknown_version() && b.is_unknown_version())
-    return false;
-
-  if (a.is_unknown_version() && b.is_unknown_version())
-    return false;
-
-  return a.version() < b.version();
-}
-
 SingleObjectInvalidationSet::SingleObjectInvalidationSet() {}
 
 SingleObjectInvalidationSet::~SingleObjectInvalidationSet() {}
diff --git a/sync/notifier/single_object_invalidation_set.h b/sync/notifier/single_object_invalidation_set.h
index c4dd051..e6f4d75 100644
--- a/sync/notifier/single_object_invalidation_set.h
+++ b/sync/notifier/single_object_invalidation_set.h
@@ -10,6 +10,7 @@
 #include "base/memory/scoped_ptr.h"
 #include "sync/base/sync_export.h"
 #include "sync/internal_api/public/base/invalidation.h"
+#include "sync/notifier/invalidation_util.h"
 
 namespace base {
 class ListValue;
@@ -17,10 +18,6 @@ class ListValue;
 
 namespace syncer {
 
-struct InvalidationVersionLessThan {
-  bool operator()(const Invalidation& a, const Invalidation& b);
-};
-
 // Holds a list of invalidations that all share the same Object ID.
 //
 // The list is kept sorted by version to make it easier to perform common
diff --git a/sync/notifier/unacked_invalidation_set.cc b/sync/notifier/unacked_invalidation_set.cc
new file mode 100644
index 0000000..705dbd2
--- /dev/null
+++ b/sync/notifier/unacked_invalidation_set.cc
@@ -0,0 +1,204 @@
+// Copyright 2013 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 "sync/notifier/unacked_invalidation_set.h"
+
+#include "base/strings/string_number_conversions.h"
+#include "sync/internal_api/public/base/ack_handle.h"
+#include "sync/notifier/object_id_invalidation_map.h"
+#include "sync/notifier/sync_invalidation_listener.h"
+
+namespace {
+
+const char kSourceKey[] = "source";
+const char kNameKey[] = "name";
+const char kInvalidationListKey[] = "invalidation-list";
+
+}  // namespace
+
+namespace syncer {
+
+const size_t UnackedInvalidationSet::kMaxBufferedInvalidations = 5;
+
+// static
+UnackedInvalidationSet::UnackedInvalidationSet(
+    invalidation::ObjectId id)
+    : registered_(false),
+      object_id_(id) {}
+
+UnackedInvalidationSet::~UnackedInvalidationSet() {}
+
+const invalidation::ObjectId& UnackedInvalidationSet::object_id() const {
+  return object_id_;
+}
+
+void UnackedInvalidationSet::Add(
+    const Invalidation& invalidation) {
+  SingleObjectInvalidationSet set;
+  set.Insert(invalidation);
+  AddSet(set);
+  if (!registered_)
+    Truncate(kMaxBufferedInvalidations);
+}
+
+void UnackedInvalidationSet::AddSet(
+    const SingleObjectInvalidationSet& invalidations) {
+  invalidations_.insert(invalidations.begin(), invalidations.end());
+  if (!registered_)
+    Truncate(kMaxBufferedInvalidations);
+}
+
+void UnackedInvalidationSet::ExportInvalidations(
+    WeakHandle<AckHandler> ack_handler,
+    ObjectIdInvalidationMap* out) const {
+  for (SingleObjectInvalidationSet::const_iterator it = invalidations_.begin();
+       it != invalidations_.end(); ++it) {
+    // Copy the invalidation and set the copy's ack_handler.
+    Invalidation inv(*it);
+    inv.set_ack_handler(ack_handler);
+    out->Insert(inv);
+  }
+}
+
+void UnackedInvalidationSet::Clear() {
+  invalidations_.clear();
+}
+
+void UnackedInvalidationSet::SetHandlerIsRegistered() {
+  registered_ = true;
+}
+
+void UnackedInvalidationSet::SetHandlerIsUnregistered() {
+  registered_ = false;
+  Truncate(kMaxBufferedInvalidations);
+}
+
+// Removes the matching ack handle from the list.
+void UnackedInvalidationSet::Acknowledge(const AckHandle& handle) {
+  bool handle_found = false;
+  for (SingleObjectInvalidationSet::const_iterator it = invalidations_.begin();
+       it != invalidations_.end(); ++it) {
+    if (it->ack_handle().Equals(handle)) {
+      invalidations_.erase(*it);
+      handle_found = true;
+      break;
+    }
+  }
+  DLOG_IF(WARNING, !handle_found)
+      << "Unrecognized to ack for object " << ObjectIdToString(object_id_);
+  (void)handle_found;  // Silence unused variable warning in release builds.
+}
+
+// Erase the invalidation with matching ack handle from the list.  Also creates
+// an 'UnknownVersion' invalidation with the same ack handle and places it at
+// the beginning of the list.  If an unknown version invalidation currently
+// exists, it is replaced.
+void UnackedInvalidationSet::Drop(const AckHandle& handle) {
+  SingleObjectInvalidationSet::const_iterator it;
+  for (it = invalidations_.begin(); it != invalidations_.end(); ++it) {
+    if (it->ack_handle().Equals(handle)) {
+      break;
+    }
+  }
+  if (it == invalidations_.end()) {
+    DLOG(WARNING) << "Unrecognized drop request for object "
+                  << ObjectIdToString(object_id_);
+    return;
+  }
+
+  Invalidation unknown_version = Invalidation::InitFromDroppedInvalidation(*it);
+  invalidations_.erase(*it);
+
+  // If an unknown version is in the list, we remove it so we can replace it.
+  if (!invalidations_.empty() && invalidations_.begin()->is_unknown_version()) {
+    invalidations_.erase(*invalidations_.begin());
+  }
+
+  invalidations_.insert(unknown_version);
+}
+
+scoped_ptr<base::DictionaryValue> UnackedInvalidationSet::ToValue() const {
+  scoped_ptr<base::DictionaryValue> value(new base::DictionaryValue);
+  value->SetString(kSourceKey, base::IntToString(object_id_.source()));
+  value->SetString(kNameKey, object_id_.name());
+
+  scoped_ptr<base::ListValue> list_value(new ListValue);
+  for (InvalidationsSet::const_iterator it = invalidations_.begin();
+       it != invalidations_.end(); ++it) {
+    list_value->Append(it->ToValue().release());
+  }
+  value->Set(kInvalidationListKey, list_value.release());
+
+  return value.Pass();
+}
+
+bool UnackedInvalidationSet::ResetFromValue(
+    const base::DictionaryValue& value) {
+  std::string source_str;
+  if (!value.GetString(kSourceKey, &source_str)) {
+    DLOG(WARNING) << "Unable to deserialize source";
+    return false;
+  }
+  int source = 0;
+  if (!base::StringToInt(source_str, &source)) {
+    DLOG(WARNING) << "Invalid source: " << source_str;
+    return false;
+  }
+  std::string name;
+  if (!value.GetString(kNameKey, &name)) {
+    DLOG(WARNING) << "Unable to deserialize name";
+    return false;
+  }
+  object_id_ = invalidation::ObjectId(source, name);
+  const base::ListValue* invalidation_list = NULL;
+  if (!value.GetList(kInvalidationListKey, &invalidation_list)
+      || !ResetListFromValue(*invalidation_list)) {
+    // Earlier versions of this class did not set this field, so we don't treat
+    // parsing errors here as a fatal failure.
+    DLOG(WARNING) << "Unable to deserialize invalidation list.";
+  }
+  return true;
+}
+
+bool UnackedInvalidationSet::ResetListFromValue(
+    const base::ListValue& list) {
+  for (size_t i = 0; i < list.GetSize(); ++i) {
+    const base::DictionaryValue* dict;
+    if (!list.GetDictionary(i, &dict)) {
+      DLOG(WARNING) << "Failed to get invalidation dictionary at index " << i;
+      return false;
+    }
+    scoped_ptr<Invalidation> invalidation = Invalidation::InitFromValue(*dict);
+    if (!invalidation) {
+      DLOG(WARNING) << "Failed to parse invalidation at index " << i;
+      return false;
+    }
+    invalidations_.insert(*invalidation.get());
+  }
+  return true;
+}
+
+void UnackedInvalidationSet::Truncate(size_t max_size) {
+  DCHECK_GT(max_size, 0U);
+
+  if (invalidations_.size() <= max_size) {
+    return;
+  }
+
+  while (invalidations_.size() > max_size) {
+    invalidations_.erase(*invalidations_.begin());
+  }
+
+  // We dropped some invalidations.  We remember the fact that an unknown
+  // amount of information has been lost by ensuring this list begins with
+  // an UnknownVersion invalidation.  We remove the oldest remaining
+  // invalidation to make room for it.
+  invalidation::ObjectId id = invalidations_.begin()->object_id();
+  invalidations_.erase(*invalidations_.begin());
+
+  Invalidation unknown_version = Invalidation::InitUnknownVersion(id);
+  invalidations_.insert(unknown_version);
+}
+
+}  // namespace syncer
diff --git a/sync/notifier/unacked_invalidation_set.h b/sync/notifier/unacked_invalidation_set.h
new file mode 100644
index 0000000..2824e6a
--- /dev/null
+++ b/sync/notifier/unacked_invalidation_set.h
@@ -0,0 +1,113 @@
+// Copyright 2013 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 SYNC_NOTIFIER_UNACKED_INVALIDATION_SET_H_
+#define SYNC_NOTIFIER_UNACKED_INVALIDATION_SET_H_
+
+#include <vector>
+
+#include "sync/base/sync_export.h"
+#include "sync/internal_api/public/base/invalidation.h"
+#include "sync/internal_api/public/util/weak_handle.h"
+#include "sync/notifier/invalidation_util.h"
+
+namespace base {
+class DictionaryValue;
+}  // namespace base
+
+namespace syncer {
+
+class SingleObjectInvalidationSet;
+class ObjectIdInvalidationMap;
+class AckHandle;
+
+// Manages the set of invalidations that are awaiting local acknowledgement for
+// a particular ObjectId.  This set of invalidations will be persisted across
+// restarts, though this class is not directly responsible for that.
+class SYNC_EXPORT UnackedInvalidationSet {
+ public:
+  static const size_t kMaxBufferedInvalidations;
+
+  UnackedInvalidationSet(invalidation::ObjectId id);
+  ~UnackedInvalidationSet();
+
+  // Returns the ObjectID of the invalidations this class is tracking.
+  const invalidation::ObjectId& object_id() const;
+
+  // Adds a new invalidation to the set awaiting acknowledgement.
+  void Add(const Invalidation& invalidation);
+
+  // Adds many new invalidations to the set awaiting acknowledgement.
+  void AddSet(const SingleObjectInvalidationSet& invalidations);
+
+  // Exports the set of invalidations awaiting acknowledgement as an
+  // ObjectIdInvalidationMap.  Each of these invalidations will be associated
+  // with the given |ack_handler|.
+  //
+  // The contents of the UnackedInvalidationSet are not directly modified by
+  // this procedure, but the AckHandles stored in those exported invalidations
+  // are likely to end up back here in calls to Acknowledge() or Drop().
+  void ExportInvalidations(WeakHandle<AckHandler> ack_handler,
+                           ObjectIdInvalidationMap* out) const;
+
+  // Removes all stored invalidations from this object.
+  void Clear();
+
+  // Indicates that a handler has registered to handle these invalidations.
+  //
+  // Registrations with the invalidations server persist across restarts, but
+  // registrations from InvalidationHandlers to the InvalidationService are not.
+  // In the time immediately after a restart, it's possible that the server
+  // will send us invalidations, and we won't have a handler to send them to.
+  //
+  // The SetIsRegistered() call indicates that this period has come to an end.
+  // There is now a handler that can receive these invalidations.  Once this
+  // function has been called, the kMaxBufferedInvalidations limit will be
+  // ignored.  It is assumed that the handler will manage its own buffer size.
+  void SetHandlerIsRegistered();
+
+  // Indicates that the handler has now unregistered itself.
+  //
+  // This causes the object to resume enforcement of the
+  // kMaxBufferedInvalidations limit.
+  void SetHandlerIsUnregistered();
+
+  // Given an AckHandle belonging to one of the contained invalidations, finds
+  // the invalidation and drops it from the list.  It is considered to be
+  // acknowledged, so there is no need to continue maintaining its state.
+  void Acknowledge(const AckHandle& handle);
+
+  // Given an AckHandle belonging to one of the contained invalidations, finds
+  // the invalidation, drops it from the list, and adds additional state to
+  // indicate that this invalidation has been lost without being acted on.
+  void Drop(const AckHandle& handle);
+
+  scoped_ptr<base::DictionaryValue> ToValue() const;
+  bool ResetFromValue(const base::DictionaryValue& value);
+
+ private:
+  // Allow this test helper to have access to our internals.
+  friend class UnackedInvalidationSetEqMatcher;
+
+  typedef std::set<Invalidation, InvalidationVersionLessThan> InvalidationsSet;
+
+  bool ResetListFromValue(const base::ListValue& value);
+
+  // Limits the list size to the given maximum.  This function will correctly
+  // update this class' internal data to indicate if invalidations have been
+  // dropped.
+  void Truncate(size_t max_size);
+
+  bool registered_;
+  invalidation::ObjectId object_id_;
+  InvalidationsSet invalidations_;
+};
+
+typedef std::map<invalidation::ObjectId,
+                 UnackedInvalidationSet,
+                 ObjectIdLessThan> UnackedInvalidationsMap;
+
+}  // namespace syncer
+
+#endif  // SYNC_NOTIFIER_UNACKED_INVALIDATION_SET_H_
diff --git a/sync/notifier/unacked_invalidation_set_unittest.cc b/sync/notifier/unacked_invalidation_set_unittest.cc
new file mode 100644
index 0000000..70cd232
--- /dev/null
+++ b/sync/notifier/unacked_invalidation_set_unittest.cc
@@ -0,0 +1,391 @@
+// Copyright 2013 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 "sync/notifier/unacked_invalidation_set.h"
+
+#include "base/json/json_string_value_serializer.h"
+#include "sync/notifier/object_id_invalidation_map.h"
+#include "sync/notifier/single_object_invalidation_set.h"
+#include "testing/gmock/include/gmock/gmock-matchers.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace syncer {
+
+// Start with some helper functions and classes.
+
+using ::testing::MakeMatcher;
+using ::testing::MatchResultListener;
+using ::testing::Matcher;
+using ::testing::MatcherInterface;
+using ::testing::PrintToString;
+
+void PrintTo(
+    const UnackedInvalidationSet& invalidations, ::std::ostream* os);
+
+void PrintTo(
+    const UnackedInvalidationsMap& map, ::std::ostream* os);
+
+::testing::Matcher<const UnackedInvalidationSet&> Eq(
+    const UnackedInvalidationSet& expected);
+
+::testing::Matcher<const UnackedInvalidationsMap&> Eq(
+    const UnackedInvalidationsMap& expected);
+
+class UnackedInvalidationSetEqMatcher
+    : public testing::MatcherInterface<const UnackedInvalidationSet&> {
+ public:
+  explicit UnackedInvalidationSetEqMatcher(
+      const UnackedInvalidationSet& expected);
+
+  virtual bool MatchAndExplain(
+      const UnackedInvalidationSet& actual,
+      MatchResultListener* listener) const OVERRIDE;
+  virtual void DescribeTo(::std::ostream* os) const OVERRIDE;
+  virtual void DescribeNegationTo(::std::ostream* os) const OVERRIDE;
+
+ private:
+  const UnackedInvalidationSet expected_;
+
+  DISALLOW_COPY_AND_ASSIGN(UnackedInvalidationSetEqMatcher);
+};
+
+UnackedInvalidationSetEqMatcher::UnackedInvalidationSetEqMatcher(
+    const UnackedInvalidationSet& expected)
+  : expected_(expected) {}
+
+namespace {
+
+struct InvalidationEq {
+  bool operator()(const syncer::Invalidation& a,
+                  const syncer::Invalidation& b) const {
+    return a.Equals(b);
+  }
+};
+
+}  // namespace
+
+bool UnackedInvalidationSetEqMatcher::MatchAndExplain(
+    const UnackedInvalidationSet& actual,
+    MatchResultListener* listener) const {
+  // Use our friendship with this class to compare the internals of two
+  // instances.
+  //
+  // Note that the registration status is intentionally not considered
+  // when performing this comparison.
+  return expected_.object_id_ == actual.object_id_
+      && std::equal(expected_.invalidations_.begin(),
+                    expected_.invalidations_.end(),
+                    actual.invalidations_.begin(),
+                    InvalidationEq());
+}
+
+void UnackedInvalidationSetEqMatcher::DescribeTo(::std::ostream* os) const {
+  *os << " is equal to " << PrintToString(expected_);
+}
+
+void UnackedInvalidationSetEqMatcher::DescribeNegationTo(
+    ::std::ostream* os) const {
+  *os << " isn't equal to " << PrintToString(expected_);
+}
+
+namespace {
+
+ObjectIdInvalidationMap UnackedInvalidationsMapToObjectIdInvalidationMap(
+    const UnackedInvalidationsMap& state_map) {
+  ObjectIdInvalidationMap object_id_invalidation_map;
+  for (UnackedInvalidationsMap::const_iterator it = state_map.begin();
+       it != state_map.end(); ++it) {
+    it->second.ExportInvalidations(syncer::WeakHandle<AckHandler>(),
+                                   &object_id_invalidation_map);
+  }
+  return object_id_invalidation_map;
+}
+
+class UnackedInvalidationsMapEqMatcher
+    : public testing::MatcherInterface<const UnackedInvalidationsMap&> {
+ public:
+  explicit UnackedInvalidationsMapEqMatcher(
+      const UnackedInvalidationsMap& expected);
+
+  virtual bool MatchAndExplain(const UnackedInvalidationsMap& actual,
+                               MatchResultListener* listener) const;
+  virtual void DescribeTo(::std::ostream* os) const;
+  virtual void DescribeNegationTo(::std::ostream* os) const;
+
+ private:
+  const UnackedInvalidationsMap expected_;
+
+  DISALLOW_COPY_AND_ASSIGN(UnackedInvalidationsMapEqMatcher);
+};
+
+UnackedInvalidationsMapEqMatcher::UnackedInvalidationsMapEqMatcher(
+    const UnackedInvalidationsMap& expected)
+    : expected_(expected) {
+}
+
+bool UnackedInvalidationsMapEqMatcher::MatchAndExplain(
+    const UnackedInvalidationsMap& actual,
+    MatchResultListener* listener) const {
+  ObjectIdInvalidationMap expected_inv =
+      UnackedInvalidationsMapToObjectIdInvalidationMap(expected_);
+  ObjectIdInvalidationMap actual_inv =
+      UnackedInvalidationsMapToObjectIdInvalidationMap(actual);
+
+  return expected_inv == actual_inv;
+}
+
+void UnackedInvalidationsMapEqMatcher::DescribeTo(
+    ::std::ostream* os) const {
+  *os << " is equal to " << PrintToString(expected_);
+}
+
+void UnackedInvalidationsMapEqMatcher::DescribeNegationTo(
+    ::std::ostream* os) const {
+  *os << " isn't equal to " << PrintToString(expected_);
+}
+
+}  // namespace
+
+void PrintTo(const UnackedInvalidationSet& invalidations,
+             ::std::ostream* os) {
+  scoped_ptr<base::DictionaryValue> value = invalidations.ToValue();
+
+  std::string output;
+  JSONStringValueSerializer serializer(&output);
+  serializer.set_pretty_print(true);
+  serializer.Serialize(*value.get());
+
+  (*os) << output;
+}
+
+void PrintTo(const UnackedInvalidationsMap& map, ::std::ostream* os) {
+  scoped_ptr<base::ListValue> list(new base::ListValue);
+  for (UnackedInvalidationsMap::const_iterator it = map.begin();
+       it != map.end(); ++it) {
+    list->Append(it->second.ToValue().release());
+  }
+
+  std::string output;
+  JSONStringValueSerializer serializer(&output);
+  serializer.set_pretty_print(true);
+  serializer.Serialize(*list.get());
+
+  (*os) << output;
+}
+
+Matcher<const UnackedInvalidationSet&> Eq(
+    const UnackedInvalidationSet& expected) {
+  return MakeMatcher(new UnackedInvalidationSetEqMatcher(expected));
+}
+
+Matcher<const UnackedInvalidationsMap&> Eq(
+    const UnackedInvalidationsMap& expected) {
+  return MakeMatcher(new UnackedInvalidationsMapEqMatcher(expected));
+}
+
+class UnackedInvalidationSetTest : public testing::Test {
+ public:
+  UnackedInvalidationSetTest()
+      : kObjectId_(10, "ASDF"),
+        unacked_invalidations_(kObjectId_) {}
+
+  SingleObjectInvalidationSet GetStoredInvalidations() {
+    ObjectIdInvalidationMap map;
+    unacked_invalidations_.ExportInvalidations(WeakHandle<AckHandler>(), &map);
+    ObjectIdSet ids = map.GetObjectIds();
+    if (ids.find(kObjectId_) != ids.end()) {
+      return map.ForObject(kObjectId_);
+    } else {
+      return SingleObjectInvalidationSet();
+    }
+  }
+
+  const invalidation::ObjectId kObjectId_;
+  UnackedInvalidationSet unacked_invalidations_;
+};
+
+namespace {
+
+// Test storage and retrieval of zero invalidations.
+TEST_F(UnackedInvalidationSetTest, Empty) {
+  EXPECT_EQ(0U, GetStoredInvalidations().GetSize());
+}
+
+// Test storage and retrieval of a single invalidation.
+TEST_F(UnackedInvalidationSetTest, OneInvalidation) {
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  unacked_invalidations_.Add(inv1);
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(1U, set.GetSize());
+  EXPECT_FALSE(set.StartsWithUnknownVersion());
+}
+
+// Test that calling Clear() returns us to the empty state.
+TEST_F(UnackedInvalidationSetTest, Clear) {
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  unacked_invalidations_.Add(inv1);
+  unacked_invalidations_.Clear();
+
+  EXPECT_EQ(0U, GetStoredInvalidations().GetSize());
+}
+
+// Test that repeated unknown version invalidations are squashed together.
+TEST_F(UnackedInvalidationSetTest, UnknownVersions) {
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  Invalidation inv2 = Invalidation::InitUnknownVersion(kObjectId_);
+  Invalidation inv3 = Invalidation::InitUnknownVersion(kObjectId_);
+  unacked_invalidations_.Add(inv1);
+  unacked_invalidations_.Add(inv2);
+  unacked_invalidations_.Add(inv3);
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(2U, set.GetSize());
+  EXPECT_TRUE(set.StartsWithUnknownVersion());
+}
+
+// Tests that no truncation occurs while we're under the limit.
+TEST_F(UnackedInvalidationSetTest, NoTruncation) {
+  size_t kMax = UnackedInvalidationSet::kMaxBufferedInvalidations;
+
+  for (size_t i = 0; i < kMax; ++i) {
+    Invalidation inv = Invalidation::Init(kObjectId_, i, "payload");
+    unacked_invalidations_.Add(inv);
+  }
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(kMax, set.GetSize());
+  EXPECT_FALSE(set.StartsWithUnknownVersion());
+  EXPECT_EQ(0, set.begin()->version());
+  EXPECT_EQ(kMax-1, static_cast<size_t>(set.rbegin()->version()));
+}
+
+// Test that truncation happens as we reach the limit.
+TEST_F(UnackedInvalidationSetTest, Truncation) {
+  size_t kMax = UnackedInvalidationSet::kMaxBufferedInvalidations;
+
+  for (size_t i = 0; i < kMax + 1; ++i) {
+    Invalidation inv = Invalidation::Init(kObjectId_, i, "payload");
+    unacked_invalidations_.Add(inv);
+  }
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(kMax, set.GetSize());
+  EXPECT_TRUE(set.StartsWithUnknownVersion());
+  EXPECT_TRUE(set.begin()->is_unknown_version());
+  EXPECT_EQ(kMax, static_cast<size_t>(set.rbegin()->version()));
+}
+
+// Test that we don't truncate while a handler is registered.
+TEST_F(UnackedInvalidationSetTest, RegistrationAndTruncation) {
+  unacked_invalidations_.SetHandlerIsRegistered();
+
+  size_t kMax = UnackedInvalidationSet::kMaxBufferedInvalidations;
+
+  for (size_t i = 0; i < kMax + 1; ++i) {
+    Invalidation inv = Invalidation::Init(kObjectId_, i, "payload");
+    unacked_invalidations_.Add(inv);
+  }
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(kMax+1, set.GetSize());
+  EXPECT_FALSE(set.StartsWithUnknownVersion());
+  EXPECT_EQ(0, set.begin()->version());
+  EXPECT_EQ(kMax, static_cast<size_t>(set.rbegin()->version()));
+
+  // Unregistering should re-enable truncation.
+  unacked_invalidations_.SetHandlerIsUnregistered();
+  SingleObjectInvalidationSet set2 = GetStoredInvalidations();
+  ASSERT_EQ(kMax, set2.GetSize());
+  EXPECT_TRUE(set2.StartsWithUnknownVersion());
+  EXPECT_TRUE(set2.begin()->is_unknown_version());
+  EXPECT_EQ(kMax, static_cast<size_t>(set2.rbegin()->version()));
+}
+
+// Test acknowledgement.
+TEST_F(UnackedInvalidationSetTest, Acknowledge) {
+  // inv2 is included in this test just to make sure invalidations that
+  // are supposed to be unaffected by this operation will be unaffected.
+
+  // We don't expect to be receiving acks or drops unless this flag is set.
+  // Not that it makes much of a difference in behavior.
+  unacked_invalidations_.SetHandlerIsRegistered();
+
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  Invalidation inv2 = Invalidation::InitUnknownVersion(kObjectId_);
+  AckHandle inv1_handle = inv1.ack_handle();
+
+  unacked_invalidations_.Add(inv1);
+  unacked_invalidations_.Add(inv2);
+
+  unacked_invalidations_.Acknowledge(inv1_handle);
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  EXPECT_EQ(1U, set.GetSize());
+  EXPECT_TRUE(set.StartsWithUnknownVersion());
+}
+
+// Test drops.
+TEST_F(UnackedInvalidationSetTest, Drop) {
+  // inv2 is included in this test just to make sure invalidations that
+  // are supposed to be unaffected by this operation will be unaffected.
+
+  // We don't expect to be receiving acks or drops unless this flag is set.
+  // Not that it makes much of a difference in behavior.
+  unacked_invalidations_.SetHandlerIsRegistered();
+
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  Invalidation inv2 = Invalidation::Init(kObjectId_, 15, "payload");
+  AckHandle inv1_handle = inv1.ack_handle();
+
+  unacked_invalidations_.Add(inv1);
+  unacked_invalidations_.Add(inv2);
+
+  unacked_invalidations_.Drop(inv1_handle);
+
+  SingleObjectInvalidationSet set = GetStoredInvalidations();
+  ASSERT_EQ(2U, set.GetSize());
+  EXPECT_TRUE(set.StartsWithUnknownVersion());
+  EXPECT_EQ(15, set.rbegin()->version());
+}
+
+class UnackedInvalidationSetSerializationTest
+    : public UnackedInvalidationSetTest {
+ public:
+  UnackedInvalidationSet SerializeDeserialize() {
+    scoped_ptr<base::DictionaryValue> value = unacked_invalidations_.ToValue();
+    UnackedInvalidationSet deserialized(kObjectId_);
+    deserialized.ResetFromValue(*value.get());
+    return deserialized;
+  }
+};
+
+TEST_F(UnackedInvalidationSetSerializationTest, Empty) {
+  UnackedInvalidationSet deserialized = SerializeDeserialize();
+  EXPECT_THAT(unacked_invalidations_, Eq(deserialized));
+}
+
+TEST_F(UnackedInvalidationSetSerializationTest, OneInvalidation) {
+  Invalidation inv = Invalidation::Init(kObjectId_, 10, "payload");
+  unacked_invalidations_.Add(inv);
+
+  UnackedInvalidationSet deserialized = SerializeDeserialize();
+  EXPECT_THAT(unacked_invalidations_, Eq(deserialized));
+}
+
+TEST_F(UnackedInvalidationSetSerializationTest, WithUnknownVersion) {
+  Invalidation inv1 = Invalidation::Init(kObjectId_, 10, "payload");
+  Invalidation inv2 = Invalidation::InitUnknownVersion(kObjectId_);
+  Invalidation inv3 = Invalidation::InitUnknownVersion(kObjectId_);
+  unacked_invalidations_.Add(inv1);
+  unacked_invalidations_.Add(inv2);
+  unacked_invalidations_.Add(inv3);
+
+  UnackedInvalidationSet deserialized = SerializeDeserialize();
+  EXPECT_THAT(unacked_invalidations_, Eq(deserialized));
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/sync_notifier.gypi b/sync/sync_notifier.gypi
index 365ed33..f3dfb72 100644
--- a/sync/sync_notifier.gypi
+++ b/sync/sync_notifier.gypi
@@ -28,6 +28,8 @@
     'notifier/invalidation_state_tracker.h',
     'notifier/invalidation_util.cc',
     'notifier/invalidation_util.h',
+    'notifier/unacked_invalidation_set.cc',
+    'notifier/unacked_invalidation_set.h',
     'notifier/invalidator.h',
     'notifier/invalidator_registrar.cc',
     'notifier/invalidator_registrar.h',
diff --git a/sync/sync_tests.gypi b/sync/sync_tests.gypi
index 535042f..56ddeed 100644
--- a/sync/sync_tests.gypi
+++ b/sync/sync_tests.gypi
@@ -331,12 +331,13 @@
               'notifier/invalidator_registrar_unittest.cc',
               'notifier/non_blocking_invalidator_unittest.cc',
               'notifier/object_id_invalidation_map_unittest.cc',
-              'notifier/single_object_invalidation_set_unittest.cc',
               'notifier/p2p_invalidator_unittest.cc',
               'notifier/push_client_channel_unittest.cc',
               'notifier/registration_manager_unittest.cc',
+              'notifier/single_object_invalidation_set_unittest.cc',
               'notifier/sync_invalidation_listener_unittest.cc',
               'notifier/sync_system_resources_unittest.cc',
+              'notifier/unacked_invalidation_set_unittest.cc',
             ],
           }],
         ],