Make prepopulated-TemplateURL-de-duper heuristic smarter. Instead of blindly preserving the first U…

chrome/browser/search_engines/util.cc

Index: chrome/browser/search_engines/util.cc
diff --git a/chrome/browser/search_engines/util.cc b/chrome/browser/search_engines/util.cc
index c68771a01c42a496213c053c61a8c14da710ffc3..e7ee99b6a3a0735b5aa9412bc726fc61928b3898 100644
--- a/chrome/browser/search_engines/util.cc
+++ b/chrome/browser/search_engines/util.cc
@@ -6,9 +6,11 @@
 
 #include <set>
 #include <string>
+#include <map>
 #include <vector>
 
 #include "base/logging.h"
+#include "base/memory/scoped_vector.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/browser/search_engines/template_url.h"
 #include "chrome/browser/search_engines/template_url_prepopulate_data.h"
@@ -35,49 +37,95 @@ string16 GetDefaultSearchEngineName(Profile* profile) {
   return default_provider->short_name();
 }
 
-// Removes (and deletes) TemplateURLs from |urls| that have duplicate
-// prepopulate ids. Duplicate prepopulate ids are not allowed, but due to a
-// bug it was possible get dups. This step is only called when the version
-// number changes. Only pass in a non-NULL value for |service| if the removed
-// items should be removed from the DB. If |removed_keyword_guids| is not NULL,
-// the Sync GUID of each item removed from the DB will be added to it.
-static void RemoveDuplicatePrepopulateIDs(
-    std::vector<TemplateURL*>* template_urls,
+void RemoveDuplicatePrepopulateIDs(
     WebDataService* service,
+    const ScopedVector<TemplateURL>& prepopulated_urls,
+    TemplateURL* default_search_provider,
+    TemplateURLService::TemplateURLVector* template_urls,
     std::set<std::string>* removed_keyword_guids) {
-  DCHECK(template_urls);
   DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
+  DCHECK(template_urls);
 
-  std::set<int> ids;
-  for (std::vector<TemplateURL*>::iterator i = template_urls->begin();
-       i != template_urls->end(); ) {
-    int prepopulate_id = (*i)->prepopulate_id();
-    if (prepopulate_id) {
-      if (ids.find(prepopulate_id) != ids.end()) {
-        if (service) {
-          service->RemoveKeyword((*i)->id());
-          if (removed_keyword_guids)
-            removed_keyword_guids->insert((*i)->sync_guid());
-        }
-        delete *i;
-        i = template_urls->erase(i);
-      } else {
-        ids.insert(prepopulate_id);
-        ++i;
+  // For convenience construct an ID->TemplateURL* map from |prepopulated_urls|.
+  typedef std::map<int, TemplateURL*> PrepopulatedURLMap;
+  PrepopulatedURLMap prepopulated_url_map;
+  for (std::vector<TemplateURL*>::const_iterator i(prepopulated_urls.begin());
+       i != prepopulated_urls.end(); ++i)
+    prepopulated_url_map[(*i)->prepopulate_id()] = *i;
+
+  // Separate |template_urls| into prepopulated and non-prepopulated groups.
+  typedef std::multimap<int, TemplateURL*> UncheckedURLMap;
+  UncheckedURLMap unchecked_urls;
+  TemplateURLService::TemplateURLVector checked_urls;
+  for (TemplateURLService::TemplateURLVector::iterator i(
+       template_urls->begin()); i != template_urls->end(); ++i) {
+    TemplateURL* turl = *i;
+    int prepopulate_id = turl->prepopulate_id();
+    if (prepopulate_id)
+      unchecked_urls.insert(std::make_pair(prepopulate_id, turl));
+    else
+      checked_urls.push_back(turl);
+  }
+
+  // For each group of prepopulated URLs with one ID, find the best URL to use
+  // and add it to the (initially all non-prepopulated) URLs we've already OKed.
+  // Delete the others from the service and from memory.
+  while (!unchecked_urls.empty()) {
+    // Find the best URL.
+    int prepopulate_id = unchecked_urls.begin()->first;
+    PrepopulatedURLMap::const_iterator prepopulated_url =
+        prepopulated_url_map.find(prepopulate_id);
+    UncheckedURLMap::iterator end = unchecked_urls.upper_bound(prepopulate_id);
+    UncheckedURLMap::iterator best = unchecked_urls.begin();
+    bool matched_keyword = false;
+    for (UncheckedURLMap::iterator i = unchecked_urls.begin(); i != end; ++i) {
+      // A URL is automatically the best if it's the default search engine.
+      if (i->second == default_search_provider) {
+        best = i;
+        break;
       }
-    } else {
-      ++i;
+
+      // Otherwise, a URL is best if it matches the prepopulated data's keyword;
+      // if none match, just fall back to using the one with the lowest ID.
+      if (matched_keyword)
+        continue;
+      if ((prepopulated_url != prepopulated_url_map.end()) &&
+           i->second->HasSameKeywordAs(*prepopulated_url->second)) {
+        best = i;
+        matched_keyword = true;
+      } else if (i->second->id() < best->second->id()) {
+        best = i;
+      }
+    }
+
+    // Add the best URL to the checked group and delete the rest.
+    checked_urls.push_back(best->second);
+    for (UncheckedURLMap::iterator i = unchecked_urls.begin(); i != end; ++i) {
+      if (i == best)
+        continue;
+      if (service) {
+        service->RemoveKeyword(i->second->id());
+        if (removed_keyword_guids)
+          removed_keyword_guids->insert(i->second->sync_guid());
+      }
+      delete i->second;
     }
+
+    // Done with this group.
+    unchecked_urls.erase(unchecked_urls.begin(), end);
   }
+
+  // Return the checked URLs.
+  template_urls->swap(checked_urls);
 }
 
 // Returns the TemplateURL with id specified from the list of TemplateURLs.
 // If not found, returns NULL.
 TemplateURL* GetTemplateURLByID(
-    const std::vector<TemplateURL*>& template_urls,
+    const TemplateURLService::TemplateURLVector& template_urls,
     int64 id) {
-  for (std::vector<TemplateURL*>::const_iterator i = template_urls.begin();
-       i != template_urls.end(); ++i) {
+  for (TemplateURLService::TemplateURLVector::const_iterator i(
+       template_urls.begin()); i != template_urls.end(); ++i) {
     if ((*i)->id() == id) {
       return *i;
     }
@@ -88,11 +136,14 @@ TemplateURL* GetTemplateURLByID(
 // Loads engines from prepopulate data and merges them in with the existing
 // engines.  This is invoked when the version of the prepopulate data changes.
 // If |removed_keyword_guids| is not NULL, the Sync GUID of each item removed
-// from the DB will be added to it.
+// from the DB will be added to it.  Note that this function will take
+// ownership of |prepopulated_urls| and will clear the vector.
 void MergeEnginesFromPrepopulateData(
     Profile* profile,
     WebDataService* service,
-    std::vector<TemplateURL*>* template_urls,
+    ScopedVector<TemplateURL>* prepopulated_urls,
+    size_t default_search_index,
+    TemplateURLService::TemplateURLVector* template_urls,
     TemplateURL** default_search_provider,
     std::set<std::string>* removed_keyword_guids) {
   DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
@@ -103,28 +154,22 @@ void MergeEnginesFromPrepopulateData(
   // prepopulate data (i.e. have a non-zero prepopulate_id()).
   typedef std::map<int, TemplateURL*> IDMap;
   IDMap id_to_turl;
-  for (std::vector<TemplateURL*>::iterator i(template_urls->begin());
-       i != template_urls->end(); ++i) {
+  for (TemplateURLService::TemplateURLVector::iterator i(
+       template_urls->begin()); i != template_urls->end(); ++i) {
     int prepopulate_id = (*i)->prepopulate_id();
     if (prepopulate_id > 0)
       id_to_turl[prepopulate_id] = *i;
   }
 
-  // Get the current set of prepopulatd URLs.
-  std::vector<TemplateURL*> prepopulated_urls;
-  size_t default_search_index;
-  TemplateURLPrepopulateData::GetPrepopulatedEngines(profile,
-      &prepopulated_urls, &default_search_index);
-
   // For each current prepopulated URL, check whether |template_urls| contained
   // a matching prepopulated URL.  If so, update the passed-in URL to match the
   // current data.  (If the passed-in URL was user-edited, we persist the user's
   // name and keyword.)  If not, add the prepopulated URL to |template_urls|.
   // Along the way, point |default_search_provider| at the default prepopulated
   // URL, if the user hasn't already set another URL as default.
-  for (size_t i = 0; i < prepopulated_urls.size(); ++i) {
+  for (size_t i = 0; i < prepopulated_urls->size(); ++i) {
     // We take ownership of |prepopulated_urls[i]|.
-    scoped_ptr<TemplateURL> prepopulated_url(prepopulated_urls[i]);
+    scoped_ptr<TemplateURL> prepopulated_url((*prepopulated_urls)[i]);
     const int prepopulated_id = prepopulated_url->prepopulate_id();
     DCHECK_NE(0, prepopulated_id);
 
@@ -146,8 +191,8 @@ void MergeEnginesFromPrepopulateData(
         service->UpdateKeyword(data);
 
       // Replace the entry in |template_urls| with the updated one.
-      std::vector<TemplateURL*>::iterator j = std::find(template_urls->begin(),
-          template_urls->end(), existing_url.get());
+      TemplateURLService::TemplateURLVector::iterator j = std::find(
+          template_urls->begin(), template_urls->end(), existing_url.get());
       *j = new TemplateURL(profile, data);
       url_in_vector = *j;
       if (*default_search_provider == existing_url.get())
@@ -160,6 +205,10 @@ void MergeEnginesFromPrepopulateData(
     if (i == default_search_index && !*default_search_provider)
       *default_search_provider = url_in_vector;
   }
+  // The above loop takes ownership of all the contents of prepopulated_urls.
+  // Clear the pointers.
+  prepopulated_urls->weak_erase(prepopulated_urls->begin(),
+                                prepopulated_urls->end());
 
   // The block above removed all the URLs from the |id_to_turl| map that were
   // found in the prepopulate data.  Any remaining URLs that haven't been
@@ -168,7 +217,7 @@ void MergeEnginesFromPrepopulateData(
     const TemplateURL* template_url = i->second;
     if ((template_url->safe_for_autoreplace()) &&
         (template_url != *default_search_provider)) {
-      std::vector<TemplateURL*>::iterator j =
+      TemplateURLService::TemplateURLVector::iterator j =
           std::find(template_urls->begin(), template_urls->end(), template_url);
       DCHECK(j != template_urls->end());
       template_urls->erase(j);
@@ -186,7 +235,7 @@ void GetSearchProvidersUsingKeywordResult(
     const WDTypedResult& result,
     WebDataService* service,
     Profile* profile,
-    std::vector<TemplateURL*>* template_urls,
+    TemplateURLService::TemplateURLVector* template_urls,
     TemplateURL** default_search_provider,
     int* new_resource_keyword_version,
     std::set<std::string>* removed_keyword_guids) {
@@ -207,27 +256,27 @@ void GetSearchProvidersUsingKeywordResult(
        ++i)
     template_urls->push_back(new TemplateURL(profile, *i));
 
-  const int resource_keyword_version =
-      TemplateURLPrepopulateData::GetDataVersion(
-          profile ? profile->GetPrefs() : NULL);
-  if (keyword_result.builtin_keyword_version != resource_keyword_version) {
-    // There should never be duplicate TemplateURLs. We had a bug such that
-    // duplicate TemplateURLs existed for one locale. As such we invoke
-    // RemoveDuplicatePrepopulateIDs to nuke the duplicates.
-    RemoveDuplicatePrepopulateIDs(template_urls, service,
-                                  removed_keyword_guids);
-  }
-
   int64 default_search_provider_id = keyword_result.default_search_provider_id;
   if (default_search_provider_id) {
     *default_search_provider =
         GetTemplateURLByID(*template_urls, default_search_provider_id);
   }
 
+  ScopedVector<TemplateURL> prepopulated_urls;
+  size_t default_search_index;
+  TemplateURLPrepopulateData::GetPrepopulatedEngines(profile,
+      &prepopulated_urls.get(), &default_search_index);
+  RemoveDuplicatePrepopulateIDs(service, prepopulated_urls,
+                                *default_search_provider, template_urls,
+                                removed_keyword_guids);
+
+  const int resource_keyword_version =
+      TemplateURLPrepopulateData::GetDataVersion(
+          profile ? profile->GetPrefs() : NULL);
   if (keyword_result.builtin_keyword_version != resource_keyword_version) {
-    MergeEnginesFromPrepopulateData(profile, service, template_urls,
-                                    default_search_provider,
-                                    removed_keyword_guids);
+    MergeEnginesFromPrepopulateData(profile, service, &prepopulated_urls,
+        default_search_index, template_urls, default_search_provider,
+        removed_keyword_guids);
     *new_resource_keyword_version = resource_keyword_version;
   }
 }