url_pattern_index.cc | Explore in Territory

// Copyright 2017 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/url_pattern_index/url_pattern_index.h"

#include <limits>
#include <string>
#include <string_view>
#include <utility>

#include "base/check_op.h"
#include "base/containers/contains.h"
#include "base/containers/flat_map.h"
#include "base/functional/callback.h"
#include "base/memory/raw_ref.h"
#include "base/no_destructor.h"
#include "base/not_fatal_until.h"
#include "base/notreached.h"
#include "base/numerics/safe_conversions.h"
#include "base/ranges/algorithm.h"
#include "base/strings/string_util.h"
#include "base/trace_event/trace_event.h"
#include "components/url_pattern_index/ngram_extractor.h"
#include "components/url_pattern_index/url_pattern.h"
#include "components/url_pattern_index/url_rule_util.h"
#include "url/gurl.h"
#include "url/origin.h"
#include "url/url_constants.h"
#include "url/url_util.h"

namespace url_pattern_index {

namespace {

FlatUrlRuleList;

ActivationTypeMap;
ElementTypeMap;

// Maps proto::ActivationType to flat::ActivationType.
const ActivationTypeMap& GetActivationTypeMap() { … }

// Maps proto::ElementType to flat::ElementType.
const ElementTypeMap& GetElementTypeMap() { … }

flat::ActivationType ProtoToFlatActivationType(proto::ActivationType type) { … }

flat::ElementType ProtoToFlatElementType(proto::ElementType type) { … }

std::string_view ToStringPiece(const flatbuffers::String* string) { … }

bool HasNoUpperAscii(std::string_view string) { … }

// Comparator to sort UrlRule. Sorts rules by descending order of rule priority.
bool UrlRuleDescendingPriorityComparator(const flat::UrlRule* lhs,
                                         const flat::UrlRule* rhs) { … }

// Returns a bitmask of all the keys of the |map| passed.
template <typename T>
int GetKeysMask(const T& map) { … }

// Checks whether a URL |rule| can be converted to its FlatBuffers equivalent,
// and performs the actual conversion.
class UrlRuleFlatBufferConverter { … };

}  // namespace

// Helpers. --------------------------------------------------------------------

bool OffsetVectorCompare::operator()(
    const std::vector<FlatStringOffset>& a,
    const std::vector<FlatStringOffset>& b) const { … }

UrlRuleOffset SerializeUrlRule(const proto::UrlRule& rule,
                               flatbuffers::FlatBufferBuilder* builder,
                               FlatDomainMap* domain_map) { … }

int CompareDomains(std::string_view lhs_domain, std::string_view rhs_domain) { … }

// UrlPatternIndexBuilder ------------------------------------------------------

UrlPatternIndexBuilder::UrlPatternIndexBuilder(
    flatbuffers::FlatBufferBuilder* flat_builder)
    : … { … }

UrlPatternIndexBuilder::~UrlPatternIndexBuilder() = default;

void UrlPatternIndexBuilder::IndexUrlRule(UrlRuleOffset offset) { … }

UrlPatternIndexOffset UrlPatternIndexBuilder::Finish() { … }

NGram UrlPatternIndexBuilder::GetMostDistinctiveNGram(
    std::string_view pattern) { … }

// UrlPatternIndex -------------------------------------------------------------

namespace {

FlatNGramIndex;

// Returns the size of the longest (sub-)domain of `host` matching one of the
// `domains` in the list.
//
// The `domains` should be sorted in descending order of their length, and
// ascending alphabetical order within the groups of same-length domains.
size_t GetLongestMatchingSubdomain(std::string_view host,
                                   const FlatDomains& domains) { … }

// |sorted_candidates| is sorted in descending order by priority. If
// |matched_rules| is specified, then all rule matches in |sorted_candidates|
// will be added to |matched_rules| and null is returned. If |matched_rules| is
// not specified, then this returns the first matching rule i.e. the rule with
// the highest priority in |sorted_candidates| or null if no rule matches.
const flat::UrlRule* FindMatchAmongCandidates(
    const FlatUrlRuleList* sorted_candidates,
    const UrlPattern::UrlInfo& url,
    const url::Origin& document_origin,
    flat::ElementType element_type,
    flat::ActivationType activation_type,
    flat::RequestMethod request_method,
    bool is_third_party,
    bool disable_generic_rules,
    const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
        embedder_conditions_matcher,
    std::vector<const flat::UrlRule*>* matched_rules,
    const base::flat_set<int>& disabled_rule_ids) { … }

// Returns whether the network request matches a UrlPattern |index| represented
// in its FlatBuffers format. |is_third_party| should reflect the relation
// between |url| and |document_origin|. If |strategy| is kAll, then
// |matched_rules| will be populated with all matching UrlRules and nullptr is
// returned.
const flat::UrlRule* FindMatchInFlatUrlPatternIndex(
    const flat::UrlPatternIndex& index,
    const UrlPattern::UrlInfo& url,
    const url::Origin& document_origin,
    flat::ElementType element_type,
    flat::ActivationType activation_type,
    flat::RequestMethod request_method,
    bool is_third_party,
    bool disable_generic_rules,
    const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
        embedder_conditions_matcher,
    UrlPatternIndexMatcher::FindRuleStrategy strategy,
    std::vector<const flat::UrlRule*>* matched_rules,
    const base::flat_set<int>& disabled_rule_ids) { … }

}  // namespace

bool IsRuleGeneric(const flat::UrlRule& rule) { … }

// Returns whether the `host` matches the domain conditions. It's considered a
// match if both:
//  1. An included domain matches the `host`, or `domains_included` is omitted
//     entirely (since rules match all domains by default).
//  2. No excluded domain match the `host`, or the longest matching excluded
//     domain is shorter than the longest matching included domain (since
//     longer, more specific domain matches take precedence).
bool DoesHostMatchDomainLists(
    std::string_view host,
    const flatbuffers::Vector<flatbuffers::Offset<flatbuffers::String>>*
        domains_included,
    const flatbuffers::Vector<flatbuffers::Offset<flatbuffers::String>>*
        domains_excluded) { … }

bool DoesURLMatchRequestDomainList(const UrlPattern::UrlInfo& url,
                                   const flat::UrlRule& rule) { … }

bool DoesOriginMatchInitiatorDomainList(const url::Origin& origin,
                                        const flat::UrlRule& rule) { … }

bool DoesRuleFlagsMatch(const flat::UrlRule& rule,
                        flat::ElementType element_type,
                        flat::ActivationType activation_type,
                        flat::RequestMethod request_method,
                        bool is_third_party,
                        const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
                            embedder_conditions_matcher) { … }

UrlPatternIndexMatcher::UrlPatternIndexMatcher(
    const flat::UrlPatternIndex* flat_index)
    : … { … }

UrlPatternIndexMatcher::~UrlPatternIndexMatcher() = default;
UrlPatternIndexMatcher::UrlPatternIndexMatcher(UrlPatternIndexMatcher&&) =
    default;
UrlPatternIndexMatcher& UrlPatternIndexMatcher::operator=(
    UrlPatternIndexMatcher&&) = default;

size_t UrlPatternIndexMatcher::GetRulesCount() const { … }

const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
    const GURL& url,
    const url::Origin& first_party_origin,
    proto::ElementType element_type,
    proto::ActivationType activation_type,
    bool is_third_party,
    bool disable_generic_rules,
    const EmbedderConditionsMatcher& embedder_conditions_matcher,
    FindRuleStrategy strategy,
    const base::flat_set<int>& disabled_rule_ids) const { … }

