sync: Merge apply updates and resolve conflicts

sync: Merge apply updates and resolve conflicts

The conflict resolution code was executed after the commit for reasons
which no longer apply.  Because we no longer have to worry about
resolving hierarchy conflicts or nigori node conflicts, we have the
opportunity to move conflict resolution closer to update application.

One advantage of resolving conflicts early is that we no longer require
an extra sync cycle to commit any 'local wins' conflict resolutions.
This makes SYNC_CYCLE_CONTINUATION sync cycles obsolete.

Another advantage is that update application and conflict resolution can
be performed without releasing the sync lock, which eliminates several
types of races that we used to have to worry about.  It's probably more
efficient, too.

It allows us to guarantee that there are no simple conflicts remaining
after the update application step is completed.  The effects might not
be very noticeable to end users, but it will be nice to remove some of
the conflict tracking code.

Finally, it removes the last use PerModelSafeGroupState.  This will let
us delete some unused code and hopefully simplify StatusController.

This patch does not pursue these cleanups as agressively as it could.
The idea here is to keep the complex logic changes in one small CL, and
perform the cleanups in a larger, but simpler, follow-up CL.

BUG=147681, 11280, 156238
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=164286

[rlarocque, 2012-10-18 23:14:50]

I'm fairly confident that the merge itself is safe.  I'm less sure about my
assertion that we can resolve all the simple conflicts with only two update
applicator passes, but I haven't found anything that proves it *isn't* possible.

You might notice that this commit creates a lot of dead code and unused data
structures.  I have a patch to complete the clean up:
http://codereview.chromium.org/11185064/.  Let me know if you'd prefer to review
both patches as one, instead of splitting them up.

Tim: Please review.
Nicolas: Please double-review the logic in apply_updates_command.  Let's make
sure there won't be any surprises in the way the update applicator and conflict
resolver interact.

[Nicolas Zea, 2012-10-23 00:55:46]

Nice!

The logic in apply updates command looks good.

[rlarocque, 2012-10-24 17:08:30]

On 2012/10/23 00:55:46, nzea wrote:
> Nice!
> 
> The logic in apply updates command looks good.

Tim: ping.

[tim (not reviewing), 2012-10-24 20:29:08]

The logic overall looks good, just some nits and a rename suggestion.

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
File sync/engine/apply_updates_command.cc (right):

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
sync/engine/apply_updates_command.cc:83: // Resolve the simple conflicts we just
detected.
In the interest of writing short and simple functions, this if-block seems like
a good candidate for a separate ResolveSimpleConflicts function (this one is at
~100 already).

http://codereview.chromium.org/11192071/diff/1/sync/engine/conflict_resolver.cc
File sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/11192071/diff/1/sync/engine/conflict_resolver....
sync/engine/conflict_resolver.cc:210: // and !paremt_matches cases here are
critical to maintaining that
nit - parent_matches

http://codereview.chromium.org/11192071/diff/1/sync/engine/syncer.cc
File sync/engine/syncer.cc (left):

http://codereview.chromium.org/11192071/diff/1/sync/engine/syncer.cc#oldcode64
sync/engine/syncer.cc:64: ENUM_CASE(RESOLVE_CONFLICTS);
It's great to move this to after applying updates, although as usual I think
hiding primary parts of what makes up a "sync cycle" from this layer makes it
harder to see what's going on (versus having APPLY_UPDATES followed by
RESOLVE_CONFLICTS). I'd prefer we wait to "merge" until we're ready to lay
everything out as "one big method" again (without SyncerStep) so you can clearly
see the major steps involved, because doing that "flattening" on its own is not
a priority and in the meantime I think the code is less readable. There's also
the minor side effect that we can't take advantage of early_exit_requested
between successive commands, (though not a big problem here today as resolve
should be fast in theory).  

But we've discussed this before (with commit), so... I guess you can ignore the
above :) 

That said, I feel most strongly about not redefining what "Processing updates"
and "Applying Updates" mean, (pushing protos into SERVER_ fields, and pushing
SERVER_ fields into local fields (in the happy case)). Renaming
ApplyUpdatesCommand to ApplyUpdatesAndResolveConflictsCommand would mostly
address my concern.

[rlarocque, 2012-10-24 21:21:22]

New patch uploaded.  PTAL.

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
File sync/engine/apply_updates_command.cc (right):

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
sync/engine/apply_updates_command.cc:83: // Resolve the simple conflicts we just
detected.
On 2012/10/24 20:29:08, timsteele wrote:
> In the interest of writing short and simple functions, this if-block seems
like
> a good candidate for a separate ResolveSimpleConflicts function (this one is
at
> ~100 already).

