[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 72733008c0f002c5f60635eeab19ebf028f4c220..8bb7f12cbb85d9caa13bcd5d228cbe4d6871fa9e 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,8 +132,142 @@ std::string GetPopularSitesFilename() {
                                             "filename");
 }
 
+void GetPreviousNTPSites(const PrefService* prefs,
+                         size_t num_tiles,
+                         std::vector<std::string>* old_sites_url,
+                         std::vector<bool>* old_sites_source) {
+  const base::ListValue* url_list = prefs->GetList(prefs::kNTPSuggestionsURL);
+  std::string url_string;
+  if (url_list->GetSize() < num_tiles)
+    num_tiles = url_list->GetSize();
+  if (num_tiles == 0) {
+    // No fallback required as Personal suggestions take precedence anyway.
+    return;
+  }
+  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->push_back(url_string);
+    }
+  }
+  old_sites_source->reserve(num_tiles);
+  const base::ListValue* source_list =
+      prefs->GetList(prefs::kNTPSuggestionsIsPersonal);
+  bool is_personal;
+  DCHECK_EQ(num_tiles, source_list->GetSize());
+  for (size_t i = 0; i < num_tiles; ++i) {
+    if (source_list->GetBoolean(i, &is_personal)) {
+      old_sites_source->push_back(is_personal);
+    }
+  }
+  DCHECK_EQ(num_tiles, old_sites_source->size());
+}
+
+void SaveCurrentNTPSites(
+    const ScopedVector<MostVisitedSites::Suggestion>& suggestions,
+    PrefService* prefs) {
+  base::ListValue url_list;
+  base::ListValue source_list;
+  for (const auto suggestion : suggestions) {
+    url_list.AppendString(suggestion->url);
+    source_list.AppendBoolean(suggestion->source != MostVisitedSites::POPULAR);
+  }
+  prefs->Set(prefs::kNTPSuggestionsIsPersonal, source_list);
+  prefs->Set(prefs::kNTPSuggestionsURL, url_list);
+}
+
+std::vector<size_t> InsertMatchingSuggestions(

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

Please add a comment explaining what this function does, in particular how it
modifies its inputs (see also below about src_suggestions), and what it returns.

[knn, 2015/09/08 13:42:00]

Done.

+    ScopedVector<MostVisitedSites::Suggestion>* src_suggestions,
+    ScopedVector<MostVisitedSites::Suggestion>* dst_suggestions,
+    const std::vector<std::string> match_urls,
+    const std::vector<std::string> match_hosts) {
+  std::vector<size_t> unmatched_suggestions;
+  size_t num_src_suggestions = src_suggestions->size();
+  size_t num_matchers = match_urls.size();
+  for (size_t i = 0; i < num_src_suggestions; ++i) {
+    size_t position;
+    for (position = 0; position < num_matchers; ++position) {
+      if ((*dst_suggestions)[position] != nullptr)
+        continue;
+      if (match_urls[position] == (*src_suggestions)[i]->url)
+        break;
+      // match_hosts is only populated for suggestions which can be replaced by
+      // host matching like popular suggestions.
+      if (match_hosts[position] == (*src_suggestions)[i]->host)
+        break;
+    }
+    if (position == num_matchers) {
+      unmatched_suggestions.push_back(i);
+    } else {
+      std::swap((*dst_suggestions)[position], (*src_suggestions)[i]);

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

This is the only reason why src_suggestions can't be const, right? But as far as
I can tell, the caller actually doesn't care if src_suggestions is modified like
this, is that correct? If so, please make src_suggestions const, and copy
elements over instead of swapping. It's not gonna be any less efficient, and a
lot more readable. (At least to me, functions that destroy their input are much
harder to understand!)

[knn, 2015/09/08 11:53:52]

We need to do a swap as ScopedVector owns the member pointers, and I don't want
to copy structs around (Hence ScopedVector).
I'll add a lot of comments if that helps?

[Marc Treib, 2015/09/08 12:07:57]

Hm. TBH I'd prefer just copying the structs (readability over performance,
unless performance actually turns out to be problematic). But since Bernhard
explicitly suggested ScopedVectors... oh well.
Can you at least null out the corresponding entry in src_suggestions after the
swap? (Maybe make a MoveElement helper function.) I think that'd make things a
bit less confusing for me. (Would it also allow you to get rid of the
vector<size_t>?)

+    }
+  }
+  return unmatched_suggestions;
+}
+
+size_t InsertAllSuggestions(
+    size_t start_position,
+    const std::vector<size_t>& insert_positions,
+    ScopedVector<MostVisitedSites::Suggestion>* src_suggestions,

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

Same here: Please make const if possible.

+    ScopedVector<MostVisitedSites::Suggestion>* dst_suggestions) {
+  size_t num_inserts = insert_positions.size();
+  size_t num_dests = dst_suggestions->size();
+
+  size_t src_pos = 0;
+  size_t i = start_position;
+  for (; i < num_dests && src_pos < num_inserts; ++i) {
+    if ((*dst_suggestions)[i] != nullptr)
+      continue;
+    size_t src = insert_positions[src_pos++];
+    std::swap((*dst_suggestions)[i], (*src_suggestions)[src]);
+  }
+  // Return destination postions filled so far which becomes the start_position
+  // for future runs.
+  return i;
+}
+
 }  // namespace
 
