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

chrome/browser/search_engines/util.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/search_engines/util.h"
 
-#include <set>
+#include <map>
 #include <vector>
 
 #include "base/logging.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"
 #include "chrome/browser/search_engines/template_url_service.h"
 #include "chrome/browser/search_engines/template_url_service_factory.h"
 #include "content/public/browser/browser_thread.h"
 
 using content::BrowserThread;
 
 string16 GetDefaultSearchEngineName(Profile* profile) {
   if (!profile) {
     NOTREACHED();
     return string16();
   }
   const TemplateURL* const default_provider =
       TemplateURLServiceFactory::GetForProfile(profile)->
       GetDefaultSearchProvider();
   if (!default_provider) {
     // TODO(cpu): bug 1187517. It is possible to have no default provider.
     // returning an empty string is a stopgap measure for the crash
     // http://code.google.com/p/chromium/issues/detail?id=2573
     return string16();
   }
   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) {
+// 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);
-  DCHECK(service == NULL || BrowserThread::CurrentlyOn(BrowserThread::UI));
 
-  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;
       }
-    } 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.

[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;
     }
   }
   return NULL;
 }
 
 // Loads engines from prepopulate data and merges them in with the existing
 // engines.  This is invoked when the version of the prepopulate data changes.
 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);
   DCHECK(default_search_provider);
 
   // Create a map to hold all provided |template_urls| that originally came from
   // 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) {
     // We take ownership of |prepopulated_urls[i]|.
     scoped_ptr<TemplateURL> prepopulated_url(prepopulated_urls[i]);
     const int prepopulated_id = prepopulated_url->prepopulate_id();
@@ skipping 10 matching lines @@
       if (!existing_url->safe_for_autoreplace()) {
         data.safe_for_autoreplace = false;
         data.SetKeyword(existing_url->keyword());
         data.short_name = existing_url->short_name();
       }
       data.id = existing_url->id();
       if (service)
         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())
         *default_search_provider = url_in_vector;
     } else {
       template_urls->push_back(prepopulated_url.release());
       url_in_vector = template_urls->back();
     }
     DCHECK(url_in_vector);
     if (i == default_search_index && !*default_search_provider)
       *default_search_provider = url_in_vector;
   }
 
   // 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
   // user-edited or made default can be removed from the data store.
   for (IDMap::iterator i(id_to_turl.begin()); i != id_to_turl.end(); ++i) {
     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);
        if (service)
          service->RemoveKeyword(template_url->id());
       delete template_url;
     }
   }
 }
 
 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));
   DCHECK(template_urls);
   DCHECK(template_urls->empty());
   DCHECK(default_search_provider);
   DCHECK(*default_search_provider == NULL);
   DCHECK_EQ(result.GetType(), KEYWORDS_RESULT);
   DCHECK(new_resource_keyword_version);
 
   *new_resource_keyword_version = 0;
   WDKeywordsResult keyword_result = reinterpret_cast<
       const WDResult<WDKeywordsResult>*>(&result)->GetValue();
 
   for (KeywordTable::Keywords::const_iterator i(
        keyword_result.keywords.begin()); i != keyword_result.keywords.end();
        ++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;
   }
 }
 
 bool DidDefaultSearchProviderChange(
     const WDTypedResult& result,
     Profile* profile,
     scoped_ptr<TemplateURL>* backup_default_search_provider) {
   DCHECK(backup_default_search_provider);
   DCHECK(!backup_default_search_provider->get());
   DCHECK_EQ(result.GetType(), KEYWORDS_RESULT);
 
   WDKeywordsResult keyword_result = reinterpret_cast<
       const WDResult<WDKeywordsResult>*>(&result)->GetValue();
 
   if (!keyword_result.did_default_search_provider_change)
     return false;
 
   if (keyword_result.backup_valid) {
     backup_default_search_provider->reset(new TemplateURL(profile,
         keyword_result.default_search_provider_backup));
   }
   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