src/chrome/browser/search_engines/template_url_service.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/search_engines/template_url_service.h"
   6
   7 #include <algorithm>
   8 #include <utility>
   9
  10 #include "base/auto_reset.h"
  11 #include "base/command_line.h"
  12 #include "base/compiler_specific.h"
  13 #include "base/environment.h"
  14 #include "base/guid.h"
  15 #include "base/i18n/case_conversion.h"
  16 #include "base/memory/scoped_vector.h"
  17 #include "base/metrics/histogram.h"
  18 #include "base/prefs/pref_service.h"
  19 #include "base/stl_util.h"
  20 #include "base/strings/string_number_conversions.h"
  21 #include "base/strings/string_split.h"
  22 #include "base/strings/string_util.h"
  23 #include "base/strings/utf_string_conversions.h"
  24 #include "base/time/time.h"
  25 #include "chrome/browser/chrome_notification_types.h"
  26 #include "chrome/browser/google/google_url_tracker_factory.h"
  27 #include "chrome/browser/history/history_service.h"
  28 #include "chrome/browser/history/history_service_factory.h"
  29 #include "chrome/browser/metrics/rappor/sampling.h"
  30 #include "chrome/browser/profiles/profile.h"
  31 #include "chrome/browser/rlz/rlz.h"
  32 #include "chrome/browser/search_engines/search_host_to_urls_map.h"
  33 #include "chrome/browser/search_engines/template_url.h"
  34 #include "chrome/browser/search_engines/template_url_prepopulate_data.h"
  35 #include "chrome/browser/search_engines/template_url_service_observer.h"
  36 #include "chrome/browser/search_engines/ui_thread_search_terms_data.h"
  37 #include "chrome/browser/search_engines/util.h"
  38 #include "chrome/browser/webdata/web_data_service.h"
  39 #include "chrome/common/chrome_switches.h"
  40 #include "chrome/common/env_vars.h"
  41 #include "chrome/common/pref_names.h"
  42 #include "components/url_fixer/url_fixer.h"
  43 #include "content/public/browser/notification_service.h"
  44 #include "extensions/common/constants.h"
  45 #include "net/base/net_util.h"
  46 #include "sync/api/sync_change.h"
  47 #include "sync/api/sync_error_factory.h"
  48 #include "sync/protocol/search_engine_specifics.pb.h"
  49 #include "sync/protocol/sync.pb.h"
  50 #include "ui/base/l10n/l10n_util.h"
  51 #include "url/gurl.h"
  52
  53 typedef SearchHostToURLsMap::TemplateURLSet TemplateURLSet;
  54 typedef TemplateURLService::SyncDataMap SyncDataMap;
  55
  56 namespace {
  57
  58 bool IdenticalSyncGUIDs(const TemplateURLData* data, const TemplateURL* turl) {
  59   if (!data || !turl)
  60     return !data && !turl;
  61
  62   return data->sync_guid == turl->sync_guid();
  63 }
  64
  65 const char kDeleteSyncedEngineHistogramName[] =
  66     "Search.DeleteSyncedSearchEngine";
  67
  68 // Values for an enumerated histogram used to track whenever an ACTION_DELETE is
  69 // sent to the server for search engines.
  70 enum DeleteSyncedSearchEngineEvent {
  71   DELETE_ENGINE_USER_ACTION,
  72   DELETE_ENGINE_PRE_SYNC,
  73   DELETE_ENGINE_EMPTY_FIELD,
  74   DELETE_ENGINE_MAX,
  75 };
  76
  77 // Returns true iff the change in |change_list| at index |i| should not be sent
  78 // up to the server based on its GUIDs presence in |sync_data| or when compared
  79 // to changes after it in |change_list|.
  80 // The criteria is:
  81 //  1) It is an ACTION_UPDATE or ACTION_DELETE and the sync_guid associated
  82 //     with it is NOT found in |sync_data|. We can only update and remove
  83 //     entries that were originally from the Sync server.
  84 //  2) It is an ACTION_ADD and the sync_guid associated with it is found in
  85 //     |sync_data|. We cannot re-add entries that Sync already knew about.
  86 //  3) There is an update after an update for the same GUID. We prune earlier
  87 //     ones just to save bandwidth (Sync would normally coalesce them).
  88 bool ShouldRemoveSyncChange(size_t index,
  89                             syncer::SyncChangeList* change_list,
  90                             const SyncDataMap* sync_data) {
  91   DCHECK(index < change_list->size());
  92   const syncer::SyncChange& change_i = (*change_list)[index];
  93   const std::string guid = change_i.sync_data().GetSpecifics()
  94       .search_engine().sync_guid();
  95   syncer::SyncChange::SyncChangeType type = change_i.change_type();
  96   if ((type == syncer::SyncChange::ACTION_UPDATE ||
  97        type == syncer::SyncChange::ACTION_DELETE) &&
  98        sync_data->find(guid) == sync_data->end())
  99     return true;
 100   if (type == syncer::SyncChange::ACTION_ADD &&
 101       sync_data->find(guid) != sync_data->end())
 102     return true;
 103   if (type == syncer::SyncChange::ACTION_UPDATE) {
 104     for (size_t j = index + 1; j < change_list->size(); j++) {
 105       const syncer::SyncChange& change_j = (*change_list)[j];
 106       if ((syncer::SyncChange::ACTION_UPDATE == change_j.change_type()) &&
 107           (change_j.sync_data().GetSpecifics().search_engine().sync_guid() ==
 108               guid))
 109         return true;
 110     }
 111   }
 112   return false;
 113 }
 114
 115 // Remove SyncChanges that should not be sent to the server from |change_list|.
 116 // This is done to eliminate incorrect SyncChanges added by the merge and
 117 // conflict resolution logic when it is unsure of whether or not an entry is new
 118 // from Sync or originally from the local model. This also removes changes that
 119 // would be otherwise be coalesced by Sync in order to save bandwidth.
 120 void PruneSyncChanges(const SyncDataMap* sync_data,
 121                       syncer::SyncChangeList* change_list) {
 122   for (size_t i = 0; i < change_list->size(); ) {
 123     if (ShouldRemoveSyncChange(i, change_list, sync_data))
 124       change_list->erase(change_list->begin() + i);
 125     else
 126       ++i;
 127   }
 128 }
 129
 130 // Helper class that reports a specific string as the Google base URL.  We use
 131 // this so that code can calculate a TemplateURL's previous search URL after a
 132 // change to the global base URL.
 133 class OldBaseURLSearchTermsData : public UIThreadSearchTermsData {
 134  public:
 135   OldBaseURLSearchTermsData(Profile* profile, const std::string& old_base_url);
 136   virtual ~OldBaseURLSearchTermsData();
 137
 138   virtual std::string GoogleBaseURLValue() const OVERRIDE;
 139
 140  private:
 141   std::string old_base_url;
 142 };
 143
 144 OldBaseURLSearchTermsData::OldBaseURLSearchTermsData(
 145     Profile* profile,
 146     const std::string& old_base_url)
 147     : UIThreadSearchTermsData(profile),
 148       old_base_url(old_base_url) {
 149 }
 150
 151 OldBaseURLSearchTermsData::~OldBaseURLSearchTermsData() {
 152 }
 153
 154 std::string OldBaseURLSearchTermsData::GoogleBaseURLValue() const {
 155   return old_base_url;
 156 }
 157
 158 // Returns true if |turl|'s GUID is not found inside |sync_data|. This is to be
 159 // used in MergeDataAndStartSyncing to differentiate between TemplateURLs from
 160 // Sync and TemplateURLs that were initially local, assuming |sync_data| is the
 161 // |initial_sync_data| parameter.
 162 bool IsFromSync(const TemplateURL* turl, const SyncDataMap& sync_data) {
 163   return !!sync_data.count(turl->sync_guid());
 164 }
 165
 166 // Log the number of instances of a keyword that exist, with zero or more
 167 // underscores, which could occur as the result of conflict resolution.
 168 void LogDuplicatesHistogram(
 169     const TemplateURLService::TemplateURLVector& template_urls) {
 170   std::map<std::string, int> duplicates;
 171   for (TemplateURLService::TemplateURLVector::const_iterator it =
 172       template_urls.begin(); it != template_urls.end(); ++it) {
 173     std::string keyword = base::UTF16ToASCII((*it)->keyword());
 174     base::TrimString(keyword, "_", &keyword);
 175     duplicates[keyword]++;
 176   }
 177
 178   // Count the keywords with duplicates.
 179   int num_dupes = 0;
 180   for (std::map<std::string, int>::const_iterator it = duplicates.begin();
 181       it != duplicates.end(); ++it) {
 182     if (it->second > 1)
 183       num_dupes++;
 184   }
 185
 186   UMA_HISTOGRAM_COUNTS_100("Search.SearchEngineDuplicateCounts", num_dupes);
 187 }
 188
 189 }  // namespace
 190
 191
 192 // TemplateURLService::ExtensionKeyword ---------------------------------------
 193
 194 TemplateURLService::ExtensionKeyword::ExtensionKeyword(
 195     const std::string& id,
 196     const std::string& name,
 197     const std::string& keyword)
 198     : extension_id(id),
 199       extension_name(name),
 200       extension_keyword(keyword) {
 201 }
 202
 203 TemplateURLService::ExtensionKeyword::~ExtensionKeyword() {}
 204
 205
 206 // TemplateURLService::LessWithPrefix -----------------------------------------
 207
 208 class TemplateURLService::LessWithPrefix {
 209  public:
 210   // We want to find the set of keywords that begin with a prefix.  The STL
 211   // algorithms will return the set of elements that are "equal to" the
 212   // prefix, where "equal(x, y)" means "!(cmp(x, y) || cmp(y, x))".  When
 213   // cmp() is the typical std::less<>, this results in lexicographic equality;
 214   // we need to extend this to mark a prefix as "not less than" a keyword it
 215   // begins, which will cause the desired elements to be considered "equal to"
 216   // the prefix.  Note: this is still a strict weak ordering, as required by
 217   // equal_range() (though I will not prove that here).
 218   //
 219   // Unfortunately the calling convention is not "prefix and element" but
 220   // rather "two elements", so we pass the prefix as a fake "element" which has
 221   // a NULL KeywordDataElement pointer.
 222   bool operator()(const KeywordToTemplateMap::value_type& elem1,
 223                   const KeywordToTemplateMap::value_type& elem2) const {
 224     return (elem1.second == NULL) ?
 225         (elem2.first.compare(0, elem1.first.length(), elem1.first) > 0) :
 226         (elem1.first < elem2.first);
 227   }
 228 };
 229
 230
 231 // TemplateURLService ---------------------------------------------------------
 232
 233 TemplateURLService::TemplateURLService(Profile* profile)
 234     : provider_map_(new SearchHostToURLsMap),
 235       profile_(profile),
 236       search_terms_data_(new UIThreadSearchTermsData(profile)),
 237       loaded_(false),
 238       load_failed_(false),
 239       load_handle_(0),
 240       default_search_provider_(NULL),
 241       next_id_(kInvalidTemplateURLID + 1),
 242       time_provider_(&base::Time::Now),
 243       models_associated_(false),
 244       processing_syncer_changes_(false),
 245       dsp_change_origin_(DSP_CHANGE_OTHER),
 246       default_search_manager_(
 247           GetPrefs(),
 248           base::Bind(&TemplateURLService::OnDefaultSearchChange,
 249                      base::Unretained(this))) {
 250   DCHECK(profile_);
 251   Init(NULL, 0);
 252 }
 253
 254 TemplateURLService::TemplateURLService(const Initializer* initializers,
 255                                        const int count)
 256     : provider_map_(new SearchHostToURLsMap),
 257       profile_(NULL),
 258       search_terms_data_(new UIThreadSearchTermsData(NULL)),
 259       loaded_(false),
 260       load_failed_(false),
 261       load_handle_(0),
 262       service_(NULL),
 263       default_search_provider_(NULL),
 264       next_id_(kInvalidTemplateURLID + 1),
 265       time_provider_(&base::Time::Now),
 266       models_associated_(false),
 267       processing_syncer_changes_(false),
 268       dsp_change_origin_(DSP_CHANGE_OTHER),
 269       default_search_manager_(
 270           GetPrefs(),
 271           base::Bind(&TemplateURLService::OnDefaultSearchChange,
 272                      base::Unretained(this))) {
 273   Init(initializers, count);
 274 }
 275
 276 TemplateURLService::~TemplateURLService() {
 277   // |service_| should be deleted during Shutdown().
 278   DCHECK(!service_);
 279   STLDeleteElements(&template_urls_);
 280 }
 281
 282 // static
 283 bool TemplateURLService::LoadDefaultSearchProviderFromPrefs(
 284     PrefService* prefs,
 285     scoped_ptr<TemplateURLData>* default_provider_data,
 286     bool* is_managed) {
 287   if (!prefs || !prefs->HasPrefPath(prefs::kDefaultSearchProviderSearchURL) ||
 288       !prefs->HasPrefPath(prefs::kDefaultSearchProviderKeyword))
 289     return false;
 290
 291   const PrefService::Preference* pref =
 292       prefs->FindPreference(prefs::kDefaultSearchProviderSearchURL);
 293   *is_managed = pref && pref->IsManaged();
 294
 295   if (!prefs->GetBoolean(prefs::kDefaultSearchProviderEnabled)) {
 296     // The user doesn't want a default search provider.
 297     default_provider_data->reset(NULL);
 298     return true;
 299   }
 300
 301   base::string16 name =
 302       base::UTF8ToUTF16(prefs->GetString(prefs::kDefaultSearchProviderName));
 303   base::string16 keyword =
 304       base::UTF8ToUTF16(prefs->GetString(prefs::kDefaultSearchProviderKeyword));
 305   if (keyword.empty())
 306     return false;
 307   std::string search_url =
 308       prefs->GetString(prefs::kDefaultSearchProviderSearchURL);
 309   // Force URL to be non-empty.  We've never supported this case, but past bugs
 310   // might have resulted in it slipping through; eventually this code can be
 311   // replaced with a DCHECK(!search_url.empty());.
 312   if (search_url.empty())
 313     return false;
 314   std::string suggest_url =
 315       prefs->GetString(prefs::kDefaultSearchProviderSuggestURL);
 316   std::string instant_url =
 317       prefs->GetString(prefs::kDefaultSearchProviderInstantURL);
 318   std::string image_url =
 319       prefs->GetString(prefs::kDefaultSearchProviderImageURL);
 320   std::string new_tab_url =
 321       prefs->GetString(prefs::kDefaultSearchProviderNewTabURL);
 322   std::string search_url_post_params =
 323       prefs->GetString(prefs::kDefaultSearchProviderSearchURLPostParams);
 324   std::string suggest_url_post_params =
 325       prefs->GetString(prefs::kDefaultSearchProviderSuggestURLPostParams);
 326   std::string instant_url_post_params =
 327       prefs->GetString(prefs::kDefaultSearchProviderInstantURLPostParams);
 328   std::string image_url_post_params =
 329       prefs->GetString(prefs::kDefaultSearchProviderImageURLPostParams);
 330   std::string icon_url =
 331       prefs->GetString(prefs::kDefaultSearchProviderIconURL);
 332   std::string encodings =
 333       prefs->GetString(prefs::kDefaultSearchProviderEncodings);
 334   std::string id_string = prefs->GetString(prefs::kDefaultSearchProviderID);
 335   std::string prepopulate_id =
 336       prefs->GetString(prefs::kDefaultSearchProviderPrepopulateID);
 337   const base::ListValue* alternate_urls =
 338       prefs->GetList(prefs::kDefaultSearchProviderAlternateURLs);
 339   std::string search_terms_replacement_key = prefs->GetString(
 340       prefs::kDefaultSearchProviderSearchTermsReplacementKey);
 341
 342   default_provider_data->reset(new TemplateURLData);
 343   (*default_provider_data)->short_name = name;
 344   (*default_provider_data)->SetKeyword(keyword);
 345   (*default_provider_data)->SetURL(search_url);
 346   (*default_provider_data)->suggestions_url = suggest_url;
 347   (*default_provider_data)->instant_url = instant_url;
 348   (*default_provider_data)->image_url = image_url;
 349   (*default_provider_data)->new_tab_url = new_tab_url;
 350   (*default_provider_data)->search_url_post_params = search_url_post_params;
 351   (*default_provider_data)->suggestions_url_post_params =
 352       suggest_url_post_params;
 353   (*default_provider_data)->instant_url_post_params = instant_url_post_params;
 354   (*default_provider_data)->image_url_post_params = image_url_post_params;
 355   (*default_provider_data)->favicon_url = GURL(icon_url);
 356   (*default_provider_data)->show_in_default_list = true;
 357   (*default_provider_data)->alternate_urls.clear();
 358   for (size_t i = 0; i < alternate_urls->GetSize(); ++i) {
 359     std::string alternate_url;
 360     if (alternate_urls->GetString(i, &alternate_url))
 361       (*default_provider_data)->alternate_urls.push_back(alternate_url);
 362   }
 363   (*default_provider_data)->search_terms_replacement_key =
 364       search_terms_replacement_key;
 365   base::SplitString(encodings, ';', &(*default_provider_data)->input_encodings);
 366   if (!id_string.empty() && !*is_managed) {
 367     int64 value;
 368     base::StringToInt64(id_string, &value);
 369     (*default_provider_data)->id = value;
 370   }
 371   if (!prepopulate_id.empty() && !*is_managed) {
 372     int value;
 373     base::StringToInt(prepopulate_id, &value);
 374     (*default_provider_data)->prepopulate_id = value;
 375   }
 376   return true;
 377 }
 378
 379 // static
 380 base::string16 TemplateURLService::CleanUserInputKeyword(
 381     const base::string16& keyword) {
 382   // Remove the scheme.
 383   base::string16 result(base::i18n::ToLower(keyword));
 384   base::TrimWhitespace(result, base::TRIM_ALL, &result);
 385   url::Component scheme_component;
 386   if (url::ExtractScheme(base::UTF16ToUTF8(keyword).c_str(),
 387                          static_cast<int>(keyword.length()),
 388                          &scheme_component)) {
 389     // If the scheme isn't "http" or "https", bail.  The user isn't trying to
 390     // type a web address, but rather an FTP, file:, or other scheme URL, or a
 391     // search query with some sort of initial operator (e.g. "site:").
 392     if (result.compare(0, scheme_component.end(),
 393                        base::ASCIIToUTF16(url::kHttpScheme)) &&
 394         result.compare(0, scheme_component.end(),
 395                        base::ASCIIToUTF16(url::kHttpsScheme)))
 396       return base::string16();
 397
 398     // Include trailing ':'.
 399     result.erase(0, scheme_component.end() + 1);
 400     // Many schemes usually have "//" after them, so strip it too.
 401     const base::string16 after_scheme(base::ASCIIToUTF16("//"));
 402     if (result.compare(0, after_scheme.length(), after_scheme) == 0)
 403       result.erase(0, after_scheme.length());
 404   }
 405
 406   // Remove leading "www.".
 407   result = net::StripWWW(result);
 408
 409   // Remove trailing "/".
 410   return (result.length() > 0 && result[result.length() - 1] == '/') ?
 411       result.substr(0, result.length() - 1) : result;
 412 }
 413
 414 // static
 415 void TemplateURLService::SaveDefaultSearchProviderToPrefs(
 416     const TemplateURL* t_url,
 417     PrefService* prefs) {
 418   if (!prefs)
 419     return;
 420
 421   bool enabled = false;
 422   std::string search_url;
 423   std::string suggest_url;
 424   std::string instant_url;
 425   std::string image_url;
 426   std::string new_tab_url;
 427   std::string search_url_post_params;
 428   std::string suggest_url_post_params;
 429   std::string instant_url_post_params;
 430   std::string image_url_post_params;
 431   std::string icon_url;
 432   std::string encodings;
 433   std::string short_name;
 434   std::string keyword;
 435   std::string id_string;
 436   std::string prepopulate_id;
 437   base::ListValue alternate_urls;
 438   std::string search_terms_replacement_key;
 439   if (t_url) {
 440     DCHECK_EQ(TemplateURL::NORMAL, t_url->GetType());
 441     enabled = true;
 442     search_url = t_url->url();
 443     suggest_url = t_url->suggestions_url();
 444     instant_url = t_url->instant_url();
 445     image_url = t_url->image_url();
 446     new_tab_url = t_url->new_tab_url();
 447     search_url_post_params = t_url->search_url_post_params();
 448     suggest_url_post_params = t_url->suggestions_url_post_params();
 449     instant_url_post_params = t_url->instant_url_post_params();
 450     image_url_post_params = t_url->image_url_post_params();
 451     GURL icon_gurl = t_url->favicon_url();
 452     if (!icon_gurl.is_empty())
 453       icon_url = icon_gurl.spec();
 454     encodings = JoinString(t_url->input_encodings(), ';');
 455     short_name = base::UTF16ToUTF8(t_url->short_name());
 456     keyword = base::UTF16ToUTF8(t_url->keyword());
 457     id_string = base::Int64ToString(t_url->id());
 458     prepopulate_id = base::Int64ToString(t_url->prepopulate_id());
 459     for (size_t i = 0; i < t_url->alternate_urls().size(); ++i)
 460       alternate_urls.AppendString(t_url->alternate_urls()[i]);
 461     search_terms_replacement_key = t_url->search_terms_replacement_key();
 462   }
 463   prefs->SetBoolean(prefs::kDefaultSearchProviderEnabled, enabled);
 464   prefs->SetString(prefs::kDefaultSearchProviderSearchURL, search_url);
 465   prefs->SetString(prefs::kDefaultSearchProviderSuggestURL, suggest_url);
 466   prefs->SetString(prefs::kDefaultSearchProviderInstantURL, instant_url);
 467   prefs->SetString(prefs::kDefaultSearchProviderImageURL, image_url);
 468   prefs->SetString(prefs::kDefaultSearchProviderNewTabURL, new_tab_url);
 469   prefs->SetString(prefs::kDefaultSearchProviderSearchURLPostParams,
 470                    search_url_post_params);
 471   prefs->SetString(prefs::kDefaultSearchProviderSuggestURLPostParams,
 472                    suggest_url_post_params);
 473   prefs->SetString(prefs::kDefaultSearchProviderInstantURLPostParams,
 474                    instant_url_post_params);
 475   prefs->SetString(prefs::kDefaultSearchProviderImageURLPostParams,
 476                    image_url_post_params);
 477   prefs->SetString(prefs::kDefaultSearchProviderIconURL, icon_url);
 478   prefs->SetString(prefs::kDefaultSearchProviderEncodings, encodings);
 479   prefs->SetString(prefs::kDefaultSearchProviderName, short_name);
 480   prefs->SetString(prefs::kDefaultSearchProviderKeyword, keyword);
 481   prefs->SetString(prefs::kDefaultSearchProviderID, id_string);
 482   prefs->SetString(prefs::kDefaultSearchProviderPrepopulateID, prepopulate_id);
 483   prefs->Set(prefs::kDefaultSearchProviderAlternateURLs, alternate_urls);
 484   prefs->SetString(prefs::kDefaultSearchProviderSearchTermsReplacementKey,
 485       search_terms_replacement_key);
 486 }
 487
 488 bool TemplateURLService::CanReplaceKeyword(
 489     const base::string16& keyword,
 490     const GURL& url,
 491     TemplateURL** template_url_to_replace) {
 492   DCHECK(!keyword.empty());  // This should only be called for non-empty
 493                              // keywords. If we need to support empty kewords
 494                              // the code needs to change slightly.
 495   TemplateURL* existing_url = GetTemplateURLForKeyword(keyword);
 496   if (template_url_to_replace)
 497     *template_url_to_replace = existing_url;
 498   if (existing_url) {
 499     // We already have a TemplateURL for this keyword. Only allow it to be
 500     // replaced if the TemplateURL can be replaced.
 501     return CanReplace(existing_url);
 502   }
 503
 504   // We don't have a TemplateURL with keyword. Only allow a new one if there
 505   // isn't a TemplateURL for the specified host, or there is one but it can
 506   // be replaced. We do this to ensure that if the user assigns a different
 507   // keyword to a generated TemplateURL, we won't regenerate another keyword for
 508   // the same host.
 509   return !url.is_valid() || url.host().empty() ||
 510       CanReplaceKeywordForHost(url.host(), template_url_to_replace);
 511 }
 512
 513 void TemplateURLService::FindMatchingKeywords(
 514     const base::string16& prefix,
 515     bool support_replacement_only,
 516     TemplateURLVector* matches) {
 517   // Sanity check args.
 518   if (prefix.empty())
 519     return;
 520   DCHECK(matches != NULL);
 521   DCHECK(matches->empty());  // The code for exact matches assumes this.
 522
 523   // Required for VS2010: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair
 524   TemplateURL* const kNullTemplateURL = NULL;
 525
 526   // Find matching keyword range.  Searches the element map for keywords
 527   // beginning with |prefix| and stores the endpoints of the resulting set in
 528   // |match_range|.
 529   const std::pair<KeywordToTemplateMap::const_iterator,
 530                   KeywordToTemplateMap::const_iterator> match_range(
 531       std::equal_range(
 532           keyword_to_template_map_.begin(), keyword_to_template_map_.end(),
 533           KeywordToTemplateMap::value_type(prefix, kNullTemplateURL),
 534           LessWithPrefix()));
 535
 536   // Return vector of matching keywords.
 537   for (KeywordToTemplateMap::const_iterator i(match_range.first);
 538        i != match_range.second; ++i) {
 539     if (!support_replacement_only ||
 540         i->second->url_ref().SupportsReplacement(search_terms_data()))
 541       matches->push_back(i->second);
 542   }
 543 }
 544
 545 TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
 546     const base::string16& keyword) {
 547   KeywordToTemplateMap::const_iterator elem(
 548       keyword_to_template_map_.find(keyword));
 549   if (elem != keyword_to_template_map_.end())
 550     return elem->second;
 551   return (!loaded_ &&
 552       initial_default_search_provider_.get() &&
 553       (initial_default_search_provider_->keyword() == keyword)) ?
 554       initial_default_search_provider_.get() : NULL;
 555 }
 556
 557 TemplateURL* TemplateURLService::GetTemplateURLForGUID(
 558     const std::string& sync_guid) {
 559   GUIDToTemplateMap::const_iterator elem(guid_to_template_map_.find(sync_guid));
 560   if (elem != guid_to_template_map_.end())
 561     return elem->second;
 562   return (!loaded_ &&
 563       initial_default_search_provider_.get() &&
 564       (initial_default_search_provider_->sync_guid() == sync_guid)) ?
 565       initial_default_search_provider_.get() : NULL;
 566 }
 567
 568 TemplateURL* TemplateURLService::GetTemplateURLForHost(
 569     const std::string& host) {
 570   if (loaded_)
 571     return provider_map_->GetTemplateURLForHost(host);
 572   TemplateURL* initial_dsp = initial_default_search_provider_.get();
 573   if (!initial_dsp)
 574     return NULL;
 575   return (initial_dsp->GenerateSearchURL(search_terms_data()).host() == host) ?
 576       initial_dsp : NULL;
 577 }
 578
 579 bool TemplateURLService::Add(TemplateURL* template_url) {
 580   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 581   if (!AddNoNotify(template_url, true))
 582     return false;
 583   NotifyObservers();
 584   return true;
 585 }
 586
 587 void TemplateURLService::AddWithOverrides(TemplateURL* template_url,
 588                                           const base::string16& short_name,
 589                                           const base::string16& keyword,
 590                                           const std::string& url) {
 591   DCHECK(!keyword.empty());
 592   DCHECK(!url.empty());
 593   template_url->data_.short_name = short_name;
 594   template_url->data_.SetKeyword(keyword);
 595   template_url->SetURL(url);
 596   Add(template_url);
 597 }
 598
 599 void TemplateURLService::AddExtensionControlledTURL(
 600     TemplateURL* template_url,
 601     scoped_ptr<AssociatedExtensionInfo> info) {
 602   DCHECK(loaded_);
 603   DCHECK(template_url);
 604   DCHECK_EQ(kInvalidTemplateURLID, template_url->id());
 605   DCHECK(info);
 606   DCHECK_EQ(info->wants_to_be_default_engine,
 607             template_url->show_in_default_list());
 608   template_url->extension_info_.swap(info);
 609   DCHECK(!FindTemplateURLForExtension(
 610       template_url->GetExtensionId(),
 611       TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION));
 612
 613   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 614   if (AddNoNotify(template_url, true)) {
 615     if (template_url->extension_info_->wants_to_be_default_engine)
 616       UpdateExtensionDefaultSearchEngine();
 617     NotifyObservers();
 618   }
 619 }
 620
 621 void TemplateURLService::Remove(TemplateURL* template_url) {
 622   RemoveNoNotify(template_url);
 623   NotifyObservers();
 624 }
 625
 626 void TemplateURLService::RemoveExtensionControlledTURL(
 627     const std::string& extension_id) {
 628   DCHECK(loaded_);
 629   TemplateURL* url = FindTemplateURLForExtension(
 630       extension_id, TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION);
 631   if (!url)
 632     return;
 633   // NULL this out so that we can call RemoveNoNotify.
 634   // UpdateExtensionDefaultSearchEngine will cause it to be reset.
 635   if (default_search_provider_ == url)
 636     default_search_provider_ = NULL;
 637   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 638   RemoveNoNotify(url);
 639   UpdateExtensionDefaultSearchEngine();
 640   NotifyObservers();
 641 }
 642
 643 void TemplateURLService::RemoveAutoGeneratedSince(base::Time created_after) {
 644   RemoveAutoGeneratedBetween(created_after, base::Time());
 645 }
 646
 647 void TemplateURLService::RemoveAutoGeneratedBetween(base::Time created_after,
 648                                                     base::Time created_before) {
 649   RemoveAutoGeneratedForOriginBetween(GURL(), created_after, created_before);
 650 }
 651
 652 void TemplateURLService::RemoveAutoGeneratedForOriginBetween(
 653     const GURL& origin,
 654     base::Time created_after,
 655     base::Time created_before) {
 656   GURL o(origin.GetOrigin());
 657   bool should_notify = false;
 658   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 659   for (size_t i = 0; i < template_urls_.size();) {
 660     if (template_urls_[i]->date_created() >= created_after &&
 661         (created_before.is_null() ||
 662          template_urls_[i]->date_created() < created_before) &&
 663         CanReplace(template_urls_[i]) &&
 664         (o.is_empty() ||
 665          template_urls_[i]->GenerateSearchURL(
 666              search_terms_data()).GetOrigin() == o)) {
 667       RemoveNoNotify(template_urls_[i]);
 668       should_notify = true;
 669     } else {
 670       ++i;
 671     }
 672   }
 673   if (should_notify)
 674     NotifyObservers();
 675 }
 676
 677
 678 void TemplateURLService::RegisterOmniboxKeyword(
 679     const std::string& extension_id,
 680     const std::string& extension_name,
 681     const std::string& keyword) {
 682   DCHECK(loaded_);
 683
 684   if (!FindTemplateURLForExtension(extension_id,
 685                                    TemplateURL::OMNIBOX_API_EXTENSION)) {
 686     ExtensionKeyword extension_url(extension_id, extension_name, keyword);
 687     Add(CreateTemplateURLForExtension(extension_url));
 688   }
 689 }
 690
 691 void TemplateURLService::UnregisterOmniboxKeyword(
 692     const std::string& extension_id) {
 693   DCHECK(loaded_);
 694   TemplateURL* url = FindTemplateURLForExtension(
 695       extension_id, TemplateURL::OMNIBOX_API_EXTENSION);
 696   if (url)
 697     Remove(url);
 698 }
 699
 700 TemplateURLService::TemplateURLVector TemplateURLService::GetTemplateURLs() {
 701   return template_urls_;
 702 }
 703
 704 void TemplateURLService::IncrementUsageCount(TemplateURL* url) {
 705   DCHECK(url);
 706   // Extension-controlled search engines are not persisted.
 707   if (url->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
 708     return;
 709   if (std::find(template_urls_.begin(), template_urls_.end(), url) ==
 710       template_urls_.end())
 711     return;
 712   ++url->data_.usage_count;
 713
 714   if (service_)
 715     service_->UpdateKeyword(url->data());
 716 }
 717
 718 void TemplateURLService::ResetTemplateURL(TemplateURL* url,
 719                                           const base::string16& title,
 720                                           const base::string16& keyword,
 721                                           const std::string& search_url) {
 722   if (ResetTemplateURLNoNotify(url, title, keyword, search_url))
 723     NotifyObservers();
 724 }
 725
 726 bool TemplateURLService::CanMakeDefault(const TemplateURL* url) {
 727   return
 728       ((default_search_provider_source_ == DefaultSearchManager::FROM_USER) ||
 729        (default_search_provider_source_ ==
 730         DefaultSearchManager::FROM_FALLBACK)) &&
 731       (url != GetDefaultSearchProvider()) &&
 732       url->url_ref().SupportsReplacement(search_terms_data()) &&
 733       (url->GetType() == TemplateURL::NORMAL);
 734 }
 735
 736 void TemplateURLService::SetUserSelectedDefaultSearchProvider(
 737     TemplateURL* url) {
 738   // Omnibox keywords cannot be made default. Extension-controlled search
 739   // engines can be made default only by the extension itself because they
 740   // aren't persisted.
 741   DCHECK(!url || (url->GetType() == TemplateURL::NORMAL));
 742   if (load_failed_) {
 743     // Skip the DefaultSearchManager, which will persist to user preferences.
 744     if ((default_search_provider_source_ == DefaultSearchManager::FROM_USER) ||
 745         (default_search_provider_source_ ==
 746          DefaultSearchManager::FROM_FALLBACK)) {
 747       ApplyDefaultSearchChange(url ? &url->data() : NULL,
 748                                DefaultSearchManager::FROM_USER);
 749     }
 750   } else {
 751     // We rely on the DefaultSearchManager to call OnDefaultSearchChange if, in
 752     // fact, the effective DSE changes.
 753     if (url)
 754       default_search_manager_.SetUserSelectedDefaultSearchEngine(url->data());
 755     else
 756       default_search_manager_.ClearUserSelectedDefaultSearchEngine();
 757   }
 758 }
 759
 760 TemplateURL* TemplateURLService::GetDefaultSearchProvider() {
 761   return loaded_ ?
 762     default_search_provider_ : initial_default_search_provider_.get();
 763 }
 764
 765 bool TemplateURLService::IsSearchResultsPageFromDefaultSearchProvider(
 766     const GURL& url) {
 767   TemplateURL* default_provider = GetDefaultSearchProvider();
 768   return default_provider &&
 769       default_provider->IsSearchURL(url, search_terms_data());
 770 }
 771
 772 bool TemplateURLService::IsExtensionControlledDefaultSearch() {
 773   return default_search_provider_source_ ==
 774       DefaultSearchManager::FROM_EXTENSION;
 775 }
 776
 777 void TemplateURLService::RepairPrepopulatedSearchEngines() {
 778   // Can't clean DB if it hasn't been loaded.
 779   DCHECK(loaded());
 780
 781   if ((default_search_provider_source_ == DefaultSearchManager::FROM_USER) ||
 782       (default_search_provider_source_ ==
 783           DefaultSearchManager::FROM_FALLBACK)) {
 784     // Clear |default_search_provider_| in case we want to remove the engine it
 785     // points to. This will get reset at the end of the function anyway.
 786     default_search_provider_ = NULL;
 787   }
 788
 789   size_t default_search_provider_index = 0;
 790   ScopedVector<TemplateURLData> prepopulated_urls =
 791       TemplateURLPrepopulateData::GetPrepopulatedEngines(
 792           GetPrefs(), &default_search_provider_index);
 793   DCHECK(!prepopulated_urls.empty());
 794   ActionsFromPrepopulateData actions(CreateActionsFromCurrentPrepopulateData(
 795       &prepopulated_urls, template_urls_, default_search_provider_));
 796
 797   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 798
 799   // Remove items.
 800   for (std::vector<TemplateURL*>::iterator i = actions.removed_engines.begin();
 801        i < actions.removed_engines.end(); ++i)
 802     RemoveNoNotify(*i);
 803
 804   // Edit items.
 805   for (EditedEngines::iterator i(actions.edited_engines.begin());
 806        i < actions.edited_engines.end(); ++i) {
 807     UIThreadSearchTermsData search_terms_data(profile());
 808     TemplateURL new_values(i->second);
 809     UpdateNoNotify(i->first, new_values, search_terms_data);
 810   }
 811
 812   // Add items.
 813   for (std::vector<TemplateURLData>::const_iterator i =
 814            actions.added_engines.begin();
 815        i < actions.added_engines.end();
 816        ++i) {
 817     AddNoNotify(new TemplateURL(*i), true);
 818   }
 819
 820   base::AutoReset<DefaultSearchChangeOrigin> change_origin(
 821       &dsp_change_origin_, DSP_CHANGE_PROFILE_RESET);
 822
 823   default_search_manager_.ClearUserSelectedDefaultSearchEngine();
 824
 825   if (!default_search_provider_) {
 826     // If the default search provider came from a user pref we would have been
 827     // notified of the new (fallback-provided) value in
 828     // ClearUserSelectedDefaultSearchEngine() above. Since we are here, the
 829     // value was presumably originally a fallback value (which may have been
 830     // repaired).
 831     DefaultSearchManager::Source source;
 832     const TemplateURLData* new_dse =
 833         default_search_manager_.GetDefaultSearchEngine(&source);
 834     // ApplyDefaultSearchChange will notify observers once it is done.
 835     ApplyDefaultSearchChange(new_dse, source);
 836   } else {
 837     NotifyObservers();
 838   }
 839 }
 840
 841 void TemplateURLService::AddObserver(TemplateURLServiceObserver* observer) {
 842   model_observers_.AddObserver(observer);
 843 }
 844
 845 void TemplateURLService::RemoveObserver(TemplateURLServiceObserver* observer) {
 846   model_observers_.RemoveObserver(observer);
 847 }
 848
 849 void TemplateURLService::Load() {
 850   if (loaded_ || load_handle_)
 851     return;
 852
 853   if (!service_)
 854     service_ = WebDataService::FromBrowserContext(profile_);
 855
 856   if (service_)
 857     load_handle_ = service_->GetKeywords(this);
 858   else
 859     ChangeToLoadedState();
 860 }
 861
 862 scoped_ptr<TemplateURLService::Subscription>
 863     TemplateURLService::RegisterOnLoadedCallback(
 864         const base::Closure& callback) {
 865   return loaded_ ?
 866       scoped_ptr<TemplateURLService::Subscription>() :
 867       on_loaded_callbacks_.Add(callback);
 868 }
 869
 870 void TemplateURLService::OnWebDataServiceRequestDone(
 871     WebDataService::Handle h,
 872     const WDTypedResult* result) {
 873   // Reset the load_handle so that we don't try and cancel the load in
 874   // the destructor.
 875   load_handle_ = 0;
 876
 877   if (!result) {
 878     // Results are null if the database went away or (most likely) wasn't
 879     // loaded.
 880     load_failed_ = true;
 881     service_ = NULL;
 882     ChangeToLoadedState();
 883     return;
 884   }
 885
 886   TemplateURLVector template_urls;
 887   int new_resource_keyword_version = 0;
 888   GetSearchProvidersUsingKeywordResult(
 889       *result,
 890       service_.get(),
 891       profile_,
 892       &template_urls,
 893       (default_search_provider_source_ == DefaultSearchManager::FROM_USER) ?
 894           initial_default_search_provider_.get() : NULL,
 895       search_terms_data(),
 896       &new_resource_keyword_version,
 897       &pre_sync_deletes_);
 898
 899   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
 900
 901   PatchMissingSyncGUIDs(&template_urls);
 902   SetTemplateURLs(&template_urls);
 903
 904   // This initializes provider_map_ which should be done before
 905   // calling UpdateKeywordSearchTermsForURL.
 906   // This also calls NotifyObservers.
 907   ChangeToLoadedState();
 908
 909   // Index any visits that occurred before we finished loading.
 910   for (size_t i = 0; i < visits_to_add_.size(); ++i)
 911     UpdateKeywordSearchTermsForURL(visits_to_add_[i]);
 912   visits_to_add_.clear();
 913
 914   if (new_resource_keyword_version)
 915     service_->SetBuiltinKeywordVersion(new_resource_keyword_version);
 916
 917   if (default_search_provider_) {
 918     UMA_HISTOGRAM_ENUMERATION(
 919         "Search.DefaultSearchProviderType",
 920         TemplateURLPrepopulateData::GetEngineType(
 921             *default_search_provider_, search_terms_data()),
 922         SEARCH_ENGINE_MAX);
 923     rappor::SampleDomainAndRegistryFromHost(
 924         "Search.DefaultSearchProvider",
 925         default_search_provider_->url_ref().GetHost(search_terms_data()));
 926   }
 927 }
 928
 929 base::string16 TemplateURLService::GetKeywordShortName(
 930     const base::string16& keyword,
 931     bool* is_omnibox_api_extension_keyword) {
 932   const TemplateURL* template_url = GetTemplateURLForKeyword(keyword);
 933
 934   // TODO(sky): Once LocationBarView adds a listener to the TemplateURLService
 935   // to track changes to the model, this should become a DCHECK.
 936   if (template_url) {
 937     *is_omnibox_api_extension_keyword =
 938         template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
 939     return template_url->AdjustedShortNameForLocaleDirection();
 940   }
 941   *is_omnibox_api_extension_keyword = false;
 942   return base::string16();
 943 }
 944
 945 void TemplateURLService::Observe(int type,
 946                                  const content::NotificationSource& source,
 947                                  const content::NotificationDetails& details) {
 948   DCHECK_EQ(type, chrome::NOTIFICATION_HISTORY_URL_VISITED);
 949   content::Details<history::URLVisitedDetails> visit_details(details);
 950   if (!loaded_)
 951     visits_to_add_.push_back(*visit_details.ptr());
 952   else
 953     UpdateKeywordSearchTermsForURL(*visit_details.ptr());
 954 }
 955
 956 void TemplateURLService::Shutdown() {
 957   // This check has to be done at Shutdown() instead of in the dtor to ensure
 958   // that no clients of WebDataService are holding ptrs to it after the first
 959   // phase of the KeyedService Shutdown() process.
 960   if (load_handle_) {
 961     DCHECK(service_.get());
 962     service_->CancelRequest(load_handle_);
 963   }
 964   service_ = NULL;
 965 }
 966
 967 syncer::SyncDataList TemplateURLService::GetAllSyncData(
 968     syncer::ModelType type) const {
 969   DCHECK_EQ(syncer::SEARCH_ENGINES, type);
 970
 971   syncer::SyncDataList current_data;
 972   for (TemplateURLVector::const_iterator iter = template_urls_.begin();
 973       iter != template_urls_.end(); ++iter) {
 974     // We don't sync keywords managed by policy.
 975     if ((*iter)->created_by_policy())
 976       continue;
 977     // We don't sync extension-controlled search engines.
 978     if ((*iter)->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
 979       continue;
 980     current_data.push_back(CreateSyncDataFromTemplateURL(**iter));
 981   }
 982
 983   return current_data;
 984 }
 985
 986 syncer::SyncError TemplateURLService::ProcessSyncChanges(
 987     const tracked_objects::Location& from_here,
 988     const syncer::SyncChangeList& change_list) {
 989   if (!models_associated_) {
 990     syncer::SyncError error(FROM_HERE,
 991                             syncer::SyncError::DATATYPE_ERROR,
 992                             "Models not yet associated.",
 993                             syncer::SEARCH_ENGINES);
 994     return error;
 995   }
 996   DCHECK(loaded_);
 997
 998   base::AutoReset<bool> processing_changes(&processing_syncer_changes_, true);
 999
1000   // We've started syncing, so set our origin member to the base Sync value.
1001   // As we move through Sync Code, we may set this to increasingly specific
1002   // origins so we can tell what exactly caused a DSP change.
1003   base::AutoReset<DefaultSearchChangeOrigin> change_origin(&dsp_change_origin_,
1004       DSP_CHANGE_SYNC_UNINTENTIONAL);
1005
1006   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
1007
1008   syncer::SyncChangeList new_changes;
1009   syncer::SyncError error;
1010   for (syncer::SyncChangeList::const_iterator iter = change_list.begin();
1011       iter != change_list.end(); ++iter) {
1012     DCHECK_EQ(syncer::SEARCH_ENGINES, iter->sync_data().GetDataType());
1013
1014     std::string guid =
1015         iter->sync_data().GetSpecifics().search_engine().sync_guid();
1016     TemplateURL* existing_turl = GetTemplateURLForGUID(guid);
1017     scoped_ptr<TemplateURL> turl(CreateTemplateURLFromTemplateURLAndSyncData(
1018         profile_, existing_turl, iter->sync_data(), &new_changes));
1019     if (!turl.get())
1020       continue;
1021
1022     // Explicitly don't check for conflicts against extension keywords; in this
1023     // case the functions which modify the keyword map know how to handle the
1024     // conflicts.
1025     // TODO(mpcomplete): If we allow editing extension keywords, then those will
1026     // need to undergo conflict resolution.
1027     TemplateURL* existing_keyword_turl =
1028         FindNonExtensionTemplateURLForKeyword(turl->keyword());
1029     if (iter->change_type() == syncer::SyncChange::ACTION_DELETE) {
1030       if (!existing_turl) {
1031         error = sync_error_factory_->CreateAndUploadError(
1032             FROM_HERE,
1033             "ProcessSyncChanges failed on ChangeType ACTION_DELETE");
1034         continue;
1035       }
1036       if (existing_turl == GetDefaultSearchProvider()) {
1037         // The only way Sync can attempt to delete the default search provider
1038         // is if we had changed the kSyncedDefaultSearchProviderGUID
1039         // preference, but perhaps it has not yet been received. To avoid
1040         // situations where this has come in erroneously, we will un-delete
1041         // the current default search from the Sync data. If the pref really
1042         // does arrive later, then default search will change to the correct
1043         // entry, but we'll have this extra entry sitting around. The result is
1044         // not ideal, but it prevents a far more severe bug where the default is
1045         // unexpectedly swapped to something else. The user can safely delete
1046         // the extra entry again later, if they choose. Most users who do not
1047         // look at the search engines UI will not notice this.
1048         // Note that we append a special character to the end of the keyword in
1049         // an attempt to avoid a ping-poinging situation where receiving clients
1050         // may try to continually delete the resurrected entry.
1051         base::string16 updated_keyword = UniquifyKeyword(*existing_turl, true);
1052         TemplateURLData data(existing_turl->data());
1053         data.SetKeyword(updated_keyword);
1054         TemplateURL new_turl(data);
1055         if (UpdateNoNotify(existing_turl, new_turl, search_terms_data()))
1056           NotifyObservers();
1057
1058         syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(new_turl);
1059         new_changes.push_back(syncer::SyncChange(FROM_HERE,
1060                                                  syncer::SyncChange::ACTION_ADD,
1061                                                  sync_data));
1062         // Ignore the delete attempt. This means we never end up resetting the
1063         // default search provider due to an ACTION_DELETE from sync.
1064         continue;
1065       }
1066
1067       Remove(existing_turl);
1068     } else if (iter->change_type() == syncer::SyncChange::ACTION_ADD) {
1069       if (existing_turl) {
1070         error = sync_error_factory_->CreateAndUploadError(
1071             FROM_HERE,
1072             "ProcessSyncChanges failed on ChangeType ACTION_ADD");
1073         continue;
1074       }
1075       const std::string guid = turl->sync_guid();
1076       if (existing_keyword_turl) {
1077         // Resolve any conflicts so we can safely add the new entry.
1078         ResolveSyncKeywordConflict(turl.get(), existing_keyword_turl,
1079                                    &new_changes);
1080       }
1081       base::AutoReset<DefaultSearchChangeOrigin> change_origin(
1082           &dsp_change_origin_, DSP_CHANGE_SYNC_ADD);
1083       // Force the local ID to kInvalidTemplateURLID so we can add it.
1084       TemplateURLData data(turl->data());
1085       data.id = kInvalidTemplateURLID;
1086       TemplateURL* added = new TemplateURL(data);
1087       if (Add(added))
1088         MaybeUpdateDSEAfterSync(added);
1089     } else if (iter->change_type() == syncer::SyncChange::ACTION_UPDATE) {
1090       if (!existing_turl) {
1091         error = sync_error_factory_->CreateAndUploadError(
1092             FROM_HERE,
1093             "ProcessSyncChanges failed on ChangeType ACTION_UPDATE");
1094         continue;
1095       }
1096       if (existing_keyword_turl && (existing_keyword_turl != existing_turl)) {
1097         // Resolve any conflicts with other entries so we can safely update the
1098         // keyword.
1099         ResolveSyncKeywordConflict(turl.get(), existing_keyword_turl,
1100                                    &new_changes);
1101       }
1102       if (UpdateNoNotify(existing_turl, *turl, search_terms_data())) {
1103         NotifyObservers();
1104         MaybeUpdateDSEAfterSync(existing_turl);
1105       }
1106     } else {
1107       // We've unexpectedly received an ACTION_INVALID.
1108       error = sync_error_factory_->CreateAndUploadError(
1109           FROM_HERE,
1110           "ProcessSyncChanges received an ACTION_INVALID");
1111     }
1112   }
1113
1114   // If something went wrong, we want to prematurely exit to avoid pushing
1115   // inconsistent data to Sync. We return the last error we received.
1116   if (error.IsSet())
1117     return error;
1118
1119   error = sync_processor_->ProcessSyncChanges(from_here, new_changes);
1120
1121   return error;
1122 }
1123
1124 syncer::SyncMergeResult TemplateURLService::MergeDataAndStartSyncing(
1125     syncer::ModelType type,
1126     const syncer::SyncDataList& initial_sync_data,
1127     scoped_ptr<syncer::SyncChangeProcessor> sync_processor,
1128     scoped_ptr<syncer::SyncErrorFactory> sync_error_factory) {
1129   DCHECK(loaded_);
1130   DCHECK_EQ(type, syncer::SEARCH_ENGINES);
1131   DCHECK(!sync_processor_.get());
1132   DCHECK(sync_processor.get());
1133   DCHECK(sync_error_factory.get());
1134   syncer::SyncMergeResult merge_result(type);
1135
1136   // Disable sync if we failed to load.
1137   if (load_failed_) {
1138     merge_result.set_error(syncer::SyncError(
1139         FROM_HERE, syncer::SyncError::DATATYPE_ERROR,
1140         "Local database load failed.", syncer::SEARCH_ENGINES));
1141     return merge_result;
1142   }
1143
1144   sync_processor_ = sync_processor.Pass();
1145   sync_error_factory_ = sync_error_factory.Pass();
1146
1147   // We do a lot of calls to Add/Remove/ResetTemplateURL here, so ensure we
1148   // don't step on our own toes.
1149   base::AutoReset<bool> processing_changes(&processing_syncer_changes_, true);
1150
1151   // We've started syncing, so set our origin member to the base Sync value.
1152   // As we move through Sync Code, we may set this to increasingly specific
1153   // origins so we can tell what exactly caused a DSP change.
1154   base::AutoReset<DefaultSearchChangeOrigin> change_origin(&dsp_change_origin_,
1155       DSP_CHANGE_SYNC_UNINTENTIONAL);
1156
1157   syncer::SyncChangeList new_changes;
1158
1159   // Build maps of our sync GUIDs to syncer::SyncData.
1160   SyncDataMap local_data_map = CreateGUIDToSyncDataMap(
1161       GetAllSyncData(syncer::SEARCH_ENGINES));
1162   SyncDataMap sync_data_map = CreateGUIDToSyncDataMap(initial_sync_data);
1163
1164   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
1165
1166   merge_result.set_num_items_before_association(local_data_map.size());
1167   for (SyncDataMap::const_iterator iter = sync_data_map.begin();
1168       iter != sync_data_map.end(); ++iter) {
1169     TemplateURL* local_turl = GetTemplateURLForGUID(iter->first);
1170     scoped_ptr<TemplateURL> sync_turl(
1171         CreateTemplateURLFromTemplateURLAndSyncData(profile_, local_turl,
1172             iter->second, &new_changes));
1173     if (!sync_turl.get())
1174       continue;
1175
1176     if (pre_sync_deletes_.find(sync_turl->sync_guid()) !=
1177         pre_sync_deletes_.end()) {
1178       // This entry was deleted before the initial sync began (possibly through
1179       // preprocessing in TemplateURLService's loading code). Ignore it and send
1180       // an ACTION_DELETE up to the server.
1181       new_changes.push_back(
1182           syncer::SyncChange(FROM_HERE,
1183                              syncer::SyncChange::ACTION_DELETE,
1184                              iter->second));
1185       UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
1186           DELETE_ENGINE_PRE_SYNC, DELETE_ENGINE_MAX);
1187       continue;
1188     }
1189
1190     if (local_turl) {
1191       DCHECK(IsFromSync(local_turl, sync_data_map));
1192       // This local search engine is already synced. If the timestamp differs
1193       // from Sync, we need to update locally or to the cloud. Note that if the
1194       // timestamps are equal, we touch neither.
1195       if (sync_turl->last_modified() > local_turl->last_modified()) {
1196         // We've received an update from Sync. We should replace all synced
1197         // fields in the local TemplateURL. Note that this includes the
1198         // TemplateURLID and the TemplateURL may have to be reparsed. This
1199         // also makes the local data's last_modified timestamp equal to Sync's,
1200         // avoiding an Update on the next MergeData call.
1201         if (UpdateNoNotify(local_turl, *sync_turl, search_terms_data()))
1202           NotifyObservers();
1203         merge_result.set_num_items_modified(
1204             merge_result.num_items_modified() + 1);
1205       } else if (sync_turl->last_modified() < local_turl->last_modified()) {
1206         // Otherwise, we know we have newer data, so update Sync with our
1207         // data fields.
1208         new_changes.push_back(
1209             syncer::SyncChange(FROM_HERE,
1210                                syncer::SyncChange::ACTION_UPDATE,
1211                                local_data_map[local_turl->sync_guid()]));
1212       }
1213       local_data_map.erase(iter->first);
1214     } else {
1215       // The search engine from the cloud has not been synced locally. Merge it
1216       // into our local model. This will handle any conflicts with local (and
1217       // already-synced) TemplateURLs. It will prefer to keep entries from Sync
1218       // over not-yet-synced TemplateURLs.
1219       MergeInSyncTemplateURL(sync_turl.get(), sync_data_map, &new_changes,
1220                              &local_data_map, &merge_result);
1221     }
1222   }
1223
1224   // The remaining SyncData in local_data_map should be everything that needs to
1225   // be pushed as ADDs to sync.
1226   for (SyncDataMap::const_iterator iter = local_data_map.begin();
1227       iter != local_data_map.end(); ++iter) {
1228     new_changes.push_back(
1229         syncer::SyncChange(FROM_HERE,
1230                            syncer::SyncChange::ACTION_ADD,
1231                            iter->second));
1232   }
1233
1234   // Do some post-processing on the change list to ensure that we are sending
1235   // valid changes to sync_processor_.
1236   PruneSyncChanges(&sync_data_map, &new_changes);
1237
1238   LogDuplicatesHistogram(GetTemplateURLs());
1239   merge_result.set_num_items_after_association(
1240       GetAllSyncData(syncer::SEARCH_ENGINES).size());
1241   merge_result.set_error(
1242       sync_processor_->ProcessSyncChanges(FROM_HERE, new_changes));
1243   if (merge_result.error().IsSet())
1244     return merge_result;
1245
1246   // The ACTION_DELETEs from this set are processed. Empty it so we don't try to
1247   // reuse them on the next call to MergeDataAndStartSyncing.
1248   pre_sync_deletes_.clear();
1249
1250   models_associated_ = true;
1251   return merge_result;
1252 }
1253
1254 void TemplateURLService::StopSyncing(syncer::ModelType type) {
1255   DCHECK_EQ(type, syncer::SEARCH_ENGINES);
1256   models_associated_ = false;
1257   sync_processor_.reset();
1258   sync_error_factory_.reset();
1259 }
1260
1261 void TemplateURLService::ProcessTemplateURLChange(
1262     const tracked_objects::Location& from_here,
1263     const TemplateURL* turl,
1264     syncer::SyncChange::SyncChangeType type) {
1265   DCHECK_NE(type, syncer::SyncChange::ACTION_INVALID);
1266   DCHECK(turl);
1267
1268   if (!models_associated_)
1269     return;  // Not syncing.
1270
1271   if (processing_syncer_changes_)
1272     return;  // These are changes originating from us. Ignore.
1273
1274   // Avoid syncing keywords managed by policy.
1275   if (turl->created_by_policy())
1276     return;
1277
1278   // Avoid syncing extension-controlled search engines.
1279   if (turl->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
1280     return;
1281
1282   syncer::SyncChangeList changes;
1283
1284   syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*turl);
1285   changes.push_back(syncer::SyncChange(from_here,
1286                                        type,
1287                                        sync_data));
1288
1289   sync_processor_->ProcessSyncChanges(FROM_HERE, changes);
1290 }
1291
1292 // static
1293 syncer::SyncData TemplateURLService::CreateSyncDataFromTemplateURL(
1294     const TemplateURL& turl) {
1295   sync_pb::EntitySpecifics specifics;
1296   sync_pb::SearchEngineSpecifics* se_specifics =
1297       specifics.mutable_search_engine();
1298   se_specifics->set_short_name(base::UTF16ToUTF8(turl.short_name()));
1299   se_specifics->set_keyword(base::UTF16ToUTF8(turl.keyword()));
1300   se_specifics->set_favicon_url(turl.favicon_url().spec());
1301   se_specifics->set_url(turl.url());
1302   se_specifics->set_safe_for_autoreplace(turl.safe_for_autoreplace());
1303   se_specifics->set_originating_url(turl.originating_url().spec());
1304   se_specifics->set_date_created(turl.date_created().ToInternalValue());
1305   se_specifics->set_input_encodings(JoinString(turl.input_encodings(), ';'));
1306   se_specifics->set_show_in_default_list(turl.show_in_default_list());
1307   se_specifics->set_suggestions_url(turl.suggestions_url());
1308   se_specifics->set_prepopulate_id(turl.prepopulate_id());
1309   se_specifics->set_instant_url(turl.instant_url());
1310   if (!turl.image_url().empty())
1311     se_specifics->set_image_url(turl.image_url());
1312   se_specifics->set_new_tab_url(turl.new_tab_url());
1313   if (!turl.search_url_post_params().empty())
1314     se_specifics->set_search_url_post_params(turl.search_url_post_params());
1315   if (!turl.suggestions_url_post_params().empty()) {
1316     se_specifics->set_suggestions_url_post_params(
1317         turl.suggestions_url_post_params());
1318   }
1319   if (!turl.instant_url_post_params().empty())
1320     se_specifics->set_instant_url_post_params(turl.instant_url_post_params());
1321   if (!turl.image_url_post_params().empty())
1322     se_specifics->set_image_url_post_params(turl.image_url_post_params());
1323   se_specifics->set_last_modified(turl.last_modified().ToInternalValue());
1324   se_specifics->set_sync_guid(turl.sync_guid());
1325   for (size_t i = 0; i < turl.alternate_urls().size(); ++i)
1326     se_specifics->add_alternate_urls(turl.alternate_urls()[i]);
1327   se_specifics->set_search_terms_replacement_key(
1328       turl.search_terms_replacement_key());
1329
1330   return syncer::SyncData::CreateLocalData(se_specifics->sync_guid(),
1331                                            se_specifics->keyword(),
1332                                            specifics);
1333 }
1334
1335 // static
1336 TemplateURL* TemplateURLService::CreateTemplateURLFromTemplateURLAndSyncData(
1337     Profile* profile,
1338     TemplateURL* existing_turl,
1339     const syncer::SyncData& sync_data,
1340     syncer::SyncChangeList* change_list) {
1341   DCHECK(change_list);
1342
1343   sync_pb::SearchEngineSpecifics specifics =
1344       sync_data.GetSpecifics().search_engine();
1345
1346   // Past bugs might have caused either of these fields to be empty.  Just
1347   // delete this data off the server.
1348   if (specifics.url().empty() || specifics.sync_guid().empty()) {
1349     change_list->push_back(
1350         syncer::SyncChange(FROM_HERE,
1351                            syncer::SyncChange::ACTION_DELETE,
1352                            sync_data));
1353     UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
1354         DELETE_ENGINE_EMPTY_FIELD, DELETE_ENGINE_MAX);
1355     return NULL;
1356   }
1357
1358   TemplateURLData data(existing_turl ?
1359       existing_turl->data() : TemplateURLData());
1360   data.short_name = base::UTF8ToUTF16(specifics.short_name());
1361   data.originating_url = GURL(specifics.originating_url());
1362   base::string16 keyword(base::UTF8ToUTF16(specifics.keyword()));
1363   // NOTE: Once this code has shipped in a couple of stable releases, we can
1364   // probably remove the migration portion, comment out the
1365   // "autogenerate_keyword" field entirely in the .proto file, and fold the
1366   // empty keyword case into the "delete data" block above.
1367   bool reset_keyword =
1368       specifics.autogenerate_keyword() || specifics.keyword().empty();
1369   if (reset_keyword)
1370     keyword = base::ASCIIToUTF16("dummy");  // Will be replaced below.
1371   DCHECK(!keyword.empty());
1372   data.SetKeyword(keyword);
1373   data.SetURL(specifics.url());
1374   data.suggestions_url = specifics.suggestions_url();
1375   data.instant_url = specifics.instant_url();
1376   data.image_url = specifics.image_url();
1377   data.new_tab_url = specifics.new_tab_url();
1378   data.search_url_post_params = specifics.search_url_post_params();
1379   data.suggestions_url_post_params = specifics.suggestions_url_post_params();
1380   data.instant_url_post_params = specifics.instant_url_post_params();
1381   data.image_url_post_params = specifics.image_url_post_params();
1382   data.favicon_url = GURL(specifics.favicon_url());
1383   data.show_in_default_list = specifics.show_in_default_list();
1384   data.safe_for_autoreplace = specifics.safe_for_autoreplace();
1385   base::SplitString(specifics.input_encodings(), ';', &data.input_encodings);
1386   // If the server data has duplicate encodings, we'll want to push an update
1387   // below to correct it.  Note that we also fix this in
1388   // GetSearchProvidersUsingKeywordResult(), since otherwise we'd never correct
1389   // local problems for clients which have disabled search engine sync.
1390   bool deduped = DeDupeEncodings(&data.input_encodings);
1391   data.date_created = base::Time::FromInternalValue(specifics.date_created());
1392   data.last_modified = base::Time::FromInternalValue(specifics.last_modified());
1393   data.prepopulate_id = specifics.prepopulate_id();
1394   data.sync_guid = specifics.sync_guid();
1395   data.alternate_urls.clear();
1396   for (int i = 0; i < specifics.alternate_urls_size(); ++i)
1397     data.alternate_urls.push_back(specifics.alternate_urls(i));
1398   data.search_terms_replacement_key = specifics.search_terms_replacement_key();
1399
1400   TemplateURL* turl = new TemplateURL(data);
1401   UIThreadSearchTermsData search_terms_data(profile);
1402   // If this TemplateURL matches a built-in prepopulated template URL, it's
1403   // possible that sync is trying to modify fields that should not be touched.
1404   // Revert these fields to the built-in values.
1405   UpdateTemplateURLIfPrepopulated(turl, profile);
1406   DCHECK_NE(TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION, turl->GetType());
1407   if (reset_keyword || deduped) {
1408     if (reset_keyword)
1409       turl->ResetKeywordIfNecessary(search_terms_data, true);
1410     syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*turl);
1411     change_list->push_back(syncer::SyncChange(FROM_HERE,
1412                                               syncer::SyncChange::ACTION_UPDATE,
1413                                               sync_data));
1414   } else if (turl->IsGoogleSearchURLWithReplaceableKeyword(search_terms_data)) {
1415     if (!existing_turl) {
1416       // We're adding a new TemplateURL that uses the Google base URL, so set
1417       // its keyword appropriately for the local environment.
1418       turl->ResetKeywordIfNecessary(search_terms_data, false);
1419     } else if (existing_turl->IsGoogleSearchURLWithReplaceableKeyword(
1420         search_terms_data)) {
1421       // Ignore keyword changes triggered by the Google base URL changing on
1422       // another client.  If the base URL changes in this client as well, we'll
1423       // pick that up separately at the appropriate time.  Otherwise, changing
1424       // the keyword here could result in having the wrong keyword for the local
1425       // environment.
1426       turl->data_.SetKeyword(existing_turl->keyword());
1427     }
1428   }
1429
1430   return turl;
1431 }
1432
1433 // static
1434 SyncDataMap TemplateURLService::CreateGUIDToSyncDataMap(
1435     const syncer::SyncDataList& sync_data) {
1436   SyncDataMap data_map;
1437   for (syncer::SyncDataList::const_iterator i(sync_data.begin());
1438        i != sync_data.end();
1439        ++i)
1440     data_map[i->GetSpecifics().search_engine().sync_guid()] = *i;
1441   return data_map;
1442 }
1443
1444 void TemplateURLService::SetKeywordSearchTermsForURL(
1445     const TemplateURL* t_url,
1446     const GURL& url,
1447     const base::string16& term) {
1448   HistoryService* history = profile_  ?
1449       HistoryServiceFactory::GetForProfile(profile_,
1450                                            Profile::EXPLICIT_ACCESS) :
1451       NULL;
1452   if (!history)
1453     return;
1454   history->SetKeywordSearchTermsForURL(url, t_url->id(), term);
1455 }
1456
1457 void TemplateURLService::Init(const Initializer* initializers,
1458                               int num_initializers) {
1459   // Register for notifications.
1460   if (profile_) {
1461     // TODO(sky): bug 1166191. The keywords should be moved into the history
1462     // db, which will mean we no longer need this notification and the history
1463     // backend can handle automatically adding the search terms as the user
1464     // navigates.
1465     content::Source<Profile> profile_source(profile_->GetOriginalProfile());
1466     notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URL_VISITED,
1467                                 profile_source);
1468     GoogleURLTracker* google_url_tracker =
1469         GoogleURLTrackerFactory::GetForProfile(profile_);
1470
1471     // GoogleURLTracker is not created in tests.
1472     if (google_url_tracker) {
1473       google_url_updated_subscription_ =
1474           google_url_tracker->RegisterCallback(base::Bind(
1475               &TemplateURLService::OnGoogleURLUpdated, base::Unretained(this)));
1476     }
1477     pref_change_registrar_.Init(GetPrefs());
1478     pref_change_registrar_.Add(
1479         prefs::kSyncedDefaultSearchProviderGUID,
1480         base::Bind(
1481             &TemplateURLService::OnSyncedDefaultSearchProviderGUIDChanged,
1482             base::Unretained(this)));
1483   }
1484
1485   DefaultSearchManager::Source source = DefaultSearchManager::FROM_USER;
1486   TemplateURLData* dse =
1487       default_search_manager_.GetDefaultSearchEngine(&source);
1488   ApplyDefaultSearchChange(dse, source);
1489
1490   if (num_initializers > 0) {
1491     // This path is only hit by test code and is used to simulate a loaded
1492     // TemplateURLService.
1493     ChangeToLoadedState();
1494
1495     // Add specific initializers, if any.
1496     WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
1497     for (int i(0); i < num_initializers; ++i) {
1498       DCHECK(initializers[i].keyword);
1499       DCHECK(initializers[i].url);
1500       DCHECK(initializers[i].content);
1501
1502       // TemplateURLService ends up owning the TemplateURL, don't try and free
1503       // it.
1504       TemplateURLData data;
1505       data.short_name = base::UTF8ToUTF16(initializers[i].content);
1506       data.SetKeyword(base::UTF8ToUTF16(initializers[i].keyword));
1507       data.SetURL(initializers[i].url);
1508       TemplateURL* template_url = new TemplateURL(data);
1509       AddNoNotify(template_url, true);
1510
1511       // Set the first provided identifier to be the default.
1512       if (i == 0)
1513         default_search_manager_.SetUserSelectedDefaultSearchEngine(data);
1514     }
1515   }
1516
1517   // Request a server check for the correct Google URL if Google is the
1518   // default search engine and not in headless mode.
1519   TemplateURL* default_search_provider = GetDefaultSearchProvider();
1520   if (profile_ && default_search_provider &&
1521       default_search_provider->HasGoogleBaseURLs(search_terms_data())) {
1522     scoped_ptr<base::Environment> env(base::Environment::Create());
1523     if (!env->HasVar(env_vars::kHeadless)) {
1524       GoogleURLTracker* tracker =
1525           GoogleURLTrackerFactory::GetForProfile(profile_);
1526       if (tracker)
1527         tracker->RequestServerCheck(false);
1528     }
1529   }
1530 }
1531
1532 void TemplateURLService::RemoveFromMaps(TemplateURL* template_url) {
1533   const base::string16& keyword = template_url->keyword();
1534   DCHECK_NE(0U, keyword_to_template_map_.count(keyword));
1535   if (keyword_to_template_map_[keyword] == template_url) {
1536     // We need to check whether the keyword can now be provided by another
1537     // TemplateURL.  See the comments in AddToMaps() for more information on
1538     // extension keywords and how they can coexist with non-extension keywords.
1539     // In the case of more than one extension, we use the most recently
1540     // installed (which will be the most recently added, which will have the
1541     // highest ID).
1542     TemplateURL* best_fallback = NULL;
1543     for (TemplateURLVector::const_iterator i(template_urls_.begin());
1544          i != template_urls_.end(); ++i) {
1545       TemplateURL* turl = *i;
1546       // This next statement relies on the fact that there can only be one
1547       // non-Omnibox API TemplateURL with a given keyword.
1548       if ((turl != template_url) && (turl->keyword() == keyword) &&
1549           (!best_fallback ||
1550            (best_fallback->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) ||
1551            ((turl->GetType() == TemplateURL::OMNIBOX_API_EXTENSION) &&
1552             (turl->id() > best_fallback->id()))))
1553         best_fallback = turl;
1554     }
1555     if (best_fallback)
1556       keyword_to_template_map_[keyword] = best_fallback;
1557     else
1558       keyword_to_template_map_.erase(keyword);
1559   }
1560
1561   if (!template_url->sync_guid().empty())
1562     guid_to_template_map_.erase(template_url->sync_guid());
1563   // |provider_map_| is only initialized after loading has completed.
1564   if (loaded_) {
1565     provider_map_->Remove(template_url, search_terms_data());
1566   }
1567 }
1568
1569 void TemplateURLService::AddToMaps(TemplateURL* template_url) {
1570   bool template_url_is_omnibox_api =
1571       template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
1572   const base::string16& keyword = template_url->keyword();
1573   KeywordToTemplateMap::const_iterator i =
1574       keyword_to_template_map_.find(keyword);
1575   if (i == keyword_to_template_map_.end()) {
1576     keyword_to_template_map_[keyword] = template_url;
1577   } else {
1578     const TemplateURL* existing_url = i->second;
1579     // We should only have overlapping keywords when at least one comes from
1580     // an extension.  In that case, the ranking order is:
1581     //   Manually-modified keywords > extension keywords > replaceable keywords
1582     // When there are multiple extensions, the last-added wins.
1583     bool existing_url_is_omnibox_api =
1584         existing_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
1585     DCHECK(existing_url_is_omnibox_api || template_url_is_omnibox_api);
1586     if (existing_url_is_omnibox_api ?
1587         !CanReplace(template_url) : CanReplace(existing_url))
1588       keyword_to_template_map_[keyword] = template_url;
1589   }
1590
1591   if (!template_url->sync_guid().empty())
1592     guid_to_template_map_[template_url->sync_guid()] = template_url;
1593   // |provider_map_| is only initialized after loading has completed.
1594   if (loaded_) {
1595     UIThreadSearchTermsData search_terms_data(profile_);
1596     provider_map_->Add(template_url, search_terms_data);
1597   }
1598 }
1599
1600 // Helper for partition() call in next function.
1601 bool HasValidID(TemplateURL* t_url) {
1602   return t_url->id() != kInvalidTemplateURLID;
1603 }
1604
1605 void TemplateURLService::SetTemplateURLs(TemplateURLVector* urls) {
1606   // Partition the URLs first, instead of implementing the loops below by simply
1607   // scanning the input twice.  While it's not supposed to happen normally, it's
1608   // possible for corrupt databases to return multiple entries with the same
1609   // keyword.  In this case, the first loop may delete the first entry when
1610   // adding the second.  If this happens, the second loop must not attempt to
1611   // access the deleted entry.  Partitioning ensures this constraint.
1612   TemplateURLVector::iterator first_invalid(
1613       std::partition(urls->begin(), urls->end(), HasValidID));
1614
1615   // First, add the items that already have id's, so that the next_id_ gets
1616   // properly set.
1617   for (TemplateURLVector::const_iterator i = urls->begin(); i != first_invalid;
1618        ++i) {
1619     next_id_ = std::max(next_id_, (*i)->id());
1620     AddNoNotify(*i, false);
1621   }
1622
1623   // Next add the new items that don't have id's.
1624   for (TemplateURLVector::const_iterator i = first_invalid; i != urls->end();
1625        ++i)
1626     AddNoNotify(*i, true);
1627
1628   // Clear the input vector to reduce the chance callers will try to use a
1629   // (possibly deleted) entry.
1630   urls->clear();
1631 }
1632
1633 void TemplateURLService::ChangeToLoadedState() {
1634   DCHECK(!loaded_);
1635
1636   UIThreadSearchTermsData search_terms_data(profile_);
1637   provider_map_->Init(template_urls_, search_terms_data);
1638   loaded_ = true;
1639
1640   // This will cause a call to NotifyObservers().
1641   ApplyDefaultSearchChangeNoMetrics(
1642       initial_default_search_provider_ ?
1643           &initial_default_search_provider_->data() : NULL,
1644       default_search_provider_source_);
1645   initial_default_search_provider_.reset();
1646   on_loaded_callbacks_.Notify();
1647 }
1648
1649 bool TemplateURLService::CanReplaceKeywordForHost(
1650     const std::string& host,
1651     TemplateURL** to_replace) {
1652   DCHECK(!to_replace || !*to_replace);
1653   const TemplateURLSet* urls = provider_map_->GetURLsForHost(host);
1654   if (!urls)
1655     return true;
1656   for (TemplateURLSet::const_iterator i(urls->begin()); i != urls->end(); ++i) {
1657     if (CanReplace(*i)) {
1658       if (to_replace)
1659         *to_replace = *i;
1660       return true;
1661     }
1662   }
1663   return false;
1664 }
1665
1666 bool TemplateURLService::CanReplace(const TemplateURL* t_url) {
1667   return (t_url != default_search_provider_ && !t_url->show_in_default_list() &&
1668           t_url->safe_for_autoreplace());
1669 }
1670
1671 TemplateURL* TemplateURLService::FindNonExtensionTemplateURLForKeyword(
1672     const base::string16& keyword) {
1673   TemplateURL* keyword_turl = GetTemplateURLForKeyword(keyword);
1674   if (!keyword_turl || (keyword_turl->GetType() == TemplateURL::NORMAL))
1675     return keyword_turl;
1676   // The extension keyword in the model may be hiding a replaceable
1677   // non-extension keyword.  Look for it.
1678   for (TemplateURLVector::const_iterator i(template_urls_.begin());
1679        i != template_urls_.end(); ++i) {
1680     if (((*i)->GetType() == TemplateURL::NORMAL) &&
1681         ((*i)->keyword() == keyword))
1682       return *i;
1683   }
1684   return NULL;
1685 }
1686
1687 bool TemplateURLService::UpdateNoNotify(
1688     TemplateURL* existing_turl,
1689     const TemplateURL& new_values,
1690     const SearchTermsData& old_search_terms_data) {
1691   DCHECK(existing_turl);
1692   if (std::find(template_urls_.begin(), template_urls_.end(), existing_turl) ==
1693       template_urls_.end())
1694     return false;
1695
1696   base::string16 old_keyword(existing_turl->keyword());
1697   keyword_to_template_map_.erase(old_keyword);
1698   if (!existing_turl->sync_guid().empty())
1699     guid_to_template_map_.erase(existing_turl->sync_guid());
1700
1701   // |provider_map_| is only initialized after loading has completed.
1702   if (loaded_)
1703     provider_map_->Remove(existing_turl, old_search_terms_data);
1704
1705   TemplateURLID previous_id = existing_turl->id();
1706   existing_turl->CopyFrom(new_values);
1707   existing_turl->data_.id = previous_id;
1708
1709   if (loaded_) {
1710     UIThreadSearchTermsData new_search_terms_data(profile_);
1711     provider_map_->Add(existing_turl, new_search_terms_data);
1712   }
1713
1714   const base::string16& keyword = existing_turl->keyword();
1715   KeywordToTemplateMap::const_iterator i =
1716       keyword_to_template_map_.find(keyword);
1717   if (i == keyword_to_template_map_.end()) {
1718     keyword_to_template_map_[keyword] = existing_turl;
1719   } else {
1720     // We can theoretically reach here in two cases:
1721     //   * There is an existing extension keyword and sync brings in a rename of
1722     //     a non-extension keyword to match.  In this case we just need to pick
1723     //     which keyword has priority to update the keyword map.
1724     //   * Autogeneration of the keyword for a Google default search provider
1725     //     at load time causes it to conflict with an existing keyword.  In this
1726     //     case we delete the existing keyword if it's replaceable, or else undo
1727     //     the change in keyword for |existing_turl|.
1728     TemplateURL* existing_keyword_turl = i->second;
1729     if (existing_keyword_turl->GetType() != TemplateURL::NORMAL) {
1730       if (!CanReplace(existing_turl))
1731         keyword_to_template_map_[keyword] = existing_turl;
1732     } else {
1733       if (CanReplace(existing_keyword_turl)) {
1734         RemoveNoNotify(existing_keyword_turl);
1735       } else {
1736         existing_turl->data_.SetKeyword(old_keyword);
1737         keyword_to_template_map_[old_keyword] = existing_turl;
1738       }
1739     }
1740   }
1741   if (!existing_turl->sync_guid().empty())
1742     guid_to_template_map_[existing_turl->sync_guid()] = existing_turl;
1743
1744   if (service_)
1745     service_->UpdateKeyword(existing_turl->data());
1746
1747   // Inform sync of the update.
1748   ProcessTemplateURLChange(
1749       FROM_HERE, existing_turl, syncer::SyncChange::ACTION_UPDATE);
1750
1751   if (default_search_provider_ == existing_turl &&
1752       default_search_provider_source_ == DefaultSearchManager::FROM_USER) {
1753     default_search_manager_.SetUserSelectedDefaultSearchEngine(
1754         default_search_provider_->data());
1755   }
1756   return true;
1757 }
1758
1759 // static
1760 void TemplateURLService::UpdateTemplateURLIfPrepopulated(
1761     TemplateURL* template_url,
1762     Profile* profile) {
1763   int prepopulate_id = template_url->prepopulate_id();
1764   if (template_url->prepopulate_id() == 0)
1765     return;
1766
1767   size_t default_search_index;
1768   ScopedVector<TemplateURLData> prepopulated_urls =
1769       TemplateURLPrepopulateData::GetPrepopulatedEngines(
1770           profile ? profile->GetPrefs() : NULL, &default_search_index);
1771
1772   for (size_t i = 0; i < prepopulated_urls.size(); ++i) {
1773     if (prepopulated_urls[i]->prepopulate_id == prepopulate_id) {
1774       MergeIntoPrepopulatedEngineData(template_url, prepopulated_urls[i]);
1775       template_url->CopyFrom(TemplateURL(*prepopulated_urls[i]));
1776     }
1777   }
1778 }
1779
1780 void TemplateURLService::MaybeUpdateDSEAfterSync(TemplateURL* synced_turl) {
1781   if (GetPrefs() &&
1782       (synced_turl->sync_guid() ==
1783           GetPrefs()->GetString(prefs::kSyncedDefaultSearchProviderGUID))) {
1784     default_search_manager_.SetUserSelectedDefaultSearchEngine(
1785         synced_turl->data());
1786   }
1787 }
1788
1789 PrefService* TemplateURLService::GetPrefs() {
1790   return profile_ ? profile_->GetPrefs() : NULL;
1791 }
1792
1793 void TemplateURLService::UpdateKeywordSearchTermsForURL(
1794     const history::URLVisitedDetails& details) {
1795   const history::URLRow& row = details.row;
1796   if (!row.url().is_valid())
1797     return;
1798
1799   const TemplateURLSet* urls_for_host =
1800       provider_map_->GetURLsForHost(row.url().host());
1801   if (!urls_for_host)
1802     return;
1803
1804   for (TemplateURLSet::const_iterator i = urls_for_host->begin();
1805        i != urls_for_host->end(); ++i) {
1806     base::string16 search_terms;
1807     if ((*i)->ExtractSearchTermsFromURL(row.url(), search_terms_data(),
1808                                         &search_terms) &&
1809         !search_terms.empty()) {
1810       if (content::PageTransitionStripQualifier(details.transition) ==
1811           content::PAGE_TRANSITION_KEYWORD) {
1812         // The visit is the result of the user entering a keyword, generate a
1813         // KEYWORD_GENERATED visit for the KEYWORD so that the keyword typed
1814         // count is boosted.
1815         AddTabToSearchVisit(**i);
1816       }
1817       SetKeywordSearchTermsForURL(*i, row.url(), search_terms);
1818     }
1819   }
1820 }
1821
1822 void TemplateURLService::AddTabToSearchVisit(const TemplateURL& t_url) {
1823   // Only add visits for entries the user hasn't modified. If the user modified
1824   // the entry the keyword may no longer correspond to the host name. It may be
1825   // possible to do something more sophisticated here, but it's so rare as to
1826   // not be worth it.
1827   if (!t_url.safe_for_autoreplace())
1828     return;
1829
1830   if (!profile_)
1831     return;
1832
1833   HistoryService* history =
1834       HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
1835   if (!history)
1836     return;
1837
1838   GURL url(
1839       url_fixer::FixupURL(base::UTF16ToUTF8(t_url.keyword()), std::string()));
1840   if (!url.is_valid())
1841     return;
1842
1843   // Synthesize a visit for the keyword. This ensures the url for the keyword is
1844   // autocompleted even if the user doesn't type the url in directly.
1845   history->AddPage(url, base::Time::Now(), NULL, 0, GURL(),
1846                    history::RedirectList(),
1847                    content::PAGE_TRANSITION_KEYWORD_GENERATED,
1848                    history::SOURCE_BROWSED, false);
1849 }
1850
1851 void TemplateURLService::GoogleBaseURLChanged(const GURL& old_base_url) {
1852   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
1853   bool something_changed = false;
1854   for (TemplateURLVector::iterator i(template_urls_.begin());
1855        i != template_urls_.end(); ++i) {
1856     TemplateURL* t_url = *i;
1857     if (t_url->HasGoogleBaseURLs(search_terms_data())) {
1858       TemplateURL updated_turl(t_url->data());
1859       updated_turl.ResetKeywordIfNecessary(search_terms_data(), false);
1860       KeywordToTemplateMap::const_iterator existing_entry =
1861           keyword_to_template_map_.find(updated_turl.keyword());
1862       if ((existing_entry != keyword_to_template_map_.end()) &&
1863           (existing_entry->second != t_url)) {
1864         // The new autogenerated keyword conflicts with another TemplateURL.
1865         // Overwrite it if it's replaceable; otherwise, leave |t_url| using its
1866         // current keyword.  (This will not prevent |t_url| from auto-updating
1867         // the keyword in the future if the conflicting TemplateURL disappears.)
1868         // Note that we must still update |t_url| in this case, or the
1869         // |provider_map_| will not be updated correctly.
1870         if (CanReplace(existing_entry->second))
1871           RemoveNoNotify(existing_entry->second);
1872         else
1873           updated_turl.data_.SetKeyword(t_url->keyword());
1874       }
1875       something_changed = true;
1876       // This will send the keyword change to sync.  Note that other clients
1877       // need to reset the keyword to an appropriate local value when this
1878       // change arrives; see CreateTemplateURLFromTemplateURLAndSyncData().
1879       UpdateNoNotify(t_url, updated_turl,
1880           OldBaseURLSearchTermsData(profile(), old_base_url.spec()));
1881     }
1882   }
1883   if (something_changed)
1884     NotifyObservers();
1885 }
1886
1887 void TemplateURLService::OnGoogleURLUpdated(GURL old_url, GURL new_url) {
1888   if (loaded_)
1889     GoogleBaseURLChanged(old_url);
1890 }
1891
1892 void TemplateURLService::OnDefaultSearchChange(
1893     const TemplateURLData* data,
1894     DefaultSearchManager::Source source) {
1895   if (GetPrefs() && (source == DefaultSearchManager::FROM_USER) &&
1896       ((source != default_search_provider_source_) ||
1897        !IdenticalSyncGUIDs(data, GetDefaultSearchProvider()))) {
1898     GetPrefs()->SetString(prefs::kSyncedDefaultSearchProviderGUID,
1899                           data->sync_guid);
1900   }
1901   ApplyDefaultSearchChange(data, source);
1902 }
1903
1904 void TemplateURLService::ApplyDefaultSearchChange(
1905     const TemplateURLData* data,
1906     DefaultSearchManager::Source source) {
1907   if (!ApplyDefaultSearchChangeNoMetrics(data, source))
1908     return;
1909
1910   UMA_HISTOGRAM_ENUMERATION(
1911       "Search.DefaultSearchChangeOrigin", dsp_change_origin_, DSP_CHANGE_MAX);
1912
1913   if (GetDefaultSearchProvider() &&
1914       GetDefaultSearchProvider()->HasGoogleBaseURLs(search_terms_data())) {
1915 #if defined(ENABLE_RLZ)
1916     RLZTracker::RecordProductEvent(
1917         rlz_lib::CHROME, RLZTracker::ChromeOmnibox(), rlz_lib::SET_TO_GOOGLE);
1918 #endif
1919   }
1920 }
1921
1922 bool TemplateURLService::ApplyDefaultSearchChangeNoMetrics(
1923     const TemplateURLData* data,
1924     DefaultSearchManager::Source source) {
1925   if (!loaded_) {
1926     // Set |initial_default_search_provider_| from the preferences. This is
1927     // mainly so we can hold ownership until we get to the point where the list
1928     // of keywords from Web Data is the owner of everything including the
1929     // default.
1930     bool changed = TemplateURL::MatchesData(
1931         initial_default_search_provider_.get(), data, search_terms_data());
1932     initial_default_search_provider_.reset(
1933         data ? new TemplateURL(*data) : NULL);
1934     default_search_provider_source_ = source;
1935     return changed;
1936   }
1937
1938   // Prevent recursion if we update the value stored in default_search_manager_.
1939   // Note that we exclude the case of data == NULL because that could cause a
1940   // false positive for recursion when the initial_default_search_provider_ is
1941   // NULL due to policy. We'll never actually get recursion with data == NULL.
1942   if (source == default_search_provider_source_ && data != NULL &&
1943       TemplateURL::MatchesData(default_search_provider_, data,
1944                                search_terms_data()))
1945     return false;
1946
1947   // This may be deleted later. Use exclusively for pointer comparison to detect
1948   // a change.
1949   TemplateURL* previous_default_search_engine = default_search_provider_;
1950
1951   WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
1952   if (default_search_provider_source_ == DefaultSearchManager::FROM_POLICY ||
1953       source == DefaultSearchManager::FROM_POLICY) {
1954     // We do this both to remove any no-longer-applicable policy-defined DSE as
1955     // well as to add the new one, if appropriate.
1956     UpdateProvidersCreatedByPolicy(
1957         &template_urls_,
1958         source == DefaultSearchManager::FROM_POLICY ? data : NULL);
1959   }
1960
1961   if (!data) {
1962     default_search_provider_ = NULL;
1963   } else if (source == DefaultSearchManager::FROM_EXTENSION) {
1964     default_search_provider_ = FindMatchingExtensionTemplateURL(
1965         *data, TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION);
1966   } else if (source == DefaultSearchManager::FROM_FALLBACK) {
1967     default_search_provider_ =
1968         FindPrepopulatedTemplateURL(data->prepopulate_id);
1969     if (default_search_provider_) {
1970       TemplateURLData update_data(*data);
1971       update_data.sync_guid = default_search_provider_->sync_guid();
1972       if (!default_search_provider_->safe_for_autoreplace()) {
1973         update_data.safe_for_autoreplace = false;
1974         update_data.SetKeyword(default_search_provider_->keyword());
1975         update_data.short_name = default_search_provider_->short_name();
1976       }
1977       UpdateNoNotify(default_search_provider_,
1978                      TemplateURL(update_data),
1979                      search_terms_data());
1980     } else {
1981       // Normally the prepopulated fallback should be present in
1982       // |template_urls_|, but in a few cases it might not be:
1983       // (1) Tests that initialize the TemplateURLService in peculiar ways.
1984       // (2) If the user deleted the pre-populated default and we subsequently
1985       // lost their user-selected value.
1986       TemplateURL* new_dse = new TemplateURL(*data);
1987       if (AddNoNotify(new_dse, true))
1988         default_search_provider_ = new_dse;
1989     }
1990   } else if (source == DefaultSearchManager::FROM_USER) {
1991     default_search_provider_ = GetTemplateURLForGUID(data->sync_guid);
1992     if (!default_search_provider_ && data->prepopulate_id) {
1993       default_search_provider_ =
1994           FindPrepopulatedTemplateURL(data->prepopulate_id);
1995     }
1996     TemplateURLData new_data(*data);
1997     new_data.show_in_default_list = true;
1998     if (default_search_provider_) {
1999       UpdateNoNotify(default_search_provider_,
2000                      TemplateURL(new_data),
2001                      search_terms_data());
2002     } else {
2003       new_data.id = kInvalidTemplateURLID;
2004       TemplateURL* new_dse = new TemplateURL(new_data);
2005       if (AddNoNotify(new_dse, true))
2006         default_search_provider_ = new_dse;
2007     }
2008     if (default_search_provider_ && GetPrefs()) {
2009       GetPrefs()->SetString(
2010           prefs::kSyncedDefaultSearchProviderGUID,
2011           default_search_provider_->sync_guid());
2012     }
2013
2014   }
2015
2016   default_search_provider_source_ = source;
2017
2018   bool changed = default_search_provider_ != previous_default_search_engine;
2019
2020   if (profile_ && changed && default_search_provider_ &&
2021       default_search_provider_->HasGoogleBaseURLs(search_terms_data())) {
2022     GoogleURLTracker* tracker =
2023         GoogleURLTrackerFactory::GetForProfile(profile_);
2024     if (tracker)
2025       tracker->RequestServerCheck(false);
2026   }
2027
2028   NotifyObservers();
2029
2030   return changed;
2031 }
2032
2033 bool TemplateURLService::AddNoNotify(TemplateURL* template_url,
2034                                      bool newly_adding) {
2035   DCHECK(template_url);
2036
2037   if (newly_adding) {
2038     DCHECK_EQ(kInvalidTemplateURLID, template_url->id());
2039     DCHECK(std::find(template_urls_.begin(), template_urls_.end(),
2040                      template_url) == template_urls_.end());
2041     template_url->data_.id = ++next_id_;
2042   }
2043
2044   template_url->ResetKeywordIfNecessary(search_terms_data(), false);
2045   // Check whether |template_url|'s keyword conflicts with any already in the
2046   // model.
2047   TemplateURL* existing_keyword_turl =
2048       GetTemplateURLForKeyword(template_url->keyword());
2049
2050   // Check whether |template_url|'s keyword conflicts with any already in the
2051   // model.  Note that we can reach here during the loading phase while
2052   // processing the template URLs from the web data service.  In this case,
2053   // GetTemplateURLForKeyword() will look not only at what's already in the
2054   // model, but at the |initial_default_search_provider_|.  Since this engine
2055   // will presumably also be present in the web data, we need to double-check
2056   // that any "pre-existing" entries we find are actually coming from
2057   // |template_urls_|, lest we detect a "conflict" between the
2058   // |initial_default_search_provider_| and the web data version of itself.
2059   if (existing_keyword_turl &&
2060       (std::find(template_urls_.begin(), template_urls_.end(),
2061                  existing_keyword_turl) != template_urls_.end())) {
2062     DCHECK_NE(existing_keyword_turl, template_url);
2063     // Only replace one of the TemplateURLs if they are either both extensions,
2064     // or both not extensions.
2065     bool are_same_type = existing_keyword_turl->GetType() ==
2066         template_url->GetType();
2067     if (CanReplace(existing_keyword_turl) && are_same_type) {
2068       RemoveNoNotify(existing_keyword_turl);
2069     } else if (CanReplace(template_url) && are_same_type) {
2070       delete template_url;
2071       return false;
2072     } else {
2073       base::string16 new_keyword =
2074           UniquifyKeyword(*existing_keyword_turl, false);
2075       ResetTemplateURLNoNotify(existing_keyword_turl,
2076                                existing_keyword_turl->short_name(), new_keyword,
2077                                existing_keyword_turl->url());
2078     }
2079   }
2080   template_urls_.push_back(template_url);
2081   AddToMaps(template_url);
2082
2083   if (newly_adding &&
2084       (template_url->GetType() !=
2085           TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)) {
2086     if (service_)
2087       service_->AddKeyword(template_url->data());
2088
2089     // Inform sync of the addition. Note that this will assign a GUID to
2090     // template_url and add it to the guid_to_template_map_.
2091     ProcessTemplateURLChange(FROM_HERE,
2092                              template_url,
2093                              syncer::SyncChange::ACTION_ADD);
2094   }
2095
2096   return true;
2097 }
2098
2099 void TemplateURLService::RemoveNoNotify(TemplateURL* template_url) {
2100   DCHECK(template_url != default_search_provider_);
2101
2102   TemplateURLVector::iterator i =
2103       std::find(template_urls_.begin(), template_urls_.end(), template_url);
2104   if (i == template_urls_.end())
2105     return;
2106
2107   RemoveFromMaps(template_url);
2108
2109   // Remove it from the vector containing all TemplateURLs.
2110   template_urls_.erase(i);
2111
2112   if (template_url->GetType() != TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION) {
2113     if (service_)
2114       service_->RemoveKeyword(template_url->id());
2115
2116     // Inform sync of the deletion.
2117     ProcessTemplateURLChange(FROM_HERE,
2118                              template_url,
2119                              syncer::SyncChange::ACTION_DELETE);
2120
2121     UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
2122                               DELETE_ENGINE_USER_ACTION, DELETE_ENGINE_MAX);
2123   }
2124
2125   if (loaded_ && profile_) {
2126     content::Source<Profile> source(profile_);
2127     TemplateURLID id = template_url->id();
2128     content::NotificationService::current()->Notify(
2129         chrome::NOTIFICATION_TEMPLATE_URL_REMOVED,
2130         source,
2131         content::Details<TemplateURLID>(&id));
2132   }
2133
2134   // We own the TemplateURL and need to delete it.
2135   delete template_url;
2136 }
2137
2138 bool TemplateURLService::ResetTemplateURLNoNotify(
2139     TemplateURL* url,
2140     const base::string16& title,
2141     const base::string16& keyword,
2142     const std::string& search_url) {
2143   DCHECK(!keyword.empty());
2144   DCHECK(!search_url.empty());
2145   TemplateURLData data(url->data());
2146   data.short_name = title;
2147   data.SetKeyword(keyword);
2148   if (search_url != data.url()) {
2149     data.SetURL(search_url);
2150     // The urls have changed, reset the favicon url.
2151     data.favicon_url = GURL();
2152   }
2153   data.safe_for_autoreplace = false;
2154   data.last_modified = time_provider_();
2155   return UpdateNoNotify(url, TemplateURL(data), search_terms_data());
2156 }
2157
2158 void TemplateURLService::NotifyObservers() {
2159   if (!loaded_)
2160     return;
2161
2162   FOR_EACH_OBSERVER(TemplateURLServiceObserver, model_observers_,
2163                     OnTemplateURLServiceChanged());
2164 }
2165
2166 // |template_urls| are the TemplateURLs loaded from the database.
2167 // |default_from_prefs| is the default search provider from the preferences, or
2168 // NULL if the DSE is not policy-defined.
2169 //
2170 // This function removes from the vector and the database all the TemplateURLs
2171 // that were set by policy, unless it is the current default search provider, in
2172 // which case it is updated with the data from prefs.
2173 void TemplateURLService::UpdateProvidersCreatedByPolicy(
2174     TemplateURLVector* template_urls,
2175     const TemplateURLData* default_from_prefs) {
2176   DCHECK(template_urls);
2177
2178   for (TemplateURLVector::iterator i = template_urls->begin();
2179        i != template_urls->end(); ) {
2180     TemplateURL* template_url = *i;
2181     if (template_url->created_by_policy()) {
2182       if (default_from_prefs &&
2183           TemplateURL::MatchesData(template_url, default_from_prefs,
2184                                    search_terms_data())) {
2185         // If the database specified a default search provider that was set
2186         // by policy, and the default search provider from the preferences
2187         // is also set by policy and they are the same, keep the entry in the
2188         // database and the |default_search_provider|.
2189         default_search_provider_ = template_url;
2190         // Prevent us from saving any other entries, or creating a new one.
2191         default_from_prefs = NULL;
2192         ++i;
2193         continue;
2194       }
2195
2196       RemoveFromMaps(template_url);
2197       i = template_urls->erase(i);
2198       if (service_)
2199         service_->RemoveKeyword(template_url->id());
2200       delete template_url;
2201     } else {
2202       ++i;
2203     }
2204   }
2205
2206   if (default_from_prefs) {
2207     default_search_provider_ = NULL;
2208     default_search_provider_source_ = DefaultSearchManager::FROM_POLICY;
2209     TemplateURLData new_data(*default_from_prefs);
2210     if (new_data.sync_guid.empty())
2211       new_data.sync_guid = base::GenerateGUID();
2212     new_data.created_by_policy = true;
2213     TemplateURL* new_dse = new TemplateURL(new_data);
2214     if (AddNoNotify(new_dse, true))
2215       default_search_provider_ = new_dse;
2216   }
2217 }
2218
2219 void TemplateURLService::ResetTemplateURLGUID(TemplateURL* url,
2220                                               const std::string& guid) {
2221   DCHECK(loaded_);
2222   DCHECK(!guid.empty());
2223
2224   TemplateURLData data(url->data());
2225   data.sync_guid = guid;
2226   UpdateNoNotify(url, TemplateURL(data), search_terms_data());
2227 }
2228
2229 base::string16 TemplateURLService::UniquifyKeyword(const TemplateURL& turl,
2230                                                    bool force) {
2231   if (!force) {
2232     // Already unique.
2233     if (!GetTemplateURLForKeyword(turl.keyword()))
2234       return turl.keyword();
2235
2236     // First, try to return the generated keyword for the TemplateURL (except
2237     // for extensions, as their keywords are not associated with their URLs).
2238     GURL gurl(turl.url());
2239     if (gurl.is_valid() &&
2240         (turl.GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
2241       base::string16 keyword_candidate = TemplateURL::GenerateKeyword(gurl);
2242       if (!GetTemplateURLForKeyword(keyword_candidate))
2243         return keyword_candidate;
2244     }
2245   }
2246
2247   // We try to uniquify the keyword by appending a special character to the end.
2248   // This is a best-effort approach where we try to preserve the original
2249   // keyword and let the user do what they will after our attempt.
2250   base::string16 keyword_candidate(turl.keyword());
2251   do {
2252     keyword_candidate.append(base::ASCIIToUTF16("_"));
2253   } while (GetTemplateURLForKeyword(keyword_candidate));
2254
2255   return keyword_candidate;
2256 }
2257
2258 bool TemplateURLService::IsLocalTemplateURLBetter(
2259     const TemplateURL* local_turl,
2260     const TemplateURL* sync_turl) {
2261   DCHECK(GetTemplateURLForGUID(local_turl->sync_guid()));
2262   return local_turl->last_modified() > sync_turl->last_modified() ||
2263          local_turl->created_by_policy() ||
2264          local_turl== GetDefaultSearchProvider();
2265 }
2266
2267 void TemplateURLService::ResolveSyncKeywordConflict(
2268     TemplateURL* unapplied_sync_turl,
2269     TemplateURL* applied_sync_turl,
2270     syncer::SyncChangeList* change_list) {
2271   DCHECK(loaded_);
2272   DCHECK(unapplied_sync_turl);
2273   DCHECK(applied_sync_turl);
2274   DCHECK(change_list);
2275   DCHECK_EQ(applied_sync_turl->keyword(), unapplied_sync_turl->keyword());
2276   DCHECK_NE(TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION,
2277             applied_sync_turl->GetType());
2278
2279   // Both |unapplied_sync_turl| and |applied_sync_turl| are known to Sync, so
2280   // don't delete either of them. Instead, determine which is "better" and
2281   // uniquify the other one, sending an update to the server for the updated
2282   // entry.
2283   const bool applied_turl_is_better =
2284       IsLocalTemplateURLBetter(applied_sync_turl, unapplied_sync_turl);
2285   TemplateURL* loser = applied_turl_is_better ?
2286       unapplied_sync_turl : applied_sync_turl;
2287   base::string16 new_keyword = UniquifyKeyword(*loser, false);
2288   DCHECK(!GetTemplateURLForKeyword(new_keyword));
2289   if (applied_turl_is_better) {
2290     // Just set the keyword of |unapplied_sync_turl|. The caller is responsible
2291     // for adding or updating unapplied_sync_turl in the local model.
2292     unapplied_sync_turl->data_.SetKeyword(new_keyword);
2293   } else {
2294     // Update |applied_sync_turl| in the local model with the new keyword.
2295     TemplateURLData data(applied_sync_turl->data());
2296     data.SetKeyword(new_keyword);
2297     if (UpdateNoNotify(
2298             applied_sync_turl, TemplateURL(data), search_terms_data()))
2299       NotifyObservers();
2300   }
2301   // The losing TemplateURL should have their keyword updated. Send a change to
2302   // the server to reflect this change.
2303   syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*loser);
2304   change_list->push_back(syncer::SyncChange(FROM_HERE,
2305       syncer::SyncChange::ACTION_UPDATE,
2306       sync_data));
2307 }
2308
2309 void TemplateURLService::MergeInSyncTemplateURL(
2310     TemplateURL* sync_turl,
2311     const SyncDataMap& sync_data,
2312     syncer::SyncChangeList* change_list,
2313     SyncDataMap* local_data,
2314     syncer::SyncMergeResult* merge_result) {
2315   DCHECK(sync_turl);
2316   DCHECK(!GetTemplateURLForGUID(sync_turl->sync_guid()));
2317   DCHECK(IsFromSync(sync_turl, sync_data));
2318
2319   TemplateURL* conflicting_turl =
2320       FindNonExtensionTemplateURLForKeyword(sync_turl->keyword());
2321   bool should_add_sync_turl = true;
2322
2323   // If there was no TemplateURL in the local model that conflicts with
2324   // |sync_turl|, skip the following preparation steps and just add |sync_turl|
2325   // directly. Otherwise, modify |conflicting_turl| to make room for
2326   // |sync_turl|.
2327   if (conflicting_turl) {
2328     if (IsFromSync(conflicting_turl, sync_data)) {
2329       // |conflicting_turl| is already known to Sync, so we're not allowed to
2330       // remove it. In this case, we want to uniquify the worse one and send an
2331       // update for the changed keyword to sync. We can reuse the logic from
2332       // ResolveSyncKeywordConflict for this.
2333       ResolveSyncKeywordConflict(sync_turl, conflicting_turl, change_list);
2334       merge_result->set_num_items_modified(
2335           merge_result->num_items_modified() + 1);
2336     } else {
2337       // |conflicting_turl| is not yet known to Sync. If it is better, then we
2338       // want to transfer its values up to sync. Otherwise, we remove it and
2339       // allow the entry from Sync to overtake it in the model.
2340       const std::string guid = conflicting_turl->sync_guid();
2341       if (IsLocalTemplateURLBetter(conflicting_turl, sync_turl)) {
2342         ResetTemplateURLGUID(conflicting_turl, sync_turl->sync_guid());
2343         syncer::SyncData sync_data =
2344             CreateSyncDataFromTemplateURL(*conflicting_turl);
2345         change_list->push_back(syncer::SyncChange(
2346             FROM_HERE, syncer::SyncChange::ACTION_UPDATE, sync_data));
2347         // Note that in this case we do not add the Sync TemplateURL to the
2348         // local model, since we've effectively "merged" it in by updating the
2349         // local conflicting entry with its sync_guid.
2350         should_add_sync_turl = false;
2351         merge_result->set_num_items_modified(
2352             merge_result->num_items_modified() + 1);
2353       } else {
2354         // We guarantee that this isn't the local search provider. Otherwise,
2355         // local would have won.
2356         DCHECK(conflicting_turl != GetDefaultSearchProvider());
2357         Remove(conflicting_turl);
2358         merge_result->set_num_items_deleted(
2359             merge_result->num_items_deleted() + 1);
2360       }
2361       // This TemplateURL was either removed or overwritten in the local model.
2362       // Remove the entry from the local data so it isn't pushed up to Sync.
2363       local_data->erase(guid);
2364     }
2365   }
2366
2367   if (should_add_sync_turl) {
2368     // Force the local ID to kInvalidTemplateURLID so we can add it.
2369     TemplateURLData data(sync_turl->data());
2370     data.id = kInvalidTemplateURLID;
2371     TemplateURL* added = new TemplateURL(data);
2372     base::AutoReset<DefaultSearchChangeOrigin> change_origin(
2373         &dsp_change_origin_, DSP_CHANGE_SYNC_ADD);
2374     if (Add(added))
2375       MaybeUpdateDSEAfterSync(added);
2376     merge_result->set_num_items_added(
2377         merge_result->num_items_added() + 1);
2378   }
2379 }
2380
2381 void TemplateURLService::PatchMissingSyncGUIDs(
2382     TemplateURLVector* template_urls) {
2383   DCHECK(template_urls);
2384   for (TemplateURLVector::iterator i = template_urls->begin();
2385        i != template_urls->end(); ++i) {
2386     TemplateURL* template_url = *i;
2387     DCHECK(template_url);
2388     if (template_url->sync_guid().empty() &&
2389         (template_url->GetType() !=
2390             TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)) {
2391       template_url->data_.sync_guid = base::GenerateGUID();
2392       if (service_)
2393         service_->UpdateKeyword(template_url->data());
2394     }
2395   }
2396 }
2397
2398 void TemplateURLService::OnSyncedDefaultSearchProviderGUIDChanged() {
2399   base::AutoReset<DefaultSearchChangeOrigin> change_origin(
2400       &dsp_change_origin_, DSP_CHANGE_SYNC_PREF);
2401
2402   std::string new_guid =
2403       GetPrefs()->GetString(prefs::kSyncedDefaultSearchProviderGUID);
2404   if (new_guid.empty()) {
2405     default_search_manager_.ClearUserSelectedDefaultSearchEngine();
2406     return;
2407   }
2408
2409   TemplateURL* turl = GetTemplateURLForGUID(new_guid);
2410   if (turl)
2411     default_search_manager_.SetUserSelectedDefaultSearchEngine(turl->data());
2412 }
2413
2414 TemplateURL* TemplateURLService::FindPrepopulatedTemplateURL(
2415     int prepopulated_id) {
2416   for (TemplateURLVector::const_iterator i = template_urls_.begin();
2417        i != template_urls_.end(); ++i) {
2418     if ((*i)->prepopulate_id() == prepopulated_id)
2419       return *i;
2420   }
2421   return NULL;
2422 }
2423
2424 TemplateURL* TemplateURLService::CreateTemplateURLForExtension(
2425     const ExtensionKeyword& extension_keyword) {
2426   TemplateURLData data;
2427   data.short_name = base::UTF8ToUTF16(extension_keyword.extension_name);
2428   data.SetKeyword(base::UTF8ToUTF16(extension_keyword.extension_keyword));
2429   // This URL is not actually used for navigation. It holds the extension's
2430   // ID, as well as forcing the TemplateURL to be treated as a search keyword.
2431   data.SetURL(std::string(extensions::kExtensionScheme) + "://" +
2432       extension_keyword.extension_id + "/?q={searchTerms}");
2433   return new TemplateURL(data);
2434 }
2435
2436 TemplateURL* TemplateURLService::FindTemplateURLForExtension(
2437     const std::string& extension_id,
2438     TemplateURL::Type type) {
2439   DCHECK_NE(TemplateURL::NORMAL, type);
2440   for (TemplateURLVector::const_iterator i = template_urls_.begin();
2441        i != template_urls_.end(); ++i) {
2442     if ((*i)->GetType() == type &&
2443         (*i)->GetExtensionId() == extension_id)
2444       return *i;
2445   }
2446   return NULL;
2447 }
2448
2449 TemplateURL* TemplateURLService::FindMatchingExtensionTemplateURL(
2450     const TemplateURLData& data,
2451     TemplateURL::Type type) {
2452   DCHECK_NE(TemplateURL::NORMAL, type);
2453   for (TemplateURLVector::const_iterator i = template_urls_.begin();
2454        i != template_urls_.end(); ++i) {
2455     if ((*i)->GetType() == type &&
2456         TemplateURL::MatchesData(*i, &data, search_terms_data()))
2457       return *i;
2458   }
2459   return NULL;
2460 }
2461
2462 void TemplateURLService::UpdateExtensionDefaultSearchEngine() {
2463   TemplateURL* most_recently_intalled_default = NULL;
2464   for (TemplateURLVector::const_iterator i = template_urls_.begin();
2465        i != template_urls_.end(); ++i) {
2466     if (((*i)->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION) &&
2467         (*i)->extension_info_->wants_to_be_default_engine &&
2468         (*i)->SupportsReplacement(search_terms_data()) &&
2469         (!most_recently_intalled_default ||
2470          (most_recently_intalled_default->extension_info_->install_time <
2471              (*i)->extension_info_->install_time)))
2472       most_recently_intalled_default = *i;
2473   }
2474
2475   if (most_recently_intalled_default) {
2476     base::AutoReset<DefaultSearchChangeOrigin> change_origin(
2477         &dsp_change_origin_, DSP_CHANGE_OVERRIDE_SETTINGS_EXTENSION);
2478     default_search_manager_.SetExtensionControlledDefaultSearchEngine(
2479         most_recently_intalled_default->data());
2480   } else {
2481     default_search_manager_.ClearExtensionControlledDefaultSearchEngine();
2482   }
2483 }