[Android] Persist ordering of NTP suggestions.

chrome/browser/android/most_visited_sites.cc

Index: chrome/browser/android/most_visited_sites.cc
diff --git a/chrome/browser/android/most_visited_sites.cc b/chrome/browser/android/most_visited_sites.cc
index 6c82bb37490e409e41c46c32c966f9b2640be105..1bae03b4aed1f1dca71e427af7f10e70dddf228b 100644
--- a/chrome/browser/android/most_visited_sites.cc
+++ b/chrome/browser/android/most_visited_sites.cc
@@ -12,6 +12,7 @@
 #include "base/command_line.h"
 #include "base/metrics/histogram.h"
 #include "base/metrics/sparse_histogram.h"
+#include "base/prefs/pref_service.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/stringprintf.h"
 #include "base/strings/utf_string_conversions.h"
@@ -26,7 +27,9 @@
 #include "chrome/browser/sync/profile_sync_service_factory.h"
 #include "chrome/browser/thumbnails/thumbnail_list_source.h"
 #include "chrome/common/chrome_switches.h"
+#include "chrome/common/pref_names.h"
 #include "components/history/core/browser/top_sites.h"
+#include "components/pref_registry/pref_registry_syncable.h"
 #include "components/suggestions/suggestions_service.h"
 #include "components/suggestions/suggestions_utils.h"
 #include "content/public/browser/browser_thread.h"
@@ -129,6 +132,52 @@ std::string GetPopularSitesFilename() {
                                             "filename");
 }
 
+void GetPreviousNTPSites(std::vector<std::string>* old_sites_url,

[Marc Treib, 2015/09/07 11:12:59]

nit: Inputs first, then outputs.

[knn, 2015/09/08 10:48:55]

Done.

+                         std::vector<bool>* old_sites_source,
+                         const PrefService* prefs,
+                         size_t num_tiles,
+                         const std::vector<std::string>& personal_urls) {
+  const base::ListValue* url_list = prefs->GetList(prefs::kNTPSuggestionsURL);
+  std::string url_string;
+  DCHECK_LE(personal_urls.size(), num_tiles);
+  if (url_list->GetSize() < num_tiles)
+    num_tiles = url_list->GetSize();
+  old_sites_url->reserve(num_tiles);
+  for (size_t i = 0; i < num_tiles; ++i) {
+    if (url_list->GetString(i, &url_string)) {
+      old_sites_url->emplace_back(url_string);

[Marc Treib, 2015/09/07 11:12:59]

push_back - no C++11 library yet. It'll do the same thing here anyway.

[knn, 2015/09/08 10:48:55]

Done.

+    }
+  }
+  if (num_tiles == 0) {

[Marc Treib, 2015/09/07 11:12:59]

Move this above the loop.

[knn, 2015/09/08 10:48:55]

Done.

+    // No fallback required as Personal suggestions take precedence anyway.
+    return;
+  }
+  old_sites_source->reserve(num_tiles);
+  const base::ListValue* host_list =
+      prefs->GetList(prefs::kNTPSuggestionsSource);
+  bool is_personal;
+  DCHECK_EQ(num_tiles, host_list->GetSize());
+  for (size_t i = 0; i < num_tiles; ++i) {
+    if (host_list->GetBoolean(i, &is_personal)) {
+      old_sites_source->push_back(is_personal);
+    }
+  }
+  DCHECK_EQ(num_tiles, old_sites_source->size());
+}
+
+void SaveCurrentNTPSites(const std::vector<std::string>& urls,
+                         const std::vector<bool>& sources,
+                         PrefService* prefs) {
+  base::ListValue url_list;
+  url_list.AppendStrings(urls);
+  prefs->Set(prefs::kNTPSuggestionsURL, url_list);
+
+  base::ListValue source_list;
+  for (const bool& source : sources)
+    source_list.AppendBoolean(source);
+  prefs->Set(prefs::kNTPSuggestionsSource, source_list);
+}
+
 }  // namespace
 
 MostVisitedSites::MostVisitedSites(Profile* profile)
