Refactor common invalidation framework types

Convert the Invalidation struct into a class.  This allows us to hide
its members, so we can do things like add a DCHECK to make sure we never
access the payload field of an unknown version invalidation.  It also
lets us use factory methods and constructors to initialize it rather
than having to initialize its fields one by one.

Convert the ObjectIdInvalidationMap from a typedef into a class.  Unlike
the typedef, the class supports multiple invalidations for the same
object ID.  It uses the newly introduced SingleObjectInvalidationSet to
manage the set of invalidations belonging to a particular ID.  Note that
the current code still sends only one invalidation per type; that will
be changed in a future commit.

The end goal of this refactoring is to make these classes smarter so
they can help manage the complexity that will be introduced when we
implement invalidation 'trickles' support.

Note that this commit changes the on-disk format for invalidations, so
any invalidations currently stored in the profile may be lost on
upgrade.  There should be no other notable changes to invalidations
behavior in this CL.

TBR=brettw
BUG=233437

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

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

19 files changed, 746 insertions, 429 deletions

diff --git a/sync/notifier/invalidation_notifier_unittest.cc b/sync/notifier/invalidation_notifier_unittest.cc
index 623bfa9..1f14319 100644
--- a/sync/notifier/invalidation_notifier_unittest.cc
+++ b/sync/notifier/invalidation_notifier_unittest.cc
@@ -16,7 +16,6 @@
 #include "sync/notifier/fake_invalidation_state_tracker.h"
 #include "sync/notifier/invalidation_state_tracker.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/invalidator_registrar.cc b/sync/notifier/invalidator_registrar.cc
index c2a18f9..43afa6e 100644
--- a/sync/notifier/invalidator_registrar.cc
+++ b/sync/notifier/invalidator_registrar.cc
@@ -8,6 +8,7 @@
 #include <utility>
 
 #include "base/logging.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace syncer {
 
