Use external ID to match native model nodes during bookmark association.

Use external ID to match native model nodes during bookmark association.

The fix improves matching of nodes in BookmarkModelAssociator in
situations where there are multiple bookmarks or folders with the
same titles or URLs.
This will address one particular scenario leading to bookmark
duplication (see crbug.com/118105).

1) In BookmarkModelAssociator::BuildAssociations, when there are
multiple native model nodes with matching title / URL, a secondary
match on external ID is used to pick a preferred one; otherwise
the first matching node is returned.
The preferred match on external ID should be applicable in most
situations except when the native model has been rebuilt from scratch.
Picking a wrong folder during the association process results in
duplicating the entire subtree within the wrong folder. This issue
should be addressed now.
2) In BookmarkModelAssociator::ApplyDeletesFromSyncJournal the external
ID match is now the primary criteria for selecting a native model
node to be deleted. The previous implementation would pick an arbitrary
native model node based on just the title / URL match anywhere in the
node hierarchy. That would happen every time after deleting a bookmark
or folder and recreating it in another place.
Since external IDs might be reused, there is a secondary match on
title and URL to ensure that the right node gets deleted. To avoid
costly O(N*M) algorithm (where N is number of bookmarks and M is
number of entries in delete journal), the implementation uses a set
of external IDs to reduce the cost to O(N*logM).

BUG=456228
Committed: https://crrev.com/89fce43a19e7f8b0225a0d750ec3eb3cb0939e3d
Cr-Commit-Position: refs/heads/master@{#315401}

[stanisc, 2015-02-06 22:19:27]

Patchset #1 (id:1) has been deleted

[stanisc, 2015-02-06 22:30:26]

stanisc@chromium.org changed reviewers:
+ zea@chromium.org

[stanisc, 2015-02-06 22:30:27]

PTAL.

[Nicolas Zea, 2015-02-06 23:34:19]

Nice. Couple comments.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
File chrome/browser/sync/glue/bookmark_model_associator.cc (right):

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:80: // If there are
multiple matches than a node with ID matching |preferred_id|
nit: "than" -> "then"?

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:170: if (match == nullptr)
{
nit: else if?

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:189: const std::string&
title,
nit: to make it clear why we're converting to a sync internal format, I think it
might be clearer to name these sync_url, sync_title, sync_is_folder.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:196:
ConvertTitleToSyncInternalFormat(bookmark_title, &bookmark_title);
I notice the previous version didn't call this, and instead skipped the
SyncAPINameToServerName call. Will than make a difference?

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:519: // bookmark nodes are
created as sync nodes.
Was this something you wanted to do in this patch or a later patch? If a later,
file a bug for it?

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:645: std::set<int64>
external_ids;
Maybe name this journaled_external_ids to make it a bit clearer?

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:647: if
(bk_delete_journals[i].external_id != 0) {
nit: looks like most of this file is doing single line conditional bodies
without curly braces. Prefer keeping to that style.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
File chrome/browser/sync/profile_sync_service_bookmark_unittest.cc (right):

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:808:
TEST_F(ProfileSyncServiceBookmarkTest,
nit: Could you add comments to these tests describing what they're testing?
(this wasn't enforced well previously, but it's a good habit to have)

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:857: // The
bookmark mode should be deleted.
nit: mode -> node

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:866: const int
kNumFolders = 10;
Comment describing what the expected directory structure is like? (i.e. 10
bookmark folders, with the 7th containing 10 url bookmarks...etc.

[stanisc, 2015-02-09 19:15:38]

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
File chrome/browser/sync/glue/bookmark_model_associator.cc (right):

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:80: // If there are
multiple matches than a node with ID matching |preferred_id|
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: "than" -> "then"?

Done.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:170: if (match == nullptr)
{
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: else if?

Done.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:189: const std::string&
title,
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: to make it clear why we're converting to a sync internal format, I think
it
> might be clearer to name these sync_url, sync_title, sync_is_folder.

See below. Adding a comment to explain that this has to do comparison equivalent
to the one used by BookmarkNodeFinder::FindBookmarkNode.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:196:
ConvertTitleToSyncInternalFormat(bookmark_title, &bookmark_title);
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> I notice the previous version didn't call this, and instead skipped the
> SyncAPINameToServerName call. Will than make a difference?

The previous version of the function (BookmarkModelAssociator::NodesMatch) in
fact was not used anywhere. The previous implementation of the algorithm used
BookmarkNodeFinder::FindBookmarkNode that does exactly the same conversion.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:519: // bookmark nodes are
created as sync nodes.
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> Was this something you wanted to do in this patch or a later patch? If a
later,
> file a bug for it?

Not in this patch. The whole BookmarkModelAssociator needs to be revisited to
handle offline mutations better using an approach similar to the one suggested
in your document.
I'll file a separate bug to address that.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:645: std::set<int64>
external_ids;
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> Maybe name this journaled_external_ids to make it a bit clearer?

Done.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:647: if
(bk_delete_journals[i].external_id != 0) {
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: looks like most of this file is doing single line conditional bodies
> without curly braces. Prefer keeping to that style.

OK, done. But I think we should use curly braces always, even when there is a
single line.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
File chrome/browser/sync/profile_sync_service_bookmark_unittest.cc (right):

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:808:
TEST_F(ProfileSyncServiceBookmarkTest,
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: Could you add comments to these tests describing what they're testing?
> (this wasn't enforced well previously, but it's a good habit to have)

Done.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:857: // The
bookmark mode should be deleted.
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> nit: mode -> node

Done.

https://codereview.chromium.org/904083002/diff/20001/chrome/browser/sync/prof...
chrome/browser/sync/profile_sync_service_bookmark_unittest.cc:866: const int
kNumFolders = 10;
On 2015/02/06 23:34:19, Nicolas Zea wrote:
> Comment describing what the expected directory structure is like? (i.e. 10
> bookmark folders, with the 7th containing 10 url bookmarks...etc.

Done.

[Nicolas Zea, 2015-02-09 20:39:36]

LGTM

[stanisc, 2015-02-09 21:48:29]

The CQ bit was checked by stanisc@chromium.org

[commit-bot: I haz the power, 2015-02-09 21:49:54]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/904083002/40001

[commit-bot: I haz the power, 2015-02-09 21:54:47]

Committed patchset #2 (id:40001)

[commit-bot: I haz the power, 2015-02-09 21:55:15]

Patchset 2 (id:??) landed as
https://crrev.com/89fce43a19e7f8b0225a0d750ec3eb3cb0939e3d
Cr-Commit-Position: refs/heads/master@{#315401}

[Ryan Hamilton, 2015-02-10 00:05:31]

A revert of this CL (patchset #2 id:40001) has been created in
https://codereview.chromium.org/906403003/ by rch@chromium.org.

The reason for reverting is: Looks like it broke a sync_unittest

http://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20%28dbg%29%28...

(But maybe it's a flake?).