+MostVisitedSites::Suggestion::Suggestion(base::string16 title,
+                                         std::string url,
+                                         MostVisitedSource source)
+    : title(title),
+      url(url),
+      host(GURL(url).host()),
+      source(source),
+      provider_index(-1) {}
+
+MostVisitedSites::Suggestion::Suggestion(base::string16 title,
+                                         std::string url,
+                                         std::string host,
+                                         MostVisitedSource source)
+    : title(title), url(url), host(host), source(source), provider_index(-1) {}
+
+MostVisitedSites::Suggestion::Suggestion(base::string16 title,
+                                         std::string url,
+                                         MostVisitedSource source,
+                                         int provider_index)
+    : title(title),
+      url(url),
+      host(GURL(url).host()),
+      source(source),
+      provider_index(provider_index) {}
+
+std::string MostVisitedSites::Suggestion::GetSourceString() {
+  switch (source) {
+    case MostVisitedSites::TOP_SITES:
+      return kHistogramClientName;

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

Maybe rename these constants, since they're now used for more than just
histograms?

[knn, 2015/09/08 11:53:52]

They are still used only in Histograms, I'll rename the function.

+    case MostVisitedSites::POPULAR:
+      return kHistogramPopularName;
+    case MostVisitedSites::SUGGESTIONS_SERVICE:
+      return provider_index >= 0
+                 ? base::StringPrintf(kHistogramServerFormat, provider_index)
+                 : kHistogramServerName;
+  }
+  NOTREACHED();
+  return std::string();
+}
+
 MostVisitedSites::MostVisitedSites(Profile* profile)
     : profile_(profile), num_sites_(0), received_most_visited_sites_(false),
       received_popular_sites_(false), recorded_uma_(false),
@@ -291,9 +428,10 @@ void MostVisitedSites::RecordOpenedMostVisitedItem(JNIEnv* env,
                                                    jobject obj,
                                                    jint index) {
   DCHECK_GE(index, 0);
-  DCHECK_LT(index, static_cast<int>(tile_sources_.size()));
-  std::string histogram = base::StringPrintf(kOpenedItemHistogramFormat,
-                                             tile_sources_[index].c_str());
+  DCHECK_LT(index, static_cast<int>(current_suggestions_.size()));
+  std::string histogram = base::StringPrintf(
+      kOpenedItemHistogramFormat,
+      current_suggestions_[index]->GetSourceString().c_str());
   LogHistogramEvent(histogram, index, num_sites_);
 }
 
