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