Bookmark Associator Refactoring

Initial refactoring of BookmarkAssociator code to prepare it for more complex
algorithm changes. The main purpose of the refactoring it to reduce the existing
algorithmic complexity by factoring out simple, distinctive parts of the algorithm
and bundling temporary variables and objects used into a context class.
Using a separate context class should make it easier to add new temporary
objects such as pending lists of unmatched native/sync nodes without having
to modify the functions argument lists all the time.

There shouldn't be any functional changes with one small exception -
the new implementation doesn't add IDs of node to the dirty associations for
nodes which external ID already matches the ID on the native side and doesn't
schedule persisting association for those nodes.

BUG=456876

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

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

4 files changed, 316 insertions, 237 deletions

diff --git a/chrome/browser/sync/glue/bookmark_change_processor.cc b/chrome/browser/sync/glue/bookmark_change_processor.cc
index 0336a78..ee1e4ca 100644
--- a/chrome/browser/sync/glue/bookmark_change_processor.cc
+++ b/chrome/browser/sync/glue/bookmark_change_processor.cc
@@ -300,7 +300,7 @@ int64 BookmarkChangeProcessor::CreateSyncNode(const BookmarkNode* parent,
 
   // Associate the ID from the sync domain with the bookmark node, so that we
   // can refer back to this item later.
-  associator->Associate(child, sync_child.GetId());
+  associator->Associate(child, sync_child);
 
   return sync_child.GetId();
 }
@@ -639,7 +639,7 @@ void BookmarkChangeProcessor::ApplyChangesFromSyncModel(
     if (synced_bookmarks_id != syncer::kInvalidId &&
         it->id == synced_bookmarks_id) {
       // This is a newly created Synced Bookmarks node. Associate it.
-      model_associator_->Associate(model->mobile_node(), it->id);
+      model_associator_->Associate(model->mobile_node(), synced_bookmarks);
       continue;
     }
 
@@ -689,7 +689,7 @@ void BookmarkChangeProcessor::ApplyChangesFromSyncModel(
                    << src.GetBookmarkSpecifics().url();
         continue;
       }
-      model_associator_->Associate(dst, src.GetId());
+      model_associator_->Associate(dst, src);
     }
 
     to_reposition.insert(std::make_pair(src.GetPositionIndex(), dst));
diff --git a/chrome/browser/sync/glue/bookmark_model_associator.cc b/chrome/browser/sync/glue/bookmark_model_associator.cc
index d24a7e7..12d2635 100644
--- a/chrome/browser/sync/glue/bookmark_model_associator.cc
+++ b/chrome/browser/sync/glue/bookmark_model_associator.cc
@@ -4,8 +4,6 @@
 
 #include "chrome/browser/sync/glue/bookmark_model_associator.h"
 
-#include <stack>
-
 #include "base/bind.h"
 #include "base/command_line.h"
 #include "base/containers/hash_tables.h"
@@ -205,47 +203,69 @@ void BookmarkNodeFinder::ConvertTitleToSyncInternalFormat(
   base::TruncateUTF8ToByteSize(*output, kTitleLimitBytes, output);
 }
 
-// Helper class to build an index of bookmark nodes by their IDs.
-class BookmarkNodeIdIndex {
- public:
-  BookmarkNodeIdIndex() { }
-  ~BookmarkNodeIdIndex() { }
+BookmarkModelAssociator::Context::Context(
+    syncer::SyncMergeResult* local_merge_result,
+    syncer::SyncMergeResult* syncer_merge_result)
+    : local_merge_result_(local_merge_result),
+      syncer_merge_result_(syncer_merge_result) {
+}
 
-  // Adds the given bookmark node and all its descendants to the ID index.
-  // Does nothing if node is NULL.
-  void AddAll(const BookmarkNode* node);
+BookmarkModelAssociator::Context::~Context() {
+}
 
-  // Finds the bookmark node with the given ID.
-  // Returns NULL if none exists with the given id.
-  const BookmarkNode* Find(int64 id) const;
+void BookmarkModelAssociator::Context::PushNode(int64 sync_id) {
+  dfs_stack_.push(sync_id);
+}
 
-  // Returns the count of nodes in the index.
-  size_t count() const { return node_index_.size(); }
+bool BookmarkModelAssociator::Context::PopNode(int64* sync_id) {
+  if (dfs_stack_.empty()) {
+    *sync_id = 0;
+    return false;
+  }
+  *sync_id = dfs_stack_.top();
+  dfs_stack_.pop();
+  return true;
+}
 
- private:
-  typedef base::hash_map<int64, const BookmarkNode*> BookmarkIdMap;
-  // Map that holds nodes indexed by their ids.
-  BookmarkIdMap node_index_;
+void BookmarkModelAssociator::Context::SetPreAssociationVersions(
+    int64 native_version,
+    int64 sync_version) {
+  local_merge_result_->set_pre_association_version(native_version);
+  syncer_merge_result_->set_pre_association_version(sync_version);
+}
 
-  DISALLOW_COPY_AND_ASSIGN(BookmarkNodeIdIndex);
-};
+void BookmarkModelAssociator::Context::SetNumItemsBeforeAssociation(
+    int local_num,
+    int sync_num) {
+  local_merge_result_->set_num_items_before_association(local_num);
+  syncer_merge_result_->set_num_items_before_association(sync_num);
+}
 
