components/search_engines/template_url.cc

   1 // Copyright 2014 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/search_engines/template_url.h"
   6
   7 #include <string>
   8 #include <tuple>
   9 #include <vector>
  10
  11 #include "base/base64.h"
  12 #include "base/base64url.h"
  13 #include "base/check_op.h"
  14 #include "base/command_line.h"
  15 #include "base/containers/adapters.h"
  16 #include "base/containers/contains.h"
  17 #include "base/feature_list.h"
  18 #include "base/format_macros.h"
  19 #include "base/i18n/case_conversion.h"
  20 #include "base/i18n/icu_string_conversions.h"
  21 #include "base/i18n/rtl.h"
  22 #include "base/metrics/field_trial.h"
  23 #include "base/metrics/histogram_functions.h"
  24 #include "base/notreached.h"
  25 #include "base/ranges/algorithm.h"
  26 #include "base/strings/escape.h"
  27 #include "base/strings/strcat.h"
  28 #include "base/strings/string_number_conversions.h"
  29 #include "base/strings/string_piece.h"
  30 #include "base/strings/string_split.h"
  31 #include "base/strings/string_util.h"
  32 #include "base/strings/stringprintf.h"
  33 #include "base/strings/utf_string_conversions.h"
  34 #include "base/trace_event/memory_usage_estimator.h"
  35 #include "build/build_config.h"
  36 #include "components/google/core/common/google_util.h"
  37 #include "components/omnibox/common/omnibox_features.h"
  38 #include "components/search_engines/search_engine_utils.h"
  39 #include "components/search_engines/search_engines_switches.h"
  40 #include "components/search_engines/search_terms_data.h"
  41 #include "components/url_formatter/url_formatter.h"
  42 #include "google_apis/google_api_keys.h"
  43 #include "net/base/mime_util.h"
  44 #include "net/base/url_util.h"
  45 #include "template_url_starter_pack_data.h"
  46 #include "third_party/metrics_proto/omnibox_input_type.pb.h"
  47 #include "ui/base/device_form_factor.h"
  48 #include "url/gurl.h"
  49
  50 namespace {
  51
  52 // The TemplateURLRef has any number of terms that need to be replaced. Each of
  53 // the terms is enclosed in braces. If the character preceeding the final
  54 // brace is a ?, it indicates the term is optional and can be replaced with
  55 // an empty string.
  56 const char kStartParameter = '{';
  57 const char kEndParameter = '}';
  58 const char kOptional = '?';
  59
  60 // Known parameters found in the URL.
  61 const char kSearchTermsParameter[] = "searchTerms";
  62 const char kSearchTermsParameterFull[] = "{searchTerms}";
  63 const char kSearchTermsParameterFullEscaped[] = "%7BsearchTerms%7D";
  64
  65 // Same as kSearchTermsParameter, with no escaping.
  66 const char kGoogleUnescapedSearchTermsParameter[] =
  67     "google:unescapedSearchTerms";
  68 const char kGoogleUnescapedSearchTermsParameterFull[] =
  69     "{google:unescapedSearchTerms}";
  70
  71 // Display value for kSearchTermsParameter.
  72 const char kDisplaySearchTerms[] = "%s";
  73
  74 // Display value for kGoogleUnescapedSearchTermsParameter.
  75 const char kDisplayUnescapedSearchTerms[] = "%S";
  76
  77 // Used if the count parameter is not optional. Indicates we want 10 search
  78 // results.
  79 const char kDefaultCount[] = "10";
  80
  81 // Used if the output encoding parameter is required.
  82 const char kOutputEncodingType[] = "UTF-8";
  83
  84 const size_t kMaxStringEncodeStringLength = 1'000'000;
  85
  86 // Attempts to encode |terms| and |original_query| in |encoding| and escape
  87 // them.  |terms| may be escaped as path or query depending on |is_in_query|;
  88 // |original_query| is always escaped as query. If |force_encode| is true
  89 // encoding ignores errors and function always returns true. Otherwise function
  90 // returns whether the encoding process succeeded.
  91 bool TryEncoding(const std::u16string& terms,
  92                  const std::u16string& original_query,
  93                  const char* encoding,
  94                  bool is_in_query,
  95                  bool force_encode,
  96                  std::u16string* escaped_terms,
  97                  std::u16string* escaped_original_query) {
  98   DCHECK(escaped_terms);
  99   DCHECK(escaped_original_query);
 100
 101   // Both |base::UTF16ToCodepage()| and |net::Escape*()| invocations below
 102   // create strings longer than their inputs. To ensure doing so does not crash,
 103   // this truncates |terms| to |kMaxStringEncodeStringLength|.
 104   const std::u16string& truncated_terms =
 105       terms.size() > kMaxStringEncodeStringLength
 106           ? terms.substr(0, kMaxStringEncodeStringLength)
 107           : terms;
 108
 109   base::OnStringConversionError::Type error_handling =
 110       force_encode ? base::OnStringConversionError::SKIP
 111                    : base::OnStringConversionError::FAIL;
 112   std::string encoded_terms;
 113   if (!base::UTF16ToCodepage(truncated_terms, encoding, error_handling,
 114                              &encoded_terms)) {
 115     return false;
 116   }
 117   *escaped_terms = base::UTF8ToUTF16(
 118       is_in_query ? base::EscapeQueryParamValue(encoded_terms, true)
 119                   : base::EscapePath(encoded_terms));
 120   if (original_query.empty())
 121     return true;
 122   std::string encoded_original_query;
 123   if (!base::UTF16ToCodepage(original_query, encoding, error_handling,
 124                              &encoded_original_query))
 125     return false;
 126   *escaped_original_query = base::UTF8ToUTF16(
 127       base::EscapeQueryParamValue(encoded_original_query, true));
 128   return true;
 129 }
 130
 131 // Finds the position of the search terms' parameter in the URL component.
 132 class SearchTermLocation {
 133  public:
 134   SearchTermLocation(const base::StringPiece& url_component,
 135                      url::Parsed::ComponentType url_component_type)
 136       : found_(false) {
 137     if (url_component_type == url::Parsed::PATH) {
 138       // GURL's constructor escapes "{" and "}" in the path of a passed string.
 139       found_ =
 140           TryMatchSearchParam(url_component, kSearchTermsParameterFullEscaped);
 141     } else {
 142       DCHECK((url_component_type == url::Parsed::QUERY) ||
 143              (url_component_type == url::Parsed::REF));
 144       url::Component query, key, value;
 145       query.len = static_cast<int>(url_component.size());
 146       while (url::ExtractQueryKeyValue(url_component.data(), &query, &key,
 147                                        &value)) {
 148         if (key.is_nonempty() && value.is_nonempty()) {
 149           const base::StringPiece value_string =
 150               url_component.substr(value.begin, value.len);
 151           if (TryMatchSearchParam(value_string, kSearchTermsParameterFull) ||
 152               TryMatchSearchParam(value_string,
 153                                   kGoogleUnescapedSearchTermsParameterFull)) {
 154             found_ = true;
 155             key_ = std::string(url_component.substr(key.begin, key.len));
 156             break;
 157           }
 158         }
 159       }
 160     }
 161   }
 162
 163   SearchTermLocation(const SearchTermLocation&) = delete;
 164   SearchTermLocation& operator=(const SearchTermLocation&) = delete;
 165
 166   bool found() const { return found_; }
 167   const std::string& key() const { return key_; }
 168   const std::string& value_prefix() const { return value_prefix_; }
 169   const std::string& value_suffix() const { return value_suffix_; }
 170
 171  private:
 172   // Returns true if the search term placeholder is present, and also assigns
 173   // the constant prefix/suffix found.
 174   bool TryMatchSearchParam(const base::StringPiece& value,
 175                            const base::StringPiece& pattern) {
 176     size_t pos = value.find(pattern);
 177     if (pos == base::StringPiece::npos)
 178       return false;
 179     value_prefix_ = std::string(value.substr(0, pos));
 180     value_suffix_ = std::string(value.substr(pos + pattern.size()));
 181     return true;
 182   }
 183
 184   bool found_;
 185   std::string key_;
 186   std::string value_prefix_;
 187   std::string value_suffix_;
 188 };
 189
 190 bool IsTemplateParameterString(const std::string& param) {
 191   return (param.length() > 2) && (*(param.begin()) == kStartParameter) &&
 192       (*(param.rbegin()) == kEndParameter);
 193 }
 194
 195 std::string YandexSearchPathFromDeviceFormFactor() {
 196   switch (ui::GetDeviceFormFactor()) {
 197     case ui::DEVICE_FORM_FACTOR_DESKTOP:
 198       return "search/";
 199     case ui::DEVICE_FORM_FACTOR_PHONE:
 200       return "search/touch/";
 201     case ui::DEVICE_FORM_FACTOR_TABLET:
 202       return "search/pad/";
 203   }
 204   NOTREACHED();
 205   return std::string();
 206 }
 207
 208 }  // namespace
 209
 210 // TemplateURLRef::SearchTermsArgs --------------------------------------------
 211
 212 TemplateURLRef::SearchTermsArgs::SearchTermsArgs() = default;
 213
 214 TemplateURLRef::SearchTermsArgs::SearchTermsArgs(
 215     const std::u16string& search_terms)
 216     : search_terms(search_terms) {}
 217
 218 TemplateURLRef::SearchTermsArgs::SearchTermsArgs(const SearchTermsArgs& other) =
 219     default;
 220
 221 TemplateURLRef::SearchTermsArgs::~SearchTermsArgs() {
 222 }
 223
 224 size_t TemplateURLRef::SearchTermsArgs::EstimateMemoryUsage() const {
 225   size_t res = 0;
 226
 227   res += base::trace_event::EstimateMemoryUsage(search_terms);
 228   res += base::trace_event::EstimateMemoryUsage(original_query);
 229   res += base::trace_event::EstimateMemoryUsage(assisted_query_stats);
 230   res += base::trace_event::EstimateMemoryUsage(current_page_url);
 231   res += base::trace_event::EstimateMemoryUsage(session_token);
 232   res += base::trace_event::EstimateMemoryUsage(prefetch_query);
 233   res += base::trace_event::EstimateMemoryUsage(prefetch_query_type);
 234   res += base::trace_event::EstimateMemoryUsage(additional_query_params);
 235   res += base::trace_event::EstimateMemoryUsage(image_thumbnail_content);
 236   res += base::trace_event::EstimateMemoryUsage(image_thumbnail_content_type);
 237   res += base::trace_event::EstimateMemoryUsage(image_url);
 238   res += base::trace_event::EstimateMemoryUsage(contextual_search_params);
 239   res += base::trace_event::EstimateMemoryUsage(image_translate_source_locale);
 240   res += base::trace_event::EstimateMemoryUsage(image_translate_target_locale);
 241
 242   return res;
 243 }
 244
 245 TemplateURLRef::SearchTermsArgs::ContextualSearchParams::
 246     ContextualSearchParams() = default;
 247
 248 TemplateURLRef::SearchTermsArgs::ContextualSearchParams::ContextualSearchParams(
 249     int version,
 250     int contextual_cards_version,
 251     std::string home_country,
 252     int64_t previous_event_id,
 253     int previous_event_results,
 254     bool is_exact_search,
 255     std::string source_lang,
 256     std::string target_lang,
 257     std::string fluent_languages,
 258     std::string related_searches_stamp,
 259     bool apply_lang_hint)
 260     : version(version),
 261       contextual_cards_version(contextual_cards_version),
 262       home_country(home_country),
 263       previous_event_id(previous_event_id),
 264       previous_event_results(previous_event_results),
 265       is_exact_search(is_exact_search),
 266       source_lang(source_lang),
 267       target_lang(target_lang),
 268       fluent_languages(fluent_languages),
 269       related_searches_stamp(related_searches_stamp),
 270       apply_lang_hint(apply_lang_hint) {}
 271
 272 TemplateURLRef::SearchTermsArgs::ContextualSearchParams::ContextualSearchParams(
 273     const ContextualSearchParams& other) = default;
 274
 275 TemplateURLRef::SearchTermsArgs::ContextualSearchParams::
 276     ~ContextualSearchParams() {
 277 }
 278
 279 size_t
 280 TemplateURLRef::SearchTermsArgs::ContextualSearchParams::EstimateMemoryUsage()
 281     const {
 282   return base::trace_event::EstimateMemoryUsage(home_country);
 283 }
 284
 285 // TemplateURLRef -------------------------------------------------------------
 286
 287 TemplateURLRef::TemplateURLRef(const TemplateURL* owner, Type type)
 288     : owner_(owner), type_(type) {
 289   DCHECK(owner_);
 290   DCHECK_NE(INDEXED, type_);
 291 }
 292
 293 TemplateURLRef::TemplateURLRef(const TemplateURL* owner, size_t index_in_owner)
 294     : owner_(owner), type_(INDEXED), index_in_owner_(index_in_owner) {
 295   DCHECK(owner_);
 296   DCHECK_LT(index_in_owner_, owner_->alternate_urls().size());
 297 }
 298
 299 TemplateURLRef::~TemplateURLRef() {
 300 }
 301
 302 TemplateURLRef::TemplateURLRef(const TemplateURLRef& source) = default;
 303
 304 TemplateURLRef& TemplateURLRef::operator=(const TemplateURLRef& source) =
 305     default;
 306
 307 std::string TemplateURLRef::GetURL() const {
 308   switch (type_) {
 309     case SEARCH:
 310       return owner_->url();
 311     case SUGGEST:
 312       return owner_->suggestions_url();
 313     case IMAGE:
 314       return owner_->image_url();
 315     case IMAGE_TRANSLATE:
 316       return owner_->image_translate_url();
 317     case NEW_TAB:
 318       return owner_->new_tab_url();
 319     case CONTEXTUAL_SEARCH:
 320       return owner_->contextual_search_url();
 321     case INDEXED:
 322       return owner_->alternate_urls()[index_in_owner_];
 323     default:
 324       NOTREACHED();
 325       return std::string();
 326   }
 327 }
 328
 329 std::string TemplateURLRef::GetPostParamsString() const {
 330   switch (type_) {
 331     case INDEXED:
 332     case SEARCH:
 333       return owner_->search_url_post_params();
 334     case SUGGEST:
 335       return owner_->suggestions_url_post_params();
 336     case NEW_TAB:
 337       return std::string();
 338     case CONTEXTUAL_SEARCH:
 339       return std::string();
 340     case IMAGE:
 341     case IMAGE_TRANSLATE:
 342       return owner_->image_url_post_params();
 343     default:
 344       NOTREACHED();
 345       return std::string();
 346   }
 347 }
 348
 349 bool TemplateURLRef::UsesPOSTMethod(
 350     const SearchTermsData& search_terms_data) const {
 351   ParseIfNecessary(search_terms_data);
 352   return !post_params_.empty();
 353 }
 354
 355 size_t TemplateURLRef::EstimateMemoryUsage() const {
 356   size_t res = 0;
 357
 358   res += base::trace_event::EstimateMemoryUsage(parsed_url_);
 359   res += base::trace_event::EstimateMemoryUsage(replacements_);
 360   res += base::trace_event::EstimateMemoryUsage(host_);
 361   res += base::trace_event::EstimateMemoryUsage(port_);
 362   res += base::trace_event::EstimateMemoryUsage(path_prefix_);
 363   res += base::trace_event::EstimateMemoryUsage(path_suffix_);
 364   res += base::trace_event::EstimateMemoryUsage(search_term_key_);
 365   res += base::trace_event::EstimateMemoryUsage(search_term_value_prefix_);
 366   res += base::trace_event::EstimateMemoryUsage(search_term_value_suffix_);
 367   res += base::trace_event::EstimateMemoryUsage(post_params_);
 368   res += sizeof(path_wildcard_present_);
 369
 370   return res;
 371 }
 372
 373 size_t TemplateURLRef::PostParam::EstimateMemoryUsage() const {
 374   size_t res = 0;
 375
 376   res += base::trace_event::EstimateMemoryUsage(name);
 377   res += base::trace_event::EstimateMemoryUsage(value);
 378   res += base::trace_event::EstimateMemoryUsage(content_type);
 379
 380   return res;
 381 }
 382
 383 bool TemplateURLRef::EncodeFormData(const PostParams& post_params,
 384                                     PostContent* post_content) const {
 385   if (post_params.empty())
 386     return true;
 387   if (!post_content)
 388     return false;
 389
 390   const char kUploadDataMIMEType[] = "multipart/form-data; boundary=";
 391   // Each name/value pair is stored in a body part which is preceded by a
 392   // boundary delimiter line.
 393   std::string boundary = net::GenerateMimeMultipartBoundary();
 394   // Sets the content MIME type.
 395   post_content->first = kUploadDataMIMEType;
 396   post_content->first += boundary;
 397   // Encodes the post parameters.
 398   std::string* post_data = &post_content->second;
 399   post_data->clear();
 400   for (const auto& param : post_params) {
 401     DCHECK(!param.name.empty());
 402     net::AddMultipartValueForUpload(param.name, param.value, boundary,
 403                                     param.content_type, post_data);
 404   }
 405   net::AddMultipartFinalDelimiterForUpload(boundary, post_data);
 406   return true;
 407 }
 408
 409 bool TemplateURLRef::SupportsReplacement(
 410     const SearchTermsData& search_terms_data) const {
 411   ParseIfNecessary(search_terms_data);
 412   return valid_ && supports_replacements_;
 413 }
 414
 415 std::string TemplateURLRef::ReplaceSearchTerms(
 416     const SearchTermsArgs& search_terms_args,
 417     const SearchTermsData& search_terms_data,
 418     PostContent* post_content) const {
 419   ParseIfNecessary(search_terms_data);
 420   if (!valid_)
 421     return std::string();
 422
 423   std::string url(HandleReplacements(search_terms_args, search_terms_data,
 424                                      post_content));
 425
 426   GURL gurl(url);
 427   if (!gurl.is_valid())
 428     return url;
 429
 430   std::vector<std::string> query_params;
 431   if (search_terms_args.append_extra_query_params_from_command_line) {
 432     std::string extra_params(
 433         base::CommandLine::ForCurrentProcess()->GetSwitchValueASCII(
 434             switches::kExtraSearchQueryParams));
 435     if (!extra_params.empty())
 436       query_params.push_back(extra_params);
 437   }
 438   if (!search_terms_args.additional_query_params.empty())
 439     query_params.push_back(search_terms_args.additional_query_params);
 440   if (!gurl.query().empty())
 441     query_params.push_back(gurl.query());
 442   if (owner_->created_from_play_api()) {
 443     // Append attribution parameter to query originating from Play API search
 444     // engine.
 445     query_params.push_back("chrome_dse_attribution=1");
 446   }
 447
 448   if (query_params.empty())
 449     return url;
 450
 451   GURL::Replacements replacements;
 452   std::string query_str = base::JoinString(query_params, "&");
 453   replacements.SetQueryStr(query_str);
 454   return gurl.ReplaceComponents(replacements).possibly_invalid_spec();
 455 }
 456
 457 bool TemplateURLRef::IsValid(const SearchTermsData& search_terms_data) const {
 458   ParseIfNecessary(search_terms_data);
 459   return valid_;
 460 }
 461
 462 std::u16string TemplateURLRef::DisplayURL(
 463     const SearchTermsData& search_terms_data) const {
 464   ParseIfNecessary(search_terms_data);
 465   std::string result(GetURL());
 466   if (valid_ && !replacements_.empty()) {
 467     base::ReplaceSubstringsAfterOffset(&result, 0,
 468                                        kSearchTermsParameterFull,
 469                                        kDisplaySearchTerms);
 470     base::ReplaceSubstringsAfterOffset(&result, 0,
 471                                        kGoogleUnescapedSearchTermsParameterFull,
 472                                        kDisplayUnescapedSearchTerms);
 473   }
 474   return base::UTF8ToUTF16(result);
 475 }
 476
 477 // static
 478 std::string TemplateURLRef::DisplayURLToURLRef(
 479     const std::u16string& display_url) {
 480   std::string result = base::UTF16ToUTF8(display_url);
 481   base::ReplaceSubstringsAfterOffset(&result, 0,
 482                                      kDisplaySearchTerms,
 483                                      kSearchTermsParameterFull);
 484   base::ReplaceSubstringsAfterOffset(&result, 0,
 485                                      kDisplayUnescapedSearchTerms,
 486                                      kGoogleUnescapedSearchTermsParameterFull);
 487   return result;
 488 }
 489
 490 const std::string& TemplateURLRef::GetHost(
 491     const SearchTermsData& search_terms_data) const {
 492   ParseIfNecessary(search_terms_data);
 493   return host_;
 494 }
 495
 496 std::string TemplateURLRef::GetPath(
 497     const SearchTermsData& search_terms_data) const {
 498   ParseIfNecessary(search_terms_data);
 499   return path_prefix_ + path_suffix_;
 500 }
 501
 502 const std::string& TemplateURLRef::GetSearchTermKey(
 503     const SearchTermsData& search_terms_data) const {
 504   ParseIfNecessary(search_terms_data);
 505   return search_term_key_;
 506 }
 507
 508 url::Parsed::ComponentType TemplateURLRef::GetSearchTermKeyLocation(
 509     const SearchTermsData& search_terms_data) const {
 510   ParseIfNecessary(search_terms_data);
 511   return search_term_key_location_;
 512 }
 513
 514 const std::string& TemplateURLRef::GetSearchTermValuePrefix(
 515     const SearchTermsData& search_terms_data) const {
 516   ParseIfNecessary(search_terms_data);
 517   return search_term_value_prefix_;
 518 }
 519
 520 const std::string& TemplateURLRef::GetSearchTermValueSuffix(
 521     const SearchTermsData& search_terms_data) const {
 522   ParseIfNecessary(search_terms_data);
 523   return search_term_value_suffix_;
 524 }
 525
 526 std::u16string TemplateURLRef::SearchTermToString16(
 527     const base::StringPiece& term) const {
 528   const std::vector<std::string>& encodings = owner_->input_encodings();
 529   std::u16string result;
 530
 531   base::UnescapeRule::Type unescape_rules =
 532       base::UnescapeRule::SPACES | base::UnescapeRule::PATH_SEPARATORS |
 533       base::UnescapeRule::URL_SPECIAL_CHARS_EXCEPT_PATH_SEPARATORS;
 534   if (search_term_key_location_ != url::Parsed::PATH)
 535     unescape_rules |= base::UnescapeRule::REPLACE_PLUS_WITH_SPACE;
 536
 537   std::string unescaped = base::UnescapeURLComponent(term, unescape_rules);
 538   for (size_t i = 0; i < encodings.size(); ++i) {
 539     if (base::CodepageToUTF16(unescaped, encodings[i].c_str(),
 540                               base::OnStringConversionError::FAIL, &result))
 541       return result;
 542   }
 543
 544   // Always fall back on UTF-8 if it works.
 545   if (base::CodepageToUTF16(unescaped, base::kCodepageUTF8,
 546                             base::OnStringConversionError::FAIL, &result))
 547     return result;
 548
 549   // When nothing worked, just use the escaped text. We have no idea what the
 550   // encoding is. We need to substitute spaces for pluses ourselves since we're
 551   // not sending it through an unescaper.
 552   result = base::UTF8ToUTF16(term);
 553   if (unescape_rules & base::UnescapeRule::REPLACE_PLUS_WITH_SPACE)
 554     std::replace(result.begin(), result.end(), '+', ' ');
 555   return result;
 556 }
 557
 558 bool TemplateURLRef::HasGoogleBaseURLs(
 559     const SearchTermsData& search_terms_data) const {
 560   ParseIfNecessary(search_terms_data);
 561   return base::ranges::any_of(
 562       replacements_, [](const Replacement& replacement) {
 563         return replacement.type == GOOGLE_BASE_URL ||
 564                replacement.type == GOOGLE_BASE_SUGGEST_URL;
 565       });
 566 }
 567
 568 bool TemplateURLRef::ExtractSearchTermsFromURL(
 569     const GURL& url,
 570     std::u16string* search_terms,
 571     const SearchTermsData& search_terms_data,
 572     url::Parsed::ComponentType* search_terms_component,
 573     url::Component* search_terms_position) const {
 574   DCHECK(search_terms);
 575   search_terms->clear();
 576
 577   ParseIfNecessary(search_terms_data);
 578
 579   // We need a search term in the template URL to extract something.
 580   if (search_term_key_.empty() &&
 581       (search_term_key_location_ != url::Parsed::PATH))
 582     return false;
 583
 584   // Host, port, and path must match.
 585   if ((url.host() != host_) || (url.port() != port_) ||
 586       (!PathIsEqual(url) && (search_term_key_location_ != url::Parsed::PATH))) {
 587     return false;
 588   }
 589
 590   base::StringPiece source;
 591   url::Component position;
 592
 593   if (search_term_key_location_ == url::Parsed::PATH) {
 594     source = url.path_piece();
 595
 596     // If the path does not contain the expected prefix and suffix, then this is
 597     // not a match.
 598     if (source.size() < (search_term_value_prefix_.size() +
 599                          search_term_value_suffix_.size()) ||
 600         !base::StartsWith(source, search_term_value_prefix_) ||
 601         !base::EndsWith(source, search_term_value_suffix_))
 602       return false;
 603     position =
 604         url::MakeRange(search_term_value_prefix_.size(),
 605                        source.length() - search_term_value_suffix_.size());
 606   } else {
 607     DCHECK(search_term_key_location_ == url::Parsed::QUERY ||
 608            search_term_key_location_ == url::Parsed::REF);
 609     source = (search_term_key_location_ == url::Parsed::QUERY)
 610                  ? url.query_piece()
 611                  : url.ref_piece();
 612
 613     url::Component query, key, value;
 614     query.len = static_cast<int>(source.size());
 615     bool key_found = false;
 616     while (url::ExtractQueryKeyValue(source.data(), &query, &key, &value)) {
 617       if (key.is_nonempty()) {
 618         if (source.substr(key.begin, key.len) == search_term_key_) {
 619           // Fail if search term key is found twice.
 620           if (key_found)
 621             return false;
 622
 623           // If the query parameter does not contain the expected prefix and
 624           // suffix, then this is not a match.
 625           base::StringPiece search_term =
 626               base::StringPiece(source).substr(value.begin, value.len);
 627           if (search_term.size() < (search_term_value_prefix_.size() +
 628                                     search_term_value_suffix_.size()) ||
 629               !base::StartsWith(search_term, search_term_value_prefix_) ||
 630               !base::EndsWith(search_term, search_term_value_suffix_))
 631             continue;
 632
 633           key_found = true;
 634           position =
 635               url::MakeRange(value.begin + search_term_value_prefix_.size(),
 636                              value.end() - search_term_value_suffix_.size());
 637         }
 638       }
 639     }
 640     if (!key_found)
 641       return false;
 642   }
 643
 644   // Extract the search term.
 645   *search_terms =
 646       SearchTermToString16(source.substr(position.begin, position.len));
 647   if (search_terms_component)
 648     *search_terms_component = search_term_key_location_;
 649   if (search_terms_position)
 650     *search_terms_position = position;
 651   return true;
 652 }
 653
 654 void TemplateURLRef::InvalidateCachedValues() const {
 655   supports_replacements_ = valid_ = parsed_ = path_wildcard_present_ = false;
 656   host_.clear();
 657   port_.clear();
 658   path_prefix_.clear();
 659   path_suffix_.clear();
 660   search_term_key_.clear();
 661   search_term_key_location_ = url::Parsed::QUERY;
 662   search_term_value_prefix_.clear();
 663   search_term_value_suffix_.clear();
 664   replacements_.clear();
 665   post_params_.clear();
 666 }
 667
 668 bool TemplateURLRef::ParseParameter(size_t start,
 669                                     size_t end,
 670                                     std::string* url,
 671                                     Replacements* replacements) const {
 672   DCHECK(start != std::string::npos &&
 673          end != std::string::npos && end > start);
 674   size_t length = end - start - 1;
 675   bool optional = false;
 676   // Make a copy of |url| that can be referenced in StringPieces below. |url| is
 677   // modified, so that can't be used in StringPiece.
 678   const std::string original_url(*url);
 679   if (original_url[end - 1] == kOptional) {
 680     optional = true;
 681     length--;
 682   }
 683
 684   const auto parameter =
 685       base::MakeStringPiece(original_url.begin() + start + 1,
 686                             original_url.begin() + start + 1 + length);
 687   const auto full_parameter = base::MakeStringPiece(
 688       original_url.begin() + start, original_url.begin() + end + 1);
 689   // Remove the parameter from the string.  For parameters who replacement is
 690   // constant and already known, just replace them directly.  For other cases,
 691   // like parameters whose values may change over time, use |replacements|.
 692   url->erase(start, end - start + 1);
 693   if (parameter == kSearchTermsParameter) {
 694     replacements->push_back(Replacement(SEARCH_TERMS, start));
 695   } else if (parameter == "count") {
 696     if (!optional)
 697       url->insert(start, kDefaultCount);
 698   } else if (parameter == "google:assistedQueryStats") {
 699     replacements->push_back(Replacement(GOOGLE_ASSISTED_QUERY_STATS, start));
 700   } else if (parameter == "google:baseURL") {
 701     replacements->push_back(Replacement(GOOGLE_BASE_URL, start));
 702   } else if (parameter == "google:baseSearchByImageURL") {
 703     replacements->push_back(
 704         Replacement(GOOGLE_BASE_SEARCH_BY_IMAGE_URL, start));
 705   } else if (parameter == "google:baseSuggestURL") {
 706     replacements->push_back(Replacement(GOOGLE_BASE_SUGGEST_URL, start));
 707   } else if (parameter == "google:currentPageUrl") {
 708     replacements->push_back(Replacement(GOOGLE_CURRENT_PAGE_URL, start));
 709   } else if (parameter == "google:cursorPosition") {
 710     replacements->push_back(Replacement(GOOGLE_CURSOR_POSITION, start));
 711   } else if (parameter == "google:imageOriginalHeight") {
 712     replacements->push_back(
 713         Replacement(TemplateURLRef::GOOGLE_IMAGE_ORIGINAL_HEIGHT, start));
 714   } else if (parameter == "google:imageOriginalWidth") {
 715     replacements->push_back(
 716         Replacement(TemplateURLRef::GOOGLE_IMAGE_ORIGINAL_WIDTH, start));
 717   } else if (parameter == "google:imageSearchSource") {
 718     replacements->push_back(
 719         Replacement(TemplateURLRef::GOOGLE_IMAGE_SEARCH_SOURCE, start));
 720   } else if (parameter == "google:imageThumbnail") {
 721     replacements->push_back(
 722         Replacement(TemplateURLRef::GOOGLE_IMAGE_THUMBNAIL, start));
 723   } else if (parameter == "google:imageThumbnailBase64") {
 724     replacements->push_back(
 725         Replacement(TemplateURLRef::GOOGLE_IMAGE_THUMBNAIL_BASE64, start));
 726   } else if (parameter == "google:processedImageDimensions") {
 727     replacements->emplace_back(
 728         Replacement(TemplateURLRef::GOOGLE_PROCESSED_IMAGE_DIMENSIONS, start));
 729   } else if (parameter == "google:imageURL") {
 730     replacements->push_back(Replacement(TemplateURLRef::GOOGLE_IMAGE_URL,
 731                                         start));
 732   } else if (parameter == "google:inputType") {
 733     replacements->push_back(Replacement(TemplateURLRef::GOOGLE_INPUT_TYPE,
 734                                         start));
 735   } else if (parameter == "google:omniboxFocusType") {
 736     replacements->push_back(
 737         Replacement(TemplateURLRef::GOOGLE_OMNIBOX_FOCUS_TYPE, start));
 738   } else if (parameter == "google:iOSSearchLanguage") {
 739     replacements->push_back(Replacement(GOOGLE_IOS_SEARCH_LANGUAGE, start));
 740   } else if (parameter == "google:contextualSearchVersion") {
 741     replacements->push_back(
 742         Replacement(GOOGLE_CONTEXTUAL_SEARCH_VERSION, start));
 743   } else if (parameter == "google:contextualSearchContextData") {
 744     replacements->push_back(
 745         Replacement(GOOGLE_CONTEXTUAL_SEARCH_CONTEXT_DATA, start));
 746   } else if (parameter == "google:originalQueryForSuggestion") {
 747     replacements->push_back(Replacement(GOOGLE_ORIGINAL_QUERY_FOR_SUGGESTION,
 748                                         start));
 749   } else if (parameter == "google:pageClassification") {
 750     replacements->push_back(Replacement(GOOGLE_PAGE_CLASSIFICATION, start));
 751   } else if (parameter == "google:clientCacheTimeToLive") {
 752     replacements->push_back(
 753         Replacement(GOOGLE_CLIENT_CACHE_TIME_TO_LIVE, start));
 754   } else if (parameter == "google:pathWildcard") {
 755     // Do nothing, we just want the path wildcard removed from the URL.
 756   } else if (parameter == "google:prefetchQuery") {
 757     replacements->push_back(Replacement(GOOGLE_PREFETCH_QUERY, start));
 758   } else if (parameter == "google:prefetchSource") {
 759     replacements->push_back(Replacement(GOOGLE_PREFETCH_SOURCE, start));
 760   } else if (parameter == "google:RLZ") {
 761     replacements->push_back(Replacement(GOOGLE_RLZ, start));
 762   } else if (parameter == "google:searchClient") {
 763     replacements->push_back(Replacement(GOOGLE_SEARCH_CLIENT, start));
 764   } else if (parameter == "google:searchFieldtrialParameter") {
 765     replacements->push_back(Replacement(GOOGLE_SEARCH_FIELDTRIAL_GROUP, start));
 766   } else if (parameter == "google:searchVersion") {
 767     replacements->push_back(Replacement(GOOGLE_SEARCH_VERSION, start));
 768   } else if (parameter == "google:sessionToken") {
 769     replacements->push_back(Replacement(GOOGLE_SESSION_TOKEN, start));
 770   } else if (parameter == "google:sourceId") {
 771 #if BUILDFLAG(IS_ANDROID) || BUILDFLAG(IS_IOS)
 772     url->insert(start, "sourceid=chrome-mobile&");
 773 #else
 774     url->insert(start, "sourceid=chrome&");
 775 #endif
 776   } else if (parameter == "google:suggestAPIKeyParameter") {
 777     url->insert(start,
 778                 base::EscapeQueryParamValue(google_apis::GetAPIKey(), false));
 779   } else if (parameter == "google:suggestClient") {
 780     replacements->push_back(Replacement(GOOGLE_SUGGEST_CLIENT, start));
 781   } else if (parameter == "google:suggestRid") {
 782     replacements->push_back(Replacement(GOOGLE_SUGGEST_REQUEST_ID, start));
 783   } else if (parameter == kGoogleUnescapedSearchTermsParameter) {
 784     replacements->push_back(Replacement(GOOGLE_UNESCAPED_SEARCH_TERMS, start));
 785   } else if (parameter == "yandex:referralID") {
 786     replacements->push_back(Replacement(YANDEX_REFERRAL_ID, start));
 787   } else if (parameter == "mailru:referralID") {
 788     replacements->push_back(Replacement(MAIL_RU_REFERRAL_ID, start));
 789   } else if (parameter == "yandex:searchPath") {
 790     url->insert(start, YandexSearchPathFromDeviceFormFactor());
 791   } else if (parameter == "imageTranslateSourceLocale") {
 792     replacements->push_back(Replacement(IMAGE_TRANSLATE_SOURCE_LOCALE, start));
 793   } else if (parameter == "imageTranslateTargetLocale") {
 794     replacements->push_back(Replacement(IMAGE_TRANSLATE_TARGET_LOCALE, start));
 795   } else if (parameter == "inputEncoding") {
 796     replacements->push_back(Replacement(ENCODING, start));
 797   } else if (parameter == "language") {
 798     replacements->push_back(Replacement(LANGUAGE, start));
 799   } else if (parameter == "outputEncoding") {
 800     if (!optional)
 801       url->insert(start, kOutputEncodingType);
 802   } else if ((parameter == "startIndex") || (parameter == "startPage")) {
 803     // We don't support these.
 804     if (!optional)
 805       url->insert(start, "1");
 806   } else if (!prepopulated_) {
 807     // If it's a prepopulated URL, we know that it's safe to remove unknown
 808     // parameters, so just ignore this and return true below. Otherwise it could
 809     // be some garbage but can also be a javascript block. Put it back.
 810     url->insert(start, full_parameter.data(), full_parameter.size());
 811     return false;
 812   }
 813   return true;
 814 }
 815
 816 std::string TemplateURLRef::ParseURL(const std::string& url,
 817                                      Replacements* replacements,
 818                                      PostParams* post_params,
 819                                      bool* valid) const {
 820   *valid = false;
 821   std::string parsed_url = url;
 822   for (size_t last = 0; last != std::string::npos; ) {
 823     last = parsed_url.find(kStartParameter, last);
 824     if (last != std::string::npos) {
 825       size_t template_end = parsed_url.find(kEndParameter, last);
 826       if (template_end != std::string::npos) {
 827         // Since we allow Javascript in the URL, {} pairs could be nested. Match
 828         // only leaf pairs with supported parameters.
 829         size_t next_template_start = parsed_url.find(kStartParameter, last + 1);
 830         if (next_template_start == std::string::npos ||
 831             next_template_start > template_end) {
 832           // If successful, ParseParameter erases from the string as such no
 833           // need to update |last|. If failed, move |last| to the end of pair.
 834           if (!ParseParameter(last, template_end, &parsed_url, replacements)) {
 835             // |template_end| + 1 may be beyond the end of the string.
 836             last = template_end;
 837           }
 838         } else {
 839           last = next_template_start;
 840         }
 841       } else {
 842         // Open brace without a closing brace, return.
 843         return std::string();
 844       }
 845     }
 846   }
 847
 848   // Handles the post parameters.
 849   const std::string& post_params_string = GetPostParamsString();
 850   if (!post_params_string.empty()) {
 851     for (const base::StringPiece& cur : base::SplitStringPiece(
 852              post_params_string, ",",
 853              base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL)) {
 854       // The '=' delimiter is required and the name must be not empty.
 855       std::vector<std::string> parts = base::SplitString(
 856           cur, "=", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
 857       if ((parts.size() != 2U) || parts[0].empty())
 858         return std::string();
 859
 860       std::string& value = parts[1];
 861       size_t replacements_size = replacements->size();
 862       if (IsTemplateParameterString(value))
 863         ParseParameter(0, value.length() - 1, &value, replacements);
 864       PostParam param = { parts[0], value };
 865       post_params->push_back(param);
 866       // If there was a replacement added, points its index to last added
 867       // PostParam.
 868       if (replacements->size() > replacements_size) {
 869         DCHECK_EQ(replacements_size + 1, replacements->size());
 870         Replacement* r = &replacements->back();
 871         r->is_post_param = true;
 872         r->index = post_params->size() - 1;
 873       }
 874     }
 875     DCHECK(!post_params->empty());
 876   }
 877
 878   *valid = true;
 879   return parsed_url;
 880 }
 881
 882 void TemplateURLRef::ParseIfNecessary(
 883     const SearchTermsData& search_terms_data) const {
 884   if (!parsed_) {
 885     InvalidateCachedValues();
 886     parsed_ = true;
 887     parsed_url_ = ParseURL(GetURL(), &replacements_, &post_params_, &valid_);
 888     supports_replacements_ = false;
 889     if (valid_) {
 890       bool has_only_one_search_term = false;
 891       for (Replacements::const_iterator i = replacements_.begin();
 892            i != replacements_.end(); ++i) {
 893         if ((i->type == SEARCH_TERMS) ||
 894             (i->type == GOOGLE_UNESCAPED_SEARCH_TERMS)) {
 895           if (has_only_one_search_term) {
 896             has_only_one_search_term = false;
 897             break;
 898           }
 899           has_only_one_search_term = true;
 900           supports_replacements_ = true;
 901         }
 902       }
 903       // Only parse the host/key if there is one search term. Technically there
 904       // could be more than one term, but it's uncommon; so we punt.
 905       if (has_only_one_search_term)
 906         ParseHostAndSearchTermKey(search_terms_data);
 907     }
 908   }
 909 }
 910
 911 void TemplateURLRef::ParsePath(const std::string& path) const {
 912   // Wildcard string used when matching URLs.
 913   const std::string wildcard_escaped = "%7Bgoogle:pathWildcard%7D";
 914
 915   // We only search for the escaped wildcard because we're only replacing it in
 916   // the path, and GURL's constructor escapes { and }.
 917   size_t wildcard_start = path.find(wildcard_escaped);
 918   path_wildcard_present_ = wildcard_start != std::string::npos;
 919   path_prefix_ = path.substr(0, wildcard_start);
 920   path_suffix_ = path_wildcard_present_
 921                      ? path.substr(wildcard_start + wildcard_escaped.length())
 922                      : std::string();
 923 }
 924
 925 bool TemplateURLRef::PathIsEqual(const GURL& url) const {
 926   base::StringPiece path = url.path_piece();
 927   if (!path_wildcard_present_)
 928     return path == path_prefix_;
 929   return ((path.length() >= path_prefix_.length() + path_suffix_.length()) &&
 930           base::StartsWith(path, path_prefix_) &&
 931           base::EndsWith(path, path_suffix_));
 932 }
 933
 934 void TemplateURLRef::ParseHostAndSearchTermKey(
 935     const SearchTermsData& search_terms_data) const {
 936   std::string url_string(GetURL());
 937   base::ReplaceSubstringsAfterOffset(
 938       &url_string, 0, "{google:baseURL}",
 939       search_terms_data.GoogleBaseURLValue());
 940   base::ReplaceSubstringsAfterOffset(
 941       &url_string, 0, "{google:baseSuggestURL}",
 942       search_terms_data.GoogleBaseSuggestURLValue());
 943   base::ReplaceSubstringsAfterOffset(&url_string, 0, "{yandex:searchPath}",
 944                                      YandexSearchPathFromDeviceFormFactor());
 945
 946   GURL url(url_string);
 947   if (!url.is_valid())
 948     return;
 949
 950   SearchTermLocation query_result(url.query_piece(), url::Parsed::QUERY);
 951   SearchTermLocation ref_result(url.ref_piece(), url::Parsed::REF);
 952   SearchTermLocation path_result(url.path_piece(), url::Parsed::PATH);
 953   const bool in_query = query_result.found();
 954   const bool in_ref = ref_result.found();
 955   const bool in_path = path_result.found();
 956   if (in_query ? (in_ref || in_path) : (in_ref == in_path))
 957     return;  // No key or multiple keys found.  We only handle having one key.
 958
 959   host_ = url.host();
 960   port_ = url.port();
 961   if (in_query) {
 962     search_term_key_location_ = url::Parsed::QUERY;
 963     search_term_key_ = query_result.key();
 964     search_term_value_prefix_ = query_result.value_prefix();
 965     search_term_value_suffix_ = query_result.value_suffix();
 966     ParsePath(url.path());
 967   } else if (in_ref) {
 968     search_term_key_location_ = url::Parsed::REF;
 969     search_term_key_ = ref_result.key();
 970     search_term_value_prefix_ = ref_result.value_prefix();
 971     search_term_value_suffix_ = ref_result.value_suffix();
 972     ParsePath(url.path());
 973   } else {
 974     DCHECK(in_path);
 975     search_term_key_location_ = url::Parsed::PATH;
 976     search_term_value_prefix_ = path_result.value_prefix();
 977     search_term_value_suffix_ = path_result.value_suffix();
 978   }
 979 }
 980
 981 void TemplateURLRef::HandleReplacement(const std::string& name,
 982                                        const std::string& value,
 983                                        const Replacement& replacement,
 984                                        std::string* url) const {
 985   size_t pos = replacement.index;
 986   if (replacement.is_post_param) {
 987     DCHECK_LT(pos, post_params_.size());
 988     DCHECK(!post_params_[pos].name.empty());
 989     post_params_[pos].value = value;
 990   } else {
 991     url->insert(pos, name.empty() ? value : (name + "=" + value + "&"));
 992   }
 993 }
 994
 995 std::string TemplateURLRef::HandleReplacements(
 996     const SearchTermsArgs& search_terms_args,
 997     const SearchTermsData& search_terms_data,
 998     PostContent* post_content) const {
 999   if (replacements_.empty()) {
1000     if (!post_params_.empty())
1001       EncodeFormData(post_params_, post_content);
1002     return parsed_url_;
1003   }
1004
1005   // Determine if the search terms are in the query or before. We're escaping
1006   // space as '+' in the former case and as '%20' in the latter case.
1007   bool is_in_query = true;
1008
1009   auto search_terms =
1010       base::ranges::find(replacements_, SEARCH_TERMS, &Replacement::type);
1011
1012   if (search_terms != replacements_.end()) {
1013     std::u16string::size_type query_start = parsed_url_.find('?');
1014     is_in_query = query_start != std::u16string::npos &&
1015                   (static_cast<std::u16string::size_type>(search_terms->index) >
1016                    query_start);
1017   }
1018
1019   std::string input_encoding;
1020   std::u16string encoded_terms;
1021   std::u16string encoded_original_query;
1022   owner_->EncodeSearchTerms(search_terms_args, is_in_query, &input_encoding,
1023                             &encoded_terms, &encoded_original_query);
1024
1025   std::string url = parsed_url_;
1026
1027   // replacements_ is ordered in ascending order, as such we need to iterate
1028   // from the back.
1029   for (const Replacement& replacement : base::Reversed(replacements_)) {
1030     switch (replacement.type) {
1031       case ENCODING:
1032         HandleReplacement(std::string(), input_encoding, replacement, &url);
1033         break;
1034
1035       case GOOGLE_CONTEXTUAL_SEARCH_VERSION:
1036         if (search_terms_args.contextual_search_params.version >= 0) {
1037           HandleReplacement(
1038               "ctxs",
1039               base::NumberToString(
1040                   search_terms_args.contextual_search_params.version),
1041               replacement, &url);
1042         }
1043         break;
1044
1045       case GOOGLE_CONTEXTUAL_SEARCH_CONTEXT_DATA: {
1046         DCHECK(!replacement.is_post_param);
1047
1048         const SearchTermsArgs::ContextualSearchParams& params =
1049             search_terms_args.contextual_search_params;
1050         std::vector<std::string> args;
1051
1052         if (params.contextual_cards_version > 0) {
1053           args.push_back("ctxsl_coca=" +
1054                          base::NumberToString(params.contextual_cards_version));
1055         }
1056         if (!params.home_country.empty())
1057           args.push_back("ctxs_hc=" + params.home_country);
1058         if (params.previous_event_id != 0) {
1059           args.push_back("ctxsl_pid=" +
1060                          base::NumberToString(params.previous_event_id));
1061         }
1062         if (params.previous_event_results != 0) {
1063           args.push_back("ctxsl_per=" +
1064                          base::NumberToString(params.previous_event_results));
1065         }
1066         if (params.is_exact_search)
1067           args.push_back("ctxsl_exact=1");
1068         if (!params.source_lang.empty())
1069           args.push_back("tlitesl=" + params.source_lang);
1070         if (!params.target_lang.empty())
1071           args.push_back("tlitetl=" + params.target_lang);
1072         if (!params.fluent_languages.empty())
1073           args.push_back("ctxs_fls=" + params.fluent_languages);
1074         if (!params.related_searches_stamp.empty())
1075           args.push_back("ctxsl_rs=" + params.related_searches_stamp);
1076         if (params.apply_lang_hint)
1077           args.push_back("ctxsl_applylh=1");
1078
1079         HandleReplacement(std::string(), base::JoinString(args, "&"),
1080                           replacement, &url);
1081         break;
1082       }
1083
1084       case GOOGLE_ASSISTED_QUERY_STATS: {
1085         DCHECK(!replacement.is_post_param);
1086         if (!search_terms_args.assisted_query_stats.empty()) {
1087           DCHECK(search_terms_args.searchbox_stats.ByteSizeLong() > 0)
1088               << "searchbox_stats must be set when assisted_query_stats is.";
1089           // Get the base URL without substituting AQS and gs_lcrp to avoid
1090           // infinite recursion and unwanted replacement respectively. We need
1091           // the URL to find out if it meets all AQS requirements (e.g. HTTPS
1092           // protocol check). See TemplateURLRef::SearchTermsArgs for more
1093           // details.
1094           SearchTermsArgs sanitized_search_terms_args(search_terms_args);
1095           sanitized_search_terms_args.assisted_query_stats.clear();
1096           // Clear the proto. Its empty state has a serialized size of zero.
1097           sanitized_search_terms_args.searchbox_stats.Clear();
1098           GURL base_url(ReplaceSearchTerms(sanitized_search_terms_args,
1099                                            search_terms_data, nullptr));
1100           if (base_url.SchemeIsCryptographic() &&
1101               base::FeatureList::IsEnabled(
1102                   omnibox::kReportAssistedQueryStats)) {
1103             HandleReplacement("aqs", search_terms_args.assisted_query_stats,
1104                               replacement, &url);
1105             base::UmaHistogramCounts1000(
1106                 "Omnibox.AssistedQueryStats.Length",
1107                 static_cast<int>(
1108                     search_terms_args.assisted_query_stats.length()));
1109           }
1110         }
1111
1112         if (search_terms_args.searchbox_stats.ByteSizeLong() > 0) {
1113           DCHECK(!search_terms_args.assisted_query_stats.empty())
1114               << "assisted_query_stats must be set when searchbox_stats is.";
1115           // Get the base URL without substituting gs_lcrp and AQS to avoid
1116           // infinite recursion and unwanted replacement respectively. We need
1117           // the URL to find out if it meets all gs_lcrp requirements (e.g.
1118           // HTTPS protocol check). See TemplateURLRef::SearchTermsArgs for more
1119           // details.
1120           SearchTermsArgs sanitized_search_terms_args(search_terms_args);
1121           sanitized_search_terms_args.assisted_query_stats.clear();
1122           // Clear the proto. Its empty state has a serialized size of zero.
1123           sanitized_search_terms_args.searchbox_stats.Clear();
1124           GURL base_url(ReplaceSearchTerms(sanitized_search_terms_args,
1125                                            search_terms_data, nullptr));
1126           if (base_url.SchemeIsCryptographic() &&
1127               base::FeatureList::IsEnabled(omnibox::kReportSearchboxStats)) {
1128             std::string serialized_searchbox_stats;
1129             search_terms_args.searchbox_stats.SerializeToString(
1130                 &serialized_searchbox_stats);
1131             if (!serialized_searchbox_stats.empty()) {
1132               std::string encoded_searchbox_stats;
1133               base::Base64UrlEncode(serialized_searchbox_stats,
1134                                     base::Base64UrlEncodePolicy::OMIT_PADDING,
1135                                     &encoded_searchbox_stats);
1136               HandleReplacement("gs_lcrp", encoded_searchbox_stats, replacement,
1137                                 &url);
1138               base::UmaHistogramCounts1000(
1139                   "Omnibox.SearchboxStats.Length",
1140                   static_cast<int>(encoded_searchbox_stats.length()));
1141             } else {
1142               base::UmaHistogramCounts1000("Omnibox.SearchboxStats.Length", 0);
1143             }
1144           }
1145         }
1146         break;
1147       }
1148
1149       case GOOGLE_BASE_URL:
1150         DCHECK(!replacement.is_post_param);
1151         HandleReplacement(std::string(), search_terms_data.GoogleBaseURLValue(),
1152                           replacement, &url);
1153         break;
1154
1155       case GOOGLE_BASE_SEARCH_BY_IMAGE_URL:
1156         DCHECK(!replacement.is_post_param);
1157         HandleReplacement(std::string(),
1158                           search_terms_data.GoogleBaseSearchByImageURLValue(),
1159                           replacement, &url);
1160         break;
1161
1162       case GOOGLE_BASE_SUGGEST_URL:
1163         DCHECK(!replacement.is_post_param);
1164         HandleReplacement(std::string(),
1165                           search_terms_data.GoogleBaseSuggestURLValue(),
1166                           replacement, &url);
1167         break;
1168
1169       case GOOGLE_CURRENT_PAGE_URL:
1170         DCHECK(!replacement.is_post_param);
1171         if (!search_terms_args.current_page_url.empty()) {
1172           const std::string& escaped_current_page_url =
1173               base::EscapeQueryParamValue(search_terms_args.current_page_url,
1174                                           true);
1175           HandleReplacement("url", escaped_current_page_url, replacement, &url);
1176         }
1177         break;
1178
1179       case GOOGLE_CURSOR_POSITION:
1180         DCHECK(!replacement.is_post_param);
1181         if (search_terms_args.cursor_position != std::u16string::npos)
1182           HandleReplacement(
1183               "cp",
1184               base::StringPrintf("%" PRIuS, search_terms_args.cursor_position),
1185               replacement, &url);
1186         break;
1187
1188       case GOOGLE_INPUT_TYPE:
1189         DCHECK(!replacement.is_post_param);
1190         HandleReplacement("oit",
1191                           base::NumberToString(search_terms_args.input_type),
1192                           replacement, &url);
1193         break;
1194
1195       case GOOGLE_OMNIBOX_FOCUS_TYPE:
1196         DCHECK(!replacement.is_post_param);
1197         if (search_terms_args.focus_type !=
1198             metrics::OmniboxFocusType::INTERACTION_DEFAULT) {
1199           HandleReplacement("oft",
1200                             base::NumberToString(
1201                                 static_cast<int>(search_terms_args.focus_type)),
1202                             replacement, &url);
1203         }
1204         break;
1205
1206       case GOOGLE_ORIGINAL_QUERY_FOR_SUGGESTION:
1207         DCHECK(!replacement.is_post_param);
1208         if (search_terms_args.accepted_suggestion >= 0 ||
1209             !search_terms_args.assisted_query_stats.empty()) {
1210           HandleReplacement("oq", base::UTF16ToUTF8(encoded_original_query),
1211                             replacement, &url);
1212         }
1213         break;
1214
1215       case GOOGLE_PAGE_CLASSIFICATION:
1216         if (search_terms_args.page_classification !=
1217             metrics::OmniboxEventProto::INVALID_SPEC) {
1218           HandleReplacement(
1219               "pgcl",
1220               base::NumberToString(search_terms_args.page_classification),
1221               replacement, &url);
1222         }
1223         break;
1224
1225       case GOOGLE_CLIENT_CACHE_TIME_TO_LIVE:
1226         if (search_terms_args.search_terms.size() == 0 &&
1227             search_terms_args.zero_suggest_cache_duration_sec > 0) {
1228           HandleReplacement(
1229               "ccttl",
1230               base::NumberToString(
1231                   search_terms_args.zero_suggest_cache_duration_sec),
1232               replacement, &url);
1233         }
1234         break;
1235
1236       case GOOGLE_PREFETCH_QUERY: {
1237         const std::string& query = search_terms_args.prefetch_query;
1238         const std::string& type = search_terms_args.prefetch_query_type;
1239         if (!query.empty() && !type.empty()) {
1240           HandleReplacement(std::string(),
1241                             "pfq=" + query + "&qha=" + type + "&", replacement,
1242                             &url);
1243         }
1244         break;
1245       }
1246
1247       case GOOGLE_PREFETCH_SOURCE: {
1248         if (search_terms_args.is_prefetch) {
1249           // Currently, Chrome only support "cs" for prefetches, but if new
1250           // prefetch sources (outside of suggestions) are added, a new prefetch
1251           // source value is needed. These should denote the source of the
1252           // prefetch to allow the search server to treat the requests based on
1253           // source. "cs" represents Chrome Suggestions as the source. Adding a
1254           // new source should be supported by the Search engine.
1255           HandleReplacement("pf", "cs", replacement, &url);
1256         }
1257         break;
1258       }
1259
1260       case GOOGLE_RLZ: {
1261         DCHECK(!replacement.is_post_param);
1262         // On platforms that don't have RLZ, we still want this branch
1263         // to happen so that we replace the RLZ template with the
1264         // empty string.  (If we don't handle this case, we hit a
1265         // NOTREACHED below.)
1266         std::u16string rlz_string = search_terms_data.GetRlzParameterValue(
1267             search_terms_args.request_source == RequestSource::CROS_APP_LIST);
1268         if (!rlz_string.empty()) {
1269           HandleReplacement("rlz", base::UTF16ToUTF8(rlz_string), replacement,
1270                             &url);
1271         }
1272         break;
1273       }
1274
1275       case GOOGLE_SEARCH_CLIENT: {
1276         DCHECK(!replacement.is_post_param);
1277         std::string client = search_terms_data.GetSearchClient();
1278         if (!client.empty())
1279           HandleReplacement("client", client, replacement, &url);
1280         break;
1281       }
1282
1283       case GOOGLE_SEARCH_FIELDTRIAL_GROUP:
1284         // We are not currently running any fieldtrials that modulate the search
1285         // url.  If we do, then we'd have some conditional insert such as:
1286         // url.insert(replacement.index, used_www ? "gcx=w&" : "gcx=c&");
1287         break;
1288
1289       case GOOGLE_SEARCH_VERSION:
1290         HandleReplacement("gs_rn", "42", replacement, &url);
1291         break;
1292
1293       case GOOGLE_SESSION_TOKEN: {
1294         std::string token = search_terms_args.session_token;
1295         if (!token.empty())
1296           HandleReplacement("psi", token, replacement, &url);
1297         break;
1298       }
1299
1300       case GOOGLE_SUGGEST_CLIENT:
1301         HandleReplacement(std::string(),
1302                           search_terms_data.GetSuggestClient(
1303                               search_terms_args.request_source),
1304                           replacement, &url);
1305         break;
1306
1307       case GOOGLE_SUGGEST_REQUEST_ID:
1308         HandleReplacement(std::string(),
1309                           search_terms_data.GetSuggestRequestIdentifier(
1310                               search_terms_args.request_source),
1311                           replacement, &url);
1312         break;
1313
1314       case GOOGLE_UNESCAPED_SEARCH_TERMS: {
1315         std::string unescaped_terms;
1316         base::UTF16ToCodepage(search_terms_args.search_terms,
1317                               input_encoding.c_str(),
1318                               base::OnStringConversionError::SKIP,
1319                               &unescaped_terms);
1320         HandleReplacement(std::string(), unescaped_terms, replacement, &url);
1321         break;
1322       }
1323
1324       case LANGUAGE:
1325         HandleReplacement(std::string(),
1326                           search_terms_data.GetApplicationLocale(), replacement,
1327                           &url);
1328         break;
1329
1330       case SEARCH_TERMS:
1331         HandleReplacement(std::string(), base::UTF16ToUTF8(encoded_terms),
1332                           replacement, &url);
1333         break;
1334
1335       case GOOGLE_IMAGE_THUMBNAIL:
1336         HandleReplacement(std::string(),
1337                           search_terms_args.image_thumbnail_content,
1338                           replacement, &url);
1339         if (replacement.is_post_param) {
1340           if (!search_terms_args.image_thumbnail_content_type.empty()) {
1341             post_params_[replacement.index].content_type =
1342                 search_terms_args.image_thumbnail_content_type;
1343           } else {
1344             post_params_[replacement.index].content_type = "image/jpeg";
1345           }
1346         }
1347         break;
1348
1349       case GOOGLE_IMAGE_THUMBNAIL_BASE64: {
1350         std::string base64_thumbnail_content;
1351         base::Base64Encode(search_terms_args.image_thumbnail_content,
1352                            &base64_thumbnail_content);
1353         HandleReplacement(std::string(), base64_thumbnail_content, replacement,
1354                           &url);
1355         if (replacement.is_post_param) {
1356           if (!search_terms_args.image_thumbnail_content_type.empty()) {
1357             post_params_[replacement.index].content_type =
1358                 search_terms_args.image_thumbnail_content_type;
1359           } else {
1360             post_params_[replacement.index].content_type = "image/jpeg";
1361           }
1362         }
1363         break;
1364       }
1365
1366       case GOOGLE_PROCESSED_IMAGE_DIMENSIONS: {
1367         std::string dimensions = search_terms_args.processed_image_dimensions;
1368         if (!dimensions.empty()) {
1369           HandleReplacement(std::string(), dimensions, replacement, &url);
1370         }
1371         break;
1372       }
1373
1374       case GOOGLE_IMAGE_URL:
1375         if (search_terms_args.image_url.is_valid()) {
1376           HandleReplacement(std::string(), search_terms_args.image_url.spec(),
1377                             replacement, &url);
1378         }
1379         break;
1380
1381       case GOOGLE_IMAGE_ORIGINAL_WIDTH:
1382         if (!search_terms_args.image_original_size.IsEmpty()) {
1383           HandleReplacement(std::string(),
1384                             base::NumberToString(
1385                                 search_terms_args.image_original_size.width()),
1386                             replacement, &url);
1387         }
1388         break;
1389
1390       case GOOGLE_IMAGE_ORIGINAL_HEIGHT:
1391         if (!search_terms_args.image_original_size.IsEmpty()) {
1392           HandleReplacement(std::string(),
1393                             base::NumberToString(
1394                                 search_terms_args.image_original_size.height()),
1395                             replacement, &url);
1396         }
1397         break;
1398
1399       case GOOGLE_IMAGE_SEARCH_SOURCE:
1400         HandleReplacement(std::string(),
1401                           search_terms_data.GoogleImageSearchSource(),
1402                           replacement, &url);
1403         break;
1404
1405       case GOOGLE_IOS_SEARCH_LANGUAGE:
1406 #if BUILDFLAG(IS_IOS)
1407         HandleReplacement("hl", search_terms_data.GetApplicationLocale(),
1408                           replacement, &url);
1409 #endif
1410         break;
1411
1412       case YANDEX_REFERRAL_ID: {
1413         std::string referral_id = search_terms_data.GetYandexReferralID();
1414         if (!referral_id.empty())
1415           HandleReplacement("clid", referral_id, replacement, &url);
1416         break;
1417       }
1418
1419       case MAIL_RU_REFERRAL_ID: {
1420         std::string referral_id = search_terms_data.GetMailRUReferralID();
1421         if (!referral_id.empty())
1422           HandleReplacement("gp", referral_id, replacement, &url);
1423         break;
1424       }
1425
1426       case IMAGE_TRANSLATE_SOURCE_LOCALE: {
1427         if (!search_terms_args.image_translate_source_locale.empty()) {
1428           HandleReplacement(owner_->image_translate_source_language_param_key(),
1429                             search_terms_args.image_translate_source_locale,
1430                             replacement, &url);
1431         }
1432         break;
1433       }
1434
1435       case IMAGE_TRANSLATE_TARGET_LOCALE: {
1436         if (!search_terms_args.image_translate_target_locale.empty()) {
1437           HandleReplacement(owner_->image_translate_target_language_param_key(),
1438                             search_terms_args.image_translate_target_locale,
1439                             replacement, &url);
1440         }
1441         break;
1442       }
1443
1444       default:
1445         NOTREACHED();
1446         break;
1447     }
1448   }
1449
1450   if (!post_params_.empty())
1451     EncodeFormData(post_params_, post_content);
1452   return url;
1453 }
1454
1455
1456 // TemplateURL ----------------------------------------------------------------
1457
1458 TemplateURL::AssociatedExtensionInfo::AssociatedExtensionInfo(
1459     const std::string& extension_id,
1460     base::Time install_time,
1461     bool wants_to_be_default_engine)
1462     : extension_id(extension_id),
1463       install_time(install_time),
1464       wants_to_be_default_engine(wants_to_be_default_engine) {}
1465
1466 TemplateURL::AssociatedExtensionInfo::~AssociatedExtensionInfo() {
1467 }
1468
1469 size_t TemplateURL::AssociatedExtensionInfo::EstimateMemoryUsage() const {
1470   return base::trace_event::EstimateMemoryUsage(extension_id);
1471 }
1472
1473 TemplateURL::TemplateURL(const TemplateURLData& data, Type type)
1474     : data_(data),
1475       suggestions_url_ref_(this, TemplateURLRef::SUGGEST),
1476       image_url_ref_(this, TemplateURLRef::IMAGE),
1477       image_translate_url_ref_(this, TemplateURLRef::IMAGE_TRANSLATE),
1478       new_tab_url_ref_(this, TemplateURLRef::NEW_TAB),
1479       contextual_search_url_ref_(this, TemplateURLRef::CONTEXTUAL_SEARCH),
1480       type_(type),
1481       engine_type_(SEARCH_ENGINE_UNKNOWN) {
1482   ResizeURLRefVector();
1483   SetPrepopulateId(data_.prepopulate_id);
1484 }
1485
1486 TemplateURL::TemplateURL(const TemplateURLData& data,
1487                          Type type,
1488                          std::string extension_id,
1489                          base::Time install_time,
1490                          bool wants_to_be_default_engine)
1491     : TemplateURL(data, type) {
1492   DCHECK(type == NORMAL_CONTROLLED_BY_EXTENSION ||
1493          type == OMNIBOX_API_EXTENSION);
1494   // Omnibox keywords may not be set as default.
1495   DCHECK(!wants_to_be_default_engine || type != OMNIBOX_API_EXTENSION) << type;
1496   DCHECK_EQ(kInvalidTemplateURLID, data.id);
1497   extension_info_ = std::make_unique<AssociatedExtensionInfo>(
1498       extension_id, install_time, wants_to_be_default_engine);
1499 }
1500
1501 TemplateURL::~TemplateURL() {
1502 }
1503
1504 bool TemplateURL::IsBetterThanEngineWithConflictingKeyword(
1505     const TemplateURL* other) const {
1506   DCHECK(other);
1507
1508   auto get_sort_key = [](const TemplateURL* engine) {
1509     return std::make_tuple(
1510         // Policy-created engines always win over non-policy created engines.
1511         engine->created_by_policy(),
1512         // Policy-enforced engines always win over policy-recommended engines.
1513         engine->enforced_by_policy(),
1514         // The integral value of the type enum is used to sort next.
1515         // This makes extension-controlled engines win.
1516         engine->type(),
1517         // For engines with associated extensions; more recently installed
1518         // extensions win.
1519         engine->extension_info_ ? engine->extension_info_->install_time
1520                                 : base::Time(),
1521         // Prefer engines that CANNOT be auto-replaced.
1522         !engine->safe_for_autoreplace(),
1523         // Prefer engines created by Play API.
1524         engine->created_from_play_api(),
1525         // Favor prepopulated engines over other auto-generated engines.
1526         engine->prepopulate_id() > 0,
1527         // Favor starter pack engines over other auto-generated engines.
1528         engine->starter_pack_id() > 0,
1529         // Favor engines derived from OpenSearch descriptions over
1530         // autogenerated engines heuristically generated from searchable forms.
1531         engine->originating_url().is_valid(),
1532         // More recently modified engines or created engines win.
1533         engine->last_modified(), engine->date_created(),
1534         // TODO(tommycli): This should be a tie-breaker than provides a total
1535         // ordering of all TemplateURLs so that distributed clients resolve
1536         // conflicts identically. This sync_guid is not globally unique today,
1537         // so we need to fix that before we can resolve conflicts with this.
1538         engine->sync_guid());
1539   };
1540
1541   // Although normally sort is done by operator<, in this case, we want the
1542   // BETTER engine to be preceding the worse engine.
1543   return get_sort_key(this) > get_sort_key(other);
1544 }
1545
1546 // static
1547 std::u16string TemplateURL::GenerateKeyword(const GURL& url) {
1548   DCHECK(url.is_valid());
1549   // Strip "www." off the front of the keyword; otherwise the keyword won't work
1550   // properly.  See http://code.google.com/p/chromium/issues/detail?id=6984 .
1551   // |url|'s hostname may be IDN-encoded. Before generating |keyword| from it,
1552   // convert to Unicode, so it won't look like a confusing punycode string.
1553   std::u16string keyword =
1554       url_formatter::IDNToUnicode(url_formatter::StripWWW(url.host()));
1555   return base::i18n::ToLower(keyword);
1556 }
1557
1558 // static
1559 GURL TemplateURL::GenerateFaviconURL(const GURL& url) {
1560   DCHECK(url.is_valid());
1561   GURL::Replacements rep;
1562
1563   static const char kFaviconPath[] = "/favicon.ico";
1564
1565   rep.SetPathStr(kFaviconPath);
1566   rep.ClearUsername();
1567   rep.ClearPassword();
1568   rep.ClearQuery();
1569   rep.ClearRef();
1570   return url.ReplaceComponents(rep);
1571 }
1572
1573 // static
1574 bool TemplateURL::MatchesData(const TemplateURL* t_url,
1575                               const TemplateURLData* data,
1576                               const SearchTermsData& search_terms_data) {
1577   if (!t_url || !data)
1578     return !t_url && !data;
1579
1580   return (t_url->short_name() == data->short_name()) &&
1581          t_url->HasSameKeywordAs(*data, search_terms_data) &&
1582          (t_url->url() == data->url()) &&
1583          (t_url->suggestions_url() == data->suggestions_url) &&
1584          (t_url->image_url() == data->image_url) &&
1585          (t_url->image_translate_url() == data->image_translate_url) &&
1586          (t_url->new_tab_url() == data->new_tab_url) &&
1587          (t_url->search_url_post_params() == data->search_url_post_params) &&
1588          (t_url->suggestions_url_post_params() ==
1589           data->suggestions_url_post_params) &&
1590          (t_url->image_url_post_params() == data->image_url_post_params) &&
1591          (t_url->safe_for_autoreplace() == data->safe_for_autoreplace) &&
1592          (t_url->input_encodings() == data->input_encodings) &&
1593          (t_url->alternate_urls() == data->alternate_urls);
1594 }
1595
1596 std::u16string TemplateURL::AdjustedShortNameForLocaleDirection() const {
1597   std::u16string bidi_safe_short_name = data_.short_name();
1598   base::i18n::AdjustStringForLocaleDirection(&bidi_safe_short_name);
1599   return bidi_safe_short_name;
1600 }
1601
1602 bool TemplateURL::SupportsReplacement(
1603     const SearchTermsData& search_terms_data) const {
1604   return url_ref().SupportsReplacement(search_terms_data);
1605 }
1606
1607 bool TemplateURL::HasGoogleBaseURLs(
1608     const SearchTermsData& search_terms_data) const {
1609   if (base::ranges::any_of(url_refs_, [&](const TemplateURLRef& ref) {
1610         return ref.HasGoogleBaseURLs(search_terms_data);
1611       }))
1612     return true;
1613
1614   return suggestions_url_ref_.HasGoogleBaseURLs(search_terms_data) ||
1615          image_url_ref_.HasGoogleBaseURLs(search_terms_data) ||
1616          image_translate_url_ref_.HasGoogleBaseURLs(search_terms_data) ||
1617          new_tab_url_ref_.HasGoogleBaseURLs(search_terms_data) ||
1618          contextual_search_url_ref_.HasGoogleBaseURLs(search_terms_data);
1619 }
1620
1621 bool TemplateURL::IsGoogleSearchURLWithReplaceableKeyword(
1622     const SearchTermsData& search_terms_data) const {
1623   return (type_ == NORMAL) && url_ref().HasGoogleBaseURLs(search_terms_data) &&
1624          google_util::IsGoogleHostname(base::UTF16ToUTF8(data_.keyword()),
1625                                        google_util::DISALLOW_SUBDOMAIN);
1626 }
1627
1628 bool TemplateURL::HasSameKeywordAs(
1629     const TemplateURLData& other,
1630     const SearchTermsData& search_terms_data) const {
1631   return (data_.keyword() == other.keyword()) ||
1632       (IsGoogleSearchURLWithReplaceableKeyword(search_terms_data) &&
1633        TemplateURL(other).IsGoogleSearchURLWithReplaceableKeyword(
1634            search_terms_data));
1635 }
1636
1637 std::string TemplateURL::GetExtensionId() const {
1638   DCHECK(extension_info_);
1639   return extension_info_->extension_id;
1640 }
1641
1642 SearchEngineType TemplateURL::GetEngineType(
1643     const SearchTermsData& search_terms_data) const {
1644   if (engine_type_ == SEARCH_ENGINE_UNKNOWN) {
1645     const GURL url = GenerateSearchURL(search_terms_data);
1646     engine_type_ = url.is_valid() ? SearchEngineUtils::GetEngineType(url)
1647                                   : SEARCH_ENGINE_OTHER;
1648     DCHECK_NE(SEARCH_ENGINE_UNKNOWN, engine_type_);
1649   }
1650   return engine_type_;
1651 }
1652
1653 BuiltinEngineType TemplateURL::GetBuiltinEngineType() const {
1654   if (data_.prepopulate_id != 0) {
1655     return KEYWORD_MODE_PREPOPULATED_ENGINE;
1656   } else if (data_.starter_pack_id != 0) {
1657     switch (data_.starter_pack_id) {
1658       case TemplateURLStarterPackData::kBookmarks:
1659         return KEYWORD_MODE_STARTER_PACK_BOOKMARKS;
1660       case TemplateURLStarterPackData::kHistory:
1661         return KEYWORD_MODE_STARTER_PACK_HISTORY;
1662       case TemplateURLStarterPackData::kTabs:
1663         return KEYWORD_MODE_STARTER_PACK_TABS;
1664       default:
1665         NOTREACHED();
1666         return KEYWORD_MODE_NON_BUILT_IN;
1667     }
1668   } else {
1669     return KEYWORD_MODE_NON_BUILT_IN;
1670   }
1671 }
1672
1673 bool TemplateURL::ExtractSearchTermsFromURL(
1674     const GURL& url,
1675     const SearchTermsData& search_terms_data,
1676     std::u16string* search_terms) const {
1677   return FindSearchTermsInURL(url, search_terms_data, search_terms, nullptr,
1678                               nullptr);
1679 }
1680
1681 bool TemplateURL::IsSearchURL(const GURL& url,
1682                               const SearchTermsData& search_terms_data) const {
1683   std::u16string search_terms;
1684   return ExtractSearchTermsFromURL(url, search_terms_data, &search_terms) &&
1685       !search_terms.empty();
1686 }
1687
1688 bool TemplateURL::KeepSearchTermsInURL(const GURL& url,
1689                                        const SearchTermsData& search_terms_data,
1690                                        const bool keep_search_intent_params,
1691                                        const bool normalize_search_terms,
1692                                        GURL* out_url,
1693                                        std::u16string* out_search_terms) const {
1694   std::u16string search_terms;
1695   if (!ExtractSearchTermsFromURL(url, search_terms_data, &search_terms) ||
1696       search_terms.empty()) {
1697     return false;
1698   }
1699
1700   if (normalize_search_terms) {
1701     search_terms =
1702         base::i18n::ToLower(base::CollapseWhitespace(search_terms, false));
1703   }
1704
1705   if (!url_ref().SupportsReplacement(search_terms_data)) {
1706     return false;
1707   }
1708
1709   std::vector<std::string> query_params;
1710   if (keep_search_intent_params && !data_.search_intent_params.empty()) {
1711     for (net::QueryIterator it(url); !it.IsAtEnd(); it.Advance()) {
1712       if (!base::Contains(data_.search_intent_params, it.GetKey())) {
1713         continue;
1714       }
1715       query_params.push_back(base::StrCat({it.GetKey(), "=", it.GetValue()}));
1716     }
1717   }
1718
1719   TemplateURLRef::SearchTermsArgs search_terms_args(search_terms);
1720   search_terms_args.additional_query_params =
1721       base::JoinString(query_params, "&");
1722   *out_url =
1723       GURL(url_ref().ReplaceSearchTerms(search_terms_args, search_terms_data));
1724   if (out_search_terms) {
1725     *out_search_terms = search_terms;
1726   }
1727   return true;
1728 }
1729
1730 bool TemplateURL::ReplaceSearchTermsInURL(
1731     const GURL& url,
1732     const TemplateURLRef::SearchTermsArgs& search_terms_args,
1733     const SearchTermsData& search_terms_data,
1734     GURL* result) const {
1735   // TODO(beaudoin): Use AQS from |search_terms_args| too.
1736   url::Parsed::ComponentType search_term_component;
1737   url::Component search_terms_position;
1738   std::u16string search_terms;
1739   if (!FindSearchTermsInURL(url, search_terms_data, &search_terms,
1740                             &search_term_component, &search_terms_position)) {
1741     return false;
1742   }
1743   DCHECK(search_terms_position.is_nonempty());
1744
1745   // Query and ref are encoded in the same way.
1746   const bool is_in_query = (search_term_component != url::Parsed::PATH);
1747
1748   std::string input_encoding;
1749   std::u16string encoded_terms;
1750   std::u16string encoded_original_query;
1751   EncodeSearchTerms(search_terms_args, is_in_query, &input_encoding,
1752                     &encoded_terms, &encoded_original_query);
1753
1754   std::string old_params;
1755   if (search_term_component == url::Parsed::QUERY) {
1756     old_params = url.query();
1757   } else if (search_term_component == url::Parsed::REF) {
1758     old_params = url.ref();
1759   } else {
1760     DCHECK_EQ(search_term_component, url::Parsed::PATH);
1761     old_params = url.path();
1762   }
1763
1764   std::string new_params(old_params, 0, search_terms_position.begin);
1765   new_params += base::UTF16ToUTF8(encoded_terms);
1766   new_params += old_params.substr(search_terms_position.end());
1767   GURL::Replacements replacements;
1768
1769   if (search_term_component == url::Parsed::QUERY) {
1770     replacements.SetQueryStr(new_params);
1771   } else if (search_term_component == url::Parsed::REF) {
1772     replacements.SetRefStr(new_params);
1773   } else {
1774     DCHECK_EQ(search_term_component, url::Parsed::PATH);
1775     replacements.SetPathStr(new_params);
1776   }
1777
1778   *result = url.ReplaceComponents(replacements);
1779   return true;
1780 }
1781
1782 void TemplateURL::EncodeSearchTerms(
1783     const TemplateURLRef::SearchTermsArgs& search_terms_args,
1784     bool is_in_query,
1785     std::string* input_encoding,
1786     std::u16string* encoded_terms,
1787     std::u16string* encoded_original_query) const {
1788   std::vector<std::string> encodings(input_encodings());
1789   if (!base::Contains(encodings, "UTF-8"))
1790     encodings.push_back("UTF-8");
1791   for (auto i = encodings.begin(); i != encodings.end(); ++i) {
1792     if (TryEncoding(search_terms_args.search_terms,
1793                     search_terms_args.original_query, i->c_str(), is_in_query,
1794                     std::next(i) == encodings.end(), encoded_terms,
1795                     encoded_original_query)) {
1796       *input_encoding = *i;
1797       return;
1798     }
1799   }
1800   NOTREACHED();
1801 }
1802
1803 GURL TemplateURL::GenerateSearchURL(const SearchTermsData& search_terms_data,
1804                                     const std::u16string& search_terms) const {
1805   if (!url_ref().IsValid(search_terms_data))
1806     return GURL();
1807
1808   if (!url_ref().SupportsReplacement(search_terms_data))
1809     return GURL(url());
1810
1811   return GURL(url_ref().ReplaceSearchTerms(
1812       TemplateURLRef::SearchTermsArgs(search_terms), search_terms_data,
1813       nullptr));
1814 }
1815
1816 GURL TemplateURL::GenerateSuggestionURL(
1817     const SearchTermsData& search_terms_data) const {
1818   if (!suggestions_url_ref().IsValid(search_terms_data))
1819     return GURL();
1820
1821   if (!suggestions_url_ref().SupportsReplacement(search_terms_data))
1822     return GURL(suggestions_url());
1823
1824   return GURL(suggestions_url_ref().ReplaceSearchTerms(
1825       TemplateURLRef::SearchTermsArgs(), search_terms_data, nullptr));
1826 }
1827
1828 bool TemplateURL::IsSideSearchSupported() const {
1829   return !side_search_param().empty();
1830 }
1831
1832 bool TemplateURL::IsSideImageSearchSupported() const {
1833   return !side_image_search_param().empty();
1834 }
1835
1836 GURL TemplateURL::GenerateSideSearchURL(
1837     const GURL& search_url,
1838     const std::string& version,
1839     const SearchTermsData& search_terms_data) const {
1840   DCHECK(IsSideSearchSupported());
1841   DCHECK(IsSearchURL(search_url, search_terms_data));
1842   return net::AppendOrReplaceQueryParameter(search_url, side_search_param(),
1843                                             version);
1844 }
1845
1846 GURL TemplateURL::RemoveSideSearchParamFromURL(
1847     const GURL& side_search_url) const {
1848   if (!IsSideSearchSupported())
1849     return side_search_url;
1850   return net::AppendOrReplaceQueryParameter(side_search_url,
1851                                             side_search_param(), absl::nullopt);
1852 }
1853
1854 GURL TemplateURL::GenerateSideImageSearchURL(const GURL& image_search_url,
1855                                              const std::string& version) const {
1856   DCHECK(IsSideImageSearchSupported());
1857   std::string value;
1858   if (net::GetValueForKeyInQuery(image_search_url, side_image_search_param(),
1859                                  &value) &&
1860       value == version)
1861     return image_search_url;
1862
1863   return net::AppendOrReplaceQueryParameter(image_search_url,
1864                                             side_image_search_param(), version);
1865 }
1866
1867 GURL TemplateURL::RemoveSideImageSearchParamFromURL(
1868     const GURL& image_search_url) const {
1869   if (!IsSideImageSearchSupported())
1870     return image_search_url;
1871   return net::AppendOrReplaceQueryParameter(
1872       image_search_url, side_image_search_param(), absl::nullopt);
1873 }
1874
1875 void TemplateURL::CopyFrom(const TemplateURL& other) {
1876   if (this == &other)
1877     return;
1878
1879   data_ = other.data_;
1880   ResizeURLRefVector();
1881   InvalidateCachedValues();
1882   SetPrepopulateId(other.data_.prepopulate_id);
1883 }
1884
1885 void TemplateURL::SetURL(const std::string& url) {
1886   data_.SetURL(url);
1887   engine_type_ = SEARCH_ENGINE_UNKNOWN;
1888   url_ref().InvalidateCachedValues();
1889 }
1890
1891 void TemplateURL::SetPrepopulateId(int id) {
1892   data_.prepopulate_id = id;
1893   const bool prepopulated = id > 0;
1894   for (TemplateURLRef& ref : url_refs_)
1895     ref.prepopulated_ = prepopulated;
1896   suggestions_url_ref_.prepopulated_ = prepopulated;
1897   image_url_ref_.prepopulated_ = prepopulated;
1898   image_translate_url_ref_.prepopulated_ = prepopulated;
1899   new_tab_url_ref_.prepopulated_ = prepopulated;
1900   contextual_search_url_ref_.prepopulated_ = prepopulated;
1901 }
1902
1903 void TemplateURL::ResetKeywordIfNecessary(
1904     const SearchTermsData& search_terms_data,
1905     bool force) {
1906   if (IsGoogleSearchURLWithReplaceableKeyword(search_terms_data) || force) {
1907     DCHECK_NE(OMNIBOX_API_EXTENSION, type_);
1908     GURL url(GenerateSearchURL(search_terms_data));
1909     if (url.is_valid())
1910       data_.SetKeyword(GenerateKeyword(url));
1911   }
1912 }
1913
1914 void TemplateURL::InvalidateCachedValues() const {
1915   for (const TemplateURLRef& ref : url_refs_)
1916     ref.InvalidateCachedValues();
1917   suggestions_url_ref_.InvalidateCachedValues();
1918   image_url_ref_.InvalidateCachedValues();
1919   image_translate_url_ref_.InvalidateCachedValues();
1920   new_tab_url_ref_.InvalidateCachedValues();
1921   contextual_search_url_ref_.InvalidateCachedValues();
1922 }
1923
1924 size_t TemplateURL::EstimateMemoryUsage() const {
1925   size_t res = 0;
1926
1927   res += base::trace_event::EstimateMemoryUsage(data_);
1928   res += base::trace_event::EstimateMemoryUsage(url_refs_);
1929   res += base::trace_event::EstimateMemoryUsage(suggestions_url_ref_);
1930   res += base::trace_event::EstimateMemoryUsage(image_url_ref_);
1931   res += base::trace_event::EstimateMemoryUsage(image_translate_url_ref_);
1932   res += base::trace_event::EstimateMemoryUsage(new_tab_url_ref_);
1933   res += base::trace_event::EstimateMemoryUsage(contextual_search_url_ref_);
1934   res += base::trace_event::EstimateMemoryUsage(extension_info_);
1935
1936   return res;
1937 }
1938
1939 void TemplateURL::ResizeURLRefVector() {
1940   const size_t new_size = data_.alternate_urls.size() + 1;
1941   if (url_refs_.size() == new_size)
1942     return;
1943
1944   url_refs_.clear();
1945   url_refs_.reserve(new_size);
1946   for (size_t i = 0; i != data_.alternate_urls.size(); ++i)
1947     url_refs_.emplace_back(this, i);
1948   url_refs_.emplace_back(this, TemplateURLRef::SEARCH);
1949 }
1950
1951 bool TemplateURL::FindSearchTermsInURL(
1952     const GURL& url,
1953     const SearchTermsData& search_terms_data,
1954     std::u16string* search_terms,
1955     url::Parsed::ComponentType* search_term_component,
1956     url::Component* search_terms_position) const {
1957   DCHECK(search_terms);
1958   search_terms->clear();
1959
1960   // Try to match with every pattern.
1961   for (const TemplateURLRef& ref : url_refs_) {
1962     if (ref.ExtractSearchTermsFromURL(url, search_terms, search_terms_data,
1963         search_term_component, search_terms_position)) {
1964       // If ExtractSearchTermsFromURL() returns true and |search_terms| is empty
1965       // it means the pattern matched but no search terms were present. In this
1966       // case we fail immediately without looking for matches in subsequent
1967       // patterns. This means that given patterns
1968       //    [ "http://foo/#q={searchTerms}", "http://foo/?q={searchTerms}" ],
1969       // calling ExtractSearchTermsFromURL() on "http://foo/?q=bar#q=' would
1970       // return false. This is important for at least Google, where such URLs
1971       // are invalid.
1972       return !search_terms->empty();
1973     }
1974   }
1975   return false;
1976 }
1977
1978 bool TemplateURL::ContainsSideSearchParam(const GURL& url) const {
1979   std::string side_search_value;
1980   if (!IsSideSearchSupported())
1981     return false;
1982   net::GetValueForKeyInQuery(url, side_search_param(), &side_search_value);
1983   return !side_search_value.empty();
1984 }
1985
1986 bool TemplateURL::ContainsSideImageSearchParam(const GURL& url) const {
1987   std::string side_image_search_value;
1988   if (!IsSideSearchSupported())
1989     return false;
1990   net::GetValueForKeyInQuery(url, side_image_search_param(),
1991                              &side_image_search_value);
1992   return !side_image_search_value.empty();
1993 }