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

This is a resubmit of https://codereview.chromium.org/904083002
which was reverted due to an unrelated flaky test. There are no
changes compared to the original patch, hence skipping the code
review (zea@ was the original reviewer).

Original patch description:

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
TBR=zea@chromium.org

Review URL: https://codereview.chromium.org/912693002

Cr-Commit-Position: refs/heads/master@{#317688}

2 files changed, 3 insertions, 0 deletions

diff --git a/sync/internal_api/delete_journal.cc b/sync/internal_api/delete_journal.cc
index ebeb5a7..edd10ae 100644
--- a/sync/internal_api/delete_journal.cc
+++ b/sync/internal_api/delete_journal.cc
@@ -21,6 +21,8 @@ void DeleteJournal::GetBookmarkDeleteJournals(
       deleted_entries.begin(); i != deleted_entries.end(); ++i) {
     delete_journal_list->push_back(BookmarkDeleteJournal());
     delete_journal_list->back().id = (*i)->ref(syncer::syncable::META_HANDLE);
+    delete_journal_list->back().external_id =
+        (*i)->ref(syncer::syncable::LOCAL_EXTERNAL_ID);
     delete_journal_list->back().is_folder = (*i)->ref(syncer::syncable::IS_DIR);
 
     const sync_pb::EntitySpecifics& specifics = (*i)->ref(
diff --git a/sync/internal_api/public/delete_journal.h b/sync/internal_api/public/delete_journal.h
index 3152b02..ecf84fe 100644
--- a/sync/internal_api/public/delete_journal.h
+++ b/sync/internal_api/public/delete_journal.h
@@ -17,6 +17,7 @@ class BaseTransaction;
 
 struct BookmarkDeleteJournal {
   int64 id;   // Metahandle of delete journal entry.
+  int64 external_id;  // Bookmark ID in the native model.
   bool is_folder;
   sync_pb::EntitySpecifics specifics;
 };