bookmark_model_merger.cc | Explore in Territory

// 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 <algorithm>
#include <string>
#include <utility>

#include "base/containers/contains.h"
#include "base/logging.h"
#include "base/metrics/histogram_functions.h"
#include "base/ranges/algorithm.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/hash_util.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 "ui/base/models/tree_node_iterator.h"

EntityData;
UpdateResponseData;
UpdateResponseDataList;

namespace sync_bookmarks {

namespace {

static const size_t kInvalidIndex = …;

// The sync protocol identifies top-level entities by means of well-known tags,
// (aka server defined tags) which should not be confused with titles or client
// tags that aren't supported by bookmarks (at the time of writing). Each tag
// corresponds to a singleton instance of a particular top-level node in a
// user's share; the tags are consistent across users. The tags allow us to
// locate the specific folders whose contents we care about synchronizing,
// without having to do a lookup by name or path.  The tags should not be made
// user-visible. For example, the tag "bookmark_bar" represents the permanent
// node for bookmarks bar in Chrome. The tag "other_bookmarks" represents the
// permanent folder Other Bookmarks in Chrome.
//
// It is the responsibility of something upstream (at time of writing, the sync
// server) to create these tagged nodes when initializing sync for the first
// time for a user.  Thus, once the backend finishes initializing, the
// SyncService can rely on the presence of tagged nodes.
const char kBookmarkBarTag[] = …;
const char kMobileBookmarksTag[] = …;
const char kOtherBookmarksTag[] = …;

// 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 = …;

// The value must be a list since there is a container using pointers to its
// elements.
UpdatesPerParentUuid;

// 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 { … };
// 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 { … };
// LINT.ThenChange(/tools/metrics/histograms/metadata/sync/enums.xml:RemoteBookmarkUpdateError)

void LogProblematicBookmark(RemoteBookmarkUpdateError problem) { … }

void LogBookmarkReuploadNeeded(bool 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) { … }

// Gets the bookmark UUID corresponding to a permanent folder identified by
// |served_defined_unique_tag| or an invalid UUID if the tag is unknown.
// |server_defined_unique_tag| must not be empty.
base::Uuid GetPermanentFolderUuidForServerDefinedUniqueTag(
    const std::string& server_defined_unique_tag) { … }

std::string LegacyCanonicalizedTitleFromSpecifics(
    const sync_pb::BookmarkSpecifics& specifics) { … }

// 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) { … }

BookmarksUuidDuplicates MatchBookmarksUuidDuplicates(
    const UpdateResponseData& update,
    const UpdateResponseData& duplicate_update) { … }

// 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) { … }

void DeduplicateValidUpdatesByUuid(
    UpdatesPerParentUuid* updates_per_parent_uuid) { … }

// 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) { … }

// 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) { … }

struct GroupedUpdates { … };

// 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) { … }

int GetNumUnsyncedEntities(const SyncedBookmarkTracker* tracker) { … }

}  // 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(
    std::unordered_map<base::Uuid, const RemoteTreeNode*, base::UuidHash>*
        uuid_to_remote_node_map) const { … }

// static
bool BookmarkModelMerger::RemoteTreeNode::UniquePositionLessThan(
    const RemoteTreeNode& lhs,
    const RemoteTreeNode& rhs) { … }

// static
BookmarkModelMerger::RemoteTreeNode
BookmarkModelMerger::RemoteTreeNode::BuildTree(
    UpdateResponseData update,
    size_t max_depth,
    UpdatesPerParentUuid* updates_per_parent_uuid) { … }

BookmarkModelMerger::BookmarkModelMerger(
    UpdateResponseDataList updates,
    BookmarkModelView* bookmark_model,
    favicon::FaviconService* favicon_service,
    SyncedBookmarkTracker* bookmark_tracker)
    : … { … }

BookmarkModelMerger::~BookmarkModelMerger() = default;

void BookmarkModelMerger::Merge() { … }

// static
BookmarkModelMerger::RemoteForest BookmarkModelMerger::BuildRemoteForest(
    syncer::UpdateResponseDataList updates,
    SyncedBookmarkTracker* tracker_for_recording_ignored_updates) { … }

// static
int BookmarkModelMerger::CountRemoteTreeNodeDescendantsForUma(
    const RemoteTreeNode& node) { … }

// static
std::unordered_map<base::Uuid, BookmarkModelMerger::GuidMatch, base::UuidHash>
BookmarkModelMerger::FindGuidMatchesOrReassignLocal(
    const RemoteForest& remote_forest,
    BookmarkModelView* bookmark_model) { … }

void BookmarkModelMerger::MergeSubtree(
    const bookmarks::BookmarkNode* local_subtree_root,
    const RemoteTreeNode& remote_node) { … }

const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNode(
    const RemoteTreeNode& remote_child,
    const bookmarks::BookmarkNode* local_parent,
    size_t local_child_start_index) const { … }

const bookmarks::BookmarkNode*
BookmarkModelMerger::UpdateBookmarkNodeFromSpecificsIncludingUuid(
    const bookmarks::BookmarkNode* local_node,
    const RemoteTreeNode& remote_node) { … }

void BookmarkModelMerger::ProcessRemoteCreation(
    const RemoteTreeNode& remote_node,
    const bookmarks::BookmarkNode* local_parent,
    size_t index) { … }

void BookmarkModelMerger::ProcessLocalCreation(
    const bookmarks::BookmarkNode* parent,
    size_t index) { … }

size_t BookmarkModelMerger::FindMatchingChildBySemanticsStartingAt(
    const RemoteTreeNode& remote_node,
    const bookmarks::BookmarkNode* local_parent,
    size_t starting_child_index) const { … }

const BookmarkModelMerger::RemoteTreeNode*
BookmarkModelMerger::FindMatchingRemoteNodeByUuid(
    const bookmarks::BookmarkNode* local_node) const { … }

const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNodeByUuid(
    const RemoteTreeNode& remote_node) const { … }

syncer::UniquePosition
BookmarkModelMerger::GenerateUniquePositionForLocalCreation(
    const bookmarks::BookmarkNode* parent,
    size_t index,
    const std::string& suffix) const { … }

void BookmarkModelMerger::ReportTimeMetrics() { … }

}  // namespace sync_bookmarks
chromium/components/sync_bookmarks/bookmark_model_merger.cc
