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

chrome/browser/sync/glue/bookmark_model_associator.cc

Index: chrome/browser/sync/glue/bookmark_model_associator.cc
diff --git a/chrome/browser/sync/glue/bookmark_model_associator.cc b/chrome/browser/sync/glue/bookmark_model_associator.cc
index e8f561967e92a994dd8355ca5f75bb9001516398..29325970137f40f063c614c2d672c5b205161a10 100644
--- a/chrome/browser/sync/glue/bookmark_model_associator.cc
+++ b/chrome/browser/sync/glue/bookmark_model_associator.cc
@@ -76,21 +76,11 @@
   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 there are multiple matches then a node with ID matching |preferred_id|
-  // is returned; otherwise the first matching node is returned.
-  // If a matching node is found, it's removed for further matches.
+  // attribute. Returns the matching node if one exists; NULL otherwise. 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,
-                                       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);
+                                       bool is_folder);
 
  private:
   // Maps bookmark node titles to instances, duplicates allowed.
@@ -103,8 +93,8 @@
 
   // Converts and truncates bookmark titles in the form sync does internally
   // to avoid mismatches due to sync munging titles.
-  static void ConvertTitleToSyncInternalFormat(const std::string& input,
-                                               std::string* output);
+  void ConvertTitleToSyncInternalFormat(
+      const std::string& input, std::string* output);
 
   const BookmarkNode* parent_node_;
   BookmarkNodeMap child_nodes_;
@@ -142,63 +132,28 @@
 }
 
 const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
-    const GURL& url,
-    const std::string& title,
-    bool is_folder,
-    int64 preferred_id) {
-  const BookmarkNode* match = nullptr;
-
+    const GURL& url, const std::string& title, bool is_folder) {
   // 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()) {
-      if (node->id() == preferred_id || preferred_id == 0) {
-        // Preferred match - use this node.
-        match = node;
-        match_iter = iter;
-        break;
-      } else if (match == nullptr) {
-        // First match - continue iterating.
-        match = node;
-        match_iter = iter;
-      }
-    }
-  }
-
-  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,
-                                     bool is_folder) {
-  if (url != bookmark_node->url() || is_folder != bookmark_node->is_folder()) {
-    return false;
-  }
-
-  // The title passed to this method comes from a sync directory entry.
-  // The following two lines are needed to make the native bookmark title
-  // comparable. The same conversion is used in BookmarkNodeFinder constructor.
-  std::string bookmark_title = base::UTF16ToUTF8(bookmark_node->GetTitle());
-  ConvertTitleToSyncInternalFormat(bookmark_title, &bookmark_title);
-  return title == bookmark_title;
-}
-
-/* static */
+      // Remove the matched node so we don't match with it again.
+      child_nodes_.erase(iter);
+      return node;
+    }
+  }
+
+  return NULL;
+}
+
 void BookmarkNodeFinder::ConvertTitleToSyncInternalFormat(
     const std::string& input, std::string* output) {
   syncer::SyncAPINameToServerName(input, output);
@@ -391,6 +346,27 @@
   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.
@@ -448,10 +424,11 @@
   // * When all children sync nodes are done, add the extra children bookmark
   //   nodes to the sync parent node.
   //
-  // 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.
+  // 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.
 
   DCHECK(bookmark_model_->loaded());
 
@@ -515,9 +492,6 @@
       bookmark_model_->root_node()->GetTotalNodeCount());
 
   // Remove obsolete bookmarks according to sync delete journal.
-  // TODO (stanisc): crbug.com/456876: 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.
   local_merge_result->set_num_items_deleted(
       ApplyDeletesFromSyncJournal(&trans));
 
@@ -560,10 +534,11 @@
             model_type());
       }
 
-      const BookmarkNode* child_node = node_finder.FindBookmarkNode(
+      const BookmarkNode* child_node = NULL;
+      child_node = node_finder.FindBookmarkNode(
           GURL(sync_child_node.GetBookmarkSpecifics().url()),
-          sync_child_node.GetTitle(), sync_child_node.GetIsFolder(),
-          sync_child_node.GetExternalId());
+          sync_child_node.GetTitle(),
+          sync_child_node.GetIsFolder());
       if (child_node) {
         Associate(child_node, sync_child_id);
 
@@ -641,14 +616,6 @@
     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> journaled_external_ids;
-  for (size_t i = 0; i < num_journals_unmatched; i++) {
-    if (bk_delete_journals[i].external_id != 0)
-      journaled_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());
@@ -663,53 +630,39 @@
   // bookmarks are removed in first pass, recheck the folders in reverse order
   // to remove empty ones.
   FolderInfoList folders_matched;
-  while (!dfs_stack.empty() && num_journals_unmatched > 0) {
+  while (!dfs_stack.empty()) {
     const BookmarkNode* parent = dfs_stack.top();
     dfs_stack.pop();
-    DCHECK(parent->is_folder());
-
-    // 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 (journaled_external_ids.find(child->id()) ==
-          journaled_external_ids.end()) {
-        // Skip bookmark node which id is not in the set of external IDs.
-        continue;
+
+    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;
+        }
+        // Move unmatched journal here and decrement counter.
+        bk_delete_journals[i] = bk_delete_journals[--num_journals_unmatched];
       }
-
-      // 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;
-        }
-      }
+    }
+    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));
     }
   }