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 216d8f3c96235d95e69cc4e8b9aa2dd174e64ae5..6e0a172d5d4749668a6d7414ed31724c9996cdf0 100644
--- a/chrome/browser/search_engines/util.cc
+++ b/chrome/browser/search_engines/util.cc
@@ -4,7 +4,7 @@
 
 #include "chrome/browser/search_engines/util.h"
 
-#include <set>
+#include <map>
 #include <vector>
 
 #include "base/logging.h"
@@ -34,44 +34,92 @@ 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.
-static void RemoveDuplicatePrepopulateIDs(
-    std::vector<TemplateURL*>* template_urls,
-    WebDataService* service) {
-  DCHECK(template_urls);
+// Removes (and deletes) TemplateURLs from |template_urls| and |service| if they
+// have duplicate prepopulate ids.
+void RemoveDuplicatePrepopulateIDs(
+    WebDataService* service,
+    const std::vector<TemplateURL*>& prepopulated_urls,
+    TemplateURL* default_search_provider,
+    TemplateURLService::TemplateURLVector* 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());
-        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;
+      }
+
+      // 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;
       }
-    } else {
-      ++i;
     }
+
+    // Add it to the checked group; remove it from elsewhere.

[Peter Kasting, 2012/05/17 20:12:17]

Nit: Let's just say "Add the best URL to the checked group and delete the rest."

[SteveT, 2012/05/17 21:27:22]

Done.

+    checked_urls.push_back(best->second);
+    unchecked_urls.erase(best);

[Peter Kasting, 2012/05/17 20:12:17]

Instead of this, let's put an "if (i == best) continue" in the loop below.  This
way we won't actually touch change the map except in the single erase() call at
the end.  While doing the erase() here happens to be safe with a map since it
won't invalidate other map iterators, it _looks_ scary, and would break if
someone changed this to be a different container type.

[SteveT, 2012/05/17 21:27:22]

Makes sense. Done.

+    for (UncheckedURLMap::iterator i = unchecked_urls.begin(); i != end; ++i) {
+      if (service)

[SteveT, 2012/05/17 13:34:54]

Since we're allowing the service to be NULL (as required by that other
callsite), we'll have to do the Remove only if it's provided, as before.

+        service->RemoveKeyword(i->second->id());
+      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;
     }
@@ -84,7 +132,9 @@ TemplateURL* GetTemplateURLByID(
 void MergeEnginesFromPrepopulateData(
     Profile* profile,
     WebDataService* service,
-    std::vector<TemplateURL*>* template_urls,
+    const std::vector<TemplateURL*>& prepopulated_urls,
+    size_t default_search_index,
+    TemplateURLService::TemplateURLVector* template_urls,
     TemplateURL** default_search_provider) {
   DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
   DCHECK(template_urls);
@@ -94,19 +144,13 @@ 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
@@ -137,8 +181,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())
@@ -159,7 +203,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);
@@ -174,7 +218,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) {
   DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
@@ -194,25 +238,25 @@ 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);
-  }
-
   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);
   }
 
+  std::vector<TemplateURL*> prepopulated_urls;
+  size_t default_search_index;
+  TemplateURLPrepopulateData::GetPrepopulatedEngines(profile,
+      &prepopulated_urls, &default_search_index);
+  RemoveDuplicatePrepopulateIDs(service, prepopulated_urls,
+                                *default_search_provider, template_urls);
+
+  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);
+    MergeEnginesFromPrepopulateData(profile, service, prepopulated_urls,
+        default_search_index, template_urls, default_search_provider);
     *new_resource_keyword_version = resource_keyword_version;
   }
 }
@@ -238,3 +282,15 @@ bool DidDefaultSearchProviderChange(
   return true;
 }
 
+namespace testing {
+
+void TestRemoveDuplicatePrepopulateIDs(
+    WebDataService* service,
+    const std::vector<TemplateURL*>& prepopulated_urls,
+    TemplateURL* default_search_provider,
+    TemplateURLService::TemplateURLVector* template_urls) {
+  RemoveDuplicatePrepopulateIDs(service, prepopulated_urls,
+      default_search_provider, template_urls);
+}
+
+}  // namespace testing