root/chrome/browser/search_engines/template_url_service.cc

DEFINITIONS

1. TemplateURLsHaveSamePrefs
2. FirstPotentialDefaultEngine
3. ShouldRemoveSyncChange
4. PruneSyncChanges
5. old_base_url
6. GoogleBaseURLValue
7. IsFromSync
8. LogDuplicatesHistogram
9. extension_keyword
10. dsp_change_origin_
11. dsp_change_origin_
12. GenerateKeyword
13. CleanUserInputKeyword
14. GenerateSearchURL
15. GenerateSearchURLUsingTermsData
16. CanReplaceKeyword
17. FindMatchingKeywords
18. GetTemplateURLForKeyword
19. GetTemplateURLForGUID
20. GetTemplateURLForHost
21. Add
22. AddAndSetProfile
23. AddWithOverrides
24. AddExtensionControlledTURL
25. Remove
26. RemoveExtensionControlledTURL
27. RemoveAutoGeneratedSince
28. RemoveAutoGeneratedBetween
29. RemoveAutoGeneratedForOriginBetween
30. RegisterOmniboxKeyword
31. UnregisterOmniboxKeyword
32. GetTemplateURLs
33. IncrementUsageCount
34. ResetTemplateURL
35. CanMakeDefault
36. SetDefaultSearchProvider
37. GetDefaultSearchProvider
38. IsSearchResultsPageFromDefaultSearchProvider
39. IsExtensionControlledDefaultSearch
40. FindNewDefaultSearchProvider
41. RepairPrepopulatedSearchEngines
42. AddObserver
43. RemoveObserver
44. Load
45. RegisterOnLoadedCallback
46. OnWebDataServiceRequestDone
47. GetKeywordShortName
48. Observe
49. Shutdown
50. OnSyncedDefaultSearchProviderGUIDChanged
51. GetAllSyncData
52. ProcessSyncChanges
53. MergeDataAndStartSyncing
54. StopSyncing
55. ProcessTemplateURLChange
56. CreateSyncDataFromTemplateURL
57. CreateTemplateURLFromTemplateURLAndSyncData
58. CreateGUIDToSyncDataMap
59. SetKeywordSearchTermsForURL
60. Init
61. RemoveFromMaps
62. AddToMaps
63. HasValidID
64. SetTemplateURLs
65. ChangeToLoadedState
66. SaveDefaultSearchProviderToPrefs
67. LoadDefaultSearchProviderFromPrefs
68. ClearDefaultProviderFromPrefs
69. CanReplaceKeywordForHost
70. CanReplace
71. FindNonExtensionTemplateURLForKeyword
72. UpdateNoNotify
73. UpdateTemplateURLIfPrepopulated
74. GetPrefs
75. UpdateKeywordSearchTermsForURL
76. AddTabToSearchVisit
77. GoogleBaseURLChanged
78. UpdateDefaultSearch
79. SetDefaultSearchProviderNoNotify
80. AddNoNotify
81. RemoveNoNotify
82. NotifyObservers
83. RemoveProvidersCreatedByPolicy
84. ResetTemplateURLGUID
85. UniquifyKeyword
86. IsLocalTemplateURLBetter
87. ResolveSyncKeywordConflict
88. MergeInSyncTemplateURL
89. SetDefaultSearchProviderIfNewlySynced
90. GetPendingSyncedDefaultSearchProvider
91. PatchMissingSyncGUIDs
92. AddTemplateURLsAndSetupDefaultEngine
93. EnsureDefaultSearchProviderExists
94. CreateTemplateURLForExtension
95. FindTemplateURLForExtension
96. FindExtensionDefaultSearchEngine
97. SetDefaultSearchProviderAfterRemovingDefaultExtension

// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "chrome/browser/search_engines/template_url_service.h"

#include <algorithm>
#include <utility>

#include "base/auto_reset.h"
#include "base/command_line.h"
#include "base/compiler_specific.h"
#include "base/environment.h"
#include "base/guid.h"
#include "base/i18n/case_conversion.h"
#include "base/memory/scoped_vector.h"
#include "base/metrics/histogram.h"
#include "base/prefs/pref_service.h"
#include "base/stl_util.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_split.h"
#include "base/strings/string_util.h"
#include "base/strings/utf_string_conversions.h"
#include "base/time/time.h"
#include "chrome/browser/chrome_notification_types.h"
#include "chrome/browser/extensions/extension_service.h"
#include "chrome/browser/google/google_url_tracker.h"
#include "chrome/browser/history/history_notifications.h"
#include "chrome/browser/history/history_service.h"
#include "chrome/browser/history/history_service_factory.h"
#include "chrome/browser/profiles/profile.h"
#include "chrome/browser/rlz/rlz.h"
#include "chrome/browser/search_engines/search_host_to_urls_map.h"
#include "chrome/browser/search_engines/search_terms_data.h"
#include "chrome/browser/search_engines/template_url.h"
#include "chrome/browser/search_engines/template_url_prepopulate_data.h"
#include "chrome/browser/search_engines/template_url_service_observer.h"
#include "chrome/browser/search_engines/util.h"
#include "chrome/browser/webdata/web_data_service.h"
#include "chrome/common/chrome_switches.h"
#include "chrome/common/env_vars.h"
#include "chrome/common/extensions/api/omnibox/omnibox_handler.h"
#include "chrome/common/net/url_fixer_upper.h"
#include "chrome/common/pref_names.h"
#include "chrome/common/url_constants.h"
#include "content/public/browser/notification_service.h"
#include "extensions/common/constants.h"
#include "net/base/net_util.h"
#include "sync/api/sync_change.h"
#include "sync/api/sync_error_factory.h"
#include "sync/protocol/search_engine_specifics.pb.h"
#include "sync/protocol/sync.pb.h"
#include "ui/base/l10n/l10n_util.h"

typedef SearchHostToURLsMap::TemplateURLSet TemplateURLSet;
typedef TemplateURLService::SyncDataMap SyncDataMap;

namespace {

bool TemplateURLsHaveSamePrefs(const TemplateURL* url1,
                               const TemplateURL* url2) {
  if (url1 == url2)
    return true;
  return (url1 != NULL) && (url2 != NULL) &&
      (url1->short_name() == url2->short_name()) &&
      url1->HasSameKeywordAs(*url2) &&
      (url1->url() == url2->url()) &&
      (url1->suggestions_url() == url2->suggestions_url()) &&
      (url1->instant_url() == url2->instant_url()) &&
      (url1->image_url() == url2->image_url()) &&
      (url1->new_tab_url() == url2->new_tab_url()) &&
      (url1->search_url_post_params() == url2->search_url_post_params()) &&
      (url1->suggestions_url_post_params() ==
          url2->suggestions_url_post_params()) &&
      (url1->instant_url_post_params() == url2->instant_url_post_params()) &&
      (url1->image_url_post_params() == url2->image_url_post_params()) &&
      (url1->favicon_url() == url2->favicon_url()) &&
      (url1->safe_for_autoreplace() == url2->safe_for_autoreplace()) &&
      (url1->show_in_default_list() == url2->show_in_default_list()) &&
      (url1->input_encodings() == url2->input_encodings()) &&
      (url1->alternate_urls() == url2->alternate_urls()) &&
      (url1->search_terms_replacement_key() ==
          url2->search_terms_replacement_key());
}

const char kFirstPotentialEngineHistogramName[] =
    "Search.FirstPotentialEngineCalled";

// Values for an enumerated histogram used to track whenever
// FirstPotentialDefaultEngine is called, and from where.
enum FirstPotentialEngineCaller {
  FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP,
  FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_PROCESSING_SYNC_CHANGES,
  FIRST_POTENTIAL_CALLSITE_ON_LOAD,
  FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_SYNCING,
  FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_NOT_SYNCING,
  FIRST_POTENTIAL_CALLSITE_MAX,
};

const char kDeleteSyncedEngineHistogramName[] =
    "Search.DeleteSyncedSearchEngine";

// Values for an enumerated histogram used to track whenever an ACTION_DELETE is
// sent to the server for search engines.
enum DeleteSyncedSearchEngineEvent {
  DELETE_ENGINE_USER_ACTION,
  DELETE_ENGINE_PRE_SYNC,
  DELETE_ENGINE_EMPTY_FIELD,
  DELETE_ENGINE_MAX,
};

TemplateURL* FirstPotentialDefaultEngine(
    const TemplateURLService::TemplateURLVector& template_urls) {
  for (TemplateURLService::TemplateURLVector::const_iterator i(
       template_urls.begin()); i != template_urls.end(); ++i) {
    if ((*i)->ShowInDefaultList() &&
        ((*i)->GetType() == TemplateURL::NORMAL))
      return *i;
  }
  return NULL;
}

// Returns true iff the change in |change_list| at index |i| should not be sent
// up to the server based on its GUIDs presence in |sync_data| or when compared
// to changes after it in |change_list|.
// The criteria is:
//  1) It is an ACTION_UPDATE or ACTION_DELETE and the sync_guid associated
//     with it is NOT found in |sync_data|. We can only update and remove
//     entries that were originally from the Sync server.
//  2) It is an ACTION_ADD and the sync_guid associated with it is found in
//     |sync_data|. We cannot re-add entries that Sync already knew about.
//  3) There is an update after an update for the same GUID. We prune earlier
//     ones just to save bandwidth (Sync would normally coalesce them).
bool ShouldRemoveSyncChange(size_t index,
                            syncer::SyncChangeList* change_list,
                            const SyncDataMap* sync_data) {
  DCHECK(index < change_list->size());
  const syncer::SyncChange& change_i = (*change_list)[index];
  const std::string guid = change_i.sync_data().GetSpecifics()
      .search_engine().sync_guid();
  syncer::SyncChange::SyncChangeType type = change_i.change_type();
  if ((type == syncer::SyncChange::ACTION_UPDATE ||
       type == syncer::SyncChange::ACTION_DELETE) &&
       sync_data->find(guid) == sync_data->end())
    return true;
  if (type == syncer::SyncChange::ACTION_ADD &&
      sync_data->find(guid) != sync_data->end())
    return true;
  if (type == syncer::SyncChange::ACTION_UPDATE) {
    for (size_t j = index + 1; j < change_list->size(); j++) {
      const syncer::SyncChange& change_j = (*change_list)[j];
      if ((syncer::SyncChange::ACTION_UPDATE == change_j.change_type()) &&
          (change_j.sync_data().GetSpecifics().search_engine().sync_guid() ==
              guid))
        return true;
    }
  }
  return false;
}

// Remove SyncChanges that should not be sent to the server from |change_list|.
// This is done to eliminate incorrect SyncChanges added by the merge and
// conflict resolution logic when it is unsure of whether or not an entry is new
// from Sync or originally from the local model. This also removes changes that
// would be otherwise be coalesced by Sync in order to save bandwidth.
void PruneSyncChanges(const SyncDataMap* sync_data,
                      syncer::SyncChangeList* change_list) {
  for (size_t i = 0; i < change_list->size(); ) {
    if (ShouldRemoveSyncChange(i, change_list, sync_data))
      change_list->erase(change_list->begin() + i);
    else
      ++i;
  }
}

// Helper class that reports a specific string as the Google base URL.  We use
// this so that code can calculate a TemplateURL's previous search URL after a
// change to the global base URL.
class OldBaseURLSearchTermsData : public UIThreadSearchTermsData {
 public:
  OldBaseURLSearchTermsData(Profile* profile, const std::string& old_base_url);
  virtual ~OldBaseURLSearchTermsData();

  virtual std::string GoogleBaseURLValue() const OVERRIDE;

 private:
  std::string old_base_url;
};

OldBaseURLSearchTermsData::OldBaseURLSearchTermsData(
    Profile* profile,
    const std::string& old_base_url)
    : UIThreadSearchTermsData(profile),
      old_base_url(old_base_url) {
}

OldBaseURLSearchTermsData::~OldBaseURLSearchTermsData() {
}

std::string OldBaseURLSearchTermsData::GoogleBaseURLValue() const {
  return old_base_url;
}

// Returns true if |turl|'s GUID is not found inside |sync_data|. This is to be
// used in MergeDataAndStartSyncing to differentiate between TemplateURLs from
// Sync and TemplateURLs that were initially local, assuming |sync_data| is the
// |initial_sync_data| parameter.
bool IsFromSync(const TemplateURL* turl, const SyncDataMap& sync_data) {
  return !!sync_data.count(turl->sync_guid());
}

// Log the number of instances of a keyword that exist, with zero or more
// underscores, which could occur as the result of conflict resolution.
void LogDuplicatesHistogram(
    const TemplateURLService::TemplateURLVector& template_urls) {
  std::map<std::string, int> duplicates;
  for (TemplateURLService::TemplateURLVector::const_iterator it =
      template_urls.begin(); it != template_urls.end(); ++it) {
    std::string keyword = base::UTF16ToASCII((*it)->keyword());
    base::TrimString(keyword, "_", &keyword);
    duplicates[keyword]++;
  }

  // Count the keywords with duplicates.
  int num_dupes = 0;
  for (std::map<std::string, int>::const_iterator it = duplicates.begin();
      it != duplicates.end(); ++it) {
    if (it->second > 1)
      num_dupes++;
  }

  UMA_HISTOGRAM_COUNTS_100("Search.SearchEngineDuplicateCounts", num_dupes);
}

}  // namespace


// TemplateURLService::ExtensionKeyword ---------------------------------------

TemplateURLService::ExtensionKeyword::ExtensionKeyword(
    const std::string& id,
    const std::string& name,
    const std::string& keyword)
    : extension_id(id),
      extension_name(name),
      extension_keyword(keyword) {
}

TemplateURLService::ExtensionKeyword::~ExtensionKeyword() {}


// TemplateURLService::LessWithPrefix -----------------------------------------

class TemplateURLService::LessWithPrefix {
 public:
  // We want to find the set of keywords that begin with a prefix.  The STL
  // algorithms will return the set of elements that are "equal to" the
  // prefix, where "equal(x, y)" means "!(cmp(x, y) || cmp(y, x))".  When
  // cmp() is the typical std::less<>, this results in lexicographic equality;
  // we need to extend this to mark a prefix as "not less than" a keyword it
  // begins, which will cause the desired elements to be considered "equal to"
  // the prefix.  Note: this is still a strict weak ordering, as required by
  // equal_range() (though I will not prove that here).
  //
  // Unfortunately the calling convention is not "prefix and element" but
  // rather "two elements", so we pass the prefix as a fake "element" which has
  // a NULL KeywordDataElement pointer.
  bool operator()(const KeywordToTemplateMap::value_type& elem1,
                  const KeywordToTemplateMap::value_type& elem2) const {
    return (elem1.second == NULL) ?
        (elem2.first.compare(0, elem1.first.length(), elem1.first) > 0) :
        (elem1.first < elem2.first);
  }
};


