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