// Copyright 2012 The Chromium Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "components/omnibox/browser/history_url_provider.h" #include #include #include #include #include "base/command_line.h" #include "base/containers/adapters.h" #include "base/feature_list.h" #include "base/functional/bind.h" #include "base/location.h" #include "base/memory/raw_ptr.h" #include "base/strings/string_util.h" #include "base/strings/utf_string_conversions.h" #include "base/task/sequenced_task_runner.h" #include "base/task/single_thread_task_runner.h" #include "base/time/time.h" #include "base/trace_event/memory_usage_estimator.h" #include "base/trace_event/trace_event.h" #include "components/bookmarks/browser/bookmark_utils.h" #include "components/history/core/browser/history_backend.h" #include "components/history/core/browser/history_database.h" #include "components/history/core/browser/history_service.h" #include "components/history/core/browser/history_types.h" #include "components/omnibox/browser/autocomplete_enums.h" #include "components/omnibox/browser/autocomplete_match.h" #include "components/omnibox/browser/autocomplete_match_classification.h" #include "components/omnibox/browser/autocomplete_provider.h" #include "components/omnibox/browser/autocomplete_provider_listener.h" #include "components/omnibox/browser/autocomplete_result.h" #include "components/omnibox/browser/autocomplete_scoring_signals_annotator.h" #include "components/omnibox/browser/history_provider.h" #include "components/omnibox/browser/in_memory_url_index_types.h" #include "components/omnibox/browser/keyword_provider.h" #include "components/omnibox/browser/omnibox_field_trial.h" #include "components/omnibox/browser/url_prefix.h" #include "components/omnibox/browser/verbatim_match.h" #include "components/prefs/pref_service.h" #include "components/search_engines/search_terms_data.h" #include "components/search_engines/template_url_service.h" #include "components/url_formatter/url_fixer.h" #include "components/url_formatter/url_formatter.h" #include "net/base/registry_controlled_domains/registry_controlled_domain.h" #include "third_party/metrics_proto/omnibox_focus_type.pb.h" #include "third_party/metrics_proto/omnibox_input_type.pb.h" #include "third_party/metrics_proto/omnibox_scoring_signals.pb.h" #include "ui/base/page_transition_types.h" #include "url/gurl.h" #include "url/third_party/mozilla/url_parse.h" #include "url/url_util.h" namespace { using ScoringSignals = ::metrics::OmniboxScoringSignals; // Acts like the > operator for URLInfo classes. bool CompareHistoryMatch(const history::HistoryMatch& a, const history::HistoryMatch& b) { // A URL that has been typed at all is better than one that has never been // typed. (Note "!"s on each side) if (!a.url_info.typed_count() != !b.url_info.typed_count()) return a.url_info.typed_count() > b.url_info.typed_count(); // Innermost matches (matches after any scheme or "www.") are better than // non-innermost matches. if (a.innermost_match != b.innermost_match) return a.innermost_match; // URLs that have been typed more often are better. if (a.url_info.typed_count() != b.url_info.typed_count()) return a.url_info.typed_count() > b.url_info.typed_count(); // For URLs that have each been typed once, a host (alone) is better than a // page inside. if ((a.url_info.typed_count() == 1) && (a.IsHostOnly() != b.IsHostOnly())) return a.IsHostOnly(); // URLs that have been visited more often are better. if (a.url_info.visit_count() != b.url_info.visit_count()) return a.url_info.visit_count() > b.url_info.visit_count(); // URLs that have been visited more recently are better. if (a.url_info.last_visit() != b.url_info.last_visit()) return a.url_info.last_visit() > b.url_info.last_visit(); // Use alphabetical order on the url spec as a tie-breaker. return a.url_info.url().spec() > b.url_info.url().spec(); } // Sorts and dedups the given list of matches. void SortAndDedupMatches(history::HistoryMatches* matches) { // Sort by quality, best first. std::sort(matches->begin(), matches->end(), &CompareHistoryMatch); // Remove duplicate matches (caused by the search string appearing in one of // the prefixes as well as after it). Consider the following scenario: // // User has visited "http://http.com" once and "http://htaccess.com" twice. // User types "http". The autocomplete search with prefix "http://" returns // the first host, while the search with prefix "" returns both hosts. Now // we sort them into rank order: // http://http.com (innermost_match) // http://htaccess.com (!innermost_match, url_info.visit_count == 2) // http://http.com (!innermost_match, url_info.visit_count == 1) // // The above scenario tells us we can't use std::unique(), since our // duplicates are not always sequential. It also tells us we should remove // the lower-quality duplicate(s), since otherwise the returned results won't // be ordered correctly. This is easy to do: we just always remove the later // element of a duplicate pair. // Be careful! Because the vector contents may change as we remove elements, // we use an index instead of an iterator in the outer loop, and don't // precalculate the ending position. for (size_t i = 0; i < matches->size(); ++i) { for (history::HistoryMatches::iterator j(matches->begin() + i + 1); j != matches->end();) { if ((*matches)[i].url_info.url() == j->url_info.url()) j = matches->erase(j); else ++j; } } } // Calculates a new relevance score applying half-life time decaying to `count` // using `time_since_last_visit` and `score_buckets`. This function will never // return a score higher than `undecayed_relevance`; in other words, it can only // demote the old score. double CalculateRelevanceUsingScoreBuckets( const HUPScoringParams::ScoreBuckets& score_buckets, const base::TimeDelta& time_since_last_visit, int undecayed_relevance, int undecayed_count) { // Back off if above relevance cap. if ((score_buckets.relevance_cap() != -1) && (undecayed_relevance >= score_buckets.relevance_cap())) return undecayed_relevance; // Time based decay using half-life time. double decayed_count = undecayed_count; double decay_factor = score_buckets.HalfLifeTimeDecay(time_since_last_visit); if (decayed_count > 0) decayed_count *= decay_factor; const HUPScoringParams::ScoreBuckets::CountMaxRelevance* score_bucket = nullptr; const double factor = (score_buckets.use_decay_factor() ? decay_factor : decayed_count); for (size_t i = 0; i < score_buckets.buckets().size(); ++i) { score_bucket = &score_buckets.buckets()[i]; if (factor >= score_bucket->first) break; } return (score_bucket && (undecayed_relevance > score_bucket->second)) ? score_bucket->second : undecayed_relevance; } // Returns a new relevance score for the given `match` based on the // `old_relevance` score and `scoring_params`. The new relevance score is // guaranteed to be less than or equal to `old_relevance`. In other words, this // function can only demote a score, never boost it. Returns `old_relevance` if // experimental scoring is disabled. int CalculateRelevanceScoreUsingScoringParams( const history::HistoryMatch& match, int old_relevance, const HUPScoringParams& scoring_params) { const base::TimeDelta time_since_last_visit = base::Time::Now() - match.url_info.last_visit(); int relevance = CalculateRelevanceUsingScoreBuckets( scoring_params.typed_count_buckets, time_since_last_visit, old_relevance, match.url_info.typed_count()); // Additional demotion (on top of typed_count demotion) of URLs that were // never typed. if (match.url_info.typed_count() == 0) { relevance = CalculateRelevanceUsingScoreBuckets( scoring_params.visited_count_buckets, time_since_last_visit, relevance, match.url_info.visit_count()); } DCHECK_LE(relevance, old_relevance); return relevance; } // Extracts typed_count, visit_count, and last_visited time from the URLRow and // puts them in the additional info field of the `match` for display in // about:omnibox. void RecordAdditionalInfoFromUrlRow(const history::URLRow& info, AutocompleteMatch* match) { match->RecordAdditionalInfo("typed count", info.typed_count()); match->RecordAdditionalInfo("visit count", info.visit_count()); match->RecordAdditionalInfo("last visit", info.last_visit()); } // Ensures that `matches` contains an entry for `info`, creating a new such // entry if necessary (using `match_template` to get all the other match data). // // If `promote` is true, this also ensures the entry is the first element in // `matches`, moving or adding it to the front as appropriate. When `promote` // is false, existing matches are left in place, and newly added matches are // placed at the back. void CreateAndPromoteMatch(const history::URLRow& info, const history::HistoryMatch& match_template, history::HistoryMatches* matches, bool promote) { // `matches` may already have an entry for this. for (history::HistoryMatches::iterator i(matches->begin()); i != matches->end(); ++i) { if (i->url_info.url() == info.url()) { // Rotate it to the front if the caller wishes. if (promote) std::rotate(matches->begin(), i, i + 1); return; } } // No entry, so create one using `match_template` as a basis. history::HistoryMatch match = match_template; match.url_info = info; if (promote) matches->push_front(match); else matches->push_back(match); } // Returns whether `match` is suitable for inline autocompletion. bool CanPromoteMatchForInlineAutocomplete(const history::HistoryMatch& match) { // We can promote this match if it's been typed at least n times, where n == 1 // for "simple" (host-only) URLs and n == 2 for others. We set a higher bar // for these long URLs because it's less likely that users will want to visit // them again. Even though we don't increment the typed_count for pasted-in // URLs, if the user manually edits the URL or types some long thing in by // hand, we wouldn't want to immediately start autocompleting it. return match.url_info.typed_count() && ((match.url_info.typed_count() > 1) || match.IsHostOnly()); } // Given the user's `input` and a `match` created from it, reduce the match's // URL to just a host. If this host still matches the user input, return it. // Returns the empty URL on failure. GURL ConvertToHostOnly(const history::HistoryMatch& match, const std::u16string& input) { // See if we should try to do host-only suggestions for this URL. Nonstandard // schemes means there's no authority section, so suggesting the host name // is useless. File URLs are standard, but host suggestion is not useful for // them either. const GURL& url = match.url_info.url(); if (!url.is_valid() || !url.IsStandard() || url.SchemeIsFile()) return GURL(); // Transform to a host-only match. Bail if the host no longer matches the // user input (e.g. because the user typed more than just a host). GURL host = url.GetWithEmptyPath(); if ((host.spec().length() < (match.input_location + input.length()))) return GURL(); // User typing is longer than this host suggestion. const std::u16string spec = base::UTF8ToUTF16(host.spec()); if (spec.compare(match.input_location, input.length(), input)) return GURL(); // User typing is no longer a prefix. return host; } } // namespace // ----------------------------------------------------------------- // HistoryURLProvider // These ugly magic numbers will go away once we switch all scoring // behavior (including URL-what-you-typed) to HistoryQuick provider. const int HistoryURLProvider::kScoreForBestInlineableResult = 1413; const int HistoryURLProvider::kScoreForUnvisitedIntranetResult = 1403; const int HistoryURLProvider::kScoreForWhatYouTypedResult = 1203; const int HistoryURLProvider::kBaseScoreForNonInlineableResult = 900; // VisitClassifier is used to classify the type of visit to a particular url. class HistoryURLProvider::VisitClassifier { public: enum class Type { kInvalid, // Navigations to the URL are not allowed. kUnvisitedIntranet, // A navigable URL for which we have no visit data but // which is known to refer to a visited intranet host. kVisited, // The site has been previously visited. }; VisitClassifier(HistoryURLProvider* provider, const AutocompleteInput& input, history::URLDatabase* db); VisitClassifier(const VisitClassifier&) = delete; VisitClassifier& operator=(const VisitClassifier&) = delete; // Returns the type of visit for the specified input. Type type() const { return type_; } // Returns the URLRow for the visit. // If the type of the visit is UNVISITED_INTRANET, the return value of this // function does not have any visit data; only the URL field is set. const history::URLRow& url_row() const { return url_row_; } private: raw_ptr provider_; raw_ptr db_; Type type_ = Type::kInvalid; history::URLRow url_row_; }; HistoryURLProvider::VisitClassifier::VisitClassifier( HistoryURLProvider* provider, const AutocompleteInput& input, history::URLDatabase* db) : provider_(provider), db_(db) { // Detect email addresses. These cases will look like "http://user@site/", // and because the history backend strips auth creds, we'll get a bogus exact // match below if the user has visited "site". if ((input.type() == metrics::OmniboxInputType::UNKNOWN) && input.parts().username.is_nonempty() && input.parts().password.is_empty() && input.parts().path.is_empty()) return; // If the input can be canonicalized to a valid URL, look up all // prefix+input combinations in the URL database to determine if the input // corresponds to any visited URL. if (!input.canonicalized_url().is_valid()) return; // Iterate over all prefixes in ascending number of components (i.e. from the // empty prefix to those that have most components). const std::string& desired_tld = input.desired_tld(); const URLPrefixes& url_prefixes = URLPrefix::GetURLPrefixes(); for (const URLPrefix& url_prefix : base::Reversed(url_prefixes)) { const GURL url_with_prefix = url_formatter::FixupURL( base::UTF16ToUTF8(url_prefix.prefix + input.text()), desired_tld); if (url_with_prefix.is_valid() && db_->GetRowForURL(url_with_prefix, &url_row_) && !url_row_.hidden()) { type_ = Type::kVisited; return; } } // If the input does not correspond to a visited URL, we check if the // canonical URL has an intranet hostname that the user visited (albeit with a // different port and/or path) before. If this is true, `url_row_` will be // mostly empty: the URL field will be set to an unvisited URL with the same // scheme and host as some visited URL in the db. const GURL as_known_intranet_url = provider_->AsKnownIntranetURL(db_, input); if (as_known_intranet_url.is_valid()) { url_row_ = history::URLRow(as_known_intranet_url); type_ = Type::kUnvisitedIntranet; } } HistoryURLProviderParams::HistoryURLProviderParams( const AutocompleteInput& input, const AutocompleteInput& input_before_fixup, bool trim_http, const AutocompleteMatch& what_you_typed_match, const TemplateURL* default_search_provider, const SearchTermsData* search_terms_data, bool allow_deleting_browser_history, const TemplateURL* starter_pack_engine) : origin_task_runner(base::SequencedTaskRunner::GetCurrentDefault()), input(input), input_before_fixup(input_before_fixup), trim_http(trim_http), what_you_typed_match(what_you_typed_match), failed(false), exact_suggestion_is_in_history(false), promote_type(NEITHER), default_search_provider( default_search_provider ? new TemplateURL(default_search_provider->data()) : nullptr), search_terms_data(SearchTermsData::MakeSnapshot(search_terms_data)), allow_deleting_browser_history(allow_deleting_browser_history), starter_pack_engine(starter_pack_engine) {} HistoryURLProviderParams::~HistoryURLProviderParams() = default; size_t HistoryURLProviderParams::EstimateMemoryUsage() const { size_t res = 0; res += base::trace_event::EstimateMemoryUsage(input); res += base::trace_event::EstimateMemoryUsage(what_you_typed_match); res += base::trace_event::EstimateMemoryUsage(matches); res += base::trace_event::EstimateMemoryUsage(default_search_provider); res += base::trace_event::EstimateMemoryUsage(search_terms_data); return res; } HistoryURLProvider::HistoryURLProvider(AutocompleteProviderClient* client, AutocompleteProviderListener* listener) : HistoryProvider(AutocompleteProvider::TYPE_HISTORY_URL, client), params_(nullptr), search_url_database_(OmniboxFieldTrial::HUPSearchDatabase()) { AddListener(listener); // Initialize the default HUP scoring params. OmniboxFieldTrial::GetDefaultHUPScoringParams(&scoring_params_); // Initialize HUP scoring params based on the current experiment. OmniboxFieldTrial::GetExperimentalHUPScoringParams(&scoring_params_); } void HistoryURLProvider::Start(const AutocompleteInput& input, bool minimal_changes) { TRACE_EVENT0("omnibox", "HistoryURLProvider::Start"); // NOTE: We could try hard to do less work in the `minimal_changes` case // here; some clever caching would let us reuse the raw matches from the // history DB without re-querying. However, we'd still have to go back to // the history thread to mark these up properly, and if pass 2 is currently // running, we'd need to wait for it to return to the main thread before // doing this (we can't just write new data for it to read due to thread // safety issues). At that point it's just as fast, and easier, to simply // re-run the query from scratch and ignore `minimal_changes`. // Cancel any in-progress query. Stop(AutocompleteStopReason::kClobbered); if (input.IsZeroSuggest() || (input.type() == metrics::OmniboxInputType::EMPTY)) { return; } // Remove the keyword from input if we're in keyword mode for a starter pack // engine. const auto [autocomplete_input, starter_pack_engine] = AdjustInputForStarterPackKeyword(input, client()->GetTemplateURLService()); // Do some fixup on the user input before matching against it, so we provide // good results for local file paths, input with spaces, etc. FixupReturn fixup_return(FixupUserInput(autocomplete_input)); if (!fixup_return.first) return; // Inputs like '@hist' shouldn't match 'history.com' because users are more // likely to be looking for a starer pack scope than a URL. However, // URLs containing '@' before the host, such as '@history.com', area valid // URLs and still needs to run autocompletion. if (autocomplete_input.GetFeaturedKeywordMode() != AutocompleteInput::FeaturedKeywordMode::kFalse) { fixup_return.second = u"@" + fixup_return.second; } url::Parsed parts; url_formatter::SegmentURL(fixup_return.second, &parts); AutocompleteInput fixed_up_input(autocomplete_input); fixed_up_input.UpdateText(fixup_return.second, std::u16string::npos, parts); // Create a match for what the user typed. const bool trim_http = !AutocompleteInput::HasHTTPScheme(autocomplete_input.text()); AutocompleteMatch what_you_typed_match( VerbatimMatchForInput(this, client(), fixed_up_input, fixed_up_input.canonicalized_url(), trim_http)); // If the input fix-up above added characters, show them as an // autocompletion, unless directed not to. if (!autocomplete_input.prevent_inline_autocomplete() && fixed_up_input.text().size() > autocomplete_input.text().size() && base::StartsWith(fixed_up_input.text(), autocomplete_input.text(), base::CompareCase::SENSITIVE)) { what_you_typed_match.fill_into_edit = fixed_up_input.text(); what_you_typed_match.inline_autocompletion = fixed_up_input.text().substr(autocomplete_input.text().size()); what_you_typed_match.contents_class.push_back( {autocomplete_input.text().length(), ACMatchClassification::URL}); } what_you_typed_match.relevance = CalculateRelevance(WHAT_YOU_TYPED, 0); if (autocomplete_input.in_keyword_mode()) { // TODO(yoangela): We may want to suppress what you typed matches when in // keyword mode. what_you_typed_match.from_keyword = true; } // Add the what-you-typed match as a fallback in case we can't get the history // service or URL DB; otherwise, we'll replace this match lower down. Don't // do this for queries, though -- while we can sometimes mark up a match for // them, it's not what the user wants, and just adds noise. if (fixed_up_input.type() != metrics::OmniboxInputType::QUERY) matches_.push_back(what_you_typed_match); // We'll need the history service to run both passes, so try to obtain it. history::HistoryService* const history_service = client()->GetHistoryService(); if (!history_service) return; // Get the default search provider and search terms data now since we have to // retrieve these on the UI thread, and the second pass runs on the history // thread. `template_url_service` can be null when testing. TemplateURLService* template_url_service = client()->GetTemplateURLService(); const TemplateURL* default_search_provider = template_url_service ? template_url_service->GetDefaultSearchProvider() : nullptr; const SearchTermsData* search_terms_data = template_url_service ? &template_url_service->search_terms_data() : nullptr; // Create the data structure for the autocomplete passes. We'll save this off // onto the `params_` member for later deletion below if we need to run pass // 2. std::unique_ptr params(new HistoryURLProviderParams( fixed_up_input, autocomplete_input, trim_http, what_you_typed_match, default_search_provider, search_terms_data, client()->AllowDeletingBrowserHistory(), starter_pack_engine)); // Pass 1: Get the in-memory URL database, and use it to find and promote // the inline autocomplete match, if any. history::URLDatabase* url_db = history_service->InMemoryDatabase(); // url_db can be null if it hasn't finished initializing (or failed to // initialize). In this case all we can do is fall back on the second pass. // // TODO(pkasting): We should just block here until this loads. Any time // someone unloads the history backend, we'll get inconsistent inline // autocomplete behavior here. if (url_db) { DoAutocomplete(nullptr, url_db, params.get()); matches_.clear(); PromoteMatchesIfNecessary(*params); // NOTE: We don't reset `params` here since at least the `promote_type` // field on it will be read by the second pass -- see comments in // DoAutocomplete(). } // Pass 2: Ask the history service to call us back on the history thread, // where we can read the full on-disk DB. if (search_url_database_ && !autocomplete_input.omit_asynchronous_matches()) { done_ = false; params_ = params.release(); // This object will be destroyed in // QueryComplete() once we're done with it. history_service->ScheduleDBTaskForUI( base::BindOnce(&HistoryURLProvider::ExecuteWithDB, this, params_)); } } void HistoryURLProvider::Stop(AutocompleteStopReason stop_reason) { AutocompleteProvider::Stop(stop_reason); if (params_) params_->cancel_flag.Set(); } size_t HistoryURLProvider::EstimateMemoryUsage() const { size_t res = HistoryProvider::EstimateMemoryUsage(); if (params_) res += base::trace_event::EstimateMemoryUsage(*params_); res += base::trace_event::EstimateMemoryUsage(scoring_params_); return res; } // Note: This object can get leaked on shutdown if there are pending // requests on the database (which hold a reference to us). Normally, these // messages get flushed for each thread. We do a round trip from main, to // history, back to main while holding a reference. If the main thread // completes before the history thread, the message to delegate back to the // main thread will not run and the reference will leak. Therefore, don't do // anything on destruction. HistoryURLProvider::~HistoryURLProvider() = default; // static int HistoryURLProvider::CalculateRelevance(MatchType match_type, int match_number) { switch (match_type) { case INLINE_AUTOCOMPLETE: return kScoreForBestInlineableResult; case UNVISITED_INTRANET: return kScoreForUnvisitedIntranetResult; case WHAT_YOU_TYPED: return kScoreForWhatYouTypedResult; default: // NORMAL return kBaseScoreForNonInlineableResult + match_number; } } // static ACMatchClassifications HistoryURLProvider::ClassifyDescription( const std::u16string& input_text, const std::u16string& description) { TermMatches term_matches = FindTermMatches(input_text, description); return ClassifyTermMatches(term_matches, description.size(), ACMatchClassification::MATCH, ACMatchClassification::NONE); } void HistoryURLProvider::ExecuteWithDB(HistoryURLProviderParams* params, history::HistoryBackend* backend, history::URLDatabase* db) { // We may get called with a null database if it couldn't be properly // initialized. if (!db) { params->failed = true; } else if (!params->cancel_flag.IsSet()) { DoAutocomplete(backend, db, params); } // Return the results (if any) to the originating sequence. params->origin_task_runner->PostTask( FROM_HERE, base::BindOnce(&HistoryURLProvider::QueryComplete, this, params)); } void HistoryURLProvider::DoAutocomplete(history::HistoryBackend* backend, history::URLDatabase* db, HistoryURLProviderParams* params) { // Get the matching URLs from the DB. params->matches.clear(); history::URLRows url_matches; // In keyword mode, it's possible we only provide results from one or two // autocomplete provider(s), so it's sometimes necessary to show more results // than provider_max_matches_. size_t max_matches = params->input.in_keyword_mode() ? provider_max_matches_in_keyword_mode_ : provider_max_matches_; if (search_url_database_) { const URLPrefixes& prefixes = URLPrefix::GetURLPrefixes(); for (const auto& prefix : prefixes) { if (params->cancel_flag.IsSet()) return; // Canceled in the middle of a query, give up. // We only need `max_matches` results in the end, but before we get there // we need to promote lower-quality matches that are prefixes of higher- // quality matches, and remove lower-quality redirects. So we ask for // more results than we need, of every prefix type, in hopes this will // give us far more than enough to work with. CullRedirects() will then // reduce the list to the best `max_matches` results. std::string prefixed_input = base::UTF16ToUTF8(prefix.prefix + params->input.text()); db->AutocompleteForPrefix(prefixed_input, max_matches * 2, !backend, &url_matches); for (const auto& url_match : url_matches) { const GURL& row_url = url_match.url(); const URLPrefix* best_prefix = URLPrefix::BestURLPrefix( base::UTF8ToUTF16(row_url.spec()), std::u16string()); DCHECK(best_prefix); history::HistoryMatch match; match.url_info = url_match; match.input_location = prefix.prefix.length(); match.innermost_match = prefix.num_components >= best_prefix->num_components; AutocompleteMatch::GetMatchComponents( row_url, {{match.input_location, prefixed_input.length()}}, &match.match_in_scheme, &match.match_in_subdomain); params->matches.push_back(std::move(match)); } } // Create sorted list of suggestions. CullPoorMatches(params); SortAndDedupMatches(¶ms->matches); } // Try to create a shorter suggestion from the best match. // We consider the what-you-typed match eligible for display when it's // navigable and there's a reasonable chance the user intended to do // something other than search. We use a variety of heuristics to determine // this, e.g. whether the user explicitly typed a scheme, or if omnibox // searching has been disabled by policy. In the cases where we've parsed as // UNKNOWN, we'll still show an accidental search infobar if need be. VisitClassifier classifier(this, params->input, db); params->have_what_you_typed_match = (params->input.type() != metrics::OmniboxInputType::QUERY) && ((params->input.type() != metrics::OmniboxInputType::UNKNOWN) || (classifier.type() == VisitClassifier::Type::kUnvisitedIntranet) || !params->trim_http || (AutocompleteInput::NumNonHostComponents(params->input.parts()) > 0) || !params->default_search_provider); const bool have_shorter_suggestion_suitable_for_inline_autocomplete = PromoteOrCreateShorterSuggestion(db, params); // Check whether what the user typed appears in history. const GURL& what_you_typed_url = params->what_you_typed_match.destination_url; bool can_check_history_for_exact_match = // Checking what_you_typed_match.destination_url.is_valid() tells us // whether VerbatimMatchForInput succeeded in constructing a valid match. what_you_typed_url.is_valid() && // We shouldn't match if the URL embedded username/password credentials, // since it will be lost in FixupExactSuggestion. !what_you_typed_url.has_username() && !what_you_typed_url.has_password() && // Additionally, in the case where the user has typed "foo.com" and // visited (but not typed) "foo/", and the input is "foo", the first pass // will fall into the FRONT_HISTORY_MATCH case for "foo.com" but the // second pass can suggest the exact input as a better URL. Since we need // both passes to agree, and since during the first pass there's no way to // know about "foo/", ensure that if the promote type was set to // FRONT_HISTORY_MATCH during the first pass, the second pass will not // consider the exact suggestion to be in history and therefore will not // suggest the exact input as a better match. (Note that during the first // pass, this conditional will always succeed since `promote_type` is // initialized to NEITHER.) (params->promote_type != HistoryURLProviderParams::FRONT_HISTORY_MATCH); params->exact_suggestion_is_in_history = can_check_history_for_exact_match && FixupExactSuggestion(db, classifier, params); // If we succeeded in fixing up the exact match based on the user's history, // we should treat it as the best match regardless of input type. If not, // then we check whether there's an inline autocompletion we can create from // this input, so we can promote that as the best match. if (params->exact_suggestion_is_in_history) { params->promote_type = HistoryURLProviderParams::WHAT_YOU_TYPED_MATCH; } else if (!params->matches.empty() && (have_shorter_suggestion_suitable_for_inline_autocomplete || CanPromoteMatchForInlineAutocomplete(params->matches[0]))) { // Note that we promote this inline-autocompleted match even when // params->prevent_inline_autocomplete is true. This is safe because in // this case the match will be marked as "not allowed to be default", and // a non-inlined match that is "allowed to be default" will be reordered // above it by the controller/AutocompleteResult. We ensure there is such // a match in two ways: // * If params->have_what_you_typed_match is true, we force the // what-you-typed match to be added in this case. See comments in // PromoteMatchesIfNecessary(). // * Otherwise, we should have some sort of QUERY or UNKNOWN input that // the SearchProvider will provide a defaultable what-you-typed match // for. params->promote_type = HistoryURLProviderParams::FRONT_HISTORY_MATCH; } else { // Failed to promote any URLs. Use the What You Typed match, if we have it. params->promote_type = params->have_what_you_typed_match ? HistoryURLProviderParams::WHAT_YOU_TYPED_MATCH : HistoryURLProviderParams::NEITHER; } const size_t max_results = max_matches + (params->exact_suggestion_is_in_history ? 1 : 0); if (backend) { // Remove redirects and trim list to size. We want to provide up to // `max_matches` results plus the What You Typed result, if it was // added to `params->matches` above. CullRedirects(backend, ¶ms->matches, max_results); } else if (params->matches.size() > max_results) { // Simply trim the list to size. params->matches.resize(max_results); } } void HistoryURLProvider::PromoteMatchesIfNecessary( const HistoryURLProviderParams& params) { bool populate_scoring_signals = OmniboxFieldTrial::IsPopulatingUrlScoringSignalsEnabled(); if (params.promote_type == HistoryURLProviderParams::NEITHER) return; if (params.promote_type == HistoryURLProviderParams::FRONT_HISTORY_MATCH) { matches_.push_back(HistoryMatchToACMatch( params, 0, CalculateRelevance(INLINE_AUTOCOMPLETE, 0), populate_scoring_signals)); } // There are two cases where we need to add the what-you-typed-match: // * If params.promote_type is WHAT_YOU_TYPED_MATCH, we're being explicitly // directed to. // * If params.have_what_you_typed_match is true, then params.promote_type // can't be NEITHER (see code near the end of DoAutocomplete()), so if // it's not WHAT_YOU_TYPED_MATCH, it must be FRONT_HISTORY_MATCH, and // we'll have promoted the history match above. If // params.prevent_inline_autocomplete is also true, then this match // will be marked "not allowed to be default", and we need to add the // what-you-typed match to ensure there's a legal default match for the // controller/AutocompleteResult to promote. (If // params.have_what_you_typed_match is false, the SearchProvider should // take care of adding this defaultable match.) if ((params.promote_type == HistoryURLProviderParams::WHAT_YOU_TYPED_MATCH) || (!matches_.back().allowed_to_be_default_match && params.have_what_you_typed_match)) { matches_.push_back(params.what_you_typed_match); } } void HistoryURLProvider::QueryComplete( HistoryURLProviderParams* params_gets_deleted) { TRACE_EVENT0("omnibox", "HistoryURLProvider::QueryComplete"); // Ensure `params_gets_deleted` gets deleted on exit. std::unique_ptr params(params_gets_deleted); // If the user hasn't already started another query, clear our member pointer // so we can't write into deleted memory. if (params_ == params_gets_deleted) params_ = nullptr; // Don't send responses for queries that have been canceled. if (params->cancel_flag.IsSet()) return; // Already set done_ when we canceled, no need to set it again. // Don't modify `matches_` if the query failed, since it might have a default // match in it, whereas `params->matches` will be empty. if (!params->failed) { matches_.clear(); PromoteMatchesIfNecessary(*params); // Determine relevance of highest scoring match, if any. int relevance = matches_.empty() ? CalculateRelevance(NORMAL, static_cast(params->matches.size() - 1)) : matches_[0].relevance; // Convert the history matches to autocomplete matches. If we promoted the // first match, skip over it. const size_t first_match = (params->exact_suggestion_is_in_history || (params->promote_type == HistoryURLProviderParams::FRONT_HISTORY_MATCH)) ? 1 : 0; bool populate_scoring_signals = OmniboxFieldTrial::IsPopulatingUrlScoringSignalsEnabled(); for (size_t i = first_match; i < params->matches.size(); ++i) { // All matches score one less than the previous match. --relevance; // The experimental scoring must not change the top result's score. if (!matches_.empty()) { relevance = CalculateRelevanceScoreUsingScoringParams( params->matches[i], relevance, scoring_params_); } matches_.push_back(HistoryMatchToACMatch(*params, i, relevance, populate_scoring_signals)); } } done_ = true; NotifyListeners(true); } bool HistoryURLProvider::FixupExactSuggestion( history::URLDatabase* db, const VisitClassifier& classifier, HistoryURLProviderParams* params) const { MatchType type = INLINE_AUTOCOMPLETE; switch (classifier.type()) { case VisitClassifier::Type::kInvalid: return false; case VisitClassifier::Type::kUnvisitedIntranet: params->what_you_typed_match.destination_url = classifier.url_row().url(); type = UNVISITED_INTRANET; break; default: DCHECK_EQ(VisitClassifier::Type::kVisited, classifier.type()); params->what_you_typed_match.deletable = params->allow_deleting_browser_history; // We have data for this match, use it. auto title = classifier.url_row().title(); params->what_you_typed_match.description = title; params->what_you_typed_match.destination_url = classifier.url_row().url(); RecordAdditionalInfoFromUrlRow(classifier.url_row(), ¶ms->what_you_typed_match); params->what_you_typed_match.description_class = ClassifyDescription( params->input.text(), params->what_you_typed_match.description); if (!classifier.url_row().typed_count()) { // If we reach here, we must be in the second pass, and we must not have // this row's data available during the first pass. That means we // either scored it as WHAT_YOU_TYPED or UNVISITED_INTRANET, and to // maintain the ordering between passes consistent, we need to score it // the same way here. const GURL as_known_intranet_url = AsKnownIntranetURL(db, params->input); type = as_known_intranet_url.is_valid() ? UNVISITED_INTRANET : WHAT_YOU_TYPED; } break; } const GURL& url = params->what_you_typed_match.destination_url; const url::Parsed& parsed = url.parsed_for_possibly_invalid_spec(); // If the what-you-typed result looks like a single word (which can be // interpreted as an intranet address) followed by a pound sign ("#"), leave // the score for the url-what-you-typed result as is and also don't mark it // as allowed to be the default match. It will likely be outscored by a // search query from the SearchProvider or, if not, the search query default // match will in any case--which is allowed to be the default match--will be // reordered to be first. This test fixes cases such as "c#" and "c# foo" // where the user has visited an intranet site "c". We want the search-what- // you-typed score to beat the URL-what-you-typed score in this case. Most // of the below test tries to make sure that this code does not trigger if // the user did anything to indicate the desired match is a URL. For // instance, "c/# foo" will not pass the test because that will be classified // as input type URL. The parsed.CountCharactersBefore() in the test looks // for the presence of a reference fragment in the URL by checking whether // the position differs included the delimiter (pound sign) versus not // including the delimiter. (One cannot simply check url.ref() because it // will not distinguish between the input "c" and the input "c#", both of // which will have empty reference fragments.) if ((type == UNVISITED_INTRANET) && (params->input.type() != metrics::OmniboxInputType::URL) && url.GetUsername().empty() && url.GetPassword().empty() && url.GetPort().empty() && (url.path() == "/") && url.GetQuery().empty() && (parsed.CountCharactersBefore(url::Parsed::REF, true) != parsed.CountCharactersBefore(url::Parsed::REF, false))) { return false; } params->what_you_typed_match.allowed_to_be_default_match = true; params->what_you_typed_match.relevance = CalculateRelevance(type, 0); // If there are any other matches, then don't promote this match here, in // hopes the caller will be able to inline autocomplete a better suggestion. // DoAutocomplete() will fall back on this match if inline autocompletion // fails. This matches how we react to never-visited URL inputs in the non- // intranet case. if (type == UNVISITED_INTRANET && !params->matches.empty()) return false; // Put it on the front of the HistoryMatches for redirect culling. CreateAndPromoteMatch(classifier.url_row(), history::HistoryMatch(), ¶ms->matches, true); return true; } GURL HistoryURLProvider::AsKnownIntranetURL( history::URLDatabase* db, const AutocompleteInput& input) const { // Normally passing the first two conditions below ought to guarantee the // third condition, but because FixupUserInput() can run and modify the // input's text and parts between Parse() and here, it seems better to be // paranoid and check. if ((input.type() != metrics::OmniboxInputType::UNKNOWN) || !base::EqualsCaseInsensitiveASCII(input.scheme(), url::kHttpScheme) || input.parts().host.is_empty()) return GURL(); const std::string host(base::UTF16ToUTF8( input.text().substr(input.parts().host.begin, input.parts().host.len))); // Check if the host has registry domain. if (net::registry_controlled_domains::HostHasRegistryControlledDomain( host, net::registry_controlled_domains::EXCLUDE_UNKNOWN_REGISTRIES, net::registry_controlled_domains::EXCLUDE_PRIVATE_REGISTRIES)) return GURL(); const GURL& url = input.canonicalized_url(); // Check if the host of the canonical URL can be found in the database. std::string scheme_in_db; if (db->IsTypedHost(host, &scheme_in_db)) { GURL::Replacements replace_scheme; replace_scheme.SetSchemeStr(scheme_in_db); return url.ReplaceComponents(replace_scheme); } // Check if appending "www." to the canonicalized URL generates a URL found in // the database. const std::string alternative_host = "www." + host; if (!base::StartsWith(host, "www.", base::CompareCase::INSENSITIVE_ASCII) && db->IsTypedHost(alternative_host, &scheme_in_db)) { GURL::Replacements replace_scheme_and_host; replace_scheme_and_host.SetHostStr(alternative_host); replace_scheme_and_host.SetSchemeStr(scheme_in_db); return url.ReplaceComponents(replace_scheme_and_host); } return GURL(); } bool HistoryURLProvider::PromoteOrCreateShorterSuggestion( history::URLDatabase* db, HistoryURLProviderParams* params) { if (params->matches.empty()) return false; // No matches, nothing to do. // Determine the base URL from which to search, and whether that URL could // itself be added as a match. We can add the base iff it's not "effectively // the same" as any "what you typed" match. const history::HistoryMatch& match = params->matches[0]; GURL search_base = ConvertToHostOnly(match, params->input.text()); bool can_add_search_base_to_matches = !params->have_what_you_typed_match; if (!search_base.is_valid()) { // Search from what the user typed when we couldn't reduce the best match // to a host. Careful: use a substring of `match` here, rather than the // first match in `params`, because they might have different prefixes. If // the user typed "google.com", params->what_you_typed_match will hold // "http://google.com/", but `match` might begin with // "http://www.google.com/". // TODO: this should be cleaned up, and is probably incorrect for IDN. std::string new_match = match.url_info.url().possibly_invalid_spec().substr( 0, match.input_location + params->input.text().length()); search_base = GURL(new_match); if (!search_base.is_valid()) { return false; // Can't construct a URL from which to start a search. } } else if (!can_add_search_base_to_matches) { can_add_search_base_to_matches = (search_base != params->what_you_typed_match.destination_url); } if (search_base == match.url_info.url()) return false; // Couldn't shorten `match`, so no URLs to search over. // Search the DB for short URLs between our base and `match`. history::URLRow info(search_base); bool promote = true; // A short URL is only worth suggesting if it's been visited at least a third // as often as the longer URL. const int min_visit_count = ((match.url_info.visit_count() - 1) / 3) + 1; // For stability between the in-memory and on-disk autocomplete passes, when // the long URL has been typed before, only suggest shorter URLs that have // also been typed. Otherwise, the on-disk pass could suggest a shorter URL // (which hasn't been typed) that the in-memory pass doesn't know about, // thereby making the top match, and thus the behavior of inline // autocomplete, unstable. const int min_typed_count = match.url_info.typed_count() ? 1 : 0; if (!db->FindShortestURLFromBase(search_base.possibly_invalid_spec(), match.url_info.url().possibly_invalid_spec(), min_visit_count, min_typed_count, can_add_search_base_to_matches, &info)) { if (!can_add_search_base_to_matches) return false; // Couldn't find anything and can't add the search base. // Try to get info on the search base itself. Promote it to the top if the // original best match isn't good enough to autocomplete. db->GetRowForURL(search_base, &info); promote = match.url_info.typed_count() <= 1; } // Promote or add the desired URL to the list of matches. const bool ensure_can_inline = promote && CanPromoteMatchForInlineAutocomplete(match); CreateAndPromoteMatch(info, match, ¶ms->matches, promote); return ensure_can_inline; } void HistoryURLProvider::CullPoorMatches( HistoryURLProviderParams* params) const { const base::Time& threshold(history::AutocompleteAgeThreshold()); for (history::HistoryMatches::iterator i(params->matches.begin()); i != params->matches.end();) { if (RowQualifiesAsSignificant(i->url_info, threshold) && (!params->default_search_provider || !params->default_search_provider->IsSearchURL( i->url_info.url(), *params->search_terms_data))) { ++i; } else { i = params->matches.erase(i); } } } void HistoryURLProvider::CullRedirects(history::HistoryBackend* backend, history::HistoryMatches* matches, size_t max_results) const { for (size_t source = 0; (source < matches->size()) && (source < max_results);) { const GURL& url = (*matches)[source].url_info.url(); // TODO(brettw) this should go away when everything uses GURL. history::RedirectList redirects = backend->QueryRedirectsFrom(url); if (!redirects.empty()) { // Remove all but the first occurrence of these redirects in the search // results. We also must add the URL we queried for, since it may not be // the first match and we'd want to remove it. // // For example, when A redirects to B and our matches are [A, X, B], // we'll get B as the redirects from, and we want to remove the second // item of that pair, removing B. If A redirects to B and our matches are // [B, X, A], we'll want to remove A instead. redirects.push_back(url); source = RemoveSubsequentMatchesOf(matches, source, redirects); } else { // Advance to next item. source++; } } if (matches->size() > max_results) matches->resize(max_results); } size_t HistoryURLProvider::RemoveSubsequentMatchesOf( history::HistoryMatches* matches, size_t source_index, const std::vector& remove) const { size_t next_index = source_index + 1; // return value = item after source // Find the first occurrence of any URL in the redirect chain. We want to // keep this one since it is rated the highest. history::HistoryMatches::iterator first(std::ranges::find_first_of( *matches, remove, history::HistoryMatch::EqualsGURL)); CHECK(first != matches->end()) << "We should have always found at least the " "original URL."; // Find any following occurrences of any URL in the redirect chain, these // should be deleted. for (history::HistoryMatches::iterator next( std::find_first_of(first + 1, matches->end(), remove.begin(), remove.end(), history::HistoryMatch::EqualsGURL)); next != matches->end(); next = std::find_first_of(next, matches->end(), remove.begin(), remove.end(), history::HistoryMatch::EqualsGURL)) { // Remove this item. When we remove an item before the source index, we // need to shift it to the right and remember that so we can return it. next = matches->erase(next); if (static_cast(next - matches->begin()) < next_index) --next_index; } return next_index; } AutocompleteMatch HistoryURLProvider::HistoryMatchToACMatch( const HistoryURLProviderParams& params, size_t match_number, int relevance, bool populate_scoring_signals) { // The FormattedStringWithEquivalentMeaning() call below requires callers to // be on the main thread. DCHECK(thread_checker_.CalledOnValidThread()); const history::HistoryMatch& history_match = params.matches[match_number]; const history::URLRow& info = history_match.url_info; bool deletable = !!info.visit_count() && client()->AllowDeletingBrowserHistory(); AutocompleteMatch match(this, relevance, deletable, AutocompleteMatchType::HISTORY_URL); match.typed_count = info.typed_count(); match.destination_url = info.url(); DCHECK(match.destination_url.is_valid()); size_t inline_autocomplete_offset = history_match.input_location + params.input.text().length(); auto fill_into_edit_format_types = url_formatter::kFormatUrlOmitDefaults; if (!params.trim_http || history_match.match_in_scheme) fill_into_edit_format_types &= ~url_formatter::kFormatUrlOmitHTTP; match.fill_into_edit = AutocompleteInput::FormattedStringWithEquivalentMeaning( info.url(), url_formatter::FormatUrl(info.url(), fill_into_edit_format_types, base::UnescapeRule::SPACES, nullptr, nullptr, &inline_autocomplete_offset), client()->GetSchemeClassifier(), &inline_autocomplete_offset); const auto format_types = AutocompleteMatch::GetFormatTypes( params.input.parts().scheme.is_nonempty() || !params.trim_http || history_match.match_in_scheme, history_match.match_in_subdomain); match.contents = url_formatter::FormatUrl(info.url(), format_types, base::UnescapeRule::SPACES, nullptr, nullptr, nullptr); auto term_matches = FindTermMatches(params.input.text(), match.contents); match.contents_class = ClassifyTermMatches( term_matches, match.contents.size(), ACMatchClassification::URL | ACMatchClassification::MATCH, ACMatchClassification::URL); match.description = AutocompleteMatch::SanitizeString(info.title()); match.description_class = ClassifyDescription(params.input.text(), match.description); // `inline_autocomplete_offset` was guaranteed not to be npos before the call // to FormatUrl(). If it is npos now, that means the represented location no // longer exists as such in the formatted string, e.g. if the offset pointed // into the middle of a punycode sequence fixed up to Unicode. In this case, // there can be no inline autocompletion, and the match must not be allowed to // be default. if (match.TryRichAutocompletion(params.input_before_fixup, match.contents, match.description)) { // If rich autocompletion applies, we skip trying the alternatives below. } else if (inline_autocomplete_offset != std::u16string::npos) { DCHECK(inline_autocomplete_offset <= match.fill_into_edit.length()); match.inline_autocompletion = match.fill_into_edit.substr(inline_autocomplete_offset); match.SetAllowedToBeDefault(params.input_before_fixup); } if (params.input.in_keyword_mode()) { match.from_keyword = true; } // If the input was in a starter pack keyword scope, set the `keyword` and // `transition` appropriately to avoid popping the user out of keyword mode. if (params.starter_pack_engine) { match.keyword = params.starter_pack_engine->keyword(); match.transition = ui::PAGE_TRANSITION_KEYWORD; } RecordAdditionalInfoFromUrlRow(info, &match); // Populate ML scoring signals when appropriate. if (populate_scoring_signals && match.IsMlSignalLoggingEligible()) { match.scoring_signals = std::make_optional(); match.scoring_signals->set_typed_count(info.typed_count()); match.scoring_signals->set_visit_count(info.visit_count()); match.scoring_signals->set_elapsed_time_last_visit_secs( (base::Time::Now() - info.last_visit()).InSeconds()); match.scoring_signals->set_allowed_to_be_default_match( match.allowed_to_be_default_match); match.scoring_signals->set_length_of_url(info.url().spec().length()); match.scoring_signals->set_is_host_only(history_match.IsHostOnly()); match.scoring_signals->set_has_non_scheme_www_match( history_match.innermost_match); } return match; }