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 <stack>
   8
   9 #include "base/bind.h"
  10 #include "base/command_line.h"
  11 #include "base/containers/hash_tables.h"
  12 #include "base/format_macros.h"
  13 #include "base/location.h"
  14 #include "base/message_loop/message_loop.h"
  15 #include "base/strings/string_number_conversions.h"
  16 #include "base/strings/stringprintf.h"
  17 #include "base/strings/utf_string_conversions.h"
  18 #include "chrome/browser/bookmarks/bookmark_model.h"
  19 #include "chrome/browser/profiles/profile.h"
  20 #include "chrome/browser/sync/glue/bookmark_change_processor.h"
  21 #include "chrome/browser/undo/bookmark_undo_service.h"
  22 #include "chrome/browser/undo/bookmark_undo_service_factory.h"
  23 #include "chrome/browser/undo/undo_manager_utils.h"
  24 #include "content/public/browser/browser_thread.h"
  25 #include "sync/api/sync_error.h"
  26 #include "sync/internal_api/public/delete_journal.h"
  27 #include "sync/internal_api/public/read_node.h"
  28 #include "sync/internal_api/public/read_transaction.h"
  29 #include "sync/internal_api/public/write_node.h"
  30 #include "sync/internal_api/public/write_transaction.h"
  31 #include "sync/syncable/syncable_write_transaction.h"
  32 #include "sync/util/cryptographer.h"
  33 #include "sync/util/data_type_histogram.h"
  34
  35 using content::BrowserThread;
  36
  37 namespace browser_sync {
  38
  39 // The sync protocol identifies top-level entities by means of well-known tags,
  40 // which should not be confused with titles.  Each tag corresponds to a
  41 // singleton instance of a particular top-level node in a user's share; the
  42 // tags are consistent across users. The tags allow us to locate the specific
  43 // folders whose contents we care about synchronizing, without having to do a
  44 // lookup by name or path.  The tags should not be made user-visible.
  45 // For example, the tag "bookmark_bar" represents the permanent node for
  46 // bookmarks bar in Chrome. The tag "other_bookmarks" represents the permanent
  47 // folder Other Bookmarks in Chrome.
  48 //
  49 // It is the responsibility of something upstream (at time of writing,
  50 // the sync server) to create these tagged nodes when initializing sync
  51 // for the first time for a user.  Thus, once the backend finishes
  52 // initializing, the ProfileSyncService can rely on the presence of tagged
  53 // nodes.
  54 //
  55 // TODO(ncarter): Pull these tags from an external protocol specification
  56 // rather than hardcoding them here.
  57 const char kBookmarkBarTag[] = "bookmark_bar";
  58 const char kMobileBookmarksTag[] = "synced_bookmarks";
  59 const char kOtherBookmarksTag[] = "other_bookmarks";
  60
  61 // Bookmark comparer for map of bookmark nodes.
  62 class BookmarkComparer {
  63  public:
  64   // Compares the two given nodes and returns whether node1 should appear
  65   // before node2 in strict weak ordering.
  66   bool operator()(const BookmarkNode* node1,
  67                   const BookmarkNode* node2) const {
  68     DCHECK(node1);
  69     DCHECK(node2);
  70
  71     // Keep folder nodes before non-folder nodes.
  72     if (node1->is_folder() != node2->is_folder())
  73       return node1->is_folder();
  74
  75     int result = node1->GetTitle().compare(node2->GetTitle());
  76     if (result != 0)
  77       return result < 0;
  78
  79     return node1->url() < node2->url();
  80   }
  81 };
  82
  83 // Provides the following abstraction: given a parent bookmark node, find best
  84 // matching child node for many sync nodes.
  85 class BookmarkNodeFinder {
  86  public:
  87   // Creates an instance with the given parent bookmark node.
  88   explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
  89
  90   // Finds the bookmark node that matches the given url, title and folder
  91   // attribute. Returns the matching node if one exists; NULL otherwise. If a
  92   // 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
  97  private:
  98   typedef std::multiset<const BookmarkNode*, BookmarkComparer> BookmarkNodesSet;
  99
 100   const BookmarkNode* parent_node_;
 101   BookmarkNodesSet child_nodes_;
 102
 103   DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
 104 };
 105
 106 class ScopedAssociationUpdater {
 107  public:
 108   explicit ScopedAssociationUpdater(BookmarkModel* model) {
 109     model_ = model;
 110     model->BeginExtensiveChanges();
 111   }
 112
 113   ~ScopedAssociationUpdater() {
 114     model_->EndExtensiveChanges();
 115   }
 116
 117  private:
 118   BookmarkModel* model_;
 119
 120   DISALLOW_COPY_AND_ASSIGN(ScopedAssociationUpdater);
 121 };
 122
 123 BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node)
 124     : parent_node_(parent_node) {
 125   for (int i = 0; i < parent_node_->child_count(); ++i) {
 126     child_nodes_.insert(parent_node_->GetChild(i));
 127   }
 128 }
 129
 130 const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
 131     const GURL& url, const std::string& title, bool is_folder) {
 132   // Create a bookmark node from the given bookmark attributes.
 133   BookmarkNode temp_node(url);
 134   temp_node.SetTitle(base::UTF8ToUTF16(title));
 135   if (is_folder)
 136     temp_node.set_type(BookmarkNode::FOLDER);
 137   else
 138     temp_node.set_type(BookmarkNode::URL);
 139
 140   const BookmarkNode* result = NULL;
 141   BookmarkNodesSet::iterator iter = child_nodes_.find(&temp_node);
 142   if (iter != child_nodes_.end()) {
 143     result = *iter;
 144     // Remove the matched node so we don't match with it again.
 145     child_nodes_.erase(iter);
 146   }
 147
 148   return result;
 149 }
 150
 151 // Helper class to build an index of bookmark nodes by their IDs.
 152 class BookmarkNodeIdIndex {
 153  public:
 154   BookmarkNodeIdIndex() { }
 155   ~BookmarkNodeIdIndex() { }
 156
 157   // Adds the given bookmark node and all its descendants to the ID index.
 158   // Does nothing if node is NULL.
 159   void AddAll(const BookmarkNode* node);
 160
 161   // Finds the bookmark node with the given ID.
 162   // Returns NULL if none exists with the given id.
 163   const BookmarkNode* Find(int64 id) const;
 164
 165   // Returns the count of nodes in the index.
 166   size_t count() const { return node_index_.size(); }
 167
 168  private:
 169   typedef base::hash_map<int64, const BookmarkNode*> BookmarkIdMap;
 170   // Map that holds nodes indexed by their ids.
 171   BookmarkIdMap node_index_;
 172
 173   DISALLOW_COPY_AND_ASSIGN(BookmarkNodeIdIndex);
 174 };
 175
 176 void BookmarkNodeIdIndex::AddAll(const BookmarkNode* node) {
 177   if (!node)
 178     return;
 179
 180   node_index_[node->id()] = node;
 181
 182   if (!node->is_folder())
 183     return;
 184
 185   for (int i = 0; i < node->child_count(); ++i)
 186     AddAll(node->GetChild(i));
 187 }
 188
 189 const BookmarkNode* BookmarkNodeIdIndex::Find(int64 id) const {
 190   BookmarkIdMap::const_iterator iter = node_index_.find(id);
 191   return iter == node_index_.end() ? NULL : iter->second;
 192 }
 193
 194 BookmarkModelAssociator::BookmarkModelAssociator(
 195     BookmarkModel* bookmark_model,
 196     Profile* profile,
 197     syncer::UserShare* user_share,
 198     DataTypeErrorHandler* unrecoverable_error_handler,
 199     bool expect_mobile_bookmarks_folder)
 200     : bookmark_model_(bookmark_model),
 201       profile_(profile),
 202       user_share_(user_share),
 203       unrecoverable_error_handler_(unrecoverable_error_handler),
 204       expect_mobile_bookmarks_folder_(expect_mobile_bookmarks_folder),
 205       weak_factory_(this) {
 206   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 207   DCHECK(bookmark_model_);
 208   DCHECK(user_share_);
 209   DCHECK(unrecoverable_error_handler_);
 210 }
 211
 212 BookmarkModelAssociator::~BookmarkModelAssociator() {
 213   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 214 }
 215
 216 void BookmarkModelAssociator::UpdatePermanentNodeVisibility() {
 217   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 218   DCHECK(bookmark_model_->loaded());
 219
 220   bookmark_model_->SetPermanentNodeVisible(
 221       BookmarkNode::MOBILE,
 222       id_map_.find(bookmark_model_->mobile_node()->id()) != id_map_.end());
 223 }
 224
 225 syncer::SyncError BookmarkModelAssociator::DisassociateModels() {
 226   id_map_.clear();
 227   id_map_inverse_.clear();
 228   dirty_associations_sync_ids_.clear();
 229   return syncer::SyncError();
 230 }
 231
 232 int64 BookmarkModelAssociator::GetSyncIdFromChromeId(const int64& node_id) {
 233   BookmarkIdToSyncIdMap::const_iterator iter = id_map_.find(node_id);
 234   return iter == id_map_.end() ? syncer::kInvalidId : iter->second;
 235 }
 236
 237 const BookmarkNode* BookmarkModelAssociator::GetChromeNodeFromSyncId(
 238     int64 sync_id) {
 239   SyncIdToBookmarkNodeMap::const_iterator iter = id_map_inverse_.find(sync_id);
 240   return iter == id_map_inverse_.end() ? NULL : iter->second;
 241 }
 242
 243 bool BookmarkModelAssociator::InitSyncNodeFromChromeId(
 244     const int64& node_id,
 245     syncer::BaseNode* sync_node) {
 246   DCHECK(sync_node);
 247   int64 sync_id = GetSyncIdFromChromeId(node_id);
 248   if (sync_id == syncer::kInvalidId)
 249     return false;
 250   if (sync_node->InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK)
 251     return false;
 252   DCHECK(sync_node->GetId() == sync_id);
 253   return true;
 254 }
 255
 256 void BookmarkModelAssociator::Associate(const BookmarkNode* node,
 257                                         int64 sync_id) {
 258   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 259   int64 node_id = node->id();
 260   DCHECK_NE(sync_id, syncer::kInvalidId);
 261   DCHECK(id_map_.find(node_id) == id_map_.end());
 262   DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end());
 263   id_map_[node_id] = sync_id;
 264   id_map_inverse_[sync_id] = node;
 265   dirty_associations_sync_ids_.insert(sync_id);
 266   PostPersistAssociationsTask();
 267   UpdatePermanentNodeVisibility();
 268 }
 269
 270 void BookmarkModelAssociator::Disassociate(int64 sync_id) {
 271   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 272   SyncIdToBookmarkNodeMap::iterator iter = id_map_inverse_.find(sync_id);
 273   if (iter == id_map_inverse_.end())
 274     return;
 275   id_map_.erase(iter->second->id());
 276   id_map_inverse_.erase(iter);
 277   dirty_associations_sync_ids_.erase(sync_id);
 278 }
 279
 280 bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 281   DCHECK(has_nodes);
 282   *has_nodes = false;
 283   bool has_mobile_folder = true;
 284   int64 bookmark_bar_sync_id;
 285   if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_sync_id)) {
 286     return false;
 287   }
 288   int64 other_bookmarks_sync_id;
 289   if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_sync_id)) {
 290     return false;
 291   }
 292   int64 mobile_bookmarks_sync_id;
 293   if (!GetSyncIdForTaggedNode(kMobileBookmarksTag, &mobile_bookmarks_sync_id)) {
 294     has_mobile_folder = false;
 295   }
 296
 297   syncer::ReadTransaction trans(FROM_HERE, user_share_);
 298
 299   syncer::ReadNode bookmark_bar_node(&trans);
 300   if (bookmark_bar_node.InitByIdLookup(bookmark_bar_sync_id) !=
 301           syncer::BaseNode::INIT_OK) {
 302     return false;
 303   }
 304
 305   syncer::ReadNode other_bookmarks_node(&trans);
 306   if (other_bookmarks_node.InitByIdLookup(other_bookmarks_sync_id) !=
 307           syncer::BaseNode::INIT_OK) {
 308     return false;
 309   }
 310
 311   syncer::ReadNode mobile_bookmarks_node(&trans);
 312   if (has_mobile_folder &&
 313       mobile_bookmarks_node.InitByIdLookup(mobile_bookmarks_sync_id) !=
 314           syncer::BaseNode::INIT_OK) {
 315     return false;
 316   }
 317
 318   // Sync model has user created nodes if any of the permanent nodes has
 319   // children.
 320   *has_nodes = bookmark_bar_node.HasChildren() ||
 321       other_bookmarks_node.HasChildren() ||
 322       (has_mobile_folder && mobile_bookmarks_node.HasChildren());
 323   return true;
 324 }
 325
 326 bool BookmarkModelAssociator::NodesMatch(
 327     const BookmarkNode* bookmark,
 328     const syncer::BaseNode* sync_node) const {
 329   if (bookmark->GetTitle() != base::UTF8ToUTF16(sync_node->GetTitle()))
 330     return false;
 331   if (bookmark->is_folder() != sync_node->GetIsFolder())
 332     return false;
 333   if (bookmark->is_url()) {
 334     if (bookmark->url() != GURL(sync_node->GetBookmarkSpecifics().url()))
 335       return false;
 336   }
 337   // Don't compare favicons here, because they are not really
 338   // user-updated and we don't have versioning information -- a site changing
 339   // its favicon shouldn't result in a bookmark mismatch.
 340   return true;
 341 }
 342
 343 bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
 344     const BookmarkNode* permanent_node, const std::string&tag) {
 345   // Do nothing if |permanent_node| is already initialized and associated.
 346   int64 sync_id = GetSyncIdFromChromeId(permanent_node->id());
 347   if (sync_id != syncer::kInvalidId)
 348     return true;
 349   if (!GetSyncIdForTaggedNode(tag, &sync_id))
 350     return false;
 351
 352   Associate(permanent_node, sync_id);
 353   return true;
 354 }
 355
 356 bool BookmarkModelAssociator::GetSyncIdForTaggedNode(const std::string& tag,
 357                                                      int64* sync_id) {
 358   syncer::ReadTransaction trans(FROM_HERE, user_share_);
 359   syncer::ReadNode sync_node(&trans);
 360   if (sync_node.InitByTagLookup(tag.c_str()) != syncer::BaseNode::INIT_OK)
 361     return false;
 362   *sync_id = sync_node.GetId();
 363   return true;
 364 }
 365
 366 syncer::SyncError BookmarkModelAssociator::AssociateModels(
 367     syncer::SyncMergeResult* local_merge_result,
 368     syncer::SyncMergeResult* syncer_merge_result) {
 369   // Since any changes to the bookmark model made here are not user initiated,
 370   // these change should not be undoable and so suspend the undo tracking.
 371 #if !defined(OS_ANDROID)
 372   ScopedSuspendUndoTracking suspend_undo(
 373       BookmarkUndoServiceFactory::GetForProfile(profile_)->undo_manager());
 374 #endif
 375   syncer::SyncError error = CheckModelSyncState(local_merge_result,
 376                                                 syncer_merge_result);
 377   if (error.IsSet())
 378     return error;
 379
 380   scoped_ptr<ScopedAssociationUpdater> association_updater(
 381       new ScopedAssociationUpdater(bookmark_model_));
 382   DisassociateModels();
 383
 384   return BuildAssociations(local_merge_result, syncer_merge_result);
 385 }
 386
 387 syncer::SyncError BookmarkModelAssociator::BuildAssociations(
 388     syncer::SyncMergeResult* local_merge_result,
 389     syncer::SyncMergeResult* syncer_merge_result) {
 390   // Algorithm description:
 391   // Match up the roots and recursively do the following:
 392   // * For each sync node for the current sync parent node, find the best
 393   //   matching bookmark node under the corresponding bookmark parent node.
 394   //   If no matching node is found, create a new bookmark node in the same
 395   //   position as the corresponding sync node.
 396   //   If a matching node is found, update the properties of it from the
 397   //   corresponding sync node.
 398   // * When all children sync nodes are done, add the extra children bookmark
 399   //   nodes to the sync parent node.
 400   //
 401   // This algorithm will do a good job of merging when folder names are a good
 402   // indicator of the two folders being the same. It will handle reordering and
 403   // new node addition very well (without creating duplicates).
 404   // This algorithm will not do well if the folder name has changes but the
 405   // children under them are all the same.
 406
 407   DCHECK(bookmark_model_->loaded());
 408
 409   // To prime our association, we associate the top-level nodes, Bookmark Bar
 410   // and Other Bookmarks.
 411   if (!AssociateTaggedPermanentNode(bookmark_model_->bookmark_bar_node(),
 412                                     kBookmarkBarTag)) {
 413     return unrecoverable_error_handler_->CreateAndUploadError(
 414         FROM_HERE,
 415         "Bookmark bar node not found",
 416         model_type());
 417   }
 418
 419   if (!AssociateTaggedPermanentNode(bookmark_model_->other_node(),
 420                                     kOtherBookmarksTag)) {
 421     return unrecoverable_error_handler_->CreateAndUploadError(
 422         FROM_HERE,
 423         "Other bookmarks node not found",
 424         model_type());
 425   }
 426
 427   if (!AssociateTaggedPermanentNode(bookmark_model_->mobile_node(),
 428                                     kMobileBookmarksTag) &&
 429       expect_mobile_bookmarks_folder_) {
 430     return unrecoverable_error_handler_->CreateAndUploadError(
 431         FROM_HERE,
 432         "Mobile bookmarks node not found",
 433         model_type());
 434   }
 435
 436   int64 bookmark_bar_sync_id = GetSyncIdFromChromeId(
 437       bookmark_model_->bookmark_bar_node()->id());
 438   DCHECK_NE(bookmark_bar_sync_id, syncer::kInvalidId);
 439   int64 other_bookmarks_sync_id = GetSyncIdFromChromeId(
 440       bookmark_model_->other_node()->id());
 441   DCHECK_NE(other_bookmarks_sync_id, syncer::kInvalidId);
 442   int64 mobile_bookmarks_sync_id = GetSyncIdFromChromeId(
 443        bookmark_model_->mobile_node()->id());
 444   if (expect_mobile_bookmarks_folder_) {
 445     DCHECK_NE(syncer::kInvalidId, mobile_bookmarks_sync_id);
 446   }
 447
 448   // WARNING: The order in which we push these should match their order in the
 449   // bookmark model (see BookmarkModel::DoneLoading(..)).
 450   std::stack<int64> dfs_stack;
 451   dfs_stack.push(bookmark_bar_sync_id);
 452   dfs_stack.push(other_bookmarks_sync_id);
 453   if (mobile_bookmarks_sync_id != syncer::kInvalidId)
 454     dfs_stack.push(mobile_bookmarks_sync_id);
 455
 456   syncer::WriteTransaction trans(FROM_HERE, user_share_);
 457   syncer::ReadNode bm_root(&trans);
 458   if (bm_root.InitByTagLookup(syncer::ModelTypeToRootTag(syncer::BOOKMARKS)) ==
 459       syncer::BaseNode::INIT_OK) {
 460     syncer_merge_result->set_num_items_before_association(
 461         bm_root.GetTotalNodeCount());
 462   }
 463   local_merge_result->set_num_items_before_association(
 464       bookmark_model_->root_node()->GetTotalNodeCount());
 465
 466   // Remove obsolete bookmarks according to sync delete journal.
 467   local_merge_result->set_num_items_deleted(
 468       ApplyDeletesFromSyncJournal(&trans));
 469
 470   while (!dfs_stack.empty()) {
 471     int64 sync_parent_id = dfs_stack.top();
 472     dfs_stack.pop();
 473
 474     syncer::ReadNode sync_parent(&trans);
 475     if (sync_parent.InitByIdLookup(sync_parent_id) !=
 476             syncer::BaseNode::INIT_OK) {
 477       return unrecoverable_error_handler_->CreateAndUploadError(
 478           FROM_HERE,
 479           "Failed to lookup node.",
 480           model_type());
 481     }
 482     // Only folder nodes are pushed on to the stack.
 483     DCHECK(sync_parent.GetIsFolder());
 484
 485     const BookmarkNode* parent_node = GetChromeNodeFromSyncId(sync_parent_id);
 486     DCHECK(parent_node->is_folder());
 487
 488     BookmarkNodeFinder node_finder(parent_node);
 489
 490     std::vector<int64> children;
 491     sync_parent.GetChildIds(&children);
 492     int index = 0;
 493     for (std::vector<int64>::const_iterator it = children.begin();
 494          it != children.end(); ++it) {
 495       int64 sync_child_id = *it;
 496       syncer::ReadNode sync_child_node(&trans);
 497       if (sync_child_node.InitByIdLookup(sync_child_id) !=
 498               syncer::BaseNode::INIT_OK) {
 499         return unrecoverable_error_handler_->CreateAndUploadError(
 500             FROM_HERE,
 501             "Failed to lookup node.",
 502             model_type());
 503       }
 504
 505       const BookmarkNode* child_node = NULL;
 506       child_node = node_finder.FindBookmarkNode(
 507           GURL(sync_child_node.GetBookmarkSpecifics().url()),
 508           sync_child_node.GetTitle(),
 509           sync_child_node.GetIsFolder());
 510       if (child_node) {
 511         Associate(child_node, sync_child_id);
 512
 513         // All bookmarks are currently modified at association time, even if
 514         // nothing has changed.
 515         // TODO(sync): Only modify the bookmark model if necessary.
 516         BookmarkChangeProcessor::UpdateBookmarkWithSyncData(
 517             sync_child_node, bookmark_model_, child_node, profile_);
 518         bookmark_model_->Move(child_node, parent_node, index);
 519         local_merge_result->set_num_items_modified(
 520             local_merge_result->num_items_modified() + 1);
 521       } else {
 522         child_node = BookmarkChangeProcessor::CreateBookmarkNode(
 523             &sync_child_node, parent_node, bookmark_model_, profile_, index);
 524         if (child_node)
 525           Associate(child_node, sync_child_id);
 526         local_merge_result->set_num_items_added(
 527             local_merge_result->num_items_added() + 1);
 528       }
 529       if (sync_child_node.GetIsFolder())
 530         dfs_stack.push(sync_child_id);
 531       ++index;
 532     }
 533
 534     // At this point all the children nodes of the parent sync node have
 535     // corresponding children in the parent bookmark node and they are all in
 536     // the right positions: from 0 to index - 1.
 537     // So the children starting from index in the parent bookmark node are the
 538     // ones that are not present in the parent sync node. So create them.
 539     for (int i = index; i < parent_node->child_count(); ++i) {
 540       int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
 541           parent_node, bookmark_model_, i, &trans, this,
 542           unrecoverable_error_handler_);
 543       if (syncer::kInvalidId == sync_child_id) {
 544         return unrecoverable_error_handler_->CreateAndUploadError(
 545             FROM_HERE,
 546             "Failed to create sync node.",
 547             model_type());
 548       }
 549       syncer_merge_result->set_num_items_added(
 550           syncer_merge_result->num_items_added() + 1);
 551       if (parent_node->GetChild(i)->is_folder())
 552         dfs_stack.push(sync_child_id);
 553     }
 554   }
 555
 556   local_merge_result->set_num_items_after_association(
 557       bookmark_model_->root_node()->GetTotalNodeCount());
 558   syncer_merge_result->set_num_items_after_association(
 559       bm_root.GetTotalNodeCount());
 560
 561   return syncer::SyncError();
 562 }
 563
 564 struct FolderInfo {
 565   FolderInfo(const BookmarkNode* f, const BookmarkNode* p, int64 id)
 566       : folder(f), parent(p), sync_id(id) {}
 567   const BookmarkNode* folder;
 568   const BookmarkNode* parent;
 569   int64 sync_id;
 570 };
 571 typedef std::vector<FolderInfo> FolderInfoList;
 572
 573 int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
 574     syncer::BaseTransaction* trans) {
 575   int64 num_bookmark_deleted = 0;
 576
 577   syncer::BookmarkDeleteJournalList bk_delete_journals;
 578   syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
 579   if (bk_delete_journals.empty())
 580     return 0;
 581   size_t num_journals_unmatched = bk_delete_journals.size();
 582
 583   // Check bookmark model from top to bottom.
 584   std::stack<const BookmarkNode*> dfs_stack;
 585   dfs_stack.push(bookmark_model_->bookmark_bar_node());
 586   dfs_stack.push(bookmark_model_->other_node());
 587   if (expect_mobile_bookmarks_folder_)
 588     dfs_stack.push(bookmark_model_->mobile_node());
 589
 590   // Remember folders that match delete journals in first pass but don't delete
 591   // them in case there are bookmarks left under them. After non-folder
 592   // bookmarks are removed in first pass, recheck the folders in reverse order
 593   // to remove empty ones.
 594   FolderInfoList folders_matched;
 595   while (!dfs_stack.empty()) {
 596     const BookmarkNode* parent = dfs_stack.top();
 597     dfs_stack.pop();
 598
 599     BookmarkNodeFinder finder(parent);
 600     // Iterate through journals from back to front. Remove matched journal by
 601     // moving an unmatched journal at the tail to its position so that we can
 602     // read unmatched journals off the head in next loop.
 603     for (int i = num_journals_unmatched - 1; i >= 0; --i) {
 604       const BookmarkNode* child = finder.FindBookmarkNode(
 605           GURL(bk_delete_journals[i].specifics.bookmark().url()),
 606           bk_delete_journals[i].specifics.bookmark().title(),
 607           bk_delete_journals[i].is_folder);
 608       if (child) {
 609         if (child->is_folder()) {
 610           // Remember matched folder without removing and delete only empty
 611           // ones later.
 612           folders_matched.push_back(FolderInfo(child, parent,
 613                                                bk_delete_journals[i].id));
 614         } else {
 615           bookmark_model_->Remove(parent, parent->GetIndexOf(child));
 616           ++num_bookmark_deleted;
 617         }
 618         // Move unmatched journal here and decrement counter.
 619         bk_delete_journals[i] = bk_delete_journals[--num_journals_unmatched];
 620       }
 621     }
 622     if (num_journals_unmatched == 0)
 623       break;
 624
 625     for (int i = 0; i < parent->child_count(); ++i) {
 626       if (parent->GetChild(i)->is_folder())
 627         dfs_stack.push(parent->GetChild(i));
 628     }
 629   }
 630
 631   // Ids of sync nodes not found in bookmark model, meaning the deletions are
 632   // persisted and correponding delete journals can be dropped.
 633   std::set<int64> journals_to_purge;
 634
 635   // Remove empty folders from bottom to top.
 636   for (FolderInfoList::reverse_iterator it = folders_matched.rbegin();
 637       it != folders_matched.rend(); ++it) {
 638     if (it->folder->child_count() == 0) {
 639       bookmark_model_->Remove(it->parent, it->parent->GetIndexOf(it->folder));
 640       ++num_bookmark_deleted;
 641     } else {
 642       // Keep non-empty folder and remove its journal so that it won't match
 643       // again in the future.
 644       journals_to_purge.insert(it->sync_id);
 645     }
 646   }
 647
 648   // Purge unmatched journals.
 649   for (size_t i = 0; i < num_journals_unmatched; ++i)
 650     journals_to_purge.insert(bk_delete_journals[i].id);
 651   syncer::DeleteJournal::PurgeDeleteJournals(trans, journals_to_purge);
 652
 653   return num_bookmark_deleted;
 654 }
 655
 656 void BookmarkModelAssociator::PostPersistAssociationsTask() {
 657   // No need to post a task if a task is already pending.
 658   if (weak_factory_.HasWeakPtrs())
 659     return;
 660   base::MessageLoop::current()->PostTask(
 661       FROM_HERE,
 662       base::Bind(
 663           &BookmarkModelAssociator::PersistAssociations,
 664           weak_factory_.GetWeakPtr()));
 665 }
 666
 667 void BookmarkModelAssociator::PersistAssociations() {
 668   // If there are no dirty associations we have nothing to do. We handle this
 669   // explicity instead of letting the for loop do it to avoid creating a write
 670   // transaction in this case.
 671   if (dirty_associations_sync_ids_.empty()) {
 672     DCHECK(id_map_.empty());
 673     DCHECK(id_map_inverse_.empty());
 674     return;
 675   }
 676
 677   int64 new_version = syncer::syncable::kInvalidTransactionVersion;
 678   std::vector<const BookmarkNode*> bnodes;
 679   {
 680     syncer::WriteTransaction trans(FROM_HERE, user_share_, &new_version);
 681     DirtyAssociationsSyncIds::iterator iter;
 682     for (iter = dirty_associations_sync_ids_.begin();
 683          iter != dirty_associations_sync_ids_.end();
 684          ++iter) {
 685       int64 sync_id = *iter;
 686       syncer::WriteNode sync_node(&trans);
 687       if (sync_node.InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK) {
 688         unrecoverable_error_handler_->OnSingleDatatypeUnrecoverableError(
 689             FROM_HERE,
 690             "Could not lookup bookmark node for ID persistence.");
 691         return;
 692       }
 693       const BookmarkNode* node = GetChromeNodeFromSyncId(sync_id);
 694       if (node && sync_node.GetExternalId() != node->id()) {
 695         sync_node.SetExternalId(node->id());
 696         bnodes.push_back(node);
 697       }
 698     }
 699     dirty_associations_sync_ids_.clear();
 700   }
 701
 702   BookmarkChangeProcessor::UpdateTransactionVersion(new_version,
 703                                                     bookmark_model_,
 704                                                     bnodes);
 705 }
 706
 707 bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
 708   // We only access the cryptographer while holding a transaction.
 709   syncer::ReadTransaction trans(FROM_HERE, user_share_);
 710   const syncer::ModelTypeSet encrypted_types = trans.GetEncryptedTypes();
 711   return !encrypted_types.Has(syncer::BOOKMARKS) ||
 712       trans.GetCryptographer()->is_ready();
 713 }
 714
 715 syncer::SyncError BookmarkModelAssociator::CheckModelSyncState(
 716     syncer::SyncMergeResult* local_merge_result,
 717     syncer::SyncMergeResult* syncer_merge_result) const {
 718   int64 native_version =
 719       bookmark_model_->root_node()->sync_transaction_version();
 720   if (native_version != syncer::syncable::kInvalidTransactionVersion) {
 721     syncer::ReadTransaction trans(FROM_HERE, user_share_);
 722     local_merge_result->set_pre_association_version(native_version);
 723
 724     int64 sync_version = trans.GetModelVersion(syncer::BOOKMARKS);
 725     syncer_merge_result->set_pre_association_version(sync_version);
 726
 727     if (native_version != sync_version) {
 728       UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
 729                                 ModelTypeToHistogramInt(syncer::BOOKMARKS),
 730                                 syncer::MODEL_TYPE_COUNT);
 731
 732       // Clear version on bookmark model so that we only report error once.
 733       bookmark_model_->SetNodeSyncTransactionVersion(
 734           bookmark_model_->root_node(),
 735           syncer::syncable::kInvalidTransactionVersion);
 736
 737       // If the native version is higher, there was a sync persistence failure,
 738       // and we need to delay association until after a GetUpdates.
 739       if (sync_version < native_version) {
 740         std::string message = base::StringPrintf(
 741             "Native version (%" PRId64 ") does not match sync version (%"
 742                 PRId64 ")",
 743             native_version,
 744             sync_version);
 745         return syncer::SyncError(FROM_HERE,
 746                                  syncer::SyncError::PERSISTENCE_ERROR,
 747                                  message,
 748                                  syncer::BOOKMARKS);
 749       }
 750     }
 751   }
 752   return syncer::SyncError();
 753 }
 754
 755 }  // namespace browser_sync