-void BookmarkNodeIdIndex::AddAll(const BookmarkNode* node) {
-  if (!node)
-    return;
+void BookmarkModelAssociator::Context::SetNumItemsAfterAssociation(
+    int local_num,
+    int sync_num) {
+  local_merge_result_->set_num_items_after_association(local_num);
+  syncer_merge_result_->set_num_items_after_association(sync_num);
+}
 
-  node_index_[node->id()] = node;
+void BookmarkModelAssociator::Context::IncrementLocalItemsDeleted() {
+  local_merge_result_->set_num_items_deleted(
+      local_merge_result_->num_items_deleted() + 1);
+}
 
-  if (!node->is_folder())
-    return;
+void BookmarkModelAssociator::Context::IncrementLocalItemsAdded() {
+  local_merge_result_->set_num_items_added(
+      local_merge_result_->num_items_added() + 1);
+}
 
-  for (int i = 0; i < node->child_count(); ++i)
-    AddAll(node->GetChild(i));
+void BookmarkModelAssociator::Context::IncrementLocalItemsModified() {
+  local_merge_result_->set_num_items_modified(
+      local_merge_result_->num_items_modified() + 1);
 }
 
-const BookmarkNode* BookmarkNodeIdIndex::Find(int64 id) const {
-  BookmarkIdMap::const_iterator iter = node_index_.find(id);
-  return iter == node_index_.end() ? NULL : iter->second;
+void BookmarkModelAssociator::Context::IncrementSyncItemsAdded() {
+  syncer_merge_result_->set_num_items_added(
+      syncer_merge_result_->num_items_added() + 1);
 }
 
 BookmarkModelAssociator::BookmarkModelAssociator(
@@ -321,8 +341,8 @@ bool BookmarkModelAssociator::InitSyncNodeFromChromeId(
   return true;
 }
 
-void BookmarkModelAssociator::Associate(const BookmarkNode* node,
-                                        int64 sync_id) {
+void BookmarkModelAssociator::AddAssociation(const BookmarkNode* node,
+                                             int64 sync_id) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   int64 node_id = node->id();
   DCHECK_NE(sync_id, syncer::kInvalidId);
@@ -330,9 +350,23 @@ void BookmarkModelAssociator::Associate(const BookmarkNode* node,
   DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end());
   id_map_[node_id] = sync_id;
   id_map_inverse_[sync_id] = node;
-  dirty_associations_sync_ids_.insert(sync_id);
-  PostPersistAssociationsTask();
+}
+
+void BookmarkModelAssociator::Associate(const BookmarkNode* node,
+                                        const syncer::BaseNode& sync_node) {
+  AddAssociation(node, sync_node.GetId());
+
+  // TODO(stanisc): crbug.com/456876: consider not doing this on every single
+  // association.
   UpdatePermanentNodeVisibility();
+
+  // The same check exists in PersistAssociations. However it is better to
+  // do the check earlier to avoid the cost of decrypting nodes again
+  // in PersistAssociations.
+  if (node->id() != sync_node.GetExternalId()) {
+    dirty_associations_sync_ids_.insert(sync_node.GetId());
+    PostPersistAssociationsTask();
+  }
 }
 
 void BookmarkModelAssociator::Disassociate(int64 sync_id) {
@@ -349,38 +383,25 @@ bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
   DCHECK(has_nodes);
   *has_nodes = false;
   bool has_mobile_folder = true;
-  int64 bookmark_bar_sync_id;
-  if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_sync_id)) {
-    return false;
-  }
-  int64 other_bookmarks_sync_id;
-  if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_sync_id)) {
-    return false;
-  }
-  int64 mobile_bookmarks_sync_id;
-  if (!GetSyncIdForTaggedNode(kMobileBookmarksTag, &mobile_bookmarks_sync_id)) {
-    has_mobile_folder = false;
-  }
 
   syncer::ReadTransaction trans(FROM_HERE, user_share_);
 
   syncer::ReadNode bookmark_bar_node(&trans);