// TemplateURLService ---------------------------------------------------------

TemplateURLService::TemplateURLService(Profile* profile)
    : provider_map_(new SearchHostToURLsMap),
      profile_(profile),
      loaded_(false),
      load_failed_(false),
      load_handle_(0),
      default_search_provider_(NULL),
      is_default_search_managed_(false),
      next_id_(kInvalidTemplateURLID + 1),
      time_provider_(&base::Time::Now),
      models_associated_(false),
      processing_syncer_changes_(false),
      pending_synced_default_search_(false),
      dsp_change_origin_(DSP_CHANGE_OTHER) {
  DCHECK(profile_);
  Init(NULL, 0);
}

TemplateURLService::TemplateURLService(const Initializer* initializers,
                                       const int count)
    : provider_map_(new SearchHostToURLsMap),
      profile_(NULL),
      loaded_(false),
      load_failed_(false),
      load_handle_(0),
      service_(NULL),
      default_search_provider_(NULL),
      is_default_search_managed_(false),
      next_id_(kInvalidTemplateURLID + 1),
      time_provider_(&base::Time::Now),
      models_associated_(false),
      processing_syncer_changes_(false),
      pending_synced_default_search_(false),
      dsp_change_origin_(DSP_CHANGE_OTHER) {
  Init(initializers, count);
}

TemplateURLService::~TemplateURLService() {
  // |service_| should be deleted during Shutdown().
  DCHECK(!service_);
  STLDeleteElements(&template_urls_);
}

// static
base::string16 TemplateURLService::GenerateKeyword(const GURL& url) {
  DCHECK(url.is_valid());
  // Strip "www." off the front of the keyword; otherwise the keyword won't work
  // properly.  See http://code.google.com/p/chromium/issues/detail?id=6984 .
  // Special case: if the host was exactly "www." (not sure this can happen but
  // perhaps with some weird intranet and custom DNS server?), ensure we at
  // least don't return the empty string.
  base::string16 keyword(net::StripWWWFromHost(url));
  return keyword.empty() ? base::ASCIIToUTF16("www") : keyword;
}

// static
base::string16 TemplateURLService::CleanUserInputKeyword(
    const base::string16& keyword) {
  // Remove the scheme.
  base::string16 result(base::i18n::ToLower(keyword));
  base::TrimWhitespace(result, base::TRIM_ALL, &result);
  url_parse::Component scheme_component;
  if (url_parse::ExtractScheme(base::UTF16ToUTF8(keyword).c_str(),
                               static_cast<int>(keyword.length()),
                               &scheme_component)) {
    // If the scheme isn't "http" or "https", bail.  The user isn't trying to
    // type a web address, but rather an FTP, file:, or other scheme URL, or a
    // search query with some sort of initial operator (e.g. "site:").
    if (result.compare(0, scheme_component.end(),
                       base::ASCIIToUTF16(content::kHttpScheme)) &&
        result.compare(0, scheme_component.end(),
                       base::ASCIIToUTF16(content::kHttpsScheme)))
      return base::string16();

    // Include trailing ':'.
    result.erase(0, scheme_component.end() + 1);
    // Many schemes usually have "//" after them, so strip it too.
    const base::string16 after_scheme(base::ASCIIToUTF16("//"));
    if (result.compare(0, after_scheme.length(), after_scheme) == 0)
      result.erase(0, after_scheme.length());
  }

  // Remove leading "www.".
  result = net::StripWWW(result);

  // Remove trailing "/".
  return (result.length() > 0 && result[result.length() - 1] == '/') ?
      result.substr(0, result.length() - 1) : result;
}

// static
GURL TemplateURLService::GenerateSearchURL(TemplateURL* t_url) {
  DCHECK(t_url);
  UIThreadSearchTermsData search_terms_data(t_url->profile());
  return GenerateSearchURLUsingTermsData(t_url, search_terms_data);
}

// static
GURL TemplateURLService::GenerateSearchURLUsingTermsData(
    const TemplateURL* t_url,
    const SearchTermsData& search_terms_data) {
  DCHECK(t_url);

  const TemplateURLRef& search_ref = t_url->url_ref();
  if (!search_ref.IsValidUsingTermsData(search_terms_data))
    return GURL();

  if (!search_ref.SupportsReplacementUsingTermsData(search_terms_data))
    return GURL(t_url->url());

  // Use something obscure for the search terms argument so that in the rare
  // case the term replaces the URL it's unlikely another keyword would have the
  // same url.
  // TODO(jnd): Add additional parameters to get post data when the search URL
  // has post parameters.
  return GURL(search_ref.ReplaceSearchTermsUsingTermsData(
      TemplateURLRef::SearchTermsArgs(
          base::ASCIIToUTF16("blah.blah.blah.blah.blah")),
      search_terms_data, NULL));
}

bool TemplateURLService::CanReplaceKeyword(
    const base::string16& keyword,
    const GURL& url,
    TemplateURL** template_url_to_replace) {
  DCHECK(!keyword.empty());  // This should only be called for non-empty
                             // keywords. If we need to support empty kewords
                             // the code needs to change slightly.
  TemplateURL* existing_url = GetTemplateURLForKeyword(keyword);
  if (template_url_to_replace)
    *template_url_to_replace = existing_url;
  if (existing_url) {
    // We already have a TemplateURL for this keyword. Only allow it to be
    // replaced if the TemplateURL can be replaced.
    return CanReplace(existing_url);
  }

  // We don't have a TemplateURL with keyword. Only allow a new one if there
  // isn't a TemplateURL for the specified host, or there is one but it can
  // be replaced. We do this to ensure that if the user assigns a different
  // keyword to a generated TemplateURL, we won't regenerate another keyword for
  // the same host.
  return !url.is_valid() || url.host().empty() ||
      CanReplaceKeywordForHost(url.host(), template_url_to_replace);
}

void TemplateURLService::FindMatchingKeywords(
    const base::string16& prefix,
    bool support_replacement_only,
    TemplateURLVector* matches) const {
  // Sanity check args.
  if (prefix.empty())
    return;
  DCHECK(matches != NULL);
  DCHECK(matches->empty());  // The code for exact matches assumes this.

  // Required for VS2010: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair
  TemplateURL* const kNullTemplateURL = NULL;

  // Find matching keyword range.  Searches the element map for keywords
  // beginning with |prefix| and stores the endpoints of the resulting set in
  // |match_range|.
  const std::pair<KeywordToTemplateMap::const_iterator,
                  KeywordToTemplateMap::const_iterator> match_range(
      std::equal_range(
          keyword_to_template_map_.begin(), keyword_to_template_map_.end(),
          KeywordToTemplateMap::value_type(prefix, kNullTemplateURL),
          LessWithPrefix()));

  // Return vector of matching keywords.
  for (KeywordToTemplateMap::const_iterator i(match_range.first);
       i != match_range.second; ++i) {
    if (!support_replacement_only || i->second->url_ref().SupportsReplacement())
      matches->push_back(i->second);
  }
}

TemplateURL* TemplateURLService::GetTemplateURLForKeyword(
    const base::string16& keyword) {
  KeywordToTemplateMap::const_iterator elem(
      keyword_to_template_map_.find(keyword));
  if (elem != keyword_to_template_map_.end())
    return elem->second;
  return ((!loaded_ || load_failed_) &&
      initial_default_search_provider_.get() &&
      (initial_default_search_provider_->keyword() == keyword)) ?
      initial_default_search_provider_.get() : NULL;
}

TemplateURL* TemplateURLService::GetTemplateURLForGUID(
    const std::string& sync_guid) {
  GUIDToTemplateMap::const_iterator elem(guid_to_template_map_.find(sync_guid));
  if (elem != guid_to_template_map_.end())
    return elem->second;
  return ((!loaded_ || load_failed_) &&
      initial_default_search_provider_.get() &&
      (initial_default_search_provider_->sync_guid() == sync_guid)) ?
      initial_default_search_provider_.get() : NULL;
}

TemplateURL* TemplateURLService::GetTemplateURLForHost(
    const std::string& host) {
  if (loaded_) {
    TemplateURL* t_url = provider_map_->GetTemplateURLForHost(host);
    if (t_url)
      return t_url;
  }
  return ((!loaded_ || load_failed_) &&
      initial_default_search_provider_.get() &&
      (GenerateSearchURL(initial_default_search_provider_.get()).host() ==
          host)) ? initial_default_search_provider_.get() : NULL;
}

void TemplateURLService::Add(TemplateURL* template_url) {
  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  if (AddNoNotify(template_url, true))
    NotifyObservers();
}

void TemplateURLService::AddAndSetProfile(TemplateURL* template_url,
                                          Profile* profile) {
  template_url->profile_ = profile;
  Add(template_url);
}

void TemplateURLService::AddWithOverrides(TemplateURL* template_url,
                                          const base::string16& short_name,
                                          const base::string16& keyword,
                                          const std::string& url) {
  DCHECK(!keyword.empty());
  DCHECK(!url.empty());
  template_url->data_.short_name = short_name;
  template_url->data_.SetKeyword(keyword);
  template_url->SetURL(url);
  Add(template_url);
}

void TemplateURLService::AddExtensionControlledTURL(
    TemplateURL* template_url,
    scoped_ptr<AssociatedExtensionInfo> info) {
  DCHECK(loaded_);
  DCHECK(template_url);
  DCHECK_EQ(kInvalidTemplateURLID, template_url->id());
  DCHECK(info);
  template_url->extension_info_.swap(info);
  DCHECK(!FindTemplateURLForExtension(
      template_url->GetExtensionId(),
      TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION));

  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  if (AddNoNotify(template_url, true)) {
    // Note that we can't call CanMakeDefault() here, since it would return
    // false when another extension is already controlling the default search
    // engine, and we want to allow new extensions to take over.
    if (template_url->extension_info_->wants_to_be_default_engine &&
        !is_default_search_managed()) {
      TemplateURL* default_candidate = FindExtensionDefaultSearchEngine();
      if (default_candidate == template_url) {
        base::AutoReset<DefaultSearchChangeOrigin> change_origin(
            &dsp_change_origin_, DSP_CHANGE_OVERRIDE_SETTINGS_EXTENSION);
        SetDefaultSearchProviderNoNotify(template_url);
      }
    }
    NotifyObservers();
  }
}

void TemplateURLService::Remove(TemplateURL* template_url) {
  RemoveNoNotify(template_url);
  NotifyObservers();
}

void TemplateURLService::RemoveExtensionControlledTURL(
    const std::string& extension_id) {
  DCHECK(loaded_);
  TemplateURL* url = FindTemplateURLForExtension(
      extension_id, TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION);
  if (!url)
    return;
  bool restore_dse = (url == GetDefaultSearchProvider());
  if (restore_dse) {
    DCHECK(!is_default_search_managed());
    default_search_provider_ = NULL;
  }
  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  RemoveNoNotify(url);
  if (restore_dse)
    SetDefaultSearchProviderAfterRemovingDefaultExtension();
  NotifyObservers();
}

void TemplateURLService::RemoveAutoGeneratedSince(base::Time created_after) {
  RemoveAutoGeneratedBetween(created_after, base::Time());
}

void TemplateURLService::RemoveAutoGeneratedBetween(base::Time created_after,
                                                    base::Time created_before) {
  RemoveAutoGeneratedForOriginBetween(GURL(), created_after, created_before);
}

void TemplateURLService::RemoveAutoGeneratedForOriginBetween(
    const GURL& origin,
    base::Time created_after,
    base::Time created_before) {
  GURL o(origin.GetOrigin());
  bool should_notify = false;
  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  for (size_t i = 0; i < template_urls_.size();) {
    if (template_urls_[i]->date_created() >= created_after &&
        (created_before.is_null() ||
         template_urls_[i]->date_created() < created_before) &&
        CanReplace(template_urls_[i]) &&
        (o.is_empty() ||
         GenerateSearchURL(template_urls_[i]).GetOrigin() == o)) {
      RemoveNoNotify(template_urls_[i]);
      should_notify = true;
    } else {
      ++i;
    }
  }
  if (should_notify)
    NotifyObservers();
}


void TemplateURLService::RegisterOmniboxKeyword(
    const std::string& extension_id,
    const std::string& extension_name,
    const std::string& keyword) {
  DCHECK(loaded_);

  if (!FindTemplateURLForExtension(extension_id,
                                   TemplateURL::OMNIBOX_API_EXTENSION)) {
    ExtensionKeyword extension_url(extension_id, extension_name, keyword);
    Add(CreateTemplateURLForExtension(extension_url));
  }
}

void TemplateURLService::UnregisterOmniboxKeyword(
    const std::string& extension_id) {
  DCHECK(loaded_);
  TemplateURL* url = FindTemplateURLForExtension(
      extension_id, TemplateURL::OMNIBOX_API_EXTENSION);
  if (url)
    Remove(url);
}

TemplateURLService::TemplateURLVector TemplateURLService::GetTemplateURLs() {
  return template_urls_;
}

