Use delete journal to remove bookmarks that are already deleted in sync model

chrome/browser/sync/glue/bookmark_model_associator.cc

 // Copyright 2012 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 "chrome/browser/sync/glue/bookmark_model_associator.h"
 
 #include <stack>
 
 #include "base/bind.h"
 #include "base/command_line.h"
 #include "base/hash_tables.h"
 #include "base/location.h"
 #include "base/message_loop.h"
 #include "base/string_number_conversions.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/browser/sync/glue/bookmark_change_processor.h"
 #include "content/public/browser/browser_thread.h"
 #include "sync/api/sync_error.h"
+#include "sync/internal_api/public/delete_journal.h"
 #include "sync/internal_api/public/read_node.h"
 #include "sync/internal_api/public/read_transaction.h"
 #include "sync/internal_api/public/write_node.h"
 #include "sync/internal_api/public/write_transaction.h"
 #include "sync/syncable/syncable_write_transaction.h"
 #include "sync/util/cryptographer.h"
 #include "sync/util/data_type_histogram.h"
 
 using content::BrowserThread;
 
@@ skipping 46 matching lines @@
   }
 };
 
 // Provides the following abstraction: given a parent bookmark node, find best
 // matching child node for many sync nodes.
 class BookmarkNodeFinder {
  public:
   // Creates an instance with the given parent bookmark node.
   explicit BookmarkNodeFinder(const BookmarkNode* parent_node);
 
   // Finds best matching node for the given sync node.

[tim (not reviewing), 2013/01/14 23:32:48]

Update comment.

[haitaol1, 2013/01/15 19:44:31]

Done.

   // 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 syncer::BaseNode& sync_node);
+  const BookmarkNode* FindBookmarkNode(const GURL& url,
+                                       const std::string& title,
+                                       bool is_folder);
 
  private:
   typedef std::multiset<const BookmarkNode*, BookmarkComparer> BookmarkNodesSet;
 
   const BookmarkNode* parent_node_;
   BookmarkNodesSet child_nodes_;
 
   DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder);
 };
 