-  if (bookmark_bar_node.InitByIdLookup(bookmark_bar_sync_id) !=
-          syncer::BaseNode::INIT_OK) {
+  if (bookmark_bar_node.InitByTagLookupForBookmarks(kBookmarkBarTag) !=
+      syncer::BaseNode::INIT_OK) {
     return false;
   }
 
   syncer::ReadNode other_bookmarks_node(&trans);
-  if (other_bookmarks_node.InitByIdLookup(other_bookmarks_sync_id) !=
-          syncer::BaseNode::INIT_OK) {
+  if (other_bookmarks_node.InitByTagLookupForBookmarks(kOtherBookmarksTag) !=
+      syncer::BaseNode::INIT_OK) {
     return false;
   }
 
   syncer::ReadNode mobile_bookmarks_node(&trans);
-  if (has_mobile_folder &&
-      mobile_bookmarks_node.InitByIdLookup(mobile_bookmarks_sync_id) !=
-          syncer::BaseNode::INIT_OK) {
-    return false;
+  if (mobile_bookmarks_node.InitByTagLookupForBookmarks(kMobileBookmarksTag) !=
+      syncer::BaseNode::INIT_OK) {
+    has_mobile_folder = false;
   }
 
   // Sync model has user created nodes if any of the permanent nodes has
@@ -392,26 +413,19 @@ bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 }
 
 bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
-    const BookmarkNode* permanent_node, const std::string&tag) {
+    syncer::BaseTransaction* trans,
+    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);
-  return true;
-}
-
-bool BookmarkModelAssociator::GetSyncIdForTaggedNode(const std::string& tag,
-                                                     int64* sync_id) {
-  syncer::ReadTransaction trans(FROM_HERE, user_share_);
-  syncer::ReadNode sync_node(&trans);
-  if (sync_node.InitByTagLookupForBookmarks(
-      tag.c_str()) != syncer::BaseNode::INIT_OK)
+  syncer::ReadNode sync_node(trans);
+  if (sync_node.InitByTagLookupForBookmarks(tag) != syncer::BaseNode::INIT_OK)
     return false;
-  *sync_id = sync_node.GetId();
+
+  Associate(permanent_node, sync_node);
   return true;
 }
 
@@ -423,8 +437,9 @@ syncer::SyncError BookmarkModelAssociator::AssociateModels(
   ScopedSuspendBookmarkUndo suspend_undo(
       BookmarkUndoServiceFactory::GetForProfileIfExists(profile_));
 
-  syncer::SyncError error = CheckModelSyncState(local_merge_result,
-                                                syncer_merge_result);
+  Context context(local_merge_result, syncer_merge_result);
+
+  syncer::SyncError error = CheckModelSyncState(&context);
   if (error.IsSet())
     return error;
 
@@ -432,107 +447,120 @@ syncer::SyncError BookmarkModelAssociator::AssociateModels(
       new ScopedAssociationUpdater(bookmark_model_));
   DisassociateModels();
 
-  return BuildAssociations(local_merge_result, syncer_merge_result);
+  return BuildAssociations(&context);
 }
 