void TemplateURLService::IncrementUsageCount(TemplateURL* url) {
  DCHECK(url);
  // Extension-controlled search engines are not persisted.
  if (url->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
    return;
  if (std::find(template_urls_.begin(), template_urls_.end(), url) ==
      template_urls_.end())
    return;
  ++url->data_.usage_count;

  if (service_.get())
    service_.get()->UpdateKeyword(url->data());
}

void TemplateURLService::ResetTemplateURL(TemplateURL* url,
                                          const base::string16& title,
                                          const base::string16& keyword,
                                          const std::string& search_url) {
  if (!loaded_)
    return;
  DCHECK(!keyword.empty());
  DCHECK(!search_url.empty());
  TemplateURLData data(url->data());
  data.short_name = title;
  data.SetKeyword(keyword);
  if (search_url != data.url()) {
    data.SetURL(search_url);
    // The urls have changed, reset the favicon url.
    data.favicon_url = GURL();
  }
  data.safe_for_autoreplace = false;
  data.last_modified = time_provider_();
  TemplateURL new_url(url->profile(), data);
  UIThreadSearchTermsData search_terms_data(url->profile());
  if (UpdateNoNotify(url, new_url, search_terms_data))
    NotifyObservers();
}

bool TemplateURLService::CanMakeDefault(const TemplateURL* url) {
  return  !is_default_search_managed() &&
      !IsExtensionControlledDefaultSearch() &&
      (url != GetDefaultSearchProvider()) &&
      url->url_ref().SupportsReplacement() &&
      (url->GetType() == TemplateURL::NORMAL);
}

void TemplateURLService::SetDefaultSearchProvider(TemplateURL* url) {
  DCHECK(!is_default_search_managed_);
  // Omnibox keywords cannot be made default. Extension-controlled search
  // engines can be made default only by the extension itself because they
  // aren't persisted.
  DCHECK(!url || (url->GetType() == TemplateURL::NORMAL));

  // Always persist the setting in the database, that way if the backup
  // signature has changed out from under us it gets reset correctly.
  if (SetDefaultSearchProviderNoNotify(url))
    NotifyObservers();
}

TemplateURL* TemplateURLService::GetDefaultSearchProvider() {
  if (loaded_ && !load_failed_)
    return default_search_provider_;
  // We're not loaded, rely on the default search provider stored in prefs.
  return initial_default_search_provider_.get();
}

bool TemplateURLService::IsSearchResultsPageFromDefaultSearchProvider(
    const GURL& url) {
  TemplateURL* default_provider = GetDefaultSearchProvider();
  return default_provider && default_provider->IsSearchURL(url);
}

bool TemplateURLService::IsExtensionControlledDefaultSearch() {
  const TemplateURL* default_provider = GetDefaultSearchProvider();
  return default_provider && (default_provider->GetType() ==
      TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION);
}

TemplateURL* TemplateURLService::FindNewDefaultSearchProvider() {
  // See if the prepopulated default still exists.
  scoped_ptr<TemplateURL> prepopulated_default(
      TemplateURLPrepopulateData::GetPrepopulatedDefaultSearch(profile_));
  for (TemplateURLVector::iterator i = template_urls_.begin();
       i != template_urls_.end(); ++i) {
    if ((*i)->prepopulate_id() == prepopulated_default->prepopulate_id())
      return *i;
  }
  // If not, use the first non-extension keyword of the templates that supports
  // search term replacement.
  if (processing_syncer_changes_) {
    UMA_HISTOGRAM_ENUMERATION(
        kFirstPotentialEngineHistogramName,
        FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_PROCESSING_SYNC_CHANGES,
        FIRST_POTENTIAL_CALLSITE_MAX);
  } else {
    if (sync_processor_.get()) {
      // We're not currently in a sync cycle, but we're syncing.
      UMA_HISTOGRAM_ENUMERATION(kFirstPotentialEngineHistogramName,
                                FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_SYNCING,
                                FIRST_POTENTIAL_CALLSITE_MAX);
    } else {
      // We're not syncing at all.
      UMA_HISTOGRAM_ENUMERATION(
          kFirstPotentialEngineHistogramName,
          FIRST_POTENTIAL_CALLSITE_FIND_NEW_DSP_NOT_SYNCING,
          FIRST_POTENTIAL_CALLSITE_MAX);
    }
  }
  return FirstPotentialDefaultEngine(template_urls_);
}

void TemplateURLService::RepairPrepopulatedSearchEngines() {
  // Can't clean DB if it hasn't been loaded.
  DCHECK(loaded());

  size_t default_search_provider_index = 0;
  ScopedVector<TemplateURL> prepopulated_urls =
      TemplateURLPrepopulateData::GetPrepopulatedEngines(
          profile_, &default_search_provider_index);
  DCHECK(!prepopulated_urls.empty());
  int default_search_engine_id =
      prepopulated_urls[default_search_provider_index]->prepopulate_id();
  TemplateURL* current_dse = default_search_provider_;
  ActionsFromPrepopulateData actions(CreateActionsFromCurrentPrepopulateData(
      &prepopulated_urls, template_urls_, current_dse));

  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());

  // Remove items.
  for (std::vector<TemplateURL*>::iterator i = actions.removed_engines.begin();
       i < actions.removed_engines.end(); ++i)
    RemoveNoNotify(*i);

  // Edit items.
  for (EditedEngines::iterator i(actions.edited_engines.begin());
       i < actions.edited_engines.end(); ++i) {
    UIThreadSearchTermsData search_terms_data(profile());
    TemplateURL new_values(profile(), i->second);
    UpdateNoNotify(i->first, new_values, search_terms_data);
  }

  // Add items.
  for (std::vector<TemplateURL*>::iterator i = actions.added_engines.begin();
       i < actions.added_engines.end(); ++i)
    AddNoNotify(*i, true);

  // Change the DSE.
  TemplateURL* new_dse = FindURLByPrepopulateID(template_urls_,
                                                default_search_engine_id);
  DCHECK(new_dse);
  if (CanMakeDefault(new_dse)) {
    base::AutoReset<DefaultSearchChangeOrigin> change_origin(
        &dsp_change_origin_, DSP_CHANGE_PROFILE_RESET);
    SetDefaultSearchProviderNoNotify(new_dse);
  }
  NotifyObservers();
}

void TemplateURLService::AddObserver(TemplateURLServiceObserver* observer) {
  model_observers_.AddObserver(observer);
}

void TemplateURLService::RemoveObserver(TemplateURLServiceObserver* observer) {
  model_observers_.RemoveObserver(observer);
}

void TemplateURLService::Load() {
  if (loaded_ || load_handle_)
    return;

  if (!service_.get()) {
    service_ = WebDataService::FromBrowserContext(profile_);
  }

  if (service_.get()) {
    load_handle_ = service_->GetKeywords(this);
  } else {
    ChangeToLoadedState();
    on_loaded_callbacks_.Notify();
  }
}

scoped_ptr<TemplateURLService::Subscription>
    TemplateURLService::RegisterOnLoadedCallback(
        const base::Closure& callback) {
  return loaded_ ?
      scoped_ptr<TemplateURLService::Subscription>() :
      on_loaded_callbacks_.Add(callback);
}

void TemplateURLService::OnWebDataServiceRequestDone(
    WebDataService::Handle h,
    const WDTypedResult* result) {
  // Reset the load_handle so that we don't try and cancel the load in
  // the destructor.
  load_handle_ = 0;

  if (!result) {
    // Results are null if the database went away or (most likely) wasn't
    // loaded.
    load_failed_ = true;
    ChangeToLoadedState();
    on_loaded_callbacks_.Notify();
    return;
  }

  // initial_default_search_provider_ is only needed before we've finished
  // loading. Now that we've loaded we can nuke it.
  initial_default_search_provider_.reset();

  TemplateURLVector template_urls;
  TemplateURL* default_search_provider = NULL;
  int new_resource_keyword_version = 0;
  GetSearchProvidersUsingKeywordResult(*result, service_.get(), profile_,
      &template_urls, &default_search_provider, &new_resource_keyword_version,
      &pre_sync_deletes_);

  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());

  AddTemplateURLsAndSetupDefaultEngine(&template_urls, default_search_provider);

  // This initializes provider_map_ which should be done before
  // calling UpdateKeywordSearchTermsForURL.
  ChangeToLoadedState();

  // Index any visits that occurred before we finished loading.
  for (size_t i = 0; i < visits_to_add_.size(); ++i)
    UpdateKeywordSearchTermsForURL(visits_to_add_[i]);
  visits_to_add_.clear();

  if (new_resource_keyword_version)
    service_->SetBuiltinKeywordVersion(new_resource_keyword_version);

  EnsureDefaultSearchProviderExists();

  NotifyObservers();
  on_loaded_callbacks_.Notify();
}

base::string16 TemplateURLService::GetKeywordShortName(
    const base::string16& keyword,
    bool* is_omnibox_api_extension_keyword) {
  const TemplateURL* template_url = GetTemplateURLForKeyword(keyword);

  // TODO(sky): Once LocationBarView adds a listener to the TemplateURLService
  // to track changes to the model, this should become a DCHECK.
  if (template_url) {
    *is_omnibox_api_extension_keyword =
        template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
    return template_url->AdjustedShortNameForLocaleDirection();
  }
  *is_omnibox_api_extension_keyword = false;
  return base::string16();
}

void TemplateURLService::Observe(int type,
                                 const content::NotificationSource& source,
                                 const content::NotificationDetails& details) {
  if (type == chrome::NOTIFICATION_HISTORY_URL_VISITED) {
    content::Details<history::URLVisitedDetails> visit_details(details);
    if (!loaded_)
      visits_to_add_.push_back(*visit_details.ptr());
    else
      UpdateKeywordSearchTermsForURL(*visit_details.ptr());
  } else if (type == chrome::NOTIFICATION_DEFAULT_SEARCH_POLICY_CHANGED) {
    // Policy has been updated, so the default search prefs may be different.
    // Reload the default search provider from them.
    // TODO(pkasting): Rather than communicating via prefs, we should eventually
    // observe policy changes directly.
    UpdateDefaultSearch();
  } else {
    DCHECK_EQ(chrome::NOTIFICATION_GOOGLE_URL_UPDATED, type);
    if (loaded_) {
      GoogleBaseURLChanged(
          content::Details<GoogleURLTracker::UpdatedDetails>(details)->first);
    }
  }
}

void TemplateURLService::Shutdown() {
  // This check has to be done at Shutdown() instead of in the dtor to ensure
  // that no clients of WebDataService are holding ptrs to it after the first
  // phase of the KeyedService Shutdown() process.
  if (load_handle_) {
    DCHECK(service_.get());
    service_->CancelRequest(load_handle_);
  }
  service_ = NULL;
}

void TemplateURLService::OnSyncedDefaultSearchProviderGUIDChanged() {
  // Listen for changes to the default search from Sync.
  PrefService* prefs = GetPrefs();
  TemplateURL* new_default_search = GetTemplateURLForGUID(
      prefs->GetString(prefs::kSyncedDefaultSearchProviderGUID));
  if (new_default_search && !is_default_search_managed_) {
    if (new_default_search != GetDefaultSearchProvider()) {
      base::AutoReset<DefaultSearchChangeOrigin> change_origin(
          &dsp_change_origin_, DSP_CHANGE_SYNC_PREF);
      SetDefaultSearchProvider(new_default_search);
      pending_synced_default_search_ = false;
    }
  } else {
    // If it's not there, or if default search is currently managed, set a
    // flag to indicate that we waiting on the search engine entry to come
    // in through Sync.
    pending_synced_default_search_ = true;
  }
  UpdateDefaultSearch();
}

syncer::SyncDataList TemplateURLService::GetAllSyncData(
    syncer::ModelType type) const {
  DCHECK_EQ(syncer::SEARCH_ENGINES, type);

  syncer::SyncDataList current_data;
  for (TemplateURLVector::const_iterator iter = template_urls_.begin();
      iter != template_urls_.end(); ++iter) {
    // We don't sync keywords managed by policy.
    if ((*iter)->created_by_policy())
      continue;
    // We don't sync extension-controlled search engines.
    if ((*iter)->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
      continue;
    current_data.push_back(CreateSyncDataFromTemplateURL(**iter));
  }

  return current_data;
}

syncer::SyncError TemplateURLService::ProcessSyncChanges(
    const tracked_objects::Location& from_here,
    const syncer::SyncChangeList& change_list) {
  if (!models_associated_) {
    syncer::SyncError error(FROM_HERE,
                            syncer::SyncError::DATATYPE_ERROR,
                            "Models not yet associated.",
                            syncer::SEARCH_ENGINES);
    return error;
  }
  DCHECK(loaded_);

  base::AutoReset<bool> processing_changes(&processing_syncer_changes_, true);

  // We've started syncing, so set our origin member to the base Sync value.
  // As we move through Sync Code, we may set this to increasingly specific
  // origins so we can tell what exactly caused a DSP change.
  base::AutoReset<DefaultSearchChangeOrigin> change_origin(&dsp_change_origin_,
      DSP_CHANGE_SYNC_UNINTENTIONAL);

  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());

  syncer::SyncChangeList new_changes;
  syncer::SyncError error;
  for (syncer::SyncChangeList::const_iterator iter = change_list.begin();
      iter != change_list.end(); ++iter) {
    DCHECK_EQ(syncer::SEARCH_ENGINES, iter->sync_data().GetDataType());

    std::string guid =
        iter->sync_data().GetSpecifics().search_engine().sync_guid();
    TemplateURL* existing_turl = GetTemplateURLForGUID(guid);
    scoped_ptr<TemplateURL> turl(CreateTemplateURLFromTemplateURLAndSyncData(
        profile_, existing_turl, iter->sync_data(), &new_changes));
    if (!turl.get())
      continue;

    // Explicitly don't check for conflicts against extension keywords; in this
    // case the functions which modify the keyword map know how to handle the
    // conflicts.
    // TODO(mpcomplete): If we allow editing extension keywords, then those will
    // need to undergo conflict resolution.
    TemplateURL* existing_keyword_turl =
        FindNonExtensionTemplateURLForKeyword(turl->keyword());
    if (iter->change_type() == syncer::SyncChange::ACTION_DELETE) {
      if (!existing_turl) {
        error = sync_error_factory_->CreateAndUploadError(
            FROM_HERE,
            "ProcessSyncChanges failed on ChangeType ACTION_DELETE");
        continue;
      }
      if (existing_turl == GetDefaultSearchProvider()) {
        // The only way Sync can attempt to delete the default search provider
        // is if we had changed the kSyncedDefaultSearchProviderGUID
        // preference, but perhaps it has not yet been received. To avoid
        // situations where this has come in erroneously, we will un-delete
        // the current default search from the Sync data. If the pref really
        // does arrive later, then default search will change to the correct
        // entry, but we'll have this extra entry sitting around. The result is
        // not ideal, but it prevents a far more severe bug where the default is
        // unexpectedly swapped to something else. The user can safely delete
        // the extra entry again later, if they choose. Most users who do not
        // look at the search engines UI will not notice this.
        // Note that we append a special character to the end of the keyword in
        // an attempt to avoid a ping-poinging situation where receiving clients
        // may try to continually delete the resurrected entry.
        base::string16 updated_keyword = UniquifyKeyword(*existing_turl, true);
        TemplateURLData data(existing_turl->data());
        data.SetKeyword(updated_keyword);
        TemplateURL new_turl(existing_turl->profile(), data);
        UIThreadSearchTermsData search_terms_data(existing_turl->profile());
        if (UpdateNoNotify(existing_turl, new_turl, search_terms_data))
          NotifyObservers();

        syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(new_turl);
        new_changes.push_back(syncer::SyncChange(FROM_HERE,
                                                 syncer::SyncChange::ACTION_ADD,
                                                 sync_data));
        // Ignore the delete attempt. This means we never end up reseting the
        // default search provider due to an ACTION_DELETE from sync.
        continue;
      }

      Remove(existing_turl);
    } else if (iter->change_type() == syncer::SyncChange::ACTION_ADD) {
      if (existing_turl) {
        error = sync_error_factory_->CreateAndUploadError(
            FROM_HERE,
            "ProcessSyncChanges failed on ChangeType ACTION_ADD");
        continue;
      }
      const std::string guid = turl->sync_guid();
      if (existing_keyword_turl) {
        // Resolve any conflicts so we can safely add the new entry.
        ResolveSyncKeywordConflict(turl.get(), existing_keyword_turl,
                                   &new_changes);
      }
      // Force the local ID to kInvalidTemplateURLID so we can add it.
      TemplateURLData data(turl->data());
      data.id = kInvalidTemplateURLID;
      Add(new TemplateURL(profile_, data));

      // Possibly set the newly added |turl| as the default search provider.
      SetDefaultSearchProviderIfNewlySynced(guid);
    } else if (iter->change_type() == syncer::SyncChange::ACTION_UPDATE) {
      if (!existing_turl) {
        error = sync_error_factory_->CreateAndUploadError(
            FROM_HERE,
            "ProcessSyncChanges failed on ChangeType ACTION_UPDATE");
        continue;
      }
      if (existing_keyword_turl && (existing_keyword_turl != existing_turl)) {
        // Resolve any conflicts with other entries so we can safely update the
        // keyword.
        ResolveSyncKeywordConflict(turl.get(), existing_keyword_turl,
                                   &new_changes);
      }
      UIThreadSearchTermsData search_terms_data(existing_turl->profile());
      if (UpdateNoNotify(existing_turl, *turl, search_terms_data))
        NotifyObservers();
    } else {
      // We've unexpectedly received an ACTION_INVALID.
      error = sync_error_factory_->CreateAndUploadError(
          FROM_HERE,
          "ProcessSyncChanges received an ACTION_INVALID");
    }
  }

  // If something went wrong, we want to prematurely exit to avoid pushing
  // inconsistent data to Sync. We return the last error we received.
  if (error.IsSet())
    return error;

  error = sync_processor_->ProcessSyncChanges(from_here, new_changes);

  return error;
}

