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
39using content::BrowserThread;
40
41namespace 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.
61const char kBookmarkBarTag[] = "bookmark_bar";
62const char kMobileBookmarksTag[] = "synced_bookmarks";
63const 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).
67const int kTitleLimitBytes = 255;
68
69// Bookmark comparer for map of bookmark nodes.
70class 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.
103class 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
124class 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
141BookmarkNodeFinder::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
148const 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.
170class 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
194void 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
207const 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
212BookmarkModelAssociator::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
230BookmarkModelAssociator::~BookmarkModelAssociator() {
231  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
232}
233
234void 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
254syncer::SyncError BookmarkModelAssociator::DisassociateModels() {
255  id_map_.clear();
256  id_map_inverse_.clear();
257  dirty_associations_sync_ids_.clear();
258  return syncer::SyncError();
259}
260
261int64 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
266const 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
272bool 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
285void 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
299void 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
309bool 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
355bool 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
376bool 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
389bool 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
400syncer::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
419syncer::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
606struct 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};
613typedef std::vector<FolderInfo> FolderInfoList;
614
615int64 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
700void 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
711void 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
754bool 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
762syncer::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