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

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

We now only consider an item committable if it and all it's immediate predecessors
 are not in conflict, and if it has a valid parent. This finishes the work
to prevent conflicting entries from committing and allows us to preserve
positional changes when in conflict.

BUG=82236
TEST=

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=120629

[Nicolas Zea, 2011-12-14 01:15:32]

PTAL. Diffed off http://codereview.chromium.org/8770032/, which is itself diffed
off http://codereview.chromium.org/8917031/

[akalin, 2011-12-14 03:39:52]

Just a few nits.  Still reading through the CL, don't quite get it yet...

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
File chrome/browser/sync/engine/get_commit_ids_command.cc (right):

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
chrome/browser/sync/engine/get_commit_ids_command.cc:158: // Either the
parent/it's predecessor's are not ready for commit, in which
it's -> its
predecessor's -> predecessors

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
File chrome/browser/sync/engine/get_commit_ids_command.h (right):

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
chrome/browser/sync/engine/get_commit_ids_command.h:153: // Appends all unsynced
predecessors of |item|, followed by |item| iteself,
iteself -> itself

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
chrome/browser/sync/engine/get_commit_ids_command.h:156: // are unready for
commit, does not modify |ordered_commit_set_|.
unready -> not ready

[akalin, 2011-12-15 01:58:20]

Took a detailed look, just one question

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
File chrome/browser/sync/engine/get_commit_ids_command.h (right):

http://codereview.chromium.org/8922015/diff/6001/chrome/browser/sync/engine/g...
chrome/browser/sync/engine/get_commit_ids_command.h:135: // returns false. If
item was not ready for commit, clears |result| and
Is there a reason for the 'clear results' action on false?  It seems like the
caller of this function eventually discards the OrderedCommitSet anyway.

[Nicolas Zea, 2011-12-30 00:02:28]

-Fred (out of town), +Nick. Mind taking a look and ensuring the logic matches
the server's expectations? There's no functional difference other than we
attempt to commit less, and have more intelligent conflict resolution. I've
tested against cosmo and things are looking good.

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

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:150: (server_prev_id ==
entry.Get(syncable::PREV_ID));
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.

[rlarocque, 2012-01-10 23:39:50]

ncarter asked me to take a look at this while he was on vacation.

I have only looked at the first few files.  I have some serious concerns about
the approach used to detect position changes, so I see no point in reading
further at this time.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:147: syncable::Id server_prev_id
= entry.ComputePrevIdFromServerPosition(
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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:148:
entry.Get(syncable::SERVER_PARENT_ID));
SERVER_PARENT_ID?  Did you mean SERVER_PREV_ID?

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:255: } else if (entry_deleted ||
!name_matches || !parent_matches) {
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.)

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:263: } else {
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]

Please take another look. Functionally nothing has changed, but I have added
substantial comments about why this is correct. Please let me no if it's not
clear or you disagree. In addition, I added a deliberately racy integration test
to ensure correctness.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:147: syncable::Id server_prev_id
= entry.ComputePrevIdFromServerPosition(
On 2012/01/10 23:39:51, rlarocque wrote:
> 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.

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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:148:
entry.Get(syncable::SERVER_PARENT_ID));
On 2012/01/10 23:39:51, rlarocque wrote:
> SERVER_PARENT_ID?  Did you mean SERVER_PREV_ID?

No, you pass the parent to ComputePrevIdFromServerPosition.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:150: (server_prev_id ==
entry.Get(syncable::PREV_ID));
On 2012/01/04 21:37:59, ncarter wrote:
> 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.

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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:255: } else if (entry_deleted ||
!name_matches || !parent_matches) {
On 2012/01/10 23:39:51, rlarocque wrote:
> 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.)

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).

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:263: } else {
On 2012/01/10 23:39:51, rlarocque wrote:
> 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?

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]