syncer::SyncMergeResult TemplateURLService::MergeDataAndStartSyncing(
    syncer::ModelType type,
    const syncer::SyncDataList& initial_sync_data,
    scoped_ptr<syncer::SyncChangeProcessor> sync_processor,
    scoped_ptr<syncer::SyncErrorFactory> sync_error_factory) {
  DCHECK(loaded_);
  DCHECK_EQ(type, syncer::SEARCH_ENGINES);
  DCHECK(!sync_processor_.get());
  DCHECK(sync_processor.get());
  DCHECK(sync_error_factory.get());
  syncer::SyncMergeResult merge_result(type);
  sync_processor_ = sync_processor.Pass();
  sync_error_factory_ = sync_error_factory.Pass();

  // We just started syncing, so set our wait-for-default flag if we are
  // expecting a default from Sync.
  if (GetPrefs()) {
    std::string default_guid = GetPrefs()->GetString(
        prefs::kSyncedDefaultSearchProviderGUID);
    const TemplateURL* current_default = GetDefaultSearchProvider();

    if (!default_guid.empty() &&
        (!current_default || current_default->sync_guid() != default_guid))
      pending_synced_default_search_ = true;
  }

  // We do a lot of calls to Add/Remove/ResetTemplateURL here, so ensure we
  // don't step on our own toes.
  base::AutoReset<bool> processing_changes(&processing_syncer_changes_, true);

  // We've started syncing, so set our origin member to the base Sync value.
  // As we move through Sync Code, we may set this to increasingly specific
  // origins so we can tell what exactly caused a DSP change.
  base::AutoReset<DefaultSearchChangeOrigin> change_origin(&dsp_change_origin_,
      DSP_CHANGE_SYNC_UNINTENTIONAL);

  syncer::SyncChangeList new_changes;

  // Build maps of our sync GUIDs to syncer::SyncData.
  SyncDataMap local_data_map = CreateGUIDToSyncDataMap(
      GetAllSyncData(syncer::SEARCH_ENGINES));
  SyncDataMap sync_data_map = CreateGUIDToSyncDataMap(initial_sync_data);

  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());

  merge_result.set_num_items_before_association(local_data_map.size());
  for (SyncDataMap::const_iterator iter = sync_data_map.begin();
      iter != sync_data_map.end(); ++iter) {
    TemplateURL* local_turl = GetTemplateURLForGUID(iter->first);
    scoped_ptr<TemplateURL> sync_turl(
        CreateTemplateURLFromTemplateURLAndSyncData(profile_, local_turl,
            iter->second, &new_changes));
    if (!sync_turl.get())
      continue;

    if (pre_sync_deletes_.find(sync_turl->sync_guid()) !=
        pre_sync_deletes_.end()) {
      // This entry was deleted before the initial sync began (possibly through
      // preprocessing in TemplateURLService's loading code). Ignore it and send
      // an ACTION_DELETE up to the server.
      new_changes.push_back(
          syncer::SyncChange(FROM_HERE,
                             syncer::SyncChange::ACTION_DELETE,
                             iter->second));
      UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
          DELETE_ENGINE_PRE_SYNC, DELETE_ENGINE_MAX);
      continue;
    }

    if (local_turl) {
      DCHECK(IsFromSync(local_turl, sync_data_map));
      // This local search engine is already synced. If the timestamp differs
      // from Sync, we need to update locally or to the cloud. Note that if the
      // timestamps are equal, we touch neither.
      if (sync_turl->last_modified() > local_turl->last_modified()) {
        // We've received an update from Sync. We should replace all synced
        // fields in the local TemplateURL. Note that this includes the
        // TemplateURLID and the TemplateURL may have to be reparsed. This
        // also makes the local data's last_modified timestamp equal to Sync's,
        // avoiding an Update on the next MergeData call.
        UIThreadSearchTermsData search_terms_data(local_turl->profile());
        if (UpdateNoNotify(local_turl, *sync_turl, search_terms_data))
          NotifyObservers();
        merge_result.set_num_items_modified(
            merge_result.num_items_modified() + 1);
      } else if (sync_turl->last_modified() < local_turl->last_modified()) {
        // Otherwise, we know we have newer data, so update Sync with our
        // data fields.
        new_changes.push_back(
            syncer::SyncChange(FROM_HERE,
                               syncer::SyncChange::ACTION_UPDATE,
                               local_data_map[local_turl->sync_guid()]));
      }
      local_data_map.erase(iter->first);
    } else {
      // The search engine from the cloud has not been synced locally. Merge it
      // into our local model. This will handle any conflicts with local (and
      // already-synced) TemplateURLs. It will prefer to keep entries from Sync
      // over not-yet-synced TemplateURLs.
      MergeInSyncTemplateURL(sync_turl.get(), sync_data_map, &new_changes,
                             &local_data_map, &merge_result);
    }
  }

  // If there is a pending synced default search provider that was processed
  // above, set it now.
  TemplateURL* pending_default = GetPendingSyncedDefaultSearchProvider();
  if (pending_default) {
    base::AutoReset<DefaultSearchChangeOrigin> change_origin(
        &dsp_change_origin_, DSP_CHANGE_SYNC_ADD);
    SetDefaultSearchProvider(pending_default);
  }

  // The remaining SyncData in local_data_map should be everything that needs to
  // be pushed as ADDs to sync.
  for (SyncDataMap::const_iterator iter = local_data_map.begin();
      iter != local_data_map.end(); ++iter) {
    new_changes.push_back(
        syncer::SyncChange(FROM_HERE,
                           syncer::SyncChange::ACTION_ADD,
                           iter->second));
  }

  // Do some post-processing on the change list to ensure that we are sending
  // valid changes to sync_processor_.
  PruneSyncChanges(&sync_data_map, &new_changes);

  LogDuplicatesHistogram(GetTemplateURLs());
  merge_result.set_num_items_after_association(
      GetAllSyncData(syncer::SEARCH_ENGINES).size());
  merge_result.set_error(
      sync_processor_->ProcessSyncChanges(FROM_HERE, new_changes));
  if (merge_result.error().IsSet())
    return merge_result;

  // The ACTION_DELETEs from this set are processed. Empty it so we don't try to
  // reuse them on the next call to MergeDataAndStartSyncing.
  pre_sync_deletes_.clear();

  models_associated_ = true;
  return merge_result;
}

void TemplateURLService::StopSyncing(syncer::ModelType type) {
  DCHECK_EQ(type, syncer::SEARCH_ENGINES);
  models_associated_ = false;
  sync_processor_.reset();
  sync_error_factory_.reset();
}

void TemplateURLService::ProcessTemplateURLChange(
    const tracked_objects::Location& from_here,
    const TemplateURL* turl,
    syncer::SyncChange::SyncChangeType type) {
  DCHECK_NE(type, syncer::SyncChange::ACTION_INVALID);
  DCHECK(turl);

  if (!models_associated_)
    return;  // Not syncing.

  if (processing_syncer_changes_)
    return;  // These are changes originating from us. Ignore.

  // Avoid syncing keywords managed by policy.
  if (turl->created_by_policy())
    return;

  // Avoid syncing extension-controlled search engines.
  if (turl->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)
    return;

  syncer::SyncChangeList changes;

  syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*turl);
  changes.push_back(syncer::SyncChange(from_here,
                                       type,
                                       sync_data));

  sync_processor_->ProcessSyncChanges(FROM_HERE, changes);
}

// static
syncer::SyncData TemplateURLService::CreateSyncDataFromTemplateURL(
    const TemplateURL& turl) {
  sync_pb::EntitySpecifics specifics;
  sync_pb::SearchEngineSpecifics* se_specifics =
      specifics.mutable_search_engine();
  se_specifics->set_short_name(base::UTF16ToUTF8(turl.short_name()));
  se_specifics->set_keyword(base::UTF16ToUTF8(turl.keyword()));
  se_specifics->set_favicon_url(turl.favicon_url().spec());
  se_specifics->set_url(turl.url());
  se_specifics->set_safe_for_autoreplace(turl.safe_for_autoreplace());
  se_specifics->set_originating_url(turl.originating_url().spec());
  se_specifics->set_date_created(turl.date_created().ToInternalValue());
  se_specifics->set_input_encodings(JoinString(turl.input_encodings(), ';'));
  se_specifics->set_show_in_default_list(turl.show_in_default_list());
  se_specifics->set_suggestions_url(turl.suggestions_url());
  se_specifics->set_prepopulate_id(turl.prepopulate_id());
  se_specifics->set_instant_url(turl.instant_url());
  if (!turl.image_url().empty())
    se_specifics->set_image_url(turl.image_url());
  se_specifics->set_new_tab_url(turl.new_tab_url());
  if (!turl.search_url_post_params().empty())
    se_specifics->set_search_url_post_params(turl.search_url_post_params());
  if (!turl.suggestions_url_post_params().empty()) {
    se_specifics->set_suggestions_url_post_params(
        turl.suggestions_url_post_params());
  }
  if (!turl.instant_url_post_params().empty())
    se_specifics->set_instant_url_post_params(turl.instant_url_post_params());
  if (!turl.image_url_post_params().empty())
    se_specifics->set_image_url_post_params(turl.image_url_post_params());
  se_specifics->set_last_modified(turl.last_modified().ToInternalValue());
  se_specifics->set_sync_guid(turl.sync_guid());
  for (size_t i = 0; i < turl.alternate_urls().size(); ++i)
    se_specifics->add_alternate_urls(turl.alternate_urls()[i]);
  se_specifics->set_search_terms_replacement_key(
      turl.search_terms_replacement_key());

  return syncer::SyncData::CreateLocalData(se_specifics->sync_guid(),
                                           se_specifics->keyword(),
                                           specifics);
}