@@ -309,6 +447,13 @@ bool MostVisitedSites::Register(JNIEnv* env) {
   return RegisterNativesImpl(env);
 }
 
+// static
+void MostVisitedSites::RegisterProfilePrefs(
+    user_prefs::PrefRegistrySyncable* registry) {
+  registry->RegisterListPref(prefs::kNTPSuggestionsURL);
+  registry->RegisterListPref(prefs::kNTPSuggestionsIsPersonal);
+}
+
 void MostVisitedSites::QueryMostVisitedURLs() {
   SuggestionsService* suggestions_service =
       SuggestionsServiceFactory::GetForProfile(profile_);
@@ -336,25 +481,23 @@ void MostVisitedSites::InitiateTopSitesQuery() {
 
 void MostVisitedSites::OnMostVisitedURLsAvailable(
     const history::MostVisitedURLList& visited_list) {
-  std::vector<base::string16> titles;
-  std::vector<std::string> urls;
-  tile_sources_.clear();
-  int num_tiles = std::min(static_cast<int>(visited_list.size()), num_sites_);
-  for (int i = 0; i < num_tiles; ++i) {
+  ScopedVector<Suggestion> suggestions;
+  size_t num_tiles =
+      std::min(visited_list.size(), static_cast<size_t>(num_sites_));
+  for (size_t i = 0; i < num_tiles; ++i) {
     const history::MostVisitedURL& visited = visited_list[i];
     if (visited.url.is_empty()) {
       num_tiles = i;
       break;  // This is the signal that there are no more real visited sites.
     }
-    titles.push_back(visited.title);
-    urls.push_back(visited.url.spec());
-    tile_sources_.push_back(kHistogramClientName);
+    suggestions.push_back(
+        new Suggestion(visited.title, visited.url.spec(), TOP_SITES));
   }
 
   received_most_visited_sites_ = true;
   mv_source_ = TOP_SITES;
-  AddPopularSites(&titles, &urls);
-  NotifyMostVisitedURLsObserver(titles, urls);
+  AddPopularSites(&suggestions);
+  NotifyMostVisitedURLsObserver(&suggestions);
 }
 
 void MostVisitedSites::OnSuggestionsProfileAvailable(
@@ -368,150 +511,126 @@ void MostVisitedSites::OnSuggestionsProfileAvailable(
   if (num_sites_ < num_tiles)
     num_tiles = num_sites_;
 
-  std::vector<base::string16> titles;
-  std::vector<std::string> urls;
-  tile_sources_.clear();
+  ScopedVector<Suggestion> suggestions;
   for (int i = 0; i < num_tiles; ++i) {
     const ChromeSuggestion& suggestion = suggestions_profile.suggestions(i);
-    titles.push_back(base::UTF8ToUTF16(suggestion.title()));
-    urls.push_back(suggestion.url());
-    std::string tile_source;
-    if (suggestion.providers_size() > 0) {
-      tile_source =
-          base::StringPrintf(kHistogramServerFormat, suggestion.providers(0));
-    } else {
-      tile_source = kHistogramServerName;
-    }
-    tile_sources_.push_back(tile_source);
+    suggestions.push_back(new Suggestion(
+        base::UTF8ToUTF16(suggestion.title()), suggestion.url(),
+        SUGGESTIONS_SERVICE,
+        suggestion.providers_size() > 0 ? suggestion.providers(0) : -1));
   }
 
   received_most_visited_sites_ = true;
   mv_source_ = SUGGESTIONS_SERVICE;
-  AddPopularSites(&titles, &urls);
-  NotifyMostVisitedURLsObserver(titles, urls);
+  AddPopularSites(&suggestions);
+  NotifyMostVisitedURLsObserver(&suggestions);
 }
 
-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(ScopedVector<Suggestion>* suggestions) {
+  size_t num_personal_suggestions = suggestions->size();
+  DCHECK_LE(num_personal_suggestions, static_cast<size_t>(num_sites_));
 
-  // Collect all non-blacklisted popular suggestions.
-  std::vector<base::string16> popular_titles;
-  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_titles.push_back(popular_site.title);
-    popular_urls.push_back(popular_site.url.spec());
-    if (static_cast<int>(popular_titles.size()) >= num_sites_)
-      break;
-  }
+  // Collect non-blacklisted popular suggestions, skipping those already present
+  // in the personal suggestions.
+  size_t num_popular_suggestions = num_sites_ - num_personal_suggestions;
+  ScopedVector<Suggestion> popular_suggestions;
+  popular_suggestions.reserve(num_popular_suggestions);
 
-  AddPopularSitesImpl(
-      num_sites_, popular_titles, popular_urls, titles, urls, &tile_sources_);
-}
-
-// 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;
+  if (num_popular_suggestions > 0 && popular_sites_) {
+    std::set<std::string> personal_hosts;
+    for (const auto& suggestion : *suggestions)
+      personal_hosts.insert(suggestion->host);
+    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;
+      std::string host = popular_site.url.host();
+      // Skip suggestions already present in personal.
+      if (personal_hosts.find(host) != personal_hosts.end())
+        continue;
+
+      popular_suggestions.push_back(new Suggestion(
+          popular_site.title, popular_site.url.spec(), host, POPULAR));
+      if (popular_suggestions.size() >= num_popular_suggestions)
         break;
-      }
-    }
-    if (!found) {
-      titles_to_insert.push_back(title);
-      urls_to_insert.push_back(url);
-      tile_sources_to_insert.push_back(tile_source);
     }
   }
+  num_popular_suggestions = popular_suggestions.size();
+  size_t num_actual_tiles = num_personal_suggestions + num_popular_suggestions;
+  std::vector<std::string> old_sites_url;
+  std::vector<bool> old_sites_is_personal;
+  GetPreviousNTPSites(profile_->GetPrefs(), num_actual_tiles, &old_sites_url,
+                      &old_sites_is_personal);
+  ScopedVector<Suggestion> merged_suggestions;
+  MergeSuggestions(suggestions, &popular_suggestions, old_sites_url,
+                   old_sites_is_personal, &merged_suggestions);
+  DCHECK_EQ(num_actual_tiles, merged_suggestions.size());
+  SaveCurrentNTPSites(merged_suggestions, profile_->GetPrefs());
+  suggestions->swap(merged_suggestions);
+}
 