It looks big, but there's very little code in here.

By my count, we have:
- 2 lines to instantiate function-like objects
- 4 lines of actual code
- 3 DCHECKs

(I'm counting lines wrapped because they exceed 80 characters as one line.)

The remainder is comments and whitespace.

http://codereview.chromium.org/11192071/diff/1/sync/engine/conflict_resolver.cc
File sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/11192071/diff/1/sync/engine/conflict_resolver....
sync/engine/conflict_resolver.cc:210: // and !paremt_matches cases here are
critical to maintaining that
On 2012/10/24 20:29:08, timsteele wrote:
> nit - parent_matches

Good catch.  Fixed.

http://codereview.chromium.org/11192071/diff/1/sync/engine/syncer.cc
File sync/engine/syncer.cc (left):

http://codereview.chromium.org/11192071/diff/1/sync/engine/syncer.cc#oldcode64
sync/engine/syncer.cc:64: ENUM_CASE(RESOLVE_CONFLICTS);
On 2012/10/24 20:29:08, timsteele wrote:
> It's great to move this to after applying updates, although as usual I think
> hiding primary parts of what makes up a "sync cycle" from this layer makes it
> harder to see what's going on (versus having APPLY_UPDATES followed by
> RESOLVE_CONFLICTS). I'd prefer we wait to "merge" until we're ready to lay
> everything out as "one big method" again (without SyncerStep) so you can
clearly
> see the major steps involved, because doing that "flattening" on its own is
not
> a priority and in the meantime I think the code is less readable. There's also
> the minor side effect that we can't take advantage of early_exit_requested
> between successive commands, (though not a big problem here today as resolve
> should be fast in theory).  

Although I do think this looks nicer, that's not my only motivation.  I wouldn't
have done this if there weren't real benefits to be had.  The flattening was
necessary to remove PerModelSafeGroupState.  It also makes it easier to perform
the { apply updates; resolve conflicts; re-apply updates } steps all under the
same lock, without which the new logic would be incorrect.  

> 
> But we've discussed this before (with commit), so... I guess you can ignore
the
> above :) 
> 
> That said, I feel most strongly about not redefining what "Processing updates"
> and "Applying Updates" mean, (pushing protos into SERVER_ fields, and pushing
> SERVER_ fields into local fields (in the happy case)). Renaming
> ApplyUpdatesCommand to ApplyUpdatesAndResolveConflictsCommand would mostly
> address my concern. 

That's reasonable.  I'll do the rename.  

Looking towards the future, I would like to eventually make simple conflict
resolution so simple that it can consist of one or two if branch in the update
applicator (or the syncer_util.cc function it defers to).  At that point,
someone unfamiliar with the history of this project might look at the name
ApplyUpdatesAndResolveConflictsCommand and wonder why we're making such a big
deal about conflict resolution.

For now, I agree that ApplyUpdatesAndResolveConflictsCommand is a good name.

[tim (not reviewing), 2012-10-24 22:34:24]

LGTM

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
File sync/engine/apply_updates_command.cc (right):

