1 files changed, 504 insertions, 0 deletions
diff --git a/chrome/browser/sync/glue/model_associator.cc b/chrome/browser/sync/glue/model_associator.cc
new file mode 100644
index 0000000..3d73612
--- /dev/null
+++ b/chrome/browser/sync/glue/model_associator.cc
@@ -0,0 +1,504 @@
+// Copyright (c) 2006-2009 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.
+
+#ifdef CHROME_PERSONALIZATION
+
+#include "chrome/browser/sync/glue/model_associator.h"
+
+#include <stack>
+
+#include "base/message_loop.h"
+#include "base/task.h"
+#include "chrome/browser/bookmarks/bookmark_model.h"
+#include "chrome/browser/sync/engine/syncapi.h"
+#include "chrome/browser/sync/profile_sync_service.h"
+
+namespace browser_sync {
+
+// The sync protocol identifies top-level entities by means of well-known tags,
+// which should not be confused with titles.  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.
+//
+// TODO(ncarter): Pull these tags from an external protocol specification
+// rather than hardcoding them here.
+static const wchar_t* kOtherBookmarksTag = L"other_bookmarks";
+static const wchar_t* kBookmarkBarTag = L"bookmark_bar";
+
+// Bookmark comparer for map of bookmark nodes.
+class BookmarkComparer {
+ public:
+  // Compares the two given nodes and returns whether node1 should appear
+  // before node2 in strict weak ordering.
+  bool operator()(const BookmarkNode* node1,
+                  const BookmarkNode* node2) const {
+    DCHECK(node1);
+    DCHECK(node2);
+
+    // Keep folder nodes before non-folder nodes.
+    if (node1->is_folder() != node2->is_folder())
+      return node1->is_folder();
+
+    int result = node1->GetTitle().compare(node2->GetTitle());
+    if (result != 0)
+      return result < 0;
+
+    result = node1->GetURL().spec().compare(node2->GetURL().spec());
+    if (result != 0)
+      return result < 0;
+
+    return false;
+  }
+};
+
+// Provides the following abstraction: given a parent bookmark node, find best
+// matching child node for many sync nodes.
+class BookmarkNodeFinder {
+ public:
+  // Creats an instance with the given parent bookmark node.
+  explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
+
+  // Finds best matching node for the given sync node.
+  // Returns the matching node if one exists; NULL otherwise. If a matching
+  // node is found, it's removed for further matches.
+  const BookmarkNode* FindBookmarkNode(const sync_api::BaseNode& sync_node);
+
+ private:
+  typedef std::set<const BookmarkNode*, BookmarkComparer> BookmarkNodesSet;
+
+  const BookmarkNode* parent_node_;
+  BookmarkNodesSet child_nodes_;
+
+  DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
+};
+
+BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node)
+    : parent_node_(parent_node) {
+  for (int i = 0; i < parent_node_->GetChildCount(); ++i)
+    child_nodes_.insert(parent_node_->GetChild(i));
+}
+
+const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
+    const sync_api::BaseNode& sync_node) {
+  // Create a bookmark node from the given sync node.
+  BookmarkNode temp_node(GURL(sync_node.GetURL()));
+  temp_node.SetTitle(UTF16ToWide(sync_node.GetTitle()));
+  if (sync_node.GetIsFolder())
+    temp_node.SetType(BookmarkNode::FOLDER);
+  else
+    temp_node.SetType(BookmarkNode::URL);
+
+  const BookmarkNode* result = NULL;
+  BookmarkNodesSet::iterator iter = child_nodes_.find(&temp_node);
+  if (iter != child_nodes_.end()) {
+    result = *iter;
+    // Remove the matched node so we don't match with it again.
+    child_nodes_.erase(iter);
+  }
+
+  return result;
+}
+
+ModelAssociator::ModelAssociator(ProfileSyncService* sync_service)
+    : sync_service_(sync_service),
+      task_pending_(false) {
+  DCHECK(sync_service_);
+}
+
+void ModelAssociator::ClearAll() {
+  id_map_.clear();
+  id_map_inverse_.clear();
+  dirty_assocations_sync_ids_.clear();
+}
+
+int64 ModelAssociator::GetSyncIdFromBookmarkId(int64 node_id) const {
+  BookmarkIdToSyncIdMap::const_iterator iter = id_map_.find(node_id);
+  return iter == id_map_.end() ? sync_api::kInvalidId : iter->second;
+}
+
+bool ModelAssociator::GetBookmarkIdFromSyncId(int64 sync_id,
+                                              int64* node_id) const {
+  SyncIdToBookmarkIdMap::const_iterator iter = id_map_inverse_.find(sync_id);
+  if (iter == id_map_inverse_.end())
+    return false;
+  *node_id = iter->second;
+  return true;
+}
+
+bool ModelAssociator::InitSyncNodeFromBookmarkId(
+    int64 node_id,
+    sync_api::BaseNode* sync_node) {
+  DCHECK(sync_node);
+  int64 sync_id = GetSyncIdFromBookmarkId(node_id);
+  if (sync_id == sync_api::kInvalidId)
+    return false;
+  if (!sync_node->InitByIdLookup(sync_id))
+    return false;
+  DCHECK(sync_node->GetId() == sync_id);
+  return true;
+}
+
+const BookmarkNode* ModelAssociator::GetBookmarkNodeFromSyncId(int64 sync_id) {
+  int64 node_id;
+  if (!GetBookmarkIdFromSyncId(sync_id, &node_id))
+    return false;
+  BookmarkModel* model = sync_service_->profile()->GetBookmarkModel();
+  return model->GetNodeByID(node_id);
+}
+
+void ModelAssociator::AssociateIds(int64 node_id, int64 sync_id) {
+  DCHECK_NE(sync_id, sync_api::kInvalidId);
+  DCHECK(id_map_.find(node_id) == id_map_.end());
+  DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end());
+  id_map_[node_id] = sync_id;
+  id_map_inverse_[sync_id] = node_id;
+  dirty_assocations_sync_ids_.insert(sync_id);
+  PostPersistAssociationsTask();
+}
+
+void ModelAssociator::DisassociateIds(int64 sync_id) {
+  SyncIdToBookmarkIdMap::iterator iter = id_map_inverse_.find(sync_id);
+  if (iter == id_map_inverse_.end())
+    return;
+  id_map_.erase(iter->second);
+  id_map_inverse_.erase(iter);
+  dirty_assocations_sync_ids_.erase(sync_id);
+}
+
+bool ModelAssociator::BookmarkModelHasUserCreatedNodes() const {
+  BookmarkModel* model = sync_service_->profile()->GetBookmarkModel();
+  DCHECK(model->IsLoaded());
+  return model->GetBookmarkBarNode()->GetChildCount() > 0 ||
+         model->other_node()->GetChildCount() > 0;
+}
+
+bool ModelAssociator::SyncModelHasUserCreatedNodes() {
+  int64 bookmark_bar_sync_id;
+  if (!GetSyncIdForTaggedNode(WideToUTF16(kBookmarkBarTag),
+                              &bookmark_bar_sync_id)) {
+    NOTREACHED();
+    return false;
+  }
+  int64 other_bookmarks_sync_id;
+  if (!GetSyncIdForTaggedNode(WideToUTF16(kOtherBookmarksTag),
+                              &other_bookmarks_sync_id)) {
+    NOTREACHED();
+    return false;
+  }
+
+  sync_api::ReadTransaction trans(
+      sync_service_->backend()->GetUserShareHandle());
+
+  sync_api::ReadNode bookmark_bar_node(&trans);
+  if (!bookmark_bar_node.InitByIdLookup(bookmark_bar_sync_id)) {
+    NOTREACHED();
+    return false;
+  }
+
+  sync_api::ReadNode other_bookmarks_node(&trans);
+  if (!other_bookmarks_node.InitByIdLookup(other_bookmarks_sync_id)) {
+    NOTREACHED();
+    return false;
+  }
+
+  // Sync model has user created nodes if either one of the permanent nodes
+  // has children.
+  return bookmark_bar_node.GetFirstChildId() != sync_api::kInvalidId ||
+         other_bookmarks_node.GetFirstChildId() != sync_api::kInvalidId;
+}
+
+bool ModelAssociator::NodesMatch(const BookmarkNode* bookmark,
+                                 const sync_api::BaseNode* sync_node) const {
+  if (bookmark->GetTitle() != UTF16ToWide(sync_node->GetTitle()))
+    return false;
+  if (bookmark->is_folder() != sync_node->GetIsFolder())
+    return false;
+  if (bookmark->is_url()) {
+    if (bookmark->GetURL() != GURL(sync_node->GetURL()))
+      return false;
+  }
+  // Don't compare favicons here, because they are not really
+  // user-updated and we don't have versioning information -- a site changing
+  // its favicon shouldn't result in a bookmark mismatch.
+  return true;
+}
+
+bool ModelAssociator::AssociateTaggedPermanentNode(
+    const BookmarkNode* permanent_node,
+    const string16 &tag) {
+  // Do nothing if |permanent_node| is already initialized and associated.
+  int64 sync_id = GetSyncIdFromBookmarkId(permanent_node->id());
+  if (sync_id != sync_api::kInvalidId)
+    return true;
+  if (!GetSyncIdForTaggedNode(tag, &sync_id))
+    return false;
+
+  AssociateIds(permanent_node->id(), sync_id);
+  return true;
+}
+
+bool ModelAssociator::GetSyncIdForTaggedNode(const string16& tag,
+                                             int64* sync_id) {
+  sync_api::ReadTransaction trans(
+      sync_service_->backend()->GetUserShareHandle());
+  sync_api::ReadNode sync_node(&trans);
+  if (!sync_node.InitByTagLookup(tag.c_str()))
+    return false;
+  *sync_id = sync_node.GetId();
+  return true;
+}
+
+bool ModelAssociator::AssociateModels() {
+  // Try to load model associations from persisted associations first. If that
+  // succeeds, we don't need to run the complex model matching algorithm.
+  if (LoadAssociations())
+    return true;
+
+  ClearAll();
+
+  // We couldn't load model assocations from persisted assocations. So build
+  // them.
+  return BuildAssocations();
+}
+
+bool ModelAssociator::BuildAssocations() {
+  // Algorithm description:
+  // Match up the roots and recursively do the following:
+  // * For each sync node for the current sync parent node, find the best
+  //   matching bookmark node under the corresponding bookmark parent node.
+  //   If no matching node is found, create a new bookmark node in the same
+  //   position as the corresponding sync node.
+  //   If a matching node is found, update the properties of it from the
+  //   corresponding sync node.
+  // * When all children sync nodes are done, add the extra children bookmark
+  //   nodes to the sync parent node.
+  //
+  // This algorithm will do a good job of merging when folder names are a good
+  // indicator of the two folders being the same. It will handle reordering and
+  // new node addition very well (without creating duplicates).
+  // This algorithm will not do well if the folder name has changes but the
+  // children under them are all the same.
+
+  BookmarkModel* model = sync_service_->profile()->GetBookmarkModel();
+  DCHECK(model->IsLoaded());
+
+  // To prime our association, we associate the top-level nodes, Bookmark Bar
+  // and Other Bookmarks.
+  if (!AssociateTaggedPermanentNode(model->other_node(),
+                                    WideToUTF16(kOtherBookmarksTag))) {
+    NOTREACHED() << "Server did not create top-level nodes.  Possibly we "
+                 << "are running against an out-of-date server?";
+    return false;
+  }
+  if (!AssociateTaggedPermanentNode(model->GetBookmarkBarNode(),
+                                    WideToUTF16(kBookmarkBarTag))) {
+    NOTREACHED() << "Server did not create top-level nodes.  Possibly we "
+                 << "are running against an out-of-date server?";
+    return false;
+  }
+  int64 bookmark_bar_sync_id = GetSyncIdFromBookmarkId(
+      model->GetBookmarkBarNode()->id());
+  DCHECK(bookmark_bar_sync_id != sync_api::kInvalidId);
+  int64 other_bookmarks_sync_id = GetSyncIdFromBookmarkId(
+      model->other_node()->id());
+  DCHECK(other_bookmarks_sync_id!= sync_api::kInvalidId);
+
+  std::stack<int64> dfs_stack;
+  dfs_stack.push(other_bookmarks_sync_id);
+  dfs_stack.push(bookmark_bar_sync_id);
+
+  sync_api::WriteTransaction trans(
+      sync_service_->backend()->GetUserShareHandle());
+
+  while (!dfs_stack.empty()) {
+    int64 sync_parent_id = dfs_stack.top();
+    dfs_stack.pop();
+
+    sync_api::ReadNode sync_parent(&trans);
+    if (!sync_parent.InitByIdLookup(sync_parent_id)) {
+      NOTREACHED();
+      return false;
+    }
+    // Only folder nodes are pushed on to the stack.
+    DCHECK(sync_parent.GetIsFolder());
+
+    const BookmarkNode* parent_node = GetBookmarkNodeFromSyncId(sync_parent_id);
+    DCHECK(parent_node->is_folder());
+
+    BookmarkNodeFinder node_finder(parent_node);
+
+    int index = 0;
+    int64 sync_child_id = sync_parent.GetFirstChildId();
+    while (sync_child_id != sync_api::kInvalidId) {
+      sync_api::WriteNode sync_child_node(&trans);
+      if (!sync_child_node.InitByIdLookup(sync_child_id)) {
+        NOTREACHED();
+        return false;
+      }
+
+      const BookmarkNode* child_node = NULL;
+      child_node = node_finder.FindBookmarkNode(sync_child_node);
+      if (child_node) {
+        model->Move(child_node, parent_node, index);
+        // Set the favicon for bookmark node from sync node or vice versa.
+        if (!sync_service_->SetBookmarkFavicon(&sync_child_node, child_node))
+          sync_service_->SetSyncNodeFavicon(child_node, &sync_child_node);
+      } else {
+        // Create a new bookmark node for the sync node.
+        child_node = sync_service_->CreateBookmarkNode(&sync_child_node,
+                                                       parent_node,
+                                                       index);
+      }
+      AssociateIds(child_node->id(), sync_child_id);
+      if (sync_child_node.GetIsFolder())
+        dfs_stack.push(sync_child_id);
+
+      sync_child_id = sync_child_node.GetSuccessorId();
+      ++index;
+    }
+
+    // At this point all the children nodes of the parent sync node have
+    // corresponding children in the parent bookmark node and they are all in
+    // the right positions: from 0 to index - 1.
+    // So the children starting from index in the parent bookmark node are the
+    // ones that are not present in the parent sync node. So create them.
+    for (int i = index; i < parent_node->GetChildCount(); ++i) {
+      sync_child_id = sync_service_->CreateSyncNode(parent_node, i, &trans);
+      if (parent_node->GetChild(i)->is_folder())
+        dfs_stack.push(sync_child_id);
+    }
+  }
+  return true;
+}
+
+void ModelAssociator::PostPersistAssociationsTask() {
+  // No need to post a task if a task is already pending.
+  if (task_pending_)
+    return;
+  task_pending_ = true;
+  MessageLoop::current()->PostTask(
+      FROM_HERE,
+      NewRunnableMethod(this, &ModelAssociator::PersistAssociations));
+}
+
+void ModelAssociator::PersistAssociations() {
+  DCHECK(task_pending_);
+  task_pending_ = false;
+
+  // If there are no dirty assocations we have nothing to do. We handle this
+  // explicity instead of letting the for loop do it to avoid creating a write
+  // transaction in this case.
+  if (dirty_assocations_sync_ids_.empty()) {
+    DCHECK(id_map_.empty());
+    DCHECK(id_map_inverse_.empty());
+    return;
+  }
+
+  sync_api::WriteTransaction trans(
+      sync_service_->backend()->GetUserShareHandle());
+  DirtyAssocationsSyncIds::iterator iter;
+  for (iter = dirty_assocations_sync_ids_.begin();
+       iter != dirty_assocations_sync_ids_.end();
+       ++iter) {
+    int64 sync_id = *iter;
+    sync_api::WriteNode sync_node(&trans);
+    if (!sync_node.InitByIdLookup(sync_id)) {
+      sync_service_->SetUnrecoverableError();
+      return;
+    }
+    int64 node_id;
+    if (GetBookmarkIdFromSyncId(sync_id, &node_id))
+      sync_node.SetExternalId(node_id);
+    else
+      NOTREACHED();
+  }
+  dirty_assocations_sync_ids_.clear();
+}
+
+bool ModelAssociator::LoadAssociations() {
+  BookmarkModel* model = sync_service_->profile()->GetBookmarkModel();
+  DCHECK(model->IsLoaded());
+  // If the bookmarks changed externally, our previous assocations may not be
+  // valid; so return false.
+  if (model->file_changed())
+    return false;
+
+  // Our persisted assocations should be valid. Try to populate id assocation
+  // maps using persisted assocations.
+
+  int64 other_bookmarks_id;
+  if (!GetSyncIdForTaggedNode(WideToUTF16(kOtherBookmarksTag),
+                              &other_bookmarks_id)) {
+    NOTREACHED();  // We should always be able to find the permanent nodes.
+    return false;
+  }
+  int64 bookmark_bar_id;
+  if (!GetSyncIdForTaggedNode(WideToUTF16(kBookmarkBarTag), &bookmark_bar_id)) {
+    NOTREACHED();  // We should always be able to find the permanent nodes.
+    return false;
+  }
+
+  std::stack<int64> dfs_stack;
+  dfs_stack.push(other_bookmarks_id);
+  dfs_stack.push(bookmark_bar_id);
+
+  sync_api::ReadTransaction trans(
+      sync_service_->backend()->GetUserShareHandle());
+
+  while (!dfs_stack.empty()) {
+    int64 parent_id = dfs_stack.top();
+    dfs_stack.pop();
+    sync_api::ReadNode sync_parent(&trans);
+    if (!sync_parent.InitByIdLookup(parent_id)) {
+      NOTREACHED();
+      return false;
+    }
+
+    int64 external_id = sync_parent.GetExternalId();
+    if (external_id == 0)
+      return false;
+
+    const BookmarkNode* node = model->GetNodeByID(external_id);
+    if (!node)
+      return false;
+
+    // Don't try to call NodesMatch on permanent nodes like bookmark bar and
+    // other bookmarks. They are not expected to match.
+    if (node != model->GetBookmarkBarNode() &&
+        node != model->other_node() &&
+        !NodesMatch(node, &sync_parent))
+      return false;
+
+    AssociateIds(external_id, sync_parent.GetId());
+    
+    // Add all children of the current node to the stack.
+    int64 child_id = sync_parent.GetFirstChildId();
+    while (child_id != sync_api::kInvalidId) {
+      dfs_stack.push(child_id);
+      sync_api::ReadNode child_node(&trans);
+      if (!child_node.InitByIdLookup(child_id)) {
+        NOTREACHED();
+        return false;
+      }
+      child_id = child_node.GetSuccessorId();
+    }
+  }
+  DCHECK(dfs_stack.empty());
+  return true;
+}
+
+}  // namespace browser_sync
+
+#endif  // CHROME_PERSONALIZATION