[Sync] Don't commit items with predecessors/parents in conflict.

chrome/browser/sync/engine/conflict_resolver.cc

Index: chrome/browser/sync/engine/conflict_resolver.cc
diff --git a/chrome/browser/sync/engine/conflict_resolver.cc b/chrome/browser/sync/engine/conflict_resolver.cc
index cca0c31d8939b42b18b9cd0db87ec8e9c1230eb8..b596a9a7204565e27d87bee444a1689449f7df87 100644
--- a/chrome/browser/sync/engine/conflict_resolver.cc
+++ b/chrome/browser/sync/engine/conflict_resolver.cc
@@ -5,6 +5,7 @@
 #include "chrome/browser/sync/engine/conflict_resolver.h"
 
 #include <algorithm>
+#include <list>
 #include <map>
 #include <set>
 
@@ -19,6 +20,7 @@
 #include "chrome/browser/sync/syncable/syncable.h"
 #include "chrome/browser/sync/util/cryptographer.h"
 
+using std::list;
 using std::map;
 using std::set;
 using syncable::BaseTransaction;
@@ -110,7 +112,7 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
   // b) All unsynced changes have been re-encrypted with the default key (
   //    occurs either in AttemptToUpdateEntry, SetPassphrase, or
   //    RefreshEncryption).
-  // c) Prev_server_specifics having a valid datatype means that we received
+  // c) Base_server_specifics having a valid datatype means that we received
   //    an undecryptable update that only changed specifics, and since then have
   //    not received any further non-specifics-only or decryptable updates.
   // d) If the server_specifics match specifics, server_specifics are
@@ -123,9 +125,6 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
   // f) Otherwise, it's in general safer to ignore local changes, with the
   //    exception of deletion conflicts (choose to undelete) and conflicts
   //    where the non_unique_name or parent don't match.