// static
TemplateURL* TemplateURLService::CreateTemplateURLFromTemplateURLAndSyncData(
    Profile* profile,
    TemplateURL* existing_turl,
    const syncer::SyncData& sync_data,
    syncer::SyncChangeList* change_list) {
  DCHECK(change_list);

  sync_pb::SearchEngineSpecifics specifics =
      sync_data.GetSpecifics().search_engine();

  // Past bugs might have caused either of these fields to be empty.  Just
  // delete this data off the server.
  if (specifics.url().empty() || specifics.sync_guid().empty()) {
    change_list->push_back(
        syncer::SyncChange(FROM_HERE,
                           syncer::SyncChange::ACTION_DELETE,
                           sync_data));
    UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
        DELETE_ENGINE_EMPTY_FIELD, DELETE_ENGINE_MAX);
    return NULL;
  }

  TemplateURLData data(existing_turl ?
      existing_turl->data() : TemplateURLData());
  data.short_name = base::UTF8ToUTF16(specifics.short_name());
  data.originating_url = GURL(specifics.originating_url());
  base::string16 keyword(base::UTF8ToUTF16(specifics.keyword()));
  // NOTE: Once this code has shipped in a couple of stable releases, we can
  // probably remove the migration portion, comment out the
  // "autogenerate_keyword" field entirely in the .proto file, and fold the
  // empty keyword case into the "delete data" block above.
  bool reset_keyword =
      specifics.autogenerate_keyword() || specifics.keyword().empty();
  if (reset_keyword)
    keyword = base::ASCIIToUTF16("dummy");  // Will be replaced below.
  DCHECK(!keyword.empty());
  data.SetKeyword(keyword);
  data.SetURL(specifics.url());
  data.suggestions_url = specifics.suggestions_url();
  data.instant_url = specifics.instant_url();
  data.image_url = specifics.image_url();
  data.new_tab_url = specifics.new_tab_url();
  data.search_url_post_params = specifics.search_url_post_params();
  data.suggestions_url_post_params = specifics.suggestions_url_post_params();
  data.instant_url_post_params = specifics.instant_url_post_params();
  data.image_url_post_params = specifics.image_url_post_params();
  data.favicon_url = GURL(specifics.favicon_url());
  data.show_in_default_list = specifics.show_in_default_list();
  data.safe_for_autoreplace = specifics.safe_for_autoreplace();
  base::SplitString(specifics.input_encodings(), ';', &data.input_encodings);
  // If the server data has duplicate encodings, we'll want to push an update
  // below to correct it.  Note that we also fix this in
  // GetSearchProvidersUsingKeywordResult(), since otherwise we'd never correct
  // local problems for clients which have disabled search engine sync.
  bool deduped = DeDupeEncodings(&data.input_encodings);
  data.date_created = base::Time::FromInternalValue(specifics.date_created());
  data.last_modified = base::Time::FromInternalValue(specifics.last_modified());
  data.prepopulate_id = specifics.prepopulate_id();
  data.sync_guid = specifics.sync_guid();
  data.alternate_urls.clear();
  for (int i = 0; i < specifics.alternate_urls_size(); ++i)
    data.alternate_urls.push_back(specifics.alternate_urls(i));
  data.search_terms_replacement_key = specifics.search_terms_replacement_key();

  TemplateURL* turl = new TemplateURL(profile, data);
  // If this TemplateURL matches a built-in prepopulated template URL, it's
  // possible that sync is trying to modify fields that should not be touched.
  // Revert these fields to the built-in values.
  UpdateTemplateURLIfPrepopulated(turl, profile);
  DCHECK_NE(TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION, turl->GetType());
  if (reset_keyword || deduped) {
    if (reset_keyword)
      turl->ResetKeywordIfNecessary(true);
    syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*turl);
    change_list->push_back(syncer::SyncChange(FROM_HERE,
                                              syncer::SyncChange::ACTION_UPDATE,
                                              sync_data));
  } else if (turl->IsGoogleSearchURLWithReplaceableKeyword()) {
    if (!existing_turl) {
      // We're adding a new TemplateURL that uses the Google base URL, so set
      // its keyword appropriately for the local environment.
      turl->ResetKeywordIfNecessary(false);
    } else if (existing_turl->IsGoogleSearchURLWithReplaceableKeyword()) {
      // Ignore keyword changes triggered by the Google base URL changing on
      // another client.  If the base URL changes in this client as well, we'll
      // pick that up separately at the appropriate time.  Otherwise, changing
      // the keyword here could result in having the wrong keyword for the local
      // environment.
      turl->data_.SetKeyword(existing_turl->keyword());
    }
  }

  return turl;
}

// static
SyncDataMap TemplateURLService::CreateGUIDToSyncDataMap(
    const syncer::SyncDataList& sync_data) {
  SyncDataMap data_map;
  for (syncer::SyncDataList::const_iterator i(sync_data.begin());
       i != sync_data.end();
       ++i)
    data_map[i->GetSpecifics().search_engine().sync_guid()] = *i;
  return data_map;
}

void TemplateURLService::SetKeywordSearchTermsForURL(
    const TemplateURL* t_url,
    const GURL& url,
    const base::string16& term) {
  HistoryService* history = profile_  ?
      HistoryServiceFactory::GetForProfile(profile_,
                                           Profile::EXPLICIT_ACCESS) :
      NULL;
  if (!history)
    return;
  history->SetKeywordSearchTermsForURL(url, t_url->id(), term);
}

void TemplateURLService::Init(const Initializer* initializers,
                              int num_initializers) {
  // Register for notifications.
  if (profile_) {
    // TODO(sky): bug 1166191. The keywords should be moved into the history
    // db, which will mean we no longer need this notification and the history
    // backend can handle automatically adding the search terms as the user
    // navigates.
    content::Source<Profile> profile_source(profile_->GetOriginalProfile());
    notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URL_VISITED,
                                profile_source);
    notification_registrar_.Add(this, chrome::NOTIFICATION_GOOGLE_URL_UPDATED,
                                profile_source);
    pref_change_registrar_.Init(GetPrefs());
    pref_change_registrar_.Add(
        prefs::kSyncedDefaultSearchProviderGUID,
        base::Bind(
            &TemplateURLService::OnSyncedDefaultSearchProviderGUIDChanged,
            base::Unretained(this)));
  }
  notification_registrar_.Add(
      this, chrome::NOTIFICATION_DEFAULT_SEARCH_POLICY_CHANGED,
      content::NotificationService::AllSources());

  if (num_initializers > 0) {
    // This path is only hit by test code and is used to simulate a loaded
    // TemplateURLService.
    ChangeToLoadedState();

    // Add specific initializers, if any.
    WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
    for (int i(0); i < num_initializers; ++i) {
      DCHECK(initializers[i].keyword);
      DCHECK(initializers[i].url);
      DCHECK(initializers[i].content);

      // TemplateURLService ends up owning the TemplateURL, don't try and free
      // it.
      TemplateURLData data;
      data.short_name = base::UTF8ToUTF16(initializers[i].content);
      data.SetKeyword(base::UTF8ToUTF16(initializers[i].keyword));
      data.SetURL(initializers[i].url);
      TemplateURL* template_url = new TemplateURL(profile_, data);
      AddNoNotify(template_url, true);

      // Set the first provided identifier to be the default.
      if (i == 0)
        SetDefaultSearchProviderNoNotify(template_url);
    }
  }

  // Initialize default search.
  UpdateDefaultSearch();

  // Request a server check for the correct Google URL if Google is the
  // default search engine and not in headless mode.
  if (profile_ && initial_default_search_provider_.get() &&
      initial_default_search_provider_->url_ref().HasGoogleBaseURLs()) {
    scoped_ptr<base::Environment> env(base::Environment::Create());
    if (!env->HasVar(env_vars::kHeadless))
      GoogleURLTracker::RequestServerCheck(profile_, false);
  }
}

void TemplateURLService::RemoveFromMaps(TemplateURL* template_url) {
  const base::string16& keyword = template_url->keyword();
  DCHECK_NE(0U, keyword_to_template_map_.count(keyword));
  if (keyword_to_template_map_[keyword] == template_url) {
    // We need to check whether the keyword can now be provided by another
    // TemplateURL.  See the comments in AddToMaps() for more information on
    // extension keywords and how they can coexist with non-extension keywords.
    // In the case of more than one extension, we use the most recently
    // installed (which will be the most recently added, which will have the
    // highest ID).
    TemplateURL* best_fallback = NULL;
    for (TemplateURLVector::const_iterator i(template_urls_.begin());
         i != template_urls_.end(); ++i) {
      TemplateURL* turl = *i;
      // This next statement relies on the fact that there can only be one
      // non-Omnibox API TemplateURL with a given keyword.
      if ((turl != template_url) && (turl->keyword() == keyword) &&
          (!best_fallback ||
           (best_fallback->GetType() != TemplateURL::OMNIBOX_API_EXTENSION) ||
           ((turl->GetType() == TemplateURL::OMNIBOX_API_EXTENSION) &&
            (turl->id() > best_fallback->id()))))
        best_fallback = turl;
    }
    if (best_fallback)
      keyword_to_template_map_[keyword] = best_fallback;
    else
      keyword_to_template_map_.erase(keyword);
  }

  if (!template_url->sync_guid().empty())
    guid_to_template_map_.erase(template_url->sync_guid());
  if (loaded_) {
    UIThreadSearchTermsData search_terms_data(template_url->profile());
    provider_map_->Remove(template_url, search_terms_data);
  }
}

void TemplateURLService::AddToMaps(TemplateURL* template_url) {
  bool template_url_is_omnibox_api =
      template_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
  const base::string16& keyword = template_url->keyword();
  KeywordToTemplateMap::const_iterator i =
      keyword_to_template_map_.find(keyword);
  if (i == keyword_to_template_map_.end()) {
    keyword_to_template_map_[keyword] = template_url;
  } else {
    const TemplateURL* existing_url = i->second;
    // We should only have overlapping keywords when at least one comes from
    // an extension.  In that case, the ranking order is:
    //   Manually-modified keywords > extension keywords > replaceable keywords
    // When there are multiple extensions, the last-added wins.
    bool existing_url_is_omnibox_api =
        existing_url->GetType() == TemplateURL::OMNIBOX_API_EXTENSION;
    DCHECK(existing_url_is_omnibox_api || template_url_is_omnibox_api);
    if (existing_url_is_omnibox_api ?
        !CanReplace(template_url) : CanReplace(existing_url))
      keyword_to_template_map_[keyword] = template_url;
  }

  if (!template_url->sync_guid().empty())
    guid_to_template_map_[template_url->sync_guid()] = template_url;
  if (loaded_) {
    UIThreadSearchTermsData search_terms_data(profile_);
    provider_map_->Add(template_url, search_terms_data);
  }
}

// Helper for partition() call in next function.
bool HasValidID(TemplateURL* t_url) {
  return t_url->id() != kInvalidTemplateURLID;
}

void TemplateURLService::SetTemplateURLs(TemplateURLVector* urls) {
  // Partition the URLs first, instead of implementing the loops below by simply
  // scanning the input twice.  While it's not supposed to happen normally, it's
  // possible for corrupt databases to return multiple entries with the same
  // keyword.  In this case, the first loop may delete the first entry when
  // adding the second.  If this happens, the second loop must not attempt to
  // access the deleted entry.  Partitioning ensures this constraint.
  TemplateURLVector::iterator first_invalid(
      std::partition(urls->begin(), urls->end(), HasValidID));

  // First, add the items that already have id's, so that the next_id_ gets
  // properly set.
  for (TemplateURLVector::const_iterator i = urls->begin(); i != first_invalid;
       ++i) {
    next_id_ = std::max(next_id_, (*i)->id());
    AddNoNotify(*i, false);
  }

  // Next add the new items that don't have id's.
  for (TemplateURLVector::const_iterator i = first_invalid; i != urls->end();
       ++i)
    AddNoNotify(*i, true);

  // Clear the input vector to reduce the chance callers will try to use a
  // (possibly deleted) entry.
  urls->clear();
}

void TemplateURLService::ChangeToLoadedState() {
  DCHECK(!loaded_);

  UIThreadSearchTermsData search_terms_data(profile_);
  provider_map_->Init(template_urls_, search_terms_data);
  loaded_ = true;
}

void TemplateURLService::SaveDefaultSearchProviderToPrefs(
    const TemplateURL* t_url) {
  PrefService* prefs = GetPrefs();
  if (!prefs)
    return;

  bool enabled = false;
  std::string search_url;
  std::string suggest_url;
  std::string instant_url;
  std::string image_url;
  std::string new_tab_url;
  std::string search_url_post_params;
  std::string suggest_url_post_params;
  std::string instant_url_post_params;
  std::string image_url_post_params;
  std::string icon_url;
  std::string encodings;
  std::string short_name;
  std::string keyword;
  std::string id_string;
  std::string prepopulate_id;
  base::ListValue alternate_urls;
  std::string search_terms_replacement_key;
  if (t_url) {
    DCHECK_EQ(TemplateURL::NORMAL, t_url->GetType());
    enabled = true;
    search_url = t_url->url();
    suggest_url = t_url->suggestions_url();
    instant_url = t_url->instant_url();
    image_url = t_url->image_url();
    new_tab_url = t_url->new_tab_url();
    search_url_post_params = t_url->search_url_post_params();
    suggest_url_post_params = t_url->suggestions_url_post_params();
    instant_url_post_params = t_url->instant_url_post_params();
    image_url_post_params = t_url->image_url_post_params();
    GURL icon_gurl = t_url->favicon_url();
    if (!icon_gurl.is_empty())
      icon_url = icon_gurl.spec();
    encodings = JoinString(t_url->input_encodings(), ';');
    short_name = base::UTF16ToUTF8(t_url->short_name());
    keyword = base::UTF16ToUTF8(t_url->keyword());
    id_string = base::Int64ToString(t_url->id());
    prepopulate_id = base::Int64ToString(t_url->prepopulate_id());
    for (size_t i = 0; i < t_url->alternate_urls().size(); ++i)
      alternate_urls.AppendString(t_url->alternate_urls()[i]);
    search_terms_replacement_key = t_url->search_terms_replacement_key();
  }
  prefs->SetBoolean(prefs::kDefaultSearchProviderEnabled, enabled);
  prefs->SetString(prefs::kDefaultSearchProviderSearchURL, search_url);
  prefs->SetString(prefs::kDefaultSearchProviderSuggestURL, suggest_url);
  prefs->SetString(prefs::kDefaultSearchProviderInstantURL, instant_url);
  prefs->SetString(prefs::kDefaultSearchProviderImageURL, image_url);
  prefs->SetString(prefs::kDefaultSearchProviderNewTabURL, new_tab_url);
  prefs->SetString(prefs::kDefaultSearchProviderSearchURLPostParams,
                   search_url_post_params);
  prefs->SetString(prefs::kDefaultSearchProviderSuggestURLPostParams,
                   suggest_url_post_params);
  prefs->SetString(prefs::kDefaultSearchProviderInstantURLPostParams,
                   instant_url_post_params);
  prefs->SetString(prefs::kDefaultSearchProviderImageURLPostParams,
                   image_url_post_params);
  prefs->SetString(prefs::kDefaultSearchProviderIconURL, icon_url);
  prefs->SetString(prefs::kDefaultSearchProviderEncodings, encodings);
  prefs->SetString(prefs::kDefaultSearchProviderName, short_name);
  prefs->SetString(prefs::kDefaultSearchProviderKeyword, keyword);
  prefs->SetString(prefs::kDefaultSearchProviderID, id_string);
  prefs->SetString(prefs::kDefaultSearchProviderPrepopulateID, prepopulate_id);
  prefs->Set(prefs::kDefaultSearchProviderAlternateURLs, alternate_urls);
  prefs->SetString(prefs::kDefaultSearchProviderSearchTermsReplacementKey,
      search_terms_replacement_key);
}

