history_fuzzy_provider.cc | Explore in Territory

// Copyright 2022 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_fuzzy_provider.h"

#include <functional>
#include <memory>
#include <ostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include "base/check.h"
#include "base/containers/contains.h"
#include "base/memory/raw_ptr.h"
#include "base/memory/scoped_refptr.h"
#include "base/metrics/histogram_functions.h"
#include "base/metrics/histogram_macros.h"
#include "base/not_fatal_until.h"
#include "base/strings/utf_string_conversions.h"
#include "base/system/sys_info.h"
#include "base/time/time.h"
#include "base/trace_event/memory_usage_estimator.h"
#include "base/trace_event/trace_event.h"
#include "build/build_config.h"
#include "components/history/core/browser/history_database.h"
#include "components/history/core/browser/history_db_task.h"
#include "components/history/core/browser/history_service.h"
#include "components/history/core/browser/url_database.h"
#include "components/omnibox/browser/autocomplete_match_classification.h"
#include "components/omnibox/browser/autocomplete_match_type.h"
#include "components/omnibox/browser/autocomplete_provider_client.h"
#include "components/omnibox/browser/bookmark_provider.h"
#include "components/omnibox/browser/history_quick_provider.h"
#include "components/omnibox/browser/omnibox_field_trial.h"
#include "components/omnibox/browser/omnibox_triggered_feature_service.h"
#include "components/url_formatter/elide_url.h"
#include "third_party/metrics_proto/omnibox_event.pb.h"
#include "third_party/metrics_proto/omnibox_focus_type.pb.h"
#include "url/gurl.h"

namespace {

// Histogram names for measuring sub-provider match conversion efficacy.
// Reminder in case other sub-providers or metrics are added: update
// the `Omnibox.HistoryFuzzy.MatchConversion` entry in histograms.xml.
const char kMetricMatchConversionHistoryQuick[] = …;
const char kMetricMatchConversionBookmark[] = …;

// Histogram name for time spent on the fuzzy search portion of provider time.
const char kMetricSearchDuration[] = …;

// Histogram name for whether a presented fuzzy match was the one taken by the
// user at the moment a match was opened.
const char kMetricPrecision[] = …;

// This cap ensures the search trie will not grow without bound. Up to half
// the total capacity may be filled at startup from loaded significant URLs.
// The enforced limit may be further constrained by
// `MaxNumHQPUrlsIndexedAtStartup`.
constexpr int kMaxTerminalCount = …;

// This utility function reduces a URL to the most meaningful and likely part
// of the hostname to be matched against, i.e. the domain, the URL's TLD+1.
// May return an empty string if the given URL is not a good candidate for
// meaningful domain name matching.
std::u16string UrlDomainReduction(const GURL& url) { … }

// This utility function prepares input text for fuzzy matching, or returns
// an empty string in cases unlikely to be worth a fuzzy matching search.
// Note, this is intended to be a fast way to improve matching and eliminate
// likely-unfruitful searches. It could make use of `SplitHost` as above, or
// `url_formatter::FormatUrlForDisplayOmitSchemePathAndTrivialSubdomains`,
// which uses `FormatUrlWithAdjustments` under the hood, but all that URL
// processing for input text that may not even be a URL seems like overkill,
// so this simple direct method is used instead.
std::u16string ReduceInputTextForMatching(const std::u16string& input) { … }

}  // namespace

namespace fuzzy {

Edit::Edit(Kind kind, size_t at, char16_t new_char)
    : … { … }

void Edit::ApplyTo(std::u16string& text) const { … }

Correction Correction::WithEdit(Edit edit) const { … }

void Correction::ApplyTo(std::u16string& text) const { … }

Node::Node() = default;

Node::Node(Node&&) = default;

Node::~Node() = default;

void Node::Insert(const std::u16string& text, size_t text_index) { … }

void Node::Delete(const std::u16string& text, size_t text_index) { … }

void Node::Clear() { … }

bool Node::FindCorrections(const std::u16string& text,
                           ToleranceSchedule tolerance_schedule,
                           std::vector<Correction>& corrections) const { … }

size_t Node::EstimateMemoryUsage() const { … }

int Node::TerminalCount() const { … }

// This task class loads URLs considered significant according to
// `HistoryDatabase::InitURLEnumeratorForSignificant` but there's nothing
// special about that implementation; we may do something different for
// fuzzy matching. The goal in general is to load and keep a reasonably sized
// set of likely relevant host names for fast fuzzy correction.
class LoadSignificantUrls : public history::HistoryDBTask { … };

}  // namespace fuzzy

// static
void HistoryFuzzyProvider::RecordOpenMatchMetrics(
    const AutocompleteResult& result,
    const AutocompleteMatch& match_opened) { … }

HistoryFuzzyProvider::HistoryFuzzyProvider(AutocompleteProviderClient* client)
    : … { … }

void HistoryFuzzyProvider::Start(const AutocompleteInput& input,
                                 bool minimal_changes) { … }

size_t HistoryFuzzyProvider::EstimateMemoryUsage() const { … }

HistoryFuzzyProvider::~HistoryFuzzyProvider() = default;

void HistoryFuzzyProvider::DoAutocomplete() { … }

int HistoryFuzzyProvider::AddConvertedMatches(const ACMatches& matches,
                                              int penalty) { … }

void HistoryFuzzyProvider::OnUrlsLoaded(fuzzy::Node node) { … }

void HistoryFuzzyProvider::OnURLVisited(
    history::HistoryService* history_service,
    const history::URLRow& url_row,
    const history::VisitRow& new_visit) { … }

void HistoryFuzzyProvider::OnHistoryDeletions(
    history::HistoryService* history_service,
    const history::DeletionInfo& deletion_info) { … }

void HistoryFuzzyProvider::RecordMatchConversion(const char* name, int count) { … }
chromium/components/omnibox/browser/history_fuzzy_provider.cc
