In the syncable directory, an index consists of (a) a rule defining which syncable Entries are included in the index and (b) a comparator defining the ordering used by the index set.

This change introduces "Indexer" traits types that are tuples of (a) and (b).  I then am able to use some templated code to add a ScopedIndexUpdater, which is shorthand for the formerly manual pattern where we'd remove items from indices before updating the indexed fields.

I'm doing this in preparation for changing the ParentChildIndex to depend on SERVER_POSITION_IN_PARENT.

BUG=60236, chromium-os:11226
TEST=sync_unit_tests

Review URL: http://codereview.chromium.org/6542072

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

5 files changed, 175 insertions, 101 deletions

diff --git a/chrome/browser/sync/engine/syncer_unittest.cc b/chrome/browser/sync/engine/syncer_unittest.cc
index 57f8eda..8fc32e3 100644
--- a/chrome/browser/sync/engine/syncer_unittest.cc
+++ b/chrome/browser/sync/engine/syncer_unittest.cc
@@ -3568,6 +3568,23 @@ TEST_F(SyncerTest, MergingExistingItems) {
   SyncRepeatedlyToTriggerConflictResolution(session_.get());
 }
 
+TEST_F(SyncerTest, OneBajillionUpdates) {
+  ScopedDirLookup dir(syncdb_.manager(), syncdb_.name());
+  CHECK(dir.good());
+  int one_bajillion = 4000;
+
+  syncable::Id parent_id = ids_.MakeServer("Parent");
+  mock_server_->AddUpdateDirectory(parent_id, ids_.root(), "foo", 1, 1);
+
+  for (int i = 1; i <= one_bajillion; ++i) {
+    syncable::Id item_id = ids_.FromNumber(i);
+    mock_server_->AddUpdateDirectory(item_id, parent_id, "dude", 1, 1);
+  }
+
+  syncer_->SyncShare(session_.get());
+  EXPECT_FALSE(session_->status_controller()->syncer_status().syncer_stuck);
+}
+
 // In this test a long changelog contains a child at the start of the changelog
 // and a parent at the end. While these updates are in progress the client would
 // appear stuck.
diff --git a/chrome/browser/sync/syncable/syncable-inl.h b/chrome/browser/sync/syncable/syncable-inl.h
index 79845cf..c5beed9 100644
--- a/chrome/browser/sync/syncable/syncable-inl.h
+++ b/chrome/browser/sync/syncable/syncable-inl.h
@@ -6,8 +6,6 @@
 #define CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_INL_H_
 #pragma once
 
-#include "chrome/common/sqlite_utils.h"
-
 namespace syncable {
 
 template <typename FieldType, FieldType field_index>
@@ -19,13 +17,6 @@ class LessField {
   }
 };
 
-struct IdRowTraits {
-  typedef syncable::Id RowType;
-  void Extract(SQLStatement* statement, syncable::Id* id) const {
-    id->s_ = statement->column_string(0);
-  }
-};
-
 }  // namespace syncable
 
 #endif  // CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_INL_H_
diff --git a/chrome/browser/sync/syncable/syncable.cc b/chrome/browser/sync/syncable/syncable.cc
index cdac405..2a8a83e 100644
--- a/chrome/browser/sync/syncable/syncable.cc
+++ b/chrome/browser/sync/syncable/syncable.cc
@@ -88,40 +88,72 @@ int64 Now() {
 #endif
 }
 
