// Copyright 2018 The Chromium Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "components/sync_bookmarks/bookmark_model_merger.h" #include #include #include #include "base/logging.h" #include "base/metrics/histogram_functions.h" #include "base/strings/string_util.h" #include "base/strings/utf_string_conversions.h" #include "base/time/time.h" #include "base/trace_event/trace_event.h" #include "base/uuid.h" #include "components/bookmarks/browser/bookmark_node.h" #include "components/bookmarks/browser/bookmark_uuids.h" #include "components/sync/base/data_type.h" #include "components/sync/base/server_defined_unique_tags.h" #include "components/sync/base/time.h" #include "components/sync/protocol/bookmark_specifics.pb.h" #include "components/sync/protocol/entity_metadata.pb.h" #include "components/sync/protocol/entity_specifics.pb.h" #include "components/sync_bookmarks/bookmark_model_view.h" #include "components/sync_bookmarks/bookmark_specifics_conversions.h" #include "components/sync_bookmarks/switches.h" #include "components/sync_bookmarks/synced_bookmark_tracker.h" #include "components/sync_bookmarks/synced_bookmark_tracker_entity.h" #include "third_party/abseil-cpp/absl/container/flat_hash_map.h" #include "ui/base/models/tree_node_iterator.h" namespace sync_bookmarks { namespace { using syncer::EntityData; using syncer::UpdateResponseData; using syncer::UpdateResponseDataList; static const size_t kInvalidIndex = -1; // Maximum depth to sync bookmarks tree to protect against stack overflow. // Keep in sync with |base::internal::kAbsoluteMaxDepth| in json_common.h. const size_t kMaxBookmarkTreeDepth = 200; // The value must be a list since there is a container using pointers to its // elements. using UpdatesPerParentUuid = absl::flat_hash_map, base::UuidHash>; // These values are persisted to logs. Entries should not be renumbered and // numeric values should never be reused. When adding values, be certain to also // update the corresponding definition in enums.xml and the // ExpectedBookmarksUuidDuplicates in unittests. // LINT.IfChange(BookmarksGUIDDuplicates) enum class BookmarksUuidDuplicates { // Both entities are URLs with matching URLs in specifics. Entities may have // different titles or parents. kMatchingUrls = 0, // Both entities are folders with matching titles. Entities may have different // parents. kMatchingFolders = 1, // Both entities are URLs, but they have different URLs. kDifferentUrls = 2, // Both entities are folders with different titles. kDifferentFolders = 3, // Entities have different types. kDifferentTypes = 4, kMaxValue = kDifferentTypes, }; // LINT.ThenChange(/tools/metrics/histograms/metadata/sync/enums.xml:BookmarksGUIDDuplicates) // Used in metrics: "Sync.ProblematicServerSideBookmarksDuringMerge". These // values are persisted to logs. Entries should not be renumbered and numeric // values should never be reused. Note the existence of gaps because the // metric enum is reused for another UMA metric, // Sync.ProblematicServerSideBookmarks, which logs the analogous error cases // for non-initial updates. // LINT.IfChange(RemoteBookmarkUpdateError) enum class RemoteBookmarkUpdateError { // Invalid specifics. kInvalidSpecifics = 1, // Invalid unique position. kInvalidUniquePosition = 2, // Parent entity not found in server. kMissingParentEntity = 4, // The bookmark's UUID did not match the originator client item ID. kUnexpectedGuid = 9, // Parent is not a folder. kParentNotFolder = 10, // Unknown/unsupported permanent folder. kUnsupportedPermanentFolder = 13, // A bookmark that is not contained in any permanent folder and is instead // hanging (directly or indirectly) from the root node. // kDeprecatedDescendantOfRootNodeWithoutPermanentFolder = 14, kMaxValue = kUnsupportedPermanentFolder, }; // LINT.ThenChange(/tools/metrics/histograms/metadata/sync/enums.xml:RemoteBookmarkUpdateError) void LogProblematicBookmark(RemoteBookmarkUpdateError problem) { base::UmaHistogramEnumeration( "Sync.ProblematicServerSideBookmarksDuringMerge", problem); } void LogBookmarkReuploadNeeded(bool is_reupload_needed) { base::UmaHistogramBoolean("Sync.BookmarkEntityReuploadNeeded.OnInitialMerge", is_reupload_needed); } // Gets the bookmark node corresponding to a permanent folder identified by // |server_defined_unique_tag| or null of the tag is unknown. |bookmark_model| // must not be null and |server_defined_unique_tag| must not be empty. const bookmarks::BookmarkNode* GetPermanentFolderForServerDefinedUniqueTag( const BookmarkModelView* bookmark_model, const std::string& server_defined_unique_tag) { DCHECK(bookmark_model); DCHECK(!server_defined_unique_tag.empty()); // WARNING: Keep this logic consistent with the analogous in // GetPermanentFolderUuidForServerDefinedUniqueTag(). if (server_defined_unique_tag == syncer::kBookmarkBarTag) { return bookmark_model->bookmark_bar_node(); } if (server_defined_unique_tag == syncer::kOtherBookmarksTag) { return bookmark_model->other_node(); } if (server_defined_unique_tag == syncer::kSyncedBookmarksTag) { return bookmark_model->mobile_node(); } return nullptr; } std::string LegacyCanonicalizedTitleFromSpecifics( const sync_pb::BookmarkSpecifics& specifics) { if (specifics.has_full_title()) { return FullTitleToLegacyCanonicalizedTitle(specifics.full_title()); } return specifics.legacy_canonicalized_title(); } // Heuristic to consider two nodes (local and remote) a match by semantics for // the purpose of merging. Two folders match by semantics if they have the same // title, two bookmarks match by semantics if they have the same title and url. // A folder and a bookmark never match. bool NodeSemanticsMatch(const bookmarks::BookmarkNode* local_node, const std::string& remote_canonicalized_title, const GURL& remote_url, sync_pb::BookmarkSpecifics::Type remote_type) { if (GetProtoTypeFromBookmarkNode(local_node) != remote_type) { return false; } if (remote_type == sync_pb::BookmarkSpecifics::URL && local_node->url() != remote_url) { return false; } const std::string local_title = base::UTF16ToUTF8(local_node->GetTitle()); // Titles match if they are identical or the remote one is the canonical form // of the local one. The latter is the case when a legacy client has // canonicalized the same local title before committing it. Modern clients // don't canonicalize titles anymore. // TODO(rushans): the comment above is off. if (local_title != remote_canonicalized_title && sync_bookmarks::FullTitleToLegacyCanonicalizedTitle(local_title) != remote_canonicalized_title) { return false; } return true; } BookmarksUuidDuplicates MatchBookmarksUuidDuplicates( const UpdateResponseData& update, const UpdateResponseData& duplicate_update) { if (update.entity.specifics.bookmark().type() != duplicate_update.entity.specifics.bookmark().type()) { return BookmarksUuidDuplicates::kDifferentTypes; } switch (update.entity.specifics.bookmark().type()) { case sync_pb::BookmarkSpecifics::UNSPECIFIED: NOTREACHED(); case sync_pb::BookmarkSpecifics::URL: { const bool matching_urls = update.entity.specifics.bookmark().url() == duplicate_update.entity.specifics.bookmark().url(); return matching_urls ? BookmarksUuidDuplicates::kMatchingUrls : BookmarksUuidDuplicates::kDifferentUrls; } case sync_pb::BookmarkSpecifics::FOLDER: { // Both entities are folders. const bool matching_titles = LegacyCanonicalizedTitleFromSpecifics( update.entity.specifics.bookmark()) == LegacyCanonicalizedTitleFromSpecifics( duplicate_update.entity.specifics.bookmark()); return matching_titles ? BookmarksUuidDuplicates::kMatchingFolders : BookmarksUuidDuplicates::kDifferentFolders; } } NOTREACHED(); } // Returns true the |next_update| is selected to keep and the |previous_update| // should be removed. False is returned otherwise. |next_update| and // |previous_update| must have the same UUID. bool CompareDuplicateUpdates(const UpdateResponseData& next_update, const UpdateResponseData& previous_update) { DCHECK_EQ(next_update.entity.specifics.bookmark().guid(), previous_update.entity.specifics.bookmark().guid()); DCHECK_NE(next_update.entity.id, previous_update.entity.id); if (next_update.entity.specifics.bookmark().type() != previous_update.entity.specifics.bookmark().type()) { // There are two entities, one of them is a folder and another one is a // URL. Prefer to save the folder as it may contain many bookmarks. return next_update.entity.specifics.bookmark().type() == sync_pb::BookmarkSpecifics::FOLDER; } // Choose the latest element to keep if both updates have the same type. return next_update.entity.creation_time > previous_update.entity.creation_time; } void DeduplicateValidUpdatesByUuid( UpdatesPerParentUuid* updates_per_parent_uuid) { DCHECK(updates_per_parent_uuid); absl::flat_hash_map::iterator, base::UuidHash> uuid_to_update; for (auto& [parent_uuid, updates] : *updates_per_parent_uuid) { auto updates_iter = updates.begin(); while (updates_iter != updates.end()) { const UpdateResponseData& update = *updates_iter; DCHECK(!update.entity.is_deleted()); DCHECK(update.entity.server_defined_unique_tag.empty()); const base::Uuid uuid_in_specifics = base::Uuid::ParseLowercase(update.entity.specifics.bookmark().guid()); DCHECK(uuid_in_specifics.is_valid()); auto [it, success] = uuid_to_update.emplace(uuid_in_specifics, updates_iter); if (success) { ++updates_iter; continue; } const auto& [uuid, previous_update_it] = *it; DCHECK_EQ(uuid_in_specifics.AsLowercaseString(), previous_update_it->entity.specifics.bookmark().guid()); DLOG(ERROR) << "Duplicate uuid for new sync ID " << update.entity.id << " and original sync ID " << previous_update_it->entity.id; const BookmarksUuidDuplicates match_result = MatchBookmarksUuidDuplicates(update, *previous_update_it); base::UmaHistogramEnumeration("Sync.BookmarksGUIDDuplicates", match_result); if (CompareDuplicateUpdates(/*next_update=*/update, /*previous_update=*/*previous_update_it)) { updates.erase(previous_update_it); uuid_to_update[uuid_in_specifics] = updates_iter; ++updates_iter; } else { updates_iter = updates.erase(updates_iter); } } } } // Checks that the |update| is valid and returns false otherwise. It is used to // verify non-deletion updates. |update| must not be a deletion and a permanent // node (they are processed in a different way). bool IsValidUpdate(const UpdateResponseData& update) { const EntityData& update_entity = update.entity; DCHECK(!update_entity.is_deleted()); DCHECK(update_entity.server_defined_unique_tag.empty()); if (!IsValidBookmarkSpecifics(update_entity.specifics.bookmark())) { // Ignore updates with invalid specifics. DLOG(ERROR) << "Remote update with invalid specifics"; LogProblematicBookmark(RemoteBookmarkUpdateError::kInvalidSpecifics); return false; } if (!HasExpectedBookmarkGuid(update_entity.specifics.bookmark(), update_entity.client_tag_hash, update_entity.originator_cache_guid, update_entity.originator_client_item_id)) { // Ignore updates with an unexpected UUID. DLOG(ERROR) << "Remote update with unexpected Uuid"; LogProblematicBookmark(RemoteBookmarkUpdateError::kUnexpectedGuid); return false; } return true; } // Returns the UUID determined by a remote update, which may be an update for a // permanent folder or a regular bookmark node. base::Uuid GetUuidForUpdate(const UpdateResponseData& update) { if (!update.entity.server_defined_unique_tag.empty()) { return GetPermanentFolderUuidForServerDefinedUniqueTag( update.entity.server_defined_unique_tag); } DCHECK(IsValidUpdate(update)); return base::Uuid::ParseLowercase(update.entity.specifics.bookmark().guid()); } struct GroupedUpdates { // |updates_per_parent_uuid| contains all valid updates grouped by their // |parent_uuid|. Permanent nodes and deletions are filtered out. Permanent // nodes are stored in a dedicated list |permanent_node_updates|. UpdatesPerParentUuid updates_per_parent_uuid; UpdateResponseDataList permanent_node_updates; }; // Groups all valid updates by the UUID of their parent. Permanent nodes are // grouped in a dedicated |permanent_node_updates| list in a returned value. GroupedUpdates GroupValidUpdates(UpdateResponseDataList updates) { GroupedUpdates grouped_updates; int num_valid_updates = 0; for (UpdateResponseData& update : updates) { const EntityData& update_entity = update.entity; if (update_entity.is_deleted()) { continue; } // Special-case the root folder to avoid recording // |RemoteBookmarkUpdateError::kUnsupportedPermanentFolder|. if (update_entity.server_defined_unique_tag == syncer::DataTypeToProtocolRootTag(syncer::BOOKMARKS)) { ++num_valid_updates; continue; } // Non-root permanent folders don't need further validation. if (!update_entity.server_defined_unique_tag.empty()) { ++num_valid_updates; grouped_updates.permanent_node_updates.push_back(std::move(update)); continue; } // Regular (non-permanent) node updates must pass IsValidUpdate(). if (!IsValidUpdate(update)) { continue; } ++num_valid_updates; const base::Uuid parent_uuid = base::Uuid::ParseLowercase( update_entity.specifics.bookmark().parent_guid()); DCHECK(parent_uuid.is_valid()); grouped_updates.updates_per_parent_uuid[parent_uuid].push_back( std::move(update)); } base::UmaHistogramCounts100000("Sync.BookmarkModelMerger.ValidInputUpdates", num_valid_updates); return grouped_updates; } int GetNumUnsyncedEntities(const SyncedBookmarkTracker* tracker) { DCHECK(tracker); int num_unsynced_entities = 0; for (const SyncedBookmarkTrackerEntity* entity : tracker->GetAllEntities()) { if (entity->IsUnsynced()) { ++num_unsynced_entities; } } return num_unsynced_entities; } } // namespace BookmarkModelMerger::RemoteTreeNode::RemoteTreeNode() = default; BookmarkModelMerger::RemoteTreeNode::~RemoteTreeNode() = default; BookmarkModelMerger::RemoteTreeNode::RemoteTreeNode( BookmarkModelMerger::RemoteTreeNode&&) = default; BookmarkModelMerger::RemoteTreeNode& BookmarkModelMerger::RemoteTreeNode::operator=( BookmarkModelMerger::RemoteTreeNode&&) = default; void BookmarkModelMerger::RemoteTreeNode::EmplaceSelfAndDescendantsByUuid( absl::flat_hash_map* uuid_to_remote_node_map) const { DCHECK(uuid_to_remote_node_map); if (entity().server_defined_unique_tag.empty()) { const base::Uuid uuid = base::Uuid::ParseLowercase(entity().specifics.bookmark().guid()); DCHECK(uuid.is_valid()); // Duplicate UUIDs have been sorted out before. bool success = uuid_to_remote_node_map->emplace(uuid, this).second; DCHECK(success); } for (const RemoteTreeNode& child : children_) { child.EmplaceSelfAndDescendantsByUuid(uuid_to_remote_node_map); } } // static bool BookmarkModelMerger::RemoteTreeNode::UniquePositionLessThan( const RemoteTreeNode& lhs, const RemoteTreeNode& rhs) { return lhs.unique_position_.LessThan(rhs.unique_position_); } // static BookmarkModelMerger::RemoteTreeNode BookmarkModelMerger::RemoteTreeNode::BuildTree( UpdateResponseData update, size_t max_depth, UpdatesPerParentUuid* updates_per_parent_uuid) { DCHECK(updates_per_parent_uuid); DCHECK(!update.entity.server_defined_unique_tag.empty() || IsValidUpdate(update)); // |uuid| may be invalid for unsupported permanent nodes. const base::Uuid uuid = GetUuidForUpdate(update); RemoteTreeNode node; node.update_ = std::move(update); node.unique_position_ = syncer::UniquePosition::FromProto( node.update_.entity.specifics.bookmark().unique_position()); // Ensure we have not reached the maximum tree depth to guard against stack // overflows. if (max_depth == 0) { return node; } // Check to prevent creating empty lists in |updates_per_parent_uuid| and // unnecessary rehashing. auto updates_per_parent_uuid_iter = updates_per_parent_uuid->find(uuid); if (updates_per_parent_uuid_iter == updates_per_parent_uuid->end()) { return node; } DCHECK(!updates_per_parent_uuid_iter->second.empty()); DCHECK(uuid.is_valid()); // Only folders may have descendants (ignore them otherwise). Treat // permanent nodes as folders explicitly. if (node.update_.entity.specifics.bookmark().type() != sync_pb::BookmarkSpecifics::FOLDER && node.update_.entity.server_defined_unique_tag.empty()) { // Children of a non-folder are ignored. for (UpdateResponseData& child_update : updates_per_parent_uuid_iter->second) { LogProblematicBookmark(RemoteBookmarkUpdateError::kParentNotFolder); // To avoid double-counting later for bucket |kMissingParentEntity|, // clear the update from the list as if it would have been moved. child_update.entity = EntityData(); } return node; } // Populate descendants recursively. node.children_.reserve(updates_per_parent_uuid_iter->second.size()); for (UpdateResponseData& child_update : updates_per_parent_uuid_iter->second) { DCHECK_EQ(child_update.entity.specifics.bookmark().parent_guid(), uuid.AsLowercaseString()); DCHECK(IsValidBookmarkSpecifics(child_update.entity.specifics.bookmark())); node.children_.push_back(BuildTree(std::move(child_update), max_depth - 1, updates_per_parent_uuid)); } // Sort the children according to their unique position. std::ranges::sort(node.children_, UniquePositionLessThan); return node; } BookmarkModelMerger::BookmarkModelMerger( UpdateResponseDataList updates, BookmarkModelView* bookmark_model, favicon::FaviconService* favicon_service, SyncedBookmarkTracker* bookmark_tracker) : bookmark_model_(bookmark_model), favicon_service_(favicon_service), bookmark_tracker_(bookmark_tracker), remote_updates_size_(updates.size()), remote_forest_(BuildRemoteForest(std::move(updates), bookmark_tracker)), uuid_to_match_map_( FindGuidMatchesOrReassignLocal(remote_forest_, bookmark_model_)) { CHECK(bookmark_tracker_->IsEmpty()); CHECK(favicon_service); CHECK(bookmark_model); CHECK(bookmark_model->bookmark_bar_node()); CHECK(bookmark_model->mobile_node()); CHECK(bookmark_model->other_node()); int num_updates_in_forest = 0; for (const auto& [server_defined_unique_tag, root] : remote_forest_) { num_updates_in_forest += 1 + CountRemoteTreeNodeDescendantsForUma(root); } base::UmaHistogramCounts100000( "Sync.BookmarkModelMerger.ReachableInputUpdates", num_updates_in_forest); } BookmarkModelMerger::~BookmarkModelMerger() = default; void BookmarkModelMerger::Merge() { TRACE_EVENT0("sync", "BookmarkModelMerger::Merge"); // Algorithm description: // Match up the roots and recursively do the following: // * For each remote node for the current remote (sync) parent node, either // find a local node with equal UUID anywhere throughout the tree or find // the best matching bookmark node under the corresponding local bookmark // parent node using semantics. If the found node has the same UUID as a // different remote bookmark, we do not consider it a semantics match, as // UUID matching takes precedence. If no matching node is found, create a // new bookmark node in the same position as the corresponding remote node. // If a matching node is found, update the properties of it from the // corresponding remote node. // * When all children remote nodes are done, add the extra children bookmark // nodes to the remote (sync) parent node, unless they will be later matched // by UUID. // // The semantics best match algorithm uses folder title or bookmark title/url // to perform the primary match. If there are multiple match candidates it // selects the first one. // Associate permanent folders. for (const auto& [server_defined_unique_tag, root] : remote_forest_) { DCHECK(!server_defined_unique_tag.empty()); const bookmarks::BookmarkNode* permanent_folder = GetPermanentFolderForServerDefinedUniqueTag(bookmark_model_, server_defined_unique_tag); // Ignore unsupported permanent folders. if (!permanent_folder) { DCHECK(!GetPermanentFolderUuidForServerDefinedUniqueTag( server_defined_unique_tag) .is_valid()); LogProblematicBookmark( RemoteBookmarkUpdateError::kUnsupportedPermanentFolder); continue; } DCHECK_EQ(permanent_folder->uuid(), GetPermanentFolderUuidForServerDefinedUniqueTag( server_defined_unique_tag)); MergeSubtree(/*local_node=*/permanent_folder, /*remote_node=*/root); } if (base::FeatureList::IsEnabled(switches::kSyncReuploadBookmarks)) { // When the reupload feature is enabled, all new empty trackers are // automatically reuploaded (since there are no entities to reupload). This // is used to disable reupload after initial merge. bookmark_tracker_->SetBookmarksReuploaded(); } if (base::FeatureList::IsEnabled( switches::kSyncMigrateBookmarksWithoutClientTagHash)) { for (const auto& [server_defined_unique_tag, root] : remote_forest_) { const bookmarks::BookmarkNode* permanent_folder = GetPermanentFolderForServerDefinedUniqueTag( bookmark_model_, server_defined_unique_tag); if (permanent_folder) { MigrateBookmarksInSubtreeWithoutClientTagHash(root, permanent_folder); } } } base::UmaHistogramCounts100000( "Sync.BookmarkModelMerger.UnsyncedEntitiesUponCompletion", GetNumUnsyncedEntities(bookmark_tracker_)); ReportTimeMetrics(); } // static BookmarkModelMerger::RemoteForest BookmarkModelMerger::BuildRemoteForest( syncer::UpdateResponseDataList updates, SyncedBookmarkTracker* tracker_for_recording_ignored_updates) { TRACE_EVENT0("sync", "BookmarkModelMerger::BuildRemoteForest"); DCHECK(tracker_for_recording_ignored_updates); // Filter out invalid remote updates and group the valid ones by the server ID // of their parent. GroupedUpdates grouped_updates = GroupValidUpdates(std::move(updates)); DeduplicateValidUpdatesByUuid(&grouped_updates.updates_per_parent_uuid); // Construct one tree per permanent entity. RemoteForest update_forest; for (UpdateResponseData& permanent_node_update : grouped_updates.permanent_node_updates) { // Make a copy of the string to avoid relying on argument evaluation order. const std::string server_defined_unique_tag = permanent_node_update.entity.server_defined_unique_tag; DCHECK(!server_defined_unique_tag.empty()); update_forest.emplace( server_defined_unique_tag, RemoteTreeNode::BuildTree(std::move(permanent_node_update), kMaxBookmarkTreeDepth, &grouped_updates.updates_per_parent_uuid)); } // All remaining entries in |updates_per_parent_uuid| must be unreachable from // permanent entities, since otherwise they would have been moved away. for (const auto& [parent_uuid, updates_for_uuid] : grouped_updates.updates_per_parent_uuid) { for (const UpdateResponseData& update : updates_for_uuid) { if (update.entity.specifics.has_bookmark()) { LogProblematicBookmark(RemoteBookmarkUpdateError::kMissingParentEntity); tracker_for_recording_ignored_updates ->RecordIgnoredServerUpdateDueToMissingParent( update.response_version); } } } return update_forest; } // static int BookmarkModelMerger::CountRemoteTreeNodeDescendantsForUma( const RemoteTreeNode& node) { int descendants = 0; for (const RemoteTreeNode& child : node.children()) { descendants += 1 + CountRemoteTreeNodeDescendantsForUma(child); } return descendants; } // static absl::flat_hash_map BookmarkModelMerger::FindGuidMatchesOrReassignLocal( const RemoteForest& remote_forest, BookmarkModelView* bookmark_model) { DCHECK(bookmark_model); TRACE_EVENT0("sync", "BookmarkModelMerger::FindGuidMatchesOrReassignLocal"); // Build a temporary lookup table for remote UUIDs. absl::flat_hash_map uuid_to_remote_node_map; for (const auto& [server_defined_unique_tag, root] : remote_forest) { root.EmplaceSelfAndDescendantsByUuid(&uuid_to_remote_node_map); } // Iterate through all local bookmarks to find matches by UUID. absl::flat_hash_map uuid_to_match_map; // Because ReplaceBookmarkNodeUuid() cannot be used while iterating the local // bookmark model, a temporary list is constructed first to reassign later. std::vector nodes_to_replace_uuid; ui::TreeNodeIterator iterator( bookmark_model->root_node()); while (iterator.has_next()) { const bookmarks::BookmarkNode* const node = iterator.Next(); DCHECK(node->uuid().is_valid()); // Ignore changes to non-syncable nodes. Managed nodes, which are // unsyncable, use a random UUID so they should never match, but this // codepath is useful when BookmarkModelMerger is used together with // `BookmarkModelViewUsingAccountNodes`, which would otherwise match against // local nodes. if (!bookmark_model->IsNodeSyncable(node)) { continue; } const auto remote_it = uuid_to_remote_node_map.find(node->uuid()); if (remote_it == uuid_to_remote_node_map.end()) { continue; } const RemoteTreeNode* const remote_node = remote_it->second; const syncer::EntityData& remote_entity = remote_node->entity(); // Permanent nodes don't match by UUID but by |server_defined_unique_tag|. // As extra precaution, specially with remote UUIDs in mind, let's ignore // them explicitly here. DCHECK(remote_entity.server_defined_unique_tag.empty()); if (node->is_permanent_node()) { continue; } if (GetProtoTypeFromBookmarkNode(node) != remote_entity.specifics.bookmark().type() || (node->is_url() && node->url() != remote_entity.specifics.bookmark().url())) { // If local node and its remote node match are conflicting in node type or // URL, replace local UUID with a random UUID. nodes_to_replace_uuid.push_back(node); continue; } const bool success = uuid_to_match_map.emplace(node->uuid(), GuidMatch{node, remote_node}) .second; // Insertion must have succeeded unless there were duplicate UUIDs in the // local BookmarkModel (invariant violation that gets resolved upon // restart). DCHECK(success); } for (const bookmarks::BookmarkNode* node : nodes_to_replace_uuid) { ReplaceBookmarkNodeUuid(node, base::Uuid::GenerateRandomV4(), bookmark_model); } return uuid_to_match_map; } void BookmarkModelMerger::MigrateBookmarksInSubtreeWithoutClientTagHash( const RemoteTreeNode& remote_node, const bookmarks::BookmarkNode* local_node) { CHECK(local_node); CHECK_LE(remote_node.children().size(), local_node->children().size()); // Recursively iterate children first for simplicity, as the order doesn't // matter. for (size_t i = 0; i < remote_node.children().size(); ++i) { const RemoteTreeNode& child_remote = remote_node.children()[i]; CHECK_LT(i, local_node->children().size()); const bookmarks::BookmarkNode* child_local = local_node->children()[i].get(); MigrateBookmarksInSubtreeWithoutClientTagHash(child_remote, child_local); } // Nothing to do for permanent folders. if (!remote_node.entity().server_defined_unique_tag.empty()) { return; } CHECK_EQ(remote_node.entity().specifics.bookmark().guid(), local_node->uuid().AsLowercaseString()); // Nothing to do if this entity already uses a client tag hash. if (!remote_node.entity().client_tag_hash.value().empty()) { return; } // Guaranteed by HasExpectedBookmarkGuid(). CHECK(!remote_node.entity().originator_cache_guid.empty() || !remote_node.entity().originator_client_item_id.empty()); const SyncedBookmarkTrackerEntity* old_entity = bookmark_tracker_->GetEntityForBookmarkNode(local_node); CHECK(old_entity); const base::Time creation_time = syncer::ProtoTimeToTime(old_entity->metadata().creation_time()); const syncer::UniquePosition pos = syncer::UniquePosition::FromProto( old_entity->metadata().unique_position()); bookmark_tracker_->MarkDeleted(old_entity, FROM_HERE); // TODO(crbug.com/376641665): Consider generating new UUIDs deterministically // rather than randomly to guard against concurrent clients or interrupted // migrations. const base::Uuid new_guid = base::Uuid::GenerateRandomV4(); local_node = ReplaceBookmarkNodeUuid(local_node, new_guid, bookmark_model_); const sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode( local_node, bookmark_model_, pos.ToProto(), /*force_favicon_load=*/true); bookmark_tracker_->AddLocalCreation(local_node, /*sync_id=*/new_guid.AsLowercaseString(), creation_time, specifics); // Make sure all direct children are marked for commit, because their parent // changed. for (const std::unique_ptr& child : local_node->children()) { SyncedBookmarkTrackerEntity* child_entity = bookmark_tracker_->GetEntityForBookmarkNode(child.get()); CHECK(child_entity); child_entity->IncrementSequenceNumber(); } } void BookmarkModelMerger::MergeSubtree( const bookmarks::BookmarkNode* local_subtree_root, const RemoteTreeNode& remote_node) { const EntityData& remote_update_entity = remote_node.entity(); SyncedBookmarkTrackerEntity* entity = bookmark_tracker_->AddRemote( local_subtree_root, remote_update_entity.id, remote_node.response_version(), remote_update_entity.creation_time, remote_update_entity.specifics); const bool is_reupload_needed = !local_subtree_root->is_permanent_node() && IsBookmarkEntityReuploadNeeded(remote_update_entity); if (is_reupload_needed) { entity->IncrementSequenceNumber(); } LogBookmarkReuploadNeeded(is_reupload_needed); // If there are remote child updates, try to match them. for (size_t remote_index = 0; remote_index < remote_node.children().size(); ++remote_index) { // TODO(crbug.com/40118203): change to DCHECK after investigating. // Here is expected that all nodes to the left of current |remote_index| are // filled with remote updates. All local nodes which are not merged will be // added later. CHECK_LE(remote_index, local_subtree_root->children().size()); const RemoteTreeNode& remote_child = remote_node.children().at(remote_index); const bookmarks::BookmarkNode* matching_local_node = FindMatchingLocalNode(remote_child, local_subtree_root, remote_index); // If no match found, create a corresponding local node. if (!matching_local_node) { ProcessRemoteCreation(remote_child, local_subtree_root, remote_index); continue; } DCHECK(!local_subtree_root->HasAncestor(matching_local_node)); // Move if required, no-op otherwise. bookmark_model_->Move(matching_local_node, local_subtree_root, remote_index); // Since nodes are matching, their subtrees should be merged as well. matching_local_node = UpdateBookmarkNodeFromSpecificsIncludingUuid( matching_local_node, remote_child); MergeSubtree(matching_local_node, remote_child); } // At this point all the children of |remote_node| have corresponding local // nodes under |local_subtree_root| and they are all in the right positions: // from 0 to remote_node.children().size() - 1. // // This means, the children starting from remote_node.children().size() in // the parent bookmark node are the ones that are not present in the parent // sync node and not tracked yet. So create all of the remaining local nodes. DCHECK_LE(remote_node.children().size(), local_subtree_root->children().size()); for (size_t i = remote_node.children().size(); i < local_subtree_root->children().size(); ++i) { // If local node has been or will be matched by UUID, skip it. if (FindMatchingRemoteNodeByUuid(local_subtree_root->children()[i].get())) { continue; } ProcessLocalCreation(local_subtree_root, i); } } const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNode( const RemoteTreeNode& remote_child, const bookmarks::BookmarkNode* local_parent, size_t local_child_start_index) const { DCHECK(local_parent); // Try to match child by UUID. If we can't, try to match child by semantics. const bookmarks::BookmarkNode* matching_local_node_by_uuid = FindMatchingLocalNodeByUuid(remote_child); if (matching_local_node_by_uuid) { return matching_local_node_by_uuid; } // All local nodes up to |remote_index-1| have processed already. Look for a // matching local node starting with the local node at position // |local_child_start_index|. FindMatchingChildBySemanticsStartingAt() // returns kInvalidIndex in the case where no semantics match was found or // the semantics match found is UUID-matchable to a different node. const size_t local_index = FindMatchingChildBySemanticsStartingAt( /*remote_node=*/remote_child, /*local_parent=*/local_parent, /*starting_child_index=*/local_child_start_index); if (local_index == kInvalidIndex) { // If no match found, return. return nullptr; } // The child at |local_index| has matched by semantics, which also means it // does not match by UUID to any other remote node. const bookmarks::BookmarkNode* matching_local_node_by_semantics = local_parent->children()[local_index].get(); DCHECK(!FindMatchingRemoteNodeByUuid(matching_local_node_by_semantics)); return matching_local_node_by_semantics; } const bookmarks::BookmarkNode* BookmarkModelMerger::UpdateBookmarkNodeFromSpecificsIncludingUuid( const bookmarks::BookmarkNode* local_node, const RemoteTreeNode& remote_node) { DCHECK(local_node); DCHECK(!local_node->is_permanent_node()); // Ensure bookmarks have the same URL, otherwise they would not have been // matched. DCHECK(local_node->is_folder() || local_node->url() == GURL(remote_node.entity().specifics.bookmark().url())); const EntityData& remote_update_entity = remote_node.entity(); const sync_pb::BookmarkSpecifics& specifics = remote_update_entity.specifics.bookmark(); // Update the local UUID if necessary for semantic matches (it's obviously not // needed for UUID-based matches). const bookmarks::BookmarkNode* possibly_replaced_local_node = local_node; if (!specifics.guid().empty() && specifics.guid() != local_node->uuid().AsLowercaseString()) { // If it's a semantic match, neither of the nodes should be involved in any // UUID-based match. DCHECK(!FindMatchingLocalNodeByUuid(remote_node)); DCHECK(!FindMatchingRemoteNodeByUuid(local_node)); possibly_replaced_local_node = ReplaceBookmarkNodeUuid( local_node, base::Uuid::ParseLowercase(specifics.guid()), bookmark_model_); // TODO(rushans): remove the code below since DCHECKs above guarantee that // |uuid_to_match_map_| has no such UUID. // // Update |uuid_to_match_map_| to avoid pointing to a deleted node. This // should not be required in practice, because the algorithm processes each // UUID once, but let's update nevertheless to avoid future issues. const auto it = uuid_to_match_map_.find(possibly_replaced_local_node->uuid()); if (it != uuid_to_match_map_.end() && it->second.local_node == local_node) { it->second.local_node = possibly_replaced_local_node; } } // Update all fields, where no-op changes are handled well. UpdateBookmarkNodeFromSpecifics(specifics, possibly_replaced_local_node, bookmark_model_, favicon_service_); return possibly_replaced_local_node; } void BookmarkModelMerger::ProcessRemoteCreation( const RemoteTreeNode& remote_node, const bookmarks::BookmarkNode* local_parent, size_t index) { TRACE_EVENT0("sync", "BookmarkModelMerger::ProcessRemoteCreation"); DCHECK(!FindMatchingLocalNodeByUuid(remote_node)); const EntityData& remote_update_entity = remote_node.entity(); DCHECK(IsValidBookmarkSpecifics(remote_update_entity.specifics.bookmark())); const sync_pb::EntitySpecifics& specifics = remote_node.entity().specifics; const bookmarks::BookmarkNode* bookmark_node = CreateBookmarkNodeFromSpecifics(specifics.bookmark(), local_parent, index, bookmark_model_, favicon_service_); DCHECK(bookmark_node); SyncedBookmarkTrackerEntity* entity = bookmark_tracker_->AddRemote( bookmark_node, remote_update_entity.id, remote_node.response_version(), remote_update_entity.creation_time, specifics); const bool is_reupload_needed = IsBookmarkEntityReuploadNeeded(remote_node.entity()); if (is_reupload_needed) { entity->IncrementSequenceNumber(); } LogBookmarkReuploadNeeded(is_reupload_needed); // Recursively, match by UUID or, if not possible, create local node for all // child remote nodes. size_t i = 0; for (const RemoteTreeNode& remote_child : remote_node.children()) { // TODO(crbug.com/40118203): change to DCHECK after investigating of some // crashes. CHECK_LE(i, bookmark_node->children().size()); const bookmarks::BookmarkNode* local_child = FindMatchingLocalNodeByUuid(remote_child); if (!local_child) { ProcessRemoteCreation(remote_child, bookmark_node, i++); continue; } bookmark_model_->Move(local_child, bookmark_node, i++); local_child = UpdateBookmarkNodeFromSpecificsIncludingUuid(local_child, remote_child); MergeSubtree(local_child, remote_child); } } void BookmarkModelMerger::ProcessLocalCreation( const bookmarks::BookmarkNode* parent, size_t index) { DCHECK_LE(index, parent->children().size()); const SyncedBookmarkTrackerEntity* parent_entity = bookmark_tracker_->GetEntityForBookmarkNode(parent); // Since we are merging top down, parent entity must be tracked. DCHECK(parent_entity); // Assign a temp server id for the entity. Will be overridden by the actual // server id upon receiving commit response. const bookmarks::BookmarkNode* node = parent->children()[index].get(); DCHECK(!FindMatchingRemoteNodeByUuid(node)); // The node's UUID cannot run into collisions because // FindGuidMatchesOrReassignLocal() takes care of reassigning local UUIDs if // they won't actually be merged with the remote bookmark with the same UUID // (e.g. incompatible types). const base::Time creation_time = base::Time::Now(); const syncer::UniquePosition::Suffix suffix = syncer::UniquePosition::GenerateSuffix( SyncedBookmarkTracker::GetClientTagHashFromUuid(node->uuid())); // Locally created nodes aren't tracked and hence don't have a unique position // yet so we need to produce new ones. const syncer::UniquePosition pos = GenerateUniquePositionForLocalCreation(parent, index, suffix); const sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode( node, bookmark_model_, pos.ToProto(), /*force_favicon_load=*/true); bookmark_tracker_->AddLocalCreation( node, /*sync_id=*/node->uuid().AsLowercaseString(), creation_time, specifics); for (size_t i = 0; i < node->children().size(); ++i) { // If a local node hasn't matched with any remote entity, its descendants // will neither, unless they have been or will be matched by UUID, in which // case we skip them for now. if (FindMatchingRemoteNodeByUuid(node->children()[i].get())) { continue; } ProcessLocalCreation(/*parent=*/node, i); } } size_t BookmarkModelMerger::FindMatchingChildBySemanticsStartingAt( const RemoteTreeNode& remote_node, const bookmarks::BookmarkNode* local_parent, size_t starting_child_index) const { DCHECK(local_parent); TRACE_EVENT0("sync", "BookmarkModelMerger::FindMatchingChildBySemanticsStartingAt"); const auto& children = local_parent->children(); DCHECK_LE(starting_child_index, children.size()); const EntityData& remote_entity = remote_node.entity(); // Precompute the remote title and URL before searching for a matching local // node. const std::string remote_canonicalized_title = LegacyCanonicalizedTitleFromSpecifics(remote_entity.specifics.bookmark()); const sync_pb::BookmarkSpecifics::Type remote_type = remote_entity.specifics.bookmark().type(); GURL remote_url; if (remote_type == sync_pb::BookmarkSpecifics::URL) { remote_url = GURL(remote_entity.specifics.bookmark().url()); } const auto it = std::find_if( children.cbegin() + starting_child_index, children.cend(), [this, &remote_canonicalized_title, &remote_url, remote_type](const auto& child) { return !FindMatchingRemoteNodeByUuid(child.get()) && NodeSemanticsMatch(child.get(), remote_canonicalized_title, remote_url, remote_type); }); return (it == children.cend()) ? kInvalidIndex : (it - children.cbegin()); } const BookmarkModelMerger::RemoteTreeNode* BookmarkModelMerger::FindMatchingRemoteNodeByUuid( const bookmarks::BookmarkNode* local_node) const { DCHECK(local_node); const auto it = uuid_to_match_map_.find(local_node->uuid()); if (it == uuid_to_match_map_.end()) { return nullptr; } DCHECK_EQ(it->second.local_node, local_node); return it->second.remote_node; } const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNodeByUuid( const RemoteTreeNode& remote_node) const { const syncer::EntityData& remote_entity = remote_node.entity(); const auto it = uuid_to_match_map_.find( base::Uuid::ParseLowercase(remote_entity.specifics.bookmark().guid())); if (it == uuid_to_match_map_.end()) { return nullptr; } DCHECK_EQ(it->second.remote_node, &remote_node); return it->second.local_node; } syncer::UniquePosition BookmarkModelMerger::GenerateUniquePositionForLocalCreation( const bookmarks::BookmarkNode* parent, size_t index, const syncer::UniquePosition::Suffix& suffix) const { // Try to find last tracked preceding entity. It is not always the previous // one as it might be skipped if it has unprocessed remote matching by UUID // update. for (size_t i = index; i > 0; --i) { const SyncedBookmarkTrackerEntity* predecessor_entity = bookmark_tracker_->GetEntityForBookmarkNode( parent->children()[i - 1].get()); if (predecessor_entity != nullptr) { return syncer::UniquePosition::After( syncer::UniquePosition::FromProto( predecessor_entity->metadata().unique_position()), suffix); } DCHECK(FindMatchingRemoteNodeByUuid(parent->children()[i - 1].get())); } return syncer::UniquePosition::InitialPosition(suffix); } void BookmarkModelMerger::ReportTimeMetrics() { base::TimeDelta all_time_elapsed = base::TimeTicks::Now() - started_; base::UmaHistogramMediumTimes("Sync.BookmarkModelMergerTime", all_time_elapsed); if (remote_updates_size_ >= 10000) { base::UmaHistogramMediumTimes("Sync.BookmarkModelMergerTime.10kUpdates", all_time_elapsed); } if (remote_updates_size_ >= 50000) { base::UmaHistogramMediumTimes("Sync.BookmarkModelMergerTime.50kUpdates", all_time_elapsed); } if (remote_updates_size_ >= 100000) { base::UmaHistogramMediumTimes("Sync.BookmarkModelMergerTime.100kUpdates", all_time_elapsed); } } } // namespace sync_bookmarks