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..22bd3699006ba5e569cbe18945d105c4ab2ed1bb 100644
--- a/chrome/browser/search_engines/util.cc
+++ b/chrome/browser/search_engines/util.cc
@@ -6,6 +6,7 @@
 
 #include <set>
 #include <string>
+#include <map>
 #include <vector>
 
 #include "base/logging.h"
@@ -35,49 +36,97 @@ 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,
+// Removes (and deletes) TemplateURLs from |template_urls| and |service| if they
+// have duplicate prepopulate ids. If |removed_keyword_guids| is not NULL, the
+// Sync GUID of each item removed from the DB will be added to it.
+void RemoveDuplicatePrepopulateIDs(
     WebDataService* service,
+    const std::vector<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);

[SteveT, 2012/05/17 15:01:45]

FYI you used to have a DCHECK(default_search_provider) here (not sure how it
left the diff) but it turns out it's possible for the caller to not have the DSP
yet. This was causing TemplateURLServiceTests and Chrome startup to crash.

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

Yeah, this was a mistake.  I was thinking one level of indirection too many,
because I was thinking about how on the caller side we have a TemplateURL**, and
I wanted to DCHECK() that the first level of pointer was non-NULL.  But we deref
before calling this function, so that assertion is implied.  Removing the DCHECK
entirely here was the right thing to do.

 
-  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 it to the checked group; remove it from elsewhere.
+    checked_urls.push_back(best->second);
+    unchecked_urls.erase(best);
+    for (UncheckedURLMap::iterator i = unchecked_urls.begin(); i != end; ++i) {
+      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;
     }
@@ -92,7 +141,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,
     std::set<std::string>* removed_keyword_guids) {
   DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
@@ -103,19 +154,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
@@ -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())
@@ -168,7 +213,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 +231,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 +252,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);
   }
 
+  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,
+                                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;
   }
 }
@@ -252,3 +297,17 @@ bool DidDefaultSearchProviderChange(
   }
   return true;
 }
+
+namespace testing {
+
+void TestRemoveDuplicatePrepopulateIDs(
+    WebDataService* service,
+    const std::vector<TemplateURL*>& prepopulated_urls,
+    TemplateURL* default_search_provider,
+    TemplateURLService::TemplateURLVector* template_urls,
+    std::set<std::string>* removed_keyword_guids) {
+  RemoveDuplicatePrepopulateIDs(service, prepopulated_urls,
+      default_search_provider, template_urls, removed_keyword_guids);
+}
+
+}  // namespace testing