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

chrome/browser/sync/glue/bookmark_model_associator.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/sync/glue/bookmark_model_associator.h"
 
 #include <stack>
 
 #include "base/bind.h"
 #include "base/command_line.h"
@@ skipping 58 matching lines @@
 const int kTitleLimitBytes = 255;
 
 // Provides the following abstraction: given a parent bookmark node, find best
 // matching child node for many sync nodes.
 class BookmarkNodeFinder {
  public:
   // Creates an instance with the given parent bookmark node.
   explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
 
   // Finds the bookmark node that matches the given url, title and folder
-  // attribute. Returns the matching node if one exists; NULL otherwise. If a
-  // matching node is found, it's removed for further matches.
+  // attribute. Returns the matching node if one exists; NULL otherwise.
+  // If there are multiple matches than a node with ID matching |preferred_id|

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

nit: "than" -> "then"?

[stanisc, 2015/02/09 19:15:37]

Done.

+  // is returned; otherwise the first matching node is returned.
+  // If a matching node is found, it's removed for further matches.
   const BookmarkNode* FindBookmarkNode(const GURL& url,
                                        const std::string& title,
-                                       bool is_folder);
+                                       bool is_folder,
+                                       int64 preferred_id);
+
+  // Returns true if |bookmark_node| matches the specified |url|,
+  // |title|, and |is_folder| flags.
+  static bool NodeMatches(const BookmarkNode* bookmark_node,
+                          const GURL& url,
+                          const std::string& title,
+                          bool is_folder);
 
  private:
   // Maps bookmark node titles to instances, duplicates allowed.
   // Titles are converted to the sync internal format before
   // being used as keys for the map.
   typedef base::hash_multimap<std::string,
                               const BookmarkNode*> BookmarkNodeMap;
   typedef std::pair<BookmarkNodeMap::iterator,
                     BookmarkNodeMap::iterator> BookmarkNodeRange;
 
   // Converts and truncates bookmark titles in the form sync does internally
   // to avoid mismatches due to sync munging titles.
-  void ConvertTitleToSyncInternalFormat(
-      const std::string& input, std::string* output);
+  static void ConvertTitleToSyncInternalFormat(const std::string& input,
+                                               std::string* output);
 
   const BookmarkNode* parent_node_;
   BookmarkNodeMap child_nodes_;
 
   DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
 };
 
 class ScopedAssociationUpdater {
  public:
   explicit ScopedAssociationUpdater(BookmarkModel* model) {
@@ skipping 17 matching lines @@
     const BookmarkNode* child_node = parent_node_->GetChild(i);
 
     std::string title = base::UTF16ToUTF8(child_node->GetTitle());
     ConvertTitleToSyncInternalFormat(title, &title);
 
     child_nodes_.insert(std::make_pair(title, child_node));
   }
 }
 
 const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
-    const GURL& url, const std::string& title, bool is_folder) {
+    const GURL& url,
+    const std::string& title,
+    bool is_folder,
+    int64 preferred_id) {
+  const BookmarkNode* match = nullptr;
+
   // First lookup a range of bookmarks with the same title.
   std::string adjusted_title;
   ConvertTitleToSyncInternalFormat(title, &adjusted_title);
   BookmarkNodeRange range = child_nodes_.equal_range(adjusted_title);
+  BookmarkNodeMap::iterator match_iter = range.second;
   for (BookmarkNodeMap::iterator iter = range.first;
        iter != range.second;
        ++iter) {
-
     // Then within the range match the node by the folder bit
     // and the url.
     const BookmarkNode* node = iter->second;
     if (is_folder == node->is_folder() && url == node->url()) {
-      // Remove the matched node so we don't match with it again.
-      child_nodes_.erase(iter);
-      return node;
+      if (node->id() == preferred_id || preferred_id == 0) {
+        // Preferred match - use this node.
+        match = node;
+        match_iter = iter;
+        break;
+      }
+
+      if (match == nullptr) {

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

nit: else if?

[stanisc, 2015/02/09 19:15:37]

Done.

+        // First match - continue iterating.
+        match = node;
+        match_iter = iter;
+      }
     }
   }
 
-  return NULL;
+  if (match_iter != range.second) {
+    // Remove the matched node so we don't match with it again.
+    child_nodes_.erase(match_iter);
+  }
+
+  return match;
 }
 
