1// Copyright (c) 2011 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/hash_tables.h"
10#include "base/message_loop.h"
11#include "base/task.h"
12#include "base/utf_string_conversions.h"
13#include "chrome/browser/bookmarks/bookmark_model.h"
14#include "chrome/browser/profiles/profile.h"
15#include "chrome/browser/sync/engine/syncapi.h"
16#include "chrome/browser/sync/glue/bookmark_change_processor.h"
17#include "chrome/browser/sync/syncable/autofill_migration.h"
18#include "chrome/browser/sync/syncable/nigori_util.h"
19#include "chrome/browser/sync/util/cryptographer.h"
20#include "content/browser/browser_thread.h"
21
22namespace browser_sync {
23
24// The sync protocol identifies top-level entities by means of well-known tags,
25// which should not be confused with titles.  Each tag corresponds to a
26// singleton instance of a particular top-level node in a user's share; the
27// tags are consistent across users. The tags allow us to locate the specific
28// folders whose contents we care about synchronizing, without having to do a
29// lookup by name or path.  The tags should not be made user-visible.
30// For example, the tag "bookmark_bar" represents the permanent node for
31// bookmarks bar in Chrome. The tag "other_bookmarks" represents the permanent
32// folder Other Bookmarks in Chrome.
33//
34// It is the responsibility of something upstream (at time of writing,
35// the sync server) to create these tagged nodes when initializing sync
36// for the first time for a user.  Thus, once the backend finishes
37// initializing, the ProfileSyncService can rely on the presence of tagged
38// nodes.
39//
40// TODO(ncarter): Pull these tags from an external protocol specification
41// rather than hardcoding them here.
42static const char kBookmarkBarTag[] = "bookmark_bar";
43static const char kOtherBookmarksTag[] = "other_bookmarks";
44
45// Bookmark comparer for map of bookmark nodes.
46class BookmarkComparer {
47 public:
48  // Compares the two given nodes and returns whether node1 should appear
49  // before node2 in strict weak ordering.
50  bool operator()(const BookmarkNode* node1,
51                  const BookmarkNode* node2) const {
52    DCHECK(node1);
53    DCHECK(node2);
54
55    // Keep folder nodes before non-folder nodes.
56    if (node1->is_folder() != node2->is_folder())
57      return node1->is_folder();
58
59    int result = node1->GetTitle().compare(node2->GetTitle());
60    if (result != 0)
61      return result < 0;
62
63    return node1->GetURL() < node2->GetURL();
64  }
65};
66
67// Provides the following abstraction: given a parent bookmark node, find best
68// matching child node for many sync nodes.
69class BookmarkNodeFinder {
70 public:
71  // Creates an instance with the given parent bookmark node.
72  explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
73
74  // Finds best matching node for the given sync node.
75  // Returns the matching node if one exists; NULL otherwise. If a matching
76  // node is found, it's removed for further matches.
77  const BookmarkNode* FindBookmarkNode(const sync_api::BaseNode& sync_node);
78
79 private:
80  typedef std::multiset<const BookmarkNode*, BookmarkComparer> BookmarkNodesSet;
81
82  const BookmarkNode* parent_node_;
83  BookmarkNodesSet child_nodes_;
84
85  DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
86};
87
88BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node)
89    : parent_node_(parent_node) {
90  for (int i = 0; i < parent_node_->child_count(); ++i) {
91    child_nodes_.insert(parent_node_->GetChild(i));
92  }
93}
94
95const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
96    const sync_api::BaseNode& sync_node) {
97  // Create a bookmark node from the given sync node.
98  BookmarkNode temp_node(sync_node.GetURL());
99  temp_node.set_title(WideToUTF16Hack(sync_node.GetTitle()));
100  if (sync_node.GetIsFolder())
101    temp_node.set_type(BookmarkNode::FOLDER);
102  else
103    temp_node.set_type(BookmarkNode::URL);
104
105  const BookmarkNode* result = NULL;
106  BookmarkNodesSet::iterator iter = child_nodes_.find(&temp_node);
107  if (iter != child_nodes_.end()) {
108    result = *iter;
109    // Remove the matched node so we don't match with it again.
110    child_nodes_.erase(iter);
111  }
112
113  return result;
114}
115
116// Helper class to build an index of bookmark nodes by their IDs.
117class BookmarkNodeIdIndex {
118 public:
119  BookmarkNodeIdIndex() { }
120  ~BookmarkNodeIdIndex() { }
121
122  // Adds the given bookmark node and all its descendants to the ID index.
123  // Does nothing if node is NULL.
124  void AddAll(const BookmarkNode* node);
125
126  // Finds the bookmark node with the given ID.
127  // Returns NULL if none exists with the given id.
128  const BookmarkNode* Find(int64 id) const;
129
130  // Returns the count of nodes in the index.
131  size_t count() const { return node_index_.size(); }
132
133 private:
134  typedef base::hash_map<int64, const BookmarkNode*> BookmarkIdMap;
135  // Map that holds nodes indexed by their ids.
136  BookmarkIdMap node_index_;
137
138  DISALLOW_COPY_AND_ASSIGN(BookmarkNodeIdIndex);
139};
140
141void BookmarkNodeIdIndex::AddAll(const BookmarkNode* node) {
142  if (!node)
143    return;
144
145  node_index_[node->id()] = node;
146
147  if (!node->is_folder())
148    return;
149
150  for (int i = 0; i < node->child_count(); ++i)
151    AddAll(node->GetChild(i));
152}
153
154const BookmarkNode* BookmarkNodeIdIndex::Find(int64 id) const {
155  BookmarkIdMap::const_iterator iter = node_index_.find(id);
156  return iter == node_index_.end() ? NULL : iter->second;
157}
158
159BookmarkModelAssociator::BookmarkModelAssociator(
160    BookmarkModel* bookmark_model,
161    sync_api::UserShare* user_share,
162    UnrecoverableErrorHandler* unrecoverable_error_handler)
163    : bookmark_model_(bookmark_model),
164      user_share_(user_share),
165      unrecoverable_error_handler_(unrecoverable_error_handler),
166      ALLOW_THIS_IN_INITIALIZER_LIST(persist_associations_(this)),
167      number_of_new_sync_nodes_created_at_association_(0) {
168  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
169  DCHECK(bookmark_model_);
170  DCHECK(user_share_);
171  DCHECK(unrecoverable_error_handler_);
172}
173
174BookmarkModelAssociator::~BookmarkModelAssociator() {
175  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
176}
177
178bool BookmarkModelAssociator::DisassociateModels() {
179  id_map_.clear();
180  id_map_inverse_.clear();
181  dirty_associations_sync_ids_.clear();
182  return true;
183}
184
185int64 BookmarkModelAssociator::GetSyncIdFromChromeId(const int64& node_id) {
186  BookmarkIdToSyncIdMap::const_iterator iter = id_map_.find(node_id);
187  return iter == id_map_.end() ? sync_api::kInvalidId : iter->second;
188}
189
190const BookmarkNode* BookmarkModelAssociator::GetChromeNodeFromSyncId(
191    int64 sync_id) {
192  SyncIdToBookmarkNodeMap::const_iterator iter = id_map_inverse_.find(sync_id);
193  return iter == id_map_inverse_.end() ? NULL : iter->second;
194}
195
196bool BookmarkModelAssociator::InitSyncNodeFromChromeId(
197    const int64& node_id,
198    sync_api::BaseNode* sync_node) {
199  DCHECK(sync_node);
200  int64 sync_id = GetSyncIdFromChromeId(node_id);
201  if (sync_id == sync_api::kInvalidId)
202    return false;
203  if (!sync_node->InitByIdLookup(sync_id))
204    return false;
205  DCHECK(sync_node->GetId() == sync_id);
206  return true;
207}
208
209void BookmarkModelAssociator::Associate(const BookmarkNode* node,
210                                        int64 sync_id) {
211  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
212  int64 node_id = node->id();
213  DCHECK_NE(sync_id, sync_api::kInvalidId);
214  DCHECK(id_map_.find(node_id) == id_map_.end());
215  DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end());
216  id_map_[node_id] = sync_id;
217  id_map_inverse_[sync_id] = node;
218  dirty_associations_sync_ids_.insert(sync_id);
219  PostPersistAssociationsTask();
220}
221
222void BookmarkModelAssociator::Disassociate(int64 sync_id) {
223  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
224  SyncIdToBookmarkNodeMap::iterator iter = id_map_inverse_.find(sync_id);
225  if (iter == id_map_inverse_.end())
226    return;
227  id_map_.erase(iter->second->id());
228  id_map_inverse_.erase(iter);
229  dirty_associations_sync_ids_.erase(sync_id);
230}
231
232bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
233  DCHECK(has_nodes);
234  *has_nodes = false;
235  int64 bookmark_bar_sync_id;
236  if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_sync_id)) {
237    return false;
238  }
239  int64 other_bookmarks_sync_id;
240  if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_sync_id)) {
241    return false;
242  }
243
244  sync_api::ReadTransaction trans(user_share_);
245
246  sync_api::ReadNode bookmark_bar_node(&trans);
247  if (!bookmark_bar_node.InitByIdLookup(bookmark_bar_sync_id)) {
248    return false;
249  }
250
251  sync_api::ReadNode other_bookmarks_node(&trans);
252  if (!other_bookmarks_node.InitByIdLookup(other_bookmarks_sync_id)) {
253    return false;
254  }
255
256  // Sync model has user created nodes if either one of the permanent nodes
257  // has children.
258  *has_nodes = bookmark_bar_node.GetFirstChildId() != sync_api::kInvalidId ||
259      other_bookmarks_node.GetFirstChildId() != sync_api::kInvalidId;
260  return true;
261}
262
263bool BookmarkModelAssociator::NodesMatch(const BookmarkNode* bookmark,
264    const sync_api::BaseNode* sync_node) const {
265  if (bookmark->GetTitle() != WideToUTF16Hack(sync_node->GetTitle()))
266    return false;
267  if (bookmark->is_folder() != sync_node->GetIsFolder())
268    return false;
269  if (bookmark->is_url()) {
270    if (bookmark->GetURL() != sync_node->GetURL())
271      return false;
272  }
273  // Don't compare favicons here, because they are not really
274  // user-updated and we don't have versioning information -- a site changing
275  // its favicon shouldn't result in a bookmark mismatch.
276  return true;
277}
278
279bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
280    const BookmarkNode* permanent_node, const std::string&tag) {
281  // Do nothing if |permanent_node| is already initialized and associated.
282  int64 sync_id = GetSyncIdFromChromeId(permanent_node->id());
283  if (sync_id != sync_api::kInvalidId)
284    return true;
285  if (!GetSyncIdForTaggedNode(tag, &sync_id))
286    return false;
287
288  Associate(permanent_node, sync_id);
289  return true;
290}
291
292bool BookmarkModelAssociator::GetSyncIdForTaggedNode(const std::string& tag,
293                                                     int64* sync_id) {
294  sync_api::ReadTransaction trans(user_share_);
295  sync_api::ReadNode sync_node(&trans);
296  if (!sync_node.InitByTagLookup(tag.c_str()))
297    return false;
298  *sync_id = sync_node.GetId();
299  return true;
300}
301
302bool BookmarkModelAssociator::AssociateModels() {
303  // Try to load model associations from persisted associations first. If that
304  // succeeds, we don't need to run the complex model matching algorithm.
305  if (LoadAssociations())
306    return true;
307
308  DisassociateModels();
309
310  // We couldn't load model associations from persisted associations. So build
311  // them.
312  return BuildAssociations();
313}
314
315bool BookmarkModelAssociator::BuildAssociations() {
316  // Algorithm description:
317  // Match up the roots and recursively do the following:
318  // * For each sync node for the current sync parent node, find the best
319  //   matching bookmark node under the corresponding bookmark parent node.
320  //   If no matching node is found, create a new bookmark node in the same
321  //   position as the corresponding sync node.
322  //   If a matching node is found, update the properties of it from the
323  //   corresponding sync node.
324  // * When all children sync nodes are done, add the extra children bookmark
325  //   nodes to the sync parent node.
326  //
327  // This algorithm will do a good job of merging when folder names are a good
328  // indicator of the two folders being the same. It will handle reordering and
329  // new node addition very well (without creating duplicates).
330  // This algorithm will not do well if the folder name has changes but the
331  // children under them are all the same.
332
333  DCHECK(bookmark_model_->IsLoaded());
334
335  // To prime our association, we associate the top-level nodes, Bookmark Bar
336  // and Other Bookmarks.
337  if (!AssociateTaggedPermanentNode(bookmark_model_->other_node(),
338                                    kOtherBookmarksTag)) {
339    LOG(ERROR) << "Server did not create top-level nodes.  Possibly we "
340               << "are running against an out-of-date server?";
341    return false;
342  }
343  if (!AssociateTaggedPermanentNode(bookmark_model_->GetBookmarkBarNode(),
344                                    kBookmarkBarTag)) {
345    LOG(ERROR) << "Server did not create top-level nodes.  Possibly we "
346               << "are running against an out-of-date server?";
347    return false;
348  }
349  int64 bookmark_bar_sync_id = GetSyncIdFromChromeId(
350      bookmark_model_->GetBookmarkBarNode()->id());
351  DCHECK(bookmark_bar_sync_id != sync_api::kInvalidId);
352  int64 other_bookmarks_sync_id = GetSyncIdFromChromeId(
353      bookmark_model_->other_node()->id());
354  DCHECK(other_bookmarks_sync_id != sync_api::kInvalidId);
355
356  std::stack<int64> dfs_stack;
357  dfs_stack.push(other_bookmarks_sync_id);
358  dfs_stack.push(bookmark_bar_sync_id);
359
360  sync_api::WriteTransaction trans(user_share_);
361
362  while (!dfs_stack.empty()) {
363    int64 sync_parent_id = dfs_stack.top();
364    dfs_stack.pop();
365
366    sync_api::ReadNode sync_parent(&trans);
367    if (!sync_parent.InitByIdLookup(sync_parent_id)) {
368      return false;
369    }
370    // Only folder nodes are pushed on to the stack.
371    DCHECK(sync_parent.GetIsFolder());
372
373    const BookmarkNode* parent_node = GetChromeNodeFromSyncId(sync_parent_id);
374    DCHECK(parent_node->is_folder());
375
376    BookmarkNodeFinder node_finder(parent_node);
377
378    int index = 0;
379    int64 sync_child_id = sync_parent.GetFirstChildId();
380    while (sync_child_id != sync_api::kInvalidId) {
381      sync_api::WriteNode sync_child_node(&trans);
382      if (!sync_child_node.InitByIdLookup(sync_child_id)) {
383        return false;
384      }
385
386      const BookmarkNode* child_node = NULL;
387      child_node = node_finder.FindBookmarkNode(sync_child_node);
388      if (child_node) {
389        bookmark_model_->Move(child_node, parent_node, index);
390        // Set the favicon for bookmark node from sync node or vice versa.
391        if (BookmarkChangeProcessor::SetBookmarkFavicon(
392            &sync_child_node, child_node, bookmark_model_)) {
393          BookmarkChangeProcessor::SetSyncNodeFavicon(
394              child_node, bookmark_model_, &sync_child_node);
395        }
396      } else {
397        // Create a new bookmark node for the sync node.
398        child_node = BookmarkChangeProcessor::CreateBookmarkNode(
399            &sync_child_node, parent_node, bookmark_model_, index);
400      }
401      Associate(child_node, sync_child_id);
402      if (sync_child_node.GetIsFolder())
403        dfs_stack.push(sync_child_id);
404
405      sync_child_id = sync_child_node.GetSuccessorId();
406      ++index;
407    }
408
409    // At this point all the children nodes of the parent sync node have
410    // corresponding children in the parent bookmark node and they are all in
411    // the right positions: from 0 to index - 1.
412    // So the children starting from index in the parent bookmark node are the
413    // ones that are not present in the parent sync node. So create them.
414    for (int i = index; i < parent_node->child_count(); ++i) {
415      sync_child_id = BookmarkChangeProcessor::CreateSyncNode(
416          parent_node, bookmark_model_, i, &trans, this,
417          unrecoverable_error_handler_);
418      if (parent_node->GetChild(i)->is_folder())
419        dfs_stack.push(sync_child_id);
420      number_of_new_sync_nodes_created_at_association_++;
421    }
422  }
423
424  return true;
425}
426
427void BookmarkModelAssociator::PostPersistAssociationsTask() {
428  // No need to post a task if a task is already pending.
429  if (!persist_associations_.empty())
430    return;
431  MessageLoop::current()->PostTask(
432      FROM_HERE,
433      persist_associations_.NewRunnableMethod(
434          &BookmarkModelAssociator::PersistAssociations));
435}
436
437void BookmarkModelAssociator::PersistAssociations() {
438  // If there are no dirty associations we have nothing to do. We handle this
439  // explicity instead of letting the for loop do it to avoid creating a write
440  // transaction in this case.
441  if (dirty_associations_sync_ids_.empty()) {
442    DCHECK(id_map_.empty());
443    DCHECK(id_map_inverse_.empty());
444    return;
445  }
446
447  sync_api::WriteTransaction trans(user_share_);
448  DirtyAssociationsSyncIds::iterator iter;
449  for (iter = dirty_associations_sync_ids_.begin();
450       iter != dirty_associations_sync_ids_.end();
451       ++iter) {
452    int64 sync_id = *iter;
453    sync_api::WriteNode sync_node(&trans);
454    if (!sync_node.InitByIdLookup(sync_id)) {
455      unrecoverable_error_handler_->OnUnrecoverableError(FROM_HERE,
456          "Could not lookup bookmark node for ID persistence.");
457      return;
458    }
459    const BookmarkNode* node = GetChromeNodeFromSyncId(sync_id);
460    if (node)
461      sync_node.SetExternalId(node->id());
462    else
463      NOTREACHED();
464  }
465  dirty_associations_sync_ids_.clear();
466}
467
468bool BookmarkModelAssociator::LoadAssociations() {
469  DCHECK(bookmark_model_->IsLoaded());
470  // If the bookmarks changed externally, our previous associations may not be
471  // valid; so return false.
472  if (bookmark_model_->file_changed())
473    return false;
474
475  // Our persisted associations should be valid. Try to populate id association
476  // maps using persisted associations.  Note that the unit tests will
477  // create the tagged nodes on demand, and the order in which we probe for
478  // them here will impact their positional ordering in that case.
479  int64 bookmark_bar_id;
480  if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_id)) {
481    // We should always be able to find the permanent nodes.
482    return false;
483  }
484  int64 other_bookmarks_id;
485  if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_id)) {
486    // We should always be able to find the permanent nodes.
487    return false;
488  }
489
490  // Build a bookmark node ID index since we are going to repeatedly search for
491  // bookmark nodes by their IDs.
492  BookmarkNodeIdIndex id_index;
493  id_index.AddAll(bookmark_model_->GetBookmarkBarNode());
494  id_index.AddAll(bookmark_model_->other_node());
495
496  std::stack<int64> dfs_stack;
497  dfs_stack.push(other_bookmarks_id);
498  dfs_stack.push(bookmark_bar_id);
499
500  sync_api::ReadTransaction trans(user_share_);
501
502  // Count total number of nodes in sync model so that we can compare that
503  // with the total number of nodes in the bookmark model.
504  size_t sync_node_count = 0;
505  while (!dfs_stack.empty()) {
506    int64 parent_id = dfs_stack.top();
507    dfs_stack.pop();
508    ++sync_node_count;
509    sync_api::ReadNode sync_parent(&trans);
510    if (!sync_parent.InitByIdLookup(parent_id)) {
511      return false;
512    }
513
514    int64 external_id = sync_parent.GetExternalId();
515    if (external_id == 0)
516      return false;
517
518    const BookmarkNode* node = id_index.Find(external_id);
519    if (!node)
520      return false;
521
522    // Don't try to call NodesMatch on permanent nodes like bookmark bar and
523    // other bookmarks. They are not expected to match.
524    if (node != bookmark_model_->GetBookmarkBarNode() &&
525        node != bookmark_model_->other_node() &&
526        !NodesMatch(node, &sync_parent))
527      return false;
528
529    Associate(node, sync_parent.GetId());
530
531    // Add all children of the current node to the stack.
532    int64 child_id = sync_parent.GetFirstChildId();
533    while (child_id != sync_api::kInvalidId) {
534      dfs_stack.push(child_id);
535      sync_api::ReadNode child_node(&trans);
536      if (!child_node.InitByIdLookup(child_id)) {
537        return false;
538      }
539      child_id = child_node.GetSuccessorId();
540    }
541  }
542  DCHECK(dfs_stack.empty());
543
544  // It's possible that the number of nodes in the bookmark model is not the
545  // same as number of nodes in the sync model. This can happen when the sync
546  // model doesn't get a chance to persist its changes, for example when
547  // Chrome does not shut down gracefully. In such cases we can't trust the
548  // loaded associations.
549  return sync_node_count == id_index.count();
550}
551
552bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
553  // We only access the cryptographer while holding a transaction.
554  sync_api::ReadTransaction trans(user_share_);
555  const syncable::ModelTypeSet& encrypted_types =
556      GetEncryptedDataTypes(trans.GetWrappedTrans());
557  return encrypted_types.count(syncable::BOOKMARKS) == 0 ||
558      trans.GetCryptographer()->is_ready();
559}
560
561}  // namespace browser_sync
562