BASELINE: Update Chromium to 68.0.3440.125

Change-Id: I23f19369e01f688e496f5bf179abb521ad73874f
Reviewed-by: Allan Sandfeld Jensen <allan.jensen@qt.io>

9 files changed, 906 insertions, 10 deletions

diff --git a/chromium/components/sync_bookmarks/BUILD.gn b/chromium/components/sync_bookmarks/BUILD.gn
index 09110f92ce3..eecc87f7ce1 100644
--- a/chromium/components/sync_bookmarks/BUILD.gn
+++ b/chromium/components/sync_bookmarks/BUILD.gn
@@ -16,6 +16,8 @@ static_library("sync_bookmarks") {
     "bookmark_model_type_controller.h",
     "bookmark_model_type_processor.cc",
     "bookmark_model_type_processor.h",
+    "synced_bookmark_tracker.cc",
+    "synced_bookmark_tracker.h",
   ]
 
   deps = [
@@ -36,6 +38,7 @@ source_set("unit_tests") {
     "bookmark_data_type_controller_unittest.cc",
     "bookmark_model_type_controller_unittest.cc",
     "bookmark_model_type_processor_unittest.cc",
+    "synced_bookmark_tracker_unittest.cc",
   ]
 
   deps = [
diff --git a/chromium/components/sync_bookmarks/bookmark_model_type_controller.cc b/chromium/components/sync_bookmarks/bookmark_model_type_controller.cc
index ccc49f88cf2..678334e0eb3 100644
--- a/chromium/components/sync_bookmarks/bookmark_model_type_controller.cc
+++ b/chromium/components/sync_bookmarks/bookmark_model_type_controller.cc
@@ -68,12 +68,15 @@ void BookmarkModelTypeController::RegisterWithBackend(
     base::Callback<void(bool)> set_downloaded,
     syncer::ModelTypeConfigurer* configurer) {
   DCHECK(CalledOnValidThread());
+  if (activated_)
+    return;
   DCHECK(configurer);
   std::unique_ptr<syncer::ActivationContext> activation_context =
       PrepareActivationContext();
   set_downloaded.Run(activation_context->model_type_state.initial_sync_done());
   configurer->ActivateNonBlockingDataType(type(),
                                           std::move(activation_context));
+  activated_ = true;
 }
 
 void BookmarkModelTypeController::StartAssociating(
@@ -92,13 +95,17 @@ void BookmarkModelTypeController::StartAssociating(
 void BookmarkModelTypeController::ActivateDataType(
     syncer::ModelTypeConfigurer* configurer) {
   DCHECK(CalledOnValidThread());
-  NOTIMPLEMENTED();
+  DCHECK(configurer);
+  DCHECK_EQ(RUNNING, state_);
 }
 
 void BookmarkModelTypeController::DeactivateDataType(
     syncer::ModelTypeConfigurer* configurer) {
   DCHECK(CalledOnValidThread());
-  NOTIMPLEMENTED();
+  if (activated_) {
+    configurer->DeactivateNonBlockingDataType(type());
+    activated_ = false;
+  }
 }
 
 void BookmarkModelTypeController::Stop() {
@@ -158,7 +165,8 @@ BookmarkModelTypeController::PrepareActivationContext() {
       directory->InitialSyncEndedForType(type()));
   // TODO(pavely): Populate model_type_state.type_context.
 
-  model_type_processor_ = std::make_unique<BookmarkModelTypeProcessor>();
+  model_type_processor_ =
+      std::make_unique<BookmarkModelTypeProcessor>(sync_client_);
   activation_context->type_processor =
       std::make_unique<syncer::ModelTypeProcessorProxy>(
           model_type_processor_->GetWeakPtr(),
diff --git a/chromium/components/sync_bookmarks/bookmark_model_type_controller.h b/chromium/components/sync_bookmarks/bookmark_model_type_controller.h
index daf3b1a130c..42451be5466 100644
--- a/chromium/components/sync_bookmarks/bookmark_model_type_controller.h
+++ b/chromium/components/sync_bookmarks/bookmark_model_type_controller.h
@@ -61,6 +61,12 @@ class BookmarkModelTypeController : public syncer::DataTypeController {
   // BookmarkModel/HistoryService.
   std::unique_ptr<BookmarkModelTypeProcessor> model_type_processor_;
 
+  // This is a hack to prevent reconfigurations from crashing, because USS
+  // activation is not idempotent. RegisterWithBackend only needs to actually do
+  // something the first time after the type is enabled.
+  // TODO(crbug.com/647505): Remove this once the DTM handles things better.
+  bool activated_ = false;
+
   DISALLOW_COPY_AND_ASSIGN(BookmarkModelTypeController);
 };
 
diff --git a/chromium/components/sync_bookmarks/bookmark_model_type_processor.cc b/chromium/components/sync_bookmarks/bookmark_model_type_processor.cc
index ccac311794b..d65bec249b0 100644
--- a/chromium/components/sync_bookmarks/bookmark_model_type_processor.cc
+++ b/chromium/components/sync_bookmarks/bookmark_model_type_processor.cc
@@ -7,13 +7,128 @@
 #include <utility>
 
 #include "base/callback.h"
+#include "base/strings/utf_string_conversions.h"
+#include "components/bookmarks/browser/bookmark_model.h"
 #include "components/sync/base/model_type.h"
+#include "components/sync/driver/sync_client.h"
 #include "components/sync/engine/commit_queue.h"
+#include "components/undo/bookmark_undo_utils.h"
 
 namespace sync_bookmarks {
 
-BookmarkModelTypeProcessor::BookmarkModelTypeProcessor()
-    : weak_ptr_factory_(this) {}
+namespace {
+
+// 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
+// ProfileSyncService can rely on the presence of tagged nodes.
+const char kBookmarkBarTag[] = "bookmark_bar";
+const char kMobileBookmarksTag[] = "synced_bookmarks";
+const char kOtherBookmarksTag[] = "other_bookmarks";
+
+// Id is created by concatenating the specifics field number and the server tag
+// similar to LookbackServerEntity::CreateId() that uses
+// GetSpecificsFieldNumberFromModelType() to compute the field number.
+static const char kBookmarksRootId[] = "32904_google_chrome_bookmarks";
+
+// |sync_entity| must contain a bookmark specifics.
+// Metainfo entries must have unique keys.
+bookmarks::BookmarkNode::MetaInfoMap GetBookmarkMetaInfo(
+    const syncer::EntityData& sync_entity) {
+  const sync_pb::BookmarkSpecifics& specifics =
+      sync_entity.specifics.bookmark();
+  bookmarks::BookmarkNode::MetaInfoMap meta_info_map;
+  for (const sync_pb::MetaInfo& meta_info : specifics.meta_info()) {
+    meta_info_map[meta_info.key()] = meta_info.value();
+  }
+  DCHECK_EQ(static_cast<size_t>(specifics.meta_info_size()),
+            meta_info_map.size());
+  return meta_info_map;
+}
+
+// Creates a bookmark node under the given parent node from the given sync node.
+// Returns the newly created node. |sync_entity| must contain a bookmark
+// specifics with Metainfo entries having unique keys.
+const bookmarks::BookmarkNode* CreateBookmarkNode(
+    const syncer::EntityData& sync_entity,
+    const bookmarks::BookmarkNode* parent,
+    bookmarks::BookmarkModel* model,
+    syncer::SyncClient* sync_client,
+    int index) {
+  DCHECK(parent);
+  DCHECK(model);
+  DCHECK(sync_client);
+
+  const sync_pb::BookmarkSpecifics& specifics =
+      sync_entity.specifics.bookmark();
+  bookmarks::BookmarkNode::MetaInfoMap metainfo =
+      GetBookmarkMetaInfo(sync_entity);
+  if (sync_entity.is_folder) {
+    return model->AddFolderWithMetaInfo(
+        parent, index, base::UTF8ToUTF16(specifics.title()), &metainfo);
+  }
+  // 'creation_time_us' was added in M24. Assume a time of 0 means now.
+  const int64_t create_time_us = specifics.creation_time_us();
+  base::Time create_time =
+      (create_time_us == 0)
+          ? base::Time::Now()
+          : base::Time::FromDeltaSinceWindowsEpoch(
+                // Use FromDeltaSinceWindowsEpoch because create_time_us has
+                // always used the Windows epoch.
+                base::TimeDelta::FromMicroseconds(create_time_us));
+  return model->AddURLWithCreationTimeAndMetaInfo(
+      parent, index, base::UTF8ToUTF16(specifics.title()),
+      GURL(specifics.url()), create_time, &metainfo);
+  // TODO(crbug.com/516866): Add the favicon related code.
+}
+
+class ScopedRemoteUpdateBookmarks {
+ public:
+  // |bookmark_model| must not be null and must outlive this object.
+  explicit ScopedRemoteUpdateBookmarks(syncer::SyncClient* const sync_client)
+      : sync_client_(sync_client),
+        suspend_undo_(sync_client->GetBookmarkUndoServiceIfExists()) {
+    // Notify UI intensive observers of BookmarkModel that we are about to make
+    // potentially significant changes to it, so the updates may be batched. For
+    // example, on Mac, the bookmarks bar displays animations when bookmark
+    // items are added or deleted.
+    sync_client_->GetBookmarkModel()->BeginExtensiveChanges();
+  }
+
+  ~ScopedRemoteUpdateBookmarks() {
+    // Notify UI intensive observers of BookmarkModel that all updates have been
+    // applied, and that they may now be consumed. This prevents issues like the
+    // one described in https://crbug.com/281562, where old and new items on the
+    // bookmarks bar would overlap.
+    sync_client_->GetBookmarkModel()->EndExtensiveChanges();
+  }
+
+ private:
+  syncer::SyncClient* const sync_client_;
+
+  // Changes made to the bookmark model due to sync should not be undoable.
+  ScopedSuspendBookmarkUndo suspend_undo_;
+
+  DISALLOW_COPY_AND_ASSIGN(ScopedRemoteUpdateBookmarks);
+};
+}  // namespace
+
+BookmarkModelTypeProcessor::BookmarkModelTypeProcessor(
+    syncer::SyncClient* sync_client)
+    : sync_client_(sync_client),
+      bookmark_model_(sync_client->GetBookmarkModel()),
+      weak_ptr_factory_(this) {}
 
 BookmarkModelTypeProcessor::~BookmarkModelTypeProcessor() = default;
 
@@ -49,7 +164,228 @@ void BookmarkModelTypeProcessor::OnUpdateReceived(
     const sync_pb::ModelTypeState& model_type_state,
     const syncer::UpdateResponseDataList& updates) {
   DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
-  NOTIMPLEMENTED();
+
+  ScopedRemoteUpdateBookmarks update_bookmarks(sync_client_);
+
+  for (const syncer::UpdateResponseData* update : ReorderUpdates(updates)) {
+    const syncer::EntityData& update_data = update->entity.value();
+    // TODO(crbug.com/516866): Check |update_data| for sanity.
+    // 1. Has bookmark specifics or no specifics in case of delete.
+    // 2. All meta info entries in the specifics have unique keys.
+    const SyncedBookmarkTracker::Entity* tracked_entity =
+        bookmark_tracker_.GetEntityForSyncId(update_data.id);
+    if (update_data.is_deleted()) {
+      ProcessRemoteDelete(update_data, tracked_entity);
+      continue;
+    }
+    if (!tracked_entity) {
+      ProcessRemoteCreate(update_data);
+      continue;
+    }
+    // Ignore changes to the permanent nodes (e.g. bookmarks bar). We only care
+    // about their children.
+    if (bookmark_model_->is_permanent_node(tracked_entity->bookmark_node())) {
+      continue;
+    }
+    ProcessRemoteUpdate(update_data, tracked_entity);
+  }
+}
+
+// static
+std::vector<const syncer::UpdateResponseData*>
+BookmarkModelTypeProcessor::ReorderUpdatesForTest(
+    const syncer::UpdateResponseDataList& updates) {
+  return ReorderUpdates(updates);
+}
+
+const SyncedBookmarkTracker* BookmarkModelTypeProcessor::GetTrackerForTest()
+    const {
+  return &bookmark_tracker_;
+}
+
+// static
+std::vector<const syncer::UpdateResponseData*>
+BookmarkModelTypeProcessor::ReorderUpdates(
+    const syncer::UpdateResponseDataList& updates) {
+  // TODO(crbug.com/516866): This is a very simple (hacky) reordering algorithm
+  // that assumes no folders exist except the top level permanent ones. This
+  // should be fixed before enabling USS for bookmarks.
+  std::vector<const syncer::UpdateResponseData*> ordered_updates;
+  for (const syncer::UpdateResponseData& update : updates) {
+    const syncer::EntityData& update_data = update.entity.value();
+    if (update_data.parent_id == "0") {
+      continue;
+    }
+    if (update_data.parent_id == kBookmarksRootId) {
+      ordered_updates.push_back(&update);
+    }
+  }
+  for (const syncer::UpdateResponseData& update : updates) {
+    const syncer::EntityData& update_data = update.entity.value();
+    // Deletions should come last.
+    if (update_data.is_deleted()) {
+      continue;
+    }
+    if (update_data.parent_id != "0" &&
+        update_data.parent_id != kBookmarksRootId) {
+      ordered_updates.push_back(&update);
+    }
+  }
+  // Now add deletions.
+  for (const syncer::UpdateResponseData& update : updates) {
+    const syncer::EntityData& update_data = update.entity.value();
+    if (!update_data.is_deleted()) {
+      continue;
+    }
+    if (update_data.parent_id != "0" &&
+        update_data.parent_id != kBookmarksRootId) {
+      ordered_updates.push_back(&update);
+    }
+  }
+  return ordered_updates;
+}
+
+void BookmarkModelTypeProcessor::ProcessRemoteCreate(
+    const syncer::EntityData& update_data) {
+  // Because the Synced Bookmarks node can be created server side, it's possible
+  // it'll arrive at the client as an update. In that case it won't have been
+  // associated at startup, the GetChromeNodeFromSyncId call above will return
+  // null, and we won't detect it as a permanent node, resulting in us trying to
+  // create it here (which will fail). Therefore, we add special logic here just
+  // to detect the Synced Bookmarks folder.
+  if (update_data.parent_id == kBookmarksRootId) {
+    // Associate permanent folders.
+    AssociatePermanentFolder(update_data);
+    return;
+  }
+
+  const bookmarks::BookmarkNode* parent_node = GetParentNode(update_data);
+  if (!parent_node) {
+    // If we cannot find the parent, we can do nothing.
+    DLOG(ERROR) << "Could not find parent of node being added."
+                << " Node title: " << update_data.specifics.bookmark().title()
+                << ", parent id = " << update_data.parent_id;
+    return;
+  }
+  // TODO(crbug.com/516866): This code appends the code to the very end of the
+  // list of the children by assigning the index to the
+  // parent_node->child_count(). It should instead compute the exact using the
+  // unique position information of the new node as well as the siblings.
+  const bookmarks::BookmarkNode* bookmark_node =
+      CreateBookmarkNode(update_data, parent_node, bookmark_model_,
+                         sync_client_, parent_node->child_count());
+  if (!bookmark_node) {
+    // We ignore bookmarks we can't add.
+    DLOG(ERROR) << "Failed to create bookmark node with title "
+                << update_data.specifics.bookmark().title() << " and url "
+                << update_data.specifics.bookmark().url();
+    return;
+  }
+  bookmark_tracker_.Associate(update_data.id, bookmark_node);
+  // TODO(crbug.com/516866): Update metadata (e.g. server version,
+  // specifics_hash).
+}
+
+void BookmarkModelTypeProcessor::ProcessRemoteUpdate(
+    const syncer::EntityData& update_data,
+    const SyncedBookmarkTracker::Entity* tracked_entity) {
+  // Can only update existing nodes.
+  DCHECK(tracked_entity);
+  DCHECK_EQ(tracked_entity,
+            bookmark_tracker_.GetEntityForSyncId(update_data.id));
+  // Must no be a deletion
+  DCHECK(!update_data.is_deleted());
+  if (tracked_entity->IsUnsynced()) {
+    // TODO(crbug.com/516866): Handle conflict resolution.
+    return;
+  }
+  if (tracked_entity->MatchesData(update_data)) {
+    // TODO(crbug.com/516866): Update metadata (e.g. server version,
+    // specifics_hash).
+    return;
+  }
+  const bookmarks::BookmarkNode* node = tracked_entity->bookmark_node();
+  if (update_data.is_folder != node->is_folder()) {
+    DLOG(ERROR) << "Could not update node. Remote node is a "
+                << (update_data.is_folder ? "folder" : "bookmark")
+                << " while local node is a "
+                << (node->is_folder() ? "folder" : "bookmark");
+    return;
+  }
+  const sync_pb::BookmarkSpecifics& specifics =
+      update_data.specifics.bookmark();
+  if (!update_data.is_folder) {
+    bookmark_model_->SetURL(node, GURL(specifics.url()));
+  }
+
+  bookmark_model_->SetTitle(node, base::UTF8ToUTF16(specifics.title()));
+  // TODO(crbug.com/516866): Add the favicon related code.
+  bookmark_model_->SetNodeMetaInfoMap(node, GetBookmarkMetaInfo(update_data));
+  // TODO(crbug.com/516866): Update metadata (e.g. server version,
+  // specifics_hash).
+  // TODO(crbug.com/516866): Handle reparenting.
+  // TODO(crbug.com/516866): Handle the case of moving the bookmark to a new
+  // position under the same parent (i.e. change in the unique position)
+}
+
+void BookmarkModelTypeProcessor::ProcessRemoteDelete(
+    const syncer::EntityData& update_data,
+    const SyncedBookmarkTracker::Entity* tracked_entity) {
+  DCHECK(update_data.is_deleted());
+
+  DCHECK_EQ(tracked_entity,
+            bookmark_tracker_.GetEntityForSyncId(update_data.id));
+
+  // Handle corner cases first.
+  if (tracked_entity == nullptr) {
+    // Local entity doesn't exist and update is tombstone.
+    DLOG(WARNING) << "Received remote delete for a non-existing item.";
+    return;
+  }
+
+  const bookmarks::BookmarkNode* node = tracked_entity->bookmark_node();
+  // Ignore changes to the permanent top-level nodes.  We only care about
+  // their children.
+  if (bookmark_model_->is_permanent_node(node)) {
+    return;
+  }
+  // TODO(crbug.com/516866): Allow deletions of non-empty direcoties if makes
+  // sense, and recursively delete children.
+  if (node->child_count() > 0) {
+    DLOG(WARNING) << "Trying to delete a non-empty folder.";
+    return;
+  }
+
+  bookmark_model_->Remove(node);
+  bookmark_tracker_.Disassociate(update_data.id);
+}
+
+const bookmarks::BookmarkNode* BookmarkModelTypeProcessor::GetParentNode(
+    const syncer::EntityData& update_data) const {
+  const SyncedBookmarkTracker::Entity* parent_entity =
+      bookmark_tracker_.GetEntityForSyncId(update_data.parent_id);
+  if (!parent_entity) {
+    return nullptr;
+  }
+  return parent_entity->bookmark_node();
+}
+
+void BookmarkModelTypeProcessor::AssociatePermanentFolder(
+    const syncer::EntityData& update_data) {
+  DCHECK_EQ(update_data.parent_id, kBookmarksRootId);
+
+  const bookmarks::BookmarkNode* permanent_node = nullptr;
+  if (update_data.server_defined_unique_tag == kBookmarkBarTag) {
+    permanent_node = bookmark_model_->bookmark_bar_node();
+  } else if (update_data.server_defined_unique_tag == kOtherBookmarksTag) {
+    permanent_node = bookmark_model_->other_node();
+  } else if (update_data.server_defined_unique_tag == kMobileBookmarksTag) {
+    permanent_node = bookmark_model_->mobile_node();
+  }
+
+  if (permanent_node != nullptr) {
+    bookmark_tracker_.Associate(update_data.id, permanent_node);
+  }
 }
 
 base::WeakPtr<syncer::ModelTypeProcessor>
diff --git a/chromium/components/sync_bookmarks/bookmark_model_type_processor.h b/chromium/components/sync_bookmarks/bookmark_model_type_processor.h
index 3a32a958a29..892c64ef9da 100644
--- a/chromium/components/sync_bookmarks/bookmark_model_type_processor.h
+++ b/chromium/components/sync_bookmarks/bookmark_model_type_processor.h
@@ -6,17 +6,28 @@
 #define COMPONENTS_SYNC_BOOKMARKS_BOOKMARK_MODEL_TYPE_PROCESSOR_H_
 
 #include <memory>
+#include <vector>
 
 #include "base/macros.h"
 #include "base/memory/weak_ptr.h"
 #include "base/sequence_checker.h"
 #include "components/sync/engine/model_type_processor.h"
+#include "components/sync_bookmarks/synced_bookmark_tracker.h"
+
+namespace syncer {
+class SyncClient;
+}
+
+namespace bookmarks {
+class BookmarkModel;
+}
 
 namespace sync_bookmarks {
 
 class BookmarkModelTypeProcessor : public syncer::ModelTypeProcessor {
  public:
-  BookmarkModelTypeProcessor();
+  // |sync_client| must not be nullptr and must outlive this object.
+  explicit BookmarkModelTypeProcessor(syncer::SyncClient* sync_client);
   ~BookmarkModelTypeProcessor() override;
 
   // ModelTypeProcessor implementation.
@@ -30,13 +41,74 @@ class BookmarkModelTypeProcessor : public syncer::ModelTypeProcessor {
   void OnUpdateReceived(const sync_pb::ModelTypeState& type_state,
                         const syncer::UpdateResponseDataList& updates) override;
 
+  // Public for testing.
+  static std::vector<const syncer::UpdateResponseData*> ReorderUpdatesForTest(
+      const syncer::UpdateResponseDataList& updates);
+
+  const SyncedBookmarkTracker* GetTrackerForTest() const;
+
   base::WeakPtr<syncer::ModelTypeProcessor> GetWeakPtr();
 
  private:
   SEQUENCE_CHECKER(sequence_checker_);
 
+  // Reorders incoming updates such that parent creation is before child
+  // creation and child deletion is before parent deletion, and deletions should
+  // come last. The returned pointers point to the elements in the original
+  // |updates|.
+  static std::vector<const syncer::UpdateResponseData*> ReorderUpdates(
+      const syncer::UpdateResponseDataList& updates);
+
+  // Given a remote update entity, it returns the parent bookmark node of the
+  // corresponding node. It returns null if the parent node cannot be found.
+  const bookmarks::BookmarkNode* GetParentNode(
+      const syncer::EntityData& update_data) const;
+
+  // Processes a remote creation of a bookmark node.
+  // 1. For permanent folders, they are only registered in |bookmark_tracker_|.
+  // 2. If the nodes parent cannot be found, the remote creation update is
+  //    ignored.
+  // 3. Otherwise, a new node is created in the local bookmark model and
+  //    registered in |bookmark_tracker_|.
+  void ProcessRemoteCreate(const syncer::EntityData& update_data);
+
+  // Processes a remote update of a bookmark node. |update_data| must not be a
+  // deletion, and the server_id must be already tracked, otherwise, it is a
+  // creation that gets handeled in ProcessRemoteCreate(). |tracked_entity| is
+  // the tracked entity for that server_id. It is passed as a dependency instead
+  // of performing a lookup inside ProcessRemoteUpdate() to avoid wasting CPU
+  // cycles for doing another lookup (this code runs on the UI thread).
+  void ProcessRemoteUpdate(const syncer::EntityData& update_data,
+                           const SyncedBookmarkTracker::Entity* tracked_entity);
+
+  // Process a remote delete of a bookmark node. |update_data| must not be a
+  // deletion. |tracked_entity| is the tracked entity for that server_id. It is
+  // passed as a dependency instead of performing a lookup inside
+  // ProcessRemoteDelete() to avoid wasting CPU cycles for doing another lookup
+  // (this code runs on the UI thread).
+  void ProcessRemoteDelete(const syncer::EntityData& update_data,
+                           const SyncedBookmarkTracker::Entity* tracked_entity);
+
+  // Associates the permanent bookmark folders with the corresponding server
+  // side ids and registers the association in |bookmark_tracker_|.
+  // |update_data| must contain server_defined_unique_tag that is used to
+  // determine the corresponding permanent node. All permanent nodes are assumed
+  // to be directly children nodes of |kBookmarksRootId|. This method is used in
+  // the initial sync cycle only.
+  void AssociatePermanentFolder(const syncer::EntityData& update_data);
+
+  syncer::SyncClient* const sync_client_;
+
+  // The bookmark model we are processing local changes from and forwarding
+  // remote changes to.
+  bookmarks::BookmarkModel* const bookmark_model_;
+
   std::unique_ptr<syncer::CommitQueue> worker_;
 
+  // Keeps the mapping between server ids and bookmarks nodes. It also caches
+  // the metadata upon a local change until the commit configration is received.
+  SyncedBookmarkTracker bookmark_tracker_;
+
   base::WeakPtrFactory<BookmarkModelTypeProcessor> weak_ptr_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(BookmarkModelTypeProcessor);
diff --git a/chromium/components/sync_bookmarks/bookmark_model_type_processor_unittest.cc b/chromium/components/sync_bookmarks/bookmark_model_type_processor_unittest.cc
index b3d40e3581d..ff2d3b32715 100644
--- a/chromium/components/sync_bookmarks/bookmark_model_type_processor_unittest.cc
+++ b/chromium/components/sync_bookmarks/bookmark_model_type_processor_unittest.cc
@@ -4,16 +4,302 @@
 
 #include "components/sync_bookmarks/bookmark_model_type_processor.h"
 
+#include <string>
+
+#include "base/strings/utf_string_conversions.h"
+#include "components/bookmarks/browser/bookmark_model.h"
+#include "components/bookmarks/test/test_bookmark_client.h"
+#include "components/sync/driver/fake_sync_client.h"
+#include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
+using base::ASCIIToUTF16;
+using testing::Eq;
+using testing::NotNull;
+
 namespace sync_bookmarks {
 
 namespace {
 
-class BookmarkModelTypeProcessorTest : public testing::Test {};
+// The parent tag for children of the root entity. Entities with this parent are
+// referred to as top level enities.
+const char kRootParentTag[] = "0";
+const char kBookmarkBarTag[] = "bookmark_bar";
+const char kBookmarksRootId[] = "32904_google_chrome_bookmarks";
+
+struct BookmarkInfo {
+  std::string server_id;
+  std::string title;
+  std::string url;  // empty for folders.
+  std::string parent_id;
+  std::string server_tag;
+};
+
+syncer::UpdateResponseData CreateUpdateData(const BookmarkInfo& bookmark_info) {
+  syncer::EntityData data;
+  data.id = bookmark_info.server_id;
+  data.parent_id = bookmark_info.parent_id;
+  data.server_defined_unique_tag = bookmark_info.server_tag;
+
+  sync_pb::BookmarkSpecifics* bookmark_specifics =
+      data.specifics.mutable_bookmark();
+  bookmark_specifics->set_title(bookmark_info.title);
+  if (bookmark_info.url.empty()) {
+    data.is_folder = true;
+  } else {
+    bookmark_specifics->set_url(bookmark_info.url);
+  }
+
+  syncer::UpdateResponseData response_data;
+  response_data.entity = data.PassToPtr();
+  // Similar to what's done in the loopback_server.
+  response_data.response_version = 0;
+  return response_data;
+}
+
+void AssertState(const BookmarkModelTypeProcessor* processor,
+                 const std::vector<BookmarkInfo>& bookmarks) {
+  const SyncedBookmarkTracker* tracker = processor->GetTrackerForTest();
+
+  // Make sure the tracker contains all bookmarks in |bookmarks| + the
+  // bookmark bar node.
+  ASSERT_THAT(tracker->TrackedEntitiesCountForTest(), Eq(bookmarks.size() + 1));
+
+  for (BookmarkInfo bookmark : bookmarks) {
+    const SyncedBookmarkTracker::Entity* entity =
+        tracker->GetEntityForSyncId(bookmark.server_id);
+    ASSERT_THAT(entity, NotNull());
+    const bookmarks::BookmarkNode* node = entity->bookmark_node();
+    ASSERT_THAT(node->GetTitle(), Eq(ASCIIToUTF16(bookmark.title)));
+    ASSERT_THAT(node->url(), Eq(GURL(bookmark.url)));
+    const SyncedBookmarkTracker::Entity* parent_entity =
+        tracker->GetEntityForSyncId(bookmark.parent_id);
+    ASSERT_THAT(node->parent(), parent_entity->bookmark_node());
+  }
+}
+
+// TODO(crbug.com/516866): Replace with a simpler implementation (e.g. by
+// simulating loading from metadata) instead of receiving remote updates.
+// Inititalizes the processor with the bookmarks in |bookmarks|.
+void InitWithSyncedBookmarks(const std::vector<BookmarkInfo>& bookmarks,
+                             BookmarkModelTypeProcessor* processor) {
+  syncer::UpdateResponseDataList updates;
+  // Add update for the permanent folder "Bookmarks bar".
+  updates.push_back(
+      CreateUpdateData({"bookmark_bar", std::string(), std::string(),
+                        kBookmarksRootId, kBookmarkBarTag}));
+  for (BookmarkInfo bookmark : bookmarks) {
+    updates.push_back(CreateUpdateData(bookmark));
+  }
+  processor->OnUpdateReceived(sync_pb::ModelTypeState(), updates);
+  AssertState(processor, bookmarks);
+}
+
+syncer::UpdateResponseData CreateTombstone(const std::string& server_id) {
+  // EntityData is considered to represent a deletion if its
+  // specifics hasn't been set.
+  syncer::EntityData data;
+  data.id = server_id;
+
+  syncer::UpdateResponseData response_data;
+  response_data.entity = data.PassToPtr();
+  return response_data;
+}
+
+syncer::UpdateResponseData CreateBookmarkRootUpdateData() {
+  return CreateUpdateData({syncer::ModelTypeToRootTag(syncer::BOOKMARKS),
+                           std::string(), std::string(), kRootParentTag,
+                           syncer::ModelTypeToRootTag(syncer::BOOKMARKS)});
+}
+
+class TestSyncClient : public syncer::FakeSyncClient {
+ public:
+  explicit TestSyncClient(bookmarks::BookmarkModel* bookmark_model)
+      : bookmark_model_(bookmark_model) {}
+
+  bookmarks::BookmarkModel* GetBookmarkModel() override {
+    return bookmark_model_;
+  }
+
+ private:
+  bookmarks::BookmarkModel* bookmark_model_;
+};
+
+class BookmarkModelTypeProcessorTest : public testing::Test {
+ public:
+  BookmarkModelTypeProcessorTest()
+      : bookmark_model_(bookmarks::TestBookmarkClient::CreateModel()),
+        sync_client_(bookmark_model_.get()) {}
+
+  TestSyncClient* sync_client() { return &sync_client_; }
+  bookmarks::BookmarkModel* bookmark_model() { return bookmark_model_.get(); }
+
+ private:
+  std::unique_ptr<bookmarks::BookmarkModel> bookmark_model_;
+  TestSyncClient sync_client_;
+};
+
+TEST_F(BookmarkModelTypeProcessorTest, ReorderUpdatesShouldIgnoreRootNodes) {
+  syncer::UpdateResponseDataList updates;
+  updates.push_back(CreateBookmarkRootUpdateData());
+  std::vector<const syncer::UpdateResponseData*> ordered_updates =
+      BookmarkModelTypeProcessor::ReorderUpdatesForTest(updates);
+  // Root node update should be filtered out.
+  EXPECT_THAT(ordered_updates.size(), Eq(0U));
+}
+
+// TODO(crbug.com/516866): This should change to cover the general case of
+// parents before children for non-deletions, and another test should be added
+// for children before parents for deletions.
+TEST_F(BookmarkModelTypeProcessorTest,
+       ReorderUpdatesShouldPlacePermanentNodesFirstForNonDeletions) {
+  const std::string kNode1Id = "node1";
+  const std::string kNode2Id = "node2";
+  syncer::UpdateResponseDataList updates;
+  updates.push_back(CreateUpdateData(
+      {kNode1Id, std::string(), std::string(), kNode2Id, std::string()}));
+  updates.push_back(CreateUpdateData({kNode2Id, std::string(), std::string(),
+                                      kBookmarksRootId, kBookmarkBarTag}));
+  std::vector<const syncer::UpdateResponseData*> ordered_updates =
+      BookmarkModelTypeProcessor::ReorderUpdatesForTest(updates);
+
+  // No update should be dropped.
+  ASSERT_THAT(ordered_updates.size(), Eq(2U));
+
+  // Updates should be ordered such that parent node update comes first.
+  EXPECT_THAT(ordered_updates[0]->entity.value().id, Eq(kNode2Id));
+  EXPECT_THAT(ordered_updates[1]->entity.value().id, Eq(kNode1Id));
+}
+
+TEST_F(BookmarkModelTypeProcessorTest, ShouldUpdateModelAfterRemoteCreation) {
+  BookmarkModelTypeProcessor processor(sync_client());
+
+  syncer::UpdateResponseDataList updates;
+  // Add update for the permanent folder "Bookmarks bar".
+  updates.push_back(
+      CreateUpdateData({"bookmark_bar", std::string(), std::string(),
+                        kBookmarksRootId, kBookmarkBarTag}));
+
+  // Add update for another node under the bookmarks bar.
+  const std::string kNodeId = "node_id";
+  const std::string kTitle = "title";
+  const std::string kUrl = "http://www.url.com";
+  updates.push_back(CreateUpdateData({kNodeId, kTitle, kUrl, kBookmarkBarTag,
+                                      /*server_tag=*/std::string()}));
+
+  const bookmarks::BookmarkNode* bookmarkbar =
+      bookmark_model()->bookmark_bar_node();
+  EXPECT_TRUE(bookmarkbar->empty());
+
+  processor.OnUpdateReceived(sync_pb::ModelTypeState(), updates);
+
+  ASSERT_THAT(bookmarkbar->GetChild(0), NotNull());
+  EXPECT_THAT(bookmarkbar->GetChild(0)->GetTitle(), Eq(ASCIIToUTF16(kTitle)));
+  EXPECT_THAT(bookmarkbar->GetChild(0)->url(), Eq(GURL(kUrl)));
+}
+
+TEST_F(BookmarkModelTypeProcessorTest, ShouldUpdateModelAfterRemoteUpdate) {
+  BookmarkModelTypeProcessor processor(sync_client());
+
+  const std::string kNodeId = "node_id";
+  const std::string kTitle = "title";
+  const std::string kUrl = "http://www.url.com";
+
+  std::vector<BookmarkInfo> bookmarks = {
+      {kNodeId, kTitle, kUrl, kBookmarkBarTag, /*server_tag=*/std::string()}};
+
+  InitWithSyncedBookmarks(bookmarks, &processor);
+
+  // Make sure original bookmark exists.
+  const bookmarks::BookmarkNode* bookmark_bar =
+      bookmark_model()->bookmark_bar_node();
+  const bookmarks::BookmarkNode* bookmark_node = bookmark_bar->GetChild(0);
+  ASSERT_THAT(bookmark_node, NotNull());
+  ASSERT_THAT(bookmark_node->GetTitle(), Eq(ASCIIToUTF16(kTitle)));
+  ASSERT_THAT(bookmark_node->url(), Eq(GURL(kUrl)));
+
+  // Process an update for the same bookmark.
+  const std::string kNewTitle = "new-title";
+  const std::string kNewUrl = "http://www.new-url.com";
+  syncer::UpdateResponseDataList updates;
+  updates.push_back(
+      CreateUpdateData({kNodeId, kNewTitle, kNewUrl, kBookmarkBarTag,
+                        /*server_tag=*/std::string()}));
+  processor.OnUpdateReceived(sync_pb::ModelTypeState(), updates);
+
+  // Check if the bookmark has been updated properly.
+  EXPECT_THAT(bookmark_bar->GetChild(0), Eq(bookmark_node));
+  EXPECT_THAT(bookmark_node->GetTitle(), Eq(ASCIIToUTF16(kNewTitle)));
+  EXPECT_THAT(bookmark_node->url(), Eq(GURL(kNewUrl)));
+}
+
+TEST_F(BookmarkModelTypeProcessorTest, ShouldUpdateModelAfterRemoteDelete) {
+  BookmarkModelTypeProcessor processor(sync_client());
+  // Build this structure
+  // bookmark_bar
+  //  |- folder1
+  //      |- title1
+  //      |- title2
+  //  |- folder2
+  //      |- title3
+
+  // Then send delete updates in this order
+  // folder1 -> title2 -> title1
+  // to exercise the code of creating a |foster_parent|.
+
+  const std::string kTitle1 = "title1";
+  const std::string kTitle1Id = "title1Id";
+  const std::string kTitle2 = "title2";
+  const std::string kTitle2Id = "title2Id";
+  const std::string kTitle3 = "title3";
+  const std::string kTitle3Id = "title3Id";
+  const std::string kFolder1 = "folder1";
+  const std::string kFolder1Id = "folder1Id";
+  const std::string kFolder2 = "folder2";
+  const std::string kFolder2Id = "folder2Id";
+  const std::string kUrl = "http://www.url.com";
+
+  std::vector<BookmarkInfo> bookmarks = {
+      {kFolder1Id, kFolder1, /*url=*/std::string(), kBookmarkBarTag,
+       /*server_tag=*/std::string()},
+      {kTitle1Id, kTitle1, kUrl, kFolder1Id, /*server_tag=*/std::string()},
+      {kTitle2Id, kTitle2, kUrl, kFolder1Id, /*server_tag=*/std::string()},
+      {kFolder2Id, kFolder2, /*url=*/std::string(), kBookmarkBarTag,
+       /*server_tag=*/std::string()},
+      {kTitle3Id, kTitle3, kUrl, kFolder2Id, /*server_tag=*/std::string()},
+  };
+
+  InitWithSyncedBookmarks(bookmarks, &processor);
+
+  const bookmarks::BookmarkNode* bookmarkbar =
+      bookmark_model()->bookmark_bar_node();
+
+  ASSERT_THAT(bookmarkbar->child_count(), Eq(2));
+  ASSERT_THAT(bookmarkbar->GetChild(0)->GetTitle(), Eq(ASCIIToUTF16(kFolder1)));
+  ASSERT_THAT(bookmarkbar->GetChild(0)->child_count(), Eq(2));
+  ASSERT_THAT(bookmarkbar->GetChild(1)->GetTitle(), Eq(ASCIIToUTF16(kFolder2)));
+  ASSERT_THAT(bookmarkbar->GetChild(1)->child_count(), Eq(1));
+  ASSERT_THAT(bookmarkbar->GetChild(1)->GetChild(0)->GetTitle(),
+              Eq(ASCIIToUTF16(kTitle3)));
+
+  // Process delete updates
+  syncer::UpdateResponseDataList updates;
+  updates.push_back(CreateTombstone(kTitle2Id));
+  updates.push_back(CreateTombstone(kTitle1Id));
+  updates.push_back(CreateTombstone(kFolder1Id));
+
+  const sync_pb::ModelTypeState model_type_state;
+  processor.OnUpdateReceived(model_type_state, updates);
 
-TEST_F(BookmarkModelTypeProcessorTest, CreateInstance) {
-  BookmarkModelTypeProcessor processor;
+  // The structure should be
+  // bookmark_bar
+  //  |- folder2
+  //      |- title3
+  EXPECT_THAT(bookmarkbar->child_count(), Eq(1));
+  EXPECT_THAT(bookmarkbar->GetChild(0)->GetTitle(), Eq(ASCIIToUTF16(kFolder2)));
+  EXPECT_THAT(bookmarkbar->GetChild(0)->child_count(), Eq(1));
+  EXPECT_THAT(bookmarkbar->GetChild(0)->GetChild(0)->GetTitle(),
+              Eq(ASCIIToUTF16(kTitle3)));
 }
 
 }  // namespace
diff --git a/chromium/components/sync_bookmarks/synced_bookmark_tracker.cc b/chromium/components/sync_bookmarks/synced_bookmark_tracker.cc
new file mode 100644
index 00000000000..175b16dc944
--- /dev/null
+++ b/chromium/components/sync_bookmarks/synced_bookmark_tracker.cc
@@ -0,0 +1,55 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/sync_bookmarks/synced_bookmark_tracker.h"
+
+#include <utility>
+
+#include "components/sync/model/entity_data.h"
+
+namespace sync_bookmarks {
+
+SyncedBookmarkTracker::Entity::Entity(
+    const bookmarks::BookmarkNode* bookmark_node)
+    : bookmark_node_(bookmark_node) {
+  DCHECK(bookmark_node);
+}
+
+SyncedBookmarkTracker::Entity::~Entity() = default;
+
+bool SyncedBookmarkTracker::Entity::MatchesData(
+    const syncer::EntityData& data) const {
+  // TODO(crbug.com/516866): Implement properly.
+  return false;
+}
+
+bool SyncedBookmarkTracker::Entity::IsUnsynced() const {
+  // TODO(crbug.com/516866): Implement properly.
+  return false;
+}
+
+SyncedBookmarkTracker::SyncedBookmarkTracker() = default;
+SyncedBookmarkTracker::~SyncedBookmarkTracker() = default;
+
+const SyncedBookmarkTracker::Entity* SyncedBookmarkTracker::GetEntityForSyncId(
+    const std::string& sync_id) const {
+  auto it = sync_id_to_entities_map_.find(sync_id);
+  return it != sync_id_to_entities_map_.end() ? it->second.get() : nullptr;
+}
+
+void SyncedBookmarkTracker::Associate(
+    const std::string& sync_id,
+    const bookmarks::BookmarkNode* bookmark_node) {
+  sync_id_to_entities_map_[sync_id] = std::make_unique<Entity>(bookmark_node);
+}
+
+void SyncedBookmarkTracker::Disassociate(const std::string& sync_id) {
+  sync_id_to_entities_map_.erase(sync_id);
+}
+
+std::size_t SyncedBookmarkTracker::TrackedEntitiesCountForTest() const {
+  return sync_id_to_entities_map_.size();
+}
+
+}  // namespace sync_bookmarks
diff --git a/chromium/components/sync_bookmarks/synced_bookmark_tracker.h b/chromium/components/sync_bookmarks/synced_bookmark_tracker.h
new file mode 100644
index 00000000000..84e5850ff3c
--- /dev/null
+++ b/chromium/components/sync_bookmarks/synced_bookmark_tracker.h
@@ -0,0 +1,85 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_SYNC_BOOKMARKS_SYNCED_BOOKMARK_TRACKER_H_
+#define COMPONENTS_SYNC_BOOKMARKS_SYNCED_BOOKMARK_TRACKER_H_
+
+#include <map>
+#include <memory>
+#include <string>
+
+#include "base/macros.h"
+#include "components/sync/protocol/entity_metadata.pb.h"
+
+namespace bookmarks {
+class BookmarkNode;
+}
+
+namespace syncer {
+struct EntityData;
+}
+
+namespace sync_bookmarks {
+
+// This class is responsible for keeping the mapping between bookmarks node in
+// the local model and the server-side corresponding sync entities. It manages
+// the metadata for its entity and caches entity data upon a local change until
+// commit confirmation is received.
+class SyncedBookmarkTracker {
+ public:
+  class Entity {
+   public:
+    // |bookmark_node| must not be null and must outlive this object.
+    explicit Entity(const bookmarks::BookmarkNode* bookmark_node);
+    ~Entity();
+
+    // Returns true if this data is out of sync with the server.
+    // A commit may or may not be in progress at this time.
+    bool IsUnsynced() const;
+
+    // Check whether |data| matches the stored specifics hash.
+    bool MatchesData(const syncer::EntityData& data) const;
+
+    // It never returns null.
+    const bookmarks::BookmarkNode* bookmark_node() const {
+      return bookmark_node_;
+    }
+
+   private:
+    const bookmarks::BookmarkNode* const bookmark_node_;
+
+    DISALLOW_COPY_AND_ASSIGN(Entity);
+  };
+
+  SyncedBookmarkTracker();
+  ~SyncedBookmarkTracker();
+
+  // Returns null if not entity is found.
+  const Entity* GetEntityForSyncId(const std::string& sync_id) const;
+
+  // Associates a server id with the corresponding local bookmark node in
+  // |sync_id_to_entities_map_|.
+  void Associate(const std::string& sync_id,
+                 const bookmarks::BookmarkNode* bookmark_node);
+
+  // Removes the association that corresponds to |sync_id| from
+  // |sync_id_to_entities_map_|.
+  void Disassociate(const std::string& sync_id);
+
+  // Returns number of tracked entities. Used only in test.
+  std::size_t TrackedEntitiesCountForTest() const;
+
+ private:
+  // A map of sync server ids to sync entities. This should contain entries and
+  // metadata for almost everything. However, since local data are loaded only
+  // when needed (e.g. before a commit cycle), the entities may not always
+  // contain model type data/specifics.
+  std::map<std::string, std::unique_ptr<Entity>> sync_id_to_entities_map_;
+
+  DISALLOW_COPY_AND_ASSIGN(SyncedBookmarkTracker);
+};
+
+}  // namespace sync_bookmarks
+
+#endif  // COMPONENTS_SYNC_BOOKMARKS_SYNCED_BOOKMARK_TRACKER_H_
diff --git a/chromium/components/sync_bookmarks/synced_bookmark_tracker_unittest.cc b/chromium/components/sync_bookmarks/synced_bookmark_tracker_unittest.cc
new file mode 100644
index 00000000000..877eeaf2193
--- /dev/null
+++ b/chromium/components/sync_bookmarks/synced_bookmark_tracker_unittest.cc
@@ -0,0 +1,45 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/sync_bookmarks/synced_bookmark_tracker.h"
+
+#include "components/bookmarks/browser/bookmark_node.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using testing::Eq;
+using testing::IsNull;
+using testing::NotNull;
+
+namespace sync_bookmarks {
+
+namespace {
+
+TEST(SyncedBookmarkTrackerTest, ShouldGetAssociatedNodes) {
+  SyncedBookmarkTracker tracker;
+  const std::string kSyncId = "SYNC_ID";
+  const int64_t kId = 1;
+  bookmarks::BookmarkNode node(kId, GURL());
+  tracker.Associate(kSyncId, &node);
+  const SyncedBookmarkTracker::Entity* entity =
+      tracker.GetEntityForSyncId(kSyncId);
+  ASSERT_THAT(entity, NotNull());
+  EXPECT_THAT(entity->bookmark_node(), Eq(&node));
+  EXPECT_THAT(tracker.GetEntityForSyncId("unknown id"), IsNull());
+}
+
+TEST(SyncedBookmarkTrackerTest, ShouldReturnNullForDisassociatedNodes) {
+  SyncedBookmarkTracker tracker;
+  const std::string kSyncId = "SYNC_ID";
+  const int64_t kId = 1;
+  bookmarks::BookmarkNode node(kId, GURL());
+  tracker.Associate(kSyncId, &node);
+  ASSERT_THAT(tracker.GetEntityForSyncId(kSyncId), NotNull());
+  tracker.Disassociate(kSyncId);
+  EXPECT_THAT(tracker.GetEntityForSyncId(kSyncId), IsNull());
+}
+
+}  // namespace
+
+}  // namespace sync_bookmarks