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