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     sync_driver::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   ScopedSuspendBookmarkUndo suspend_undo(profile_);
    406 
    407   syncer::SyncError error = CheckModelSyncState(local_merge_result,
    408                                                 syncer_merge_result);
    409   if (error.IsSet())
    410     return error;
    411 
    412   scoped_ptr<ScopedAssociationUpdater> association_updater(
    413       new ScopedAssociationUpdater(bookmark_model_));
    414   DisassociateModels();
    415 
    416   return BuildAssociations(local_merge_result, syncer_merge_result);
    417 }
    418 
    419 syncer::SyncError BookmarkModelAssociator::BuildAssociations(
    420     syncer::SyncMergeResult* local_merge_result,
    421     syncer::SyncMergeResult* syncer_merge_result) {
    422   // Algorithm description:
    423   // Match up the roots and recursively do the following:
    424   // * For each sync node for the current sync parent node, find the best
    425   //   matching bookmark node under the corresponding bookmark parent node.
    426   //   If no matching node is found, create a new bookmark node in the same
    427   //   position as the corresponding sync node.
    428   //   If a matching node is found, update the properties of it from the
    429   //   corresponding sync node.
    430   // * When all children sync nodes are done, add the extra children bookmark
    431   //   nodes to the sync parent node.
    432   //
    433   // This algorithm will do a good job of merging when folder names are a good
    434   // indicator of the two folders being the same. It will handle reordering and
    435   // new node addition very well (without creating duplicates).
    436   // This algorithm will not do well if the folder name has changes but the
    437   // children under them are all the same.
    438 
    439   DCHECK(bookmark_model_->loaded());
    440 
    441   // To prime our association, we associate the top-level nodes, Bookmark Bar
    442   // and Other Bookmarks.
    443   if (!AssociateTaggedPermanentNode(bookmark_model_->bookmark_bar_node(),
    444                                     kBookmarkBarTag)) {
    445     return unrecoverable_error_handler_->CreateAndUploadError(
    446         FROM_HERE,
    447         "Bookmark bar node not found",
    448         model_type());
    449   }
    450 
    451   if (!AssociateTaggedPermanentNode(bookmark_model_->other_node(),
    452                                     kOtherBookmarksTag)) {
    453     return unrecoverable_error_handler_->CreateAndUploadError(
    454         FROM_HERE,
    455         "Other bookmarks node not found",
    456         model_type());
    457   }
    458 
    459   if (!AssociateTaggedPermanentNode(bookmark_model_->mobile_node(),
    460                                     kMobileBookmarksTag) &&
    461       expect_mobile_bookmarks_folder_) {
    462     return unrecoverable_error_handler_->CreateAndUploadError(
    463         FROM_HERE,
    464         "Mobile bookmarks node not found",
    465         model_type());
    466   }
    467 
    468   // Note: the root node may have additional extra nodes. Currently none of
    469   // them are meant to sync.
    470 
    471   int64 bookmark_bar_sync_id = GetSyncIdFromChromeId(
    472       bookmark_model_->bookmark_bar_node()->id());
    473   DCHECK_NE(bookmark_bar_sync_id, syncer::kInvalidId);
    474   int64 other_bookmarks_sync_id = GetSyncIdFromChromeId(
    475       bookmark_model_->other_node()->id());
    476   DCHECK_NE(other_bookmarks_sync_id, syncer::kInvalidId);
    477   int64 mobile_bookmarks_sync_id = GetSyncIdFromChromeId(
    478        bookmark_model_->mobile_node()->id());
    479   if (expect_mobile_bookmarks_folder_) {
    480     DCHECK_NE(syncer::kInvalidId, mobile_bookmarks_sync_id);
    481   }
    482 
    483   // WARNING: The order in which we push these should match their order in the
    484   // bookmark model (see BookmarkModel::DoneLoading(..)).
    485   std::stack<int64> dfs_stack;
    486   dfs_stack.push(bookmark_bar_sync_id);
    487   dfs_stack.push(other_bookmarks_sync_id);
    488   if (mobile_bookmarks_sync_id != syncer::kInvalidId)
    489     dfs_stack.push(mobile_bookmarks_sync_id);
    490 
    491   syncer::WriteTransaction trans(FROM_HERE, user_share_);
    492   syncer::ReadNode bm_root(&trans);
    493   if (bm_root.InitTypeRoot(syncer::BOOKMARKS) == syncer::BaseNode::INIT_OK) {
    494     syncer_merge_result->set_num_items_before_association(
    495         bm_root.GetTotalNodeCount());
    496   }
    497   local_merge_result->set_num_items_before_association(
    498       bookmark_model_->root_node()->GetTotalNodeCount());
    499 
    500   // Remove obsolete bookmarks according to sync delete journal.
    501   local_merge_result->set_num_items_deleted(
    502       ApplyDeletesFromSyncJournal(&trans));
    503 
    504   while (!dfs_stack.empty()) {
    505     int64 sync_parent_id = dfs_stack.top();
    506     dfs_stack.pop();
    507 
    508     syncer::ReadNode sync_parent(&trans);
    509     if (sync_parent.InitByIdLookup(sync_parent_id) !=
    510             syncer::BaseNode::INIT_OK) {
    511       return unrecoverable_error_handler_->CreateAndUploadError(
    512           FROM_HERE,
    513           "Failed to lookup node.",
    514           model_type());
    515     }
    516     // Only folder nodes are pushed on to the stack.
    517     DCHECK(sync_parent.GetIsFolder());
    518 
    519     const BookmarkNode* parent_node = GetChromeNodeFromSyncId(sync_parent_id);
    520     if (!parent_node) {
    521       return unrecoverable_error_handler_->CreateAndUploadError(
    522           FROM_HERE, "Failed to find bookmark node for sync id.", model_type());
    523     }
    524     DCHECK(parent_node->is_folder());
    525 
    526     BookmarkNodeFinder node_finder(parent_node);
    527 
    528     std::vector<int64> children;
    529     sync_parent.GetChildIds(&children);
    530     int index = 0;
    531     for (std::vector<int64>::const_iterator it = children.begin();
    532          it != children.end(); ++it) {
    533       int64 sync_child_id = *it;
    534       syncer::ReadNode sync_child_node(&trans);
    535       if (sync_child_node.InitByIdLookup(sync_child_id) !=
    536               syncer::BaseNode::INIT_OK) {
    537         return unrecoverable_error_handler_->CreateAndUploadError(
    538             FROM_HERE,
    539             "Failed to lookup node.",
    540             model_type());
    541       }
    542 
    543       const BookmarkNode* child_node = NULL;
    544       child_node = node_finder.FindBookmarkNode(
    545           GURL(sync_child_node.GetBookmarkSpecifics().url()),
    546           sync_child_node.GetTitle(),
    547           sync_child_node.GetIsFolder());
    548       if (child_node) {
    549         Associate(child_node, sync_child_id);
    550 
    551         // All bookmarks are currently modified at association time, even if
    552         // nothing has changed.
    553         // TODO(sync): Only modify the bookmark model if necessary.
    554         BookmarkChangeProcessor::UpdateBookmarkWithSyncData(
    555             sync_child_node, bookmark_model_, child_node, profile_);
    556         bookmark_model_->Move(child_node, parent_node, index);
    557         local_merge_result->set_num_items_modified(
    558             local_merge_result->num_items_modified() + 1);
    559       } else {
    560         DCHECK_LE(index, parent_node->child_count());
    561         child_node = BookmarkChangeProcessor::CreateBookmarkNode(
    562             &sync_child_node, parent_node, bookmark_model_, profile_, index);
    563         if (!child_node) {
    564           return unrecoverable_error_handler_->CreateAndUploadError(
    565               FROM_HERE, "Failed to create bookmark node.", model_type());
    566         }
    567         Associate(child_node, sync_child_id);
    568         local_merge_result->set_num_items_added(
    569             local_merge_result->num_items_added() + 1);
    570       }
    571       if (sync_child_node.GetIsFolder())
    572         dfs_stack.push(sync_child_id);
    573       ++index;
    574     }
    575 
    576     // At this point all the children nodes of the parent sync node have
    577     // corresponding children in the parent bookmark node and they are all in
    578     // the right positions: from 0 to index - 1.
    579     // So the children starting from index in the parent bookmark node are the
    580     // ones that are not present in the parent sync node. So create them.
    581     for (int i = index; i < parent_node->child_count(); ++i) {
    582       int64 sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
    583           parent_node, bookmark_model_, i, &trans, this,
    584           unrecoverable_error_handler_);
    585       if (syncer::kInvalidId == sync_child_id) {
    586         return unrecoverable_error_handler_->CreateAndUploadError(
    587             FROM_HERE,
    588             "Failed to create sync node.",
    589             model_type());
    590       }
    591       syncer_merge_result->set_num_items_added(
    592           syncer_merge_result->num_items_added() + 1);
    593       if (parent_node->GetChild(i)->is_folder())
    594         dfs_stack.push(sync_child_id);
    595     }
    596   }
    597 
    598   local_merge_result->set_num_items_after_association(
    599       bookmark_model_->root_node()->GetTotalNodeCount());
    600   syncer_merge_result->set_num_items_after_association(
    601       bm_root.GetTotalNodeCount());
    602 
    603   return syncer::SyncError();
    604 }
    605 
    606 struct FolderInfo {
    607   FolderInfo(const BookmarkNode* f, const BookmarkNode* p, int64 id)
    608       : folder(f), parent(p), sync_id(id) {}
    609   const BookmarkNode* folder;
    610   const BookmarkNode* parent;
    611   int64 sync_id;
    612 };
    613 typedef std::vector<FolderInfo> FolderInfoList;
    614 
    615 int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
    616     syncer::BaseTransaction* trans) {
    617   int64 num_bookmark_deleted = 0;
    618 
    619   syncer::BookmarkDeleteJournalList bk_delete_journals;
    620   syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
    621   if (bk_delete_journals.empty())
    622     return 0;
    623   size_t num_journals_unmatched = bk_delete_journals.size();
    624 
    625   // Check bookmark model from top to bottom.
    626   std::stack<const BookmarkNode*> dfs_stack;
    627   dfs_stack.push(bookmark_model_->bookmark_bar_node());
    628   dfs_stack.push(bookmark_model_->other_node());
    629   if (expect_mobile_bookmarks_folder_)
    630     dfs_stack.push(bookmark_model_->mobile_node());
    631   // Note: the root node may have additional extra nodes. Currently none of
    632   // them are meant to sync.
    633 
    634   // Remember folders that match delete journals in first pass but don't delete
    635   // them in case there are bookmarks left under them. After non-folder
    636   // bookmarks are removed in first pass, recheck the folders in reverse order
    637   // to remove empty ones.
    638   FolderInfoList folders_matched;
    639   while (!dfs_stack.empty()) {
    640     const BookmarkNode* parent = dfs_stack.top();
    641     dfs_stack.pop();
    642 
    643     BookmarkNodeFinder finder(parent);
    644     // Iterate through journals from back to front. Remove matched journal by
    645     // moving an unmatched journal at the tail to its position so that we can
    646     // read unmatched journals off the head in next loop.
    647     for (int i = num_journals_unmatched - 1; i >= 0; --i) {
    648       const BookmarkNode* child = finder.FindBookmarkNode(
    649           GURL(bk_delete_journals[i].specifics.bookmark().url()),
    650           bk_delete_journals[i].specifics.bookmark().title(),
    651           bk_delete_journals[i].is_folder);
    652       if (child) {
    653         if (child->is_folder()) {
    654           // Remember matched folder without removing and delete only empty
    655           // ones later.
    656           folders_matched.push_back(FolderInfo(child, parent,
    657                                                bk_delete_journals[i].id));
    658         } else {
    659           bookmark_model_->Remove(parent, parent->GetIndexOf(child));
    660           ++num_bookmark_deleted;
    661         }
    662         // Move unmatched journal here and decrement counter.
    663         bk_delete_journals[i] = bk_delete_journals[--num_journals_unmatched];
    664       }
    665     }
    666     if (num_journals_unmatched == 0)
    667       break;
    668 
    669     for (int i = 0; i < parent->child_count(); ++i) {
    670       if (parent->GetChild(i)->is_folder())
    671         dfs_stack.push(parent->GetChild(i));
    672     }
    673   }
    674 
    675   // Ids of sync nodes not found in bookmark model, meaning the deletions are
    676   // persisted and correponding delete journals can be dropped.
    677   std::set<int64> journals_to_purge;
    678 
    679   // Remove empty folders from bottom to top.
    680   for (FolderInfoList::reverse_iterator it = folders_matched.rbegin();
    681       it != folders_matched.rend(); ++it) {
    682     if (it->folder->child_count() == 0) {
    683       bookmark_model_->Remove(it->parent, it->parent->GetIndexOf(it->folder));
    684       ++num_bookmark_deleted;
    685     } else {
    686       // Keep non-empty folder and remove its journal so that it won't match
    687       // again in the future.
    688       journals_to_purge.insert(it->sync_id);
    689     }
    690   }
    691 
    692   // Purge unmatched journals.
    693   for (size_t i = 0; i < num_journals_unmatched; ++i)
    694     journals_to_purge.insert(bk_delete_journals[i].id);
    695   syncer::DeleteJournal::PurgeDeleteJournals(trans, journals_to_purge);
    696 
    697   return num_bookmark_deleted;
    698 }
    699 
    700 void BookmarkModelAssociator::PostPersistAssociationsTask() {
    701   // No need to post a task if a task is already pending.
    702   if (weak_factory_.HasWeakPtrs())
    703     return;
    704   base::MessageLoop::current()->PostTask(
    705       FROM_HERE,
    706       base::Bind(
    707           &BookmarkModelAssociator::PersistAssociations,
    708           weak_factory_.GetWeakPtr()));
    709 }
    710 
    711 void BookmarkModelAssociator::PersistAssociations() {
    712   // If there are no dirty associations we have nothing to do. We handle this
    713   // explicity instead of letting the for loop do it to avoid creating a write
    714   // transaction in this case.
    715   if (dirty_associations_sync_ids_.empty()) {
    716     DCHECK(id_map_.empty());
    717     DCHECK(id_map_inverse_.empty());
    718     return;
    719   }
    720 
    721   int64 new_version = syncer::syncable::kInvalidTransactionVersion;
    722   std::vector<const BookmarkNode*> bnodes;
    723   {
    724     syncer::WriteTransaction trans(FROM_HERE, user_share_, &new_version);
    725     DirtyAssociationsSyncIds::iterator iter;
    726     for (iter = dirty_associations_sync_ids_.begin();
    727          iter != dirty_associations_sync_ids_.end();
    728          ++iter) {
    729       int64 sync_id = *iter;
    730       syncer::WriteNode sync_node(&trans);
    731       if (sync_node.InitByIdLookup(sync_id) != syncer::BaseNode::INIT_OK) {
    732         syncer::SyncError error(
    733             FROM_HERE,
    734             syncer::SyncError::DATATYPE_ERROR,
    735             "Could not lookup bookmark node for ID persistence.",
    736             syncer::BOOKMARKS);
    737         unrecoverable_error_handler_->OnSingleDataTypeUnrecoverableError(error);
    738         return;
    739       }
    740       const BookmarkNode* node = GetChromeNodeFromSyncId(sync_id);
    741       if (node && sync_node.GetExternalId() != node->id()) {
    742         sync_node.SetExternalId(node->id());
    743         bnodes.push_back(node);
    744       }
    745     }
    746     dirty_associations_sync_ids_.clear();
    747   }
    748 
    749   BookmarkChangeProcessor::UpdateTransactionVersion(new_version,
    750                                                     bookmark_model_,
    751                                                     bnodes);
    752 }
    753 
    754 bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
    755   // We only access the cryptographer while holding a transaction.
    756   syncer::ReadTransaction trans(FROM_HERE, user_share_);
    757   const syncer::ModelTypeSet encrypted_types = trans.GetEncryptedTypes();
    758   return !encrypted_types.Has(syncer::BOOKMARKS) ||
    759       trans.GetCryptographer()->is_ready();
    760 }
    761 
    762 syncer::SyncError BookmarkModelAssociator::CheckModelSyncState(
    763     syncer::SyncMergeResult* local_merge_result,
    764     syncer::SyncMergeResult* syncer_merge_result) const {
    765   int64 native_version =
    766       bookmark_model_->root_node()->sync_transaction_version();
    767   if (native_version != syncer::syncable::kInvalidTransactionVersion) {
    768     syncer::ReadTransaction trans(FROM_HERE, user_share_);
    769     local_merge_result->set_pre_association_version(native_version);
    770 
    771     int64 sync_version = trans.GetModelVersion(syncer::BOOKMARKS);
    772     syncer_merge_result->set_pre_association_version(sync_version);
    773 
    774     if (native_version != sync_version) {
    775       UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
    776                                 ModelTypeToHistogramInt(syncer::BOOKMARKS),
    777                                 syncer::MODEL_TYPE_COUNT);
    778 
    779       // Clear version on bookmark model so that we only report error once.
    780       bookmark_model_->SetNodeSyncTransactionVersion(
    781           bookmark_model_->root_node(),
    782           syncer::syncable::kInvalidTransactionVersion);
    783 
    784       // If the native version is higher, there was a sync persistence failure,
    785       // and we need to delay association until after a GetUpdates.
    786       if (sync_version < native_version) {
    787         std::string message = base::StringPrintf(
    788             "Native version (%" PRId64 ") does not match sync version (%"
    789                 PRId64 ")",
    790             native_version,
    791             sync_version);
    792         return syncer::SyncError(FROM_HERE,
    793                                  syncer::SyncError::PERSISTENCE_ERROR,
    794                                  message,
    795                                  syncer::BOOKMARKS);
    796       }
    797     }
    798   }
    799   return syncer::SyncError();
    800 }
    801 
    802 }  // namespace browser_sync
    803