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.
5 #include "chrome/browser/sync/glue/bookmark_model_associator.h"
8 #include "base/command_line.h"
9 #include "base/containers/hash_tables.h"
10 #include "base/format_macros.h"
11 #include "base/location.h"
12 #include "base/macros.h"
13 #include "base/metrics/field_trial.h"
14 #include "base/single_thread_task_runner.h"
15 #include "base/strings/string_number_conversions.h"
16 #include "base/strings/string_util.h"
17 #include "base/strings/stringprintf.h"
18 #include "base/strings/utf_string_conversions.h"
19 #include "base/thread_task_runner_handle.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_factory.h"
23 #include "components/bookmarks/browser/bookmark_client.h"
24 #include "components/bookmarks/browser/bookmark_model.h"
25 #include "components/undo/bookmark_undo_service.h"
26 #include "components/undo/bookmark_undo_utils.h"
27 #include "content/public/browser/browser_thread.h"
28 #include "sync/api/sync_error.h"
29 #include "sync/api/sync_merge_result.h"
30 #include "sync/internal_api/public/delete_journal.h"
31 #include "sync/internal_api/public/read_node.h"
32 #include "sync/internal_api/public/read_transaction.h"
33 #include "sync/internal_api/public/write_node.h"
34 #include "sync/internal_api/public/write_transaction.h"
35 #include "sync/internal_api/syncapi_internal.h"
36 #include "sync/syncable/entry.h"
37 #include "sync/syncable/syncable_write_transaction.h"
38 #include "sync/util/cryptographer.h"
39 #include "sync/util/data_type_histogram.h"
41 using bookmarks::BookmarkModel
;
42 using bookmarks::BookmarkNode
;
43 using content::BrowserThread
;
45 namespace browser_sync
{
47 // The sync protocol identifies top-level entities by means of well-known tags,
48 // which should not be confused with titles. Each tag corresponds to a
49 // singleton instance of a particular top-level node in a user's share; the
50 // tags are consistent across users. The tags allow us to locate the specific
51 // folders whose contents we care about synchronizing, without having to do a
52 // lookup by name or path. The tags should not be made user-visible.
53 // For example, the tag "bookmark_bar" represents the permanent node for
54 // bookmarks bar in Chrome. The tag "other_bookmarks" represents the permanent
55 // folder Other Bookmarks in Chrome.
57 // It is the responsibility of something upstream (at time of writing,
58 // the sync server) to create these tagged nodes when initializing sync
59 // for the first time for a user. Thus, once the backend finishes
60 // initializing, the ProfileSyncService can rely on the presence of tagged
63 // TODO(ncarter): Pull these tags from an external protocol specification
64 // rather than hardcoding them here.
65 const char kBookmarkBarTag
[] = "bookmark_bar";
66 const char kMobileBookmarksTag
[] = "synced_bookmarks";
67 const char kOtherBookmarksTag
[] = "other_bookmarks";
69 // Maximum number of bytes to allow in a title (must match sync's internal
70 // limits; see write_node.cc).
71 const int kTitleLimitBytes
= 255;
73 // TODO(stanisc): crbug.com/456876: Remove this once the optimistic association
74 // experiment has ended.
75 bool IsOptimisticAssociationEnabled() {
76 const std::string group_name
=
77 base::FieldTrialList::FindFullName("SyncOptimisticBookmarkAssociation");
78 return group_name
== "Enabled";
81 // Provides the following abstraction: given a parent bookmark node, find best
82 // matching child node for many sync nodes.
83 class BookmarkNodeFinder
{
85 // Creates an instance with the given parent bookmark node.
86 explicit BookmarkNodeFinder(const BookmarkNode
* parent_node
);
88 // Finds the bookmark node that matches the given url, title and folder
89 // attribute. Returns the matching node if one exists; NULL otherwise.
90 // If there are multiple matches then a node with ID matching |preferred_id|
91 // is returned; otherwise the first matching node is returned.
92 // If a matching node is found, it's removed for further matches.
93 const BookmarkNode
* FindBookmarkNode(const GURL
& url
,
94 const std::string
& title
,
98 // Returns true if |bookmark_node| matches the specified |url|,
99 // |title|, and |is_folder| flags.
100 static bool NodeMatches(const BookmarkNode
* bookmark_node
,
102 const std::string
& title
,
106 // Maps bookmark node titles to instances, duplicates allowed.
107 // Titles are converted to the sync internal format before
108 // being used as keys for the map.
109 typedef base::hash_multimap
<std::string
,
110 const BookmarkNode
*> BookmarkNodeMap
;
111 typedef std::pair
<BookmarkNodeMap::iterator
,
112 BookmarkNodeMap::iterator
> BookmarkNodeRange
;
114 // Converts and truncates bookmark titles in the form sync does internally
115 // to avoid mismatches due to sync munging titles.
116 static void ConvertTitleToSyncInternalFormat(const std::string
& input
,
117 std::string
* output
);
119 const BookmarkNode
* parent_node_
;
120 BookmarkNodeMap child_nodes_
;
122 DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder
);
125 class ScopedAssociationUpdater
{
127 explicit ScopedAssociationUpdater(BookmarkModel
* model
) {
129 model
->BeginExtensiveChanges();
132 ~ScopedAssociationUpdater() {
133 model_
->EndExtensiveChanges();
137 BookmarkModel
* model_
;
139 DISALLOW_COPY_AND_ASSIGN(ScopedAssociationUpdater
);
142 BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode
* parent_node
)
143 : parent_node_(parent_node
) {
144 for (int i
= 0; i
< parent_node_
->child_count(); ++i
) {
145 const BookmarkNode
* child_node
= parent_node_
->GetChild(i
);
147 std::string title
= base::UTF16ToUTF8(child_node
->GetTitle());
148 ConvertTitleToSyncInternalFormat(title
, &title
);
150 child_nodes_
.insert(std::make_pair(title
, child_node
));
154 const BookmarkNode
* BookmarkNodeFinder::FindBookmarkNode(
156 const std::string
& title
,
158 int64 preferred_id
) {
159 const BookmarkNode
* match
= nullptr;
161 // First lookup a range of bookmarks with the same title.
162 std::string adjusted_title
;
163 ConvertTitleToSyncInternalFormat(title
, &adjusted_title
);
164 BookmarkNodeRange range
= child_nodes_
.equal_range(adjusted_title
);
165 BookmarkNodeMap::iterator match_iter
= range
.second
;
166 for (BookmarkNodeMap::iterator iter
= range
.first
;
167 iter
!= range
.second
;
169 // Then within the range match the node by the folder bit
171 const BookmarkNode
* node
= iter
->second
;
172 if (is_folder
== node
->is_folder() && url
== node
->url()) {
173 if (node
->id() == preferred_id
|| preferred_id
== 0) {
174 // Preferred match - use this node.
178 } else if (match
== nullptr) {
179 // First match - continue iterating.
186 if (match_iter
!= range
.second
) {
187 // Remove the matched node so we don't match with it again.
188 child_nodes_
.erase(match_iter
);
195 bool BookmarkNodeFinder::NodeMatches(const BookmarkNode
* bookmark_node
,
197 const std::string
& title
,
199 if (url
!= bookmark_node
->url() || is_folder
!= bookmark_node
->is_folder()) {
203 // The title passed to this method comes from a sync directory entry.
204 // The following two lines are needed to make the native bookmark title
205 // comparable. The same conversion is used in BookmarkNodeFinder constructor.
206 std::string bookmark_title
= base::UTF16ToUTF8(bookmark_node
->GetTitle());
207 ConvertTitleToSyncInternalFormat(bookmark_title
, &bookmark_title
);
208 return title
== bookmark_title
;
212 void BookmarkNodeFinder::ConvertTitleToSyncInternalFormat(
213 const std::string
& input
, std::string
* output
) {
214 syncer::SyncAPINameToServerName(input
, output
);
215 base::TruncateUTF8ToByteSize(*output
, kTitleLimitBytes
, output
);
218 BookmarkModelAssociator::Context::Context(
219 syncer::SyncMergeResult
* local_merge_result
,
220 syncer::SyncMergeResult
* syncer_merge_result
)
221 : local_merge_result_(local_merge_result
),
222 syncer_merge_result_(syncer_merge_result
),
224 native_model_sync_state_(UNSET
),
225 id_index_initialized_(false) {
228 BookmarkModelAssociator::Context::~Context() {
231 void BookmarkModelAssociator::Context::PushNode(int64 sync_id
) {
232 dfs_stack_
.push(sync_id
);
235 bool BookmarkModelAssociator::Context::PopNode(int64
* sync_id
) {
236 if (dfs_stack_
.empty()) {
240 *sync_id
= dfs_stack_
.top();
245 void BookmarkModelAssociator::Context::SetPreAssociationVersions(
246 int64 native_version
,
247 int64 sync_version
) {
248 local_merge_result_
->set_pre_association_version(native_version
);
249 syncer_merge_result_
->set_pre_association_version(sync_version
);
252 void BookmarkModelAssociator::Context::SetNumItemsBeforeAssociation(
255 local_merge_result_
->set_num_items_before_association(local_num
);
256 syncer_merge_result_
->set_num_items_before_association(sync_num
);
259 void BookmarkModelAssociator::Context::SetNumItemsAfterAssociation(
262 local_merge_result_
->set_num_items_after_association(local_num
);
263 syncer_merge_result_
->set_num_items_after_association(sync_num
);
266 void BookmarkModelAssociator::Context::IncrementLocalItemsDeleted() {
267 local_merge_result_
->set_num_items_deleted(
268 local_merge_result_
->num_items_deleted() + 1);
271 void BookmarkModelAssociator::Context::IncrementLocalItemsAdded() {
272 local_merge_result_
->set_num_items_added(
273 local_merge_result_
->num_items_added() + 1);
276 void BookmarkModelAssociator::Context::IncrementLocalItemsModified() {
277 local_merge_result_
->set_num_items_modified(
278 local_merge_result_
->num_items_modified() + 1);
281 void BookmarkModelAssociator::Context::IncrementSyncItemsAdded() {
282 syncer_merge_result_
->set_num_items_added(
283 syncer_merge_result_
->num_items_added() + 1);
286 void BookmarkModelAssociator::Context::IncrementSyncItemsDeleted(int count
) {
287 syncer_merge_result_
->set_num_items_deleted(
288 syncer_merge_result_
->num_items_deleted() + count
);
291 void BookmarkModelAssociator::Context::UpdateDuplicateCount(
292 const base::string16
& title
,
294 // base::Hash is defined for 8-byte strings only so have to
295 // cast the title data to char* and double the length in order to
297 size_t bookmark_hash
= base::Hash(reinterpret_cast<const char*>(title
.data()),
298 title
.length() * 2) ^
299 base::Hash(url
.spec());
301 if (!hashes_
.insert(bookmark_hash
).second
) {
302 // This hash code already exists in the set.
307 void BookmarkModelAssociator::Context::AddBookmarkRoot(
308 const bookmarks::BookmarkNode
* root
) {
309 bookmark_roots_
.push_back(root
);
312 void BookmarkModelAssociator::Context::BuildIdIndex() {
313 DCHECK(!id_index_initialized_
);
315 for (BookmarkList::const_iterator it
= bookmark_roots_
.begin();
316 it
!= bookmark_roots_
.end(); ++it
) {
320 while (!stack
.empty()) {
321 const BookmarkNode
* parent
= stack
.top();
323 DCHECK(parent
->is_folder());
324 for (int i
= 0; i
< parent
->child_count(); ++i
) {
325 const BookmarkNode
* node
= parent
->GetChild(i
);
326 DCHECK(id_index_
.find(node
->id()) == id_index_
.end());
327 id_index_
.insert(std::make_pair(node
->id(), node
));
328 if (node
->is_folder())
333 id_index_initialized_
= true;
336 const BookmarkNode
* BookmarkModelAssociator::Context::LookupNodeInIdIndex(
338 if (!id_index_initialized_
) {
339 // Build the index on demand.
340 DCHECK(!bookmark_roots_
.empty());
344 IdIndex::const_iterator it
= id_index_
.find(native_id
);
345 if (it
== id_index_
.end())
350 void BookmarkModelAssociator::Context::MarkForVersionUpdate(
351 const bookmarks::BookmarkNode
* node
) {
352 bookmarks_for_version_update_
.push_back(node
);
355 BookmarkModelAssociator::BookmarkModelAssociator(
356 BookmarkModel
* bookmark_model
,
358 syncer::UserShare
* user_share
,
359 sync_driver::DataTypeErrorHandler
* unrecoverable_error_handler
,
360 bool expect_mobile_bookmarks_folder
)
361 : bookmark_model_(bookmark_model
),
363 user_share_(user_share
),
364 unrecoverable_error_handler_(unrecoverable_error_handler
),
365 expect_mobile_bookmarks_folder_(expect_mobile_bookmarks_folder
),
366 optimistic_association_enabled_(IsOptimisticAssociationEnabled()),
367 weak_factory_(this) {
368 DCHECK_CURRENTLY_ON(BrowserThread::UI
);
369 DCHECK(bookmark_model_
);
371 DCHECK(unrecoverable_error_handler_
);
374 BookmarkModelAssociator::~BookmarkModelAssociator() {
375 DCHECK_CURRENTLY_ON(BrowserThread::UI
);
378 void BookmarkModelAssociator::UpdatePermanentNodeVisibility() {
379 DCHECK_CURRENTLY_ON(BrowserThread::UI
);
380 DCHECK(bookmark_model_
->loaded());
382 BookmarkNode::Type bookmark_node_types
[] = {
383 BookmarkNode::BOOKMARK_BAR
,
384 BookmarkNode::OTHER_NODE
,
385 BookmarkNode::MOBILE
,
387 for (size_t i
= 0; i
< arraysize(bookmark_node_types
); ++i
) {
388 int64 id
= bookmark_model_
->PermanentNode(bookmark_node_types
[i
])->id();
389 bookmark_model_
->SetPermanentNodeVisible(
390 bookmark_node_types
[i
],
391 id_map_
.find(id
) != id_map_
.end());
394 // Note: the root node may have additional extra nodes. Currently their
395 // visibility is not affected by sync.
398 syncer::SyncError
BookmarkModelAssociator::DisassociateModels() {
400 id_map_inverse_
.clear();
401 dirty_associations_sync_ids_
.clear();
402 return syncer::SyncError();
405 int64
BookmarkModelAssociator::GetSyncIdFromChromeId(const int64
& node_id
) {
406 BookmarkIdToSyncIdMap::const_iterator iter
= id_map_
.find(node_id
);
407 return iter
== id_map_
.end() ? syncer::kInvalidId
: iter
->second
;
410 const BookmarkNode
* BookmarkModelAssociator::GetChromeNodeFromSyncId(
412 SyncIdToBookmarkNodeMap::const_iterator iter
= id_map_inverse_
.find(sync_id
);
413 return iter
== id_map_inverse_
.end() ? NULL
: iter
->second
;
416 bool BookmarkModelAssociator::InitSyncNodeFromChromeId(
417 const int64
& node_id
,
418 syncer::BaseNode
* sync_node
) {
420 int64 sync_id
= GetSyncIdFromChromeId(node_id
);
421 if (sync_id
== syncer::kInvalidId
)
423 if (sync_node
->InitByIdLookup(sync_id
) != syncer::BaseNode::INIT_OK
)
425 DCHECK(sync_node
->GetId() == sync_id
);
429 void BookmarkModelAssociator::AddAssociation(const BookmarkNode
* node
,
431 DCHECK_CURRENTLY_ON(BrowserThread::UI
);
432 int64 node_id
= node
->id();
433 DCHECK_NE(sync_id
, syncer::kInvalidId
);
434 DCHECK(id_map_
.find(node_id
) == id_map_
.end());
435 DCHECK(id_map_inverse_
.find(sync_id
) == id_map_inverse_
.end());
436 id_map_
[node_id
] = sync_id
;
437 id_map_inverse_
[sync_id
] = node
;
440 void BookmarkModelAssociator::Associate(const BookmarkNode
* node
,
441 const syncer::BaseNode
& sync_node
) {
442 AddAssociation(node
, sync_node
.GetId());
444 // TODO(stanisc): crbug.com/456876: consider not doing this on every single
446 UpdatePermanentNodeVisibility();
448 // The same check exists in PersistAssociations. However it is better to
449 // do the check earlier to avoid the cost of decrypting nodes again
450 // in PersistAssociations.
451 if (node
->id() != sync_node
.GetExternalId()) {
452 dirty_associations_sync_ids_
.insert(sync_node
.GetId());
453 PostPersistAssociationsTask();
457 void BookmarkModelAssociator::Disassociate(int64 sync_id
) {
458 DCHECK_CURRENTLY_ON(BrowserThread::UI
);
459 SyncIdToBookmarkNodeMap::iterator iter
= id_map_inverse_
.find(sync_id
);
460 if (iter
== id_map_inverse_
.end())
462 id_map_
.erase(iter
->second
->id());
463 id_map_inverse_
.erase(iter
);
464 dirty_associations_sync_ids_
.erase(sync_id
);
467 bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes
) {
470 bool has_mobile_folder
= true;
472 syncer::ReadTransaction
trans(FROM_HERE
, user_share_
);
474 syncer::ReadNode
bookmark_bar_node(&trans
);
475 if (bookmark_bar_node
.InitByTagLookupForBookmarks(kBookmarkBarTag
) !=
476 syncer::BaseNode::INIT_OK
) {
480 syncer::ReadNode
other_bookmarks_node(&trans
);
481 if (other_bookmarks_node
.InitByTagLookupForBookmarks(kOtherBookmarksTag
) !=
482 syncer::BaseNode::INIT_OK
) {
486 syncer::ReadNode
mobile_bookmarks_node(&trans
);
487 if (mobile_bookmarks_node
.InitByTagLookupForBookmarks(kMobileBookmarksTag
) !=
488 syncer::BaseNode::INIT_OK
) {
489 has_mobile_folder
= false;
492 // Sync model has user created nodes if any of the permanent nodes has
494 *has_nodes
= bookmark_bar_node
.HasChildren() ||
495 other_bookmarks_node
.HasChildren() ||
496 (has_mobile_folder
&& mobile_bookmarks_node
.HasChildren());
500 bool BookmarkModelAssociator::AssociateTaggedPermanentNode(
501 syncer::BaseTransaction
* trans
,
502 const BookmarkNode
* permanent_node
,
503 const std::string
& tag
) {
504 // Do nothing if |permanent_node| is already initialized and associated.
505 int64 sync_id
= GetSyncIdFromChromeId(permanent_node
->id());
506 if (sync_id
!= syncer::kInvalidId
)
509 syncer::ReadNode
sync_node(trans
);
510 if (sync_node
.InitByTagLookupForBookmarks(tag
) != syncer::BaseNode::INIT_OK
)
513 Associate(permanent_node
, sync_node
);
517 syncer::SyncError
BookmarkModelAssociator::AssociateModels(
518 syncer::SyncMergeResult
* local_merge_result
,
519 syncer::SyncMergeResult
* syncer_merge_result
) {
520 // Since any changes to the bookmark model made here are not user initiated,
521 // these change should not be undoable and so suspend the undo tracking.
522 ScopedSuspendBookmarkUndo
suspend_undo(
523 BookmarkUndoServiceFactory::GetForProfileIfExists(profile_
));
525 Context
context(local_merge_result
, syncer_merge_result
);
527 syncer::SyncError error
= CheckModelSyncState(&context
);
531 scoped_ptr
<ScopedAssociationUpdater
> association_updater(
532 new ScopedAssociationUpdater(bookmark_model_
));
533 DisassociateModels();
535 error
= BuildAssociations(&context
);
537 // Clear version on bookmark model so that the conservative association
538 // algorithm is used on the next association.
539 bookmark_model_
->SetNodeSyncTransactionVersion(
540 bookmark_model_
->root_node(),
541 syncer::syncable::kInvalidTransactionVersion
);
547 syncer::SyncError
BookmarkModelAssociator::AssociatePermanentFolders(
548 syncer::BaseTransaction
* trans
,
550 // To prime our association, we associate the top-level nodes, Bookmark Bar
551 // and Other Bookmarks.
552 if (!AssociateTaggedPermanentNode(trans
, bookmark_model_
->bookmark_bar_node(),
554 return unrecoverable_error_handler_
->CreateAndUploadError(
555 FROM_HERE
, "Bookmark bar node not found", model_type());
558 if (!AssociateTaggedPermanentNode(trans
, bookmark_model_
->other_node(),
559 kOtherBookmarksTag
)) {
560 return unrecoverable_error_handler_
->CreateAndUploadError(
561 FROM_HERE
, "Other bookmarks node not found", model_type());
564 if (!AssociateTaggedPermanentNode(trans
, bookmark_model_
->mobile_node(),
565 kMobileBookmarksTag
) &&
566 expect_mobile_bookmarks_folder_
) {
567 return unrecoverable_error_handler_
->CreateAndUploadError(
568 FROM_HERE
, "Mobile bookmarks node not found", model_type());
571 // Note: the root node may have additional extra nodes. Currently none of
572 // them are meant to sync.
573 int64 bookmark_bar_sync_id
=
574 GetSyncIdFromChromeId(bookmark_model_
->bookmark_bar_node()->id());
575 DCHECK_NE(bookmark_bar_sync_id
, syncer::kInvalidId
);
576 context
->AddBookmarkRoot(bookmark_model_
->bookmark_bar_node());
577 int64 other_bookmarks_sync_id
=
578 GetSyncIdFromChromeId(bookmark_model_
->other_node()->id());
579 DCHECK_NE(other_bookmarks_sync_id
, syncer::kInvalidId
);
580 context
->AddBookmarkRoot(bookmark_model_
->other_node());
581 int64 mobile_bookmarks_sync_id
=
582 GetSyncIdFromChromeId(bookmark_model_
->mobile_node()->id());
583 if (expect_mobile_bookmarks_folder_
)
584 DCHECK_NE(syncer::kInvalidId
, mobile_bookmarks_sync_id
);
585 if (mobile_bookmarks_sync_id
!= syncer::kInvalidId
)
586 context
->AddBookmarkRoot(bookmark_model_
->mobile_node());
588 // WARNING: The order in which we push these should match their order in the
589 // bookmark model (see BookmarkModel::DoneLoading(..)).
590 context
->PushNode(bookmark_bar_sync_id
);
591 context
->PushNode(other_bookmarks_sync_id
);
592 if (mobile_bookmarks_sync_id
!= syncer::kInvalidId
)
593 context
->PushNode(mobile_bookmarks_sync_id
);
595 return syncer::SyncError();
598 void BookmarkModelAssociator::SetNumItemsBeforeAssociation(
599 syncer::BaseTransaction
* trans
,
602 syncer::ReadNode
bm_root(trans
);
603 if (bm_root
.InitTypeRoot(syncer::BOOKMARKS
) == syncer::BaseNode::INIT_OK
) {
604 syncer_num
= bm_root
.GetTotalNodeCount();
606 context
->SetNumItemsBeforeAssociation(
607 GetTotalBookmarkCountAndRecordDuplicates(bookmark_model_
->root_node(),
612 int BookmarkModelAssociator::GetTotalBookmarkCountAndRecordDuplicates(
613 const bookmarks::BookmarkNode
* node
,
614 Context
* context
) const {
615 int count
= 1; // Start with one to include the node itself.
617 if (!node
->is_root()) {
618 context
->UpdateDuplicateCount(node
->GetTitle(), node
->url());
621 for (int i
= 0; i
< node
->child_count(); ++i
) {
623 GetTotalBookmarkCountAndRecordDuplicates(node
->GetChild(i
), context
);
629 void BookmarkModelAssociator::SetNumItemsAfterAssociation(
630 syncer::BaseTransaction
* trans
,
633 syncer::ReadNode
bm_root(trans
);
634 if (bm_root
.InitTypeRoot(syncer::BOOKMARKS
) == syncer::BaseNode::INIT_OK
) {
635 syncer_num
= bm_root
.GetTotalNodeCount();
637 context
->SetNumItemsAfterAssociation(
638 bookmark_model_
->root_node()->GetTotalNodeCount(), syncer_num
);
641 syncer::SyncError
BookmarkModelAssociator::BuildAssociations(Context
* context
) {
642 DCHECK(bookmark_model_
->loaded());
643 DCHECK_NE(context
->native_model_sync_state(), AHEAD
);
645 int initial_duplicate_count
= 0;
646 int64 new_version
= syncer::syncable::kInvalidTransactionVersion
;
648 syncer::WriteTransaction
trans(FROM_HERE
, user_share_
, &new_version
);
650 syncer::SyncError error
= AssociatePermanentFolders(&trans
, context
);
654 SetNumItemsBeforeAssociation(&trans
, context
);
655 initial_duplicate_count
= context
->duplicate_count();
657 // Remove obsolete bookmarks according to sync delete journal.
658 // TODO(stanisc): crbug.com/456876: rewrite this to avoid a separate
659 // traversal and instead perform deletes at the end of the loop below where
660 // the unmatched bookmark nodes are created as sync nodes.
661 ApplyDeletesFromSyncJournal(&trans
, context
);
663 // Algorithm description:
664 // Match up the roots and recursively do the following:
665 // * For each sync node for the current sync parent node, find the best
666 // matching bookmark node under the corresponding bookmark parent node.
667 // If no matching node is found, create a new bookmark node in the same
668 // position as the corresponding sync node.
669 // If a matching node is found, update the properties of it from the
670 // corresponding sync node.
671 // * When all children sync nodes are done, add the extra children bookmark
672 // nodes to the sync parent node.
674 // The best match algorithm uses folder title or bookmark title/url to
675 // perform the primary match. If there are multiple match candidates it
676 // selects the preferred one based on sync node external ID match to the
677 // bookmark folder ID.
678 int64 sync_parent_id
;
679 while (context
->PopNode(&sync_parent_id
)) {
680 syncer::ReadNode
sync_parent(&trans
);
681 if (sync_parent
.InitByIdLookup(sync_parent_id
) !=
682 syncer::BaseNode::INIT_OK
) {
683 return unrecoverable_error_handler_
->CreateAndUploadError(
684 FROM_HERE
, "Failed to lookup node.", model_type());
686 // Only folder nodes are pushed on to the stack.
687 DCHECK(sync_parent
.GetIsFolder());
689 const BookmarkNode
* parent_node
= GetChromeNodeFromSyncId(sync_parent_id
);
691 return unrecoverable_error_handler_
->CreateAndUploadError(
692 FROM_HERE
, "Failed to find bookmark node for sync id.",
695 DCHECK(parent_node
->is_folder());
697 std::vector
<int64
> children
;
698 sync_parent
.GetChildIds(&children
);
700 if (optimistic_association_enabled_
&&
701 context
->native_model_sync_state() == IN_SYNC
) {
702 // Optimistic case where based on the version check there shouldn't
703 // be any new sync changes.
705 BuildAssociationsOptimistic(&trans
, parent_node
, children
, context
);
707 error
= BuildAssociations(&trans
, parent_node
, children
, context
);
713 SetNumItemsAfterAssociation(&trans
, context
);
716 BookmarkChangeProcessor::UpdateTransactionVersion(
717 new_version
, bookmark_model_
, context
->bookmarks_for_version_update());
719 UMA_HISTOGRAM_COUNTS("Sync.BookmarksDuplicationsAtAssociation",
720 context
->duplicate_count());
721 UMA_HISTOGRAM_COUNTS("Sync.BookmarksNewDuplicationsAtAssociation",
722 context
->duplicate_count() - initial_duplicate_count
);
724 if (context
->duplicate_count() > initial_duplicate_count
) {
725 UMA_HISTOGRAM_ENUMERATION("Sync.BookmarksModelSyncStateAtNewDuplication",
726 context
->native_model_sync_state(),
727 NATIVE_MODEL_SYNC_STATE_COUNT
);
730 return syncer::SyncError();
733 syncer::SyncError
BookmarkModelAssociator::BuildAssociations(
734 syncer::WriteTransaction
* trans
,
735 const BookmarkNode
* parent_node
,
736 const std::vector
<int64
>& sync_ids
,
738 BookmarkNodeFinder
node_finder(parent_node
);
741 for (std::vector
<int64
>::const_iterator it
= sync_ids
.begin();
742 it
!= sync_ids
.end(); ++it
) {
743 int64 sync_child_id
= *it
;
744 syncer::ReadNode
sync_child_node(trans
);
745 if (sync_child_node
.InitByIdLookup(sync_child_id
) !=
746 syncer::BaseNode::INIT_OK
) {
747 return unrecoverable_error_handler_
->CreateAndUploadError(
748 FROM_HERE
, "Failed to lookup node.", model_type());
751 GURL
url(sync_child_node
.GetBookmarkSpecifics().url());
752 const BookmarkNode
* child_node
= node_finder
.FindBookmarkNode(
753 url
, sync_child_node
.GetTitle(), sync_child_node
.GetIsFolder(),
754 sync_child_node
.GetExternalId());
756 // All bookmarks are currently modified at association time, even if
757 // nothing has changed.
758 // TODO(sync): Only modify the bookmark model if necessary.
759 BookmarkChangeProcessor::UpdateBookmarkWithSyncData(
760 sync_child_node
, bookmark_model_
, child_node
, profile_
);
761 bookmark_model_
->Move(child_node
, parent_node
, index
);
762 context
->IncrementLocalItemsModified();
764 syncer::SyncError error
;
765 child_node
= CreateBookmarkNode(parent_node
, index
, &sync_child_node
, url
,
771 // Skip this node and continue. Don't increment index in this case.
775 context
->IncrementLocalItemsAdded();
778 Associate(child_node
, sync_child_node
);
779 // All bookmarks are marked for version update because
780 // all bookmarks are always updated with data. This could be optimized -
781 // see the note above.
782 context
->MarkForVersionUpdate(child_node
);
784 if (sync_child_node
.GetIsFolder())
785 context
->PushNode(sync_child_id
);
789 // At this point all the children nodes of the parent sync node have
790 // corresponding children in the parent bookmark node and they are all in
791 // the right positions: from 0 to index - 1.
792 // So the children starting from index in the parent bookmark node are the
793 // ones that are not present in the parent sync node. So create them.
794 for (int i
= index
; i
< parent_node
->child_count(); ++i
) {
795 int64 sync_child_id
= BookmarkChangeProcessor::CreateSyncNode(
796 parent_node
, bookmark_model_
, i
, trans
, this,
797 unrecoverable_error_handler_
);
798 if (syncer::kInvalidId
== sync_child_id
) {
799 return unrecoverable_error_handler_
->CreateAndUploadError(
800 FROM_HERE
, "Failed to create sync node.", model_type());
803 context
->IncrementSyncItemsAdded();
804 const BookmarkNode
* child_node
= parent_node
->GetChild(i
);
805 context
->MarkForVersionUpdate(child_node
);
806 if (child_node
->is_folder())
807 context
->PushNode(sync_child_id
);
810 return syncer::SyncError();
813 syncer::SyncError
BookmarkModelAssociator::BuildAssociationsOptimistic(
814 syncer::WriteTransaction
* trans
,
815 const BookmarkNode
* parent_node
,
816 const std::vector
<int64
>& sync_ids
,
818 BookmarkNodeFinder
node_finder(parent_node
);
820 // TODO(stanisc): crbug/456876: Review optimistic case specific logic here.
821 // This is the case when the transcation version of the native model
822 // matches the transaction version on the sync side.
823 // For now the logic is exactly the same as for the regular case with
824 // the exception of not propagating sync data for matching nodes.
826 for (std::vector
<int64
>::const_iterator it
= sync_ids
.begin();
827 it
!= sync_ids
.end(); ++it
) {
828 int64 sync_child_id
= *it
;
829 syncer::ReadNode
sync_child_node(trans
);
830 if (sync_child_node
.InitByIdLookup(sync_child_id
) !=
831 syncer::BaseNode::INIT_OK
) {
832 return unrecoverable_error_handler_
->CreateAndUploadError(
833 FROM_HERE
, "Failed to lookup node.", model_type());
836 int64 external_id
= sync_child_node
.GetExternalId();
837 GURL
url(sync_child_node
.GetBookmarkSpecifics().url());
838 const BookmarkNode
* child_node
= node_finder
.FindBookmarkNode(
839 url
, sync_child_node
.GetTitle(), sync_child_node
.GetIsFolder(),
842 // If the child node is matched assume it is in sync and skip
844 // TODO(stanisc): crbug/456876: Replace the code that moves
845 // the local node with the sync node reordering code.
846 // The local node has the correct position in this particular case,
847 // not the sync node.
848 if (parent_node
->GetChild(index
) != child_node
) {
849 bookmark_model_
->Move(child_node
, parent_node
, index
);
850 context
->IncrementLocalItemsModified();
853 if (external_id
!= 0) {
854 const BookmarkNode
* matching_node
=
855 context
->LookupNodeInIdIndex(external_id
);
857 // There is another matching node which means the local node
858 // has been either moved or edited.
859 // In this case assume the local model to be correct, delete the
860 // sync node, and let the matching node to be propagated to Sync.
861 // TODO(stanisc): crbug/456876: this should really be handled with
862 // a move, but the move depends on the traversal order.
863 int num
= RemoveSyncNodeHierarchy(trans
, sync_child_node
.GetId());
864 context
->IncrementSyncItemsDeleted(num
);
868 // Existing sync node isn't associated. This is unexpected during
869 // optimistic association unless there the previous association failed
871 // persist extern IDs (that might be the case because persisting
874 // Report this error only once per session.
875 static bool g_unmatched_unassociated_node_reported
= false;
876 if (!g_unmatched_unassociated_node_reported
) {
877 g_unmatched_unassociated_node_reported
= true;
878 unrecoverable_error_handler_
->CreateAndUploadError(
880 "Unassociated sync node detected during optimistic association",
885 syncer::SyncError error
;
886 child_node
= CreateBookmarkNode(parent_node
, index
, &sync_child_node
, url
,
892 // Skip this node and continue. Don't increment index in this case.
896 context
->IncrementLocalItemsAdded();
897 context
->MarkForVersionUpdate(child_node
);
900 Associate(child_node
, sync_child_node
);
902 if (sync_child_node
.GetIsFolder())
903 context
->PushNode(sync_child_id
);
907 // At this point all the children nodes of the parent sync node have
908 // corresponding children in the parent bookmark node and they are all in
909 // the right positions: from 0 to index - 1.
910 // So the children starting from index in the parent bookmark node are the
911 // ones that are not present in the parent sync node. So create them.
912 for (int i
= index
; i
< parent_node
->child_count(); ++i
) {
913 int64 sync_child_id
= BookmarkChangeProcessor::CreateSyncNode(
914 parent_node
, bookmark_model_
, i
, trans
, this,
915 unrecoverable_error_handler_
);
916 if (syncer::kInvalidId
== sync_child_id
) {
917 return unrecoverable_error_handler_
->CreateAndUploadError(
918 FROM_HERE
, "Failed to create sync node.", model_type());
920 context
->IncrementSyncItemsAdded();
921 const BookmarkNode
* child_node
= parent_node
->GetChild(i
);
922 context
->MarkForVersionUpdate(child_node
);
923 if (child_node
->is_folder())
924 context
->PushNode(sync_child_id
);
927 return syncer::SyncError();
930 const BookmarkNode
* BookmarkModelAssociator::CreateBookmarkNode(
931 const BookmarkNode
* parent_node
,
933 const syncer::BaseNode
* sync_child_node
,
936 syncer::SyncError
* error
) {
937 DCHECK_LE(bookmark_index
, parent_node
->child_count());
939 const std::string
& sync_title
= sync_child_node
->GetTitle();
941 if (!sync_child_node
->GetIsFolder() && !url
.is_valid()) {
942 unrecoverable_error_handler_
->CreateAndUploadError(
943 FROM_HERE
, "Cannot associate sync node " +
944 sync_child_node
->GetEntry()->GetId().value() +
945 " with invalid url " + url
.possibly_invalid_spec() +
946 " and title " + sync_title
,
948 // Don't propagate the error to the model_type in this case.
952 base::string16 bookmark_title
= base::UTF8ToUTF16(sync_title
);
953 const BookmarkNode
* child_node
= BookmarkChangeProcessor::CreateBookmarkNode(
954 bookmark_title
, url
, sync_child_node
, parent_node
, bookmark_model_
,
955 profile_
, bookmark_index
);
957 *error
= unrecoverable_error_handler_
->CreateAndUploadError(
958 FROM_HERE
, "Failed to create bookmark node with title " + sync_title
+
959 " and url " + url
.possibly_invalid_spec(),
964 context
->UpdateDuplicateCount(bookmark_title
, url
);
968 int BookmarkModelAssociator::RemoveSyncNodeHierarchy(
969 syncer::WriteTransaction
* trans
,
971 syncer::WriteNode
sync_node(trans
);
972 if (sync_node
.InitByIdLookup(sync_id
) != syncer::BaseNode::INIT_OK
) {
973 syncer::SyncError
error(FROM_HERE
, syncer::SyncError::DATATYPE_ERROR
,
974 "Could not lookup bookmark node for ID deletion.",
976 unrecoverable_error_handler_
->OnSingleDataTypeUnrecoverableError(error
);
980 return BookmarkChangeProcessor::RemoveSyncNodeHierarchy(trans
, &sync_node
,
985 FolderInfo(const BookmarkNode
* f
, const BookmarkNode
* p
, int64 id
)
986 : folder(f
), parent(p
), sync_id(id
) {}
987 const BookmarkNode
* folder
;
988 const BookmarkNode
* parent
;
991 typedef std::vector
<FolderInfo
> FolderInfoList
;
993 void BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
994 syncer::BaseTransaction
* trans
,
996 syncer::BookmarkDeleteJournalList bk_delete_journals
;
997 syncer::DeleteJournal::GetBookmarkDeleteJournals(trans
, &bk_delete_journals
);
998 if (bk_delete_journals
.empty())
1001 size_t num_journals_unmatched
= bk_delete_journals
.size();
1003 // Make a set of all external IDs in the delete journal,
1004 // ignore entries with unset external IDs.
1005 std::set
<int64
> journaled_external_ids
;
1006 for (size_t i
= 0; i
< num_journals_unmatched
; i
++) {
1007 if (bk_delete_journals
[i
].external_id
!= 0)
1008 journaled_external_ids
.insert(bk_delete_journals
[i
].external_id
);
1011 // Check bookmark model from top to bottom.
1012 BookmarkStack dfs_stack
;
1013 for (BookmarkList::const_iterator it
= context
->bookmark_roots().begin();
1014 it
!= context
->bookmark_roots().end(); ++it
) {
1015 dfs_stack
.push(*it
);
1018 // Remember folders that match delete journals in first pass but don't delete
1019 // them in case there are bookmarks left under them. After non-folder
1020 // bookmarks are removed in first pass, recheck the folders in reverse order
1021 // to remove empty ones.
1022 FolderInfoList folders_matched
;
1023 while (!dfs_stack
.empty() && num_journals_unmatched
> 0) {
1024 const BookmarkNode
* parent
= dfs_stack
.top();
1026 DCHECK(parent
->is_folder());
1028 // Enumerate folder children in reverse order to make it easier to remove
1029 // bookmarks matching entries in the delete journal.
1030 for (int child_index
= parent
->child_count() - 1;
1031 child_index
>= 0 && num_journals_unmatched
> 0; --child_index
) {
1032 const BookmarkNode
* child
= parent
->GetChild(child_index
);
1033 if (child
->is_folder())
1034 dfs_stack
.push(child
);
1036 if (journaled_external_ids
.find(child
->id()) ==
1037 journaled_external_ids
.end()) {
1038 // Skip bookmark node which id is not in the set of external IDs.
1042 // Iterate through the journal entries from back to front. Remove matched
1043 // journal by moving an unmatched entry at the tail to the matched
1044 // position so that we can read unmatched entries off the head in next
1046 for (int journal_index
= num_journals_unmatched
- 1; journal_index
>= 0;
1048 const syncer::BookmarkDeleteJournal
& delete_entry
=
1049 bk_delete_journals
[journal_index
];
1050 if (child
->id() == delete_entry
.external_id
&&
1051 BookmarkNodeFinder::NodeMatches(
1052 child
, GURL(delete_entry
.specifics
.bookmark().url()),
1053 delete_entry
.specifics
.bookmark().title(),
1054 delete_entry
.is_folder
)) {
1055 if (child
->is_folder()) {
1056 // Remember matched folder without removing and delete only empty
1058 folders_matched
.push_back(
1059 FolderInfo(child
, parent
, delete_entry
.id
));
1061 bookmark_model_
->Remove(child
);
1062 context
->IncrementLocalItemsDeleted();
1064 // Move unmatched journal here and decrement counter.
1065 bk_delete_journals
[journal_index
] =
1066 bk_delete_journals
[--num_journals_unmatched
];
1073 // Ids of sync nodes not found in bookmark model, meaning the deletions are
1074 // persisted and correponding delete journals can be dropped.
1075 std::set
<int64
> journals_to_purge
;
1077 // Remove empty folders from bottom to top.
1078 for (FolderInfoList::reverse_iterator it
= folders_matched
.rbegin();
1079 it
!= folders_matched
.rend(); ++it
) {
1080 if (it
->folder
->child_count() == 0) {
1081 bookmark_model_
->Remove(it
->folder
);
1082 context
->IncrementLocalItemsDeleted();
1084 // Keep non-empty folder and remove its journal so that it won't match
1085 // again in the future.
1086 journals_to_purge
.insert(it
->sync_id
);
1090 // Purge unmatched journals.
1091 for (size_t i
= 0; i
< num_journals_unmatched
; ++i
)
1092 journals_to_purge
.insert(bk_delete_journals
[i
].id
);
1093 syncer::DeleteJournal::PurgeDeleteJournals(trans
, journals_to_purge
);
1096 void BookmarkModelAssociator::PostPersistAssociationsTask() {
1097 // No need to post a task if a task is already pending.
1098 if (weak_factory_
.HasWeakPtrs())
1100 base::ThreadTaskRunnerHandle::Get()->PostTask(
1101 FROM_HERE
, base::Bind(&BookmarkModelAssociator::PersistAssociations
,
1102 weak_factory_
.GetWeakPtr()));
1105 void BookmarkModelAssociator::PersistAssociations() {
1106 // If there are no dirty associations we have nothing to do. We handle this
1107 // explicity instead of letting the for loop do it to avoid creating a write
1108 // transaction in this case.
1109 if (dirty_associations_sync_ids_
.empty()) {
1110 DCHECK(id_map_
.empty());
1111 DCHECK(id_map_inverse_
.empty());
1115 int64 new_version
= syncer::syncable::kInvalidTransactionVersion
;
1116 std::vector
<const BookmarkNode
*> bnodes
;
1118 syncer::WriteTransaction
trans(FROM_HERE
, user_share_
, &new_version
);
1119 DirtyAssociationsSyncIds::iterator iter
;
1120 for (iter
= dirty_associations_sync_ids_
.begin();
1121 iter
!= dirty_associations_sync_ids_
.end();
1123 int64 sync_id
= *iter
;
1124 syncer::WriteNode
sync_node(&trans
);
1125 if (sync_node
.InitByIdLookup(sync_id
) != syncer::BaseNode::INIT_OK
) {
1126 syncer::SyncError
error(
1128 syncer::SyncError::DATATYPE_ERROR
,
1129 "Could not lookup bookmark node for ID persistence.",
1131 unrecoverable_error_handler_
->OnSingleDataTypeUnrecoverableError(error
);
1134 const BookmarkNode
* node
= GetChromeNodeFromSyncId(sync_id
);
1135 if (node
&& sync_node
.GetExternalId() != node
->id()) {
1136 sync_node
.SetExternalId(node
->id());
1137 bnodes
.push_back(node
);
1140 dirty_associations_sync_ids_
.clear();
1143 BookmarkChangeProcessor::UpdateTransactionVersion(new_version
,
1148 bool BookmarkModelAssociator::CryptoReadyIfNecessary() {
1149 // We only access the cryptographer while holding a transaction.
1150 syncer::ReadTransaction
trans(FROM_HERE
, user_share_
);
1151 const syncer::ModelTypeSet encrypted_types
= trans
.GetEncryptedTypes();
1152 return !encrypted_types
.Has(syncer::BOOKMARKS
) ||
1153 trans
.GetCryptographer()->is_ready();
1156 syncer::SyncError
BookmarkModelAssociator::CheckModelSyncState(
1157 Context
* context
) const {
1158 DCHECK_EQ(context
->native_model_sync_state(), UNSET
);
1159 int64 native_version
=
1160 bookmark_model_
->root_node()->sync_transaction_version();
1161 if (native_version
!= syncer::syncable::kInvalidTransactionVersion
) {
1162 syncer::ReadTransaction
trans(FROM_HERE
, user_share_
);
1163 int64 sync_version
= trans
.GetModelVersion(syncer::BOOKMARKS
);
1164 context
->SetPreAssociationVersions(native_version
, sync_version
);
1166 if (native_version
== sync_version
) {
1167 context
->set_native_model_sync_state(IN_SYNC
);
1169 UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
1170 ModelTypeToHistogramInt(syncer::BOOKMARKS
),
1171 syncer::MODEL_TYPE_COUNT
);
1173 // Clear version on bookmark model so that we only report error once.
1174 bookmark_model_
->SetNodeSyncTransactionVersion(
1175 bookmark_model_
->root_node(),
1176 syncer::syncable::kInvalidTransactionVersion
);
1178 // If the native version is higher, there was a sync persistence failure,
1179 // and we need to delay association until after a GetUpdates.
1180 if (native_version
> sync_version
) {
1181 context
->set_native_model_sync_state(AHEAD
);
1182 std::string message
= base::StringPrintf(
1183 "Native version (%" PRId64
") does not match sync version (%"
1187 return syncer::SyncError(FROM_HERE
,
1188 syncer::SyncError::PERSISTENCE_ERROR
,
1192 context
->set_native_model_sync_state(BEHIND
);
1196 return syncer::SyncError();
1199 } // namespace browser_sync