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