-///////////////////////////////////////////////////////////////////////////
-// Compare functions and hashes for the indices.
+namespace {
 
-template <Int64Field field_index>
-class SameField {
+// A ScopedIndexUpdater temporarily removes an entry from an index,
+// and restores it to the index when the scope exits.  This simplifies
+// the common pattern where items need to be removed from an index
+// before updating the field.
+//
+// This class is parameterized on the Indexer traits type, which
+// must define a Comparator and a static bool ShouldInclude
+// function for testing whether the item ought to be included
+// in the index.
+template<typename Indexer>
+class ScopedIndexUpdater {
  public:
-  inline bool operator()(const syncable::EntryKernel* a,
-                         const syncable::EntryKernel* b) const {
-    return a->ref(field_index) == b->ref(field_index);
+  ScopedIndexUpdater(const ScopedKernelLock& proof_of_lock,
+                     EntryKernel* entry,
+                     typename Index<Indexer>::Set* index)
+      : entry_(entry),
+        index_(index) {
+    // First call to ShouldInclude happens before the field is updated.
+    if (Indexer::ShouldInclude(entry_)) {
+      CHECK(index_->erase(entry_));
+    }
   }
-};
 
-template <Int64Field field_index>
-class HashField {
- public:
-  inline size_t operator()(const syncable::EntryKernel* a) const {
-    return hasher_(a->ref(field_index));
+  ~ScopedIndexUpdater() {
+    // Second call to ShouldInclude happens after the field is updated.
+    if (Indexer::ShouldInclude(entry_)) {
+      CHECK(index_->insert(entry_).second);
+    }
   }
-  base::hash_set<int64> hasher_;
+ private:
+  // The entry that was temporarily removed from the index.
+  EntryKernel* entry_;
+  // The index which we are updating.
+  typename Index<Indexer>::Set* const index_;
 };
 
-class LessParentIdAndHandle {
+}  // namespace
+
+///////////////////////////////////////////////////////////////////////////
+// Comparator and filter functions for the indices.
+
+// static
+bool ClientTagIndexer::ShouldInclude(const EntryKernel* a) {
+  return !a->ref(UNIQUE_CLIENT_TAG).empty();
+}
+
+class ParentIdAndHandleIndexer::Comparator {
  public:
   bool operator() (const syncable::EntryKernel* a,
                    const syncable::EntryKernel* b) const {
-    if (a->ref(PARENT_ID) != b->ref(PARENT_ID)) {
-      return a->ref(PARENT_ID) < b->ref(PARENT_ID);
-    }
+    int cmp = a->ref(PARENT_ID).compare(b->ref(PARENT_ID));
+    if (cmp != 0)
+      return cmp < 0;
 
     // Meta handles are immutable per entry so this is ideal.
     return a->ref(META_HANDLE) < b->ref(META_HANDLE);
   }
 };
 
+// static
+bool ParentIdAndHandleIndexer::ShouldInclude(const EntryKernel* a) {
+  return !a->ref(IS_DEL);
+}
+
 ///////////////////////////////////////////////////////////////////////////
 // EntryKernel
 
@@ -449,47 +481,29 @@ void Directory::InsertEntry(EntryKernel* entry, ScopedKernelLock* lock) {
   CHECK(entry->ref(UNIQUE_CLIENT_TAG).empty());
 }
 
-void Directory::Undelete(EntryKernel* const entry) {
-  DCHECK(entry->ref(IS_DEL));
-  ScopedKernelLock lock(this);
-  entry->put(IS_DEL, false);
-  entry->mark_dirty(kernel_->dirty_metahandles);
-  CHECK(kernel_->parent_id_child_index->insert(entry).second);
-}
-
-void Directory::Delete(EntryKernel* const entry) {
-  DCHECK(!entry->ref(IS_DEL));
-  entry->put(IS_DEL, true);
-  entry->mark_dirty(kernel_->dirty_metahandles);
-  ScopedKernelLock lock(this);
-  CHECK_EQ(1U, kernel_->parent_id_child_index->erase(entry));
-}
-
 bool Directory::ReindexId(EntryKernel* const entry, const Id& new_id) {
   ScopedKernelLock lock(this);
   if (NULL != GetEntryById(new_id, &lock))
     return false;
-  CHECK_EQ(1U, kernel_->ids_index->erase(entry));
-  entry->put(ID, new_id);
-  CHECK(kernel_->ids_index->insert(entry).second);
+
+  {
+    // Update the indices that depend on the ID field.
+    ScopedIndexUpdater<IdIndexer> updater_a(lock, entry, kernel_->ids_index);
+    entry->put(ID, new_id);
+  }
   return true;
 }
 
 void Directory::ReindexParentId(EntryKernel* const entry,
                                 const Id& new_parent_id) {
   ScopedKernelLock lock(this);
-  if (entry->ref(IS_DEL)) {
-    entry->put(PARENT_ID, new_parent_id);
-    return;
-  }
 
-  if (entry->ref(PARENT_ID) == new_parent_id) {
-    return;
+  {
+    // Update the indices that depend on the PARENT_ID field.
+    ScopedIndexUpdater<ParentIdAndHandleIndexer> index_updater(lock, entry,
+        kernel_->parent_id_child_index);
+    entry->put(PARENT_ID, new_parent_id);
   }
-
-  CHECK_EQ(1U, kernel_->parent_id_child_index->erase(entry));
-  entry->put(PARENT_ID, new_parent_id);
-  CHECK(kernel_->parent_id_child_index->insert(entry).second);
 }
 
 void Directory::ClearDirtyMetahandles() {
@@ -1342,15 +1356,23 @@ bool MutableEntry::PutIsDel(bool is_del) {
   if (is_del == kernel_->ref(IS_DEL)) {
     return true;
   }
-  if (is_del) {
+  if (is_del)
     UnlinkFromOrder();
-    dir()->Delete(kernel_);
-    return true;
-  } else {
-    dir()->Undelete(kernel_);
-    PutPredecessor(Id());  // Restores position to the 0th index.
-    return true;
+
+  {
+    ScopedKernelLock lock(dir());
+    // Some indices don't include deleted items and must be updated
+    // upon a value change.
+    ScopedIndexUpdater<ParentIdAndHandleIndexer> updater(lock, kernel_,
+        dir()->kernel_->parent_id_child_index);
+
+    kernel_->put(IS_DEL, is_del);
+    kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
   }
+
+  if (!is_del)
+    PutPredecessor(Id());  // Restores position to the 0th index.
+  return true;
 }
 
 bool MutableEntry::Put(Int64Field field, const int64& value) {
@@ -1420,6 +1442,7 @@ bool MutableEntry::PutUniqueClientTag(const string& new_tag) {
     return true;
   }
 
+  ScopedKernelLock lock(dir());
   if (!new_tag.empty()) {
     // Make sure your new value is not in there already.
     EntryKernel lookup_kernel_ = *kernel_;
@@ -1429,17 +1452,11 @@ bool MutableEntry::PutUniqueClientTag(const string& new_tag) {
     if (new_tag_conflicts) {
       return false;
     }
+  }
 
-    // We're sure that the new tag doesn't exist now so,
-    // erase the old tag and finish up.
-    dir()->kernel_->client_tag_index->erase(kernel_);
-    kernel_->put(UNIQUE_CLIENT_TAG, new_tag);
-    kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
-    CHECK(dir()->kernel_->client_tag_index->insert(kernel_).second);
-  } else {
-    // The new tag is empty. Since the old tag is not equal to the new tag,
-    // The old tag isn't empty, and thus must exist in the index.
-    CHECK(dir()->kernel_->client_tag_index->erase(kernel_));
+  {
+    ScopedIndexUpdater<ClientTagIndexer> index_updater(lock, kernel_,
+        dir()->kernel_->client_tag_index);
     kernel_->put(UNIQUE_CLIENT_TAG, new_tag);
     kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
   }
diff --git a/chrome/browser/sync/syncable/syncable.h b/chrome/browser/sync/syncable/syncable.h
index 797f04e..af09779 100644
--- a/chrome/browser/sync/syncable/syncable.h
+++ b/chrome/browser/sync/syncable/syncable.h
@@ -210,8 +210,6 @@ enum CreateNewUpdateItem {
   CREATE_NEW_UPDATE_ITEM
 };
 
-typedef std::set<std::string> AttributeKeySet;
-
 typedef std::set<int64> MetahandleSet;
 
 // Why the singular enums?  So the code compile-time dispatches instead of
@@ -539,12 +537,7 @@ class MutableEntry : public Entry {
   DISALLOW_COPY_AND_ASSIGN(MutableEntry);
 };
 
-template <Int64Field field_index>
-class SameField;
-template <Int64Field field_index>
-class HashField;
 class LessParentIdAndHandle;
-class LessMultiIncusionTargetAndMetahandle;
 template <typename FieldType, FieldType field_index>
 class LessField;
 class LessEntryMetaHandles {
@@ -556,6 +549,72 @@ class LessEntryMetaHandles {
 };
 typedef std::set<EntryKernel, LessEntryMetaHandles> OriginalEntries;
 
+// How syncable indices & Indexers work.
+//
+// The syncable Directory maintains several indices on the Entries it tracks.
+// The indices follow a common pattern:
+//   (a) The index allows efficient lookup of an Entry* with particular
+//       field values.  This is done by use of a std::set<> and a custom
+//       comparator.
+//   (b) There may be conditions for inclusion in the index -- for example,
+//       deleted items might not be indexed.
+//   (c) Because the index set contains only Entry*, one must be careful
+//       to remove Entries from the set before updating the value of
+//       an indexed field.
+// The traits of an index are a Comparator (to define the set ordering) and a
+// ShouldInclude function (to define the conditions for inclusion).  For each
+// index, the traits are grouped into a class called an Indexer which
+// can be used as a template type parameter.
+
+// Traits type for metahandle index.
+struct MetahandleIndexer {
+  // This index is of the metahandle field values.
+  typedef LessField<MetahandleField, META_HANDLE> Comparator;
+
+  // This index includes all entries.
+  inline static bool ShouldInclude(const EntryKernel* a) {
+    return true;
+  }
+};
+
+// Traits type for ID field index.
+struct IdIndexer {
+  // This index is of the ID field values.
+  typedef LessField<IdField, ID> Comparator;
+
+  // This index includes all entries.
+  inline static bool ShouldInclude(const EntryKernel* a) {
+    return true;
+  }
+};
+
+// Traits type for unique client tag index.
+struct ClientTagIndexer {
+  // This index is of the client-tag values.
+  typedef LessField<StringField, UNIQUE_CLIENT_TAG> Comparator;
+
+  // Items are only in this index if they have a non-empty client tag value.
+  static bool ShouldInclude(const EntryKernel* a);
+};
+
+// This index contains EntryKernels ordered by parent ID and metahandle.
+// It allows efficient lookup of the children of a given parent.
+struct ParentIdAndHandleIndexer {
+  // This index is of the parent ID and metahandle.  We use a custom
+  // comparator.
+  class Comparator;
+
+  // This index does not include deleted items.
+  static bool ShouldInclude(const EntryKernel* a);
+};
+
+// Given an Indexer providing the semantics of an index, defines the
+// set type used to actually contain the index.
+template <typename Indexer>
+struct Index {
+  typedef std::set<EntryKernel*, typename Indexer::Comparator> Set;
+};
+
 // a WriteTransaction has a writer tag describing which body of code is doing
 // the write. This is defined up here since DirectoryChangeEvent also contains
 // one.
@@ -598,9 +657,6 @@ struct DirectoryChangeEvent {
   }
 };
 
-// A list of metahandles whose metadata should not be purged.
-typedef std::multiset<int64> Pegs;
-
 // The name Directory in this case means the entire directory
 // structure within a single user account.
 //
@@ -779,8 +835,6 @@ class Directory {
 
   // These don't do semantic checking.
   // The semantic checking is implemented higher up.
-  void Undelete(EntryKernel* const entry);
-  void Delete(EntryKernel* const entry);
   void UnlinkEntryFromOrder(EntryKernel* entry,
                             WriteTransaction* trans,
                             ScopedKernelLock* lock);
@@ -917,27 +971,19 @@ class Directory {
 
   Directory& operator = (const Directory&);
 
-  // TODO(sync):  If lookups and inserts in these sets become
-  // the bottle-neck, then we can use hash-sets instead.  But
-  // that will require using #ifdefs and compiler-specific code,
-  // so use standard sets for now.
  public:
-  typedef std::set<EntryKernel*, LessField<MetahandleField, META_HANDLE> >
-    MetahandlesIndex;
-  typedef std::set<EntryKernel*, LessField<IdField, ID> > IdsIndex;
+  typedef Index<MetahandleIndexer>::Set MetahandlesIndex;
+  typedef Index<IdIndexer>::Set IdsIndex;
   // All entries in memory must be in both the MetahandlesIndex and
   // the IdsIndex, but only non-deleted entries will be the
   // ParentIdChildIndex.
-  // This index contains EntryKernels ordered by parent ID and metahandle.
-  // It allows efficient lookup of the children of a given parent.
-  typedef std::set<EntryKernel*, LessParentIdAndHandle> ParentIdChildIndex;
+  typedef Index<ParentIdAndHandleIndexer>::Set ParentIdChildIndex;
 
   // Contains both deleted and existing entries with tags.
   // We can't store only existing tags because the client would create
   // items that had a duplicated ID in the end, resulting in a DB key
   // violation. ID reassociation would fail after an attempted commit.
-  typedef std::set<EntryKernel*,
-                   LessField<StringField, UNIQUE_CLIENT_TAG> > ClientTagIndex;
+  typedef Index<ClientTagIndexer>::Set ClientTagIndex;
 
  protected:
   // Used by tests.
@@ -972,8 +1018,10 @@ class Directory {
     // Never hold the mutex and do anything with the database or any
     // other buffered IO.  Violating this rule will result in deadlock.
     base::Lock mutex;
-    MetahandlesIndex* metahandles_index;  // Entries indexed by metahandle
-    IdsIndex* ids_index;  // Entries indexed by id
+    // Entries indexed by metahandle
+    MetahandlesIndex* metahandles_index;
+    // Entries indexed by id
+    IdsIndex* ids_index;
     ParentIdChildIndex* parent_id_child_index;
     ClientTagIndex* client_tag_index;
     // So we don't have to create an EntryKernel every time we want to
diff --git a/chrome/browser/sync/syncable/syncable_id.h b/chrome/browser/sync/syncable/syncable_id.h
index f606867..d52a524 100644
--- a/chrome/browser/sync/syncable/syncable_id.h
+++ b/chrome/browser/sync/syncable/syncable_id.h
@@ -20,7 +20,6 @@ struct sqlite3_stmt;
 
 namespace syncable {
 struct EntryKernel;
-struct IdRowTraits;
 class Id;
 }  // namespace syncable
 
@@ -44,7 +43,6 @@ std::ostream& operator<<(std::ostream& out, const Id& id);
 class Id {
   friend int UnpackEntry(SQLStatement* statement,
                          syncable::EntryKernel** kernel);
-  friend struct syncable::IdRowTraits;
   friend int BindFields(const EntryKernel& entry, SQLStatement* statement);
   friend std::ostream& operator<<(std::ostream& out, const Id& id);
   friend class MockConnectionManager;
@@ -78,6 +76,9 @@ class Id {
   inline void Clear() {
     s_ = "r";
   }
+  inline int compare(const Id& that) const {
+    return s_.compare(that.s_);
+  }
   // Must never allow id == 0 or id < 0 to compile.
   inline bool operator == (const Id& that) const {
     return s_ == that.s_;