Fix GetCommitIds local deletion case resulting in orphaning of directory entries

This fixes filtering of commits in the case when a hierarchy of bookmarks
gets deleted and there is a conflict in the middle of the hierarchy.
Before the fix the folder above the conflicting entry would be still
committed and then subsequently deleted and that would leave the conflicting
entry orphaned and unreachable on both the clint and the server.

The fix provides a better implementation of FilterUnreadyEntries which
removes not only entries that are in direct conflict themselves but also all
other entries dependent on them. For conflicting deleted entries it removes
all deleted folders above them. For conflicting non-deleted folders it removes
all entries below (prior to the fix that was done in the ordering part of the
algorithm).

I've included a new unit test that reproduces the bug condition and
verifies the fix.

BUG=569775

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

Cr-Commit-Position: refs/heads/master@{#367565}

2 files changed, 312 insertions, 61 deletions

diff --git a/sync/engine/get_commit_ids.cc b/sync/engine/get_commit_ids.cc
index 85c14d8..a4c7f6b 100644
--- a/sync/engine/get_commit_ids.cc
+++ b/sync/engine/get_commit_ids.cc
@@ -119,20 +119,17 @@ bool HasAttachmentNotOnServer(const syncable::Entry& entry) {
   return false;
 }
 
-// An entry is not considered ready for commit if any are true:
-// 1. It's in conflict.
-// 2. It requires encryption (either the type is encrypted but a passphrase
+// An entry may not commit if any are true:
+// 1. It requires encryption (either the type is encrypted but a passphrase
 //    is missing from the cryptographer, or the entry itself wasn't properly
 //    encrypted).
-// 3. It's type is currently throttled.
-// 4. It's a delete but has not been committed.
-bool IsEntryReadyForCommit(ModelTypeSet requested_types,
-                           ModelTypeSet encrypted_types,
-                           bool passphrase_missing,
-                           const syncable::Entry& entry) {
+// 2. It's type is currently throttled.
+// 3. It's a delete but has not been committed.
+bool MayEntryCommit(ModelTypeSet requested_types,
+                    ModelTypeSet encrypted_types,
+                    bool passphrase_missing,
+                    const syncable::Entry& entry) {
   DCHECK(entry.GetIsUnsynced());
-  if (IsEntryInConflict(entry))
-    return false;
 
   const ModelType type = entry.GetModelType();
   // We special case the nigori node because even though it is considered an
@@ -186,6 +183,74 @@ bool IsEntryReadyForCommit(ModelTypeSet requested_types,
   return true;
 }
 
+bool SupportsHierarchy(const syncable::Entry& item) {
+  // Types with explicit server supported hierarchy only.
+  return IsTypeWithServerGeneratedRoot(item.GetModelType());
+}
+
+// Excludes ancestors of deleted conflicted items from
+// |ready_unsynced_set|.
+void ExcludeDeletedAncestors(
+    syncable::BaseTransaction* trans,
+    const std::vector<int64_t>& deleted_conflicted_items,
+    std::set<int64_t>* ready_unsynced_set) {
+  for (auto iter = deleted_conflicted_items.begin();
+       iter != deleted_conflicted_items.end(); ++iter) {
+    syncable::Entry item(trans, syncable::GET_BY_HANDLE, *iter);
+    syncable::Id parent_id = item.GetParentId();
+    DCHECK(!parent_id.IsNull());
+
+    while (!parent_id.IsRoot()) {
+      syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id);
+      CHECK(parent.good()) << "Bad user-only parent in item path.";
+      int64_t handle = parent.GetMetahandle();
+
+      if (!parent.GetIsDel())
+        break;
+
+      auto ready_iter = ready_unsynced_set->find(handle);
+      if (ready_iter == ready_unsynced_set->end())
+        break;
+
+      // Remove this entry from |ready_unsynced_set|.
+      ready_unsynced_set->erase(ready_iter);
+      parent_id = parent.GetParentId();
+    }
+  }
+}
+
+// Iterates over children of items from |conflicted_items| list that are in
+// |ready_unsynced_set|, exludes them from |ready_unsynced_set| and adds them
+// to |excluded_items| list.
+void ExcludeChildren(syncable::BaseTransaction* trans,
+                     const std::vector<int64_t>& conflicted_items,
+                     std::vector<int64_t>* excluded_items,
+                     std::set<int64_t>* ready_unsynced_set) {
+  for (auto iter = conflicted_items.begin(); iter != conflicted_items.end();
+       ++iter) {
+    syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
+
+    if (!entry.GetIsDir() || entry.GetIsDel())
+      continue;
+
+    std::vector<int64_t> children;
+    entry.GetChildHandles(&children);
+
+    for (std::vector<int64_t>::const_iterator child_iter = children.begin();
+         child_iter != children.end(); ++child_iter) {
+      // Collect all child handles that are in |ready_unsynced_set|.
+      int64_t child_handle = *child_iter;
+      auto ready_iter = ready_unsynced_set->find(child_handle);
+      if (ready_iter != ready_unsynced_set->end()) {
+        // Remove this entry from |ready_unsynced_set| and add it
+        // to |excluded_items|.
+        ready_unsynced_set->erase(ready_iter);
+        excluded_items->push_back(child_handle);
+      }
+    }
+  }
+}
+
 // Filters |unsynced_handles| to remove all entries that do not belong to the
 // specified |requested_types|, or are not eligible for a commit at this time.
 void FilterUnreadyEntries(
@@ -195,21 +260,51 @@ void FilterUnreadyEntries(
     bool passphrase_missing,
     const syncable::Directory::Metahandles& unsynced_handles,
     std::set<int64_t>* ready_unsynced_set) {
-  for (syncable::Directory::Metahandles::const_iterator iter =
-       unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) {
+  std::vector<int64_t> deleted_conflicted_items;
+  std::vector<int64_t> conflicted_items;
+
+  // Go over all unsynced handles, filter the ones that might be committed based
+  // on type / encryption, then based on whether they are in conflict add them
+  // to either |ready_unsynced_set| or one of the conflicted lists.
+  for (auto iter = unsynced_handles.begin(); iter != unsynced_handles.end();
+       ++iter) {
     syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
     // TODO(maniscalco): While we check if entry is ready to be committed, we
     // also need to check that all of its ancestors (parents, transitive) are
     // ready to be committed.  Once attachments can prevent an entry from being
     // committable, this method must ensure all ancestors are ready for commit
     // (bug 356273).
-    if (IsEntryReadyForCommit(requested_types,
-                              encrypted_types,
-                              passphrase_missing,
-                              entry)) {
-      ready_unsynced_set->insert(*iter);
+    if (MayEntryCommit(requested_types, encrypted_types, passphrase_missing,
+                       entry)) {
+      if (IsEntryInConflict(entry)) {
+        // Conflicting hierarchical entries might prevent their ancestors or
+        // descendants from being committed.
+        if (SupportsHierarchy(entry)) {
+          if (entry.GetIsDel()) {
+            deleted_conflicted_items.push_back(*iter);
+          } else if (entry.GetIsDir()) {
+            // Populate the initial version of |conflicted_items| with folder
+            // items that are in conflict.
+            conflicted_items.push_back(*iter);
+          }
+        }
+      } else {
+        ready_unsynced_set->insert(*iter);
+      }
     }
   }
+
+  // If there are any deleted conflicted entries, remove their deleted ancestors
+  // from |ready_unsynced_set| as well.
+  ExcludeDeletedAncestors(trans, deleted_conflicted_items, ready_unsynced_set);
+
+  // Starting with conflicted_items containing conflicted folders go down and
+  // exclude all descendants from |ready_unsynced_set|.
+  while (!conflicted_items.empty()) {
+    std::vector<int64_t> new_list;
+    ExcludeChildren(trans, conflicted_items, &new_list, ready_unsynced_set);
+    conflicted_items.swap(new_list);
+  }
 }
 
 // This class helps to implement OrderCommitIds().  Its members track the
@@ -231,21 +326,19 @@ class Traversal {
  private:
   // The following functions do not modify the traversal directly.  They return
   // their results in the |result| vector instead.
-  bool AddUncommittedParents(const std::set<int64_t>& ready_unsynced_set,
+  void AddUncommittedParents(const std::set<int64_t>& ready_unsynced_set,
                              const syncable::Entry& item,
                              syncable::Directory::Metahandles* result) const;
 
-  void TryAddItem(const std::set<int64_t>& ready_unsynced_set,
+  bool TryAddItem(const std::set<int64_t>& ready_unsynced_set,
                   const syncable::Entry& item,
                   syncable::Directory::Metahandles* result) const;
 
-  bool AddDeletedParents(const std::set<int64_t>& ready_unsynced_set,
+  void AddDeletedParents(const std::set<int64_t>& ready_unsynced_set,
                          const syncable::Entry& item,
                          const syncable::Directory::Metahandles& traversed,
                          syncable::Directory::Metahandles* result) const;
 
-  bool SupportsHierarchy(const syncable::Entry& item) const;
-
   // Returns true if we've collected enough items.
   bool IsFull() const;
 
@@ -273,7 +366,7 @@ Traversal::Traversal(syncable::BaseTransaction* trans,
 
 Traversal::~Traversal() {}
 
-bool Traversal::AddUncommittedParents(
+void Traversal::AddUncommittedParents(
     const std::set<int64_t>& ready_unsynced_set,
     const syncable::Entry& item,
     syncable::Directory::Metahandles* result) const {
@@ -291,41 +384,40 @@ bool Traversal::AddUncommittedParents(
       // We can return early.
       break;
     }
-    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;
+
+    if (!TryAddItem(ready_unsynced_set, parent, &dependencies)) {
+      // The parent isn't in |ready_unsynced_set|.
+      break;
     }
-    TryAddItem(ready_unsynced_set, parent, &dependencies);
+
     parent_id = parent.GetParentId();
   }
 
   // Reverse what we added to get the correct order.
   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
-  return true;
 }
 
 // Adds the given item to the list if it is unsynced and ready for commit.
-void Traversal::TryAddItem(const std::set<int64_t>& ready_unsynced_set,
+bool Traversal::TryAddItem(const std::set<int64_t>& ready_unsynced_set,
                            const syncable::Entry& item,
                            syncable::Directory::Metahandles* result) const {
   DCHECK(item.GetIsUnsynced());
   int64_t item_handle = item.GetMetahandle();
   if (ready_unsynced_set.count(item_handle) != 0) {
     result->push_back(item_handle);
+    return true;
   }
+  return false;
 }
 
 // Traverses the tree from bottom to top, adding the deleted parents of the
 // given |item|.  Stops traversing if it encounters a non-deleted node, or
-// a node that was already listed in the |traversed| list.  Returns an error
-// (false) if a node along the traversal is in a conflict state.
+// a node that was already listed in the |traversed| list.
 //
 // The result list is reversed before it is returned, so the resulting
 // traversal is in top to bottom order.  Also note that this function appends
 // to the result list without clearing it.
-bool Traversal::AddDeletedParents(
+void Traversal::AddDeletedParents(
     const std::set<int64_t>& ready_unsynced_set,
     const syncable::Entry& item,
     const syncable::Directory::Metahandles& traversed,
@@ -363,19 +455,17 @@ bool Traversal::AddDeletedParents(
       // We can return early.
       break;
     }
-    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;
+
+    if (!TryAddItem(ready_unsynced_set, parent, &dependencies)) {
+      // The parent isn't in ready_unsynced_set.
+      break;
     }
-    TryAddItem(ready_unsynced_set, parent, &dependencies);
+
     parent_id = parent.GetParentId();
   }
 
   // Reverse what we added to get the correct order.
   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
-  return true;
 }
 
 bool Traversal::IsFull() const {
@@ -386,11 +476,6 @@ bool Traversal::HaveItem(int64_t handle) const {
   return added_handles_.find(handle) != added_handles_.end();
 }
 
-bool Traversal::SupportsHierarchy(const syncable::Entry& item) const {
-  // Types with explicit server supported hierarchy only.
-  return IsTypeWithServerGeneratedRoot(item.GetModelType());
-}
-
 void Traversal::AppendManyToTraversal(
     const syncable::Directory::Metahandles& handles) {
   out_->insert(out_->end(), handles.begin(), handles.end());
@@ -419,11 +504,9 @@ void Traversal::AddCreatesAndMoves(
         // We only commit an item + its dependencies if it and all its
         // dependencies are not in conflict.
         syncable::Directory::Metahandles item_dependencies;
-        if (AddUncommittedParents(ready_unsynced_set, entry,
-                                  &item_dependencies)) {
-          TryAddItem(ready_unsynced_set, entry, &item_dependencies);
-          AppendManyToTraversal(item_dependencies);
-        }
+        AddUncommittedParents(ready_unsynced_set, entry, &item_dependencies);
+        TryAddItem(ready_unsynced_set, entry, &item_dependencies);
+        AppendManyToTraversal(item_dependencies);
       } else {
         // No hierarchy dependencies, just commit the item itself.
         AppendToTraversal(metahandle);
@@ -461,16 +544,12 @@ void Traversal::AddDeletes(const std::set<int64_t>& ready_unsynced_set) {
     if (entry.GetIsDel()) {
       if (SupportsHierarchy(entry)) {
         syncable::Directory::Metahandles parents;
-        if (AddDeletedParents(ready_unsynced_set, entry, deletion_list,
-                              &parents)) {
-          // Append parents and chilren in top to bottom order.
-          deletion_list.insert(deletion_list.end(), parents.begin(),
-                               parents.end());
-          deletion_list.push_back(metahandle);
-        }
-      } else {
-        deletion_list.push_back(metahandle);
+        AddDeletedParents(ready_unsynced_set, entry, deletion_list, &parents);
+        // Append parents and chilren in top to bottom order.
+        deletion_list.insert(deletion_list.end(), parents.begin(),
+                             parents.end());
       }
+      deletion_list.push_back(metahandle);
     }
   }
 
diff --git a/sync/engine/syncer_unittest.cc b/sync/engine/syncer_unittest.cc
index 073ac51..b2a92de 100644
--- a/sync/engine/syncer_unittest.cc
+++ b/sync/engine/syncer_unittest.cc
@@ -62,6 +62,7 @@
 #include "sync/util/cryptographer.h"
 #include "sync/util/extensions_activity.h"
 #include "sync/util/time.h"
+#include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 using base::TimeDelta;
@@ -2809,6 +2810,177 @@ TEST_F(SyncerTest, DeletingEntryInFolder) {
   EXPECT_EQ(0, GetCommitCounters(BOOKMARKS).num_commits_conflict);
 }
 
+// Test conflict resolution when deleting a hierarchy of nodes within a folder
+// and running into a conflict in one of items. The conflict in a deleted
+// item must prevent all deleted ancestors from being committed as well;
+// otherwise the conflicting item would end up being orphaned.
+TEST_F(SyncerTest, DeletingFolderWithConflictInSubfolder) {
+  int64_t top_handle, nested_handle, leaf_handle;
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, directory());
+    MutableEntry top_entry(&trans, CREATE, BOOKMARKS, trans.root_id(), "top");
+    ASSERT_TRUE(top_entry.good());
+    top_entry.PutIsDir(true);
+    top_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    top_entry.PutIsUnsynced(true);
+    top_handle = top_entry.GetMetahandle();
+
+    MutableEntry nested_entry(&trans, CREATE, BOOKMARKS, top_entry.GetId(),
+                              "nested");
+    ASSERT_TRUE(nested_entry.good());
+    nested_entry.PutIsDir(true);
+    nested_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    nested_entry.PutIsUnsynced(true);
+    nested_handle = nested_entry.GetMetahandle();
+
+    MutableEntry leaf_entry(&trans, CREATE, BOOKMARKS, nested_entry.GetId(),
+                            "leaf");
+    ASSERT_TRUE(leaf_entry.good());
+    leaf_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    leaf_entry.PutIsUnsynced(true);
+    leaf_handle = leaf_entry.GetMetahandle();
+  }
+  EXPECT_TRUE(SyncShareNudge());
+
+  // Delete all 3 entries and also add unapplied update to the middle one.
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, directory());
+    MutableEntry leaf_entry(&trans, GET_BY_HANDLE, leaf_handle);
+    ASSERT_TRUE(leaf_entry.good());
+    EXPECT_TRUE(leaf_entry.GetId().ServerKnows());
+    leaf_entry.PutIsUnsynced(true);
+    leaf_entry.PutIsDel(true);
+
+    MutableEntry nested_entry(&trans, GET_BY_HANDLE, nested_handle);
+    ASSERT_TRUE(nested_entry.good());
+    EXPECT_TRUE(nested_entry.GetId().ServerKnows());
+    nested_entry.PutIsUnsynced(true);
+    nested_entry.PutIsDel(true);
+
+    sync_pb::EntitySpecifics specifics;
+    specifics.mutable_bookmark()->set_url("http://demo/");
+    specifics.mutable_bookmark()->set_favicon("PNG");
+    nested_entry.PutServerSpecifics(specifics);
+    // This will put the entry into conflict.
+    nested_entry.PutIsUnappliedUpdate(true);
+    nested_entry.PutServerVersion(nested_entry.GetBaseVersion() + 1);
+
+    MutableEntry top_entry(&trans, GET_BY_HANDLE, top_handle);
+    ASSERT_TRUE(top_entry.good());
+    EXPECT_TRUE(top_entry.GetId().ServerKnows());
+    top_entry.PutIsUnsynced(true);
+    top_entry.PutIsDel(true);
+  }
+  EXPECT_TRUE(SyncShareNudge());
+
+  // Verify that the top folder hasn't been committed. Doing so would
+  // orphan the nested folder.
+  syncable::Id top_id;
+  {
+    syncable::ReadTransaction trans(FROM_HERE, directory());
+    Entry top_entry(&trans, GET_BY_HANDLE, top_handle);
+    ASSERT_TRUE(top_entry.good());
+    top_id = top_entry.GetId();
+
+    EXPECT_TRUE(top_entry.GetIsUnsynced());
+    EXPECT_TRUE(top_entry.GetIsDel());
+  }
+
+  EXPECT_THAT(mock_server_->committed_ids(),
+              testing::Not(testing::Contains(top_id)));
+}
+
+// Test conflict resolution when committing a hierarchy of items and running
+// into a conflict in a parent folder. A conflicting parent must prevent any
+// of its descendants from being committed.
+TEST_F(SyncerTest, CommittingItemsWithConflictInParentFolder) {
+  int64_t top_handle, nested_handle, leaf_handle;
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, directory());
+    MutableEntry top_entry(&trans, CREATE, BOOKMARKS, trans.root_id(), "top");
+    ASSERT_TRUE(top_entry.good());
+    top_entry.PutIsDir(true);
+    top_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    top_entry.PutIsUnsynced(true);
+    top_handle = top_entry.GetMetahandle();
+
+    MutableEntry nested_entry(&trans, CREATE, BOOKMARKS, top_entry.GetId(),
+                              "nested");
+    ASSERT_TRUE(nested_entry.good());
+    nested_entry.PutIsDir(true);
+    nested_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    nested_entry.PutIsUnsynced(true);
+    nested_handle = nested_entry.GetMetahandle();
+
+    MutableEntry leaf_entry(&trans, CREATE, BOOKMARKS, nested_entry.GetId(),
+                            "leaf");
+    ASSERT_TRUE(leaf_entry.good());
+    leaf_entry.PutSpecifics(DefaultBookmarkSpecifics());
+    leaf_entry.PutIsUnsynced(true);
+    leaf_handle = leaf_entry.GetMetahandle();
+  }
+  EXPECT_TRUE(SyncShareNudge());
+
+  // Touch all 3 entries and also add unapplied update to the top one.
+  syncable::Id top_id, nested_id, leaf_id;
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, directory());
+    sync_pb::EntitySpecifics specifics;
+    specifics.mutable_bookmark()->set_url("http://demo/");
+
+    MutableEntry top_entry(&trans, GET_BY_HANDLE, top_handle);
+    ASSERT_TRUE(top_entry.good());
+    top_id = top_entry.GetId();
+    EXPECT_TRUE(top_id.ServerKnows());
+    top_entry.PutIsUnsynced(true);
+    top_entry.PutSpecifics(specifics);
+
+    // This will put the top entry into conflict.
+    top_entry.PutIsUnappliedUpdate(true);
+    top_entry.PutServerIsDel(true);
+    top_entry.PutServerVersion(top_entry.GetBaseVersion() + 1);
+
+    MutableEntry nested_entry(&trans, GET_BY_HANDLE, nested_handle);
+    ASSERT_TRUE(nested_entry.good());
+    nested_id = nested_entry.GetId();
+    EXPECT_TRUE(nested_id.ServerKnows());
+    nested_entry.PutSpecifics(specifics);
+    nested_entry.PutIsUnsynced(true);
+
+    MutableEntry leaf_entry(&trans, GET_BY_HANDLE, leaf_handle);
+    ASSERT_TRUE(leaf_entry.good());
+    leaf_id = leaf_entry.GetId();
+    EXPECT_TRUE(leaf_id.ServerKnows());
+    leaf_entry.PutSpecifics(specifics);
+    leaf_entry.PutIsUnsynced(true);
+  }
+  EXPECT_TRUE(SyncShareNudge());
+
+  // Verify that all 3 entries remain unsynced
+  EXPECT_THAT(mock_server_->committed_ids(),
+              testing::Not(testing::Contains(top_id)));
+  EXPECT_THAT(mock_server_->committed_ids(),
+              testing::Not(testing::Contains(nested_id)));
+  EXPECT_THAT(mock_server_->committed_ids(),
+              testing::Not(testing::Contains(leaf_id)));
+
+  {
+    syncable::ReadTransaction trans(FROM_HERE, directory());
+
+    Entry top_entry(&trans, GET_BY_HANDLE, top_handle);
+    ASSERT_TRUE(top_entry.good());
+    ASSERT_TRUE(top_entry.GetIsUnsynced());
+
+    Entry nested_entry(&trans, GET_BY_HANDLE, nested_handle);
+    ASSERT_TRUE(nested_entry.good());
+    ASSERT_TRUE(nested_entry.GetIsUnsynced());
+
+    Entry leaf_entry(&trans, GET_BY_HANDLE, leaf_handle);
+    ASSERT_TRUE(leaf_entry.good());
+    ASSERT_TRUE(leaf_entry.GetIsUnsynced());
+  }
+}
+
 // Test conflict resolution when handling an update for an item with specified
 // Parent ID and having an implicit (unset) Parent ID in the update.
 TEST_F(SyncerTest, ConflictWithImplicitParent) {