-  // TODO(sync): We can't compare position here without performing the
-  // NEXT_ID/PREV_ID -> position_in_parent interpolation. Fix that, and take it
-  // into account.
   if (!entry.Get(syncable::SERVER_IS_DEL)) {
     // TODO(nick): The current logic is arbitrary; instead, it ought to be made
     // consistent with the ModelAssociator behavior for a datatype.  It would
@@ -136,8 +135,22 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
     bool name_matches = entry.Get(syncable::NON_UNIQUE_NAME) ==
                         entry.Get(syncable::SERVER_NON_UNIQUE_NAME);
     bool parent_matches = entry.Get(syncable::PARENT_ID) ==
-                                    entry.Get(syncable::SERVER_PARENT_ID);
+                          entry.Get(syncable::SERVER_PARENT_ID);
     bool entry_deleted = entry.Get(syncable::IS_DEL);
+    // This positional check is conservative. It will likely be false if the
+    // predecessor is unsynced/unapplied. For this reason, we ensure conflicting
+    // predecessors are resolved before their successors. Being
+    // conservative results in being less likely to lose local positioning
+    // changes, with the cost of occasional unnecessary commits.
+    // TODO(zea): change this once we can directly compare server position to
+    // client position.
+    syncable::Id server_prev_id = entry.ComputePrevIdFromServerPosition(

[rlarocque, 2012/01/10 23:39:51]

ComputePrevIdFromServerPosition() will not return entries that are UNSYNCED or
UNAPPLIED_UPDATES.  Processing predecessors first, as you do in this CL, should
ensure this is not a problem 99% of the time.  

In the rare case where there is a conflict set, however, there could be UNSYNCED
or UNAPPLIED updates preceding the current entry.  That will affect the
correctness of this function.

Conflict sets are so rare that I'm not sure I care about this.  You might want
to mention it in the comments, though.

=========

On second thought, it's worse than that.  

IngoreLocalChanges() and OverwriteServerChanges() will unset one of the two
flags (IS_UNSYNCED or IS_UNAPPLIED_UPDATES).  By definition, simple conflicts
start with both flags set, so there will still be one flag left set afterwards. 
This flag will not get cleared until the updates are actually applied in the
APPLY_UPDATES_TO_RESOLVE_CONFLICTS step.  So you can't rely on
ComputePrevIdFromServerPosition() + resolving conflicts in order.

ComputePrevIdFromServerPosition() has good reason for not returning unsynced or
unapplied entries.  This is by design and will not be easy to work around.

[Nicolas Zea, 2012/01/18 02:54:39]

See my updated comments. Basically, this situation is fine. We'll wind up
thinking the position changed (even if it didn't), but that's okay. As long as
we never think the position stayed the same when it in fact changed we're good.

[rlarocque, 2012/01/18 20:21:55]

It sounds like you're expecting this to return the first non-conflicting item to
the left of the consecutive string of conflicts of which 'entry' is a member,
using client-side ordering, before any conflict resolution has taken place. 
Correct?

If that is the case, why not traverse the list yourself, rather than relying on
ComputePrevIdFromServerPosition()?  I suspect that we could contrive a case
where using the server position as a starting point (rather than starting with
'entry') leads to invalid results.

[Nicolas Zea, 2012/01/18 20:40:42]

No, I expect it to return the first fully synced item to the left of the
'entry', using server side ordering, after any "everything matches" conflict
resolution has taken place. The key here is that it uses server side ordering,
which is why I can't simply traverse using the prev id.

In addition, because we traverse in predecessor->successor order, and the
"everything matches" case results in entries becoming "fully synced" (we unset
IS_UNSYNCED and IS_UNAPPLIED), we support chains of conflicting entries where
all items have "everything matches". If we didn't traverse in
predecessor->successor order for chains of conflicting entries, then this
ComputerPrevIdFromServerPosition would ignore potential "everything matches"
entries (since it looks at the predecessors and they won't be marked as "fully
synced" yet).

Does that make more sense?

+        entry.Get(syncable::SERVER_PARENT_ID));

[rlarocque, 2012/01/10 23:39:51]

SERVER_PARENT_ID?  Did you mean SERVER_PREV_ID?

[Nicolas Zea, 2012/01/18 02:54:39]

No, you pass the parent to ComputePrevIdFromServerPosition.

+    bool position_matches = parent_matches &&
+                            (server_prev_id == entry.Get(syncable::PREV_ID));

[ncarter (slow), 2012/01/04 21:37:59]

The comment about 'conservative' could be read to mean a few different (and
opposite) things. It might be clearer to say that you want position_matches to
be a sufficient (but not necessary) criterion implying that the client and
server 
agree, position-wise.

But is it a sufficient criterion? In the case of:

Initial State: [abcde]
Server Updates: [aCDbe] (C & D updated)
Local State: [aDCbe] (C & D both unsynced + unapplied)

In this case, D's PREV_ID is "a", and D's ComputePrevIdFromServerPosition will
also be "a" (because that function will never return an unapplied update).

I'm having trouble reasoning about this code.  I think your change definitely
makes things better in the sense that "Resolving simple conflict, everything
matches ..." case used to not take position into account at all, and that case
(which resolves things by simply unsetting the UNSYNCED and UNAPPLIED bits) has
a high potential to introduce client vs. server state divergence.

But as I'm looking at this, I'm wondering if these checks are wrong from a
first-principles perspective. Let's chat offline.

[Nicolas Zea, 2012/01/18 02:54:39]

Upon further reflection, the code as stands actually covers this case. In this
example only one of the items is in "real" conflict. D will be treated as not
having had anything changed and resolved as such, but C's prev's won't match,
and it will be re-inserted appropriately.

+    DVLOG_IF(1, !position_matches) << "Position doesn't match, server prev id "
+        << " is " << server_prev_id << ", local prev id is "
+        << entry.Get(syncable::PREV_ID);
     const sync_pb::EntitySpecifics& specifics =
         entry.Get(syncable::SPECIFICS);
     const sync_pb::EntitySpecifics& server_specifics =
@@ -218,15 +231,14 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
                                 NIGORI_MERGE,
                                 CONFLICT_RESOLUTION_SIZE);
     } else if (!entry_deleted && name_matches && parent_matches &&
-               specifics_match) {
+               position_matches && specifics_match) {
       DVLOG(1) << "Resolving simple conflict, everything matches, ignoring "
                << "changes for: " << entry;
       // This unsets both IS_UNSYNCED and IS_UNAPPLIED_UPDATE, and sets the
       // BASE_VERSION to match the SERVER_VERSION. If we didn't also unset
-      // IS_UNAPPLIED_UPDATE, then we would lose unsynced positional data
-      // when the server update gets applied and the item is re-inserted into
-      // the PREV_ID/NEXT_ID linked list (see above TODO about comparing
-      // positional info).
+      // IS_UNAPPLIED_UPDATE, then we would lose unsynced positional data from
+      // adjacent entries when the server update gets applied and the item is
+      // re-inserted into the PREV_ID/NEXT_ID linked list.
       OverwriteServerChanges(trans, &entry);
       IgnoreLocalChanges(&entry);
       UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
@@ -240,9 +252,6 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
       UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
                                 IGNORE_ENCRYPTION,
                                 CONFLICT_RESOLUTION_SIZE);
-      // Now that we've resolved the conflict, clear the prev server
-      // specifics.
-      entry.Put(syncable::BASE_SERVER_SPECIFICS, sync_pb::EntitySpecifics());
     } else if (entry_deleted || !name_matches || !parent_matches) {

[rlarocque, 2012/01/10 23:39:51]

Assertion:
If this condition is true, then we would never have been at risk of entering the
if branch on line 234.  In other words, your change has no effect in cases where
(entry_deleted || !name_matches || !parent_matches).

(This is building towards a conclusion in my next comment.)

[Nicolas Zea, 2012/01/18 02:54:39]

I'm not sure I understand this assertion. The if statement above is a stronger
condition than this one (although it includes this one) and has a stronger
action (unsetting both IS_UNSYNCED and IS_UNAPPLIED).

       OverwriteServerChanges(trans, &entry);
       status->increment_num_server_overwrites();
@@ -260,6 +269,9 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
                                 OVERWRITE_LOCAL,
                                 CONFLICT_RESOLUTION_SIZE);
     }
