1 // Copyright 2018 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "components/sync_bookmarks/bookmark_model_observer_impl.h"
10 #include "base/no_destructor.h"
11 #include "components/bookmarks/browser/bookmark_model.h"
12 #include "components/bookmarks/browser/bookmark_node.h"
13 #include "components/sync/base/hash_util.h"
14 #include "components/sync/base/unique_position.h"
15 #include "components/sync/engine/commit_and_get_updates_types.h"
16 #include "components/sync/protocol/entity_metadata.pb.h"
17 #include "components/sync/protocol/entity_specifics.pb.h"
18 #include "components/sync_bookmarks/bookmark_specifics_conversions.h"
19 #include "components/sync_bookmarks/synced_bookmark_tracker_entity.h"
20 #include "third_party/abseil-cpp/absl/types/variant.h"
22 namespace sync_bookmarks {
26 // A helper wrapper used to compare UniquePosition with positions before the
27 // first and after the last elements.
28 class UniquePositionWrapper {
30 static UniquePositionWrapper Min() {
31 return UniquePositionWrapper(MinUniquePosition{});
34 static UniquePositionWrapper Max() {
35 return UniquePositionWrapper(MaxUniquePosition{});
38 // |unique_position| must be valid.
39 static UniquePositionWrapper ForValidUniquePosition(
40 syncer::UniquePosition unique_position) {
41 DCHECK(unique_position.IsValid());
42 return UniquePositionWrapper(std::move(unique_position));
45 UniquePositionWrapper(UniquePositionWrapper&&) = default;
46 UniquePositionWrapper& operator=(UniquePositionWrapper&&) = default;
48 // Returns valid UniquePosition or invalid one for Min() and Max().
49 const syncer::UniquePosition& GetUniquePosition() const {
50 static const base::NoDestructor<syncer::UniquePosition>
52 if (HoldsUniquePosition()) {
53 return absl::get<syncer::UniquePosition>(value_);
55 return *kEmptyUniquePosition;
58 bool LessThan(const UniquePositionWrapper& other) const {
59 if (value_.index() != other.value_.index()) {
60 return value_.index() < other.value_.index();
62 if (!HoldsUniquePosition()) {
63 // Both arguments are MinUniquePosition or MaxUniquePosition, in both
64 // cases they are equal.
67 return GetUniquePosition().LessThan(other.GetUniquePosition());
71 struct MinUniquePosition {};
72 struct MaxUniquePosition {};
74 explicit UniquePositionWrapper(absl::variant<MinUniquePosition,
75 syncer::UniquePosition,
76 MaxUniquePosition> value)
77 : value_(std::move(value)) {}
79 bool HoldsUniquePosition() const {
80 return absl::holds_alternative<syncer::UniquePosition>(value_);
83 // The order is used to compare positions.
84 absl::variant<MinUniquePosition, syncer::UniquePosition, MaxUniquePosition>
90 BookmarkModelObserverImpl::BookmarkModelObserverImpl(
91 const base::RepeatingClosure& nudge_for_commit_closure,
92 base::OnceClosure on_bookmark_model_being_deleted_closure,
93 SyncedBookmarkTracker* bookmark_tracker)
94 : bookmark_tracker_(bookmark_tracker),
95 nudge_for_commit_closure_(nudge_for_commit_closure),
96 on_bookmark_model_being_deleted_closure_(
97 std::move(on_bookmark_model_being_deleted_closure)) {
98 DCHECK(bookmark_tracker_);
101 BookmarkModelObserverImpl::~BookmarkModelObserverImpl() = default;
103 void BookmarkModelObserverImpl::BookmarkModelLoaded(
104 bookmarks::BookmarkModel* model,
105 bool ids_reassigned) {
106 // This class isn't responsible for any loading-related logic.
109 void BookmarkModelObserverImpl::BookmarkModelBeingDeleted(
110 bookmarks::BookmarkModel* model) {
111 std::move(on_bookmark_model_being_deleted_closure_).Run();
114 void BookmarkModelObserverImpl::BookmarkNodeMoved(
115 bookmarks::BookmarkModel* model,
116 const bookmarks::BookmarkNode* old_parent,
118 const bookmarks::BookmarkNode* new_parent,
120 const bookmarks::BookmarkNode* node = new_parent->children()[new_index].get();
122 // We shouldn't see changes to the top-level nodes.
123 DCHECK(!model->is_permanent_node(node));
124 if (!model->client()->CanSyncNode(node)) {
127 const SyncedBookmarkTrackerEntity* entity =
128 bookmark_tracker_->GetEntityForBookmarkNode(node);
131 const std::string& sync_id = entity->metadata().server_id();
132 const base::Time modification_time = base::Time::Now();
133 const syncer::UniquePosition unique_position =
134 ComputePosition(*new_parent, new_index, sync_id);
136 sync_pb::EntitySpecifics specifics =
137 CreateSpecificsFromBookmarkNode(node, model, unique_position.ToProto(),
138 /*force_favicon_load=*/true);
140 bookmark_tracker_->Update(entity, entity->metadata().server_version(),
141 modification_time, specifics);
142 // Mark the entity that it needs to be committed.
143 bookmark_tracker_->IncrementSequenceNumber(entity);
144 nudge_for_commit_closure_.Run();
145 bookmark_tracker_->CheckAllNodesTracked(model);
148 void BookmarkModelObserverImpl::BookmarkNodeAdded(
149 bookmarks::BookmarkModel* model,
150 const bookmarks::BookmarkNode* parent,
152 bool added_by_user) {
153 const bookmarks::BookmarkNode* node = parent->children()[index].get();
154 if (!model->client()->CanSyncNode(node)) {
158 const SyncedBookmarkTrackerEntity* parent_entity =
159 bookmark_tracker_->GetEntityForBookmarkNode(parent);
160 DCHECK(parent_entity);
162 const syncer::UniquePosition unique_position =
163 ComputePosition(*parent, index, node->guid().AsLowercaseString());
165 sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode(
166 node, model, unique_position.ToProto(), /*force_favicon_load=*/true);
168 // It is possible that a created bookmark was restored after deletion and
169 // the tombstone was not committed yet. In that case the existing entity
170 // should be updated.
171 const SyncedBookmarkTrackerEntity* entity =
172 bookmark_tracker_->GetEntityForGUID(node->guid());
173 const base::Time creation_time = base::Time::Now();
175 // If there is a tracked entity with the same client tag hash (effectively
176 // the same bookmark GUID), it must be a tombstone. Otherwise it means
177 // the bookmark model contains to bookmarks with the same GUID.
178 DCHECK(!entity->bookmark_node()) << "Added bookmark with duplicate GUID";
179 bookmark_tracker_->UndeleteTombstoneForBookmarkNode(entity, node);
180 bookmark_tracker_->Update(entity, entity->metadata().server_version(),
181 creation_time, specifics);
183 entity = bookmark_tracker_->Add(node, node->guid().AsLowercaseString(),
184 syncer::kUncommittedVersion, creation_time,
188 // Mark the entity that it needs to be committed.
189 bookmark_tracker_->IncrementSequenceNumber(entity);
190 nudge_for_commit_closure_.Run();
192 // Do not check if all nodes are tracked because it's still possible that some
193 // nodes are untracked, e.g. if current node has been just restored and its
194 // children will be added soon.
197 void BookmarkModelObserverImpl::OnWillRemoveBookmarks(
198 bookmarks::BookmarkModel* model,
199 const bookmarks::BookmarkNode* parent,
201 const bookmarks::BookmarkNode* node) {
202 if (!model->client()->CanSyncNode(node)) {
205 bookmark_tracker_->CheckAllNodesTracked(model);
207 nudge_for_commit_closure_.Run();
210 void BookmarkModelObserverImpl::BookmarkNodeRemoved(
211 bookmarks::BookmarkModel* model,
212 const bookmarks::BookmarkNode* parent,
214 const bookmarks::BookmarkNode* node,
215 const std::set<GURL>& removed_urls) {
216 // All the work should have already been done in OnWillRemoveBookmarks.
217 DCHECK(bookmark_tracker_->GetEntityForBookmarkNode(node) == nullptr);
218 bookmark_tracker_->CheckAllNodesTracked(model);
221 void BookmarkModelObserverImpl::OnWillRemoveAllUserBookmarks(
222 bookmarks::BookmarkModel* model) {
223 bookmark_tracker_->CheckAllNodesTracked(model);
224 const bookmarks::BookmarkNode* root_node = model->root_node();
225 for (const auto& permanent_node : root_node->children()) {
226 for (const auto& child : permanent_node->children()) {
227 if (model->client()->CanSyncNode(child.get())) {
228 ProcessDelete(child.get());
232 nudge_for_commit_closure_.Run();
235 void BookmarkModelObserverImpl::BookmarkAllUserNodesRemoved(
236 bookmarks::BookmarkModel* model,
237 const std::set<GURL>& removed_urls) {
238 // All the work should have already been done in OnWillRemoveAllUserBookmarks.
239 bookmark_tracker_->CheckAllNodesTracked(model);
242 void BookmarkModelObserverImpl::BookmarkNodeChanged(
243 bookmarks::BookmarkModel* model,
244 const bookmarks::BookmarkNode* node) {
245 if (!model->client()->CanSyncNode(node)) {
249 // We shouldn't see changes to the top-level nodes.
250 DCHECK(!model->is_permanent_node(node));
252 const SyncedBookmarkTrackerEntity* entity =
253 bookmark_tracker_->GetEntityForBookmarkNode(node);
255 // If the node hasn't been added to the tracker yet, we do nothing. It will
256 // be added later. It's how BookmarkModel currently notifies observers, if
257 // further changes are triggered *during* observer notification. Consider
258 // the following scenario:
259 // 1. New bookmark added.
260 // 2. BookmarkModel notifies all the observers about the new node.
261 // 3. One observer A get's notified before us.
262 // 4. Observer A decided to update the bookmark node.
263 // 5. BookmarkModel notifies all observers about the update.
264 // 6. We received the notification about the update before the creation.
265 // 7. We will get the notification about the addition later and then we can
266 // start tracking the node.
270 sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode(
271 node, model, entity->metadata().unique_position(),
272 /*force_favicon_load=*/true);
273 ProcessUpdate(entity, specifics);
276 void BookmarkModelObserverImpl::BookmarkMetaInfoChanged(
277 bookmarks::BookmarkModel* model,
278 const bookmarks::BookmarkNode* node) {
279 BookmarkNodeChanged(model, node);
282 void BookmarkModelObserverImpl::BookmarkNodeFaviconChanged(
283 bookmarks::BookmarkModel* model,
284 const bookmarks::BookmarkNode* node) {
285 if (!model->client()->CanSyncNode(node)) {
289 // We shouldn't see changes to the top-level nodes.
290 DCHECK(!model->is_permanent_node(node));
292 // Ignore favicons that are being loaded.
293 if (!node->is_favicon_loaded()) {
294 // Subtle way to trigger a load of the favicon. This very same function will
295 // be notified when the favicon gets loaded (read from HistoryService and
296 // cached in RAM within BookmarkModel).
297 model->GetFavicon(node);
301 const SyncedBookmarkTrackerEntity* entity =
302 bookmark_tracker_->GetEntityForBookmarkNode(node);
304 // This should be practically unreachable but in theory it's possible that a
305 // favicon changes *during* the creation of a bookmark (by another
306 // observer). See analogous codepath in BookmarkNodeChanged().
310 const sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode(
311 node, model, entity->metadata().unique_position(),
312 /*force_favicon_load=*/false);
314 // TODO(crbug.com/1094825): implement |base_specifics_hash| similar to
315 // ClientTagBasedModelTypeProcessor.
316 if (!entity->MatchesFaviconHash(specifics.bookmark().favicon())) {
317 ProcessUpdate(entity, specifics);
321 // The favicon content didn't actually change, which means this event is
322 // almost certainly the result of favicon loading having completed.
323 if (entity->IsUnsynced()) {
324 // Nudge for commit once favicon is loaded. This is needed in case when
325 // unsynced entity was skipped while building commit requests (since favicon
327 nudge_for_commit_closure_.Run();
331 void BookmarkModelObserverImpl::BookmarkNodeChildrenReordered(
332 bookmarks::BookmarkModel* model,
333 const bookmarks::BookmarkNode* node) {
334 if (!model->client()->CanSyncNode(node)) {
338 if (node->children().size() <= 1) {
339 // There is no real change in the order of |node|'s children.
343 // The given node's children got reordered, all the corresponding sync nodes
344 // need to be reordered. The code is optimized to detect move of only one
345 // bookmark (which is the case on Android platform). There are 2 main cases:
346 // a bookmark moved to left or to right. Moving a bookmark to the first and
347 // last positions are two more special cases. The algorithm iterates over each
348 // bookmark and compares it to the left and right nodes to determine whether
349 // it's ordered or not.
351 // Each digit below represents bookmark's original position.
353 // Moving a bookmark to the left: 0123456 -> 0612345.
354 // When processing '6', its unique position is greater than both left and
357 // Moving a bookmark to the right: 0123456 -> 0234516.
358 // When processing '1', its unique position is less than both left and right
361 // Note that in both cases left node is less than right node. This condition
362 // is checked when iterating over bookmarks and if it's violated, the
363 // algorithm falls back to generating positions for all the following nodes.
365 // For example, if two nodes are moved to one place: 0123456 -> 0156234 (nodes
366 // '5' and '6' are moved together). In this case, 0156 will remain and when
367 // processing '2', algorithm will fall back to generating unique positions for
368 // nodes '2', '3' and '4'. It will be detected by comparing the next node '3'
369 // with the previous '6'.
371 // Store |cur| outside of the loop to prevent parsing UniquePosition twice.
372 UniquePositionWrapper cur = UniquePositionWrapper::ForValidUniquePosition(
373 GetUniquePositionForNode(node->children().front().get()));
374 UniquePositionWrapper prev = UniquePositionWrapper::Min();
375 for (size_t current_index = 0; current_index < node->children().size();
377 UniquePositionWrapper next = UniquePositionWrapper::Max();
378 if (current_index + 1 < node->children().size()) {
379 next = UniquePositionWrapper::ForValidUniquePosition(
380 GetUniquePositionForNode(node->children()[current_index + 1].get()));
383 // |prev| is the last ordered node. Compare |cur| and |next| with it to
384 // decide whether current node needs to be updated. Consider the following
385 // cases: 0. |prev| < |cur| < |next|: all elements are ordered.
386 // 1. |cur| < |prev| < |next|: update current node and put it between |prev|
388 // 2. |cur| < |next| < |prev|: both |cur| and |next| are out of order, fall
389 // back to simple approach.
390 // 3. |next| < |cur| < |prev|: same as #2.
391 // 4. |prev| < |next| < |cur|: update current node and put it between |prev|
393 // 5. |next| < |prev| < |cur|: consider current node ordered, |next| will be
394 // updated on the next step.
396 // In the following code only cases where current node needs to be updated
397 // are considered (#0 and #5 are omitted because there is nothing to do).
399 bool update_current_position = false;
400 if (cur.LessThan(prev)) {
401 // |cur| < |prev|, cases #1, #2 and #3.
402 if (next.LessThan(prev)) {
403 // There are two consecutive nodes which both are out of order (#2, #3):
404 // |prev| > |cur| and |prev| > |next|.
405 // It means that more than one bookmark has been reordered, fall back to
406 // generating unique positions for all the remaining children.
408 // |current_index| is always not 0 because |prev| cannot be
409 // UniquePositionWrapper::Min() if |next| < |prev|.
410 DCHECK_GT(current_index, 0u);
411 UpdateAllUniquePositionsStartingAt(node, model, current_index);
414 update_current_position = true;
415 } else if (next.LessThan(cur) && prev.LessThan(next)) {
416 // |prev| < |next| < |cur| (case #4).
417 update_current_position = true;
420 if (update_current_position) {
421 cur = UniquePositionWrapper::ForValidUniquePosition(
422 UpdateUniquePositionForNode(node->children()[current_index].get(),
423 model, prev.GetUniquePosition(),
424 next.GetUniquePosition()));
427 DCHECK(prev.LessThan(cur));
428 prev = std::move(cur);
429 cur = std::move(next);
432 nudge_for_commit_closure_.Run();
435 syncer::UniquePosition BookmarkModelObserverImpl::ComputePosition(
436 const bookmarks::BookmarkNode& parent,
438 const std::string& sync_id) {
439 const std::string& suffix = syncer::GenerateSyncableBookmarkHash(
440 bookmark_tracker_->model_type_state().cache_guid(), sync_id);
441 DCHECK(!parent.children().empty());
442 const SyncedBookmarkTrackerEntity* predecessor_entity = nullptr;
443 const SyncedBookmarkTrackerEntity* successor_entity = nullptr;
445 // Look for the first tracked predecessor.
446 for (auto i = parent.children().crend() - index;
447 i != parent.children().crend(); ++i) {
448 const bookmarks::BookmarkNode* predecessor_node = i->get();
450 bookmark_tracker_->GetEntityForBookmarkNode(predecessor_node);
451 if (predecessor_entity) {
456 // Look for the first tracked successor.
457 for (auto i = parent.children().cbegin() + index + 1;
458 i != parent.children().cend(); ++i) {
459 const bookmarks::BookmarkNode* successor_node = i->get();
461 bookmark_tracker_->GetEntityForBookmarkNode(successor_node);
462 if (successor_entity) {
467 if (!predecessor_entity && !successor_entity) {
468 // No tracked siblings.
469 return syncer::UniquePosition::InitialPosition(suffix);
472 if (!predecessor_entity && successor_entity) {
473 // No predecessor, insert before the successor.
474 return syncer::UniquePosition::Before(
475 syncer::UniquePosition::FromProto(
476 successor_entity->metadata().unique_position()),
480 if (predecessor_entity && !successor_entity) {
481 // No successor, insert after the predecessor
482 return syncer::UniquePosition::After(
483 syncer::UniquePosition::FromProto(
484 predecessor_entity->metadata().unique_position()),
488 // Both predecessor and successor, insert in the middle.
489 return syncer::UniquePosition::Between(
490 syncer::UniquePosition::FromProto(
491 predecessor_entity->metadata().unique_position()),
492 syncer::UniquePosition::FromProto(
493 successor_entity->metadata().unique_position()),
497 void BookmarkModelObserverImpl::ProcessUpdate(
498 const SyncedBookmarkTrackerEntity* entity,
499 const sync_pb::EntitySpecifics& specifics) {
502 // Data should be committed to the server only if there is an actual change,
503 // determined here by comparing hashes.
504 if (entity->MatchesSpecificsHash(specifics)) {
505 // Specifics haven't actually changed, so the local change can be ignored.
509 bookmark_tracker_->Update(entity, entity->metadata().server_version(),
510 /*modification_time=*/base::Time::Now(), specifics);
511 // Mark the entity that it needs to be committed.
512 bookmark_tracker_->IncrementSequenceNumber(entity);
513 nudge_for_commit_closure_.Run();
516 void BookmarkModelObserverImpl::ProcessDelete(
517 const bookmarks::BookmarkNode* node) {
518 // If not a leaf node, process all children first.
519 for (const auto& child : node->children()) {
520 ProcessDelete(child.get());
522 // Process the current node.
523 const SyncedBookmarkTrackerEntity* entity =
524 bookmark_tracker_->GetEntityForBookmarkNode(node);
525 // Shouldn't try to delete untracked entities.
527 // If the entity hasn't been committed and doesn't have an inflight commit
528 // request, simply remove it from the tracker.
529 if (entity->metadata().server_version() == syncer::kUncommittedVersion &&
530 !entity->commit_may_have_started()) {
531 bookmark_tracker_->Remove(entity);
534 bookmark_tracker_->MarkDeleted(entity);
535 // Mark the entity that it needs to be committed.
536 bookmark_tracker_->IncrementSequenceNumber(entity);
539 syncer::UniquePosition BookmarkModelObserverImpl::GetUniquePositionForNode(
540 const bookmarks::BookmarkNode* node) const {
541 DCHECK(bookmark_tracker_);
543 const SyncedBookmarkTrackerEntity* entity =
544 bookmark_tracker_->GetEntityForBookmarkNode(node);
546 return syncer::UniquePosition::FromProto(
547 entity->metadata().unique_position());
550 syncer::UniquePosition BookmarkModelObserverImpl::UpdateUniquePositionForNode(
551 const bookmarks::BookmarkNode* node,
552 bookmarks::BookmarkModel* bookmark_model,
553 const syncer::UniquePosition& prev,
554 const syncer::UniquePosition& next) {
555 DCHECK(bookmark_tracker_);
557 DCHECK(bookmark_model);
559 const SyncedBookmarkTrackerEntity* entity =
560 bookmark_tracker_->GetEntityForBookmarkNode(node);
562 const std::string suffix = syncer::GenerateSyncableBookmarkHash(
563 bookmark_tracker_->model_type_state().cache_guid(),
564 entity->metadata().server_id());
565 const base::Time modification_time = base::Time::Now();
567 syncer::UniquePosition new_unique_position;
568 if (prev.IsValid() && next.IsValid()) {
569 new_unique_position = syncer::UniquePosition::Between(prev, next, suffix);
570 } else if (prev.IsValid()) {
571 new_unique_position = syncer::UniquePosition::After(prev, suffix);
573 new_unique_position = syncer::UniquePosition::Before(next, suffix);
576 sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode(
577 node, bookmark_model, new_unique_position.ToProto(),
578 /*force_favicon_load=*/true);
579 bookmark_tracker_->Update(entity, entity->metadata().server_version(),
580 modification_time, specifics);
582 // Mark the entity that it needs to be committed.
583 bookmark_tracker_->IncrementSequenceNumber(entity);
584 return new_unique_position;
587 void BookmarkModelObserverImpl::UpdateAllUniquePositionsStartingAt(
588 const bookmarks::BookmarkNode* parent,
589 bookmarks::BookmarkModel* bookmark_model,
590 size_t start_index) {
591 DCHECK_GT(start_index, 0u);
592 DCHECK_LT(start_index, parent->children().size());
594 syncer::UniquePosition prev =
595 GetUniquePositionForNode(parent->children()[start_index - 1].get());
596 for (size_t current_index = start_index;
597 current_index < parent->children().size(); ++current_index) {
598 // Right position is unknown because it will also be updated.
599 prev = UpdateUniquePositionForNode(parent->children()[current_index].get(),
600 bookmark_model, prev,
601 /*next=*/syncer::UniquePosition());
605 } // namespace sync_bookmarks