@@ skipping 15 matching lines @@
 };
 
 BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node)
     : parent_node_(parent_node) {
   for (int i = 0; i < parent_node_->child_count(); ++i) {
     child_nodes_.insert(parent_node_->GetChild(i));
   }
 }
 
 const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode(
-    const syncer::BaseNode& sync_node) {
-  // Create a bookmark node from the given sync node.
-  BookmarkNode temp_node(GURL(sync_node.GetBookmarkSpecifics().url()));
-  temp_node.SetTitle(UTF8ToUTF16(sync_node.GetTitle()));
-  if (sync_node.GetIsFolder())
+    const GURL& url, const std::string& title, bool is_folder) {
+  // Create a bookmark node from the given bookmark attributes.
+  BookmarkNode temp_node(url);
+  temp_node.SetTitle(UTF8ToUTF16(title));
+  if (is_folder)
     temp_node.set_type(BookmarkNode::FOLDER);
   else
     temp_node.set_type(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);
@@ skipping 299 matching lines @@
   syncer::WriteTransaction trans(FROM_HERE, user_share_);
   syncer::ReadNode bm_root(&trans);
   if (bm_root.InitByTagLookup(syncer::ModelTypeToRootTag(syncer::BOOKMARKS)) ==
       syncer::BaseNode::INIT_OK) {
     syncer_merge_result->set_num_items_before_association(
         bm_root.GetTotalNodeCount());
   }
   local_merge_result->set_num_items_before_association(
       bookmark_model_->root_node()->GetTotalNodeCount());
 
+  // Remove obsolete bookmarks according to sync delete journal.
+  local_merge_result->set_num_items_deleted(
+      ApplyDeletesFromSyncJournal(&trans));
+
   while (!dfs_stack.empty()) {
     int64 sync_parent_id = dfs_stack.top();
     dfs_stack.pop();
 
     syncer::ReadNode sync_parent(&trans);
     if (sync_parent.InitByIdLookup(sync_parent_id) !=
             syncer::BaseNode::INIT_OK) {
       return unrecoverable_error_handler_->CreateAndUploadError(
           FROM_HERE,
           "Failed to lookup node.",
@@ skipping 13 matching lines @@
       syncer::WriteNode sync_child_node(&trans);
       if (sync_child_node.InitByIdLookup(sync_child_id) !=
               syncer::BaseNode::INIT_OK) {
         return unrecoverable_error_handler_->CreateAndUploadError(
             FROM_HERE,
             "Failed to lookup node.",
             model_type());
       }
 
       const BookmarkNode* child_node = NULL;
-      child_node = node_finder.FindBookmarkNode(sync_child_node);
+      child_node = node_finder.FindBookmarkNode(
+          GURL(sync_child_node.GetBookmarkSpecifics().url()),
+          sync_child_node.GetTitle(),
+          sync_child_node.GetIsFolder());
       if (child_node)
         Associate(child_node, sync_child_id);
       // All bookmarks are currently modified at association time (even if
       // it doesn't change anything).
       // TODO(sync): introduce logic to only modify the bookmark model if
       // necessary.
       const BookmarkNode* new_child_node =
           BookmarkChangeProcessor::CreateOrUpdateBookmarkNode(
               &sync_child_node,
               bookmark_model_,
@@ skipping 35 matching lines @@
   }
 
   local_merge_result->set_num_items_after_association(
       bookmark_model_->root_node()->GetTotalNodeCount());
   syncer_merge_result->set_num_items_after_association(
       bm_root.GetTotalNodeCount());
 
   return syncer::SyncError();
 }
 
+struct FolderInfo {
+  FolderInfo(const BookmarkNode* f, const BookmarkNode* p, int64 id)
+      : folder(f), parent(p), sync_id(id) {}
+  const BookmarkNode* folder;
+  const BookmarkNode* parent;
+  int64 sync_id;
+};
+typedef std::vector<FolderInfo> FolderInfoList;
+
+int64 BookmarkModelAssociator::ApplyDeletesFromSyncJournal(
+    syncer::BaseTransaction* trans) {
+  int64 num_bookmark_deleted = 0;
+
+  syncer::BookmarkDeleteJournalList bk_delete_journals;
+  syncer::DeleteJournal::GetBookmarkDeleteJournals(trans, &bk_delete_journals);
+  if (bk_delete_journals.empty())
+    return 0;
+  size_t num_journals_unmatched = bk_delete_journals.size();
+
+  // Check bookmark model from top to bottom.
+  std::stack<const BookmarkNode*> dfs_stack;
+  dfs_stack.push(bookmark_model_->bookmark_bar_node());
+  dfs_stack.push(bookmark_model_->other_node());
+  if (expect_mobile_bookmarks_folder_)
+    dfs_stack.push(bookmark_model_->mobile_node());
+
+  FolderInfoList folders_matched;

[tim (not reviewing), 2013/01/14 23:32:48]

Comment explaining why we keep this, which I think is so that the 2-pass
algorithm below works; 1st pass to identify folders but not remove them. I think
(?) we avoid removal so that we can add their children to the dfs? Could we not
Remove in the same iteration of the loop after we add the children, avoid the
extra scan and avoid the need for the  FolderInfoList?)  Could we also then add
the id to journals_to_purge from the same loop? 

[haitaol1, 2013/01/15 19:44:31]

Added comments. Do it in one pass is difficult because folders could embed in
each other, making it difficult to decide whether the upper-level folder should
be removed. Second scan should not cost too much because it only looks at
folders found in first pass.

On 2013/01/14 23:32:48, timsteele wrote:

+  while (!dfs_stack.empty()) {
+    const BookmarkNode* parent = dfs_stack.top();
+    dfs_stack.pop();
+
+    BookmarkNodeFinder finder(parent);
+    // Iterate through journals from back to front and keep unmatched journals

[tim (not reviewing), 2013/01/14 23:32:48]

Mention that the reason we do this shuffling is so we can conveniently read off
all remaining unmatched entries after the loop.

[haitaol1, 2013/01/15 19:44:31]

Done.

+    // at the beginning of journal list.
+    for (int i = num_journals_unmatched - 1; i >= 0; --i) {
+      const BookmarkNode* child = finder.FindBookmarkNode(
+          GURL(bk_delete_journals[i].specifics.bookmark().url()),
+          bk_delete_journals[i].specifics.bookmark().title(),
+          bk_delete_journals[i].is_folder);
+      if (child) {
+        if (child->is_folder()) {
+          // Remember matched folder without removing and delete only empty
+          // ones later.
+          folders_matched.push_back(FolderInfo(child, parent,
+                                               bk_delete_journals[i].id));
+        } else {
+          bookmark_model_->Remove(parent, parent->GetIndexOf(child));
+          ++num_bookmark_deleted;
+        }
+        // Move unmatched journal here and decrement counter.
+        bk_delete_journals[i] = bk_delete_journals[--num_journals_unmatched];
+      }
+    }
+    if (num_journals_unmatched == 0)
+      break;
+
+    for (int i = 0; i < parent->child_count(); ++i) {
+      if (parent->GetChild(i)->is_folder())
+        dfs_stack.push(parent->GetChild(i));
+    }
+  }
+
+  // Ids of sync nodes not found in bookmark model, meaning the deletions are
+  // persisted and correponding delete journals can be dropped.
+  std::set<int64> journals_to_purge;
+
+  // Remove empty folders from bottom to top.
+  for (FolderInfoList::const_reverse_iterator it = folders_matched.rbegin();
+      it != folders_matched.rend(); ++it) {
+    if (it->folder->child_count() == 0) {
+      bookmark_model_->Remove(it->parent, it->parent->GetIndexOf(it->folder));
+      ++num_bookmark_deleted;
+    } else {
+      // Keep non-empty folder and remove its journal so that it won't match
+      // again in the future.
+      journals_to_purge.insert(it->sync_id);
+    }
+  }
+
+  // Purge unmatched journals.
+  for (size_t i = 0; i < num_journals_unmatched; ++i)
+    journals_to_purge.insert(bk_delete_journals[i].id);
+  syncer::DeleteJournal::PurgeDeleteJournals(trans, journals_to_purge);
+
+  return num_bookmark_deleted;
+}
+
 void BookmarkModelAssociator::PostPersistAssociationsTask() {
   // No need to post a task if a task is already pending.
   if (weak_factory_.HasWeakPtrs())
     return;
   MessageLoop::current()->PostTask(
       FROM_HERE,
       base::Bind(
           &BookmarkModelAssociator::PersistAssociations,
           weak_factory_.GetWeakPtr()));
 }
@@ skipping 57 matching lines @@
       UMA_HISTOGRAM_ENUMERATION("Sync.LocalModelOutOfSync",
                                 syncer::BOOKMARKS, syncer::MODEL_TYPE_COUNT);
       // Clear version on bookmark model so that we only report error once.
       bookmark_model_->DeleteNodeMetaInfo(bookmark_model_->root_node(),
                                           kBookmarkTransactionVersionKey);
     }
   }
 }
 
 }  // namespace browser_sync