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