+/* static */
+bool BookmarkNodeFinder::NodeMatches(const BookmarkNode* bookmark_node,
+                                     const GURL& url,
+                                     const std::string& title,

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

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.

[stanisc, 2015/02/09 19:15:37]

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

+                                     bool is_folder) {
+  if (url != bookmark_node->url() || is_folder != bookmark_node->is_folder()) {
+    return false;
+  }
+
+  std::string bookmark_title = base::UTF16ToUTF8(bookmark_node->GetTitle());
+  ConvertTitleToSyncInternalFormat(bookmark_title, &bookmark_title);

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

I notice the previous version didn't call this, and instead skipped the
SyncAPINameToServerName call. Will than make a difference?

[stanisc, 2015/02/09 19:15:37]

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.

+  return title == bookmark_title;
+}
+
+/* static */
 void BookmarkNodeFinder::ConvertTitleToSyncInternalFormat(
     const std::string& input, std::string* output) {
   syncer::SyncAPINameToServerName(input, output);
   base::TruncateUTF8ToByteSize(*output, kTitleLimitBytes, output);
 }
 
 // Helper class to build an index of bookmark nodes by their IDs.
 class BookmarkNodeIdIndex {
  public:
   BookmarkNodeIdIndex() { }
@@ skipping 172 matching lines @@
   }
 
   // Sync model has user created nodes if any of the permanent nodes has
   // children.
   *has_nodes = bookmark_bar_node.HasChildren() ||
       other_bookmarks_node.HasChildren() ||
       (has_mobile_folder && mobile_bookmarks_node.HasChildren());
   return true;
 }
 
