sync: Allow commit of successors of conflict items

In a time when sync tracked positions using a linked list, it was
necessary to not commit any items whose predecessors were in conflict.
Doing so would have strange side-effects to items' positions.

Now that each item has its own absolute position value, the positions of
items no longer rely on their siblings.  Therefore, it's safe to commit
items even if the position of their siblings is in doubt.

BUG=147715

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

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

3 files changed, 60 insertions, 75 deletions

diff --git a/sync/engine/get_commit_ids_command.cc b/sync/engine/get_commit_ids_command.cc
index 7297f51..5d47a6c 100644
--- a/sync/engine/get_commit_ids_command.cc
+++ b/sync/engine/get_commit_ids_command.cc
@@ -198,14 +198,16 @@ bool GetCommitIdsCommand::AddUncommittedParentsAndTheirPredecessors(
       // We can return early.
       break;
     }
-    if (!AddItemThenPredecessors(trans, ready_unsynced_set, parent,
-                                 &item_dependencies)) {
-      // There was a parent/predecessor in conflict. We return without adding
-      // anything to |commit_set|.
-      DVLOG(1) << "Parent or parent's predecessor was in conflict, omitting "
-               << item;
+    if (IsEntryInConflict(parent)) {
+      // We ignore all entries that are children of a conflicing item.  Return
+      // false immediately to forget the traversal we've built up so far.
+      DVLOG(1) << "Parent was in conflict, omitting " << item;
       return false;
     }
+    AddItemThenPredecessors(trans,
+                            ready_unsynced_set,
+                            parent,
+                            &item_dependencies);
     parent_id = parent.Get(syncable::PARENT_ID);
   }
 
@@ -214,26 +216,24 @@ bool GetCommitIdsCommand::AddUncommittedParentsAndTheirPredecessors(
   return true;
 }
 