const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
    const GURL& url,
    const url::Origin& first_party_origin,
    flat::ElementType element_type,
    flat::ActivationType activation_type,
    flat::RequestMethod request_method,
    bool is_third_party,
    bool disable_generic_rules,
    const EmbedderConditionsMatcher& embedder_conditions_matcher,
    FindRuleStrategy strategy,
    const base::flat_set<int>& disabled_rule_ids) const { … }

std::vector<const flat::UrlRule*> UrlPatternIndexMatcher::FindAllMatches(
    const GURL& url,
    const url::Origin& first_party_origin,
    proto::ElementType element_type,
    proto::ActivationType activation_type,
    bool is_third_party,
    bool disable_generic_rules,
    const EmbedderConditionsMatcher& embedder_conditions_matcher,
    const base::flat_set<int>& disabled_rule_ids) const { … }

std::vector<const flat::UrlRule*> UrlPatternIndexMatcher::FindAllMatches(
    const GURL& url,
    const url::Origin& first_party_origin,
    flat::ElementType element_type,
    flat::ActivationType activation_type,
    flat::RequestMethod request_method,
    bool is_third_party,
    bool disable_generic_rules,
    const EmbedderConditionsMatcher& embedder_conditions_matcher,
    const base::flat_set<int>& disabled_rule_ids) const { … }

}  // namespace url_pattern_index
chromium/components/url_pattern_index/url_pattern_index.cc