http://codereview.chromium.org/11192071/diff/1/sync/engine/apply_updates_comm...
sync/engine/apply_updates_command.cc:83: // Resolve the simple conflicts we just
detected.
On 2012/10/24 21:21:22, rlarocque wrote:
> On 2012/10/24 20:29:08, timsteele wrote:
> > In the interest of writing short and simple functions, this if-block seems
> like
> > a good candidate for a separate ResolveSimpleConflicts function (this one is
> at
> > ~100 already).
> 
> It looks big, but there's very little code in here.
> 
> By my count, we have:
> - 2 lines to instantiate function-like objects
> - 4 lines of actual code
> - 3 DCHECKs
> 
> (I'm counting lines wrapped because they exceed 80 characters as one line.)
> 
> The remainder is comments and whitespace.

Fair enough. Note though based on several readability reviews I've seen, I think
the point the style guide makes is that when a function "looks big" you pay a
readability price.

It also seems like a natural break-up if we're going to name the command
ApplyUpdatesAndResolveConflicts.  

I think it's preferable, but won't hold up this review because of it.

[commit-bot: I haz the power, 2012-10-24 22:47:52]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/11192071/11001

[commit-bot: I haz the power, 2012-10-24 22:47:59]

Failed to apply patch for sync/engine/conflict_resolver.cc:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file sync/engine/conflict_resolver.cc
  Hunk #6 FAILED at 271.
  Hunk #7 succeeded at 300 (offset -20 lines).
  1 out of 7 hunks FAILED -- saving rejects to file
sync/engine/conflict_resolver.cc.rej

Patch:       sync/engine/conflict_resolver.cc
Index: sync/engine/conflict_resolver.cc
diff --git a/sync/engine/conflict_resolver.cc b/sync/engine/conflict_resolver.cc
index
eec418ad03ddae893dbd43edffa4eec36b44cc68..fe274ae5e6f0e167e79d8111dca6099094faab19
100644
--- a/sync/engine/conflict_resolver.cc
+++ b/sync/engine/conflict_resolver.cc
@@ -35,11 +35,10 @@ ConflictResolver::ConflictResolver() {
 ConflictResolver::~ConflictResolver() {
 }
 
-ConflictResolver::ProcessSimpleConflictResult
-ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
-                                        const Id& id,
-                                        const Cryptographer* cryptographer,
-                                        StatusController* status) {
+void ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
+                                             const Id& id,
+                                             const Cryptographer*
cryptographer,
+                                             StatusController* status) {
   MutableEntry entry(trans, syncable::GET_BY_ID, id);
   // Must be good as the entry won't have been cleaned up.
   CHECK(entry.good());
@@ -50,7 +49,7 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
       !entry.Get(syncable::IS_UNSYNCED)) {
     // This is very unusual, but it can happen in tests.  We may be able to
     // assert NOTREACHED() here when those tests are updated.
-    return NO_SYNC_PROGRESS;
+    return;
   }
 
   if (entry.Get(syncable::IS_DEL) && entry.Get(syncable::SERVER_IS_DEL)) {
@@ -60,7 +59,7 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
     entry.Put(syncable::IS_UNAPPLIED_UPDATE, false);
     // we've made changes, but they won't help syncing progress.
     // METRIC simple conflict resolved by merge.
-    return NO_SYNC_PROGRESS;
+    return;
   }
 
   // This logic determines "client wins" vs. "server wins" strategy picking.
@@ -206,6 +205,10 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
                                 IGNORE_ENCRYPTION,
                                 CONFLICT_RESOLUTION_SIZE);
     } else if (entry_deleted || !name_matches || !parent_matches) {
+      // NOTE: The update application logic assumes that conflict resolution
+      // will never result in changes to the local hierarchy.  The
entry_deleted
+      // and !parent_matches cases here are critical to maintaining that
+      // assumption.
       OverwriteServerChanges(&entry);
       status->increment_num_server_overwrites();
       DVLOG(1) << "Resolving simple conflict, overwriting server changes "
@@ -225,22 +228,16 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
     // 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 it should be a hierarchy
-    // conflict.  Hierarchy conflicts should not be processed by this function.
-    // We could end up here if a change was made since we last tried to detect
-    // conflicts, which was during update application.
     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, "
-                 << "should be a hierarchy conflict. (race condition).";
-        return NO_SYNC_PROGRESS;
-      }
+      // If a server deleted folder has local contents it should be a hierarchy
+      // conflict.  Hierarchy conflicts should not be processed by this
+      // function.
+      DCHECK(children.empty());
     }
 
     // The entry is deleted on the server but still exists locally.
@@ -274,16 +271,14 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
                                 UNDELETE,
                                 CONFLICT_RESOLUTION_SIZE);
     }
-    return SYNC_PROGRESS;
   }
 }
 
-bool ConflictResolver::ResolveConflicts(
+void ConflictResolver::ResolveConflicts(
     syncable::WriteTransaction* trans,
     const Cryptographer* cryptographer,
     const std::set<syncable::Id>& simple_conflict_ids,
     sessions::StatusController* status) {
-  bool forward_progress = false;
   // Iterate over simple conflict items.
   set<Id>::const_iterator conflicting_item_it;
   set<Id> processed_items;
@@ -323,17 +318,11 @@ bool ConflictResolver::ResolveConflicts(
     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;
-      }
+      ProcessSimpleConflict(trans, id, cryptographer, status);
       processed_items.insert(id);
     }
   }
-  return forward_progress;
+  return;
 }
 
 }  // namespace syncer

[commit-bot: I haz the power, 2012-10-25 20:22:49]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/11192071/14001

[commit-bot: I haz the power, 2012-10-25 20:22:57]

Failed to apply patch for sync/engine/conflict_resolver.cc:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file sync/engine/conflict_resolver.cc
  Hunk #4 FAILED at 205.
  1 out of 7 hunks FAILED -- saving rejects to file
