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