-  // 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;
-        break;
-      }
-    }
+// static
+void MostVisitedSites::MergeSuggestions(

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

Let this just return the result, rather than passing it out through a pointer
param?

[knn, 2015/09/08 13:42:00]

ScopedVector is move only. But actually there is very little change either way
since the actual work is done in Insert{Matching/All}Suggestions using pointers.

[Marc Treib, 2015/09/08 13:56:55]

But it has a .Pass() method :)

[knn, 2015/09/08 14:17:32]

My bad missed that.

+    ScopedVector<Suggestion>* personal_suggestions,
+    ScopedVector<Suggestion>* popular_suggestions,

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

If InsertMatchingSuggestions and InsertAllSuggestions above take const inputs,
then these can also be const& instead of * :)

+    const std::vector<std::string>& old_sites_url,
+    const std::vector<bool>& old_sites_is_personal,
+    // Return value.
+    ScopedVector<Suggestion>* merged_suggestions) {
+  size_t num_personal_suggestions = personal_suggestions->size();
+  size_t num_popular_suggestions = popular_suggestions->size();
+  size_t num_tiles = num_popular_suggestions + num_personal_suggestions;
+  merged_suggestions->resize(num_tiles);
+
+  size_t num_old_tiles = old_sites_url.size();
+  DCHECK_LE(num_old_tiles, num_tiles);
+  DCHECK_EQ(num_old_tiles, old_sites_is_personal.size());
+  std::vector<std::string> old_sites_host;
+  old_sites_host.reserve(num_old_tiles);
+  // Only populate the hosts for popular suggestions as only they can be
+  // replaced by host. Personal suggestions require an exact url match to be
+  // replaced.
+  for (size_t i = 0; i < num_old_tiles; ++i) {
+    old_sites_host.push_back(old_sites_is_personal[i]
+                                 ? std::string()
+                                 : GURL(old_sites_url[i]).host());
   }
 
-  titles->swap(new_titles);
-  urls->swap(new_urls);
-  tile_sources->swap(new_tile_sources);
+  // Insert personal suggestions if they existed previously.
+  std::vector<size_t> new_personal_suggestions = InsertMatchingSuggestions(
+      personal_suggestions, merged_suggestions, old_sites_url, old_sites_host);
+  // Insert popular suggestions if they existed previously.
+  std::vector<size_t> new_popular_suggestions = InsertMatchingSuggestions(
+      popular_suggestions, merged_suggestions, old_sites_url, old_sites_host);
+  // Insert leftover personal suggestions.
+  size_t filled_so_far = InsertAllSuggestions(
+      0, new_personal_suggestions, personal_suggestions, merged_suggestions);
+  // Insert leftover popular suggestions.
+  InsertAllSuggestions(filled_so_far, new_popular_suggestions,
+                       popular_suggestions, merged_suggestions);
 }
 
 void MostVisitedSites::NotifyMostVisitedURLsObserver(
-    const std::vector<base::string16>& titles,
-    const std::vector<std::string>& urls) {
-  DCHECK_EQ(titles.size(), urls.size());
+    ScopedVector<Suggestion>* suggestions) {
+  current_suggestions_.swap(*suggestions);

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

This is unexpected - I wouldn't expect a Notify method to change member state.
In fact, can all the (non-static) methods operate directly on
current_suggestions_, and pass one less ScopedVector around?

[knn, 2015/09/08 13:42:00]

Done.

+  size_t num_suggestions = current_suggestions_.size();
   if (received_most_visited_sites_ && received_popular_sites_ &&
       !recorded_uma_) {
     RecordImpressionUMAMetrics();
-    UMA_HISTOGRAM_SPARSE_SLOWLY(kNumTilesHistogramName, titles.size());
+    UMA_HISTOGRAM_SPARSE_SLOWLY(kNumTilesHistogramName, num_suggestions);
     recorded_uma_ = true;
   }
+  std::vector<base::string16> titles;
+  std::vector<std::string> urls;
+  titles.reserve(num_suggestions);
+  urls.reserve(num_suggestions);
+  for (const auto suggestion : current_suggestions_) {
+    titles.push_back(suggestion->title);
+    urls.push_back(suggestion->url);
+  }
   JNIEnv* env = AttachCurrentThread();
+  DCHECK_EQ(titles.size(), urls.size());
   Java_MostVisitedURLsObserver_onMostVisitedURLsAvailable(
       env, observer_.obj(), ToJavaArrayOfStrings(env, titles).obj(),
       ToJavaArrayOfStrings(env, urls).obj());
@@ -553,9 +672,10 @@ void MostVisitedSites::RecordThumbnailUMAMetrics() {
 }
 
 void MostVisitedSites::RecordImpressionUMAMetrics() {
-  for (size_t i = 0; i < tile_sources_.size(); i++) {
-    std::string histogram = base::StringPrintf(kImpressionHistogramFormat,
-                                               tile_sources_[i].c_str());
+  for (size_t i = 0; i < current_suggestions_.size(); i++) {
+    std::string histogram =
+        base::StringPrintf(kImpressionHistogramFormat,
+                           current_suggestions_[i]->GetSourceString().c_str());
     LogHistogramEvent(histogram, static_cast<int>(i), num_sites_);
   }
 }