sync: Reduce work done to process bookmark changes

The ChangeReorderBuffer and BookmarkChangeProcessor collaborate to
handle bookmark-specific ordering and hierarchy requirements.  With a
bit of help from the directory and some changes to these classes, we can
achieve the same effect as before with less work.

Prior to this CL, the BookmarkChangeProcessor would apply a
position-affecting from sync to the bookmark model by updating all
siblings of the position change in left to right order.  The idea was to
have all the predecessors of the modified item in sync before applying
the change.  The ChangeReorderBuffer helps out by manufacturing fake
changes for siblings of position changes, and delivering them all to the
BookmarkChangeProcessor in syncable::Directory left-to-right order.

This CL works solves the issue by splitting the work up into two
separate passes.  On the first pass, any modified nodes are moved to the
far right within their parent folder.  The second pass iterates over
these modified items in syncable::Directory left-to-right position
order, and moves them to the proper index in the bookmark model.  This
has the same effect as the earlier algorithm: all predecessors are
synced at the time of the final move operation.  This should be much
cheaper than modifying all the siblings of a position change.

This new algorithm also allows us to remove lots of sibling ordering
requirements from the ChangeReorderBuffer and related functions, since
the BookmarkChangeProcessor no longer requires its changes to be
delivered in sibling order.  It also no longer needs to manufacture fake
changes for siblings of position changes.

This CL also includes a few cosmetic changes to the
BookmarkChangeProcessor.

BUG=123429

Review URL: https://chromiumcodereview.appspot.com/16507010

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

11 files changed, 107 insertions, 120 deletions

diff --git a/sync/internal_api/base_node.cc b/sync/internal_api/base_node.cc
index 3a719cd..db5f595 100644
--- a/sync/internal_api/base_node.cc
+++ b/sync/internal_api/base_node.cc
@@ -223,6 +223,10 @@ int BaseNode::GetTotalNodeCount() const {
   return GetEntry()->GetTotalNodeCount();
 }
 