-bool BookmarkModelAssociator::NodesMatch(
-    const BookmarkNode* bookmark,
-    const syncer::BaseNode* sync_node) const {
-  std::string truncated_title = base::UTF16ToUTF8(bookmark->GetTitle());
-  base::TruncateUTF8ToByteSize(truncated_title,
-                               kTitleLimitBytes,
-                               &truncated_title);
-  if (truncated_title != sync_node->GetTitle())
-    return false;
-  if (bookmark->is_folder() != sync_node->GetIsFolder())
-    return false;
-  if (bookmark->is_url()) {
-    if (bookmark->url() != GURL(sync_node->GetBookmarkSpecifics().url()))
-      return false;
-  }
-  // Don't compare favicons here, because they are not really
-  // user-updated and we don't have versioning information -- a site changing
-  // its favicon shouldn't result in a bookmark mismatch.
-  return true;
-}
-
 bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
     const BookmarkNode* permanent_node, const std::string&tag) {
   // Do nothing if |permanent_node| is already initialized and associated.
   int64 sync_id = GetSyncIdFromChromeId(permanent_node->id());
   if (sync_id != syncer::kInvalidId)
     return true;
   if (!GetSyncIdForTaggedNode(tag, &sync_id))
     return false;
 
   Associate(permanent_node, sync_id);
@@ skipping 37 matching lines @@
   // Match up the roots and recursively do the following:
   // * For each sync node for the current sync parent node, find the best
   //   matching bookmark node under the corresponding bookmark parent node.
   //   If no matching node is found, create a new bookmark node in the same
   //   position as the corresponding sync node.
   //   If a matching node is found, update the properties of it from the
   //   corresponding sync node.
   // * When all children sync nodes are done, add the extra children bookmark
   //   nodes to the sync parent node.
   //
-  // This algorithm will do a good job of merging when folder names are a good
-  // indicator of the two folders being the same. It will handle reordering and
-  // new node addition very well (without creating duplicates).
-  // This algorithm will not do well if the folder name has changes but the
-  // children under them are all the same.
+  // The best match algorithm uses folder title or bookmark title/url to
+  // perform the primary match. If there are multiple match candidates it
+  // selects the preferred one based on sync node external ID match to the
+  // bookmark folder ID.
 
   DCHECK(bookmark_model_->loaded());
 
   // To prime our association, we associate the top-level nodes, Bookmark Bar
   // and Other Bookmarks.
   if (!AssociateTaggedPermanentNode(bookmark_model_->bookmark_bar_node(),
                                     kBookmarkBarTag)) {
     return unrecoverable_error_handler_->CreateAndUploadError(
         FROM_HERE,
         "Bookmark bar node not found",
@@ skipping 43 matching lines @@
   syncer::WriteTransaction trans(FROM_HERE, user_share_);
   syncer::ReadNode bm_root(&trans);
   if (bm_root.InitTypeRoot(syncer::BOOKMARKS) == syncer::BaseNode::INIT_OK) {
     syncer_merge_result->set_num_items_before_association(
         bm_root.GetTotalNodeCount());
   }
   local_merge_result->set_num_items_before_association(
       bookmark_model_->root_node()->GetTotalNodeCount());
 
   // Remove obsolete bookmarks according to sync delete journal.
+  // TODO (stanisc): rewrite this to avoid a separate traversal and instead
+  // perform deletes at the end of the loop below where the unmatched
+  // bookmark nodes are created as sync nodes.

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

Was this something you wanted to do in this patch or a later patch? If a later,
file a bug for it?

[stanisc, 2015/02/09 19:15:37]

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.

   local_merge_result->set_num_items_deleted(
       ApplyDeletesFromSyncJournal(&trans));
 
   while (!dfs_stack.empty()) {
     int64 sync_parent_id = dfs_stack.top();
     dfs_stack.pop();
 
     syncer::ReadNode sync_parent(&trans);
     if (sync_parent.InitByIdLookup(sync_parent_id) !=
             syncer::BaseNode::INIT_OK) {
@@ skipping 22 matching lines @@
       int64 sync_child_id = *it;
       syncer::ReadNode sync_child_node(&trans);
       if (sync_child_node.InitByIdLookup(sync_child_id) !=
               syncer::BaseNode::INIT_OK) {
         return unrecoverable_error_handler_->CreateAndUploadError(
             FROM_HERE,
             "Failed to lookup node.",
             model_type());
       }
 
-      const BookmarkNode* child_node = NULL;
-      child_node = node_finder.FindBookmarkNode(
+      const BookmarkNode* child_node = node_finder.FindBookmarkNode(
           GURL(sync_child_node.GetBookmarkSpecifics().url()),
-          sync_child_node.GetTitle(),
-          sync_child_node.GetIsFolder());
+          sync_child_node.GetTitle(), sync_child_node.GetIsFolder(),
+          sync_child_node.GetExternalId());
       if (child_node) {
         Associate(child_node, sync_child_id);
 
         // All bookmarks are currently modified at association time, even if
         // nothing has changed.
         // TODO(sync): Only modify the bookmark model if necessary.
         BookmarkChangeProcessor::UpdateBookmarkWithSyncData(
             sync_child_node, bookmark_model_, child_node, profile_);
         bookmark_model_->Move(child_node, parent_node, index);
         local_merge_result->set_num_items_modified(
@@ skipping 57 matching lines @@
 int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
     syncer::BaseTransaction* trans) {
   int64 num_bookmark_deleted = 0;
 
   syncer::BookmarkDeleteJournalList bk_delete_journals;
   syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
   if (bk_delete_journals.empty())
     return 0;
   size_t num_journals_unmatched = bk_delete_journals.size();
 
+  // Make a set of all external IDs in the delete journal,
+  // ignore entries with unset external IDs.
+  std::set<int64> external_ids;

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

Maybe name this journaled_external_ids to make it a bit clearer?

[stanisc, 2015/02/09 19:15:37]

Done.

+  for (size_t i = 0; i < num_journals_unmatched; i++) {
+    if (bk_delete_journals[i].external_id != 0) {

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

nit: looks like most of this file is doing single line conditional bodies
without curly braces. Prefer keeping to that style.

[stanisc, 2015/02/09 19:15:37]

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

+      external_ids.insert(bk_delete_journals[i].external_id);
+    }
+  }
+
   // Check bookmark model from top to bottom.
   std::stack<const BookmarkNode*> dfs_stack;
   dfs_stack.push(bookmark_model_->bookmark_bar_node());
   dfs_stack.push(bookmark_model_->other_node());
   if (expect_mobile_bookmarks_folder_)
     dfs_stack.push(bookmark_model_->mobile_node());
   // Note: the root node may have additional extra nodes. Currently none of
   // them are meant to sync.
 
   // Remember folders that match delete journals in first pass but don't delete
   // them in case there are bookmarks left under them. After non-folder
   // bookmarks are removed in first pass, recheck the folders in reverse order
   // to remove empty ones.
   FolderInfoList folders_matched;
-  while (!dfs_stack.empty()) {
+  while (!dfs_stack.empty() && num_journals_unmatched > 0) {
     const BookmarkNode* parent = dfs_stack.top();
     dfs_stack.pop();
+    DCHECK(parent->is_folder());
 
-    BookmarkNodeFinder finder(parent);
-    // Iterate through journals from back to front. Remove matched journal by
-    // moving an unmatched journal at the tail to its position so that we can
-    // read unmatched journals off the head in next loop.
-    for (int i = num_journals_unmatched - 1; i >= 0; --i) {
-      const BookmarkNode* child = finder.FindBookmarkNode(
-          GURL(bk_delete_journals[i].specifics.bookmark().url()),
-          bk_delete_journals[i].specifics.bookmark().title(),
-          bk_delete_journals[i].is_folder);
-      if (child) {
-        if (child->is_folder()) {
-          // Remember matched folder without removing and delete only empty
-          // ones later.
-          folders_matched.push_back(FolderInfo(child, parent,
-                                               bk_delete_journals[i].id));
-        } else {
-          bookmark_model_->Remove(parent, parent->GetIndexOf(child));
-          ++num_bookmark_deleted;
+    // Enumerate folder children in reverse order to make it easier to remove
+    // bookmarks matching entries in the delete journal.
+    for (int child_index = parent->child_count() - 1;
+         child_index >= 0 && num_journals_unmatched > 0; --child_index) {
+      const BookmarkNode* child = parent->GetChild(child_index);
+      if (child->is_folder()) {
+        dfs_stack.push(child);
+      }
+
+      if (external_ids.find(child->id()) == external_ids.end()) {
+        // Skip bookmark node which id is not in the set of external IDs.
+        continue;
+      }
+
+      // Iterate through the journal entries from back to front. Remove matched
+      // journal by moving an unmatched entry at the tail to the matched
+      // position so that we can read unmatched entries off the head in next
+      // loop.
+      for (int journal_index = num_journals_unmatched - 1; journal_index >= 0;
+           --journal_index) {
+        const syncer::BookmarkDeleteJournal& delete_entry =
+            bk_delete_journals[journal_index];
+        if (child->id() == delete_entry.external_id &&
+            BookmarkNodeFinder::NodeMatches(
+                child, GURL(delete_entry.specifics.bookmark().url()),
+                delete_entry.specifics.bookmark().title(),
+                delete_entry.is_folder)) {
+          if (child->is_folder()) {
+            // Remember matched folder without removing and delete only empty
+            // ones later.
+            folders_matched.push_back(
+                FolderInfo(child, parent, delete_entry.id));
+          } else {
+            bookmark_model_->Remove(parent, child_index);
+            ++num_bookmark_deleted;
+          }
+          // Move unmatched journal here and decrement counter.
+          bk_delete_journals[journal_index] =
+              bk_delete_journals[--num_journals_unmatched];
+          break;
         }
-        // Move unmatched journal here and decrement counter.
-        bk_delete_journals[i] = bk_delete_journals[--num_journals_unmatched];
       }
     }
-    if (num_journals_unmatched == 0)
-      break;
-
-    for (int i = 0; i < parent->child_count(); ++i) {
-      if (parent->GetChild(i)->is_folder())
-        dfs_stack.push(parent->GetChild(i));
-    }
   }
 
   // Ids of sync nodes not found in bookmark model, meaning the deletions are
   // persisted and correponding delete journals can be dropped.
   std::set<int64> journals_to_purge;
 
   // Remove empty folders from bottom to top.
   for (FolderInfoList::reverse_iterator it = folders_matched.rbegin();
       it != folders_matched.rend(); ++it) {
     if (it->folder->child_count() == 0) {
@@ skipping 110 matching lines @@
                                  syncer::SyncError::PERSISTENCE_ERROR,
                                  message,
                                  syncer::BOOKMARKS);
       }
     }
   }
   return syncer::SyncError();
 }
 
 }  // namespace browser_sync