@@ -17,7 +18,7 @@ InvalidatorRegistrar::InvalidatorRegistrar()
 InvalidatorRegistrar::~InvalidatorRegistrar() {
   DCHECK(thread_checker_.CalledOnValidThread());
   CHECK(!handlers_.might_have_observers());
-  // |id_to_handler_map_| may be non-empty but that's okay.
+  CHECK(handler_to_ids_map_.empty());
 }
 
 void InvalidatorRegistrar::RegisterHandler(InvalidationHandler* handler) {
@@ -33,29 +34,29 @@ void InvalidatorRegistrar::UpdateRegisteredIds(
   DCHECK(thread_checker_.CalledOnValidThread());
   CHECK(handler);
   CHECK(handlers_.HasObserver(handler));
-  // Remove all existing entries for |handler|.
-  for (IdHandlerMap::iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ) {
-    if (it->second == handler) {
-      IdHandlerMap::iterator erase_it = it;
-      ++it;
-      id_to_handler_map_.erase(erase_it);
-    } else {
-      ++it;
+
+  for (HandlerIdsMap::const_iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    if (it->first == handler) {
+      continue;
     }
-  }
 
-  // Now add the entries for |handler|. We keep track of the last insertion
-  // point so we only traverse the map once to insert all the new entries.
-  IdHandlerMap::iterator insert_it = id_to_handler_map_.begin();
-  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    insert_it =
-        id_to_handler_map_.insert(insert_it, std::make_pair(*it, handler));
-    CHECK_EQ(handler, insert_it->second)
+    std::vector<invalidation::ObjectId> intersection;
+    std::set_intersection(
+        it->second.begin(), it->second.end(),
+        ids.begin(), ids.end(),
+        intersection.begin(), ObjectIdLessThan());
+    CHECK(intersection.empty())
         << "Duplicate registration: trying to register "
-        << ObjectIdToString(insert_it->first) << " for "
+        << ObjectIdToString(*intersection.begin()) << " for "
         << handler << " when it's already registered for "
-        << insert_it->second;
+        << it->first;
+  }
+
+  if (ids.empty()) {
+    handler_to_ids_map_.erase(handler);
+  } else {
+    handler_to_ids_map_[handler] = ids;
   }
 }
 
@@ -64,27 +65,26 @@ void InvalidatorRegistrar::UnregisterHandler(InvalidationHandler* handler) {
   CHECK(handler);
   CHECK(handlers_.HasObserver(handler));
   handlers_.RemoveObserver(handler);
+  handler_to_ids_map_.erase(handler);
 }
 
 ObjectIdSet InvalidatorRegistrar::GetRegisteredIds(
     InvalidationHandler* handler) const {
   DCHECK(thread_checker_.CalledOnValidThread());
-  ObjectIdSet registered_ids;
-  for (IdHandlerMap::const_iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ++it) {
-    if (it->second == handler) {
-      registered_ids.insert(it->first);
-    }
+  HandlerIdsMap::const_iterator lookup = handler_to_ids_map_.find(handler);
+  if (lookup != handler_to_ids_map_.end()) {
+    return lookup->second;
+  } else {
+    return ObjectIdSet();
   }
-  return registered_ids;
 }
 
 ObjectIdSet InvalidatorRegistrar::GetAllRegisteredIds() const {
   DCHECK(thread_checker_.CalledOnValidThread());
   ObjectIdSet registered_ids;
-  for (IdHandlerMap::const_iterator it = id_to_handler_map_.begin();
-       it != id_to_handler_map_.end(); ++it) {
-    registered_ids.insert(it->first);
+  for (HandlerIdsMap::const_iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    registered_ids.insert(it->second.begin(), it->second.end());
   }
   return registered_ids;
 }
@@ -97,23 +97,13 @@ void InvalidatorRegistrar::DispatchInvalidationsToHandlers(
     return;
   }
 
-  typedef std::map<InvalidationHandler*, ObjectIdInvalidationMap> DispatchMap;
-  DispatchMap dispatch_map;
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    InvalidationHandler* const handler = ObjectIdToHandler(it->first);
-    // Filter out invalidations for IDs with no handler.
-    if (handler)
-      dispatch_map[handler].insert(*it);
-  }
-
-  // Emit invalidations only for handlers in |handlers_|.
-  ObserverListBase<InvalidationHandler>::Iterator it(handlers_);
-  InvalidationHandler* handler = NULL;
-  while ((handler = it.GetNext()) != NULL) {
-    DispatchMap::const_iterator dispatch_it = dispatch_map.find(handler);
-    if (dispatch_it != dispatch_map.end())
-      handler->OnIncomingInvalidation(dispatch_it->second);
+  for (HandlerIdsMap::iterator it = handler_to_ids_map_.begin();
+       it != handler_to_ids_map_.end(); ++it) {
+    ObjectIdInvalidationMap to_emit =
+        invalidation_map.GetSubsetWithObjectIds(it->second);
+    if (!to_emit.Empty()) {
+      it->first->OnIncomingInvalidation(to_emit);
+    }
   }
 }
 
@@ -142,11 +132,4 @@ void InvalidatorRegistrar::DetachFromThreadForTest() {
   thread_checker_.DetachFromThread();
 }
 
-InvalidationHandler* InvalidatorRegistrar::ObjectIdToHandler(
-    const invalidation::ObjectId& id) {
-  DCHECK(thread_checker_.CalledOnValidThread());
-  IdHandlerMap::const_iterator it = id_to_handler_map_.find(id);
-  return (it == id_to_handler_map_.end()) ? NULL : it->second;
-}
-
 }  // namespace syncer
diff --git a/sync/notifier/invalidator_registrar.h b/sync/notifier/invalidator_registrar.h
index f2a3c63..fb6b388 100644
--- a/sync/notifier/invalidator_registrar.h
+++ b/sync/notifier/invalidator_registrar.h
@@ -13,7 +13,6 @@
 #include "sync/base/sync_export.h"
 #include "sync/notifier/invalidation_handler.h"
 #include "sync/notifier/invalidation_util.h"
-#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace invalidation {
 class ObjectId;
@@ -21,6 +20,8 @@ class ObjectId;
 
 namespace syncer {
 
+class ObjectIdInvalidationMap;
+
 // A helper class for implementations of the Invalidator interface.  It helps
 // keep track of registered handlers and which object ID registrations are
 // associated with which handlers, so implementors can just reuse the logic
@@ -76,15 +77,11 @@ class SYNC_EXPORT InvalidatorRegistrar {
   void DetachFromThreadForTest();
 
  private:
-  typedef std::map<invalidation::ObjectId, InvalidationHandler*,
-                   ObjectIdLessThan>
-      IdHandlerMap;
-
-  InvalidationHandler* ObjectIdToHandler(const invalidation::ObjectId& id);
+  typedef std::map<InvalidationHandler*, ObjectIdSet> HandlerIdsMap;
 
   base::ThreadChecker thread_checker_;
   ObserverList<InvalidationHandler> handlers_;
-  IdHandlerMap id_to_handler_map_;
+  HandlerIdsMap handler_to_ids_map_;
   InvalidatorState state_;
 
   DISALLOW_COPY_AND_ASSIGN(InvalidatorRegistrar);
diff --git a/sync/notifier/invalidator_registrar_unittest.cc b/sync/notifier/invalidator_registrar_unittest.cc
index ad22247..7a01401 100644
--- a/sync/notifier/invalidator_registrar_unittest.cc
+++ b/sync/notifier/invalidator_registrar_unittest.cc
@@ -9,7 +9,6 @@
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidator_registrar.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/invalidator_test_template.h b/sync/notifier/invalidator_test_template.h
index 0353000..b86cf50 100644
--- a/sync/notifier/invalidator_test_template.h
+++ b/sync/notifier/invalidator_test_template.h
@@ -81,11 +81,11 @@
 #include "base/compiler_specific.h"
 #include "google/cacheinvalidation/include/types.h"
 #include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/invalidation_test_util.h"
+#include "sync/internal_api/public/base/object_id_invalidation_map_test_util.h"
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/fake_invalidation_state_tracker.h"
 #include "sync/notifier/invalidator.h"
-#include "sync/notifier/object_id_invalidation_map.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
@@ -135,13 +135,13 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
 
   invalidator->RegisterHandler(&handler);
 
-  ObjectIdInvalidationMap states;
-  states[this->id1].payload = "1";
-  states[this->id2].payload = "2";
-  states[this->id3].payload = "3";
+  ObjectIdInvalidationMap invalidation_map;
+  invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+  invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+  invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
 
   // Should be ignored since no IDs are registered to |handler|.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(0, handler.GetInvalidationCount());
 
   ObjectIdSet ids;
@@ -152,25 +152,26 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
   this->delegate_.TriggerOnInvalidatorStateChange(INVALIDATIONS_ENABLED);
   EXPECT_EQ(INVALIDATIONS_ENABLED, handler.GetInvalidatorState());
 
-  ObjectIdInvalidationMap expected_states;
-  expected_states[this->id1].payload = "1";
-  expected_states[this->id2].payload = "2";
+  ObjectIdInvalidationMap expected_invalidations;
+  expected_invalidations.Insert(Invalidation::Init(this->id1, 1, "1"));
+  expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
 
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(1, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   ids.erase(this->id1);
   ids.insert(this->id3);
   invalidator->UpdateRegisteredIds(&handler, ids);
 
-  expected_states.erase(this->id1);
-  expected_states[this->id3].payload = "3";
+  expected_invalidations = ObjectIdInvalidationMap();
+  expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
+  expected_invalidations.Insert(Invalidation::Init(this->id3, 3, "3"));
 
   // Removed object IDs should not be notified, newly-added ones should.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
-  EXPECT_THAT(expected_states, Eq(handler.GetLastInvalidationMap()));
+  EXPECT_THAT(expected_invalidations, Eq(handler.GetLastInvalidationMap()));
 
   this->delegate_.TriggerOnInvalidatorStateChange(TRANSIENT_INVALIDATION_ERROR);
   EXPECT_EQ(TRANSIENT_INVALIDATION_ERROR,
@@ -184,7 +185,7 @@ TYPED_TEST_P(InvalidatorTest, Basic) {
   invalidator->UnregisterHandler(&handler);
 
   // Should be ignored since |handler| isn't registered anymore.
-  this->delegate_.TriggerOnIncomingInvalidation(states);
+  this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
   EXPECT_EQ(2, handler.GetInvalidationCount());
 }
 
@@ -236,25 +237,26 @@ TYPED_TEST_P(InvalidatorTest, MultipleHandlers) {
   EXPECT_EQ(TRANSIENT_INVALIDATION_ERROR, handler4.GetInvalidatorState());
 
   {
-    ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    states[this->id4].payload = "4";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
+    ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
+    invalidation_map.Insert(Invalidation::Init(this->id4, 4, "4"));
 
-    ObjectIdInvalidationMap expected_states;
-    expected_states[this->id1].payload = "1";
-    expected_states[this->id2].payload = "2";
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
+
+    ObjectIdInvalidationMap expected_invalidations;
+    expected_invalidations.Insert(Invalidation::Init(this->id1, 1, "1"));
+    expected_invalidations.Insert(Invalidation::Init(this->id2, 2, "2"));
 
     EXPECT_EQ(1, handler1.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler1.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler1.GetLastInvalidationMap()));
 
-    expected_states.clear();
-    expected_states[this->id3].payload = "3";
+    expected_invalidations = ObjectIdInvalidationMap();
+    expected_invalidations.Insert(Invalidation::Init(this->id3, 3, "3"));
 
     EXPECT_EQ(1, handler2.GetInvalidationCount());
-    EXPECT_THAT(expected_states, Eq(handler2.GetLastInvalidationMap()));
+    EXPECT_THAT(expected_invalidations, Eq(handler2.GetLastInvalidationMap()));
 
     EXPECT_EQ(0, handler3.GetInvalidationCount());
     EXPECT_EQ(0, handler4.GetInvalidationCount());
@@ -306,11 +308,11 @@ TYPED_TEST_P(InvalidatorTest, EmptySetUnregisters) {
   EXPECT_EQ(INVALIDATIONS_ENABLED, handler2.GetInvalidatorState());
 
   {
-    ObjectIdInvalidationMap states;
-    states[this->id1].payload = "1";
-    states[this->id2].payload = "2";
-    states[this->id3].payload = "3";
-    this->delegate_.TriggerOnIncomingInvalidation(states);
+    ObjectIdInvalidationMap invalidation_map;
+    invalidation_map.Insert(Invalidation::Init(this->id1, 1, "1"));
+    invalidation_map.Insert(Invalidation::Init(this->id2, 2, "2"));
+    invalidation_map.Insert(Invalidation::Init(this->id3, 3, "3"));
+    this->delegate_.TriggerOnIncomingInvalidation(invalidation_map);
     EXPECT_EQ(0, handler1.GetInvalidationCount());
     EXPECT_EQ(1, handler2.GetInvalidationCount());
   }
diff --git a/sync/notifier/non_blocking_invalidator_unittest.cc b/sync/notifier/non_blocking_invalidator_unittest.cc
index f463077..e9cf31e 100644
--- a/sync/notifier/non_blocking_invalidator_unittest.cc
+++ b/sync/notifier/non_blocking_invalidator_unittest.cc
@@ -17,7 +17,6 @@
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidation_state_tracker.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
diff --git a/sync/notifier/object_id_invalidation_map.cc b/sync/notifier/object_id_invalidation_map.cc
index bde2e4c..e1f584d 100644
--- a/sync/notifier/object_id_invalidation_map.cc
+++ b/sync/notifier/object_id_invalidation_map.cc
@@ -1,93 +1,112 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// 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/object_id_invalidation_map.h"
 
-#include <algorithm>
-
-#include "base/compiler_specific.h"
-#include "base/values.h"
+#include "base/json/json_string_value_serializer.h"
 
 namespace syncer {
 
-ObjectIdSet ObjectIdInvalidationMapToSet(
-    const ObjectIdInvalidationMap& invalidation_map) {
-  ObjectIdSet ids;
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    ids.insert(it->first);
+// static
+ObjectIdInvalidationMap ObjectIdInvalidationMap::InvalidateAll(
+    const ObjectIdSet& ids) {
+  ObjectIdInvalidationMap invalidate_all;
+  for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
+    invalidate_all.Insert(Invalidation::InitUnknownVersion(*it));
   }
-  return ids;
+  return invalidate_all;
+}
+
+ObjectIdInvalidationMap::ObjectIdInvalidationMap() {}
+
+ObjectIdInvalidationMap::~ObjectIdInvalidationMap() {}
+
+ObjectIdSet ObjectIdInvalidationMap::GetObjectIds() const {
+  ObjectIdSet ret;
+  for (IdToListMap::const_iterator it = map_.begin(); it != map_.end(); ++it) {
+    ret.insert(it->first);
+  }
+  return ret;
+}
+
+bool ObjectIdInvalidationMap::Empty() const {
+  return map_.empty();
+}
+
+void ObjectIdInvalidationMap::Insert(const Invalidation& invalidation) {
+  map_[invalidation.object_id()].Insert(invalidation);
 }
 
-ObjectIdInvalidationMap ObjectIdSetToInvalidationMap(
-    const ObjectIdSet& ids, int64 version, const std::string& payload) {
-  ObjectIdInvalidationMap invalidation_map;
+ObjectIdInvalidationMap ObjectIdInvalidationMap::GetSubsetWithObjectIds(
+    const ObjectIdSet& ids) const {
+  IdToListMap new_map;
   for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    // TODO(dcheng): Do we need to provide a way to set AckHandle?
-    invalidation_map[*it].version = version;
-    invalidation_map[*it].payload = payload;
+    IdToListMap::const_iterator lookup = map_.find(*it);
+    if (lookup != map_.end()) {
+      new_map[*it] = lookup->second;
+    }
   }
-  return invalidation_map;
+  return ObjectIdInvalidationMap(new_map);
 }
 
-namespace {
+const SingleObjectInvalidationSet& ObjectIdInvalidationMap::ForObject(
+    invalidation::ObjectId id) const {
+  IdToListMap::const_iterator lookup = map_.find(id);
+  DCHECK(lookup != map_.end());
+  DCHECK(!lookup->second.IsEmpty());
+  return lookup->second;
+}
 
-struct ObjectIdInvalidationMapValueEquals {
-  bool operator()(const ObjectIdInvalidationMap::value_type& value1,
-                  const ObjectIdInvalidationMap::value_type& value2) const {
-    return
-        (value1.first == value2.first) &&
-        value1.second.Equals(value2.second);
+void ObjectIdInvalidationMap::GetAllInvalidations(
+    std::vector<syncer::Invalidation>* out) const {
+  for (IdToListMap::const_iterator it = map_.begin(); it != map_.end(); ++it) {
+    out->insert(out->begin(), it->second.begin(), it->second.end());
   }
-};
-
-}  // namespace
-
-bool ObjectIdInvalidationMapEquals(
-    const ObjectIdInvalidationMap& invalidation_map1,
-    const ObjectIdInvalidationMap& invalidation_map2) {
-  return
-      (invalidation_map1.size() == invalidation_map2.size()) &&
-      std::equal(invalidation_map1.begin(), invalidation_map1.end(),
-                 invalidation_map2.begin(),
-                 ObjectIdInvalidationMapValueEquals());
 }
 
-scoped_ptr<base::ListValue> ObjectIdInvalidationMapToValue(
-    const ObjectIdInvalidationMap& invalidation_map) {
+bool ObjectIdInvalidationMap::operator==(
+    const ObjectIdInvalidationMap& other) const {
+  return map_ == other.map_;
+}
+
+scoped_ptr<base::ListValue> ObjectIdInvalidationMap::ToValue() const {
   scoped_ptr<base::ListValue> value(new base::ListValue());
-  for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-       it != invalidation_map.end(); ++it) {
-    base::DictionaryValue* entry = new base::DictionaryValue();
-    entry->Set("objectId", ObjectIdToValue(it->first).release());
-    entry->Set("state", it->second.ToValue().release());
-    value->Append(entry);
+  for (IdToListMap::const_iterator it1 = map_.begin();
+       it1 != map_.end(); ++it1) {
+    for (SingleObjectInvalidationSet::const_iterator it2 =
+         it1->second.begin(); it2 != it1->second.end(); ++it2) {
+      value->Append(it2->ToValue().release());
+    }
   }
   return value.Pass();
 }
 
-bool ObjectIdInvalidationMapFromValue(const base::ListValue& value,
-                               ObjectIdInvalidationMap* out) {
-  out->clear();
-  for (base::ListValue::const_iterator it = value.begin();
-       it != value.end(); ++it) {
-    const base::DictionaryValue* entry = NULL;
-    const base::DictionaryValue* id_value = NULL;
-    const base::DictionaryValue* invalidation_value = NULL;
-    invalidation::ObjectId id;
-    Invalidation invalidation;
-    if (!(*it)->GetAsDictionary(&entry) ||
-        !entry->GetDictionary("objectId", &id_value) ||
-        !entry->GetDictionary("state", &invalidation_value) ||
-        !ObjectIdFromValue(*id_value, &id) ||
-        !invalidation.ResetFromValue(*invalidation_value)) {
+bool ObjectIdInvalidationMap::ResetFromValue(const base::ListValue& value) {
+  map_.clear();
+  for (size_t i = 0; i < value.GetSize(); ++i) {
+    const DictionaryValue* dict;
+    if (!value.GetDictionary(i, &dict)) {
       return false;
     }
-    ignore_result(out->insert(std::make_pair(id, invalidation)));
+    scoped_ptr<Invalidation> invalidation = Invalidation::InitFromValue(*dict);
+    if (!invalidation) {
+      return false;
+    }
+    Insert(*invalidation.get());
   }
   return true;
 }
 
+std::string ObjectIdInvalidationMap::ToString() const {
+  std::string output;
+  JSONStringValueSerializer serializer(&output);
+  serializer.set_pretty_print(true);
+  serializer.Serialize(*ToValue().get());
+  return output;
+}
+
+ObjectIdInvalidationMap::ObjectIdInvalidationMap(const IdToListMap& map)
+  : map_(map) {}
+
 }  // namespace syncer
diff --git a/sync/notifier/object_id_invalidation_map.h b/sync/notifier/object_id_invalidation_map.h
index bb97fb3..c17e101 100644
--- a/sync/notifier/object_id_invalidation_map.h
+++ b/sync/notifier/object_id_invalidation_map.h
@@ -1,4 +1,4 @@
-// Copyright 2012 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -6,40 +6,67 @@
 #define SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_H_
 
 #include <map>
-#include <string>
+#include <vector>
 
-#include "base/basictypes.h"
-#include "base/memory/scoped_ptr.h"
-#include "google/cacheinvalidation/include/types.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;
-}  // namespace base
+#include "sync/notifier/single_object_invalidation_set.h"
 
 namespace syncer {
 
-typedef std::map<invalidation::ObjectId,
-                 Invalidation,
-                 ObjectIdLessThan> ObjectIdInvalidationMap;
+// A set of notifications with some helper methods to organize them by object ID
+// and version number.
+class SYNC_EXPORT ObjectIdInvalidationMap {
+  public:
+   // Creates an invalidation map that includes an 'unknown version'
+   // invalidation for each specified ID in |ids|.
+   static ObjectIdInvalidationMap InvalidateAll(const ObjectIdSet& ids);
+
+   ObjectIdInvalidationMap();
+   ~ObjectIdInvalidationMap();
+
+   // Returns set of ObjectIds for which at least one invalidation is present.
+   ObjectIdSet GetObjectIds() const;
+
+   // Returns true if this map contains no invalidations.
+   bool Empty() const;
+
+   // Returns true if both maps contain the same set of invalidations.
+   bool operator==(const ObjectIdInvalidationMap& other) const;
+
+   // Inserts a new invalidation into this map.
+   void Insert(const Invalidation& invalidation);
+
+   // Returns a new map containing the subset of invaliations from this map
+   // whose IDs were in the specified |ids| set.
+   ObjectIdInvalidationMap GetSubsetWithObjectIds(const ObjectIdSet& ids) const;
+
+   // Returns the subset of invalidations with IDs matching |id|.
+   const SingleObjectInvalidationSet& ForObject(
+       invalidation::ObjectId id) const;
+
+   // Returns the contents of this map in a single vector.
+   void GetAllInvalidations(std::vector<syncer::Invalidation>* out) const;
+
+   // Serialize this map to a value.
+   scoped_ptr<base::ListValue> ToValue() const;
+
+   // Deserialize the value into a map and use it to re-initialize this object.
+   bool ResetFromValue(const base::ListValue& value);
 
-// Converts between ObjectIdInvalidationMaps and ObjectIdSets.
-ObjectIdSet ObjectIdInvalidationMapToSet(
-    const ObjectIdInvalidationMap& invalidation_map);
-SYNC_EXPORT ObjectIdInvalidationMap ObjectIdSetToInvalidationMap(
-    const ObjectIdSet& ids, int64 version, const std::string& payload);
+   // Prints the contentes of this map as a human-readable string.
+   std::string ToString() const;
 
-SYNC_EXPORT bool ObjectIdInvalidationMapEquals(
-    const ObjectIdInvalidationMap& invalidation_map1,
-    const ObjectIdInvalidationMap& invalidation_map2);
+  private:
+   typedef std::map<invalidation::ObjectId,
+                    SingleObjectInvalidationSet,
+                    ObjectIdLessThan> IdToListMap;
 
-scoped_ptr<base::ListValue> ObjectIdInvalidationMapToValue(
-    const ObjectIdInvalidationMap& invalidation_map);
+   ObjectIdInvalidationMap(const IdToListMap& map);
 
-bool ObjectIdInvalidationMapFromValue(const base::ListValue& value,
-                               ObjectIdInvalidationMap* out);
+   IdToListMap map_;
+};
 
 }  // namespace syncer
 
diff --git a/sync/notifier/object_id_invalidation_map_test_util.cc b/sync/notifier/object_id_invalidation_map_test_util.cc
deleted file mode 100644
index f2f8285..0000000
--- a/sync/notifier/object_id_invalidation_map_test_util.cc
+++ /dev/null
@@ -1,114 +0,0 @@
-// Copyright (c) 2012 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/object_id_invalidation_map_test_util.h"
-
-#include <algorithm>
-
-#include "base/basictypes.h"
-
-namespace syncer {
-
-using ::testing::MakeMatcher;
-using ::testing::MatchResultListener;
-using ::testing::Matcher;
-using ::testing::MatcherInterface;
-using ::testing::PrintToString;
-
-namespace {
-
-class ObjectIdInvalidationMapEqMatcher
-    : public MatcherInterface<const ObjectIdInvalidationMap&> {
- public:
-  explicit ObjectIdInvalidationMapEqMatcher(
-      const ObjectIdInvalidationMap& expected);
-
-  virtual bool MatchAndExplain(const ObjectIdInvalidationMap& actual,
-                               MatchResultListener* listener) const;
-  virtual void DescribeTo(::std::ostream* os) const;
-  virtual void DescribeNegationTo(::std::ostream* os) const;
-
- private:
-  const ObjectIdInvalidationMap expected_;
-
-  DISALLOW_COPY_AND_ASSIGN(ObjectIdInvalidationMapEqMatcher);
-};
-
-ObjectIdInvalidationMapEqMatcher::ObjectIdInvalidationMapEqMatcher(
-    const ObjectIdInvalidationMap& expected) : expected_(expected) {
-}
-
-bool ObjectIdInvalidationMapEqMatcher::MatchAndExplain(
-    const ObjectIdInvalidationMap& actual,
-    MatchResultListener* listener) const {
-  ObjectIdInvalidationMap expected_only;
-  ObjectIdInvalidationMap actual_only;
-  typedef std::pair<invalidation::ObjectId,
-                    std::pair<Invalidation, Invalidation> >
-      ValueDifference;
-  std::vector<ValueDifference> value_differences;
-
-  std::set_difference(expected_.begin(), expected_.end(),
-                      actual.begin(), actual.end(),
-                      std::inserter(expected_only, expected_only.begin()),
-                      expected_.value_comp());
-  std::set_difference(actual.begin(), actual.end(),
-                      expected_.begin(), expected_.end(),
-                      std::inserter(actual_only, actual_only.begin()),
-                      actual.value_comp());
-
-  for (ObjectIdInvalidationMap::const_iterator it = expected_.begin();
-       it != expected_.end(); ++it) {
-    ObjectIdInvalidationMap::const_iterator find_it =
-        actual.find(it->first);
-    if (find_it != actual.end() &&
-        !Matches(Eq(it->second))(find_it->second)) {
-      value_differences.push_back(std::make_pair(
-          it->first, std::make_pair(it->second, find_it->second)));
-    }
-  }
-
-  if (expected_only.empty() && actual_only.empty() && value_differences.empty())
-    return true;
-
-  bool printed_header = false;
-  if (!actual_only.empty()) {
-    *listener << " which has these unexpected elements: "
-              << PrintToString(actual_only);
-    printed_header = true;
-  }
-
-  if (!expected_only.empty()) {
-    *listener << (printed_header ? ",\nand" : "which")
-              << " doesn't have these expected elements: "
-              << PrintToString(expected_only);
-    printed_header = true;
-  }
-
-  if (!value_differences.empty()) {
-    *listener << (printed_header ? ",\nand" : "which")
-              << " differ in the following values: "
-              << PrintToString(value_differences);
-  }
-
-  return false;
-}
-
-void ObjectIdInvalidationMapEqMatcher::DescribeTo(::std::ostream* os) const {
-  *os << " is equal to " << PrintToString(expected_);
-}
-
-void ObjectIdInvalidationMapEqMatcher::DescribeNegationTo
-(::std::ostream* os) const {
-  *os << " isn't equal to " << PrintToString(expected_);
-}
-
-}  // namespace
-
-Matcher<const ObjectIdInvalidationMap&> Eq(
-    const ObjectIdInvalidationMap& expected) {
-  return MakeMatcher(new ObjectIdInvalidationMapEqMatcher(expected));
-}
-
-}  // namespace syncer
diff --git a/sync/notifier/object_id_invalidation_map_test_util.h b/sync/notifier/object_id_invalidation_map_test_util.h
deleted file mode 100644
index 0217da8..0000000
--- a/sync/notifier/object_id_invalidation_map_test_util.h
+++ /dev/null
@@ -1,21 +0,0 @@
-// Copyright (c) 2012 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_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
-#define SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
-
-// Convince googletest to use the correct overload for PrintTo().
-#include "sync/internal_api/public/base/invalidation_test_util.h"
-#include "sync/internal_api/public/base/model_type.h"
-#include "sync/notifier/object_id_invalidation_map.h"
-#include "testing/gmock/include/gmock/gmock.h"
-
-namespace syncer {
-
-::testing::Matcher<const ObjectIdInvalidationMap&> Eq(
-    const ObjectIdInvalidationMap& expected);
-
-}  // namespace syncer
-
-#endif  // SYNC_NOTIFIER_OBJECT_ID_INVALIDATION_MAP_TEST_UTILH_
diff --git a/sync/notifier/object_id_invalidation_map_unittest.cc b/sync/notifier/object_id_invalidation_map_unittest.cc
new file mode 100644
index 0000000..1acd920
--- /dev/null
+++ b/sync/notifier/object_id_invalidation_map_unittest.cc
@@ -0,0 +1,104 @@
+// 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/object_id_invalidation_map.h"
+
+#include "google/cacheinvalidation/types.pb.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace syncer {
+
+namespace {
+
+class ObjectIdInvalidationMapTest : public testing::Test {
+ public:
+  ObjectIdInvalidationMapTest()
+      : kIdOne(ipc::invalidation::ObjectSource::TEST, "one"),
+        kIdTwo(ipc::invalidation::ObjectSource::TEST, "two"),
+        kInv1(Invalidation::Init(kIdOne, 10, "ten")) {
+    set1.insert(kIdOne);
+    set2.insert(kIdTwo);
+    all_set.insert(kIdOne);
+    all_set.insert(kIdTwo);
+
+    one_invalidation.Insert(kInv1);
+    invalidate_all = ObjectIdInvalidationMap::InvalidateAll(all_set);
+  }
+
+ protected:
+  const invalidation::ObjectId kIdOne;
+  const invalidation::ObjectId kIdTwo;
+  const Invalidation kInv1;
+
+  ObjectIdSet set1;
+  ObjectIdSet set2;
+  ObjectIdSet all_set;
+  ObjectIdInvalidationMap empty;
+  ObjectIdInvalidationMap one_invalidation;
+  ObjectIdInvalidationMap invalidate_all;
+};
+
+TEST_F(ObjectIdInvalidationMapTest, Empty) {
+  EXPECT_TRUE(empty.Empty());
+  EXPECT_FALSE(one_invalidation.Empty());
+  EXPECT_FALSE(invalidate_all.Empty());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, Equality) {
+  ObjectIdInvalidationMap empty2;
+  EXPECT_TRUE(empty == empty2);
+
+  ObjectIdInvalidationMap one_invalidation2;
+  one_invalidation2.Insert(kInv1);
+  EXPECT_TRUE(one_invalidation == one_invalidation2);
+
+  EXPECT_FALSE(empty == invalidate_all);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, GetObjectIds) {
+  EXPECT_EQ(ObjectIdSet(), empty.GetObjectIds());
+  EXPECT_EQ(set1, one_invalidation.GetObjectIds());
+  EXPECT_EQ(all_set, invalidate_all.GetObjectIds());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, GetSubsetWithObjectIds) {
+  EXPECT_TRUE(empty.GetSubsetWithObjectIds(set1).Empty());
+
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(set1) ==
+              one_invalidation);
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(all_set) ==
+              one_invalidation);
+  EXPECT_TRUE(one_invalidation.GetSubsetWithObjectIds(set2).Empty());
+
+  EXPECT_TRUE(invalidate_all.GetSubsetWithObjectIds(ObjectIdSet()).Empty());
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeEmpty) {
+  scoped_ptr<base::ListValue> value = empty.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(empty == deserialized);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeOneInvalidation) {
+  scoped_ptr<base::ListValue> value = one_invalidation.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(one_invalidation == deserialized);
+}
+
+TEST_F(ObjectIdInvalidationMapTest, SerializeInvalidateAll) {
+  scoped_ptr<base::ListValue> value = invalidate_all.ToValue();
+  ASSERT_TRUE(value.get());
+  ObjectIdInvalidationMap deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(invalidate_all == deserialized);
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/notifier/p2p_invalidator.cc b/sync/notifier/p2p_invalidator.cc
index 2468a51..3d47f41 100644
--- a/sync/notifier/p2p_invalidator.cc
+++ b/sync/notifier/p2p_invalidator.cc
@@ -14,6 +14,7 @@
 #include "jingle/notifier/listener/push_client.h"
 #include "sync/notifier/invalidation_handler.h"
 #include "sync/notifier/invalidation_util.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace syncer {
 
@@ -27,7 +28,7 @@ const char kNotifyAll[] = "notifyAll";
 
 const char kSenderIdKey[] = "senderId";
 const char kNotificationTypeKey[] = "notificationType";
-const char kIdInvalidationMapKey[] = "idInvalidationMap";
+const char kInvalidationsKey[] = "invalidations";
 
 }  // namespace
 
@@ -96,8 +97,7 @@ bool P2PNotificationData::Equals(const P2PNotificationData& other) const {
   return
       (sender_id_ == other.sender_id_) &&
       (target_ == other.target_) &&
-      ObjectIdInvalidationMapEquals(invalidation_map_,
-                                    other.invalidation_map_);
+      (invalidation_map_ == other.invalidation_map_);
 }
 
 std::string P2PNotificationData::ToString() const {
@@ -105,8 +105,7 @@ std::string P2PNotificationData::ToString() const {
   dict->SetString(kSenderIdKey, sender_id_);
   dict->SetString(kNotificationTypeKey,
                   P2PNotificationTargetToString(target_));
-  dict->Set(kIdInvalidationMapKey,
-            ObjectIdInvalidationMapToValue(invalidation_map_).release());
+  dict->Set(kInvalidationsKey, invalidation_map_.ToValue().release());
   std::string json;
   base::JSONWriter::Write(dict.get(), &json);
   return json;
@@ -129,10 +128,9 @@ bool P2PNotificationData::ResetFromString(const std::string& str) {
   }
   target_ = P2PNotificationTargetFromString(target_str);
   const base::ListValue* invalidation_map_list = NULL;
-  if (!data_dict->GetList(kIdInvalidationMapKey, &invalidation_map_list) ||
-      !ObjectIdInvalidationMapFromValue(*invalidation_map_list,
-                                        &invalidation_map_)) {
-    LOG(WARNING) << "Could not parse " << kIdInvalidationMapKey;
+  if (!data_dict->GetList(kInvalidationsKey, &invalidation_map_list) ||
+      !invalidation_map_.ResetFromValue(*invalidation_map_list)) {
+    LOG(WARNING) << "Could not parse " << kInvalidationsKey;
   }
   return true;
 }
@@ -161,8 +159,7 @@ void P2PInvalidator::RegisterHandler(InvalidationHandler* handler) {
 }
 
 void P2PInvalidator::UpdateRegisteredIds(InvalidationHandler* handler,
-                                      const ObjectIdSet& ids) {
-  // TODO(akalin): Handle arbitrary object IDs (http://crbug.com/140411).
+                                         const ObjectIdSet& ids) {
   DCHECK(thread_checker_.CalledOnValidThread());
   ObjectIdSet new_ids;
   const ObjectIdSet& old_ids = registrar_.GetRegisteredIds(handler);
@@ -173,10 +170,8 @@ void P2PInvalidator::UpdateRegisteredIds(InvalidationHandler* handler,
   registrar_.UpdateRegisteredIds(handler, ids);
   const P2PNotificationData notification_data(
       invalidator_client_id_,
-      NOTIFY_SELF,
-      ObjectIdSetToInvalidationMap(new_ids,
-                                   Invalidation::kUnknownVersion,
-                                   std::string()));
+      send_notification_target_,
+      ObjectIdInvalidationMap::InvalidateAll(ids));
   SendNotificationData(notification_data);
 }
 
@@ -213,9 +208,10 @@ void P2PInvalidator::UpdateCredentials(
   logged_in_ = true;
 }
 
-void P2PInvalidator::SendInvalidation(
-    const ObjectIdInvalidationMap& invalidation_map) {
+void P2PInvalidator::SendInvalidation(const ObjectIdSet& ids) {
   DCHECK(thread_checker_.CalledOnValidThread());
+  ObjectIdInvalidationMap invalidation_map =
+      ObjectIdInvalidationMap::InvalidateAll(ids);
   const P2PNotificationData notification_data(
       invalidator_client_id_, send_notification_target_, invalidation_map);
   SendNotificationData(notification_data);
@@ -230,9 +226,8 @@ void P2PInvalidator::OnNotificationsEnabled() {
     const P2PNotificationData notification_data(
         invalidator_client_id_,
         NOTIFY_SELF,
-        ObjectIdSetToInvalidationMap(registrar_.GetAllRegisteredIds(),
-                                     Invalidation::kUnknownVersion,
-                                     std::string()));
+        ObjectIdInvalidationMap::InvalidateAll(
+            registrar_.GetAllRegisteredIds()));
     SendNotificationData(notification_data);
   }
 }
@@ -266,9 +261,8 @@ void P2PInvalidator::OnIncomingNotification(
     notification_data = P2PNotificationData(
         invalidator_client_id_,
         NOTIFY_ALL,
-        ObjectIdSetToInvalidationMap(registrar_.GetAllRegisteredIds(),
-                                     Invalidation::kUnknownVersion,
-                                     std::string()));
+        ObjectIdInvalidationMap::InvalidateAll(
+            registrar_.GetAllRegisteredIds()));
   }
   if (!notification_data.IsTargeted(invalidator_client_id_)) {
     DVLOG(1) << "Not a target of the notification -- "
@@ -288,7 +282,7 @@ void P2PInvalidator::SendNotificationDataForTest(
 void P2PInvalidator::SendNotificationData(
     const P2PNotificationData& notification_data) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  if (notification_data.GetIdInvalidationMap().empty()) {
+  if (notification_data.GetIdInvalidationMap().Empty()) {
     DVLOG(1) << "Not sending XMPP notification with empty state map: "
              << notification_data.ToString();
     return;
diff --git a/sync/notifier/p2p_invalidator.h b/sync/notifier/p2p_invalidator.h
index 515b27b..bf622f0 100644
--- a/sync/notifier/p2p_invalidator.h
+++ b/sync/notifier/p2p_invalidator.h
@@ -24,6 +24,7 @@
 #include "sync/notifier/invalidator.h"
 #include "sync/notifier/invalidator_registrar.h"
 #include "sync/notifier/invalidator_state.h"
+#include "sync/notifier/object_id_invalidation_map.h"
 
 namespace notifier {
 class PushClient;
@@ -118,8 +119,7 @@ class SYNC_EXPORT_PRIVATE P2PInvalidator
   virtual void OnIncomingNotification(
       const notifier::Notification& notification) OVERRIDE;
 
-  void SendInvalidation(
-      const ObjectIdInvalidationMap& invalidation_map);
+  void SendInvalidation(const ObjectIdSet& ids);
 
   void SendNotificationDataForTest(
       const P2PNotificationData& notification_data);
diff --git a/sync/notifier/p2p_invalidator_unittest.cc b/sync/notifier/p2p_invalidator_unittest.cc
index 24cfe02..3cbabaf 100644
--- a/sync/notifier/p2p_invalidator_unittest.cc
+++ b/sync/notifier/p2p_invalidator_unittest.cc
@@ -10,7 +10,6 @@
 #include "sync/internal_api/public/base/model_type.h"
 #include "sync/notifier/fake_invalidation_handler.h"
 #include "sync/notifier/invalidator_test_template.h"
-#include "sync/notifier/object_id_invalidation_map_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
@@ -98,9 +97,7 @@ class P2PInvalidatorTest : public testing::Test {
   ObjectIdInvalidationMap MakeInvalidationMap(ModelTypeSet types) {
     ObjectIdInvalidationMap invalidations;
     ObjectIdSet ids = ModelTypeSetToObjectIdSet(types);
-    return ObjectIdSetToInvalidationMap(ids,
-                                        Invalidation::kUnknownVersion,
-                                        std::string());
+    return ObjectIdInvalidationMap::InvalidateAll(ids);
   }
 
   // Simulate receiving all the notifications we sent out since last
@@ -166,10 +163,10 @@ TEST_F(P2PInvalidatorTest, P2PNotificationDataDefault) {
   EXPECT_TRUE(notification_data.IsTargeted(std::string()));
   EXPECT_FALSE(notification_data.IsTargeted("other1"));
   EXPECT_FALSE(notification_data.IsTargeted("other2"));
-  EXPECT_TRUE(notification_data.GetIdInvalidationMap().empty());
+  EXPECT_TRUE(notification_data.GetIdInvalidationMap().Empty());
   const std::string& notification_data_str = notification_data.ToString();
   EXPECT_EQ(
-      "{\"idInvalidationMap\":[],\"notificationType\":\"notifySelf\","
+      "{\"invalidations\":[],\"notificationType\":\"notifySelf\","
       "\"senderId\":\"\"}", notification_data_str);
 
   P2PNotificationData notification_data_parsed;
@@ -180,27 +177,22 @@ TEST_F(P2PInvalidatorTest, P2PNotificationDataDefault) {
 // Make sure the P2PNotificationData <-> string conversions work for a
 // non-default-constructed P2PNotificationData.
 TEST_F(P2PInvalidatorTest, P2PNotificationDataNonDefault) {
-  const ObjectIdInvalidationMap& invalidation_map =
-      ObjectIdSetToInvalidationMap(
-          ModelTypeSetToObjectIdSet(ModelTypeSet(BOOKMARKS, THEMES)),
-          Invalidation::kUnknownVersion,
-          std::string());
-  const P2PNotificationData notification_data(
-      "sender", NOTIFY_ALL, invalidation_map);
+  ObjectIdInvalidationMap invalidation_map =
+      MakeInvalidationMap(ModelTypeSet(BOOKMARKS, THEMES));
+  const P2PNotificationData notification_data("sender",
+                                              NOTIFY_ALL,
+                                              invalidation_map);
   EXPECT_TRUE(notification_data.IsTargeted("sender"));
   EXPECT_TRUE(notification_data.IsTargeted("other1"));
   EXPECT_TRUE(notification_data.IsTargeted("other2"));
-  EXPECT_THAT(invalidation_map,
-              Eq(notification_data.GetIdInvalidationMap()));
+  EXPECT_EQ(invalidation_map, notification_data.GetIdInvalidationMap());
   const std::string& notification_data_str = notification_data.ToString();
   EXPECT_EQ(
-      "{\"idInvalidationMap\":["
-      "{\"objectId\":{\"name\":\"BOOKMARK\",\"source\":1004},"
-      "\"state\":{\"ackHandle\":{\"state\":\"\",\"timestamp\":\"0\"},"
-      "\"payload\":\"\",\"version\":\"-1\"}},"
-      "{\"objectId\":{\"name\":\"THEME\",\"source\":1004},"
-      "\"state\":{\"ackHandle\":{\"state\":\"\",\"timestamp\":\"0\"},"
-      "\"payload\":\"\",\"version\":\"-1\"}}"
+      "{\"invalidations\":["
+      "{\"isUnknownVersion\":true,"
+       "\"objectId\":{\"name\":\"BOOKMARK\",\"source\":1004}},"
+      "{\"isUnknownVersion\":true,"
+       "\"objectId\":{\"name\":\"THEME\",\"source\":1004}}"
       "],\"notificationType\":\"notifyAll\","
       "\"senderId\":\"sender\"}", notification_data_str);
 
@@ -248,14 +240,8 @@ TEST_F(P2PInvalidatorTest, NotificationsBasic) {
 
   // Sent with target NOTIFY_OTHERS so should not be propagated to
   // |fake_handler_|.
-  {
-    const ObjectIdInvalidationMap& invalidation_map =
-        ObjectIdSetToInvalidationMap(
-            ModelTypeSetToObjectIdSet(ModelTypeSet(THEMES, APPS)),
-            Invalidation::kUnknownVersion,
-            std::string());
-    invalidator->SendInvalidation(invalidation_map);
-  }
+  invalidator->SendInvalidation(
+      ModelTypeSetToObjectIdSet(ModelTypeSet(THEMES, APPS)));
 
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
@@ -270,9 +256,7 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
   const ModelTypeSet expected_types(THEMES);
 
   const ObjectIdInvalidationMap& invalidation_map =
-      ObjectIdSetToInvalidationMap(ModelTypeSetToObjectIdSet(changed_types),
-                                   Invalidation::kUnknownVersion,
-                                   std::string());
+      MakeInvalidationMap(changed_types);
 
   P2PInvalidator* const invalidator = delegate_.GetInvalidator();
   notifier::FakePushClient* const push_client = delegate_.GetPushClient();
@@ -288,23 +272,23 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
 
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(MakeInvalidationMap(enabled_types),
-              Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(ModelTypeSetToObjectIdSet(enabled_types),
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(P2PNotificationData());
   ReflectSentNotifications();
   EXPECT_EQ(1, fake_handler_.GetInvalidationCount());
 
-  const ObjectIdInvalidationMap& expected_ids =
-      MakeInvalidationMap(expected_types);
+  const ObjectIdSet& expected_ids = ModelTypeSetToObjectIdSet(expected_types);
 
   // Should be propagated.
   invalidator->SendNotificationDataForTest(
       P2PNotificationData("sender", NOTIFY_SELF, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(2, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
@@ -329,7 +313,8 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
       P2PNotificationData("sender2", NOTIFY_OTHERS, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(3, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
@@ -342,14 +327,16 @@ TEST_F(P2PInvalidatorTest, SendNotificationData) {
       P2PNotificationData("sender", NOTIFY_ALL, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(4, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be propagated.
   invalidator->SendNotificationDataForTest(
       P2PNotificationData("sender2", NOTIFY_ALL, invalidation_map));
   ReflectSentNotifications();
   EXPECT_EQ(5, fake_handler_.GetInvalidationCount());
-  EXPECT_THAT(expected_ids, Eq(fake_handler_.GetLastInvalidationMap()));
+  EXPECT_EQ(expected_ids,
+            fake_handler_.GetLastInvalidationMap().GetObjectIds());
 
   // Should be dropped.
   invalidator->SendNotificationDataForTest(
diff --git a/sync/notifier/single_object_invalidation_set.cc b/sync/notifier/single_object_invalidation_set.cc
new file mode 100644
index 0000000..55202bb
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set.cc
@@ -0,0 +1,130 @@
+// 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/single_object_invalidation_set.h"
+
+#include "base/values.h"
+#include "sync/notifier/invalidation_util.h"
+
+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() {}
+
+void SingleObjectInvalidationSet::Insert(const Invalidation& invalidation) {
+  invalidations_.insert(invalidation);
+}
+
+void SingleObjectInvalidationSet::InsertAll(
+    const SingleObjectInvalidationSet& other) {
+  invalidations_.insert(other.begin(), other.end());
+}
+
+void SingleObjectInvalidationSet::Clear() {
+  invalidations_.clear();
+}
+
+bool SingleObjectInvalidationSet::StartsWithUnknownVersion() const {
+  return !invalidations_.empty() &&
+      invalidations_.begin()->is_unknown_version();
+}
+
+size_t SingleObjectInvalidationSet::GetSize() const {
+  return invalidations_.size();
+}
+
+bool SingleObjectInvalidationSet::IsEmpty() const {
+  return invalidations_.empty();
+}
+
+namespace {
+
+struct InvalidationComparator {
+  bool operator()(const Invalidation& inv1, const Invalidation& inv2) {
+    return inv1.Equals(inv2);
+  }
+};
+
+}  // namespace
+
+bool SingleObjectInvalidationSet::operator==(
+    const SingleObjectInvalidationSet& other) const {
+  return std::equal(invalidations_.begin(),
+                    invalidations_.end(),
+                    other.invalidations_.begin(),
+                    InvalidationComparator());
+}
+
+SingleObjectInvalidationSet::const_iterator
+SingleObjectInvalidationSet::begin() const {
+  return invalidations_.begin();
+}
+
+SingleObjectInvalidationSet::const_iterator
+SingleObjectInvalidationSet::end() const {
+  return invalidations_.end();
+}
+
+SingleObjectInvalidationSet::const_reverse_iterator
+SingleObjectInvalidationSet::rbegin() const {
+  return invalidations_.rbegin();
+}
+
+SingleObjectInvalidationSet::const_reverse_iterator
+SingleObjectInvalidationSet::rend() const {
+  return invalidations_.rend();
+}
+
+const Invalidation& SingleObjectInvalidationSet::back() const {
+  return *invalidations_.rbegin();
+}
+
+scoped_ptr<base::ListValue> SingleObjectInvalidationSet::ToValue() const {
+  scoped_ptr<base::ListValue> value(new ListValue);
+  for (InvalidationsSet::const_iterator it = invalidations_.begin();
+       it != invalidations_.end(); ++it) {
+    value->Append(it->ToValue().release());
+  }
+  return value.Pass();
+}
+
+bool SingleObjectInvalidationSet::ResetFromValue(
+    const base::ListValue& list) {
+  for (size_t i = 0; i < list.GetSize(); ++i) {
+    const base::DictionaryValue* dict;
+    if (!list.GetDictionary(i, &dict)) {
+      DLOG(WARNING) << "Could not find invalidation 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);
+  }
+  return true;
+}
+
+}  // namespace syncer
diff --git a/sync/notifier/single_object_invalidation_set.h b/sync/notifier/single_object_invalidation_set.h
new file mode 100644
index 0000000..c4dd051
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set.h
@@ -0,0 +1,66 @@
+// 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_SINGLE_OBJECT_INVALIDATION_SET_H_
+#define SYNC_NOTIFIER_SINGLE_OBJECT_INVALIDATION_SET_H_
+
+#include <set>
+
+#include "base/memory/scoped_ptr.h"
+#include "sync/base/sync_export.h"
+#include "sync/internal_api/public/base/invalidation.h"
+
+namespace base {
+class ListValue;
+}  // namespace base
+
+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
+// operations, like checking for an unknown version invalidation or fetching the
+// highest invalidation with the highest version number.
+class SYNC_EXPORT SingleObjectInvalidationSet {
+ public:
+  typedef std::set<Invalidation, InvalidationVersionLessThan> InvalidationsSet;
+  typedef InvalidationsSet::const_iterator const_iterator;
+  typedef InvalidationsSet::const_reverse_iterator const_reverse_iterator;
+
+  SingleObjectInvalidationSet();
+  ~SingleObjectInvalidationSet();
+
+  void Insert(const Invalidation& invalidation);
+  void InsertAll(const SingleObjectInvalidationSet& other);
+  void Clear();
+
+  // Returns true if this list contains an unknown version.
+  //
+  // Unknown version invalidations always end up at the start of the list,
+  // because they have the lowest possible value in the sort ordering.
+  bool StartsWithUnknownVersion() const;
+  size_t GetSize() const;
+  bool IsEmpty() const;
+  bool operator==(const SingleObjectInvalidationSet& other) const;
+
+  const_iterator begin() const;
+  const_iterator end() const;
+  const_reverse_iterator rbegin() const;
+  const_reverse_iterator rend() const;
+  const Invalidation& back() const;
+
+  scoped_ptr<base::ListValue> ToValue() const;
+  bool ResetFromValue(const base::ListValue& list);
+
+ private:
+  InvalidationsSet invalidations_;
+};
+
+}  // syncer
+
+#endif  // SYNC_NOTIFIER_SINGLE_OBJECT_INVALIDATION_SET_H_
diff --git a/sync/notifier/single_object_invalidation_set_unittest.cc b/sync/notifier/single_object_invalidation_set_unittest.cc
new file mode 100644
index 0000000..3fe074e
--- /dev/null
+++ b/sync/notifier/single_object_invalidation_set_unittest.cc
@@ -0,0 +1,110 @@
+// 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/single_object_invalidation_set.h"
+
+#include "google/cacheinvalidation/types.pb.h"
+#include "sync/internal_api/public/base/invalidation_test_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace syncer {
+
+namespace {
+
+class SingleObjectInvalidationSetTest : public testing::Test {
+ public:
+  SingleObjectInvalidationSetTest()
+      : kId(ipc::invalidation::ObjectSource::TEST, "one") {
+  }
+ protected:
+  const invalidation::ObjectId kId;
+};
+
+TEST_F(SingleObjectInvalidationSetTest, InsertionAndOrdering) {
+  SingleObjectInvalidationSet l1;
+  SingleObjectInvalidationSet l2;
+
+  Invalidation inv0 = Invalidation::InitUnknownVersion(kId);
+  Invalidation inv1 = Invalidation::Init(kId, 1, "one");
+  Invalidation inv2 = Invalidation::Init(kId, 5, "five");
+
+  l1.Insert(inv0);
+  l1.Insert(inv1);
+  l1.Insert(inv2);
+
+  l2.Insert(inv1);
+  l2.Insert(inv2);
+  l2.Insert(inv0);
+
+  ASSERT_EQ(3U, l1.GetSize());
+  ASSERT_EQ(3U, l2.GetSize());
+
+  SingleObjectInvalidationSet::const_iterator it1 = l1.begin();
+  SingleObjectInvalidationSet::const_iterator it2 = l2.begin();
+  EXPECT_THAT(inv0, Eq(*it1));
+  EXPECT_THAT(inv0, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_THAT(inv1, Eq(*it1));
+  EXPECT_THAT(inv1, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_THAT(inv2, Eq(*it1));
+  EXPECT_THAT(inv2, Eq(*it2));
+  it1++;
+  it2++;
+  EXPECT_TRUE(it1 == l1.end());
+  EXPECT_TRUE(it2 == l2.end());
+}
+
+TEST_F(SingleObjectInvalidationSetTest, StartWithUnknownVersion) {
+  SingleObjectInvalidationSet list;
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+
+  list.Insert(Invalidation::InitUnknownVersion(kId));
+  EXPECT_TRUE(list.StartsWithUnknownVersion());
+
+  list.Clear();
+  EXPECT_FALSE(list.StartsWithUnknownVersion());
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeEmpty) {
+  SingleObjectInvalidationSet list;
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeOne) {
+  SingleObjectInvalidationSet list;
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+TEST_F(SingleObjectInvalidationSetTest, SerializeMany) {
+  SingleObjectInvalidationSet list;
+  list.Insert(Invalidation::Init(kId, 1, "one"));
+  list.Insert(Invalidation::InitUnknownVersion(kId));
+
+  scoped_ptr<base::ListValue> value = list.ToValue();
+  ASSERT_TRUE(value.get());
+  SingleObjectInvalidationSet deserialized;
+  deserialized.ResetFromValue(*value.get());
+  EXPECT_TRUE(list == deserialized);
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/notifier/sync_invalidation_listener.cc b/sync/notifier/sync_invalidation_listener.cc
index ed07f20..71be3ec 100644
--- a/sync/notifier/sync_invalidation_listener.cc
+++ b/sync/notifier/sync_invalidation_listener.cc
@@ -22,6 +22,8 @@ namespace {
 
 const char kApplicationName[] = "chrome-sync";
 
+static const int64 kUnknownVersion = -1;
+
 }  // namespace
 
 namespace syncer {
@@ -220,7 +222,7 @@ void SyncInvalidationListener::InvalidateUnknownVersion(
   ids.insert(object_id);
   PrepareInvalidation(
       ids,
-      Invalidation::kUnknownVersion,
+      kUnknownVersion,
       std::string(),
       client,
       ack_handle);
@@ -237,7 +239,7 @@ void SyncInvalidationListener::InvalidateAll(
 
   PrepareInvalidation(
       registered_ids_,
-      Invalidation::kUnknownVersion,
+      kUnknownVersion,
       std::string(),
       client,
       ack_handle);
@@ -275,13 +277,22 @@ void SyncInvalidationListener::EmitInvalidation(
     const invalidation::AckHandle& ack_handle,
     const AckHandleMap& local_ack_handles) {
   DCHECK(CalledOnValidThread());
-  ObjectIdInvalidationMap invalidation_map =
-      ObjectIdSetToInvalidationMap(ids, version, payload);
+
+  ObjectIdInvalidationMap invalidation_map;
   for (AckHandleMap::const_iterator it = local_ack_handles.begin();
        it != local_ack_handles.end(); ++it) {
     // Update in-memory copy of the invalidation state.
     invalidation_state_map_[it->first].expected = it->second;
-    invalidation_map[it->first].ack_handle = it->second;
+
+    if (version == kUnknownVersion) {
+      Invalidation inv = Invalidation::InitUnknownVersion(it->first);
+      inv.set_ack_handle(it->second);
+      invalidation_map.Insert(inv);
+    } else {
+      Invalidation inv = Invalidation::Init(it->first, version, payload);
+      inv.set_ack_handle(it->second);
+      invalidation_map.Insert(inv);
+    }
   }
   ack_tracker_.Track(ids);
   delegate_->OnInvalidate(invalidation_map);
@@ -291,13 +302,19 @@ void SyncInvalidationListener::EmitInvalidation(
 void SyncInvalidationListener::OnTimeout(const ObjectIdSet& ids) {
   ObjectIdInvalidationMap invalidation_map;
   for (ObjectIdSet::const_iterator it = ids.begin(); it != ids.end(); ++it) {
-    Invalidation invalidation;
-    invalidation.ack_handle = invalidation_state_map_[*it].expected;
-    invalidation.version = invalidation_state_map_[*it].version;
-    invalidation.payload = invalidation_state_map_[*it].payload;
-    invalidation_map.insert(std::make_pair(*it, invalidation));
+    if (invalidation_state_map_[*it].version == kUnknownVersion) {
+      Invalidation inv = Invalidation::InitUnknownVersion(*it);
+      inv.set_ack_handle(invalidation_state_map_[*it].expected);
+      invalidation_map.Insert(inv);
+    } else {
+      Invalidation inv = Invalidation::Init(
+          *it,
+          invalidation_state_map_[*it].version,
+          invalidation_state_map_[*it].payload);
+      inv.set_ack_handle(invalidation_state_map_[*it].expected);
+      invalidation_map.Insert(inv);
+    }
   }
-
   delegate_->OnInvalidate(invalidation_map);
 }
 
diff --git a/sync/notifier/sync_invalidation_listener_unittest.cc b/sync/notifier/sync_invalidation_listener_unittest.cc
index d3aa712..18dd123 100644
--- a/sync/notifier/sync_invalidation_listener_unittest.cc
+++ b/sync/notifier/sync_invalidation_listener_unittest.cc
@@ -141,37 +141,62 @@ class FakeDelegate : public SyncInvalidationListener::Delegate {
         state_(TRANSIENT_INVALIDATION_ERROR) {}
   virtual ~FakeDelegate() {}
 
-  int GetInvalidationCount(const ObjectId& id) const {
-    ObjectIdCountMap::const_iterator it = invalidation_counts_.find(id);
-    return (it == invalidation_counts_.end()) ? 0 : it->second;
+  size_t GetInvalidationCount(const ObjectId& id) const {
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      return 0;
+    } else {
+      return it->second.size();
+    }
   }
 
   int64 GetVersion(const ObjectId& id) const {
-    ObjectIdInvalidationMap::const_iterator it = invalidations_.find(id);
-    return (it == invalidations_.end()) ? 0 : it->second.version;
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return 0;
+    } else {
+      return it->second.back().version();
+    }
   }
 
   std::string GetPayload(const ObjectId& id) const {
-    ObjectIdInvalidationMap::const_iterator it = invalidations_.find(id);
-    return (it == invalidations_.end()) ? std::string() : it->second.payload;
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return "";
+    } else {
+      return it->second.back().payload();
+    }
   }
 
+  bool IsUnknownVersion(const ObjectId& id) const {
+    Map::const_iterator it = invalidations_.find(id);
+    if (it == invalidations_.end()) {
+      ADD_FAILURE() << "No invalidations for ID " << ObjectIdToString(id);
+      return false;
+    } else {
+      return it->second.back().is_unknown_version();
+    }
+  }
   InvalidatorState GetInvalidatorState() const {
     return state_;
   }
 
   void Acknowledge(const ObjectId& id) {
-    listener_->Acknowledge(id, invalidations_[id].ack_handle);
+    listener_->Acknowledge(id, invalidations_[id].back().ack_handle());
   }
 
   // SyncInvalidationListener::Delegate implementation.
 
   virtual void OnInvalidate(
       const ObjectIdInvalidationMap& invalidation_map) OVERRIDE {
-    for (ObjectIdInvalidationMap::const_iterator it = invalidation_map.begin();
-         it != invalidation_map.end(); ++it) {
-      ++invalidation_counts_[it->first];
-      invalidations_[it->first] = it->second;
+    ObjectIdSet ids = invalidation_map.GetObjectIds();
+    for (ObjectIdSet::iterator it = ids.begin(); it != ids.end(); ++it) {
+      const SingleObjectInvalidationSet& incoming =
+          invalidation_map.ForObject(*it);
+      List& list = invalidations_[*it];
+      list.insert(list.end(), incoming.begin(), incoming.end());
     }
   }
 
@@ -181,8 +206,9 @@ class FakeDelegate : public SyncInvalidationListener::Delegate {
 
  private:
   typedef std::map<ObjectId, int, ObjectIdLessThan> ObjectIdCountMap;
-  ObjectIdCountMap invalidation_counts_;
-  ObjectIdInvalidationMap invalidations_;
+  typedef std::vector<Invalidation> List;
+  typedef std::map<ObjectId, List, ObjectIdLessThan> Map;
+  Map invalidations_;
   SyncInvalidationListener* listener_;
   InvalidatorState state_;
 };
@@ -308,6 +334,10 @@ class SyncInvalidationListenerTest : public testing::Test {
     return fake_delegate_.GetPayload(id);
   }
 
+  bool IsUnknownVersion(const ObjectId& id) const {
+    return fake_delegate_.IsUnknownVersion(id);
+  }
+
   InvalidatorState GetInvalidatorState() const {
     return fake_delegate_.GetInvalidatorState();
   }
@@ -489,7 +519,6 @@ TEST_F(SyncInvalidationListenerTest, InvalidateUnregisteredWithPayload) {
   const ObjectId& id = kUnregisteredId;
 
   EXPECT_EQ(0, GetInvalidationCount(id));
-  EXPECT_EQ("", GetPayload(id));
   EXPECT_EQ(kMinVersion, GetMaxVersion(id));
 
   FireInvalidate(id, kVersion1, "unregistered payload");
@@ -524,25 +553,18 @@ TEST_F(SyncInvalidationListenerTest, InvalidateVersion) {
   VerifyAcknowledged(id);
 }
 
-// Fire an invalidation with an unknown version twice.  It shouldn't
-// update the payload or version either time, but it should still be
-// processed.
+// Fire an invalidation with an unknown version twice.  It shouldn't update the
+// version either time, but it should still be processed.
 TEST_F(SyncInvalidationListenerTest, InvalidateUnknownVersion) {
   const ObjectId& id = kBookmarksId_;
 
   FireInvalidateUnknownVersion(id);
 
   EXPECT_EQ(1, GetInvalidationCount(id));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(id));
-  EXPECT_EQ("", GetPayload(id));
-  EXPECT_EQ(kMinVersion, GetMaxVersion(id));
+  EXPECT_TRUE(IsUnknownVersion(id));
   AcknowledgeAndVerify(id);
 
   FireInvalidateUnknownVersion(id);
-
-  EXPECT_EQ(2, GetInvalidationCount(id));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(id));
-  EXPECT_EQ("", GetPayload(id));
   EXPECT_EQ(kMinVersion, GetMaxVersion(id));
   AcknowledgeAndVerify(id);
 }
@@ -555,8 +577,7 @@ TEST_F(SyncInvalidationListenerTest, InvalidateAll) {
   for (ObjectIdSet::const_iterator it = registered_ids_.begin();
        it != registered_ids_.end(); ++it) {
     EXPECT_EQ(1, GetInvalidationCount(*it));
-    EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(*it));
-    EXPECT_EQ("", GetPayload(*it));
+    EXPECT_TRUE(IsUnknownVersion(*it));
     EXPECT_EQ(kMinVersion, GetMaxVersion(*it));
     AcknowledgeAndVerify(*it);
   }
@@ -601,14 +622,12 @@ TEST_F(SyncInvalidationListenerTest, InvalidateMultipleIds) {
   FireInvalidateAll();
 
   EXPECT_EQ(2, GetInvalidationCount(kBookmarksId_));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(kBookmarksId_));
-  EXPECT_EQ("", GetPayload(kBookmarksId_));
+  EXPECT_TRUE(IsUnknownVersion(kBookmarksId_));
   EXPECT_EQ(3, GetMaxVersion(kBookmarksId_));
   AcknowledgeAndVerify(kBookmarksId_);
 
   EXPECT_EQ(1, GetInvalidationCount(kPreferencesId_));
-  EXPECT_EQ(Invalidation::kUnknownVersion, GetVersion(kPreferencesId_));
-  EXPECT_EQ("", GetPayload(kPreferencesId_));
+  EXPECT_TRUE(IsUnknownVersion(kBookmarksId_));
   EXPECT_EQ(kMinVersion, GetMaxVersion(kPreferencesId_));
   AcknowledgeAndVerify(kPreferencesId_);