I will keep reading, but I'm taking a break for now.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:147: syncable::Id server_prev_id
= entry.ComputePrevIdFromServerPosition(
On 2012/01/18 02:54:39, nzea wrote:
> On 2012/01/10 23:39:51, rlarocque wrote:
> > 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.
> 
> 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.

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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:263: } else {
On 2012/01/18 02:54:39, nzea wrote:
> On 2012/01/10 23:39:51, rlarocque wrote:
> > 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?
> 
> 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)

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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:344: // We have a simple
conflict. In order check if positions have changed,
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]

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/conflict_resolver.cc (right):

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:147: syncable::Id server_prev_id
= entry.ComputePrevIdFromServerPosition(
On 2012/01/18 20:21:55, rlarocque wrote:
> On 2012/01/18 02:54:39, nzea wrote:
> > On 2012/01/10 23:39:51, rlarocque wrote:
> > > 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.
> > 
> > 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.
> 
> 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.

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?

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:263: } else {
On 2012/01/18 20:21:55, rlarocque wrote:
> On 2012/01/18 02:54:39, nzea wrote:
> > On 2012/01/10 23:39:51, rlarocque wrote:
> > > 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?
> > 
> > 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)
> 
> 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.

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.

http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
chrome/browser/sync/engine/conflict_resolver.cc:344: // We have a simple
conflict. In order check if positions have changed,
On 2012/01/18 20:21:55, rlarocque wrote:
> 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?

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..

[rlarocque, 2012-01-20 02:08:49]

Thanks, that makes thing much clearer.  I had missed the fact that there was a
case that unset both flags.  Now it makes a lot more sense.

I've added some responses inline, and I've got another set of drafts to edit and
post later tonight.

On 2012/01/18 20:40:42, nzea wrote:
>
http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
> File chrome/browser/sync/engine/conflict_resolver.cc (right):
> 
>
http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
> chrome/browser/sync/engine/conflict_resolver.cc:147: syncable::Id
server_prev_id
> = entry.ComputePrevIdFromServerPosition(
> On 2012/01/18 20:21:55, rlarocque wrote:
> > On 2012/01/18 02:54:39, nzea wrote:
> > > On 2012/01/10 23:39:51, rlarocque wrote:
> > > > 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.
> > > 
> > > 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.
> > 
> > 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.
> 
> 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?
> 

Yes.  I'm still a bit suspicious about this because I can't remember how
SERVER_POSITION_IN_PARENT is derived, but it certainly makes a lot more sense
now.  I'm willing to assume it's correct.

>
http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
> chrome/browser/sync/engine/conflict_resolver.cc:263: } else {
> On 2012/01/18 20:21:55, rlarocque wrote:
> > On 2012/01/18 02:54:39, nzea wrote:
> > > On 2012/01/10 23:39:51, rlarocque wrote:
> > > > 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?
> > > 
> > > 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)
> > 
> > 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.
> 
> 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.
> 

OK.  I'm not sure I like the fact that we toggle between the "ignore all
changes" and "server wins" options based on a flag that's expected to be a bit
flaky, but I suppose there's not much we can do about it until we get better at
comparing positions.

>
http://codereview.chromium.org/8922015/diff/18015/chrome/browser/sync/engine/...
> chrome/browser/sync/engine/conflict_resolver.cc:344: // We have a simple
> conflict. In order check if positions have changed,
> On 2012/01/18 20:21:55, rlarocque wrote:
> > 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?
> 
> 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..

Yep, makes sense.  I missed the fact that there was a case that unset *both*
flags.

[rlarocque, 2012-01-20 06:26:51]

That's all for now.

Sorry this took so long.  I'm having some trouble grasping the big picture.  I
think I missed the whiteboard session that explained all this.  It would be a
good idea to wait until ncarter gets back so he can give this code a proper
review.