@@ -309,6 +358,13 @@ bool MostVisitedSites::Register(JNIEnv* env) {
   return RegisterNativesImpl(env);
 }
 
+// static
+void MostVisitedSites::RegisterProfilePrefs(
+    user_prefs::PrefRegistrySyncable* registry) {
+  registry->RegisterListPref(prefs::kNTPSuggestionsURL);
+  registry->RegisterListPref(prefs::kNTPSuggestionsSource);
+}
+
 void MostVisitedSites::QueryMostVisitedURLs() {
   SuggestionsService* suggestions_service =
       SuggestionsServiceFactory::GetForProfile(profile_);
@@ -353,8 +409,10 @@ void MostVisitedSites::OnMostVisitedURLsAvailable(
 
   received_most_visited_sites_ = true;
   mv_source_ = TOP_SITES;
-  AddPopularSites(&titles, &urls);
-  NotifyMostVisitedURLsObserver(titles, urls);
+  std::vector<base::string16> ordered_titles;
+  std::vector<std::string> ordered_urls;
+  AddPopularSites(&ordered_titles, &ordered_urls, &titles, &urls);
+  NotifyMostVisitedURLsObserver(ordered_titles, ordered_urls);
 }
 
 void MostVisitedSites::OnSuggestionsProfileAvailable(
@@ -387,118 +445,175 @@ void MostVisitedSites::OnSuggestionsProfileAvailable(
 
   received_most_visited_sites_ = true;
   mv_source_ = SUGGESTIONS_SERVICE;
-  AddPopularSites(&titles, &urls);
-  NotifyMostVisitedURLsObserver(titles, urls);
+  std::vector<base::string16> ordered_titles;
+  std::vector<std::string> ordered_urls;
+  AddPopularSites(&ordered_titles, &ordered_urls, &titles, &urls);
+  NotifyMostVisitedURLsObserver(ordered_titles, ordered_urls);
 }
 
-void MostVisitedSites::AddPopularSites(std::vector<base::string16>* titles,
-                                       std::vector<std::string>* urls) {
-  if (!popular_sites_)
-    return;
-
-  DCHECK_EQ(titles->size(), urls->size());
-  DCHECK_EQ(titles->size(), tile_sources_.size());
-  DCHECK_LE(static_cast<int>(titles->size()), num_sites_);
+void MostVisitedSites::AddPopularSites(

[Marc Treib, 2015/09/07 11:12:59]

Any reason why this doesn't just update |titles| and |urls| in-place anymore?
Would save the caller from having to create two extra vectors.

[knn, 2015/09/08 10:48:56]

Did you mean inplace? I did not want to complicate the logic too much.

[Marc Treib, 2015/09/08 11:39:49]

I just meant that the caller shouldn't have to pass in extra vectors, but you've
changed that anyway in the latest PS :)

+    std::vector<base::string16>* result_titles,
+    std::vector<std::string>* result_urls,
+    std::vector<base::string16>* personal_titles,
+    std::vector<std::string>* personal_urls) {
+  size_t num_personal_suggestions = personal_titles->size();
+  DCHECK_EQ(num_personal_suggestions, personal_urls->size());
+  DCHECK_EQ(num_personal_suggestions, tile_sources_.size());
+  DCHECK_LE(num_personal_suggestions, static_cast<size_t>(num_sites_));
+  std::vector<std::string> personal_hosts;

[Marc Treib, 2015/09/07 11:12:59]

Make this an std::set? Would make checking membership later more convenient.

[knn, 2015/09/08 10:48:55]

Done.

+  for (const std::string& personal_url : *personal_urls) {
+    personal_hosts.emplace_back(GURL(personal_url).host());
+  }
 
-  // Collect all non-blacklisted popular suggestions.
+  // Collect non-blacklisted popular suggestions removing duplicates from

[Marc Treib, 2015/09/07 11:12:59]

nit: You're not removing anything from personal suggestions.
"Collect non-blacklisted popular suggestions, skipping those already present in
the personal suggestions" ?

[knn, 2015/09/08 10:48:55]

Done.

+  // personal suggestions.
+  size_t num_popular_suggestions = num_sites_ - num_personal_suggestions;
   std::vector<base::string16> popular_titles;
+  popular_titles.reserve(num_popular_suggestions);
   std::vector<std::string> popular_urls;
-  scoped_refptr<TopSites> top_sites(TopSitesFactory::GetForProfile(profile_));
-  for (const PopularSites::Site& popular_site : popular_sites_->sites()) {
-    // Skip blacklisted sites.
-    if (top_sites && top_sites->IsBlacklisted(popular_site.url))
-      continue;
+  popular_urls.reserve(num_popular_suggestions);
+  std::vector<std::string> popular_hosts;
+  popular_hosts.reserve(num_popular_suggestions);
 
-    popular_titles.push_back(popular_site.title);
-    popular_urls.push_back(popular_site.url.spec());
-    if (static_cast<int>(popular_titles.size()) >= num_sites_)
-      break;
-  }
+  if (num_popular_suggestions > 0 && popular_sites_) {
+    scoped_refptr<TopSites> top_sites(TopSitesFactory::GetForProfile(profile_));
+    for (const PopularSites::Site& popular_site : popular_sites_->sites()) {
+      if (popular_titles.size() >= num_popular_suggestions)

[Marc Treib, 2015/09/07 11:12:59]

Put this at the end, right after you've added one?

[knn, 2015/09/08 10:48:55]

Done.

+        break;
+      // Skip blacklisted sites.
+      if (top_sites && top_sites->IsBlacklisted(popular_site.url))
+        continue;
+      std::string host = popular_site.url.host();
+      // Skip suggestions already present in personal.
+      if (std::find(personal_hosts.begin(), personal_hosts.end(), host) !=
+          personal_hosts.end()) {
+        continue;
+      }
 
-  AddPopularSitesImpl(
-      num_sites_, popular_titles, popular_urls, titles, urls, &tile_sources_);
+      popular_titles.push_back(popular_site.title);
+      popular_urls.push_back(popular_site.url.spec());
+      popular_hosts.emplace_back(host);

[Marc Treib, 2015/09/07 11:12:59]

push_back

[knn, 2015/09/08 10:48:55]

Done.

+    }
+  }
+  num_popular_suggestions = popular_titles.size();
+  size_t num_actual_tiles = num_personal_suggestions + num_popular_suggestions;
+  std::vector<std::string> old_sites_url;
+  std::vector<bool> old_sites_source;
+  GetPreviousNTPSites(&old_sites_url, &old_sites_source, profile_->GetPrefs(),
+                      num_actual_tiles, *personal_urls);
+  std::vector<bool> result_is_personal;
+  MergeSuggestions(&result_is_personal, result_urls, result_titles,
+                   num_actual_tiles, num_personal_suggestions,
+                   num_popular_suggestions, personal_urls, personal_titles,
+                   &popular_urls, &popular_titles, personal_hosts,
+                   popular_hosts, old_sites_url, old_sites_source);
+  DCHECK_EQ(num_actual_tiles, result_urls->size());
+  DCHECK_EQ(num_actual_tiles, result_titles->size());
+  DCHECK_EQ(num_actual_tiles, result_is_personal.size());
+  SaveCurrentNTPSites(*result_urls, result_is_personal, profile_->GetPrefs());
 }
 
 // static
-void MostVisitedSites::AddPopularSitesImpl(
-    int num_sites,
-    const std::vector<base::string16>& popular_titles,
-    const std::vector<std::string>& popular_urls,
-    std::vector<base::string16>* titles,
-    std::vector<std::string>* urls,
-    std::vector<std::string>* tile_sources) {
-  // Start off with the popular suggestions.
-  std::vector<base::string16> new_titles(popular_titles);
-  std::vector<std::string> new_urls(popular_urls);
-  std::vector<std::string> new_tile_sources(new_titles.size(),
-                                            kHistogramPopularName);
-
-  // Now, go over the personalized suggestions and replace matching popular
-  // suggestions. This is so that when some of the popular suggestions become
-  // personal, they retain their absolute positions.
-  std::vector<base::string16> titles_to_insert;
-  std::vector<std::string> urls_to_insert;
-  std::vector<std::string> tile_sources_to_insert;
-  for (size_t site_index = 0; site_index < titles->size(); site_index++) {
-    const base::string16& title = (*titles)[site_index];
-    const std::string& url = (*urls)[site_index];
-    const std::string& tile_source = (*tile_sources)[site_index];
-    // See if we already have a matching popular site.
-    bool found = false;
-    for (size_t i = 0; i < new_urls.size(); i++) {
-      if (new_tile_sources[i] == kHistogramPopularName &&
-          GURL(new_urls[i]).host() == GURL(url).host()) {
-        // We have a matching popular sites suggestion. Replace it with the
-        // actual URL and title.
-        new_titles[i] = title;
-        new_urls[i] = url;
-        new_tile_sources[i] = tile_source;
-        found = true;
+void MostVisitedSites::MergeSuggestions(
+    // Return values.
+    std::vector<bool>* result_is_personal,
+    std::vector<std::string>* result_urls,
+    std::vector<base::string16>* result_titles,
+    // Arguments.
+    size_t num_tiles,
+    size_t num_personal_suggestions,
+    size_t num_popular_suggestions,
+    // Passed as ptr for move semantics only.
+    std::vector<std::string>* personal_urls,
+    std::vector<base::string16>* personal_titles,
+    std::vector<std::string>* popular_urls,
+    std::vector<base::string16>* popular_titles,
+    const std::vector<std::string>& personal_hosts,
+    const std::vector<std::string>& popular_hosts,
+    const std::vector<std::string>& old_sites_url,
+    const std::vector<bool>& old_sites_source) {
+  // Initialize return values.
+  result_is_personal->resize(num_tiles, false);
+  result_urls->resize(num_tiles);
+  result_titles->resize(num_tiles);
+
+  std::vector<bool> result_is_filled(num_tiles, false);
+  size_t num_old_tiles = old_sites_url.size();
+  DCHECK_LE(num_old_tiles, num_tiles);

[Marc Treib, 2015/09/07 11:12:59]

I don't think this is necessarily always true?

[knn, 2015/09/08 10:48:56]

It is because GetPreviousNTPSites ensures that.

+  std::vector<std::string> old_sites_host;
+  old_sites_host.reserve(num_old_tiles);
+  for (size_t i = 0; i < num_old_tiles; ++i) {
+    old_sites_host.emplace_back(
+        old_sites_source[i] ? std::string() : GURL(old_sites_url[i]).host());
+  }
+
+  std::vector<size_t> personal_suggestions_to_insert;
+  // Insert personal suggestions if they existed previously.
+  for (size_t i = 0; i < num_personal_suggestions; ++i) {
+    size_t position;
+    for (position = 0; position < num_old_tiles; ++position) {
+      if (result_is_filled[position])
+        continue;
+      if (old_sites_url[position] == (*personal_urls)[i])
+        break;
+      if (old_sites_host[position] == personal_hosts[i])

[Marc Treib, 2015/09/07 11:12:59]

I think here you also need to check that the old suggestions was a popular one?
There can be multiple personal suggestions with the same host.

[knn, 2015/09/08 10:48:55]

I do that by only populating the host field for popular suggestions. I explained
this while populating the field, now I have duplicated the comment to be more
clear.

[Marc Treib, 2015/09/08 11:39:49]

Acknowledged.

         break;
-      }
     }
-    if (!found) {
-      titles_to_insert.push_back(title);
-      urls_to_insert.push_back(url);
-      tile_sources_to_insert.push_back(tile_source);
+    if (position == num_old_tiles) {
+      personal_suggestions_to_insert.push_back(i);
+    } else {
+      (*result_urls)[position] = std::move((*personal_urls)[i]);

[Marc Treib, 2015/09/07 11:12:59]

We're not allowed to use C++11 library features yet, so no std::move. On the
upside, that also means the inputs can be const& instead of * :)

[knn, 2015/09/08 10:48:55]

Done.

+      (*result_titles)[position] = std::move((*personal_titles)[i]);
+      (*result_is_personal)[position] = true;
+      result_is_filled[position] = true;
     }
   }
 
-  // Append personalized suggestions at the end if there's room.
-  size_t num_to_append =
-      std::min(static_cast<size_t>(num_sites) - new_titles.size(),
-               titles_to_insert.size());
-  new_titles.insert(new_titles.end(),
-                    titles_to_insert.end() - num_to_append,
-                    titles_to_insert.end());
-  new_urls.insert(new_urls.end(),
-                  urls_to_insert.end() - num_to_append,
-                  urls_to_insert.end());
-  new_tile_sources.insert(new_tile_sources.end(),
-                          tile_sources_to_insert.end() - num_to_append,
-                          tile_sources_to_insert.end());
-
-  // Finally, go over the remaining personalized suggestions and evict popular
-  // suggestions to accommodate them. Do it in reverse order, so the least
-  // important popular suggestions will be evicted.
-  for (size_t i = titles_to_insert.size() - num_to_append; i > 0; --i) {
-    const base::string16& title = titles_to_insert[i - 1];
-    const std::string& url = urls_to_insert[i - 1];
-    const std::string& tile_source = tile_sources_to_insert[i - 1];
-    for (size_t insert_i = new_titles.size(); insert_i > 0; --insert_i) {
-      size_t insert_index = insert_i - 1;
-      if (new_tile_sources[insert_index] == kHistogramPopularName) {
-        new_titles[insert_index] = title;
-        new_urls[insert_index] = url;
-        new_tile_sources[insert_index] = tile_source;
+  std::vector<size_t> popular_suggestions_to_insert;
+  // Insert popular suggestions if they existed previously.
+  for (size_t i = 0; i < num_popular_suggestions; ++i) {
+    size_t position;
+    for (position = 0; position < num_old_tiles; ++position) {
+      if (result_is_filled[position])
+        continue;
+      if (old_sites_host[position] == popular_hosts[i])
         break;
-      }
+    }
+    if (position == num_old_tiles) {
+      popular_suggestions_to_insert.push_back(i);
+    } else {
+      (*result_urls)[position] = std::move((*popular_urls)[i]);

[Marc Treib, 2015/09/07 11:12:59]

^^

+      (*result_titles)[position] = std::move((*popular_titles)[i]);
+      result_is_filled[position] = true;
     }
   }
 
-  titles->swap(new_titles);
-  urls->swap(new_urls);
-  tile_sources->swap(new_tile_sources);
+  // Insert leftover personal suggestions.
+  size_t insert_position = 0;
+  size_t insert_size = personal_suggestions_to_insert.size();
+  for (/*insert_position continued*/ size_t i = 0;
+       insert_position < num_tiles && i < insert_size; ++insert_position) {
+    if (result_is_filled[insert_position])
+      continue;
+    size_t to_insert = personal_suggestions_to_insert[i++];
+    (*result_urls)[insert_position] = std::move((*personal_urls)[to_insert]);
+    (*result_titles)[insert_position] =
+        std::move((*personal_titles)[to_insert]);
+    (*result_is_personal)[insert_position] = true;
+    // Ignore setting result_is_filled as it is isn't used anymore.

[Marc Treib, 2015/09/07 11:12:59]

s/Ignore/Skip/g

+  }
+
+  // Insert leftover popular suggestions.
+  insert_size = popular_suggestions_to_insert.size();
+  for (/*insert_position continued*/ size_t i = 0;
+       insert_position < num_tiles && i < insert_size; ++insert_position) {
+    if (result_is_filled[insert_position])
+      continue;
+    size_t to_insert = popular_suggestions_to_insert[i++];
+    (*result_urls)[insert_position] = std::move((*popular_urls)[to_insert]);
+    (*result_titles)[insert_position] = std::move((*popular_titles)[to_insert]);
+    // Ignore setting result_is_filled as it is isn't used anymore.
+  }
 }
 
 void MostVisitedSites::NotifyMostVisitedURLsObserver(