sync/engine/conflict_resolver.cc.rej

Patch:       sync/engine/conflict_resolver.cc
Index: sync/engine/conflict_resolver.cc
diff --git a/sync/engine/conflict_resolver.cc b/sync/engine/conflict_resolver.cc
index
c6806bef3f0c3a358a925b7bf777133364eedac1..0f1a4851beac93befa348dec6418b08fceb1df2f
100644
--- a/sync/engine/conflict_resolver.cc
+++ b/sync/engine/conflict_resolver.cc
@@ -35,11 +35,10 @@ ConflictResolver::ConflictResolver() {
 ConflictResolver::~ConflictResolver() {
 }
 
-ConflictResolver::ProcessSimpleConflictResult
-ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
-                                        const Id& id,
-                                        const Cryptographer* cryptographer,
-                                        StatusController* status) {
+void ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans,
+                                             const Id& id,
+                                             const Cryptographer*
cryptographer,
+                                             StatusController* status) {
   MutableEntry entry(trans, syncable::GET_BY_ID, id);
   // Must be good as the entry won't have been cleaned up.
   CHECK(entry.good());
@@ -50,7 +49,7 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
       !entry.Get(syncable::IS_UNSYNCED)) {
     // This is very unusual, but it can happen in tests.  We may be able to
     // assert NOTREACHED() here when those tests are updated.
-    return NO_SYNC_PROGRESS;
+    return;
   }
 
   if (entry.Get(syncable::IS_DEL) && entry.Get(syncable::SERVER_IS_DEL)) {
@@ -60,7 +59,7 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
     entry.Put(syncable::IS_UNAPPLIED_UPDATE, false);
     // we've made changes, but they won't help syncing progress.
     // METRIC simple conflict resolved by merge.
-    return NO_SYNC_PROGRESS;
+    return;
   }
 
   // This logic determines "client wins" vs. "server wins" strategy picking.
@@ -206,6 +205,10 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
                                 IGNORE_ENCRYPTION,
                                 CONFLICT_RESOLUTION_SIZE);
     } else if (entry_deleted || !name_matches || !parent_matches) {
+      // NOTE: The update application logic assumes that conflict resolution
+      // will never result in changes to the local hierarchy.  The
entry_deleted
+      // and !parent_matches cases here are critical to maintaining that
+      // assumption.
       OverwriteServerChanges(&entry);
       status->increment_num_server_overwrites();
       DVLOG(1) << "Resolving simple conflict, overwriting server changes "
@@ -225,22 +228,16 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
     // 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 it should be a hierarchy
-    // conflict.  Hierarchy conflicts should not be processed by this function.
-    // We could end up here if a change was made since we last tried to detect
-    // conflicts, which was during update application.
     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, "
-                 << "should be a hierarchy conflict. (race condition).";
-        return NO_SYNC_PROGRESS;
-      }
+      // If a server deleted folder has local contents it should be a hierarchy
+      // conflict.  Hierarchy conflicts should not be processed by this
+      // function.
+      DCHECK(children.empty());
     }
 
     // The entry is deleted on the server but still exists locally.
@@ -253,17 +250,14 @@ ConflictResolver::ProcessSimpleConflict(WriteTransaction*
trans,
     UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict",
                               UNDELETE,
                               CONFLICT_RESOLUTION_SIZE);
-
-    return SYNC_PROGRESS;
   }
 }
 
-bool ConflictResolver::ResolveConflicts(
+void ConflictResolver::ResolveConflicts(
     syncable::WriteTransaction* trans,
     const Cryptographer* cryptographer,
     const std::set<syncable::Id>& simple_conflict_ids,
     sessions::StatusController* status) {
-  bool forward_progress = false;
   // Iterate over simple conflict items.
   set<Id>::const_iterator conflicting_item_it;
   set<Id> processed_items;
@@ -303,17 +297,11 @@ bool ConflictResolver::ResolveConflicts(
     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;
-      }
+      ProcessSimpleConflict(trans, id, cryptographer, status);
       processed_items.insert(id);
     }
   }
-  return forward_progress;
+  return;
 }
 
 }  // namespace syncer

[commit-bot: I haz the power, 2012-10-25 21:47:35]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/11192071/12003

[commit-bot: I haz the power, 2012-10-26 01:05:55]

Retried try job too often for step(s) interactive_ui_tests

[commit-bot: I haz the power, 2012-10-26 01:21:36]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/11192071/12003

[commit-bot: I haz the power, 2012-10-26 07:53:19]

Change committed as 164286