// 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