-syncer::SyncError BookmarkModelAssociator::BuildAssociations(
-    syncer::SyncMergeResult* local_merge_result,
-    syncer::SyncMergeResult* syncer_merge_result) {
-  // Algorithm description:
-  // 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.
-  //
-  // 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());
-
+syncer::SyncError BookmarkModelAssociator::AssociatePermanentFolders(
+    syncer::BaseTransaction* trans,
+    Context* context) {
   // To prime our association, we associate the top-level nodes, Bookmark Bar
   // and Other Bookmarks.
-  if (!AssociateTaggedPermanentNode(bookmark_model_->bookmark_bar_node(),
+  if (!AssociateTaggedPermanentNode(trans, bookmark_model_->bookmark_bar_node(),
                                     kBookmarkBarTag)) {
     return unrecoverable_error_handler_->CreateAndUploadError(
-        FROM_HERE,
-        "Bookmark bar node not found",
-        model_type());
+        FROM_HERE, "Bookmark bar node not found", model_type());
   }
 
-  if (!AssociateTaggedPermanentNode(bookmark_model_->other_node(),
+  if (!AssociateTaggedPermanentNode(trans, bookmark_model_->other_node(),
                                     kOtherBookmarksTag)) {
     return unrecoverable_error_handler_->CreateAndUploadError(
-        FROM_HERE,
-        "Other bookmarks node not found",
-        model_type());
+        FROM_HERE, "Other bookmarks node not found", model_type());
   }
 
-  if (!AssociateTaggedPermanentNode(bookmark_model_->mobile_node(),
+  if (!AssociateTaggedPermanentNode(trans, bookmark_model_->mobile_node(),
                                     kMobileBookmarksTag) &&
       expect_mobile_bookmarks_folder_) {
     return unrecoverable_error_handler_->CreateAndUploadError(
-        FROM_HERE,
-        "Mobile bookmarks node not found",
-        model_type());
+        FROM_HERE, "Mobile bookmarks node not found", model_type());
   }
 
   // Note: the root node may have additional extra nodes. Currently none of
   // them are meant to sync.
-
-  int64 bookmark_bar_sync_id = GetSyncIdFromChromeId(
-      bookmark_model_->bookmark_bar_node()->id());
+  int64 bookmark_bar_sync_id =
+      GetSyncIdFromChromeId(bookmark_model_->bookmark_bar_node()->id());
   DCHECK_NE(bookmark_bar_sync_id, syncer::kInvalidId);
-  int64 other_bookmarks_sync_id = GetSyncIdFromChromeId(
-      bookmark_model_->other_node()->id());
+  int64 other_bookmarks_sync_id =
+      GetSyncIdFromChromeId(bookmark_model_->other_node()->id());
   DCHECK_NE(other_bookmarks_sync_id, syncer::kInvalidId);
-  int64 mobile_bookmarks_sync_id = GetSyncIdFromChromeId(
-       bookmark_model_->mobile_node()->id());
+  int64 mobile_bookmarks_sync_id =
+      GetSyncIdFromChromeId(bookmark_model_->mobile_node()->id());
   if (expect_mobile_bookmarks_folder_) {
     DCHECK_NE(syncer::kInvalidId, mobile_bookmarks_sync_id);
   }
 
   // WARNING: The order in which we push these should match their order in the
   // bookmark model (see BookmarkModel::DoneLoading(..)).
-  std::stack<int64> dfs_stack;
-  dfs_stack.push(bookmark_bar_sync_id);
-  dfs_stack.push(other_bookmarks_sync_id);
+  context->PushNode(bookmark_bar_sync_id);
+  context->PushNode(other_bookmarks_sync_id);
   if (mobile_bookmarks_sync_id != syncer::kInvalidId)
-    dfs_stack.push(mobile_bookmarks_sync_id);
+    context->PushNode(mobile_bookmarks_sync_id);
 
-  syncer::WriteTransaction trans(FROM_HERE, user_share_);
-  syncer::ReadNode bm_root(&trans);
+  return syncer::SyncError();
+}
+
+void BookmarkModelAssociator::SetNumItemsBeforeAssociation(
+    syncer::BaseTransaction* trans,
+    Context* context) {
+  int syncer_num = 0;
+  syncer::ReadNode bm_root(trans);
+  if (bm_root.InitTypeRoot(syncer::BOOKMARKS) == syncer::BaseNode::INIT_OK) {
+    syncer_num = bm_root.GetTotalNodeCount();
+  }
+  context->SetNumItemsBeforeAssociation(
+      bookmark_model_->root_node()->GetTotalNodeCount(), syncer_num);
+}
+
+void BookmarkModelAssociator::SetNumItemsAfterAssociation(
+    syncer::BaseTransaction* trans,
+    Context* context) {
+  int syncer_num = 0;
+  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());
+    syncer_num = bm_root.GetTotalNodeCount();
   }
-  local_merge_result->set_num_items_before_association(
-      bookmark_model_->root_node()->GetTotalNodeCount());
+  context->SetNumItemsAfterAssociation(
+      bookmark_model_->root_node()->GetTotalNodeCount(), syncer_num);
+}
+
+syncer::SyncError BookmarkModelAssociator::BuildAssociations(Context* context) {
+  DCHECK(bookmark_model_->loaded());
+
+  syncer::WriteTransaction trans(FROM_HERE, user_share_);
+
+  syncer::SyncError error = AssociatePermanentFolders(&trans, context);
+  if (error.IsSet())
+    return error;
+
+  SetNumItemsBeforeAssociation(&trans, context);
 
   // Remove obsolete bookmarks according to sync delete journal.
-  // TODO (stanisc): crbug.com/456876: rewrite this to avoid a separate
+  // 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));
-
-  while (!dfs_stack.empty()) {
-    int64 sync_parent_id = dfs_stack.top();
-    dfs_stack.pop();
+  ApplyDeletesFromSyncJournal(&trans, context);
 
+  // Algorithm description:
+  // 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.
+  //
+  // 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.
+  int64 sync_parent_id;
+  while (context->PopNode(&sync_parent_id)) {
     syncer::ReadNode sync_parent(&trans);
     if (sync_parent.InitByIdLookup(sync_parent_id) !=
-            syncer::BaseNode::INIT_OK) {
+        syncer::BaseNode::INIT_OK) {
       return unrecoverable_error_handler_->CreateAndUploadError(
-          FROM_HERE,
-          "Failed to lookup node.",
-          model_type());
+          FROM_HERE, "Failed to lookup node.", model_type());
     }
     // Only folder nodes are pushed on to the stack.
     DCHECK(sync_parent.GetIsFolder());
@@ -544,84 +572,86 @@ syncer::SyncError BookmarkModelAssociator::BuildAssociations(
     }
     DCHECK(parent_node->is_folder());
 
-    BookmarkNodeFinder node_finder(parent_node);
-
     std::vector<int64> children;
     sync_parent.GetChildIds(&children);
-    int index = 0;
-    for (std::vector<int64>::const_iterator it = children.begin();
-         it != children.end(); ++it) {
-      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());
-      }
+    error = BuildAssociations(&trans, parent_node, children, context);
+    if (error.IsSet())
+      return error;
+  }
 
-      const BookmarkNode* child_node = node_finder.FindBookmarkNode(
-          GURL(sync_child_node.GetBookmarkSpecifics().url()),
-          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(
-            local_merge_result->num_items_modified() + 1);
-      } else {
-        DCHECK_LE(index, parent_node->child_count());
-        child_node = BookmarkChangeProcessor::CreateBookmarkNode(
-            &sync_child_node, parent_node, bookmark_model_, profile_, index);
-        if (!child_node) {
-          return unrecoverable_error_handler_->CreateAndUploadError(
-              FROM_HERE, "Failed to create bookmark node with title " +
-                             sync_child_node.GetTitle() + " and url " +
-                             sync_child_node.GetBookmarkSpecifics().url(),
-              model_type());
-        }
-        Associate(child_node, sync_child_id);
-        local_merge_result->set_num_items_added(
-            local_merge_result->num_items_added() + 1);
-      }
-      if (sync_child_node.GetIsFolder())
-        dfs_stack.push(sync_child_id);
-      ++index;
+  SetNumItemsAfterAssociation(&trans, context);
+
+  return syncer::SyncError();
+}
+
+syncer::SyncError BookmarkModelAssociator::BuildAssociations(
+    syncer::WriteTransaction* trans,
+    const BookmarkNode* parent_node,
+    const std::vector<int64>& sync_ids,
+    Context* context) {
+  BookmarkNodeFinder node_finder(parent_node);
+
+  int index = 0;
+  for (std::vector<int64>::const_iterator it = sync_ids.begin();
+       it != sync_ids.end(); ++it) {
+    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());
     }
 
-    // At this point all the children nodes of the parent sync node have
-    // corresponding children in the parent bookmark node and they are all in
-    // the right positions: from 0 to index - 1.
-    // So the children starting from index in the parent bookmark node are the
-    // ones that are not present in the parent sync node. So create them.
-    for (int i = index; i < parent_node->child_count(); ++i) {
-      int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
-          parent_node, bookmark_model_, i, &trans, this,
-          unrecoverable_error_handler_);
-      if (syncer::kInvalidId == sync_child_id) {
+    GURL url(sync_child_node.GetBookmarkSpecifics().url());
+    const BookmarkNode* child_node = node_finder.FindBookmarkNode(
+        url, sync_child_node.GetTitle(), sync_child_node.GetIsFolder(),
+        sync_child_node.GetExternalId());
+    if (child_node) {
+      // 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);
+      context->IncrementLocalItemsModified();
+    } else {
+      DCHECK_LE(index, parent_node->child_count());
+      child_node = BookmarkChangeProcessor::CreateBookmarkNode(
+          &sync_child_node, parent_node, bookmark_model_, profile_, index);
+      if (!child_node) {
         return unrecoverable_error_handler_->CreateAndUploadError(
-            FROM_HERE,
-            "Failed to create sync node.",
+            FROM_HERE, "Failed to create bookmark node with title " +
+                           sync_child_node.GetTitle() + " and url " +
+                           url.possibly_invalid_spec(),
             model_type());
       }
-      syncer_merge_result->set_num_items_added(
-          syncer_merge_result->num_items_added() + 1);
-      if (parent_node->GetChild(i)->is_folder())
-        dfs_stack.push(sync_child_id);
+      context->IncrementLocalItemsAdded();
     }
+
+    Associate(child_node, sync_child_node);
+
+    if (sync_child_node.GetIsFolder())
+      context->PushNode(sync_child_id);
+    ++index;
   }
 
-  local_merge_result->set_num_items_after_association(
-      bookmark_model_->root_node()->GetTotalNodeCount());
-  syncer_merge_result->set_num_items_after_association(
-      bm_root.GetTotalNodeCount());
+  // At this point all the children nodes of the parent sync node have
+  // corresponding children in the parent bookmark node and they are all in
+  // the right positions: from 0 to index - 1.
+  // So the children starting from index in the parent bookmark node are the
+  // ones that are not present in the parent sync node. So create them.
+  for (int i = index; i < parent_node->child_count(); ++i) {
+    int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
+        parent_node, bookmark_model_, i, trans, this,
+        unrecoverable_error_handler_);
+    if (syncer::kInvalidId == sync_child_id) {
+      return unrecoverable_error_handler_->CreateAndUploadError(
+          FROM_HERE, "Failed to create sync node.", model_type());
+    }
+    context->IncrementSyncItemsAdded();
+    if (parent_node->GetChild(i)->is_folder())
+      context->PushNode(sync_child_id);
+  }
 
   return syncer::SyncError();
 }
