Fix the pinning algorithm so that pinned URLs are not shifted during insertions and deletions.

BUG=none
TEST=TopSitesTest

Review URL: http://codereview.chromium.org/3039029

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@53796 0039d316-1c4b-4281-b951-d872f2087c98

2 files changed, 66 insertions, 23 deletions

diff --git a/chrome/browser/history/top_sites.cc b/chrome/browser/history/top_sites.cc
index a568e2b..3d9a719 100644
--- a/chrome/browser/history/top_sites.cc
+++ b/chrome/browser/history/top_sites.cc
@@ -370,36 +370,48 @@ void TopSites::MigratePinnedURLs() {
 
 void TopSites::ApplyBlacklistAndPinnedURLs(const MostVisitedURLList& urls,
                                            MostVisitedURLList* out) {
+  MostVisitedURLList urls_copy;
   for (size_t i = 0; i < urls.size(); i++) {
     if (!IsBlacklisted(urls[i].url))
-      out->push_back(urls[i]);
+      urls_copy.push_back(urls[i]);
   }
 
-  for (DictionaryValue::key_iterator it = pinned_urls_->begin_keys();
-       it != pinned_urls_->end_keys(); ++it) {
-    GURL url(WideToASCII(*it));
-
-    int index = IndexOf(*out, url);
-    if (index == -1) {
-      if (url.is_empty()) {
-        MigratePinnedURLs();
-        out->clear();
-        ApplyBlacklistAndPinnedURLs(urls, out);
-        return;
-      }
-      LOG(INFO) << "Unknown url: " << url.spec();
+  for (size_t pinned_index = 0; pinned_index < kTopSitesShown; pinned_index++) {
+    GURL url;
+    bool found = GetPinnedURLAtIndex(pinned_index, &url);
+    if (!found)
       continue;
+
+    DCHECK(!url.is_empty());
+    int cur_index = IndexOf(urls_copy, url);
+    MostVisitedURL tmp;
+    if (cur_index < 0) {
+      // Pinned URL not in urls.
+      tmp.url = url;
+    } else {
+      tmp = urls_copy[cur_index];
+      urls_copy.erase(urls_copy.begin() + cur_index);
     }
+    if (pinned_index > out->size())
+      out->resize(pinned_index);  // Add empty URLs as fillers.
+    out->insert(out->begin() + pinned_index, tmp);
+  }
 
-    size_t pinned_index = 0;
-    bool result = GetIndexOfPinnedURL(url, &pinned_index);
-    DCHECK(result) << url.spec();
-    if (static_cast<int>(pinned_index) != index) {
-      MostVisitedURL tmp = (*out)[index];
-      out->erase(out->begin() + index);
-      if (pinned_index > out->size())
-        out->resize(pinned_index);  // Add empty URLs as fillers.
-      out->insert(out->begin() + pinned_index, tmp);
+  // Add non-pinned URLs in the empty spots.
+  size_t current_url = 0;  // Index into the remaining URLs in urls_copy.
+  for (size_t i = 0; i < kTopSitesShown && current_url < urls_copy.size();
+       i++) {
+    if (i == out->size()) {
+      out->push_back(urls_copy[current_url]);
+      current_url++;
+    } else if (i < out->size()) {
+      if ((*out)[i].url.is_empty()) {
+        // Replace the filler
+        (*out)[i] = urls_copy[current_url];
+        current_url++;
+      }
+    } else {
+      NOTREACHED();
     }
   }
 }
@@ -650,6 +662,7 @@ void TopSites::StartQueryForMostVisited() {
 void TopSites::StartMigration() {
   migration_in_progress_ = true;
   StartQueryForMostVisited();
+  MigratePinnedURLs();
 }
 
 void TopSites::AddBlacklistedURL(const GURL& url) {
diff --git a/chrome/browser/history/top_sites_unittest.cc b/chrome/browser/history/top_sites_unittest.cc
index 60d4a86..c07c6fd 100644
--- a/chrome/browser/history/top_sites_unittest.cc
+++ b/chrome/browser/history/top_sites_unittest.cc
@@ -1115,6 +1115,36 @@ TEST_F(TopSitesTest, PinnedURLs) {
   EXPECT_EQ("http://google.com/", urls()[1].url.spec());
   EXPECT_EQ(welcome_url(), urls()[2].url);
   EXPECT_EQ(themes_url(), urls()[3].url);
+
+  top_sites().AddPinnedURL(GURL("http://bbc.com"), 1);
+  top_sites().AddPinnedURL(themes_url(), 0);
+  top_sites().GetMostVisitedURLs(
+      &c,
+      NewCallback(static_cast<TopSitesTest*>(this),
+                  &TopSitesTest::OnTopSitesAvailable));
+
+  ASSERT_EQ(4u, urls().size());
+  EXPECT_EQ(themes_url(), urls()[0].url);
+  EXPECT_EQ("http://bbc.com/", urls()[1].url.spec());
+  EXPECT_EQ("http://google.com/", urls()[2].url.spec());
+  EXPECT_EQ(welcome_url(), urls()[3].url);
+
+  top_sites().RemovePinnedURL(GURL("http://bbc.com"));
+  top_sites().RemovePinnedURL(themes_url());
+
+  top_sites().AddPinnedURL(welcome_url(), 1);
+  top_sites().AddPinnedURL(GURL("http://bbc.com"), 3);
+
+  top_sites().GetMostVisitedURLs(
+      &c,
+      NewCallback(static_cast<TopSitesTest*>(this),
+                  &TopSitesTest::OnTopSitesAvailable));
+
+  ASSERT_EQ(4u, urls().size());
+  EXPECT_EQ("http://google.com/", urls()[0].url.spec());
+  EXPECT_EQ(welcome_url(), urls()[1].url);
+  EXPECT_EQ(themes_url(), urls()[2].url);
+  EXPECT_EQ("http://bbc.com/", urls()[3].url.spec());
 }
 
 TEST_F(TopSitesTest, BlacklistingAndPinnedURLs) {