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