bookmark_model_merger.cc 42 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055
  1. // Copyright 2018 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/sync_bookmarks/bookmark_model_merger.h"
  5. #include <algorithm>
  6. #include <string>
  7. #include <utility>
  8. #include "base/containers/contains.h"
  9. #include "base/guid.h"
  10. #include "base/logging.h"
  11. #include "base/metrics/histogram_functions.h"
  12. #include "base/ranges/algorithm.h"
  13. #include "base/strings/string_util.h"
  14. #include "base/strings/utf_string_conversions.h"
  15. #include "base/trace_event/trace_event.h"
  16. #include "components/bookmarks/browser/bookmark_model.h"
  17. #include "components/bookmarks/browser/bookmark_node.h"
  18. #include "components/sync/base/hash_util.h"
  19. #include "components/sync/protocol/bookmark_specifics.pb.h"
  20. #include "components/sync/protocol/entity_metadata.pb.h"
  21. #include "components/sync/protocol/entity_specifics.pb.h"
  22. #include "components/sync_bookmarks/bookmark_specifics_conversions.h"
  23. #include "components/sync_bookmarks/switches.h"
  24. #include "components/sync_bookmarks/synced_bookmark_tracker.h"
  25. #include "components/sync_bookmarks/synced_bookmark_tracker_entity.h"
  26. #include "ui/base/models/tree_node_iterator.h"
  27. using syncer::EntityData;
  28. using syncer::UpdateResponseData;
  29. using syncer::UpdateResponseDataList;
  30. namespace sync_bookmarks {
  31. namespace {
  32. static const size_t kInvalidIndex = -1;
  33. // The sync protocol identifies top-level entities by means of well-known tags,
  34. // (aka server defined tags) which should not be confused with titles or client
  35. // tags that aren't supported by bookmarks (at the time of writing). Each tag
  36. // corresponds to a singleton instance of a particular top-level node in a
  37. // user's share; the tags are consistent across users. The tags allow us to
  38. // locate the specific folders whose contents we care about synchronizing,
  39. // without having to do a lookup by name or path. The tags should not be made
  40. // user-visible. For example, the tag "bookmark_bar" represents the permanent
  41. // node for bookmarks bar in Chrome. The tag "other_bookmarks" represents the
  42. // permanent folder Other Bookmarks in Chrome.
  43. //
  44. // It is the responsibility of something upstream (at time of writing, the sync
  45. // server) to create these tagged nodes when initializing sync for the first
  46. // time for a user. Thus, once the backend finishes initializing, the
  47. // SyncService can rely on the presence of tagged nodes.
  48. const char kBookmarkBarTag[] = "bookmark_bar";
  49. const char kMobileBookmarksTag[] = "synced_bookmarks";
  50. const char kOtherBookmarksTag[] = "other_bookmarks";
  51. // Maximum depth to sync bookmarks tree to protect against stack overflow.
  52. // Keep in sync with |base::internal::kAbsoluteMaxDepth| in json_common.h.
  53. const size_t kMaxBookmarkTreeDepth = 200;
  54. // The value must be a list since there is a container using pointers to its
  55. // elements.
  56. using UpdatesPerParentGUID =
  57. std::unordered_map<base::GUID,
  58. std::list<syncer::UpdateResponseData>,
  59. base::GUIDHash>;
  60. // These values are persisted to logs. Entries should not be renumbered and
  61. // numeric values should never be reused. When adding values, be certain to also
  62. // update the corresponding definition in enums.xml and the
  63. // ExpectedBookmarksGUIDDuplicates in unittests.
  64. enum class BookmarksGUIDDuplicates {
  65. // Both entities are URLs with matching URLs in specifics. Entities may have
  66. // different titles or parents.
  67. kMatchingUrls = 0,
  68. // Both entities are folders with matching titles. Entities may have different
  69. // parents.
  70. kMatchingFolders = 1,
  71. // Both entities are URLs, but they have different URLs.
  72. kDifferentUrls = 2,
  73. // Both entities are folders with different titles.
  74. kDifferentFolders = 3,
  75. // Entities have different types.
  76. kDifferentTypes = 4,
  77. kMaxValue = kDifferentTypes,
  78. };
  79. // Used in metrics: "Sync.ProblematicServerSideBookmarksDuringMerge". These
  80. // values are persisted to logs. Entries should not be renumbered and numeric
  81. // values should never be reused. Note the existence of gaps because the
  82. // metric enum is reused for another UMA metric,
  83. // Sync.ProblematicServerSideBookmarks, which logs the analogous error cases
  84. // for non-initial updates.
  85. enum class RemoteBookmarkUpdateError {
  86. // Invalid specifics.
  87. kInvalidSpecifics = 1,
  88. // Invalid unique position.
  89. kInvalidUniquePosition = 2,
  90. // Parent entity not found in server.
  91. kMissingParentEntity = 4,
  92. // The bookmark's GUID did not match the originator client item ID.
  93. kUnexpectedGuid = 9,
  94. // Parent is not a folder.
  95. kParentNotFolder = 10,
  96. // Unknown/unsupported permanent folder.
  97. kUnsupportedPermanentFolder = 13,
  98. // A bookmark that is not contained in any permanent folder and is instead
  99. // hanging (directly or indirectly) from the root node.
  100. // kDeprecatedDescendantOfRootNodeWithoutPermanentFolder = 14,
  101. kMaxValue = kUnsupportedPermanentFolder,
  102. };
  103. void LogProblematicBookmark(RemoteBookmarkUpdateError problem) {
  104. base::UmaHistogramEnumeration(
  105. "Sync.ProblematicServerSideBookmarksDuringMerge", problem);
  106. }
  107. void LogBookmarkReuploadNeeded(bool is_reupload_needed) {
  108. base::UmaHistogramBoolean("Sync.BookmarkEntityReuploadNeeded.OnInitialMerge",
  109. is_reupload_needed);
  110. }
  111. // Gets the bookmark node corresponding to a permanent folder identified by
  112. // |server_defined_unique_tag| or null of the tag is unknown. |bookmark_model|
  113. // must not be null and |server_defined_unique_tag| must not be empty.
  114. const bookmarks::BookmarkNode* GetPermanentFolderForServerDefinedUniqueTag(
  115. const bookmarks::BookmarkModel* bookmark_model,
  116. const std::string& server_defined_unique_tag) {
  117. DCHECK(bookmark_model);
  118. DCHECK(!server_defined_unique_tag.empty());
  119. // WARNING: Keep this logic consistent with the analogous in
  120. // GetPermanentFolderGUIDForServerDefinedUniqueTag().
  121. if (server_defined_unique_tag == kBookmarkBarTag) {
  122. return bookmark_model->bookmark_bar_node();
  123. }
  124. if (server_defined_unique_tag == kOtherBookmarksTag) {
  125. return bookmark_model->other_node();
  126. }
  127. if (server_defined_unique_tag == kMobileBookmarksTag) {
  128. return bookmark_model->mobile_node();
  129. }
  130. return nullptr;
  131. }
  132. // Gets the bookmark GUID corresponding to a permanent folder identified by
  133. // |served_defined_unique_tag| or an invalid GUID if the tag is unknown.
  134. // |server_defined_unique_tag| must not be empty.
  135. base::GUID GetPermanentFolderGUIDForServerDefinedUniqueTag(
  136. const std::string& server_defined_unique_tag) {
  137. DCHECK(!server_defined_unique_tag.empty());
  138. // WARNING: Keep this logic consistent with the analogous in
  139. // GetPermanentFolderForServerDefinedUniqueTag().
  140. if (server_defined_unique_tag == kBookmarkBarTag) {
  141. return base::GUID::ParseLowercase(
  142. bookmarks::BookmarkNode::kBookmarkBarNodeGuid);
  143. }
  144. if (server_defined_unique_tag == kOtherBookmarksTag) {
  145. return base::GUID::ParseLowercase(
  146. bookmarks::BookmarkNode::kOtherBookmarksNodeGuid);
  147. }
  148. if (server_defined_unique_tag == kMobileBookmarksTag) {
  149. return base::GUID::ParseLowercase(
  150. bookmarks::BookmarkNode::kMobileBookmarksNodeGuid);
  151. }
  152. return base::GUID();
  153. }
  154. std::string LegacyCanonicalizedTitleFromSpecifics(
  155. const sync_pb::BookmarkSpecifics& specifics) {
  156. if (specifics.has_full_title()) {
  157. return FullTitleToLegacyCanonicalizedTitle(specifics.full_title());
  158. }
  159. return specifics.legacy_canonicalized_title();
  160. }
  161. // Heuristic to consider two nodes (local and remote) a match by semantics for
  162. // the purpose of merging. Two folders match by semantics if they have the same
  163. // title, two bookmarks match by semantics if they have the same title and url.
  164. // A folder and a bookmark never match.
  165. bool NodeSemanticsMatch(const bookmarks::BookmarkNode* local_node,
  166. const std::string& remote_canonicalized_title,
  167. const GURL& remote_url,
  168. sync_pb::BookmarkSpecifics::Type remote_type) {
  169. if (GetProtoTypeFromBookmarkNode(local_node) != remote_type) {
  170. return false;
  171. }
  172. if (remote_type == sync_pb::BookmarkSpecifics::URL &&
  173. local_node->url() != remote_url) {
  174. return false;
  175. }
  176. const std::string local_title = base::UTF16ToUTF8(local_node->GetTitle());
  177. // Titles match if they are identical or the remote one is the canonical form
  178. // of the local one. The latter is the case when a legacy client has
  179. // canonicalized the same local title before committing it. Modern clients
  180. // don't canonicalize titles anymore.
  181. // TODO(rushans): the comment above is off.
  182. if (local_title != remote_canonicalized_title &&
  183. sync_bookmarks::FullTitleToLegacyCanonicalizedTitle(local_title) !=
  184. remote_canonicalized_title) {
  185. return false;
  186. }
  187. return true;
  188. }
  189. BookmarksGUIDDuplicates MatchBookmarksGUIDDuplicates(
  190. const UpdateResponseData& update,
  191. const UpdateResponseData& duplicate_update) {
  192. if (update.entity.specifics.bookmark().type() !=
  193. duplicate_update.entity.specifics.bookmark().type()) {
  194. return BookmarksGUIDDuplicates::kDifferentTypes;
  195. }
  196. switch (update.entity.specifics.bookmark().type()) {
  197. case sync_pb::BookmarkSpecifics::UNSPECIFIED:
  198. NOTREACHED();
  199. break;
  200. case sync_pb::BookmarkSpecifics::URL: {
  201. const bool matching_urls =
  202. update.entity.specifics.bookmark().url() ==
  203. duplicate_update.entity.specifics.bookmark().url();
  204. return matching_urls ? BookmarksGUIDDuplicates::kMatchingUrls
  205. : BookmarksGUIDDuplicates::kDifferentUrls;
  206. }
  207. case sync_pb::BookmarkSpecifics::FOLDER: {
  208. // Both entities are folders.
  209. const bool matching_titles =
  210. LegacyCanonicalizedTitleFromSpecifics(
  211. update.entity.specifics.bookmark()) ==
  212. LegacyCanonicalizedTitleFromSpecifics(
  213. duplicate_update.entity.specifics.bookmark());
  214. return matching_titles ? BookmarksGUIDDuplicates::kMatchingFolders
  215. : BookmarksGUIDDuplicates::kDifferentFolders;
  216. }
  217. }
  218. NOTREACHED();
  219. return BookmarksGUIDDuplicates();
  220. }
  221. // Returns true the |next_update| is selected to keep and the |previous_update|
  222. // should be removed. False is returned otherwise. |next_update| and
  223. // |previous_update| must have the same GUID.
  224. bool CompareDuplicateUpdates(const UpdateResponseData& next_update,
  225. const UpdateResponseData& previous_update) {
  226. DCHECK_EQ(next_update.entity.specifics.bookmark().guid(),
  227. previous_update.entity.specifics.bookmark().guid());
  228. DCHECK_NE(next_update.entity.id, previous_update.entity.id);
  229. if (next_update.entity.specifics.bookmark().type() !=
  230. previous_update.entity.specifics.bookmark().type()) {
  231. // There are two entities, one of them is a folder and another one is a
  232. // URL. Prefer to save the folder as it may contain many bookmarks.
  233. return next_update.entity.specifics.bookmark().type() ==
  234. sync_pb::BookmarkSpecifics::FOLDER;
  235. }
  236. // Choose the latest element to keep if both updates have the same type.
  237. return next_update.entity.creation_time >
  238. previous_update.entity.creation_time;
  239. }
  240. void DeduplicateValidUpdatesByGUID(
  241. UpdatesPerParentGUID* updates_per_parent_guid) {
  242. DCHECK(updates_per_parent_guid);
  243. std::unordered_map<base::GUID, std::list<UpdateResponseData>::iterator,
  244. base::GUIDHash>
  245. guid_to_update;
  246. for (auto& [parent_guid, updates] : *updates_per_parent_guid) {
  247. auto updates_iter = updates.begin();
  248. while (updates_iter != updates.end()) {
  249. const UpdateResponseData& update = *updates_iter;
  250. DCHECK(!update.entity.is_deleted());
  251. DCHECK(update.entity.server_defined_unique_tag.empty());
  252. const base::GUID guid_in_specifics =
  253. base::GUID::ParseLowercase(update.entity.specifics.bookmark().guid());
  254. DCHECK(guid_in_specifics.is_valid());
  255. auto [it, success] =
  256. guid_to_update.emplace(guid_in_specifics, updates_iter);
  257. if (success) {
  258. ++updates_iter;
  259. continue;
  260. }
  261. const auto& [guid, previous_update_it] = *it;
  262. DCHECK_EQ(guid_in_specifics.AsLowercaseString(),
  263. previous_update_it->entity.specifics.bookmark().guid());
  264. DLOG(ERROR) << "Duplicate guid for new sync ID " << update.entity.id
  265. << " and original sync ID " << previous_update_it->entity.id;
  266. const BookmarksGUIDDuplicates match_result =
  267. MatchBookmarksGUIDDuplicates(update, *previous_update_it);
  268. base::UmaHistogramEnumeration("Sync.BookmarksGUIDDuplicates",
  269. match_result);
  270. if (CompareDuplicateUpdates(/*next_update=*/update,
  271. /*previous_update=*/*previous_update_it)) {
  272. updates.erase(previous_update_it);
  273. guid_to_update[guid_in_specifics] = updates_iter;
  274. ++updates_iter;
  275. } else {
  276. updates_iter = updates.erase(updates_iter);
  277. }
  278. }
  279. }
  280. }
  281. // Checks that the |update| is valid and returns false otherwise. It is used to
  282. // verify non-deletion updates. |update| must not be a deletion and a permanent
  283. // node (they are processed in a different way).
  284. bool IsValidUpdate(const UpdateResponseData& update) {
  285. const EntityData& update_entity = update.entity;
  286. DCHECK(!update_entity.is_deleted());
  287. DCHECK(update_entity.server_defined_unique_tag.empty());
  288. if (!IsValidBookmarkSpecifics(update_entity.specifics.bookmark())) {
  289. // Ignore updates with invalid specifics.
  290. DLOG(ERROR) << "Remote update with invalid specifics";
  291. LogProblematicBookmark(RemoteBookmarkUpdateError::kInvalidSpecifics);
  292. return false;
  293. }
  294. if (!HasExpectedBookmarkGuid(update_entity.specifics.bookmark(),
  295. update_entity.client_tag_hash,
  296. update_entity.originator_cache_guid,
  297. update_entity.originator_client_item_id)) {
  298. // Ignore updates with an unexpected GUID.
  299. DLOG(ERROR) << "Remote update with unexpected GUID";
  300. LogProblematicBookmark(RemoteBookmarkUpdateError::kUnexpectedGuid);
  301. return false;
  302. }
  303. return true;
  304. }
  305. // Returns the GUID determined by a remote update, which may be an update for a
  306. // permanent folder or a regular bookmark node.
  307. base::GUID GetGUIDForUpdate(const UpdateResponseData& update) {
  308. if (!update.entity.server_defined_unique_tag.empty()) {
  309. return GetPermanentFolderGUIDForServerDefinedUniqueTag(
  310. update.entity.server_defined_unique_tag);
  311. }
  312. DCHECK(IsValidUpdate(update));
  313. return base::GUID::ParseLowercase(update.entity.specifics.bookmark().guid());
  314. }
  315. struct GroupedUpdates {
  316. // |updates_per_parent_guid| contains all valid updates grouped by their
  317. // |parent_guid|. Permanent nodes and deletions are filtered out. Permanent
  318. // nodes are stored in a dedicated list |permanent_node_updates|.
  319. UpdatesPerParentGUID updates_per_parent_guid;
  320. UpdateResponseDataList permanent_node_updates;
  321. };
  322. // Groups all valid updates by the GUID of their parent. Permanent nodes are
  323. // grouped in a dedicated |permanent_node_updates| list in a returned value.
  324. GroupedUpdates GroupValidUpdates(UpdateResponseDataList updates) {
  325. GroupedUpdates grouped_updates;
  326. int num_valid_updates = 0;
  327. for (UpdateResponseData& update : updates) {
  328. const EntityData& update_entity = update.entity;
  329. if (update_entity.is_deleted()) {
  330. continue;
  331. }
  332. // Special-case the root folder to avoid recording
  333. // |RemoteBookmarkUpdateError::kUnsupportedPermanentFolder|.
  334. if (update_entity.server_defined_unique_tag ==
  335. syncer::ModelTypeToRootTag(syncer::BOOKMARKS)) {
  336. ++num_valid_updates;
  337. continue;
  338. }
  339. // Non-root permanent folders don't need further validation.
  340. if (!update_entity.server_defined_unique_tag.empty()) {
  341. ++num_valid_updates;
  342. grouped_updates.permanent_node_updates.push_back(std::move(update));
  343. continue;
  344. }
  345. // Regular (non-permanent) node updates must pass IsValidUpdate().
  346. if (!IsValidUpdate(update)) {
  347. continue;
  348. }
  349. ++num_valid_updates;
  350. const base::GUID parent_guid = base::GUID::ParseLowercase(
  351. update_entity.specifics.bookmark().parent_guid());
  352. DCHECK(parent_guid.is_valid());
  353. grouped_updates.updates_per_parent_guid[parent_guid].push_back(
  354. std::move(update));
  355. }
  356. base::UmaHistogramCounts100000("Sync.BookmarkModelMerger.ValidInputUpdates",
  357. num_valid_updates);
  358. return grouped_updates;
  359. }
  360. int GetNumUnsyncedEntities(const SyncedBookmarkTracker* tracker) {
  361. DCHECK(tracker);
  362. int num_unsynced_entities = 0;
  363. for (const SyncedBookmarkTrackerEntity* entity : tracker->GetAllEntities()) {
  364. if (entity->IsUnsynced()) {
  365. ++num_unsynced_entities;
  366. }
  367. }
  368. return num_unsynced_entities;
  369. }
  370. } // namespace
  371. BookmarkModelMerger::RemoteTreeNode::RemoteTreeNode() = default;
  372. BookmarkModelMerger::RemoteTreeNode::~RemoteTreeNode() = default;
  373. BookmarkModelMerger::RemoteTreeNode::RemoteTreeNode(
  374. BookmarkModelMerger::RemoteTreeNode&&) = default;
  375. BookmarkModelMerger::RemoteTreeNode&
  376. BookmarkModelMerger::RemoteTreeNode::operator=(
  377. BookmarkModelMerger::RemoteTreeNode&&) = default;
  378. void BookmarkModelMerger::RemoteTreeNode::EmplaceSelfAndDescendantsByGUID(
  379. std::unordered_map<base::GUID, const RemoteTreeNode*, base::GUIDHash>*
  380. guid_to_remote_node_map) const {
  381. DCHECK(guid_to_remote_node_map);
  382. if (entity().server_defined_unique_tag.empty()) {
  383. const base::GUID guid =
  384. base::GUID::ParseLowercase(entity().specifics.bookmark().guid());
  385. DCHECK(guid.is_valid());
  386. // Duplicate GUIDs have been sorted out before.
  387. bool success = guid_to_remote_node_map->emplace(guid, this).second;
  388. DCHECK(success);
  389. }
  390. for (const RemoteTreeNode& child : children_) {
  391. child.EmplaceSelfAndDescendantsByGUID(guid_to_remote_node_map);
  392. }
  393. }
  394. // static
  395. bool BookmarkModelMerger::RemoteTreeNode::UniquePositionLessThan(
  396. const RemoteTreeNode& lhs,
  397. const RemoteTreeNode& rhs) {
  398. return lhs.unique_position_.LessThan(rhs.unique_position_);
  399. }
  400. // static
  401. BookmarkModelMerger::RemoteTreeNode
  402. BookmarkModelMerger::RemoteTreeNode::BuildTree(
  403. UpdateResponseData update,
  404. size_t max_depth,
  405. UpdatesPerParentGUID* updates_per_parent_guid) {
  406. DCHECK(updates_per_parent_guid);
  407. DCHECK(!update.entity.server_defined_unique_tag.empty() ||
  408. IsValidUpdate(update));
  409. // |guid| may be invalid for unsupported permanent nodes.
  410. const base::GUID guid = GetGUIDForUpdate(update);
  411. RemoteTreeNode node;
  412. node.update_ = std::move(update);
  413. node.unique_position_ = syncer::UniquePosition::FromProto(
  414. node.update_.entity.specifics.bookmark().unique_position());
  415. // Ensure we have not reached the maximum tree depth to guard against stack
  416. // overflows.
  417. if (max_depth == 0) {
  418. return node;
  419. }
  420. // Check to prevent creating empty lists in |updates_per_parent_guid| and
  421. // unnecessary rehashing.
  422. auto updates_per_parent_guid_iter = updates_per_parent_guid->find(guid);
  423. if (updates_per_parent_guid_iter == updates_per_parent_guid->end()) {
  424. return node;
  425. }
  426. DCHECK(!updates_per_parent_guid_iter->second.empty());
  427. DCHECK(guid.is_valid());
  428. // Only folders may have descendants (ignore them otherwise). Treat
  429. // permanent nodes as folders explicitly.
  430. if (node.update_.entity.specifics.bookmark().type() !=
  431. sync_pb::BookmarkSpecifics::FOLDER &&
  432. node.update_.entity.server_defined_unique_tag.empty()) {
  433. // Children of a non-folder are ignored.
  434. for (UpdateResponseData& child_update :
  435. updates_per_parent_guid_iter->second) {
  436. LogProblematicBookmark(RemoteBookmarkUpdateError::kParentNotFolder);
  437. // To avoid double-counting later for bucket |kMissingParentEntity|,
  438. // clear the update from the list as if it would have been moved.
  439. child_update.entity = EntityData();
  440. }
  441. return node;
  442. }
  443. // Populate descendants recursively.
  444. node.children_.reserve(updates_per_parent_guid_iter->second.size());
  445. for (UpdateResponseData& child_update :
  446. updates_per_parent_guid_iter->second) {
  447. DCHECK_EQ(child_update.entity.specifics.bookmark().parent_guid(),
  448. guid.AsLowercaseString());
  449. DCHECK(IsValidBookmarkSpecifics(child_update.entity.specifics.bookmark()));
  450. node.children_.push_back(BuildTree(std::move(child_update), max_depth - 1,
  451. updates_per_parent_guid));
  452. }
  453. // Sort the children according to their unique position.
  454. base::ranges::sort(node.children_, UniquePositionLessThan);
  455. return node;
  456. }
  457. BookmarkModelMerger::BookmarkModelMerger(
  458. UpdateResponseDataList updates,
  459. bookmarks::BookmarkModel* bookmark_model,
  460. favicon::FaviconService* favicon_service,
  461. SyncedBookmarkTracker* bookmark_tracker)
  462. : bookmark_model_(bookmark_model),
  463. favicon_service_(favicon_service),
  464. bookmark_tracker_(bookmark_tracker),
  465. remote_forest_(BuildRemoteForest(std::move(updates), bookmark_tracker)),
  466. guid_to_match_map_(
  467. FindGuidMatchesOrReassignLocal(remote_forest_, bookmark_model_)) {
  468. DCHECK(bookmark_tracker_->IsEmpty());
  469. DCHECK(favicon_service);
  470. int num_updates_in_forest = 0;
  471. for (const auto& [server_defined_unique_tag, root] : remote_forest_) {
  472. num_updates_in_forest += 1 + CountRemoteTreeNodeDescendantsForUma(root);
  473. }
  474. base::UmaHistogramCounts100000(
  475. "Sync.BookmarkModelMerger.ReachableInputUpdates", num_updates_in_forest);
  476. }
  477. BookmarkModelMerger::~BookmarkModelMerger() = default;
  478. void BookmarkModelMerger::Merge() {
  479. TRACE_EVENT0("sync", "BookmarkModelMerger::Merge");
  480. // Algorithm description:
  481. // Match up the roots and recursively do the following:
  482. // * For each remote node for the current remote (sync) parent node, either
  483. // find a local node with equal GUID anywhere throughout the tree or find
  484. // the best matching bookmark node under the corresponding local bookmark
  485. // parent node using semantics. If the found node has the same GUID as a
  486. // different remote bookmark, we do not consider it a semantics match, as
  487. // GUID matching takes precedence. If no matching node is found, create a
  488. // new bookmark node in the same position as the corresponding remote node.
  489. // If a matching node is found, update the properties of it from the
  490. // corresponding remote node.
  491. // * When all children remote nodes are done, add the extra children bookmark
  492. // nodes to the remote (sync) parent node, unless they will be later matched
  493. // by GUID.
  494. //
  495. // The semantics best match algorithm uses folder title or bookmark title/url
  496. // to perform the primary match. If there are multiple match candidates it
  497. // selects the first one.
  498. // Associate permanent folders.
  499. for (const auto& [server_defined_unique_tag, root] : remote_forest_) {
  500. DCHECK(!server_defined_unique_tag.empty());
  501. const bookmarks::BookmarkNode* permanent_folder =
  502. GetPermanentFolderForServerDefinedUniqueTag(bookmark_model_,
  503. server_defined_unique_tag);
  504. // Ignore unsupported permanent folders.
  505. if (!permanent_folder) {
  506. DCHECK(!GetPermanentFolderGUIDForServerDefinedUniqueTag(
  507. server_defined_unique_tag)
  508. .is_valid());
  509. LogProblematicBookmark(
  510. RemoteBookmarkUpdateError::kUnsupportedPermanentFolder);
  511. continue;
  512. }
  513. DCHECK_EQ(permanent_folder->guid(),
  514. GetPermanentFolderGUIDForServerDefinedUniqueTag(
  515. server_defined_unique_tag));
  516. MergeSubtree(/*local_node=*/permanent_folder,
  517. /*remote_node=*/root);
  518. }
  519. if (base::FeatureList::IsEnabled(switches::kSyncReuploadBookmarks)) {
  520. // When the reupload feature is enabled, all new empty trackers are
  521. // automatically reuploaded (since there are no entities to reupload). This
  522. // is used to disable reupload after initial merge.
  523. bookmark_tracker_->SetBookmarksReuploaded();
  524. }
  525. base::UmaHistogramCounts100000(
  526. "Sync.BookmarkModelMerger.UnsyncedEntitiesUponCompletion",
  527. GetNumUnsyncedEntities(bookmark_tracker_));
  528. }
  529. // static
  530. BookmarkModelMerger::RemoteForest BookmarkModelMerger::BuildRemoteForest(
  531. syncer::UpdateResponseDataList updates,
  532. SyncedBookmarkTracker* tracker_for_recording_ignored_updates) {
  533. TRACE_EVENT0("sync", "BookmarkModelMerger::BuildRemoteForest");
  534. DCHECK(tracker_for_recording_ignored_updates);
  535. // Filter out invalid remote updates and group the valid ones by the server ID
  536. // of their parent.
  537. GroupedUpdates grouped_updates = GroupValidUpdates(std::move(updates));
  538. DeduplicateValidUpdatesByGUID(&grouped_updates.updates_per_parent_guid);
  539. // Construct one tree per permanent entity.
  540. RemoteForest update_forest;
  541. for (UpdateResponseData& permanent_node_update :
  542. grouped_updates.permanent_node_updates) {
  543. // Make a copy of the string to avoid relying on argument evaluation order.
  544. const std::string server_defined_unique_tag =
  545. permanent_node_update.entity.server_defined_unique_tag;
  546. DCHECK(!server_defined_unique_tag.empty());
  547. update_forest.emplace(
  548. server_defined_unique_tag,
  549. RemoteTreeNode::BuildTree(std::move(permanent_node_update),
  550. kMaxBookmarkTreeDepth,
  551. &grouped_updates.updates_per_parent_guid));
  552. }
  553. // All remaining entries in |updates_per_parent_guid| must be unreachable from
  554. // permanent entities, since otherwise they would have been moved away.
  555. for (const auto& [parent_guid, updates] :
  556. grouped_updates.updates_per_parent_guid) {
  557. for (const UpdateResponseData& update : updates) {
  558. if (update.entity.specifics.has_bookmark()) {
  559. LogProblematicBookmark(RemoteBookmarkUpdateError::kMissingParentEntity);
  560. tracker_for_recording_ignored_updates
  561. ->RecordIgnoredServerUpdateDueToMissingParent(
  562. update.response_version);
  563. }
  564. }
  565. }
  566. return update_forest;
  567. }
  568. // static
  569. int BookmarkModelMerger::CountRemoteTreeNodeDescendantsForUma(
  570. const RemoteTreeNode& node) {
  571. int descendants = 0;
  572. for (const RemoteTreeNode& child : node.children()) {
  573. descendants += 1 + CountRemoteTreeNodeDescendantsForUma(child);
  574. }
  575. return descendants;
  576. }
  577. // static
  578. std::unordered_map<base::GUID, BookmarkModelMerger::GuidMatch, base::GUIDHash>
  579. BookmarkModelMerger::FindGuidMatchesOrReassignLocal(
  580. const RemoteForest& remote_forest,
  581. bookmarks::BookmarkModel* bookmark_model) {
  582. DCHECK(bookmark_model);
  583. TRACE_EVENT0("sync", "BookmarkModelMerger::FindGuidMatchesOrReassignLocal");
  584. // Build a temporary lookup table for remote GUIDs.
  585. std::unordered_map<base::GUID, const RemoteTreeNode*, base::GUIDHash>
  586. guid_to_remote_node_map;
  587. for (const auto& [server_defined_unique_tag, root] : remote_forest) {
  588. root.EmplaceSelfAndDescendantsByGUID(&guid_to_remote_node_map);
  589. }
  590. // Iterate through all local bookmarks to find matches by GUID.
  591. std::unordered_map<base::GUID, BookmarkModelMerger::GuidMatch, base::GUIDHash>
  592. guid_to_match_map;
  593. // Because ReplaceBookmarkNodeGUID() cannot be used while iterating the local
  594. // bookmark model, a temporary list is constructed first to reassign later.
  595. std::vector<const bookmarks::BookmarkNode*> nodes_to_replace_guid;
  596. ui::TreeNodeIterator<const bookmarks::BookmarkNode> iterator(
  597. bookmark_model->root_node());
  598. while (iterator.has_next()) {
  599. const bookmarks::BookmarkNode* const node = iterator.Next();
  600. DCHECK(node->guid().is_valid());
  601. const auto remote_it = guid_to_remote_node_map.find(node->guid());
  602. if (remote_it == guid_to_remote_node_map.end()) {
  603. continue;
  604. }
  605. const RemoteTreeNode* const remote_node = remote_it->second;
  606. const syncer::EntityData& remote_entity = remote_node->entity();
  607. // Permanent nodes don't match by GUID but by |server_defined_unique_tag|.
  608. // As extra precaution, specially with remote GUIDs in mind, let's ignore
  609. // them explicitly here.
  610. DCHECK(remote_entity.server_defined_unique_tag.empty());
  611. if (node->is_permanent_node()) {
  612. continue;
  613. }
  614. if (GetProtoTypeFromBookmarkNode(node) !=
  615. remote_entity.specifics.bookmark().type() ||
  616. (node->is_url() &&
  617. node->url() != remote_entity.specifics.bookmark().url())) {
  618. // If local node and its remote node match are conflicting in node type or
  619. // URL, replace local GUID with a random GUID.
  620. nodes_to_replace_guid.push_back(node);
  621. continue;
  622. }
  623. const bool success =
  624. guid_to_match_map.emplace(node->guid(), GuidMatch{node, remote_node})
  625. .second;
  626. // Insertion must have succeeded unless there were duplicate GUIDs in the
  627. // local BookmarkModel (invariant violation that gets resolved upon
  628. // restart).
  629. DCHECK(success);
  630. }
  631. for (const bookmarks::BookmarkNode* node : nodes_to_replace_guid) {
  632. ReplaceBookmarkNodeGUID(node, base::GUID::GenerateRandomV4(),
  633. bookmark_model);
  634. }
  635. return guid_to_match_map;
  636. }
  637. void BookmarkModelMerger::MergeSubtree(
  638. const bookmarks::BookmarkNode* local_subtree_root,
  639. const RemoteTreeNode& remote_node) {
  640. const EntityData& remote_update_entity = remote_node.entity();
  641. const SyncedBookmarkTrackerEntity* entity = bookmark_tracker_->Add(
  642. local_subtree_root, remote_update_entity.id,
  643. remote_node.response_version(), remote_update_entity.creation_time,
  644. remote_update_entity.specifics);
  645. const bool is_reupload_needed =
  646. !local_subtree_root->is_permanent_node() &&
  647. IsBookmarkEntityReuploadNeeded(remote_update_entity);
  648. if (is_reupload_needed) {
  649. bookmark_tracker_->IncrementSequenceNumber(entity);
  650. }
  651. LogBookmarkReuploadNeeded(is_reupload_needed);
  652. // If there are remote child updates, try to match them.
  653. for (size_t remote_index = 0; remote_index < remote_node.children().size();
  654. ++remote_index) {
  655. // TODO(crbug.com/1050776): change to DCHECK after investigating.
  656. // Here is expected that all nodes to the left of current |remote_index| are
  657. // filled with remote updates. All local nodes which are not merged will be
  658. // added later.
  659. CHECK_LE(remote_index, local_subtree_root->children().size());
  660. const RemoteTreeNode& remote_child =
  661. remote_node.children().at(remote_index);
  662. const bookmarks::BookmarkNode* matching_local_node =
  663. FindMatchingLocalNode(remote_child, local_subtree_root, remote_index);
  664. // If no match found, create a corresponding local node.
  665. if (!matching_local_node) {
  666. ProcessRemoteCreation(remote_child, local_subtree_root, remote_index);
  667. continue;
  668. }
  669. DCHECK(!local_subtree_root->HasAncestor(matching_local_node));
  670. // Move if required, no-op otherwise.
  671. bookmark_model_->Move(matching_local_node, local_subtree_root,
  672. remote_index);
  673. // Since nodes are matching, their subtrees should be merged as well.
  674. matching_local_node = UpdateBookmarkNodeFromSpecificsIncludingGUID(
  675. matching_local_node, remote_child);
  676. MergeSubtree(matching_local_node, remote_child);
  677. }
  678. // At this point all the children of |remote_node| have corresponding local
  679. // nodes under |local_subtree_root| and they are all in the right positions:
  680. // from 0 to remote_node.children().size() - 1.
  681. //
  682. // This means, the children starting from remote_node.children().size() in
  683. // the parent bookmark node are the ones that are not present in the parent
  684. // sync node and not tracked yet. So create all of the remaining local nodes.
  685. DCHECK_LE(remote_node.children().size(),
  686. local_subtree_root->children().size());
  687. for (size_t i = remote_node.children().size();
  688. i < local_subtree_root->children().size(); ++i) {
  689. // If local node has been or will be matched by GUID, skip it.
  690. if (FindMatchingRemoteNodeByGUID(local_subtree_root->children()[i].get())) {
  691. continue;
  692. }
  693. ProcessLocalCreation(local_subtree_root, i);
  694. }
  695. }
  696. const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNode(
  697. const RemoteTreeNode& remote_child,
  698. const bookmarks::BookmarkNode* local_parent,
  699. size_t local_child_start_index) const {
  700. DCHECK(local_parent);
  701. // Try to match child by GUID. If we can't, try to match child by semantics.
  702. const bookmarks::BookmarkNode* matching_local_node_by_guid =
  703. FindMatchingLocalNodeByGUID(remote_child);
  704. if (matching_local_node_by_guid) {
  705. return matching_local_node_by_guid;
  706. }
  707. // All local nodes up to |remote_index-1| have processed already. Look for a
  708. // matching local node starting with the local node at position
  709. // |local_child_start_index|. FindMatchingChildBySemanticsStartingAt()
  710. // returns kInvalidIndex in the case where no semantics match was found or
  711. // the semantics match found is GUID-matchable to a different node.
  712. const size_t local_index = FindMatchingChildBySemanticsStartingAt(
  713. /*remote_node=*/remote_child,
  714. /*local_parent=*/local_parent,
  715. /*starting_child_index=*/local_child_start_index);
  716. if (local_index == kInvalidIndex) {
  717. // If no match found, return.
  718. return nullptr;
  719. }
  720. // The child at |local_index| has matched by semantics, which also means it
  721. // does not match by GUID to any other remote node.
  722. const bookmarks::BookmarkNode* matching_local_node_by_semantics =
  723. local_parent->children()[local_index].get();
  724. DCHECK(!FindMatchingRemoteNodeByGUID(matching_local_node_by_semantics));
  725. return matching_local_node_by_semantics;
  726. }
  727. const bookmarks::BookmarkNode*
  728. BookmarkModelMerger::UpdateBookmarkNodeFromSpecificsIncludingGUID(
  729. const bookmarks::BookmarkNode* local_node,
  730. const RemoteTreeNode& remote_node) {
  731. DCHECK(local_node);
  732. DCHECK(!local_node->is_permanent_node());
  733. // Ensure bookmarks have the same URL, otherwise they would not have been
  734. // matched.
  735. DCHECK(local_node->is_folder() ||
  736. local_node->url() ==
  737. GURL(remote_node.entity().specifics.bookmark().url()));
  738. const EntityData& remote_update_entity = remote_node.entity();
  739. const sync_pb::BookmarkSpecifics& specifics =
  740. remote_update_entity.specifics.bookmark();
  741. // Update the local GUID if necessary for semantic matches (it's obviously not
  742. // needed for GUID-based matches).
  743. const bookmarks::BookmarkNode* possibly_replaced_local_node = local_node;
  744. if (!specifics.guid().empty() &&
  745. specifics.guid() != local_node->guid().AsLowercaseString()) {
  746. // If it's a semantic match, neither of the nodes should be involved in any
  747. // GUID-based match.
  748. DCHECK(!FindMatchingLocalNodeByGUID(remote_node));
  749. DCHECK(!FindMatchingRemoteNodeByGUID(local_node));
  750. possibly_replaced_local_node = ReplaceBookmarkNodeGUID(
  751. local_node, base::GUID::ParseLowercase(specifics.guid()),
  752. bookmark_model_);
  753. // TODO(rushans): remove the code below since DCHECKs above guarantee that
  754. // |guid_to_match_map_| has no such GUID.
  755. //
  756. // Update |guid_to_match_map_| to avoid pointing to a deleted node. This
  757. // should not be required in practice, because the algorithm processes each
  758. // GUID once, but let's update nevertheless to avoid future issues.
  759. const auto it =
  760. guid_to_match_map_.find(possibly_replaced_local_node->guid());
  761. if (it != guid_to_match_map_.end() && it->second.local_node == local_node) {
  762. it->second.local_node = possibly_replaced_local_node;
  763. }
  764. }
  765. // Update all fields, where no-op changes are handled well.
  766. UpdateBookmarkNodeFromSpecifics(specifics, possibly_replaced_local_node,
  767. bookmark_model_, favicon_service_);
  768. return possibly_replaced_local_node;
  769. }
  770. void BookmarkModelMerger::ProcessRemoteCreation(
  771. const RemoteTreeNode& remote_node,
  772. const bookmarks::BookmarkNode* local_parent,
  773. size_t index) {
  774. DCHECK(!FindMatchingLocalNodeByGUID(remote_node));
  775. const EntityData& remote_update_entity = remote_node.entity();
  776. DCHECK(IsValidBookmarkSpecifics(remote_update_entity.specifics.bookmark()));
  777. const sync_pb::EntitySpecifics& specifics = remote_node.entity().specifics;
  778. const bookmarks::BookmarkNode* bookmark_node =
  779. CreateBookmarkNodeFromSpecifics(specifics.bookmark(), local_parent, index,
  780. bookmark_model_, favicon_service_);
  781. DCHECK(bookmark_node);
  782. const SyncedBookmarkTrackerEntity* entity = bookmark_tracker_->Add(
  783. bookmark_node, remote_update_entity.id, remote_node.response_version(),
  784. remote_update_entity.creation_time, specifics);
  785. const bool is_reupload_needed =
  786. IsBookmarkEntityReuploadNeeded(remote_node.entity());
  787. if (is_reupload_needed) {
  788. bookmark_tracker_->IncrementSequenceNumber(entity);
  789. }
  790. LogBookmarkReuploadNeeded(is_reupload_needed);
  791. // Recursively, match by GUID or, if not possible, create local node for all
  792. // child remote nodes.
  793. size_t i = 0;
  794. for (const RemoteTreeNode& remote_child : remote_node.children()) {
  795. // TODO(crbug.com/1050776): change to DCHECK after investigating of some
  796. // crashes.
  797. CHECK_LE(i, bookmark_node->children().size());
  798. const bookmarks::BookmarkNode* local_child =
  799. FindMatchingLocalNodeByGUID(remote_child);
  800. if (!local_child) {
  801. ProcessRemoteCreation(remote_child, bookmark_node, i++);
  802. continue;
  803. }
  804. bookmark_model_->Move(local_child, bookmark_node, i++);
  805. local_child =
  806. UpdateBookmarkNodeFromSpecificsIncludingGUID(local_child, remote_child);
  807. MergeSubtree(local_child, remote_child);
  808. }
  809. }
  810. void BookmarkModelMerger::ProcessLocalCreation(
  811. const bookmarks::BookmarkNode* parent,
  812. size_t index) {
  813. DCHECK_LE(index, parent->children().size());
  814. const SyncedBookmarkTrackerEntity* parent_entity =
  815. bookmark_tracker_->GetEntityForBookmarkNode(parent);
  816. // Since we are merging top down, parent entity must be tracked.
  817. DCHECK(parent_entity);
  818. // Assign a temp server id for the entity. Will be overridden by the actual
  819. // server id upon receiving commit response.
  820. const bookmarks::BookmarkNode* node = parent->children()[index].get();
  821. DCHECK(!FindMatchingRemoteNodeByGUID(node));
  822. // The node's GUID cannot run into collisions because
  823. // FindGuidMatchesOrReassignLocal() takes care of reassigning local GUIDs if
  824. // they won't actually be merged with the remote bookmark with the same GUID
  825. // (e.g. incompatible types).
  826. const std::string sync_id = node->guid().AsLowercaseString();
  827. const int64_t server_version = syncer::kUncommittedVersion;
  828. const base::Time creation_time = base::Time::Now();
  829. const std::string& suffix = syncer::GenerateSyncableBookmarkHash(
  830. bookmark_tracker_->model_type_state().cache_guid(), sync_id);
  831. // Locally created nodes aren't tracked and hence don't have a unique position
  832. // yet so we need to produce new ones.
  833. const syncer::UniquePosition pos =
  834. GenerateUniquePositionForLocalCreation(parent, index, suffix);
  835. const sync_pb::EntitySpecifics specifics = CreateSpecificsFromBookmarkNode(
  836. node, bookmark_model_, pos.ToProto(), /*force_favicon_load=*/true);
  837. const SyncedBookmarkTrackerEntity* entity = bookmark_tracker_->Add(
  838. node, sync_id, server_version, creation_time, specifics);
  839. // Mark the entity that it needs to be committed.
  840. bookmark_tracker_->IncrementSequenceNumber(entity);
  841. for (size_t i = 0; i < node->children().size(); ++i) {
  842. // If a local node hasn't matched with any remote entity, its descendants
  843. // will neither, unless they have been or will be matched by GUID, in which
  844. // case we skip them for now.
  845. if (FindMatchingRemoteNodeByGUID(node->children()[i].get())) {
  846. continue;
  847. }
  848. ProcessLocalCreation(/*parent=*/node, i);
  849. }
  850. }
  851. size_t BookmarkModelMerger::FindMatchingChildBySemanticsStartingAt(
  852. const RemoteTreeNode& remote_node,
  853. const bookmarks::BookmarkNode* local_parent,
  854. size_t starting_child_index) const {
  855. DCHECK(local_parent);
  856. const auto& children = local_parent->children();
  857. DCHECK_LE(starting_child_index, children.size());
  858. const EntityData& remote_entity = remote_node.entity();
  859. // Precompute the remote title and URL before searching for a matching local
  860. // node.
  861. const std::string remote_canonicalized_title =
  862. LegacyCanonicalizedTitleFromSpecifics(remote_entity.specifics.bookmark());
  863. const sync_pb::BookmarkSpecifics::Type remote_type =
  864. remote_entity.specifics.bookmark().type();
  865. GURL remote_url;
  866. if (remote_type == sync_pb::BookmarkSpecifics::URL) {
  867. remote_url = GURL(remote_entity.specifics.bookmark().url());
  868. }
  869. const auto it = std::find_if(
  870. children.cbegin() + starting_child_index, children.cend(),
  871. [this, &remote_canonicalized_title, &remote_url,
  872. remote_type](const auto& child) {
  873. return !FindMatchingRemoteNodeByGUID(child.get()) &&
  874. NodeSemanticsMatch(child.get(), remote_canonicalized_title,
  875. remote_url, remote_type);
  876. });
  877. return (it == children.cend()) ? kInvalidIndex : (it - children.cbegin());
  878. }
  879. const BookmarkModelMerger::RemoteTreeNode*
  880. BookmarkModelMerger::FindMatchingRemoteNodeByGUID(
  881. const bookmarks::BookmarkNode* local_node) const {
  882. DCHECK(local_node);
  883. const auto it = guid_to_match_map_.find(local_node->guid());
  884. if (it == guid_to_match_map_.end()) {
  885. return nullptr;
  886. }
  887. DCHECK_EQ(it->second.local_node, local_node);
  888. return it->second.remote_node;
  889. }
  890. const bookmarks::BookmarkNode* BookmarkModelMerger::FindMatchingLocalNodeByGUID(
  891. const RemoteTreeNode& remote_node) const {
  892. const syncer::EntityData& remote_entity = remote_node.entity();
  893. const auto it = guid_to_match_map_.find(
  894. base::GUID::ParseLowercase(remote_entity.specifics.bookmark().guid()));
  895. if (it == guid_to_match_map_.end()) {
  896. return nullptr;
  897. }
  898. DCHECK_EQ(it->second.remote_node, &remote_node);
  899. return it->second.local_node;
  900. }
  901. syncer::UniquePosition
  902. BookmarkModelMerger::GenerateUniquePositionForLocalCreation(
  903. const bookmarks::BookmarkNode* parent,
  904. size_t index,
  905. const std::string& suffix) const {
  906. // Try to find last tracked preceding entity. It is not always the previous
  907. // one as it might be skipped if it has unprocessed remote matching by GUID
  908. // update.
  909. for (size_t i = index; i > 0; --i) {
  910. const SyncedBookmarkTrackerEntity* predecessor_entity =
  911. bookmark_tracker_->GetEntityForBookmarkNode(
  912. parent->children()[i - 1].get());
  913. if (predecessor_entity != nullptr) {
  914. return syncer::UniquePosition::After(
  915. syncer::UniquePosition::FromProto(
  916. predecessor_entity->metadata().unique_position()),
  917. suffix);
  918. }
  919. DCHECK(FindMatchingRemoteNodeByGUID(parent->children()[i - 1].get()));
  920. }
  921. return syncer::UniquePosition::InitialPosition(suffix);
  922. }
  923. } // namespace sync_bookmarks