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

chrome/browser/sync/engine/conflict_resolver.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/sync/engine/conflict_resolver.h"
 
 #include <algorithm>
+#include <list>
 #include <map>
 #include <set>
 
 #include "base/location.h"
 #include "base/metrics/histogram.h"
 #include "chrome/browser/sync/engine/syncer.h"
 #include "chrome/browser/sync/engine/syncer_util.h"
 #include "chrome/browser/sync/protocol/nigori_specifics.pb.h"
 #include "chrome/browser/sync/protocol/service_constants.h"
 #include "chrome/browser/sync/sessions/status_controller.h"
 #include "chrome/browser/sync/syncable/directory_manager.h"
 #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;
 using syncable::Directory;
 using syncable::Entry;
 using syncable::GetModelTypeFromSpecifics;
 using syncable::Id;
 using syncable::IsRealDataType;
 using syncable::MutableEntry;
 using syncable::ScopedDirLookup;
@@ skipping 71 matching lines @@
     return NO_SYNC_PROGRESS;
   }
 
   // This logic determines "client wins" vs. "server wins" strategy picking.
   // By the time we get to this point, we rely on the following to be true:
   // a) We can decrypt both the local and server data (else we'd be in
   //    conflict encryption and not attempting to resolve).
   // 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
   //    encrypted with the default key, and all other visible properties match,
   //    then we can safely ignore the local changes as redundant.
   // e) Otherwise if the base_server_specifics match the server_specifics, no
   //    functional change must have been made server-side (else
   //    base_server_specifics would have been cleared), and we can therefore
   //    safely ignore the server changes as redundant.
   // 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
     // be nice if we could route this back to ModelAssociator code to pick one
     // of three options: CLIENT, SERVER, or MERGE.  Some datatypes (autofill)
     // are easily mergeable.
     // See http://crbug.com/77339.
     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 =
         entry.Get(syncable::SERVER_SPECIFICS);
     const sync_pb::EntitySpecifics& base_server_specifics =
         entry.Get(syncable::BASE_SERVER_SPECIFICS);
     std::string decrypted_specifics, decrypted_server_specifics;
     bool specifics_match = false;
     bool server_encrypted_with_default_key = false;
     if (specifics.has_encrypted()) {
@@ skipping 60 matching lines @@
       // We deliberately leave the server's device information. This client will
       // add it's own device information on restart.
       entry.Put(syncable::SPECIFICS, specifics);
       DVLOG(1) << "Resovling simple conflict, merging nigori nodes: " << entry;
       status->increment_num_server_overwrites();
       OverwriteServerChanges(trans, &entry);
       UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
                                 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",
                                 CHANGES_MATCH,
                                 CONFLICT_RESOLUTION_SIZE);
     } else if (base_server_specifics_match) {
       DVLOG(1) << "Resolving simple conflict, ignoring server encryption "
                << " changes for: " << entry;
       status->increment_num_server_overwrites();
       OverwriteServerChanges(trans, &entry);
       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();
       DVLOG(1) << "Resolving simple conflict, overwriting server changes "
                << "for: " << entry;
       UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
                                 OVERWRITE_SERVER,
                                 CONFLICT_RESOLUTION_SIZE);
     } else {

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

I believe this is where your change on line 234 starts to matter.  After your
change is committed, we will no longer ignore conflicts when !position_matches
and the branch on line 255 is not taken.  Instead, we will overwrite the local
entries with the new position information provided by the server.  Is that
correct?

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

See above comment. When the position doesn't match, we will typically overwrite
the local data, yes (excluding the server encryption case and the line 255 case)

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

As I understand it, most conflicts end up being resolved by one of the branches
of the if statement that starts at line 199.  There are other cases (ie.
SERVER_IS_DEL), but I think we don't care about them here.

Conflicts are partitioned into different sets according to what 'if' branch they
fall into:
* line 199: the Nigori conflicts (irrelevant in this discussion)
* line 233: "everything matches" conflicts
* line 247: encryption only conflicts
* line 255: server overwrite conflicts
* line 263: local overwrite conflicts

Your change to the if statement on line 233 made it slightly harder for a
conflict to qualify for the "everything matches" set.  Some conflicts that would
have been handled by the branch starting at line 233 will be handled by a
different branch following your change.  Let's refer to these as the
"position-only" conflicts.

So where do these position only conflicts get handled following your change?  I
presume not the branch in line 247 (at the moment I don't quite see how, but I
think we shouldn't resolve these as encryption only conflicts and assume there
is something in the definition of base_server_specifics_match that ensures
this).  I know they won't be handled by the branch on line 255, since, as I have
defined them, position only conflicts must meet all the conditions of line 233
*except* position_matches, and are therefore they fail the check on line 255
(because, according to the definition and line 233, they have !entry_deleted &&
name_matches && parent_matches && specifics_match && !position_matches).

Finally, we arrive at line 263.  By process of elimination, it must be this
branch that handles position only conflicts.  

The point I'm making here is that your change will cause entries that meet my
definition of position only conflicts to be handled by the else branch on line
263, whereas they would have been handled by the branch at line 233 before you
introduced the position_matches variable.  Conflicts that do not fall into the
set of position only conflicts are not affected in any way.  

I mention all this because I'm not sure my conclusion makes sense.  Let me know
if I've misunderstood the change in some way.

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

Okay, I think we're in agreement here then. Yes, the point of this change is to
make the "everything matches" case more strict. The reason for this is that
falling into this case unnecessarily results in the client and server diverging
in their view of the world, which can cause significant problems down the line. 

Previously, I was ignoring position conflicts. Now, position conflicts will
typically wind up in overwriting local data (server wins), but will definitely
not result in everything matches.

       DVLOG(1) << "Resolving simple conflict, ignoring local changes for: "
                << entry;
       IgnoreLocalChanges(&entry);
       status->increment_num_local_overwrites();
       UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
                                 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.
     if (entry.Get(syncable::IS_DIR)) {
       Directory::ChildHandles children;
       trans->directory()->GetChildHandlesById(trans,
                                               entry.Get(syncable::ID),
                                               &children);
       if (0 != children.size()) {
         DVLOG(1) << "Entry is a server deleted directory with local contents, "
@@ skipping 38 matching lines @@
 }
 
 bool ConflictResolver::ResolveSimpleConflicts(
     syncable::WriteTransaction* trans,
     const Cryptographer* cryptographer,
     const ConflictProgress& progress,
     sessions::StatusController* status) {
   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:
+      // 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;
-        case SYNC_PROGRESS:
-          forward_progress = true;
-          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);
       }
     }
   }
   return forward_progress;
 }
 
 bool ConflictResolver::ResolveConflicts(syncable::WriteTransaction* trans,
                                         const Cryptographer* cryptographer,
                                         const ConflictProgress& progress,
                                         sessions::StatusController* status) {
   // TODO(rlarocque): A good amount of code related to the resolution of
   // conflict sets has been deleted here.  This was done because the code had
   // not been used in years.  An unrelated bug fix accidentally re-enabled the
   // code, forcing us to make a decision about what we should do with the code.
   // We decided to do the safe thing and delete it for now.  This restores the
   // behaviour we've relied on for quite some time.  We should think about what
   // that code was trying to do and consider re-enabling parts of it.
 
   if (progress.ConflictSetsSize() > 0) {
     DVLOG(1) << "Detected " << progress.IdToConflictSetSize()
         << " non-simple conflicting entries in " << progress.ConflictSetsSize()
         << " unprocessed conflict sets.";
   }
 
   return ResolveSimpleConflicts(trans, cryptographer, progress, status);
 }
 
 }  // namespace browser_sync