bool TemplateURLService::LoadDefaultSearchProviderFromPrefs(
    scoped_ptr<TemplateURL>* default_provider,
    bool* is_managed) {
  PrefService* prefs = GetPrefs();
  if (!prefs || !prefs->HasPrefPath(prefs::kDefaultSearchProviderSearchURL))
    return false;

  const PrefService::Preference* pref =
      prefs->FindPreference(prefs::kDefaultSearchProviderSearchURL);
  *is_managed = pref && pref->IsManaged();

  if (!prefs->GetBoolean(prefs::kDefaultSearchProviderEnabled)) {
    // The user doesn't want a default search provider.
    default_provider->reset(NULL);
    return true;
  }

  base::string16 name =
      base::UTF8ToUTF16(prefs->GetString(prefs::kDefaultSearchProviderName));
  base::string16 keyword =
      base::UTF8ToUTF16(prefs->GetString(prefs::kDefaultSearchProviderKeyword));
  // Force keyword to be non-empty.
  // TODO(pkasting): This is only necessary as long as we're potentially loading
  // older prefs where empty keywords are theoretically possible.  Eventually
  // this code can be replaced with a DCHECK(!keyword.empty());.
  bool update_keyword = keyword.empty();
  if (update_keyword)
    keyword = base::ASCIIToUTF16("dummy");
  std::string search_url =
      prefs->GetString(prefs::kDefaultSearchProviderSearchURL);
  // Force URL to be non-empty.  We've never supported this case, but past bugs
  // might have resulted in it slipping through; eventually this code can be
  // replaced with a DCHECK(!search_url.empty());.
  if (search_url.empty())
    return false;
  std::string suggest_url =
      prefs->GetString(prefs::kDefaultSearchProviderSuggestURL);
  std::string instant_url =
      prefs->GetString(prefs::kDefaultSearchProviderInstantURL);
  std::string image_url =
      prefs->GetString(prefs::kDefaultSearchProviderImageURL);
  std::string new_tab_url =
      prefs->GetString(prefs::kDefaultSearchProviderNewTabURL);
  std::string search_url_post_params =
      prefs->GetString(prefs::kDefaultSearchProviderSearchURLPostParams);
  std::string suggest_url_post_params =
      prefs->GetString(prefs::kDefaultSearchProviderSuggestURLPostParams);
  std::string instant_url_post_params =
      prefs->GetString(prefs::kDefaultSearchProviderInstantURLPostParams);
  std::string image_url_post_params =
      prefs->GetString(prefs::kDefaultSearchProviderImageURLPostParams);
  std::string icon_url =
      prefs->GetString(prefs::kDefaultSearchProviderIconURL);
  std::string encodings =
      prefs->GetString(prefs::kDefaultSearchProviderEncodings);
  std::string id_string = prefs->GetString(prefs::kDefaultSearchProviderID);
  std::string prepopulate_id =
      prefs->GetString(prefs::kDefaultSearchProviderPrepopulateID);
  const base::ListValue* alternate_urls =
      prefs->GetList(prefs::kDefaultSearchProviderAlternateURLs);
  std::string search_terms_replacement_key = prefs->GetString(
      prefs::kDefaultSearchProviderSearchTermsReplacementKey);

  TemplateURLData data;
  data.short_name = name;
  data.SetKeyword(keyword);
  data.SetURL(search_url);
  data.suggestions_url = suggest_url;
  data.instant_url = instant_url;
  data.image_url = image_url;
  data.new_tab_url = new_tab_url;
  data.search_url_post_params = search_url_post_params;
  data.suggestions_url_post_params = suggest_url_post_params;
  data.instant_url_post_params = instant_url_post_params;
  data.image_url_post_params = image_url_post_params;
  data.favicon_url = GURL(icon_url);
  data.show_in_default_list = true;
  data.alternate_urls.clear();
  for (size_t i = 0; i < alternate_urls->GetSize(); ++i) {
    std::string alternate_url;
    if (alternate_urls->GetString(i, &alternate_url))
      data.alternate_urls.push_back(alternate_url);
  }
  data.search_terms_replacement_key = search_terms_replacement_key;
  base::SplitString(encodings, ';', &data.input_encodings);
  if (!id_string.empty() && !*is_managed) {
    int64 value;
    base::StringToInt64(id_string, &value);
    data.id = value;
  }
  if (!prepopulate_id.empty() && !*is_managed) {
    int value;
    base::StringToInt(prepopulate_id, &value);
    data.prepopulate_id = value;
  }
  default_provider->reset(new TemplateURL(profile_, data));
  DCHECK_EQ(TemplateURL::NORMAL, (*default_provider)->GetType());
  if (update_keyword)
    (*default_provider)->ResetKeywordIfNecessary(true);
  return true;
}

void TemplateURLService::ClearDefaultProviderFromPrefs() {
  // We overwrite user preferences. If the default search engine is managed,
  // there is no effect.
  SaveDefaultSearchProviderToPrefs(NULL);
  // Default value for kDefaultSearchProviderEnabled is true.
  PrefService* prefs = GetPrefs();
  if (prefs)
    prefs->SetBoolean(prefs::kDefaultSearchProviderEnabled, true);
}

bool TemplateURLService::CanReplaceKeywordForHost(
    const std::string& host,
    TemplateURL** to_replace) {
  DCHECK(!to_replace || !*to_replace);
  const TemplateURLSet* urls = provider_map_->GetURLsForHost(host);
  if (!urls)
    return true;
  for (TemplateURLSet::const_iterator i(urls->begin()); i != urls->end(); ++i) {
    if (CanReplace(*i)) {
      if (to_replace)
        *to_replace = *i;
      return true;
    }
  }
  return false;
}

bool TemplateURLService::CanReplace(const TemplateURL* t_url) {
  return (t_url != default_search_provider_ && !t_url->show_in_default_list() &&
          t_url->safe_for_autoreplace());
}

TemplateURL* TemplateURLService::FindNonExtensionTemplateURLForKeyword(
    const base::string16& keyword) {
  TemplateURL* keyword_turl = GetTemplateURLForKeyword(keyword);
  if (!keyword_turl || (keyword_turl->GetType() == TemplateURL::NORMAL))
    return keyword_turl;
  // The extension keyword in the model may be hiding a replaceable
  // non-extension keyword.  Look for it.
  for (TemplateURLVector::const_iterator i(template_urls_.begin());
       i != template_urls_.end(); ++i) {
    if (((*i)->GetType() == TemplateURL::NORMAL) &&
        ((*i)->keyword() == keyword))
      return *i;
  }
  return NULL;
}

bool TemplateURLService::UpdateNoNotify(
    TemplateURL* existing_turl,
    const TemplateURL& new_values,
    const SearchTermsData& old_search_terms_data) {
  DCHECK(loaded_);
  DCHECK(existing_turl);
  if (std::find(template_urls_.begin(), template_urls_.end(), existing_turl) ==
      template_urls_.end())
    return false;

  base::string16 old_keyword(existing_turl->keyword());
  keyword_to_template_map_.erase(old_keyword);
  if (!existing_turl->sync_guid().empty())
    guid_to_template_map_.erase(existing_turl->sync_guid());

  provider_map_->Remove(existing_turl, old_search_terms_data);
  TemplateURLID previous_id = existing_turl->id();
  existing_turl->CopyFrom(new_values);
  existing_turl->data_.id = previous_id;
  UIThreadSearchTermsData new_search_terms_data(profile_);
  provider_map_->Add(existing_turl, new_search_terms_data);

  const base::string16& keyword = existing_turl->keyword();
  KeywordToTemplateMap::const_iterator i =
      keyword_to_template_map_.find(keyword);
  if (i == keyword_to_template_map_.end()) {
    keyword_to_template_map_[keyword] = existing_turl;
  } else {
    // We can theoretically reach here in two cases:
    //   * There is an existing extension keyword and sync brings in a rename of
    //     a non-extension keyword to match.  In this case we just need to pick
    //     which keyword has priority to update the keyword map.
    //   * Autogeneration of the keyword for a Google default search provider
    //     at load time causes it to conflict with an existing keyword.  In this
    //     case we delete the existing keyword if it's replaceable, or else undo
    //     the change in keyword for |existing_turl|.
    TemplateURL* existing_keyword_turl = i->second;
    if (existing_keyword_turl->GetType() != TemplateURL::NORMAL) {
      if (!CanReplace(existing_turl))
        keyword_to_template_map_[keyword] = existing_turl;
    } else {
      if (CanReplace(existing_keyword_turl)) {
        RemoveNoNotify(existing_keyword_turl);
      } else {
        existing_turl->data_.SetKeyword(old_keyword);
        keyword_to_template_map_[old_keyword] = existing_turl;
      }
    }
  }
  if (!existing_turl->sync_guid().empty())
    guid_to_template_map_[existing_turl->sync_guid()] = existing_turl;

  if (service_.get())
    service_->UpdateKeyword(existing_turl->data());

  // Inform sync of the update.
  ProcessTemplateURLChange(FROM_HERE,
                           existing_turl,
                           syncer::SyncChange::ACTION_UPDATE);

  if (default_search_provider_ == existing_turl) {
    bool success = SetDefaultSearchProviderNoNotify(existing_turl);
    DCHECK(success);
  }
  return true;
}

// static
void TemplateURLService::UpdateTemplateURLIfPrepopulated(
    TemplateURL* template_url,
    Profile* profile) {
  int prepopulate_id = template_url->prepopulate_id();
  if (template_url->prepopulate_id() == 0)
    return;

  size_t default_search_index;
  ScopedVector<TemplateURL> prepopulated_urls =
      TemplateURLPrepopulateData::GetPrepopulatedEngines(profile,
                                                         &default_search_index);

  for (size_t i = 0; i < prepopulated_urls.size(); ++i) {
    if (prepopulated_urls[i]->prepopulate_id() == prepopulate_id) {
      MergeIntoPrepopulatedEngineData(&prepopulated_urls[i]->data_,
                                      template_url);
      template_url->CopyFrom(*prepopulated_urls[i]);
    }
  }
}

PrefService* TemplateURLService::GetPrefs() {
  return profile_ ? profile_->GetPrefs() : NULL;
}

void TemplateURLService::UpdateKeywordSearchTermsForURL(
    const history::URLVisitedDetails& details) {
  const history::URLRow& row = details.row;
  if (!row.url().is_valid())
    return;

  const TemplateURLSet* urls_for_host =
      provider_map_->GetURLsForHost(row.url().host());
  if (!urls_for_host)
    return;

  for (TemplateURLSet::const_iterator i = urls_for_host->begin();
       i != urls_for_host->end(); ++i) {
    base::string16 search_terms;
    if ((*i)->ExtractSearchTermsFromURL(row.url(), &search_terms) &&
        !search_terms.empty()) {
      if (content::PageTransitionStripQualifier(details.transition) ==
          content::PAGE_TRANSITION_KEYWORD) {
        // The visit is the result of the user entering a keyword, generate a
        // KEYWORD_GENERATED visit for the KEYWORD so that the keyword typed
        // count is boosted.
        AddTabToSearchVisit(**i);
      }
      SetKeywordSearchTermsForURL(*i, row.url(), search_terms);
    }
  }
}

void TemplateURLService::AddTabToSearchVisit(const TemplateURL& t_url) {
  // Only add visits for entries the user hasn't modified. If the user modified
  // the entry the keyword may no longer correspond to the host name. It may be
  // possible to do something more sophisticated here, but it's so rare as to
  // not be worth it.
  if (!t_url.safe_for_autoreplace())
    return;

  if (!profile_)
    return;

  HistoryService* history =
      HistoryServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
  if (!history)
    return;

  GURL url(URLFixerUpper::FixupURL(base::UTF16ToUTF8(t_url.keyword()),
                                   std::string()));
  if (!url.is_valid())
    return;

  // Synthesize a visit for the keyword. This ensures the url for the keyword is
  // autocompleted even if the user doesn't type the url in directly.
  history->AddPage(url, base::Time::Now(), NULL, 0, GURL(),
                   history::RedirectList(),
                   content::PAGE_TRANSITION_KEYWORD_GENERATED,
                   history::SOURCE_BROWSED, false);
}

void TemplateURLService::GoogleBaseURLChanged(const GURL& old_base_url) {
  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  bool something_changed = false;
  for (TemplateURLVector::iterator i(template_urls_.begin());
       i != template_urls_.end(); ++i) {
    TemplateURL* t_url = *i;
    if (t_url->url_ref().HasGoogleBaseURLs() ||
        t_url->suggestions_url_ref().HasGoogleBaseURLs()) {
      TemplateURL updated_turl(t_url->profile(), t_url->data());
      updated_turl.ResetKeywordIfNecessary(false);
      KeywordToTemplateMap::const_iterator existing_entry =
          keyword_to_template_map_.find(updated_turl.keyword());
      if ((existing_entry != keyword_to_template_map_.end()) &&
          (existing_entry->second != t_url)) {
        // The new autogenerated keyword conflicts with another TemplateURL.
        // Overwrite it if it's replaceable; otherwise, leave |t_url| using its
        // current keyword.  (This will not prevent |t_url| from auto-updating
        // the keyword in the future if the conflicting TemplateURL disappears.)
        // Note that we must still update |t_url| in this case, or the
        // |provider_map_| will not be updated correctly.
        if (CanReplace(existing_entry->second))
          RemoveNoNotify(existing_entry->second);
        else
          updated_turl.data_.SetKeyword(t_url->keyword());
      }
      something_changed = true;
      // This will send the keyword change to sync.  Note that other clients
      // need to reset the keyword to an appropriate local value when this
      // change arrives; see CreateTemplateURLFromTemplateURLAndSyncData().
      UpdateNoNotify(t_url, updated_turl,
          OldBaseURLSearchTermsData(t_url->profile(), old_base_url.spec()));
    }
  }
  if (something_changed)
    NotifyObservers();
}