The one bit that does concern me is how this code will interact with conflict
sets.  I'm not sure this system will work if there are unresolvable conflicts
present.  We should talk about that.  (And possibly other parts of this, too. 
I'm curious as to how this all works and would like to learn the overall design,
if you have the time.)

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/get_commit_ids_command.cc (right):

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:133: if
(entry.Get(syncable::IS_DEL) && !entry.Get(syncable::ID).ServerKnows()) {
I worry about this.  I think there's an unlikely race where we could commit to
the server, but lose power or crash before we persist that information.  (I'm
not sure this is possible, but, from what I know of the directory code, it
sounds plausible.)

If that did happen, then I suppose we would re-download the item from the server
and treat it as if it were new, so maybe there's no harm...

I suppose what I'm trying to say here that I'm not 100% convinced that this is
safe.  Unless you're sure that it is, or you think that the benefits of it are
worth the risk, I'd prefer to not make this change as part of this commit.

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:140: // Extra validity
checks.
Why do these checks here?

UPDATE: I see now that this code has been moved here from the iterator.  That's
a good move, and I understand why you would be reluctant to delete them.

I still think these checks are a bit arbitrary, though.  Why not verify these
assertions elsewhere?  Or *everywhere*, with the help of CheckTreeInvariants? 
(questions are rhetorical).

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:170: if
(entry.Get(syncable::IS_UNSYNCED) &&
I prefer the DCHECK in IsEntryReadyForCommit() to silently ignoring !IS_UNSYNCED
entries in this list here.  Under what circumstances could we have !IS_UNSYNCED
items in this list, short of a logic error?

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:316: // We only commit an
item + its dependencies if it and all its
This could interact badly with conflict set processing on Cosmo.  Because we
never resolve conflict sets, it's possible that an entry could be both unsynced
and unapplied (aka. in conflict) indefinitely.  I worry that an unresolved
conflict set conflict could prevent us from committing changes to its successors
and children.  (Actually, children are unlikely to be a problem, but affecting
successors is probably bad.)

On Zipit, conflict sets will be resolved server side so this won't be a problem.

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/get_commit_ids_command.h (right):

http://codereview.chromium.org/8922015/diff/34001/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.h:60: //    False: if a
dependent item was in conflict, and hence no child cannot be
grammar nit: double negative.

[Nicolas Zea, 2012-02-02 23:59:09]

Okay, I cut out some of the code I changed, including the deletion logic changes
and checking that the immediate parent is not in conflict.

In addition, I 100% of new users now have bookmarks on the new backend, and
existing users and being migrated currently (since beginning of week). Since
this affects positioning of new bookmarks while missing a passphrase, I'd like
to get this in and merged for m18.

[rlarocque, 2012-02-04 01:00:45]

Looks good.  Probably better than the old logic.  

I have a few minor comments.  LGTM once they're addressed.

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/get_commit_ids_command.cc (left):

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:161: break;  // Parent was
already present in the set.
Interesting.  That comment doesn't agree with the logic in
AddItemThenPredecessors().

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/get_commit_ids_command.cc (right):

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:51: // We filter out all
unready entries from the set of unsynced handles to
FYI: This comment is no longer valid.  We no longer perform another sync based
on the number of unsynced handles; see crbug.com/94670.  It also doesn't mention
that we do this to filter out throttled types.

I don't think that affects your change.  But since you're touching this comment
anyway, you might want to update it.

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:119:
syncable::EntryNeedsEncryption(encrypted_types, entry))) {
I don't understand why EntryNeedsEncryption() always returns false for
PASSWORDS.  Does that make sense in this context?  Why?

[Nicolas Zea, 2012-02-06 17:29:56]

Committing once trybots go green

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
File chrome/browser/sync/engine/get_commit_ids_command.cc (right):

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:51: // We filter out all
unready entries from the set of unsynced handles to
On 2012/02/04 01:00:45, rlarocque wrote:
> FYI: This comment is no longer valid.  We no longer perform another sync based
> on the number of unsynced handles; see crbug.com/94670.  It also doesn't
mention
> that we do this to filter out throttled types.
> 
> I don't think that affects your change.  But since you're touching this
comment
> anyway, you might want to update it.

Done.

http://codereview.chromium.org/8922015/diff/56002/chrome/browser/sync/engine/...
chrome/browser/sync/engine/get_commit_ids_command.cc:119:
syncable::EntryNeedsEncryption(encrypted_types, entry))) {
On 2012/02/04 01:00:45, rlarocque wrote:
> I don't understand why EntryNeedsEncryption() always returns false for
> PASSWORDS.  Does that make sense in this context?  Why?

Passwords are always _already_ encrypted. The specifics don't support not
encrypting them. Therefore, we no they don't need encryption.

Note that this method is _entry_ needs encryption, not type. In other words,
it's denoting that the entry is not fully encrypted but needs to be. This will
never be true for passwords or nigori.

[commit-bot: I haz the power, 2012-02-06 19:10:07]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/zea@chromium.org/8922015/61001

[commit-bot: I haz the power, 2012-02-06 22:08:50]

Change committed as 120629