-bool GetCommitIdsCommand::AddItem(const std::set<int64>& ready_unsynced_set,
-                                  const syncable::Entry& item,
-                                  OrderedCommitSet* result) const {
+// Adds the given item to the list if it is unsynced and ready for commit.
+void GetCommitIdsCommand::TryAddItem(const std::set<int64>& ready_unsynced_set,
+                                     const syncable::Entry& item,
+                                     OrderedCommitSet* result) const {
   DCHECK(item.Get(syncable::IS_UNSYNCED));
-  // An item in conflict means that dependent items (successors and children)
-  // cannot be added either.
-  if (IsEntryInConflict(item))
-    return false;
   int64 item_handle = item.Get(syncable::META_HANDLE);
-  if (ready_unsynced_set.count(item_handle) == 0) {
-    // It's not in conflict, but not ready for commit. Just return true without
-    // adding it to the commit set.
-    return true;
+  if (ready_unsynced_set.count(item_handle) != 0) {
+    result->AddCommitItem(item_handle, item.Get(syncable::ID),
+                          item.GetModelType());
   }
-  result->AddCommitItem(item_handle, item.Get(syncable::ID),
-                        item.GetModelType());
-  return true;
 }
 
-bool GetCommitIdsCommand::AddItemThenPredecessors(
+// Adds the given item, and all its unsynced predecessors.  The traversal will
+// be cut short if any item along the traversal is not IS_UNSYNCED, or if we
+// detect that this area of the tree has already been traversed.  Items that are
+// not 'ready' for commit (see IsEntryReadyForCommit()) will not be added to the
+// list, though they will not stop the traversal.
+void GetCommitIdsCommand::AddItemThenPredecessors(
     syncable::BaseTransaction* trans,
     const std::set<int64>& ready_unsynced_set,
     const syncable::Entry& item,
@@ -242,50 +242,44 @@ bool GetCommitIdsCommand::AddItemThenPredecessors(
   if (commit_set_->HaveCommitItem(item_handle)) {
     // We've already added this item to the commit set, and so must have
     // already added the predecessors as well.
-    return true;
+    return;
   }
-  if (!AddItem(ready_unsynced_set, item, result))
-    return false;  // Item is in conflict.
+  TryAddItem(ready_unsynced_set, item, result);
   if (item.Get(syncable::IS_DEL))
-    return true;  // Deleted items have no predecessors.
+    return;  // Deleted items have no predecessors.
 
   syncable::Id prev_id = item.GetPredecessorId();
   while (!prev_id.IsRoot()) {
     syncable::Entry prev(trans, syncable::GET_BY_ID, prev_id);
     CHECK(prev.good()) << "Bad id when walking predecessors.";
-    if (!prev.Get(syncable::IS_UNSYNCED))
-      break;
+    if (!prev.Get(syncable::IS_UNSYNCED)) {
+      // We're interested in "runs" of unsynced items.  This item breaks
+      // the streak, so we stop traversing.
+      return;
+    }
     int64 handle = prev.Get(syncable::META_HANDLE);
     if (commit_set_->HaveCommitItem(handle)) {
       // We've already added this item to the commit set, and so must have
       // already added the predecessors as well.
-      return true;
+      return;
     }
-    if (!AddItem(ready_unsynced_set, prev, result))
-      return false;  // Item is in conflict.
+    TryAddItem(ready_unsynced_set, prev, result);
     prev_id = prev.GetPredecessorId();
   }
-  return true;
 }
 
-bool GetCommitIdsCommand::AddPredecessorsThenItem(
+// Same as AddItemThenPredecessor, but the traversal order will be reversed.
+void GetCommitIdsCommand::AddPredecessorsThenItem(
     syncable::BaseTransaction* trans,
     const ModelSafeRoutingInfo& routes,
     const std::set<int64>& ready_unsynced_set,
     const syncable::Entry& item,
     OrderedCommitSet* result) const {
   OrderedCommitSet item_dependencies(routes);
-  if (!AddItemThenPredecessors(trans, ready_unsynced_set, item,
-                               &item_dependencies)) {
-    // Either the item or its predecessors are in conflict, so don't add any
-    // items to the commit set.
-    DVLOG(1) << "Predecessor was in conflict, omitting " << item;
-    return false;
-  }
+  AddItemThenPredecessors(trans, ready_unsynced_set, item, &item_dependencies);
 
   // Reverse what we added to get the correct order.
   result->AppendReverse(item_dependencies);
-  return true;
 }
 
 bool GetCommitIdsCommand::IsCommitBatchFull() const {
@@ -315,12 +309,12 @@ void GetCommitIdsCommand::AddCreatesAndMoves(
               routes,
               ready_unsynced_set,
               entry,
-              &item_dependencies) &&
-          AddPredecessorsThenItem(trans,
-                                  routes,
-                                  ready_unsynced_set,
-                                  entry,
-                                  &item_dependencies)) {
+              &item_dependencies)) {
+        AddPredecessorsThenItem(trans,
+                                routes,
+                                ready_unsynced_set,
+                                entry,
+                                &item_dependencies);
         commit_set_->Append(item_dependencies);
       }
     }
diff --git a/sync/engine/get_commit_ids_command.h b/sync/engine/get_commit_ids_command.h
index 1bbbecd..02d6766 100644
--- a/sync/engine/get_commit_ids_command.h
+++ b/sync/engine/get_commit_ids_command.h
@@ -70,14 +70,14 @@ class SYNC_EXPORT_PRIVATE GetCommitIdsCommand : public SyncerCommand {
       std::set<int64>* ready_unsynced_set);
 
  private:
-  // Add all the uncommitted parents (and their predecessors) of |item| to
-  // |result| if they are ready to commit. Entries are added in root->child
-  // order and predecessor->successor order.
+  // Add all the uncommitted parents of |item| to |result| if they are ready to
+  // commit. Entries are added in root->child order and predecessor->successor
+  // order.
   // Returns values:
-  //    False: if a dependent item was in conflict, and hence no child cannot be
+  //    False: if a parent item was in conflict, and hence no child cannot be
   //           committed.
-  //    True: if all parents and their predecessors were checked for commit
-  //          readiness and were added to |result| as necessary.
+  //    True: if all parents were checked for commit readiness and were added to
+  //          |result| as necessary.
   bool AddUncommittedParentsAndTheirPredecessors(
       syncable::BaseTransaction* trans,
       const ModelSafeRoutingInfo& routes,
@@ -90,32 +90,21 @@ class SYNC_EXPORT_PRIVATE GetCommitIdsCommand : public SyncerCommand {
   // Adds |item| to |result| if it's ready for committing and was not already
   // present.
   // Prereq: |item| is unsynced.
-  // Returns values:
-  //    False: if |item| was in conflict.
-  //    True: if |item| was checked for commit readiness and added to |result|
-  //          as necessary.
-  bool AddItem(const std::set<int64>& ready_unsynced_set,
-               const syncable::Entry& item,
-               sessions::OrderedCommitSet* result) const;
-
-  // Adds item and all its unsynced predecessors to |result| as necessary, as
-  // long as no item was in conflict.
-  // Return values:
-  //   False: if there was an entry in conflict.
-  //   True: if all entries were checked for commit readiness and added to
-  //         |result| as necessary.
-  bool AddItemThenPredecessors(syncable::BaseTransaction* trans,
+  void TryAddItem(const std::set<int64>& ready_unsynced_set,
+                  const syncable::Entry& item,
+                  sessions::OrderedCommitSet* result) const;
+
+  // Adds |item| and all its unsynced predecessors to |result| as necessary.
+  // Entries that are unsynced but not ready to commit are not added to the
+  // list, though they do not stop the traversal.
+  void AddItemThenPredecessors(syncable::BaseTransaction* trans,
                                const std::set<int64>& ready_unsynced_set,
                                const syncable::Entry& item,
                                sessions::OrderedCommitSet* result) const;
 
   // Appends all commit ready predecessors of |item|, followed by |item| itself,
-  // to |commit_set|, iff item and all its predecessors not in conflict.
-  // Return values:
-  //   False: if there was an entry in conflict.
-  //   True: if all entries were checked for commit readiness and added to
-  //         |result| as necessary.
-  bool AddPredecessorsThenItem(syncable::BaseTransaction* trans,
+  // to |commit_set|.
+  void AddPredecessorsThenItem(syncable::BaseTransaction* trans,
                                const ModelSafeRoutingInfo& routes,
                                const std::set<int64>& ready_unsynced_set,
                                const syncable::Entry& item,
diff --git a/sync/engine/syncer_unittest.cc b/sync/engine/syncer_unittest.cc
index c85ab7e..71eef90 100644
--- a/sync/engine/syncer_unittest.cc
+++ b/sync/engine/syncer_unittest.cc
@@ -644,19 +644,21 @@ TEST_F(SyncerTest, GetCommitIdsCommandTruncates) {
   }
 
   // The arrangement is now: x (b (d) c (e)) w j
-  // Entry "w" is in conflict, making its sucessors unready to commit.
+  // Entry "w" is in conflict, so it is not eligible for commit.
   vector<int64> unsynced_handle_view;
   vector<syncable::Id> expected_order;
   {
     syncable::ReadTransaction rtrans(FROM_HERE, directory());
     GetUnsyncedEntries(&rtrans, &unsynced_handle_view);
   }
-  // The expected order is "x", "b", "c", "d", "e", truncated appropriately.
+  // The expected order is "x", "b", "c", "d", "e", "j", truncated
+  // appropriately.
   expected_order.push_back(ids_.MakeServer("x"));
   expected_order.push_back(ids_.MakeLocal("b"));
   expected_order.push_back(ids_.MakeLocal("c"));
   expected_order.push_back(ids_.MakeLocal("d"));
   expected_order.push_back(ids_.MakeLocal("e"));
+  expected_order.push_back(ids_.MakeLocal("j"));
   DoTruncationTest(unsynced_handle_view, expected_order);
 }