void TemplateURLService::UpdateDefaultSearch() {
  if (!loaded_) {
    // Set |initial_default_search_provider_| from the preferences.  We use this
    // value for default search provider until the database has been loaded.
    if (!LoadDefaultSearchProviderFromPrefs(&initial_default_search_provider_,
                                            &is_default_search_managed_)) {
      // Prefs does not specify, so rely on the prepopulated engines.  This
      // should happen only the first time Chrome is started.
      initial_default_search_provider_.reset(
          TemplateURLPrepopulateData::GetPrepopulatedDefaultSearch(profile_));
      is_default_search_managed_ = false;
    }
    return;
  }
  // Load the default search specified in prefs.
  scoped_ptr<TemplateURL> new_default_from_prefs;
  bool new_is_default_managed = false;
  // Load the default from prefs.  It's possible that it won't succeed
  // because we are in the middle of doing SaveDefaultSearchProviderToPrefs()
  // and all the preference items have not been saved.  In that case, we
  // don't have yet a default.  It would be much better if we could save
  // preferences in batches and trigger notifications at the end.
  LoadDefaultSearchProviderFromPrefs(&new_default_from_prefs,
                                     &new_is_default_managed);
  if (!is_default_search_managed_ && !new_is_default_managed) {
    // We're not interested in cases where the default was and remains
    // unmanaged.  In that case, preferences have no impact on the default.
    return;
  }
  WebDataService::KeywordBatchModeScoper keyword_scoper(service_.get());
  if (is_default_search_managed_ && new_is_default_managed) {
    // The default was managed and remains managed.  Update the default only
    // if it has changed; we don't want to respond to changes triggered by
    // SaveDefaultSearchProviderToPrefs.
    if (TemplateURLsHaveSamePrefs(default_search_provider_,
                                  new_default_from_prefs.get()))
      return;
    if (new_default_from_prefs.get() == NULL) {
      // default_search_provider_ can't be NULL otherwise
      // TemplateURLsHaveSamePrefs would have returned true.  Remove this now
      // invalid value.
      TemplateURL* old_default = default_search_provider_;
      bool success = SetDefaultSearchProviderNoNotify(NULL);
      DCHECK(success);
      RemoveNoNotify(old_default);
    } else if (default_search_provider_) {
      TemplateURLData data(new_default_from_prefs->data());
      data.created_by_policy = true;
      TemplateURL new_values(new_default_from_prefs->profile(), data);
      UIThreadSearchTermsData search_terms_data(
          default_search_provider_->profile());
      UpdateNoNotify(default_search_provider_, new_values, search_terms_data);
    } else {
      TemplateURL* new_template = NULL;
      if (new_default_from_prefs.get()) {
        TemplateURLData data(new_default_from_prefs->data());
        data.created_by_policy = true;
        new_template = new TemplateURL(profile_, data);
        if (!AddNoNotify(new_template, true))
          return;
      }
      bool success = SetDefaultSearchProviderNoNotify(new_template);
      DCHECK(success);
    }
  } else if (!is_default_search_managed_ && new_is_default_managed) {
    // The default used to be unmanaged and is now managed.  Add the new
    // managed default to the list of URLs and set it as default.
    is_default_search_managed_ = new_is_default_managed;
    TemplateURL* new_template = NULL;
    if (new_default_from_prefs.get()) {
      TemplateURLData data(new_default_from_prefs->data());
      data.created_by_policy = true;
      new_template = new TemplateURL(profile_, data);
      if (!AddNoNotify(new_template, true))
        return;
    }
    bool success = SetDefaultSearchProviderNoNotify(new_template);
    DCHECK(success);
  } else {
    // The default was managed and is no longer.
    DCHECK(is_default_search_managed_ && !new_is_default_managed);
    is_default_search_managed_ = new_is_default_managed;
    // If we had a default, delete the previous default if created by policy
    // and set a likely default.
    if ((default_search_provider_ != NULL) &&
        default_search_provider_->created_by_policy()) {
      TemplateURL* old_default = default_search_provider_;
      default_search_provider_ = NULL;
      RemoveNoNotify(old_default);
    }

    // The likely default should be from Sync if we were waiting on Sync.
    // Otherwise, it should be FindNewDefaultSearchProvider.
    TemplateURL* synced_default = GetPendingSyncedDefaultSearchProvider();
    if (synced_default) {
      pending_synced_default_search_ = false;

      base::AutoReset<DefaultSearchChangeOrigin> change_origin(
          &dsp_change_origin_, DSP_CHANGE_SYNC_NOT_MANAGED);
      SetDefaultSearchProviderNoNotify(synced_default);
    } else {
      SetDefaultSearchProviderNoNotify(FindNewDefaultSearchProvider());
    }
  }
  NotifyObservers();
}

bool TemplateURLService::SetDefaultSearchProviderNoNotify(TemplateURL* url) {
  if (url) {
    if (std::find(template_urls_.begin(), template_urls_.end(), url) ==
        template_urls_.end())
      return false;
    // Omnibox keywords cannot be made default.
    DCHECK_NE(TemplateURL::OMNIBOX_API_EXTENSION, url->GetType());
  }

  // Only bother reassigning |url| if it has changed. Notice that we don't just
  // early exit if they are equal, because |url| may have had its fields
  // changed, and needs to be persisted below (for example, when this is called
  // from UpdateNoNotify).
  if (default_search_provider_ != url) {
    // Engines set by policy override extension-controlled engines, which
    // override other engines.
    DCHECK(!is_default_search_managed() || !url ||
           (url->GetType() == TemplateURL::NORMAL));
    if (is_default_search_managed() || !default_search_provider_ ||
        (default_search_provider_->GetType() == TemplateURL::NORMAL) ||
        (url &&
         (url->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION))){
      UMA_HISTOGRAM_ENUMERATION("Search.DefaultSearchChangeOrigin",
                                dsp_change_origin_, DSP_CHANGE_MAX);
      default_search_provider_ = url;
    }
  }

  if (url) {
    // Don't mark the url as edited, otherwise we won't be able to rev the
    // template urls we ship with.
    url->data_.show_in_default_list = true;
    if (service_.get() && (url->GetType() == TemplateURL::NORMAL))
      service_->UpdateKeyword(url->data());

    if (url->url_ref().HasGoogleBaseURLs()) {
      GoogleURLTracker::RequestServerCheck(profile_, false);
#if defined(ENABLE_RLZ)
      RLZTracker::RecordProductEvent(rlz_lib::CHROME,
                                     RLZTracker::CHROME_OMNIBOX,
                                     rlz_lib::SET_TO_GOOGLE);
#endif
    }
  }

  // Extension-controlled search engines shouldn't be persisted anywhere.
  if (url && (url->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION))
    return true;

  if (!is_default_search_managed_) {
    SaveDefaultSearchProviderToPrefs(url);

    // If we are syncing, we want to set the synced pref that will notify other
    // instances to change their default to this new search provider.
    // Note: we don't update the pref if we're currently in the middle of
    // handling a sync operation. Sync operations from other clients are not
    // guaranteed to arrive together, and any client that deletes the default
    // needs to set a new default as well. If we update the default here, we're
    // likely to race with the update from the other client, resulting in
    // a possibly random default search provider.
    if (sync_processor_.get() && url && !url->sync_guid().empty() &&
        GetPrefs() && !processing_syncer_changes_) {
      GetPrefs()->SetString(prefs::kSyncedDefaultSearchProviderGUID,
                            url->sync_guid());
    }
  }

  if (service_.get())
    service_->SetDefaultSearchProviderID(url ? url->id() : 0);

  // Inform sync the change to the show_in_default_list flag.
  if (url)
    ProcessTemplateURLChange(FROM_HERE,
                             url,
                             syncer::SyncChange::ACTION_UPDATE);
  return true;
}

bool TemplateURLService::AddNoNotify(TemplateURL* template_url,
                                     bool newly_adding) {
  DCHECK(template_url);

  if (newly_adding) {
    DCHECK_EQ(kInvalidTemplateURLID, template_url->id());
    DCHECK(std::find(template_urls_.begin(), template_urls_.end(),
                     template_url) == template_urls_.end());
    template_url->data_.id = ++next_id_;
  }

  template_url->ResetKeywordIfNecessary(false);
  // Check whether |template_url|'s keyword conflicts with any already in the
  // model.
  TemplateURL* existing_keyword_turl =
      GetTemplateURLForKeyword(template_url->keyword());
  if (existing_keyword_turl != NULL) {
    DCHECK_NE(existing_keyword_turl, template_url);
    // Only replace one of the TemplateURLs if they are either both extensions,
    // or both not extensions.
    bool are_same_type = existing_keyword_turl->GetType() ==
        template_url->GetType();
    if (CanReplace(existing_keyword_turl) && are_same_type) {
      RemoveNoNotify(existing_keyword_turl);
    } else if (CanReplace(template_url) && are_same_type) {
      delete template_url;
      return false;
    } else {
      base::string16 new_keyword =
          UniquifyKeyword(*existing_keyword_turl, false);
      ResetTemplateURL(existing_keyword_turl,
                       existing_keyword_turl->short_name(), new_keyword,
                       existing_keyword_turl->url());
    }
  }
  template_urls_.push_back(template_url);
  AddToMaps(template_url);

  if (newly_adding &&
      (template_url->GetType() !=
          TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)) {
    if (service_.get())
      service_->AddKeyword(template_url->data());

    // Inform sync of the addition. Note that this will assign a GUID to
    // template_url and add it to the guid_to_template_map_.
    ProcessTemplateURLChange(FROM_HERE,
                             template_url,
                             syncer::SyncChange::ACTION_ADD);
  }

  return true;
}

void TemplateURLService::RemoveNoNotify(TemplateURL* template_url) {
  DCHECK(template_url != default_search_provider_);

  TemplateURLVector::iterator i =
      std::find(template_urls_.begin(), template_urls_.end(), template_url);
  if (i == template_urls_.end())
    return;

  RemoveFromMaps(template_url);

  // Remove it from the vector containing all TemplateURLs.
  template_urls_.erase(i);

  if (template_url->GetType() != TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION) {
    if (service_.get())
      service_->RemoveKeyword(template_url->id());

    // Inform sync of the deletion.
    ProcessTemplateURLChange(FROM_HERE,
                             template_url,
                             syncer::SyncChange::ACTION_DELETE);

    UMA_HISTOGRAM_ENUMERATION(kDeleteSyncedEngineHistogramName,
                              DELETE_ENGINE_USER_ACTION, DELETE_ENGINE_MAX);
  }

  if (profile_) {
    content::Source<Profile> source(profile_);
    TemplateURLID id = template_url->id();
    content::NotificationService::current()->Notify(
        chrome::NOTIFICATION_TEMPLATE_URL_REMOVED,
        source,
        content::Details<TemplateURLID>(&id));
  }

  // We own the TemplateURL and need to delete it.
  delete template_url;
}

void TemplateURLService::NotifyObservers() {
  if (!loaded_)
    return;

  FOR_EACH_OBSERVER(TemplateURLServiceObserver, model_observers_,
                    OnTemplateURLServiceChanged());
}

// |template_urls| are the TemplateURLs loaded from the database.
// |default_search_provider| points to one of them, if it was set in the db.
// |default_from_prefs| is the default search provider from the preferences.
// Check |is_default_search_managed_| to determine if it was set by policy.
//
// This function removes from the vector and the database all the TemplateURLs
// that were set by policy, unless it is the current default search provider
// and matches what is set by a managed preference.
void TemplateURLService::RemoveProvidersCreatedByPolicy(
    TemplateURLVector* template_urls,
    TemplateURL** default_search_provider,
    TemplateURL* default_from_prefs) {
  DCHECK(template_urls);
  DCHECK(default_search_provider);
  for (TemplateURLVector::iterator i = template_urls->begin();
       i != template_urls->end(); ) {
    TemplateURL* template_url = *i;
    if (template_url->created_by_policy()) {
      if (template_url == *default_search_provider &&
          is_default_search_managed_ &&
          TemplateURLsHaveSamePrefs(template_url,
                                    default_from_prefs)) {
        // If the database specified a default search provider that was set
        // by policy, and the default search provider from the preferences
        // is also set by policy and they are the same, keep the entry in the
        // database and the |default_search_provider|.
        ++i;
        continue;
      }

      // The database loaded a managed |default_search_provider|, but it has
      // been updated in the prefs. Remove it from the database, and update the
      // |default_search_provider| pointer here.
      if (*default_search_provider &&
          (*default_search_provider)->id() == template_url->id())
        *default_search_provider = NULL;

      i = template_urls->erase(i);
      if (service_.get())
        service_->RemoveKeyword(template_url->id());
      delete template_url;
    } else {
      ++i;
    }
  }
}

void TemplateURLService::ResetTemplateURLGUID(TemplateURL* url,
                                              const std::string& guid) {
  DCHECK(loaded_);
  DCHECK(!guid.empty());

  TemplateURLData data(url->data());
  data.sync_guid = guid;
  TemplateURL new_url(url->profile(), data);
  UIThreadSearchTermsData search_terms_data(url->profile());
  UpdateNoNotify(url, new_url, search_terms_data);
}

base::string16 TemplateURLService::UniquifyKeyword(const TemplateURL& turl,
                                                   bool force) {
  if (!force) {
    // Already unique.
    if (!GetTemplateURLForKeyword(turl.keyword()))
      return turl.keyword();

    // First, try to return the generated keyword for the TemplateURL (except
    // for extensions, as their keywords are not associated with their URLs).
    GURL gurl(turl.url());
    if (gurl.is_valid() &&
        (turl.GetType() != TemplateURL::OMNIBOX_API_EXTENSION)) {
      base::string16 keyword_candidate = GenerateKeyword(gurl);
      if (!GetTemplateURLForKeyword(keyword_candidate))
        return keyword_candidate;
    }
  }

  // We try to uniquify the keyword by appending a special character to the end.
  // This is a best-effort approach where we try to preserve the original
  // keyword and let the user do what they will after our attempt.
  base::string16 keyword_candidate(turl.keyword());
  do {
    keyword_candidate.append(base::ASCIIToUTF16("_"));
  } while (GetTemplateURLForKeyword(keyword_candidate));

  return keyword_candidate;
}

bool TemplateURLService::IsLocalTemplateURLBetter(
    const TemplateURL* local_turl,
    const TemplateURL* sync_turl) {
  DCHECK(GetTemplateURLForGUID(local_turl->sync_guid()));
  return local_turl->last_modified() > sync_turl->last_modified() ||
         local_turl->created_by_policy() ||
         local_turl== GetDefaultSearchProvider();
}

