Fix GetCommitIds local deletion case resulting in orphaning of directory entries

sync/engine/get_commit_ids.cc

Index: sync/engine/get_commit_ids.cc
diff --git a/sync/engine/get_commit_ids.cc b/sync/engine/get_commit_ids.cc
index 85c14d8e2b643183cc2396dd0f469b49ea237db3..a4c7f6b7f7944f97b1c2b44a37af5115608e7aec 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);
     }
   }