+int BaseNode::GetPositionIndex() const {
+  return GetEntry()->GetPositionIndex();
+}
+
 DictionaryValue* BaseNode::GetSummaryAsValue() const {
   DictionaryValue* node_info = new DictionaryValue();
   node_info->SetString("id", base::Int64ToString(GetId()));
diff --git a/sync/internal_api/change_reorder_buffer.cc b/sync/internal_api/change_reorder_buffer.cc
index 0ddb6b3..ffe7be2 100644
--- a/sync/internal_api/change_reorder_buffer.cc
+++ b/sync/internal_api/change_reorder_buffer.cc
@@ -9,9 +9,8 @@
 #include <set>
 #include <utility>  // for pair<>
 
-#include "sync/internal_api/public/base/model_type.h"
-#include "sync/internal_api/public/read_node.h"
-#include "sync/syncable/directory.h"
+#include "sync/internal_api/public/base_node.h"
+#include "sync/internal_api/public/base_transaction.h"
 #include "sync/syncable/entry.h"
 #include "sync/syncable/syncable_base_transaction.h"
 
@@ -61,7 +60,7 @@ class ChangeReorderBuffer::Traversal {
       } else {
         // Otherwise, get the parent ID so that we can add a ParentChildLink.
         syncable::Entry parent(trans, syncable::GET_BY_ID,
-                             node.Get(syncable::PARENT_ID));
+                               node.Get(syncable::PARENT_ID));
         CHECK(parent.good());
         node_parent = parent.Get(syncable::META_HANDLE);
 
@@ -121,6 +120,38 @@ ChangeReorderBuffer::ChangeReorderBuffer() {
 ChangeReorderBuffer::~ChangeReorderBuffer() {
 }
 
+void ChangeReorderBuffer::PushAddedItem(int64 id) {
+  operations_[id] = ChangeRecord::ACTION_ADD;
+}
+
+void ChangeReorderBuffer::PushDeletedItem(int64 id) {
+  operations_[id] = ChangeRecord::ACTION_DELETE;
+}
+
+void ChangeReorderBuffer::PushUpdatedItem(int64 id) {
+  operations_[id] = ChangeRecord::ACTION_UPDATE;
+}
+
+void ChangeReorderBuffer::SetExtraDataForId(
+    int64 id,
+    ExtraPasswordChangeRecordData* extra) {
+  extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra);
+}
+
+void ChangeReorderBuffer::SetSpecificsForId(
+    int64 id,
+    const sync_pb::EntitySpecifics& specifics) {
+  specifics_[id] = specifics;
+}
+
+void ChangeReorderBuffer::Clear() {
+  operations_.clear();
+}
+
+bool ChangeReorderBuffer::IsEmpty() const {
+  return operations_.empty();
+}
+
 bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
     const BaseTransaction* sync_trans,
     ImmutableChangeRecordList* changes) {
@@ -130,17 +161,16 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
   // (a) Push deleted items straight into the |changelist|.
   // (b) Construct a traversal spanning all non-deleted items.
   // (c) Construct a set of all parent nodes of any position changes.
-  set<int64> parents_of_position_changes;
   Traversal traversal;
 
   ChangeRecordList changelist;
 
   OperationMap::const_iterator i;
   for (i = operations_.begin(); i != operations_.end(); ++i) {
-    if (i->second == OP_DELETE) {
+    if (i->second == ChangeRecord::ACTION_DELETE) {
       ChangeRecord record;
       record.id = i->first;
-      record.action = ChangeRecord::ACTION_DELETE;
+      record.action = i->second;
       if (specifics_.find(record.id) != specifics_.end())
         record.specifics = specifics_[record.id];
       if (extra_data_.find(record.id) != extra_data_.end())
@@ -148,22 +178,10 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
       changelist.push_back(record);
     } else {
       traversal.ExpandToInclude(trans, i->first);
-      if (i->second == OP_ADD ||
-          i->second == OP_UPDATE_POSITION_AND_PROPERTIES) {
-        ReadNode node(sync_trans);
-        CHECK_EQ(BaseNode::INIT_OK, node.InitByIdLookup(i->first));
-
-        // We only care about parents of entry's with position-sensitive models.
-        if (node.GetEntry()->ShouldMaintainPosition()) {
-          parents_of_position_changes.insert(node.GetParentId());
-          traversal.ExpandToInclude(trans, node.GetParentId());
-        }
-      }
     }
   }
 
-  // Step 2: Breadth-first expansion of the traversal, enumerating children in
-  // the syncable sibling order if there were any position updates.
+  // Step 2: Breadth-first expansion of the traversal.
   queue<int64> to_visit;
   to_visit.push(traversal.top());
   while (!to_visit.empty()) {
@@ -175,10 +193,7 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
     if (i != operations_.end()) {
       ChangeRecord record;
       record.id = next;
-      if (i->second == OP_ADD)
-        record.action = ChangeRecord::ACTION_ADD;
-      else
-        record.action = ChangeRecord::ACTION_UPDATE;
+      record.action = i->second;
       if (specifics_.find(record.id) != specifics_.end())
         record.specifics = specifics_[record.id];
       if (extra_data_.find(record.id) != extra_data_.end())
@@ -187,33 +202,11 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
     }
 
     // Now add the children of |next| to |to_visit|.
-    if (parents_of_position_changes.find(next) ==
-        parents_of_position_changes.end()) {
-        // No order changes on this parent -- traverse only the nodes listed
-        // in the traversal (and not in sibling order).
-        Traversal::LinkSet::const_iterator j = traversal.begin_children(next);
-        Traversal::LinkSet::const_iterator end = traversal.end_children(next);
-        for (; j != end; ++j) {
-          CHECK(j->first == next);
-          to_visit.push(j->second);
-        }
-    } else {
-      // There were ordering changes on the children of this parent, so
-      // enumerate all the children in the sibling order.
-      syncable::Entry parent(trans, syncable::GET_BY_HANDLE, next);
-      syncable::Id id = parent.GetFirstChildId();
-      while (!id.IsRoot()) {
-        syncable::Entry child(trans, syncable::GET_BY_ID, id);
-        CHECK(child.good());
-        int64 handle = child.Get(syncable::META_HANDLE);
-        to_visit.push(handle);
-        // If there is no operation on this child node, record it as as an
-        // update, so that the listener gets notified of all nodes in the new
-        // ordering.
-        if (operations_.find(handle) == operations_.end())
-          operations_[handle] = OP_UPDATE_POSITION_AND_PROPERTIES;
-        id = child.GetSuccessorId();
-      }
+    Traversal::LinkSet::const_iterator j = traversal.begin_children(next);
+    Traversal::LinkSet::const_iterator end = traversal.end_children(next);
+    for (; j != end; ++j) {
+      CHECK(j->first == next);
+      to_visit.push(j->second);
     }
   }
 
diff --git a/sync/internal_api/change_reorder_buffer.h b/sync/internal_api/change_reorder_buffer.h
index 09aaf8e..c1c577d 100644
--- a/sync/internal_api/change_reorder_buffer.h
+++ b/sync/internal_api/change_reorder_buffer.h
@@ -14,12 +14,13 @@
 
 #include "base/compiler_specific.h"
 #include "base/memory/linked_ptr.h"
-#include "sync/internal_api/public/base_transaction.h"
 #include "sync/internal_api/public/change_record.h"
 #include "sync/protocol/sync.pb.h"
 
 namespace syncer {
 
+class BaseTransaction;
+
 // ChangeReorderBuffer is a utility type which accepts an unordered set
 // of changes (via its Push methods), and yields an ImmutableChangeRecordList
 // (via the GetAllChangesInTreeOrder method) that are in the order that
@@ -28,61 +29,34 @@ namespace syncer {
 // The ordering produced by ChangeReorderBuffer is as follows:
 //  (a) All Deleted items appear first.
 //  (b) For Updated and/or Added items, parents appear before their children.
-//  (c) When there are changes to the sibling order (this means Added items,
-//      or Updated items with the |position_changed| parameter set to true),
-//      all siblings under a parent will appear in the output, even if they
-//      are not explicitly pushed.  The sibling order will be preserved in
-//      the output list -- items will appear before their sibling-order
-//      successors.
-//  (d) When there are no changes to the sibling order under a parent node,
-//      the sibling order is not necessarily preserved in the output for
-//      its children.
+//
+// The sibling order is not necessarily preserved.
 class ChangeReorderBuffer {
  public:
   ChangeReorderBuffer();
   ~ChangeReorderBuffer();
 
-  // Insert an item, identified by the metahandle |id|, into the reorder
-  // buffer. This item will appear in the output list as an ACTION_ADD
-  // ChangeRecord.
-  void PushAddedItem(int64 id) {
-    operations_[id] = OP_ADD;
-  }
-
-  // Insert an item, identified by the metahandle |id|, into the reorder
-  // buffer. This item will appear in the output list as an ACTION_DELETE
-  // ChangeRecord.
-  void PushDeletedItem(int64 id) {
-    operations_[id] = OP_DELETE;
-  }
-
-  // Insert an item, identified by the metahandle |id|, into the reorder
-  // buffer. This item will appear in the output list as an ACTION_UPDATE
-  // ChangeRecord. Also, if |position_changed| is true, all siblings of this
-  // item will appear in the output list as well; if it wasn't explicitly
-  // pushed, the siblings will have an ACTION_UPDATE ChangeRecord.
-  void PushUpdatedItem(int64 id, bool position_changed) {
-    operations_[id] = position_changed ? OP_UPDATE_POSITION_AND_PROPERTIES :
-                                         OP_UPDATE_PROPERTIES_ONLY;
-  }
-
-  void SetExtraDataForId(int64 id, ExtraPasswordChangeRecordData* extra) {
-    extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra);
-  }
-
-  void SetSpecificsForId(int64 id, const sync_pb::EntitySpecifics& specifics) {
-    specifics_[id] = specifics;
-  }
-
-  // Reset the buffer, forgetting any pushed items, so that it can be used
-  // again to reorder a new set of changes.
-  void Clear() {
-    operations_.clear();
-  }
-
-  bool IsEmpty() const {
-    return operations_.empty();
-  }
+  // Insert an item, identified by the metahandle |id|, into the reorder buffer.
+  // This item will appear in the output list as an ACTION_ADD ChangeRecord.
+  void PushAddedItem(int64 id);
+
+  // Insert an item, identified by the metahandle |id|, into the reorder buffer.
+  // This item will appear in the output list as an ACTION_DELETE ChangeRecord.
+  void PushDeletedItem(int64 id);
+
+  // Insert an item, identified by the metahandle |id|, into the reorder buffer.
+  // This item will appear in the output list as an ACTION_UPDATE ChangeRecord.
+  void PushUpdatedItem(int64 id);
+
+  void SetExtraDataForId(int64 id, ExtraPasswordChangeRecordData* extra);
+
+  void SetSpecificsForId(int64 id, const sync_pb::EntitySpecifics& specifics);
+
+  // Reset the buffer, forgetting any pushed items, so that it can be used again
+  // to reorder a new set of changes.
+  void Clear();
+
+  bool IsEmpty() const;
 
   // Output a reordered list of changes to |changes| using the items
   // that were pushed into the reorder buffer. |sync_trans| is used to
@@ -94,13 +68,7 @@ class ChangeReorderBuffer {
 
  private:
   class Traversal;
-  enum Operation {
-    OP_ADD,                             // AddedItem.
-    OP_DELETE,                          // DeletedItem.
-    OP_UPDATE_PROPERTIES_ONLY,          // UpdatedItem with position_changed=0.
-    OP_UPDATE_POSITION_AND_PROPERTIES,  // UpdatedItem with position_changed=1.
-  };
-  typedef std::map<int64, Operation> OperationMap;
+  typedef std::map<int64, ChangeRecord::Action> OperationMap;
   typedef std::map<int64, sync_pb::EntitySpecifics> SpecificsMap;
   typedef std::map<int64, linked_ptr<ExtraPasswordChangeRecordData> >
       ExtraDataMap;
diff --git a/sync/internal_api/public/base_node.h b/sync/internal_api/public/base_node.h
index 6c54ce2..a9f50bc 100644
--- a/sync/internal_api/public/base_node.h
+++ b/sync/internal_api/public/base_node.h
@@ -204,6 +204,11 @@ class SYNC_EXPORT BaseNode {
   // Recursively iterates through all children.
   int GetTotalNodeCount() const;
 
+  // Returns this item's position within its parent.
+  // Do not call this function on items that do not support positioning
+  // (ie. non-bookmarks).
+  int GetPositionIndex() const;
+
   // These virtual accessors provide access to data members of derived classes.
   virtual const syncable::Entry* GetEntry() const = 0;
   virtual const BaseTransaction* GetTransaction() const = 0;
diff --git a/sync/internal_api/sync_manager_impl.cc b/sync/internal_api/sync_manager_impl.cc
index 55150f1..4ed5abd 100644
--- a/sync/internal_api/sync_manager_impl.cc
+++ b/sync/internal_api/sync_manager_impl.cc
@@ -946,8 +946,7 @@ void SyncManagerImpl::HandleCalculateChangesChangeEventFromSyncer(
       change_buffers[type].PushDeletedItem(handle);
     else if (exists_now && existed_before &&
              VisiblePropertiesDiffer(it->second, crypto)) {
-      change_buffers[type].PushUpdatedItem(
-          handle, VisiblePositionsDiffer(it->second));
+      change_buffers[type].PushUpdatedItem(handle);
     }
 
     SetExtraChangeRecordData(handle, type, &change_buffers[type], crypto,
diff --git a/sync/internal_api/sync_manager_impl.h b/sync/internal_api/sync_manager_impl.h
index 3d2c2cf..a916b30 100644
--- a/sync/internal_api/sync_manager_impl.h
+++ b/sync/internal_api/sync_manager_impl.h
@@ -20,6 +20,7 @@
 #include "sync/internal_api/js_sync_encryption_handler_observer.h"
 #include "sync/internal_api/js_sync_manager_observer.h"
 #include "sync/internal_api/public/sync_manager.h"
+#include "sync/internal_api/public/user_share.h"
 #include "sync/internal_api/sync_encryption_handler_impl.h"
 #include "sync/js/js_backend.h"
 #include "sync/notifier/invalidation_handler.h"
diff --git a/sync/internal_api/sync_manager_impl_unittest.cc b/sync/internal_api/sync_manager_impl_unittest.cc
index d42c9376..7ef30146 100644
--- a/sync/internal_api/sync_manager_impl_unittest.cc
+++ b/sync/internal_api/sync_manager_impl_unittest.cc
@@ -3500,16 +3500,11 @@ TEST_F(SyncManagerChangeProcessingTest, MoveIntoPopulatedFolder) {
     child_a.PutPredecessor(child_b.Get(syncable::ID));
   }
 
-  EXPECT_EQ(2UL, GetChangeListSize());
-
-  // Verify that both child A and child B are in the change list, even though
-  // only child A was moved.  The rules state that all siblings of
-  // position-modified items must be included in the list of changes.
-  int64 child_a_pos = FindChangeInList(child_a_id, ChangeRecord::ACTION_UPDATE);
-  int64 child_b_pos = FindChangeInList(child_b_id, ChangeRecord::ACTION_UPDATE);
+  EXPECT_EQ(1UL, GetChangeListSize());
 
-  // Siblings should appear in left-to-right order.
-  EXPECT_LT(child_b_pos, child_a_pos);
+  // Verify that only child a is in the change list.
+  // (This function will add a failure if the lookup fails.)
+  FindChangeInList(child_a_id, ChangeRecord::ACTION_UPDATE);
 }
 
 // Tests the ordering of deletion changes.
diff --git a/sync/syncable/directory.cc b/sync/syncable/directory.cc
index 74cde4f..200606e 100644
--- a/sync/syncable/directory.cc
+++ b/sync/syncable/directory.cc
@@ -4,6 +4,8 @@
 
 #include "sync/syncable/directory.h"
 
+#include <iterator>
+
 #include "base/base64.h"
 #include "base/debug/trace_event.h"
 #include "base/stl_util.h"
@@ -327,6 +329,16 @@ void Directory::GetChildSetForKernel(
   child_sets->push_back(descendants);
 }
 
+int Directory::GetPositionIndex(
+    BaseTransaction* trans,
+    EntryKernel* kernel) const {
+  const OrderedChildSet* siblings =
+      kernel_->parent_child_index.GetChildren(kernel->ref(PARENT_ID));
+
+  OrderedChildSet::const_iterator it = siblings->find(kernel);
+  return std::distance(siblings->begin(), it);
+}
+
 EntryKernel* Directory::GetRootEntry() {
   return GetEntryById(Id());
 }
diff --git a/sync/syncable/directory.h b/sync/syncable/directory.h
index e149ae3..2212a8c 100644
--- a/sync/syncable/directory.h
+++ b/sync/syncable/directory.h
@@ -257,6 +257,10 @@ class SYNC_EXPORT Directory {
   // Counts all items under the given node, including the node itself.
   int GetTotalNodeCount(BaseTransaction*, EntryKernel* kernel_) const;
 
+  // Returns this item's position within its parent folder.
+  // The left-most item is 0, second left-most is 1, etc.
+  int GetPositionIndex(BaseTransaction*, EntryKernel* kernel_) const;
+
   // Returns true iff |id| has children.
   bool HasChildren(BaseTransaction* trans, const Id& id);
 
diff --git a/sync/syncable/entry.cc b/sync/syncable/entry.cc
index e9b9f64..f888392 100644
--- a/sync/syncable/entry.cc
+++ b/sync/syncable/entry.cc
@@ -112,6 +112,10 @@ int Entry::GetTotalNodeCount() const {
   return dir()->GetTotalNodeCount(basetrans_, kernel_);
 }
 
+int Entry::GetPositionIndex() const {
+  return dir()->GetPositionIndex(basetrans_, kernel_);
+}
+
 bool Entry::ShouldMaintainPosition() const {
   return kernel_->ShouldMaintainPosition();
 }
diff --git a/sync/syncable/entry.h b/sync/syncable/entry.h
index 097f8a8..177dc5d 100644
--- a/sync/syncable/entry.h
+++ b/sync/syncable/entry.h
@@ -110,6 +110,8 @@ class SYNC_EXPORT Entry {
   Id GetFirstChildId() const;
   int GetTotalNodeCount() const;
 
+  int GetPositionIndex() const;
+
   // Returns a vector of this node's children's handles.
   // Clears |result| if there are no children.  If this node is of a type that
   // supports user-defined ordering then the resulting vector will be in the