void TemplateURLService::ResolveSyncKeywordConflict(
    TemplateURL* unapplied_sync_turl,
    TemplateURL* applied_sync_turl,
    syncer::SyncChangeList* change_list) {
  DCHECK(loaded_);
  DCHECK(unapplied_sync_turl);
  DCHECK(applied_sync_turl);
  DCHECK(change_list);
  DCHECK_EQ(applied_sync_turl->keyword(), unapplied_sync_turl->keyword());
  DCHECK_NE(TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION,
            applied_sync_turl->GetType());

  // Both |unapplied_sync_turl| and |applied_sync_turl| are known to Sync, so
  // don't delete either of them. Instead, determine which is "better" and
  // uniquify the other one, sending an update to the server for the updated
  // entry.
  const bool applied_turl_is_better =
      IsLocalTemplateURLBetter(applied_sync_turl, unapplied_sync_turl);
  TemplateURL* loser = applied_turl_is_better ?
      unapplied_sync_turl : applied_sync_turl;
  base::string16 new_keyword = UniquifyKeyword(*loser, false);
  DCHECK(!GetTemplateURLForKeyword(new_keyword));
  if (applied_turl_is_better) {
    // Just set the keyword of |unapplied_sync_turl|. The caller is responsible
    // for adding or updating unapplied_sync_turl in the local model.
    unapplied_sync_turl->data_.SetKeyword(new_keyword);
  } else {
    // Update |applied_sync_turl| in the local model with the new keyword.
    TemplateURLData data(applied_sync_turl->data());
    data.SetKeyword(new_keyword);
    TemplateURL new_turl(applied_sync_turl->profile(), data);
    UIThreadSearchTermsData search_terms_data(applied_sync_turl->profile());
    if (UpdateNoNotify(applied_sync_turl, new_turl, search_terms_data))
      NotifyObservers();
  }
  // The losing TemplateURL should have their keyword updated. Send a change to
  // the server to reflect this change.
  syncer::SyncData sync_data = CreateSyncDataFromTemplateURL(*loser);
  change_list->push_back(syncer::SyncChange(FROM_HERE,
      syncer::SyncChange::ACTION_UPDATE,
      sync_data));
}

void TemplateURLService::MergeInSyncTemplateURL(
    TemplateURL* sync_turl,
    const SyncDataMap& sync_data,
    syncer::SyncChangeList* change_list,
    SyncDataMap* local_data,
    syncer::SyncMergeResult* merge_result) {
  DCHECK(sync_turl);
  DCHECK(!GetTemplateURLForGUID(sync_turl->sync_guid()));
  DCHECK(IsFromSync(sync_turl, sync_data));

  TemplateURL* conflicting_turl =
      FindNonExtensionTemplateURLForKeyword(sync_turl->keyword());
  bool should_add_sync_turl = true;

  // If there was no TemplateURL in the local model that conflicts with
  // |sync_turl|, skip the following preparation steps and just add |sync_turl|
  // directly. Otherwise, modify |conflicting_turl| to make room for
  // |sync_turl|.
  if (conflicting_turl) {
    if (IsFromSync(conflicting_turl, sync_data)) {
      // |conflicting_turl| is already known to Sync, so we're not allowed to
      // remove it. In this case, we want to uniquify the worse one and send an
      // update for the changed keyword to sync. We can reuse the logic from
      // ResolveSyncKeywordConflict for this.
      ResolveSyncKeywordConflict(sync_turl, conflicting_turl, change_list);
      merge_result->set_num_items_modified(
          merge_result->num_items_modified() + 1);
    } else {
      // |conflicting_turl| is not yet known to Sync. If it is better, then we
      // want to transfer its values up to sync. Otherwise, we remove it and
      // allow the entry from Sync to overtake it in the model.
      const std::string guid = conflicting_turl->sync_guid();
      if (IsLocalTemplateURLBetter(conflicting_turl, sync_turl)) {
        ResetTemplateURLGUID(conflicting_turl, sync_turl->sync_guid());
        syncer::SyncData sync_data =
            CreateSyncDataFromTemplateURL(*conflicting_turl);
        change_list->push_back(syncer::SyncChange(
            FROM_HERE, syncer::SyncChange::ACTION_UPDATE, sync_data));
        if (conflicting_turl == GetDefaultSearchProvider() &&
            !pending_synced_default_search_) {
          // If we're not waiting for the Synced default to come in, we should
          // override the pref with our new GUID. If we are waiting for the
          // arrival of a synced default, setting the pref here would cause us
          // to lose the GUID we are waiting on.
          PrefService* prefs = GetPrefs();
          if (prefs) {
            prefs->SetString(prefs::kSyncedDefaultSearchProviderGUID,
                             conflicting_turl->sync_guid());
          }
        }
        // Note that in this case we do not add the Sync TemplateURL to the
        // local model, since we've effectively "merged" it in by updating the
        // local conflicting entry with its sync_guid.
        should_add_sync_turl = false;
        merge_result->set_num_items_modified(
            merge_result->num_items_modified() + 1);
      } else {
        // We guarantee that this isn't the local search provider. Otherwise,
        // local would have won.
        DCHECK(conflicting_turl != GetDefaultSearchProvider());
        Remove(conflicting_turl);
        merge_result->set_num_items_deleted(
            merge_result->num_items_deleted() + 1);
      }
      // This TemplateURL was either removed or overwritten in the local model.
      // Remove the entry from the local data so it isn't pushed up to Sync.
      local_data->erase(guid);
    }
  }

  if (should_add_sync_turl) {
    // Force the local ID to kInvalidTemplateURLID so we can add it.
    TemplateURLData data(sync_turl->data());
    data.id = kInvalidTemplateURLID;
    Add(new TemplateURL(profile_, data));
    merge_result->set_num_items_added(
        merge_result->num_items_added() + 1);
  }
}

void TemplateURLService::SetDefaultSearchProviderIfNewlySynced(
    const std::string& guid) {
  // If we're not syncing or if default search is managed by policy, ignore.
  if (!sync_processor_.get() || is_default_search_managed_)
    return;

  PrefService* prefs = GetPrefs();
  if (prefs && pending_synced_default_search_ &&
      prefs->GetString(prefs::kSyncedDefaultSearchProviderGUID) == guid) {
    // Make sure this actually exists. We should not be calling this unless we
    // really just added this TemplateURL.
    TemplateURL* turl_from_sync = GetTemplateURLForGUID(guid);
    if (turl_from_sync && turl_from_sync->SupportsReplacement()) {
      base::AutoReset<DefaultSearchChangeOrigin> change_origin(
          &dsp_change_origin_, DSP_CHANGE_SYNC_ADD);
      SetDefaultSearchProvider(turl_from_sync);
    }
    pending_synced_default_search_ = false;
  }
}

TemplateURL* TemplateURLService::GetPendingSyncedDefaultSearchProvider() {
  PrefService* prefs = GetPrefs();
  if (!prefs || !pending_synced_default_search_)
    return NULL;

  // Could be NULL if no such thing exists.
  return GetTemplateURLForGUID(
      prefs->GetString(prefs::kSyncedDefaultSearchProviderGUID));
}

void TemplateURLService::PatchMissingSyncGUIDs(
    TemplateURLVector* template_urls) {
  DCHECK(template_urls);
  for (TemplateURLVector::iterator i = template_urls->begin();
       i != template_urls->end(); ++i) {
    TemplateURL* template_url = *i;
    DCHECK(template_url);
    if (template_url->sync_guid().empty() &&
        (template_url->GetType() !=
            TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION)) {
      template_url->data_.sync_guid = base::GenerateGUID();
      if (service_.get())
        service_->UpdateKeyword(template_url->data());
    }
  }
}

void TemplateURLService::AddTemplateURLsAndSetupDefaultEngine(
    TemplateURLVector* template_urls,
    TemplateURL* default_search_provider) {
  DCHECK(template_urls);
  is_default_search_managed_ = false;
  bool database_specified_a_default = (default_search_provider != NULL);

  // Check if default search provider is now managed.
  scoped_ptr<TemplateURL> default_from_prefs;
  LoadDefaultSearchProviderFromPrefs(&default_from_prefs,
                                     &is_default_search_managed_);

  // Remove entries that were created because of policy as they may have
  // changed since the database was saved.
  RemoveProvidersCreatedByPolicy(template_urls,
                                 &default_search_provider,
                                 default_from_prefs.get());

  PatchMissingSyncGUIDs(template_urls);

  if (is_default_search_managed_) {
    SetTemplateURLs(template_urls);

    if (TemplateURLsHaveSamePrefs(default_search_provider,
                                  default_from_prefs.get())) {
      // The value from the preferences was previously stored in the database.
      // Reuse it.
    } else {
      // The value from the preferences takes over.
      default_search_provider = NULL;
      if (default_from_prefs) {
        TemplateURLData data(default_from_prefs->data());
        data.created_by_policy = true;
        data.id = kInvalidTemplateURLID;
        default_search_provider = new TemplateURL(profile_, data);
        if (!AddNoNotify(default_search_provider, true))
          default_search_provider = NULL;
      }
    }
    // Note that this saves the default search provider to prefs.
    if (!default_search_provider ||
        ((default_search_provider->GetType() !=
            TemplateURL::OMNIBOX_API_EXTENSION) &&
         default_search_provider->SupportsReplacement())) {
      bool success = SetDefaultSearchProviderNoNotify(default_search_provider);
      DCHECK(success);
    }
  } else {
    // If we had a managed default, replace it with the synced default if
    // applicable, or the first provider of the list.
    TemplateURL* synced_default = GetPendingSyncedDefaultSearchProvider();
    if (synced_default) {
      default_search_provider = synced_default;
      pending_synced_default_search_ = false;
    } else if (database_specified_a_default &&
        default_search_provider == NULL) {
      UMA_HISTOGRAM_ENUMERATION(kFirstPotentialEngineHistogramName,
                                FIRST_POTENTIAL_CALLSITE_ON_LOAD,
                                FIRST_POTENTIAL_CALLSITE_MAX);
      default_search_provider = FirstPotentialDefaultEngine(*template_urls);
    }

    // If the default search provider existed previously, then just
    // set the member variable. Otherwise, we'll set it using the method
    // to ensure that it is saved properly after its id is set.
    if (default_search_provider &&
        (default_search_provider->id() != kInvalidTemplateURLID)) {
      default_search_provider_ = default_search_provider;
      default_search_provider = NULL;
    }
    SetTemplateURLs(template_urls);

    if (default_search_provider) {
      base::AutoReset<DefaultSearchChangeOrigin> change_origin(
          &dsp_change_origin_, default_from_prefs ?
              dsp_change_origin_ : DSP_CHANGE_NEW_ENGINE_NO_PREFS);
      // Note that this saves the default search provider to prefs.
      SetDefaultSearchProvider(default_search_provider);
    } else {
      // Always save the default search provider to prefs. That way we don't
      // have to worry about it being out of sync.
      if (default_search_provider_)
        SaveDefaultSearchProviderToPrefs(default_search_provider_);
    }
  }
}

void TemplateURLService::EnsureDefaultSearchProviderExists() {
  if (!is_default_search_managed()) {
    bool has_default_search_provider = default_search_provider_ &&
        default_search_provider_->SupportsReplacement();
    UMA_HISTOGRAM_BOOLEAN("Search.HasDefaultSearchProvider",
                          has_default_search_provider);
    // Ensure that default search provider exists. See http://crbug.com/116952.
    if (!has_default_search_provider) {
      bool success =
          SetDefaultSearchProviderNoNotify(FindNewDefaultSearchProvider());
      DCHECK(success);
    }
    // Don't log anything if the user has a NULL default search provider.
    if (default_search_provider_) {
      UMA_HISTOGRAM_ENUMERATION("Search.DefaultSearchProviderType",
          TemplateURLPrepopulateData::GetEngineType(*default_search_provider_),
          SEARCH_ENGINE_MAX);
    }
  }
}

TemplateURL* TemplateURLService::CreateTemplateURLForExtension(
    const ExtensionKeyword& extension_keyword) const {
  TemplateURLData data;
  data.short_name = base::UTF8ToUTF16(extension_keyword.extension_name);
  data.SetKeyword(base::UTF8ToUTF16(extension_keyword.extension_keyword));
  // This URL is not actually used for navigation. It holds the extension's
  // ID, as well as forcing the TemplateURL to be treated as a search keyword.
  data.SetURL(std::string(extensions::kExtensionScheme) + "://" +
      extension_keyword.extension_id + "/?q={searchTerms}");
  return new TemplateURL(profile_, data);
}

TemplateURL* TemplateURLService::FindTemplateURLForExtension(
    const std::string& extension_id,
    TemplateURL::Type type) const {
  DCHECK_NE(TemplateURL::NORMAL, type);
  for (TemplateURLVector::const_iterator i = template_urls_.begin();
       i != template_urls_.end(); ++i) {
    if ((*i)->GetType() == type &&
        (*i)->GetExtensionId() == extension_id)
      return *i;
  }

  return NULL;
}

TemplateURL* TemplateURLService::FindExtensionDefaultSearchEngine() const {
  TemplateURL* most_recently_intalled_default = NULL;
  for (TemplateURLVector::const_iterator i = template_urls_.begin();
       i != template_urls_.end(); ++i) {
    if (((*i)->GetType() == TemplateURL::NORMAL_CONTROLLED_BY_EXTENSION) &&
        (*i)->extension_info_->wants_to_be_default_engine &&
        (*i)->SupportsReplacement() &&
        (!most_recently_intalled_default ||
         (most_recently_intalled_default->extension_info_->install_time <
             (*i)->extension_info_->install_time)))
      most_recently_intalled_default = *i;
  }

  return most_recently_intalled_default;
}

void TemplateURLService::
    SetDefaultSearchProviderAfterRemovingDefaultExtension() {
  DCHECK(!is_default_search_managed());
  TemplateURL* new_dse = FindExtensionDefaultSearchEngine();
  if (!new_dse) {
    scoped_ptr<TemplateURL> default_provider;
    bool is_managed;
    if (LoadDefaultSearchProviderFromPrefs(&default_provider, &is_managed) &&
        default_provider) {
      for (TemplateURLVector::const_iterator i = template_urls_.begin();
           i != template_urls_.end(); ++i) {
        if ((*i)->id() == default_provider->id()) {
          new_dse = *i;
          break;
        }
      }
    }
  }
  if (!new_dse)
    new_dse = FindNewDefaultSearchProvider();
  SetDefaultSearchProviderNoNotify(new_dse);
}