src/chrome/browser/sync/glue/bookmark_model_associator.cc

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