chrome/browser/sync/glue/bookmark_model_associator.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/sync/glue/bookmark_model_associator.h"
   6
   7 #include "base/bind.h"
   8 #include "base/command_line.h"
   9 #include "base/containers/hash_tables.h"
  10 #include "base/format_macros.h"
  11 #include "base/location.h"
  12 #include "base/macros.h"
  13 #include "base/metrics/field_trial.h"
  14 #include "base/single_thread_task_runner.h"
  15 #include "base/strings/string_number_conversions.h"
  16 #include "base/strings/string_util.h"
  17 #include "base/strings/stringprintf.h"
  18 #include "base/strings/utf_string_conversions.h"
  19 #include "base/thread_task_runner_handle.h"
  20 #include "chrome/browser/profiles/profile.h"
  21 #include "chrome/browser/sync/glue/bookmark_change_processor.h"
  22 #include "chrome/browser/undo/bookmark_undo_service_factory.h"
  23 #include "components/bookmarks/browser/bookmark_client.h"
  24 #include "components/bookmarks/browser/bookmark_model.h"
  25 #include "components/undo/bookmark_undo_service.h"
  26 #include "components/undo/bookmark_undo_utils.h"
  27 #include "content/public/browser/browser_thread.h"
  28 #include "sync/api/sync_error.h"
  29 #include "sync/api/sync_merge_result.h"
  30 #include "sync/internal_api/public/delete_journal.h"
  31 #include "sync/internal_api/public/read_node.h"
  32 #include "sync/internal_api/public/read_transaction.h"
  33 #include "sync/internal_api/public/write_node.h"
  34 #include "sync/internal_api/public/write_transaction.h"
  35 #include "sync/internal_api/syncapi_internal.h"
  36 #include "sync/syncable/entry.h"
  37 #include "sync/syncable/syncable_write_transaction.h"
  38 #include "sync/util/cryptographer.h"
  39 #include "sync/util/data_type_histogram.h"
  40
  41 using bookmarks::BookmarkModel;
  42 using bookmarks::BookmarkNode;
  43 using content::BrowserThread;
  44
  45 namespace browser_sync {
  46
  47 // The sync protocol identifies top-level entities by means of well-known tags,
  48 // which should not be confused with titles.  Each tag corresponds to a
  49 // singleton instance of a particular top-level node in a user's share; the
  50 // tags are consistent across users. The tags allow us to locate the specific
  51 // folders whose contents we care about synchronizing, without having to do a
  52 // lookup by name or path.  The tags should not be made user-visible.
  53 // For example, the tag "bookmark_bar" represents the permanent node for
  54 // bookmarks bar in Chrome. The tag "other_bookmarks" represents the permanent
  55 // folder Other Bookmarks in Chrome.
  56 //
  57 // It is the responsibility of something upstream (at time of writing,
  58 // the sync server) to create these tagged nodes when initializing sync
  59 // for the first time for a user.  Thus, once the backend finishes
  60 // initializing, the ProfileSyncService can rely on the presence of tagged
  61 // nodes.
  62 //
  63 // TODO(ncarter): Pull these tags from an external protocol specification
  64 // rather than hardcoding them here.
  65 const char kBookmarkBarTag[] = "bookmark_bar";
  66 const char kMobileBookmarksTag[] = "synced_bookmarks";
  67 const char kOtherBookmarksTag[] = "other_bookmarks";
  68
  69 // Maximum number of bytes to allow in a title (must match sync's internal
  70 // limits; see write_node.cc).
  71 const int kTitleLimitBytes = 255;
  72
  73 // TODO(stanisc): crbug.com/456876: Remove this once the optimistic association
  74 // experiment has ended.
  75 bool IsOptimisticAssociationEnabled() {
  76   const std::string group_name =
  77       base::FieldTrialList::FindFullName("SyncOptimisticBookmarkAssociation");
  78   return group_name == "Enabled";
  79 }
  80
  81 // Provides the following abstraction: given a parent bookmark node, find best
  82 // matching child node for many sync nodes.
  83 class BookmarkNodeFinder {
  84  public:
  85   // Creates an instance with the given parent bookmark node.
  86   explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
  87
  88   // Finds the bookmark node that matches the given url, title and folder
  89   // attribute. Returns the matching node if one exists; NULL otherwise.
  90   // If there are multiple matches then a node with ID matching |preferred_id|
  91   // is returned; otherwise the first matching node is returned.
  92   // If a matching node is found, it's removed for further matches.
  93   const BookmarkNode* FindBookmarkNode(const GURL& url,
  94                                        const std::string& title,
  95                                        bool is_folder,
  96                                        int64 preferred_id);
  97
  98   // Returns true if |bookmark_node| matches the specified |url|,
  99   // |title|, and |is_folder| flags.
 100   static bool NodeMatches(const BookmarkNode* bookmark_node,
 101                           const GURL& url,
 102                           const std::string& title,
 103                           bool is_folder);
 104
 105  private:
 106   // Maps bookmark node titles to instances, duplicates allowed.
 107   // Titles are converted to the sync internal format before
 108   // being used as keys for the map.
 109   typedef base::hash_multimap<std::string,
 110                               const BookmarkNode*> BookmarkNodeMap;
 111   typedef std::pair<BookmarkNodeMap::iterator,
 112                     BookmarkNodeMap::iterator> BookmarkNodeRange;
 113
 114   // Converts and truncates bookmark titles in the form sync does internally
 115   // to avoid mismatches due to sync munging titles.
 116   static void ConvertTitleToSyncInternalFormat(const std::string& input,
 117                                                std::string* output);
 118
 119   const BookmarkNode* parent_node_;
 120   BookmarkNodeMap child_nodes_;
 121
 122   DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
 123 };
 124
 125 class ScopedAssociationUpdater {
 126  public:
 127   explicit ScopedAssociationUpdater(BookmarkModel* model) {
 128     model_ = model;
 129     model->BeginExtensiveChanges();
 130   }
 131
 132   ~ScopedAssociationUpdater() {
 133     model_->EndExtensiveChanges();
 134   }
 135
 136  private:
 137   BookmarkModel* model_;
 138
 139   DISALLOW_COPY_AND_ASSIGN(ScopedAssociationUpdater);
 140 };
 141
 142 BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node)
 143     : parent_node_(parent_node) {
 144   for (int i = 0; i < parent_node_->child_count(); ++i) {
 145     const BookmarkNode* child_node = parent_node_->GetChild(i);
 146
 147     std::string title = base::UTF16ToUTF8(child_node->GetTitle());
 148     ConvertTitleToSyncInternalFormat(title, &title);
 149
 150     child_nodes_.insert(std::make_pair(title, child_node));
 151   }
 152 }
 153
 154 const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
 155     const GURL& url,
 156     const std::string& title,
 157     bool is_folder,
 158     int64 preferred_id) {
 159   const BookmarkNode* match = nullptr;
 160
 161   // First lookup a range of bookmarks with the same title.
 162   std::string adjusted_title;
 163   ConvertTitleToSyncInternalFormat(title, &adjusted_title);
 164   BookmarkNodeRange range = child_nodes_.equal_range(adjusted_title);
 165   BookmarkNodeMap::iterator match_iter = range.second;
 166   for (BookmarkNodeMap::iterator iter = range.first;
 167        iter != range.second;
 168        ++iter) {
 169     // Then within the range match the node by the folder bit
 170     // and the url.
 171     const BookmarkNode* node = iter->second;
 172     if (is_folder == node->is_folder() && url == node->url()) {
 173       if (node->id() == preferred_id || preferred_id == 0) {
 174         // Preferred match - use this node.
 175         match = node;
 176         match_iter = iter;
 177         break;
 178       } else if (match == nullptr) {
 179         // First match - continue iterating.
 180         match = node;
 181         match_iter = iter;
 182       }
 183     }
 184   }
 185
 186   if (match_iter != range.second) {
 187     // Remove the matched node so we don't match with it again.
 188     child_nodes_.erase(match_iter);
 189   }
 190
 191   return match;
 192 }
 193
 194 /* static */
 195 bool BookmarkNodeFinder::NodeMatches(const BookmarkNode* bookmark_node,
 196                                      const GURL& url,
 197                                      const std::string& title,
 198                                      bool is_folder) {
 199   if (url != bookmark_node->url() || is_folder != bookmark_node->is_folder()) {
 200     return false;
 201   }
 202
 203   // The title passed to this method comes from a sync directory entry.
 204   // The following two lines are needed to make the native bookmark title
 205   // comparable. The same conversion is used in BookmarkNodeFinder constructor.
 206   std::string bookmark_title = base::UTF16ToUTF8(bookmark_node->GetTitle());
 207   ConvertTitleToSyncInternalFormat(bookmark_title, &bookmark_title);
 208   return title == bookmark_title;
 209 }
 210
 211 /* static */
 212 void BookmarkNodeFinder::ConvertTitleToSyncInternalFormat(
 213     const std::string& input, std::string* output) {
 214   syncer::SyncAPINameToServerName(input, output);
 215   base::TruncateUTF8ToByteSize(*output, kTitleLimitBytes, output);
 216 }
 217
 218 BookmarkModelAssociator::Context::Context(
 219     syncer::SyncMergeResult* local_merge_result,
 220     syncer::SyncMergeResult* syncer_merge_result)
 221     : local_merge_result_(local_merge_result),
 222       syncer_merge_result_(syncer_merge_result),
 223       duplicate_count_(0),
 224       native_model_sync_state_(UNSET),
 225       id_index_initialized_(false) {
 226 }
 227
 228 BookmarkModelAssociator::Context::~Context() {
 229 }
 230
 231 void BookmarkModelAssociator::Context::PushNode(int64 sync_id) {
 232   dfs_stack_.push(sync_id);
 233 }
 234
 235 bool BookmarkModelAssociator::Context::PopNode(int64* sync_id) {
 236   if (dfs_stack_.empty()) {
 237     *sync_id = 0;
 238     return false;
 239   }
 240   *sync_id = dfs_stack_.top();
 241   dfs_stack_.pop();
 242   return true;
 243 }
 244
 245 void BookmarkModelAssociator::Context::SetPreAssociationVersions(
 246     int64 native_version,
 247     int64 sync_version) {
 248   local_merge_result_->set_pre_association_version(native_version);
 249   syncer_merge_result_->set_pre_association_version(sync_version);
 250 }
 251
 252 void BookmarkModelAssociator::Context::SetNumItemsBeforeAssociation(
 253     int local_num,
 254     int sync_num) {
 255   local_merge_result_->set_num_items_before_association(local_num);
 256   syncer_merge_result_->set_num_items_before_association(sync_num);
 257 }
 258
 259 void BookmarkModelAssociator::Context::SetNumItemsAfterAssociation(
 260     int local_num,
 261     int sync_num) {
 262   local_merge_result_->set_num_items_after_association(local_num);
 263   syncer_merge_result_->set_num_items_after_association(sync_num);
 264 }
 265
 266 void BookmarkModelAssociator::Context::IncrementLocalItemsDeleted() {
 267   local_merge_result_->set_num_items_deleted(
 268       local_merge_result_->num_items_deleted() + 1);
 269 }
 270
 271 void BookmarkModelAssociator::Context::IncrementLocalItemsAdded() {
 272   local_merge_result_->set_num_items_added(
 273       local_merge_result_->num_items_added() + 1);
 274 }
 275
 276 void BookmarkModelAssociator::Context::IncrementLocalItemsModified() {
 277   local_merge_result_->set_num_items_modified(
 278       local_merge_result_->num_items_modified() + 1);
 279 }
 280
 281 void BookmarkModelAssociator::Context::IncrementSyncItemsAdded() {
 282   syncer_merge_result_->set_num_items_added(
 283       syncer_merge_result_->num_items_added() + 1);
 284 }
 285
 286 void BookmarkModelAssociator::Context::IncrementSyncItemsDeleted(int count) {
 287   syncer_merge_result_->set_num_items_deleted(
 288       syncer_merge_result_->num_items_deleted() + count);
 289 }
 290
 291 void BookmarkModelAssociator::Context::UpdateDuplicateCount(
 292     const base::string16& title,
 293     const GURL& url) {
 294   // base::Hash is defined for 8-byte strings only so have to
 295   // cast the title data to char* and double the length in order to
 296   // compute its hash.
 297   size_t bookmark_hash = base::Hash(reinterpret_cast<const char*>(title.data()),
 298                                     title.length() * 2) ^
 299                          base::Hash(url.spec());
 300
 301   if (!hashes_.insert(bookmark_hash).second) {
 302     // This hash code already exists in the set.
 303     ++duplicate_count_;
 304   }
 305 }
 306
 307 void BookmarkModelAssociator::Context::AddBookmarkRoot(
 308     const bookmarks::BookmarkNode* root) {
 309   bookmark_roots_.push_back(root);
 310 }
 311
 312 void BookmarkModelAssociator::Context::BuildIdIndex() {
 313   DCHECK(!id_index_initialized_);
 314   BookmarkStack stack;
 315   for (BookmarkList::const_iterator it = bookmark_roots_.begin();
 316        it != bookmark_roots_.end(); ++it) {
 317     stack.push(*it);
 318   }
 319
 320   while (!stack.empty()) {
 321     const BookmarkNode* parent = stack.top();
 322     stack.pop();
 323     DCHECK(parent->is_folder());
 324     for (int i = 0; i < parent->child_count(); ++i) {
 325       const BookmarkNode* node = parent->GetChild(i);
 326       DCHECK(id_index_.find(node->id()) == id_index_.end());
 327       id_index_.insert(std::make_pair(node->id(), node));
 328       if (node->is_folder())
 329         stack.push(node);
 330     }
 331   }
 332
 333   id_index_initialized_ = true;
 334 }
 335
 336 const BookmarkNode* BookmarkModelAssociator::Context::LookupNodeInIdIndex(
 337     int64 native_id) {
 338   if (!id_index_initialized_) {
 339     // Build the index on demand.
 340     DCHECK(!bookmark_roots_.empty());
 341     BuildIdIndex();
 342   }
 343
 344   IdIndex::const_iterator it = id_index_.find(native_id);
 345   if (it == id_index_.end())
 346     return nullptr;
 347   return it->second;
 348 }
 349
 350 void BookmarkModelAssociator::Context::MarkForVersionUpdate(
 351     const bookmarks::BookmarkNode* node) {
 352   bookmarks_for_version_update_.push_back(node);
 353 }
 354
 355 BookmarkModelAssociator::BookmarkModelAssociator(
 356     BookmarkModel* bookmark_model,
 357     Profile* profile,
 358     syncer::UserShare* user_share,
 359     sync_driver::DataTypeErrorHandler* unrecoverable_error_handler,
 360     bool expect_mobile_bookmarks_folder)
 361     : bookmark_model_(bookmark_model),
 362       profile_(profile),
 363       user_share_(user_share),
 364       unrecoverable_error_handler_(unrecoverable_error_handler),
 365       expect_mobile_bookmarks_folder_(expect_mobile_bookmarks_folder),
 366       optimistic_association_enabled_(IsOptimisticAssociationEnabled()),
 367       weak_factory_(this) {
 368   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 369   DCHECK(bookmark_model_);
 370   DCHECK(user_share_);
 371   DCHECK(unrecoverable_error_handler_);
 372 }
 373
 374 BookmarkModelAssociator::~BookmarkModelAssociator() {
 375   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 376 }
 377
 378 void BookmarkModelAssociator::UpdatePermanentNodeVisibility() {
 379   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 380   DCHECK(bookmark_model_->loaded());
 381
 382   BookmarkNode::Type bookmark_node_types[] = {
 383     BookmarkNode::BOOKMARK_BAR,
 384     BookmarkNode::OTHER_NODE,
 385     BookmarkNode::MOBILE,
 386   };
 387   for (size_t i = 0; i < arraysize(bookmark_node_types); ++i) {
 388     int64 id = bookmark_model_->PermanentNode(bookmark_node_types[i])->id();
 389     bookmark_model_->SetPermanentNodeVisible(
 390       bookmark_node_types[i],
 391       id_map_.find(id) != id_map_.end());
 392   }
 393
 394   // Note: the root node may have additional extra nodes. Currently their
 395   // visibility is not affected by sync.
 396 }
 397
 398 syncer::SyncError BookmarkModelAssociator::DisassociateModels() {
 399   id_map_.clear();
 400   id_map_inverse_.clear();
 401   dirty_associations_sync_ids_.clear();
 402   return syncer::SyncError();
 403 }
 404
 405 int64 BookmarkModelAssociator::GetSyncIdFromChromeId(const int64& node_id) {
 406   BookmarkIdToSyncIdMap::const_iterator iter = id_map_.find(node_id);
 407   return iter == id_map_.end() ? syncer::kInvalidId : iter->second;
 408 }
 409
 410 const BookmarkNode* BookmarkModelAssociator::GetChromeNodeFromSyncId(
 411     int64 sync_id) {
 412   SyncIdToBookmarkNodeMap::const_iterator iter = id_map_inverse_.find(sync_id);
 413   return iter == id_map_inverse_.end() ? NULL : iter->second;
 414 }
 415
 416 bool BookmarkModelAssociator::InitSyncNodeFromChromeId(
 417     const int64& node_id,
 418     syncer::BaseNode* sync_node) {
 419   DCHECK(sync_node);
 420   int64 sync_id = GetSyncIdFromChromeId(node_id);
 421   if (sync_id == syncer::kInvalidId)
 422     return false;
 423   if (sync_node->InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK)
 424     return false;
 425   DCHECK(sync_node->GetId() == sync_id);
 426   return true;
 427 }
 428
 429 void BookmarkModelAssociator::AddAssociation(const BookmarkNode* node,
 430                                              int64 sync_id) {
 431   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 432   int64 node_id = node->id();
 433   DCHECK_NE(sync_id, syncer::kInvalidId);
 434   DCHECK(id_map_.find(node_id) == id_map_.end());
 435   DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end());
 436   id_map_[node_id] = sync_id;
 437   id_map_inverse_[sync_id] = node;
 438 }
 439
 440 void BookmarkModelAssociator::Associate(const BookmarkNode* node,
 441                                         const syncer::BaseNode& sync_node) {
 442   AddAssociation(node, sync_node.GetId());
 443
 444   // TODO(stanisc): crbug.com/456876: consider not doing this on every single
 445   // association.
 446   UpdatePermanentNodeVisibility();
 447
 448   // The same check exists in PersistAssociations. However it is better to
 449   // do the check earlier to avoid the cost of decrypting nodes again
 450   // in PersistAssociations.
 451   if (node->id() != sync_node.GetExternalId()) {
 452     dirty_associations_sync_ids_.insert(sync_node.GetId());
 453     PostPersistAssociationsTask();
 454   }
 455 }
 456
 457 void BookmarkModelAssociator::Disassociate(int64 sync_id) {
 458   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 459   SyncIdToBookmarkNodeMap::iterator iter = id_map_inverse_.find(sync_id);
 460   if (iter == id_map_inverse_.end())
 461     return;
 462   id_map_.erase(iter->second->id());
 463   id_map_inverse_.erase(iter);
 464   dirty_associations_sync_ids_.erase(sync_id);
 465 }
 466
 467 bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 468   DCHECK(has_nodes);
 469   *has_nodes = false;
 470   bool has_mobile_folder = true;
 471
 472   syncer::ReadTransaction trans(FROM_HERE, user_share_);
 473
 474   syncer::ReadNode bookmark_bar_node(&trans);
 475   if (bookmark_bar_node.InitByTagLookupForBookmarks(kBookmarkBarTag) !=
 476       syncer::BaseNode::INIT_OK) {
 477     return false;
 478   }
 479
 480   syncer::ReadNode other_bookmarks_node(&trans);
 481   if (other_bookmarks_node.InitByTagLookupForBookmarks(kOtherBookmarksTag) !=
 482       syncer::BaseNode::INIT_OK) {
 483     return false;
 484   }
 485
 486   syncer::ReadNode mobile_bookmarks_node(&trans);
 487   if (mobile_bookmarks_node.InitByTagLookupForBookmarks(kMobileBookmarksTag) !=
 488       syncer::BaseNode::INIT_OK) {
 489     has_mobile_folder = false;
 490   }
 491
 492   // Sync model has user created nodes if any of the permanent nodes has
 493   // children.
 494   *has_nodes = bookmark_bar_node.HasChildren() ||
 495       other_bookmarks_node.HasChildren() ||
 496       (has_mobile_folder && mobile_bookmarks_node.HasChildren());
 497   return true;
 498 }
 499
 500 bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
 501     syncer::BaseTransaction* trans,
 502     const BookmarkNode* permanent_node,
 503     const std::string& tag) {
 504   // Do nothing if |permanent_node| is already initialized and associated.
 505   int64 sync_id = GetSyncIdFromChromeId(permanent_node->id());
 506   if (sync_id != syncer::kInvalidId)
 507     return true;
 508
 509   syncer::ReadNode sync_node(trans);
 510   if (sync_node.InitByTagLookupForBookmarks(tag) != syncer::BaseNode::INIT_OK)
 511     return false;
 512
 513   Associate(permanent_node, sync_node);
 514   return true;
 515 }
 516
 517 syncer::SyncError BookmarkModelAssociator::AssociateModels(
 518     syncer::SyncMergeResult* local_merge_result,
 519     syncer::SyncMergeResult* syncer_merge_result) {
 520   // Since any changes to the bookmark model made here are not user initiated,
 521   // these change should not be undoable and so suspend the undo tracking.
 522   ScopedSuspendBookmarkUndo suspend_undo(
 523       BookmarkUndoServiceFactory::GetForProfileIfExists(profile_));
 524
 525   Context context(local_merge_result, syncer_merge_result);
 526
 527   syncer::SyncError error = CheckModelSyncState(&context);
 528   if (error.IsSet())
 529     return error;
 530
 531   scoped_ptr<ScopedAssociationUpdater> association_updater(
 532       new ScopedAssociationUpdater(bookmark_model_));
 533   DisassociateModels();
 534
 535   error = BuildAssociations(&context);
 536   if (error.IsSet()) {
 537     // Clear version on bookmark model so that the conservative association
 538     // algorithm is used on the next association.
 539     bookmark_model_->SetNodeSyncTransactionVersion(
 540         bookmark_model_->root_node(),
 541         syncer::syncable::kInvalidTransactionVersion);
 542   }
 543
 544   return error;
 545 }
 546
 547 syncer::SyncError BookmarkModelAssociator::AssociatePermanentFolders(
 548     syncer::BaseTransaction* trans,
 549     Context* context) {
 550   // To prime our association, we associate the top-level nodes, Bookmark Bar
 551   // and Other Bookmarks.
 552   if (!AssociateTaggedPermanentNode(trans, bookmark_model_->bookmark_bar_node(),
 553                                     kBookmarkBarTag)) {
 554     return unrecoverable_error_handler_->CreateAndUploadError(
 555         FROM_HERE, "Bookmark bar node not found", model_type());
 556   }
 557
 558   if (!AssociateTaggedPermanentNode(trans, bookmark_model_->other_node(),
 559                                     kOtherBookmarksTag)) {
 560     return unrecoverable_error_handler_->CreateAndUploadError(
 561         FROM_HERE, "Other bookmarks node not found", model_type());
 562   }
 563
 564   if (!AssociateTaggedPermanentNode(trans, bookmark_model_->mobile_node(),
 565                                     kMobileBookmarksTag) &&
 566       expect_mobile_bookmarks_folder_) {
 567     return unrecoverable_error_handler_->CreateAndUploadError(
 568         FROM_HERE, "Mobile bookmarks node not found", model_type());
 569   }
 570
 571   // Note: the root node may have additional extra nodes. Currently none of
 572   // them are meant to sync.
 573   int64 bookmark_bar_sync_id =
 574       GetSyncIdFromChromeId(bookmark_model_->bookmark_bar_node()->id());
 575   DCHECK_NE(bookmark_bar_sync_id, syncer::kInvalidId);
 576   context->AddBookmarkRoot(bookmark_model_->bookmark_bar_node());
 577   int64 other_bookmarks_sync_id =
 578       GetSyncIdFromChromeId(bookmark_model_->other_node()->id());
 579   DCHECK_NE(other_bookmarks_sync_id, syncer::kInvalidId);
 580   context->AddBookmarkRoot(bookmark_model_->other_node());
 581   int64 mobile_bookmarks_sync_id =
 582       GetSyncIdFromChromeId(bookmark_model_->mobile_node()->id());
 583   if (expect_mobile_bookmarks_folder_)
 584     DCHECK_NE(syncer::kInvalidId, mobile_bookmarks_sync_id);
 585   if (mobile_bookmarks_sync_id != syncer::kInvalidId)
 586     context->AddBookmarkRoot(bookmark_model_->mobile_node());
 587
 588   // WARNING: The order in which we push these should match their order in the
 589   // bookmark model (see BookmarkModel::DoneLoading(..)).
 590   context->PushNode(bookmark_bar_sync_id);
 591   context->PushNode(other_bookmarks_sync_id);
 592   if (mobile_bookmarks_sync_id != syncer::kInvalidId)
 593     context->PushNode(mobile_bookmarks_sync_id);
 594
 595   return syncer::SyncError();
 596 }
 597
 598 void BookmarkModelAssociator::SetNumItemsBeforeAssociation(
 599     syncer::BaseTransaction* trans,
 600     Context* context) {
 601   int syncer_num = 0;
 602   syncer::ReadNode bm_root(trans);
 603   if (bm_root.InitTypeRoot(syncer::BOOKMARKS) == syncer::BaseNode::INIT_OK) {
 604     syncer_num = bm_root.GetTotalNodeCount();
 605   }
 606   context->SetNumItemsBeforeAssociation(
 607       GetTotalBookmarkCountAndRecordDuplicates(bookmark_model_->root_node(),
 608                                                context),
 609       syncer_num);
 610 }
 611
 612 int BookmarkModelAssociator::GetTotalBookmarkCountAndRecordDuplicates(
 613     const bookmarks::BookmarkNode* node,
 614     Context* context) const {
 615   int count = 1;  // Start with one to include the node itself.
 616
 617   if (!node->is_root()) {
 618     context->UpdateDuplicateCount(node->GetTitle(), node->url());
 619   }
 620
 621   for (int i = 0; i < node->child_count(); ++i) {
 622     count +=
 623         GetTotalBookmarkCountAndRecordDuplicates(node->GetChild(i), context);
 624   }
 625
 626   return count;
 627 }
 628
 629 void BookmarkModelAssociator::SetNumItemsAfterAssociation(
 630     syncer::BaseTransaction* trans,
 631     Context* context) {
 632   int syncer_num = 0;
 633   syncer::ReadNode bm_root(trans);
 634   if (bm_root.InitTypeRoot(syncer::BOOKMARKS) == syncer::BaseNode::INIT_OK) {
 635     syncer_num = bm_root.GetTotalNodeCount();
 636   }
 637   context->SetNumItemsAfterAssociation(
 638       bookmark_model_->root_node()->GetTotalNodeCount(), syncer_num);
 639 }
 640
 641 syncer::SyncError BookmarkModelAssociator::BuildAssociations(Context* context) {
 642   DCHECK(bookmark_model_->loaded());
 643   DCHECK_NE(context->native_model_sync_state(), AHEAD);
 644
 645   int initial_duplicate_count = 0;
 646   int64 new_version = syncer::syncable::kInvalidTransactionVersion;
 647   {
 648     syncer::WriteTransaction trans(FROM_HERE, user_share_, &new_version);
 649
 650     syncer::SyncError error = AssociatePermanentFolders(&trans, context);
 651     if (error.IsSet())
 652       return error;
 653
 654     SetNumItemsBeforeAssociation(&trans, context);
 655     initial_duplicate_count = context->duplicate_count();
 656
 657     // Remove obsolete bookmarks according to sync delete journal.
 658     // TODO(stanisc): crbug.com/456876: rewrite this to avoid a separate
 659     // traversal and instead perform deletes at the end of the loop below where
 660     // the unmatched bookmark nodes are created as sync nodes.
 661     ApplyDeletesFromSyncJournal(&trans, context);
 662
 663     // Algorithm description:
 664     // Match up the roots and recursively do the following:
 665     // * For each sync node for the current sync parent node, find the best
 666     //   matching bookmark node under the corresponding bookmark parent node.
 667     //   If no matching node is found, create a new bookmark node in the same
 668     //   position as the corresponding sync node.
 669     //   If a matching node is found, update the properties of it from the
 670     //   corresponding sync node.
 671     // * When all children sync nodes are done, add the extra children bookmark
 672     //   nodes to the sync parent node.
 673     //
 674     // The best match algorithm uses folder title or bookmark title/url to
 675     // perform the primary match. If there are multiple match candidates it
 676     // selects the preferred one based on sync node external ID match to the
 677     // bookmark folder ID.
 678     int64 sync_parent_id;
 679     while (context->PopNode(&sync_parent_id)) {
 680       syncer::ReadNode sync_parent(&trans);
 681       if (sync_parent.InitByIdLookup(sync_parent_id) !=
 682           syncer::BaseNode::INIT_OK) {
 683         return unrecoverable_error_handler_->CreateAndUploadError(
 684             FROM_HERE, "Failed to lookup node.", model_type());
 685       }
 686       // Only folder nodes are pushed on to the stack.
 687       DCHECK(sync_parent.GetIsFolder());
 688
 689       const BookmarkNode* parent_node = GetChromeNodeFromSyncId(sync_parent_id);
 690       if (!parent_node) {
 691         return unrecoverable_error_handler_->CreateAndUploadError(
 692             FROM_HERE, "Failed to find bookmark node for sync id.",
 693             model_type());
 694       }
 695       DCHECK(parent_node->is_folder());
 696
 697       std::vector<int64> children;
 698       sync_parent.GetChildIds(&children);
 699
 700       if (optimistic_association_enabled_ &&
 701           context->native_model_sync_state() == IN_SYNC) {
 702         // Optimistic case where based on the version check there shouldn't
 703         // be any new sync changes.
 704         error =
 705             BuildAssociationsOptimistic(&trans, parent_node, children, context);
 706       } else {
 707         error = BuildAssociations(&trans, parent_node, children, context);
 708       }
 709       if (error.IsSet())
 710         return error;
 711     }
 712
 713     SetNumItemsAfterAssociation(&trans, context);
 714   }
 715
 716   BookmarkChangeProcessor::UpdateTransactionVersion(
 717       new_version, bookmark_model_, context->bookmarks_for_version_update());
 718
 719   UMA_HISTOGRAM_COUNTS("Sync.BookmarksDuplicationsAtAssociation",
 720                        context->duplicate_count());
 721   UMA_HISTOGRAM_COUNTS("Sync.BookmarksNewDuplicationsAtAssociation",
 722                        context->duplicate_count() - initial_duplicate_count);
 723
 724   if (context->duplicate_count() > initial_duplicate_count) {
 725     UMA_HISTOGRAM_ENUMERATION("Sync.BookmarksModelSyncStateAtNewDuplication",
 726                               context->native_model_sync_state(),
 727                               NATIVE_MODEL_SYNC_STATE_COUNT);
 728   }
 729
 730   return syncer::SyncError();
 731 }
 732
 733 syncer::SyncError BookmarkModelAssociator::BuildAssociations(
 734     syncer::WriteTransaction* trans,
 735     const BookmarkNode* parent_node,
 736     const std::vector<int64>& sync_ids,
 737     Context* context) {
 738   BookmarkNodeFinder node_finder(parent_node);
 739
 740   int index = 0;
 741   for (std::vector<int64>::const_iterator it = sync_ids.begin();
 742        it != sync_ids.end(); ++it) {
 743     int64 sync_child_id = *it;
 744     syncer::ReadNode sync_child_node(trans);
 745     if (sync_child_node.InitByIdLookup(sync_child_id) !=
 746         syncer::BaseNode::INIT_OK) {
 747       return unrecoverable_error_handler_->CreateAndUploadError(
 748           FROM_HERE, "Failed to lookup node.", model_type());
 749     }
 750
 751     GURL url(sync_child_node.GetBookmarkSpecifics().url());
 752     const BookmarkNode* child_node = node_finder.FindBookmarkNode(
 753         url, sync_child_node.GetTitle(), sync_child_node.GetIsFolder(),
 754         sync_child_node.GetExternalId());
 755     if (child_node) {
 756       // All bookmarks are currently modified at association time, even if
 757       // nothing has changed.
 758       // TODO(sync): Only modify the bookmark model if necessary.
 759       BookmarkChangeProcessor::UpdateBookmarkWithSyncData(
 760           sync_child_node, bookmark_model_, child_node, profile_);
 761       bookmark_model_->Move(child_node, parent_node, index);
 762       context->IncrementLocalItemsModified();
 763     } else {
 764       syncer::SyncError error;
 765       child_node = CreateBookmarkNode(parent_node, index, &sync_child_node, url,
 766                                       context, &error);
 767       if (!child_node) {
 768         if (error.IsSet()) {
 769           return error;
 770         } else {
 771           // Skip this node and continue. Don't increment index in this case.
 772           continue;
 773         }
 774       }
 775       context->IncrementLocalItemsAdded();
 776     }
 777
 778     Associate(child_node, sync_child_node);
 779     // All bookmarks are marked for version update because
 780     // all bookmarks are always updated with data. This could be optimized -
 781     // see the note above.
 782     context->MarkForVersionUpdate(child_node);
 783
 784     if (sync_child_node.GetIsFolder())
 785       context->PushNode(sync_child_id);
 786     ++index;
 787   }
 788
 789   // At this point all the children nodes of the parent sync node have
 790   // corresponding children in the parent bookmark node and they are all in
 791   // the right positions: from 0 to index - 1.
 792   // So the children starting from index in the parent bookmark node are the
 793   // ones that are not present in the parent sync node. So create them.
 794   for (int i = index; i < parent_node->child_count(); ++i) {
 795     int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
 796         parent_node, bookmark_model_, i, trans, this,
 797         unrecoverable_error_handler_);
 798     if (syncer::kInvalidId == sync_child_id) {
 799       return unrecoverable_error_handler_->CreateAndUploadError(
 800           FROM_HERE, "Failed to create sync node.", model_type());
 801     }
 802
 803     context->IncrementSyncItemsAdded();
 804     const BookmarkNode* child_node = parent_node->GetChild(i);
 805     context->MarkForVersionUpdate(child_node);
 806     if (child_node->is_folder())
 807       context->PushNode(sync_child_id);
 808   }
 809
 810   return syncer::SyncError();
 811 }
 812
 813 syncer::SyncError BookmarkModelAssociator::BuildAssociationsOptimistic(
 814     syncer::WriteTransaction* trans,
 815     const BookmarkNode* parent_node,
 816     const std::vector<int64>& sync_ids,
 817     Context* context) {
 818   BookmarkNodeFinder node_finder(parent_node);
 819
 820   // TODO(stanisc): crbug/456876: Review optimistic case specific logic here.
 821   // This is the case when the transcation version of the native model
 822   // matches the transaction version on the sync side.
 823   // For now the logic is exactly the same as for the regular case with
 824   // the exception of not propagating sync data for matching nodes.
 825   int index = 0;
 826   for (std::vector<int64>::const_iterator it = sync_ids.begin();
 827        it != sync_ids.end(); ++it) {
 828     int64 sync_child_id = *it;
 829     syncer::ReadNode sync_child_node(trans);
 830     if (sync_child_node.InitByIdLookup(sync_child_id) !=
 831         syncer::BaseNode::INIT_OK) {
 832       return unrecoverable_error_handler_->CreateAndUploadError(
 833           FROM_HERE, "Failed to lookup node.", model_type());
 834     }
 835
 836     int64 external_id = sync_child_node.GetExternalId();
 837     GURL url(sync_child_node.GetBookmarkSpecifics().url());
 838     const BookmarkNode* child_node = node_finder.FindBookmarkNode(
 839         url, sync_child_node.GetTitle(), sync_child_node.GetIsFolder(),
 840         external_id);
 841     if (child_node) {
 842       // If the child node is matched assume it is in sync and skip
 843       // propagated data.
 844       // TODO(stanisc): crbug/456876: Replace the code that moves
 845       // the local node with the sync node reordering code.
 846       // The local node has the correct position in this particular case,
 847       // not the sync node.
 848       if (parent_node->GetChild(index) != child_node) {
 849         bookmark_model_->Move(child_node, parent_node, index);
 850         context->IncrementLocalItemsModified();
 851       }
 852     } else {
 853       if (external_id != 0) {
 854         const BookmarkNode* matching_node =
 855             context->LookupNodeInIdIndex(external_id);
 856         if (matching_node) {
 857           // There is another matching node which means the local node
 858           // has been either moved or edited.
 859           // In this case assume the local model to be correct, delete the
 860           // sync node, and let the matching node to be propagated to Sync.
 861           // TODO(stanisc): crbug/456876: this should really be handled with
 862           // a move, but the move depends on the traversal order.
 863           int num = RemoveSyncNodeHierarchy(trans, sync_child_node.GetId());
 864           context->IncrementSyncItemsDeleted(num);
 865           continue;
 866         }
 867       } else {
 868         // Existing sync node isn't associated. This is unexpected during
 869         // optimistic association unless there the previous association failed
 870         // to
 871         // persist extern IDs (that might be the case because persisting
 872         // external
 873         // IDs is delayed).
 874         // Report this error only once per session.
 875         static bool g_unmatched_unassociated_node_reported = false;
 876         if (!g_unmatched_unassociated_node_reported) {
 877           g_unmatched_unassociated_node_reported = true;
 878           unrecoverable_error_handler_->CreateAndUploadError(
 879               FROM_HERE,
 880               "Unassociated sync node detected during optimistic association",
 881               model_type());
 882         }
 883       }
 884
 885       syncer::SyncError error;
 886       child_node = CreateBookmarkNode(parent_node, index, &sync_child_node, url,
 887                                       context, &error);
 888       if (!child_node) {
 889         if (error.IsSet()) {
 890           return error;
 891         } else {
 892           // Skip this node and continue. Don't increment index in this case.
 893           continue;
 894         }
 895       }
 896       context->IncrementLocalItemsAdded();
 897       context->MarkForVersionUpdate(child_node);
 898     }
 899
 900     Associate(child_node, sync_child_node);
 901
 902     if (sync_child_node.GetIsFolder())
 903       context->PushNode(sync_child_id);
 904     ++index;
 905   }
 906
 907   // At this point all the children nodes of the parent sync node have
 908   // corresponding children in the parent bookmark node and they are all in
 909   // the right positions: from 0 to index - 1.
 910   // So the children starting from index in the parent bookmark node are the
 911   // ones that are not present in the parent sync node. So create them.
 912   for (int i = index; i < parent_node->child_count(); ++i) {
 913     int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
 914         parent_node, bookmark_model_, i, trans, this,
 915         unrecoverable_error_handler_);
 916     if (syncer::kInvalidId == sync_child_id) {
 917       return unrecoverable_error_handler_->CreateAndUploadError(
 918           FROM_HERE, "Failed to create sync node.", model_type());
 919     }
 920     context->IncrementSyncItemsAdded();
 921     const BookmarkNode* child_node = parent_node->GetChild(i);
 922     context->MarkForVersionUpdate(child_node);
 923     if (child_node->is_folder())
 924       context->PushNode(sync_child_id);
 925   }
 926
 927   return syncer::SyncError();
 928 }
 929
 930 const BookmarkNode* BookmarkModelAssociator::CreateBookmarkNode(
 931     const BookmarkNode* parent_node,
 932     int bookmark_index,
 933     const syncer::BaseNode* sync_child_node,
 934     const GURL& url,
 935     Context* context,
 936     syncer::SyncError* error) {
 937   DCHECK_LE(bookmark_index, parent_node->child_count());
 938
 939   const std::string& sync_title = sync_child_node->GetTitle();
 940
 941   if (!sync_child_node->GetIsFolder() && !url.is_valid()) {
 942     unrecoverable_error_handler_->CreateAndUploadError(
 943         FROM_HERE, "Cannot associate sync node " +
 944                        sync_child_node->GetEntry()->GetId().value() +
 945                        " with invalid url " + url.possibly_invalid_spec() +
 946                        " and title " + sync_title,
 947         model_type());
 948     // Don't propagate the error to the model_type in this case.
 949     return nullptr;
 950   }
 951
 952   base::string16 bookmark_title = base::UTF8ToUTF16(sync_title);
 953   const BookmarkNode* child_node = BookmarkChangeProcessor::CreateBookmarkNode(
 954       bookmark_title, url, sync_child_node, parent_node, bookmark_model_,
 955       profile_, bookmark_index);
 956   if (!child_node) {
 957     *error = unrecoverable_error_handler_->CreateAndUploadError(
 958         FROM_HERE, "Failed to create bookmark node with title " + sync_title +
 959                        " and url " + url.possibly_invalid_spec(),
 960         model_type());
 961     return nullptr;
 962   }
 963
 964   context->UpdateDuplicateCount(bookmark_title, url);
 965   return child_node;
 966 }
 967
 968 int BookmarkModelAssociator::RemoveSyncNodeHierarchy(
 969     syncer::WriteTransaction* trans,
 970     int64 sync_id) {
 971   syncer::WriteNode sync_node(trans);
 972   if (sync_node.InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK) {
 973     syncer::SyncError error(FROM_HERE, syncer::SyncError::DATATYPE_ERROR,
 974                             "Could not lookup bookmark node for ID deletion.",
 975                             syncer::BOOKMARKS);
 976     unrecoverable_error_handler_->OnSingleDataTypeUnrecoverableError(error);
 977     return 0;
 978   }
 979
 980   return BookmarkChangeProcessor::RemoveSyncNodeHierarchy(trans, &sync_node,
 981                                                           this);
 982 }
 983
 984 struct FolderInfo {
 985   FolderInfo(const BookmarkNode* f, const BookmarkNode* p, int64 id)
 986       : folder(f), parent(p), sync_id(id) {}
 987   const BookmarkNode* folder;
 988   const BookmarkNode* parent;
 989   int64 sync_id;
 990 };
 991 typedef std::vector<FolderInfo> FolderInfoList;
 992
 993 void BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
 994     syncer::BaseTransaction* trans,
 995     Context* context) {
 996   syncer::BookmarkDeleteJournalList bk_delete_journals;
 997   syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
 998   if (bk_delete_journals.empty())
 999     return;
1000
1001   size_t num_journals_unmatched = bk_delete_journals.size();
1002
1003   // Make a set of all external IDs in the delete journal,
1004   // ignore entries with unset external IDs.
1005   std::set<int64> journaled_external_ids;
1006   for (size_t i = 0; i < num_journals_unmatched; i++) {
1007     if (bk_delete_journals[i].external_id != 0)
1008       journaled_external_ids.insert(bk_delete_journals[i].external_id);
1009   }
1010
1011   // Check bookmark model from top to bottom.
1012   BookmarkStack dfs_stack;
1013   for (BookmarkList::const_iterator it = context->bookmark_roots().begin();
1014        it != context->bookmark_roots().end(); ++it) {
1015     dfs_stack.push(*it);
1016   }
1017
1018   // Remember folders that match delete journals in first pass but don't delete
1019   // them in case there are bookmarks left under them. After non-folder
1020   // bookmarks are removed in first pass, recheck the folders in reverse order
1021   // to remove empty ones.
1022   FolderInfoList folders_matched;
1023   while (!dfs_stack.empty() && num_journals_unmatched > 0) {
1024     const BookmarkNode* parent = dfs_stack.top();
1025     dfs_stack.pop();
1026     DCHECK(parent->is_folder());
1027
1028     // Enumerate folder children in reverse order to make it easier to remove
1029     // bookmarks matching entries in the delete journal.
1030     for (int child_index = parent->child_count() - 1;
1031          child_index >= 0 && num_journals_unmatched > 0; --child_index) {
1032       const BookmarkNode* child = parent->GetChild(child_index);
1033       if (child->is_folder())
1034         dfs_stack.push(child);
1035
1036       if (journaled_external_ids.find(child->id()) ==
1037           journaled_external_ids.end()) {
1038         // Skip bookmark node which id is not in the set of external IDs.
1039         continue;
1040       }
1041
1042       // Iterate through the journal entries from back to front. Remove matched
1043       // journal by moving an unmatched entry at the tail to the matched
1044       // position so that we can read unmatched entries off the head in next
1045       // loop.
1046       for (int journal_index = num_journals_unmatched - 1; journal_index >= 0;
1047            --journal_index) {
1048         const syncer::BookmarkDeleteJournal& delete_entry =
1049             bk_delete_journals[journal_index];
1050         if (child->id() == delete_entry.external_id &&
1051             BookmarkNodeFinder::NodeMatches(
1052                 child, GURL(delete_entry.specifics.bookmark().url()),
1053                 delete_entry.specifics.bookmark().title(),
1054                 delete_entry.is_folder)) {
1055           if (child->is_folder()) {
1056             // Remember matched folder without removing and delete only empty
1057             // ones later.
1058             folders_matched.push_back(
1059                 FolderInfo(child, parent, delete_entry.id));
1060           } else {
1061             bookmark_model_->Remove(child);
1062             context->IncrementLocalItemsDeleted();
1063           }
1064           // Move unmatched journal here and decrement counter.
1065           bk_delete_journals[journal_index] =
1066               bk_delete_journals[--num_journals_unmatched];
1067           break;
1068         }
1069       }
1070     }
1071   }
1072
1073   // Ids of sync nodes not found in bookmark model, meaning the deletions are
1074   // persisted and correponding delete journals can be dropped.
1075   std::set<int64> journals_to_purge;
1076
1077   // Remove empty folders from bottom to top.
1078   for (FolderInfoList::reverse_iterator it = folders_matched.rbegin();
1079       it != folders_matched.rend(); ++it) {
1080     if (it->folder->child_count() == 0) {
1081       bookmark_model_->Remove(it->folder);
1082       context->IncrementLocalItemsDeleted();
1083     } else {
1084       // Keep non-empty folder and remove its journal so that it won't match
1085       // again in the future.
1086       journals_to_purge.insert(it->sync_id);
1087     }
1088   }
1089
1090   // Purge unmatched journals.
1091   for (size_t i = 0; i < num_journals_unmatched; ++i)
1092     journals_to_purge.insert(bk_delete_journals[i].id);
1093   syncer::DeleteJournal::PurgeDeleteJournals(trans, journals_to_purge);
1094 }
1095
1096 void BookmarkModelAssociator::PostPersistAssociationsTask() {
1097   // No need to post a task if a task is already pending.
1098   if (weak_factory_.HasWeakPtrs())
1099     return;
1100   base::ThreadTaskRunnerHandle::Get()->PostTask(
1101       FROM_HERE, base::Bind(&BookmarkModelAssociator::PersistAssociations,
1102                             weak_factory_.GetWeakPtr()));
1103 }
1104
1105 void BookmarkModelAssociator::PersistAssociations() {
1106   // If there are no dirty associations we have nothing to do. We handle this
1107   // explicity instead of letting the for loop do it to avoid creating a write
1108   // transaction in this case.
1109   if (dirty_associations_sync_ids_.empty()) {
1110     DCHECK(id_map_.empty());
1111     DCHECK(id_map_inverse_.empty());
1112     return;
1113   }
1114
1115   int64 new_version = syncer::syncable::kInvalidTransactionVersion;
1116   std::vector<const BookmarkNode*> bnodes;
1117   {
1118     syncer::WriteTransaction trans(FROM_HERE, user_share_, &new_version);
1119     DirtyAssociationsSyncIds::iterator iter;
1120     for (iter = dirty_associations_sync_ids_.begin();
1121          iter != dirty_associations_sync_ids_.end();
1122          ++iter) {
1123       int64 sync_id = *iter;
1124       syncer::WriteNode sync_node(&trans);
1125       if (sync_node.InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK) {
1126         syncer::SyncError error(
1127             FROM_HERE,
1128             syncer::SyncError::DATATYPE_ERROR,
1129             "Could not lookup bookmark node for ID persistence.",
1130             syncer::BOOKMARKS);
1131         unrecoverable_error_handler_->OnSingleDataTypeUnrecoverableError(error);
1132         return;
1133       }
1134       const BookmarkNode* node = GetChromeNodeFromSyncId(sync_id);
1135       if (node && sync_node.GetExternalId() != node->id()) {
1136         sync_node.SetExternalId(node->id());
1137         bnodes.push_back(node);
1138       }
1139     }
1140     dirty_associations_sync_ids_.clear();
1141   }
1142
1143   BookmarkChangeProcessor::UpdateTransactionVersion(new_version,
1144                                                     bookmark_model_,
1145                                                     bnodes);
1146 }
1147
1148 bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
1149   // We only access the cryptographer while holding a transaction.
1150   syncer::ReadTransaction trans(FROM_HERE, user_share_);
1151   const syncer::ModelTypeSet encrypted_types = trans.GetEncryptedTypes();
1152   return !encrypted_types.Has(syncer::BOOKMARKS) ||
1153       trans.GetCryptographer()->is_ready();
1154 }
1155
1156 syncer::SyncError BookmarkModelAssociator::CheckModelSyncState(
1157     Context* context) const {
1158   DCHECK_EQ(context->native_model_sync_state(), UNSET);
1159   int64 native_version =
1160       bookmark_model_->root_node()->sync_transaction_version();
1161   if (native_version != syncer::syncable::kInvalidTransactionVersion) {
1162     syncer::ReadTransaction trans(FROM_HERE, user_share_);
1163     int64 sync_version = trans.GetModelVersion(syncer::BOOKMARKS);
1164     context->SetPreAssociationVersions(native_version, sync_version);
1165
1166     if (native_version == sync_version) {
1167       context->set_native_model_sync_state(IN_SYNC);
1168     } else {
1169       UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
1170                                 ModelTypeToHistogramInt(syncer::BOOKMARKS),
1171                                 syncer::MODEL_TYPE_COUNT);
1172
1173       // Clear version on bookmark model so that we only report error once.
1174       bookmark_model_->SetNodeSyncTransactionVersion(
1175           bookmark_model_->root_node(),
1176           syncer::syncable::kInvalidTransactionVersion);
1177
1178       // If the native version is higher, there was a sync persistence failure,
1179       // and we need to delay association until after a GetUpdates.
1180       if (native_version > sync_version) {
1181         context->set_native_model_sync_state(AHEAD);
1182         std::string message = base::StringPrintf(
1183             "Native version (%" PRId64 ") does not match sync version (%"
1184                 PRId64 ")",
1185             native_version,
1186             sync_version);
1187         return syncer::SyncError(FROM_HERE,
1188                                  syncer::SyncError::PERSISTENCE_ERROR,
1189                                  message,
1190                                  syncer::BOOKMARKS);
1191       } else {
1192         context->set_native_model_sync_state(BEHIND);
1193       }
1194     }
1195   }
1196   return syncer::SyncError();
1197 }
1198
1199 }  // namespace browser_sync