+    // Now that we've resolved the conflict, clear the prev server
+    // specifics.
+    entry.Put(syncable::BASE_SERVER_SPECIFICS, sync_pb::EntitySpecifics());
     return SYNC_PROGRESS;
   } else {  // SERVER_IS_DEL is true
     // If a server deleted folder has local contents we should be in a set.
@@ -318,21 +330,46 @@ bool ConflictResolver::ResolveSimpleConflicts(
   bool forward_progress = false;
   // First iterate over simple conflict items (those that belong to no set).
   set<Id>::const_iterator conflicting_item_it;
+  set<Id> processed_items;
   for (conflicting_item_it = progress.ConflictingItemsBegin();
        conflicting_item_it != progress.ConflictingItemsEnd();
        ++conflicting_item_it) {
     Id id = *conflicting_item_it;
+    if (processed_items.count(id) > 0)
+      continue;
     map<Id, ConflictSet*>::const_iterator item_set_it =
         progress.IdToConflictSetFind(id);
     if (item_set_it == progress.IdToConflictSetEnd() ||
         0 == item_set_it->second) {
-      // We have a simple conflict.
-      switch (ProcessSimpleConflict(trans, id, cryptographer, status)) {
-        case NO_SYNC_PROGRESS:
-          break;
-        case SYNC_PROGRESS:
-          forward_progress = true;
+      // We have a simple conflict. In order check if positions have changed,

[rlarocque, 2012/01/18 20:21:55]

I don't understand why this is necessary.

I think (but haven't 100% confirmed) that we won't modify any PREV_ID or
SERVER_POSITION_IN_PARENT values during this step of the syncer state machine. 
Those changes don't get applied until the APPLY_UPDATES_TO_RESOLVE_CONFLICTS
step.

What inputs to the position detection/conflict resolution will be affected by
the order in which conflicts are processed?

[Nicolas Zea, 2012/01/18 20:40:42]

You're right, we don't modify  anything except IS_UNSYNCED or IS_UNAPPLIED.  But
because ComputerPrevIdFromServerPosition will traverse backwards through the
predecessors, we need anything that should have been "everything matches" to
have already been processed. This is what enables us to handle chains of
"everything matches" conflicts by marking everything as fully synced. See my
response to your comment above..

+      // we need to process conflicting predecessors before successors. Traverse
+      // backwards through all continuous conflicting predecessors, building a
+      // stack of items to resolve in predecessor->successor order, then process
+      // each item individually.
+      list<Id> predecessors;
+      Id prev_id = id;
+      do {
+        predecessors.push_back(prev_id);
+        Entry entry(trans, syncable::GET_BY_ID, prev_id);
+        // Any entry in conflict must be valid.
+        CHECK(entry.good());
+        Id new_prev_id = entry.Get(syncable::PREV_ID);
+        if (new_prev_id == prev_id)
           break;
+        prev_id = new_prev_id;
+      } while (processed_items.count(prev_id) == 0 &&
+               progress.HasSimpleConflictItem(prev_id));  // Excludes root.
+      while (!predecessors.empty()) {
+        id = predecessors.back();
+        predecessors.pop_back();
+        switch (ProcessSimpleConflict(trans, id, cryptographer, status)) {
+          case NO_SYNC_PROGRESS:
+            break;
+          case SYNC_PROGRESS:
+            forward_progress = true;
+            break;
+        }
+        processed_items.insert(id);
       }
     }
   }