Sync: Optimistic bookmark association implementation

This patch introduces the logic for preventing bookmark duplication
during the optimistic bookmark association. The optimistic bookmark
duplication is used when the local model is supposed to be in
sync with the stored synced data in the pre-association transaction
version check. The optimistic algorithm is currently behind the
SyncOptimisticBookmarkAssociation Finch Experiment switch.

Here is what the algorithm does so far:

1) In the beginning of the association process build an index of all
native bookmark nodes by ID.

2) Then it traverses the Sync hierarchy just like the regular algorithm
does and tries to find a match for each sync node by title and URL
just like the regular algorithm does.

3) If the match isn't found the optimistic algorithm looks in the index
for a bookmark match by "external ID" stored in the sync node.
If there is a match, that means the corresponding bookmark node
has been moved to another folder or renamed. In that case the local
state is considered to be the "true" one and the sync node gets deleted.

4) The matching bookmark node in another folder is then propagated
to Sync as a new node. At the end we end up having just one copy in
the new place that corresponds to the local hierarchy.

I added code for updating the transaction version for all "touched"
bookmark nodes in the main body of both optimistic and non-optimistic
algorithm. I realized that the current optimization hasn't been
consistently doing that. The next iteration of the algorithm will rely
on transaction versions of individual nodes, so we need to fix that.

Known issues that might be addressed in the next iteration:

1) Since the new algorithm applies to the optimistic case only it would
cover only about 10-15% of bookmark duplications. If the algorithm
works well we should be able to extend it to the non-optimistic case.

2) The condition described above is handled as a combination
of delete and add rather than a single move. That isn't optimal
when handling a folder with a large hierarchy because the
current
implementation will have to delete and re-add each node in the folder
vs. changing just the parent/position for the folder itself.
We might try to improve that in the next iteration.

3) Node re-position within the same parent is still not handled.

4) Deleting a node with its children in the old location results
in putting all nodes to the delete journal. Playing back the journal
would remove these nodes in their new location because the new nodes
are identical including the matching external ID.
To prevent that I had to reset external ID before tombstoning nodes,
but a better solution would be to not put nodes in delete journal
for client initiated deletes.

5) It would be better to build the node index on demand. We'll change
that in the next iteration of the algorithm if there is an impact
on performance.

BUG=456876

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

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

2 files changed, 8 insertions, 0 deletions

diff --git a/sync/internal_api/public/read_node.h b/sync/internal_api/public/read_node.h
index 5749f9c..69c3114 100644
--- a/sync/internal_api/public/read_node.h
+++ b/sync/internal_api/public/read_node.h
@@ -48,6 +48,10 @@ class SYNC_EXPORT ReadNode : public BaseNode {
   // nodes, which should be looked up with InitTypeRoot().
   InitByLookupResult InitByTagLookupForBookmarks(const std::string& tag);
 
+  // Returns transaction version of the last transaction where this node has
+  // been modified.
+  int64 GetTransactionVersion() const;
+
   // Implementation of BaseNode's abstract virtual accessors.
   const syncable::Entry* GetEntry() const override;
   const BaseTransaction* GetTransaction() const override;
diff --git a/sync/internal_api/read_node.cc b/sync/internal_api/read_node.cc
index c162800..15dffc8 100644
--- a/sync/internal_api/read_node.cc
+++ b/sync/internal_api/read_node.cc
@@ -77,6 +77,10 @@ const BaseTransaction* ReadNode::GetTransaction() const {
   return transaction_;
 }
 
+int64 ReadNode::GetTransactionVersion() const {
+  return GetEntry()->GetTransactionVersion();
+}
+
 BaseNode::InitByLookupResult ReadNode::InitByTagLookupForBookmarks(
     const std::string& tag) {
   DCHECK(!entry_) << "Init called twice";