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

1 files changed, 26 insertions, 58 deletions

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;