@@ -635,14 +665,14 @@ struct FolderInfo {
 };
 typedef std::vector<FolderInfo> FolderInfoList;
 
-int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
-    syncer::BaseTransaction* trans) {
-  int64 num_bookmark_deleted = 0;
-
+void BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
+    syncer::BaseTransaction* trans,
+    Context* context) {
   syncer::BookmarkDeleteJournalList bk_delete_journals;
   syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
   if (bk_delete_journals.empty())
-    return 0;
+    return;
+
   size_t num_journals_unmatched = bk_delete_journals.size();
 
   // Make a set of all external IDs in the delete journal,
@@ -706,7 +736,7 @@ int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
                 FolderInfo(child, parent, delete_entry.id));
           } else {
             bookmark_model_->Remove(parent, child_index);
-            ++num_bookmark_deleted;
+            context->IncrementLocalItemsDeleted();
           }
           // Move unmatched journal here and decrement counter.
           bk_delete_journals[journal_index] =
@@ -726,7 +756,7 @@ int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
       it != folders_matched.rend(); ++it) {
     if (it->folder->child_count() == 0) {
       bookmark_model_->Remove(it->parent, it->parent->GetIndexOf(it->folder));
-      ++num_bookmark_deleted;
+      context->IncrementLocalItemsDeleted();
     } else {
       // Keep non-empty folder and remove its journal so that it won't match
       // again in the future.
@@ -738,8 +768,6 @@ int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
   for (size_t i = 0; i < num_journals_unmatched; ++i)
     journals_to_purge.insert(bk_delete_journals[i].id);
   syncer::DeleteJournal::PurgeDeleteJournals(trans, journals_to_purge);
-
-  return num_bookmark_deleted;
 }
 
 void BookmarkModelAssociator::PostPersistAssociationsTask() {
@@ -805,16 +833,13 @@ bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
 }
 
 syncer::SyncError BookmarkModelAssociator::CheckModelSyncState(
-    syncer::SyncMergeResult* local_merge_result,
-    syncer::SyncMergeResult* syncer_merge_result) const {
+    Context* context) const {
   int64 native_version =
       bookmark_model_->root_node()->sync_transaction_version();
   if (native_version != syncer::syncable::kInvalidTransactionVersion) {
     syncer::ReadTransaction trans(FROM_HERE, user_share_);
-    local_merge_result->set_pre_association_version(native_version);
-
     int64 sync_version = trans.GetModelVersion(syncer::BOOKMARKS);
-    syncer_merge_result->set_pre_association_version(sync_version);
+    context->SetPreAssociationVersions(native_version, sync_version);
 
     if (native_version != sync_version) {
       UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
diff --git a/chrome/browser/sync/glue/bookmark_model_associator.h b/chrome/browser/sync/glue/bookmark_model_associator.h
index aecdcbf..01818bd 100644
--- a/chrome/browser/sync/glue/bookmark_model_associator.h
+++ b/chrome/browser/sync/glue/bookmark_model_associator.h
@@ -7,6 +7,7 @@
 
 #include <map>
 #include <set>
+#include <stack>
 #include <string>
 
 #include "base/basictypes.h"
@@ -28,6 +29,7 @@ namespace syncer {
 class BaseNode;
 class BaseTransaction;
 struct UserShare;
+class WriteTransaction;
 }
 
 namespace browser_sync {
@@ -90,8 +92,9 @@ class BookmarkModelAssociator
   bool InitSyncNodeFromChromeId(const int64& node_id,
                                 syncer::BaseNode* sync_node) override;
 
-  // Associates the given bookmark node with the given sync id.
-  void Associate(const bookmarks::BookmarkNode* node, int64 sync_id) override;
+  // Associates the given bookmark node with the given sync node.
+  void Associate(const bookmarks::BookmarkNode* node,
+                 const syncer::BaseNode& sync_node) override;
   // Remove the association that corresponds to the given sync id.
   void Disassociate(int64 sync_id) override;
 
@@ -103,32 +106,69 @@ class BookmarkModelAssociator
   // See ModelAssociator interface.
   bool CryptoReadyIfNecessary() override;
 
- protected:
-  // Stores the id of the node with the given tag in |sync_id|.
-  // Returns of that node was found successfully.
-  // Tests override this.
-  virtual bool GetSyncIdForTaggedNode(const std::string& tag, int64* sync_id);
-
  private:
   typedef std::map<int64, int64> BookmarkIdToSyncIdMap;
   typedef std::map<int64, const bookmarks::BookmarkNode*>
       SyncIdToBookmarkNodeMap;
   typedef std::set<int64> DirtyAssociationsSyncIds;
 
+  // Add association between native node and sync node to the maps.
+  void AddAssociation(const bookmarks::BookmarkNode* node, int64 sync_id);
+
   // Posts a task to persist dirty associations.
   void PostPersistAssociationsTask();
   // Persists all dirty associations.
   void PersistAssociations();
 
+  // Helper class used within AssociateModels to simplify the logic and
+  // minimize the number of arguments passed between private functions.
+  class Context {
+   public:
+    Context(syncer::SyncMergeResult* local_merge_result,
+            syncer::SyncMergeResult* syncer_merge_result);
+    ~Context();
+
+    // Push a sync node to the DFS stack.
+    void PushNode(int64 sync_id);
+    // Pops a sync node from the DFS stack. Returns false if the stack
+    // is empty.
+    bool PopNode(int64* sync_id);
+
+    // The following methods are used to update |local_merge_result_| and
+    // |syncer_merge_result_|.
+    void SetPreAssociationVersions(int64 native_version, int64 sync_version);
+    void SetNumItemsBeforeAssociation(int local_num, int sync_num);
+    void SetNumItemsAfterAssociation(int local_num, int sync_num);
+    void IncrementLocalItemsDeleted();
+    void IncrementLocalItemsAdded();
+    void IncrementLocalItemsModified();
+    void IncrementSyncItemsAdded();
+
+   private:
+    // DFS stack of sync nodes traversed during association.
+    std::stack<int64> dfs_stack_;
+    // Local and merge results are not owned.
+    syncer::SyncMergeResult* local_merge_result_;
+    syncer::SyncMergeResult* syncer_merge_result_;
+
+    DISALLOW_COPY_AND_ASSIGN(Context);
+  };
+
   // Matches up the bookmark model and the sync model to build model
   // associations.
-  syncer::SyncError BuildAssociations(
-      syncer::SyncMergeResult* local_merge_result,
-      syncer::SyncMergeResult* syncer_merge_result);
+  syncer::SyncError BuildAssociations(Context* context);
 
-  // Removes bookmark nodes whose corresponding sync nodes have been deleted
-  // according to sync delete journals. Return number of deleted bookmarks.
-  int64 ApplyDeletesFromSyncJournal(syncer::BaseTransaction* trans);
+  // Two helper functions that populate SyncMergeResult with numbers of
+  // items before/after the association.
+  void SetNumItemsBeforeAssociation(syncer::BaseTransaction* trans,
+                                    Context* context);
+  void SetNumItemsAfterAssociation(syncer::BaseTransaction* trans,
+                                   Context* context);
+
+  // Helper function that associates all tagged permanent folders and primes
+  // the provided context with sync IDs of those folders.
+  syncer::SyncError AssociatePermanentFolders(syncer::BaseTransaction* trans,
+                                              Context* context);
 
   // Associate a top-level node of the bookmark model with a permanent node in
   // the sync domain.  Such permanent nodes are identified by a tag that is
@@ -137,16 +177,29 @@ class BookmarkModelAssociator
   // Bookmarks folder.  The sync nodes are server-created.
   // Returns true on success, false if association failed.
   bool AssociateTaggedPermanentNode(
+      syncer::BaseTransaction* trans,
       const bookmarks::BookmarkNode* permanent_node,
       const std::string& tag) WARN_UNUSED_RESULT;
 
+  // Removes bookmark nodes whose corresponding sync nodes have been deleted
+  // according to sync delete journals.
+  void ApplyDeletesFromSyncJournal(syncer::BaseTransaction* trans,
+                                   Context* context);
+
+  // The main part of the association process that associatiates
+  // native nodes that are children of |parent_node| with sync nodes with IDs
+  // from |sync_ids|.
+  syncer::SyncError BuildAssociations(
+      syncer::WriteTransaction* trans,
+      const bookmarks::BookmarkNode* parent_node,
+      const std::vector<int64>& sync_ids,
+      Context* context);
+
   // Check whether bookmark model and sync model are synced by comparing
   // their transaction versions.
   // Returns a PERSISTENCE_ERROR if a transaction mismatch was detected where
   // the native model has a newer transaction verison.
-  syncer::SyncError CheckModelSyncState(
-      syncer::SyncMergeResult* local_merge_result,
-      syncer::SyncMergeResult* syncer_merge_result) const;
+  syncer::SyncError CheckModelSyncState(Context* context) const;
 
   bookmarks::BookmarkModel* bookmark_model_;
   Profile* profile_;
diff --git a/components/sync_driver/model_associator.h b/components/sync_driver/model_associator.h
index 0bc6d7a..4d6e327 100644
--- a/components/sync_driver/model_associator.h
+++ b/components/sync_driver/model_associator.h
@@ -83,8 +83,9 @@ class PerDataTypeAssociatorInterface : public AssociatorInterface {
       const IDType& node_id,
       syncer::BaseNode* sync_node) = 0;
 
-  // Associates the given chrome node with the given sync id.
-  virtual void Associate(const Node* node, int64 sync_id) = 0;
+  // Associates the given chrome node with the given sync node.
+  virtual void Associate(const Node* node,
+                         const syncer::BaseNode& sync_node) = 0;
 
   // Remove the association that corresponds to the given sync id.
   virtual void Disassociate(int64 sync_id) = 0;