blob: 961c74491376d7d10de992e2ccf39c71b9734b02 [file] [log] [blame]
// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <stddef.h>
#include <memory>
#include <set>
#include <vector>
#include "base/macros.h"
#include "base/memory/ref_counted.h"
#include "components/url_matcher/regex_set_matcher.h"
#include "components/url_matcher/substring_set_matcher.h"
#include "components/url_matcher/url_matcher_export.h"
class GURL;
namespace url_matcher {
// This class represents a single URL matching condition, e.g. a match on the
// host suffix or the containment of a string in the query component of a GURL.
// The difference from a simple StringPattern is that this also supports
// checking whether the {Host, Path, Query} of a URL contains a string. The
// reduction of URL matching conditions to StringPatterns conducted by
// URLMatcherConditionFactory is not capable of expressing that alone.
// Also supported is matching regular expressions against the URL (URL_MATCHES).
class URL_MATCHER_EXPORT URLMatcherCondition {
enum Criterion {
ORIGIN_AND_PATH_MATCHES, // Matches the URL minus its query string.
URLMatcherCondition(Criterion criterion,
const StringPattern* substring_pattern);
URLMatcherCondition(const URLMatcherCondition& rhs);
URLMatcherCondition& operator=(const URLMatcherCondition& rhs);
bool operator<(const URLMatcherCondition& rhs) const;
Criterion criterion() const { return criterion_; }
const StringPattern* string_pattern() const {
return string_pattern_;
// Returns whether this URLMatcherCondition needs to be executed on a
// full URL rather than the individual components (see
// URLMatcherConditionFactory).
bool IsFullURLCondition() const;
// Returns whether this URLMatcherCondition is a regular expression to be
// handled by a regex matcher instead of a substring matcher.
bool IsRegexCondition() const;
// Returns whether this URLMatcherCondition is a regular expression that shall
// be evaluated on the URL without the query parameter.
bool IsOriginAndPathRegexCondition() const;
// Returns whether this condition is fulfilled according to
// |matching_patterns| and |url|.
bool IsMatch(const std::set<StringPattern::ID>& matching_patterns,
const GURL& url) const;
// |criterion_| and |string_pattern_| describe together what property a URL
// needs to fulfill to be considered a match.
Criterion criterion_;
// This is the StringPattern that is used in a SubstringSetMatcher.
const StringPattern* string_pattern_;
// Class to map the problem of finding {host, path, query} {prefixes, suffixes,
// containments, and equality} in GURLs to the substring matching problem.
// Say, you want to check whether the path of a URL starts with "/index.html".
// This class preprocesses a URL like "" into something
// like "|/index.html". After preprocessing, you can search for
// "|/index.html" in the string and see that this candidate URL actually has
// a path that starts with "/index.html". On the contrary,
// "" would be normalized to
// "|/images/index.html". It is easy to see that it contains
// "/index.html" but the path of the URL does not start with "/index.html".
// This preprocessing is important if you want to match a URL against many
// patterns because it reduces the matching to a "discover all substrings
// of a dictionary in a text" problem, which can be solved very efficiently
// by the Aho-Corasick algorithm.
// IMPORTANT: The URLMatcherConditionFactory owns the StringPattern
// referenced by created URLMatcherConditions. Therefore, it must outlive
// all created URLMatcherCondition and the SubstringSetMatcher.
class URL_MATCHER_EXPORT URLMatcherConditionFactory {
// Canonicalizes a URL for "Create{Host,Path,Query}*Condition" searches.
std::string CanonicalizeURLForComponentSearches(const GURL& url) const;
// Factory methods for various condition types.
// Note that these methods fill the pattern_singletons_. If you create
// conditions and don't register them to a URLMatcher, they will continue to
// consume memory. You need to call ForgetUnusedPatterns() or
// URLMatcher::ClearUnusedConditionSets() in this case.
URLMatcherCondition CreateHostPrefixCondition(const std::string& prefix);
URLMatcherCondition CreateHostSuffixCondition(const std::string& suffix);
URLMatcherCondition CreateHostContainsCondition(const std::string& str);
URLMatcherCondition CreateHostEqualsCondition(const std::string& str);
URLMatcherCondition CreatePathPrefixCondition(const std::string& prefix);
URLMatcherCondition CreatePathSuffixCondition(const std::string& suffix);
URLMatcherCondition CreatePathContainsCondition(const std::string& str);
URLMatcherCondition CreatePathEqualsCondition(const std::string& str);
URLMatcherCondition CreateQueryPrefixCondition(const std::string& prefix);
URLMatcherCondition CreateQuerySuffixCondition(const std::string& suffix);
URLMatcherCondition CreateQueryContainsCondition(const std::string& str);
URLMatcherCondition CreateQueryEqualsCondition(const std::string& str);
// This covers the common case, where you don't care whether a domain
// "" is expressed as "" or "", and it
// should be followed by a given |path_prefix|.
URLMatcherCondition CreateHostSuffixPathPrefixCondition(
const std::string& host_suffix,
const std::string& path_prefix);
URLMatcherCondition CreateHostEqualsPathPrefixCondition(
const std::string& host,
const std::string& path_prefix);
// Canonicalizes a URL for "CreateURL*Condition" searches.
std::string CanonicalizeURLForFullSearches(const GURL& url) const;
// Canonicalizes a URL for "CreateURLMatchesCondition" searches.
std::string CanonicalizeURLForRegexSearches(const GURL& url) const;
// Canonicalizes a URL for "CreateOriginAndPathMatchesCondition" searches.
std::string CanonicalizeURLForOriginAndPathRegexSearches(
const GURL& url) const;
URLMatcherCondition CreateURLPrefixCondition(const std::string& prefix);
URLMatcherCondition CreateURLSuffixCondition(const std::string& suffix);
URLMatcherCondition CreateURLContainsCondition(const std::string& str);
URLMatcherCondition CreateURLEqualsCondition(const std::string& str);
URLMatcherCondition CreateURLMatchesCondition(const std::string& regex);
URLMatcherCondition CreateOriginAndPathMatchesCondition(
const std::string& regex);
// Removes all patterns from |pattern_singletons_| that are not listed in
// |used_patterns|. These patterns are not referenced any more and get
// freed.
void ForgetUnusedPatterns(
const std::set<StringPattern::ID>& used_patterns);
// Returns true if this object retains no allocated data. Only for debugging.
bool IsEmpty() const;
// Creates a URLMatcherCondition according to the parameters passed.
// The URLMatcherCondition will refer to a StringPattern that is
// owned by |pattern_singletons_|.
URLMatcherCondition CreateCondition(URLMatcherCondition::Criterion criterion,
const std::string& pattern);
// Prepends a "." to the prefix if it does not start with one.
std::string CanonicalizeHostPrefix(const std::string& prefix) const;
// Appends a "." to the hostname if it does not start with one.
std::string CanonicalizeHostSuffix(const std::string& suffix) const;
// Adds "." to either side of the hostname if not present yet.
std::string CanonicalizeHostname(const std::string& hostname) const;
// Convert the query string to canonical form suitable for key token search.
std::string CanonicalizeQuery(std::string query,
bool prepend_beginning_of_query_component,
bool append_end_of_query_component) const;
// Counter that ensures that all created StringPatterns have unique IDs.
// Note that substring patterns and regex patterns will use different IDs.
int id_counter_;
// This comparison considers only the pattern() value of the
// StringPatterns.
struct StringPatternPointerCompare {
bool operator()(StringPattern* lhs, StringPattern* rhs) const;
// Set to ensure that we generate only one StringPattern for each content
// of StringPattern::pattern().
using PatternSingletons = std::map<StringPattern*,
PatternSingletons substring_pattern_singletons_;
PatternSingletons regex_pattern_singletons_;
PatternSingletons origin_and_path_regex_pattern_singletons_;
// This class represents a single URL query matching condition. The query
// matching is done as a search for a key and optionally a value.
// The matching makes use of CanonicalizeURLForComponentSearches to ensure that
// the key starts and ends (optionally) with the right marker.
class URL_MATCHER_EXPORT URLQueryElementMatcherCondition {
// Multiple occurrences of the same key can happen in a URL query. The type
// ensures that every (MATCH_ALL), any (MATCH_ANY), first (MATCH_FIRST) or
// last (MATCH_LAST) instance of the key occurrence matches the value.
// Allows the match to be exact (QUERY_VALUE_MATCH_EXACT, starts and ends with
// a delimiter or a border) or simply a prefix (QUERY_VALUE_MATCH_PREFIX,
// starts with a delimiter or a border).
enum QueryValueMatchType {
// Used to indicate if the query parameter is of type &key=value&
URLQueryElementMatcherCondition(const std::string& key,
const std::string& value,
QueryValueMatchType query_value_match_type,
QueryElementType query_element_type,
Type match_type,
URLMatcherConditionFactory* factory);
URLQueryElementMatcherCondition(const URLQueryElementMatcherCondition& other);
bool operator<(const URLQueryElementMatcherCondition& rhs) const;
// Returns whether the URL query satisfies the key value constraint.
bool IsMatch(const std::string& canonical_url_query) const;
const StringPattern* string_pattern() const { return string_pattern_; }
Type match_type_;
std::string key_;
std::string value_;
size_t key_length_;
size_t value_length_;
const StringPattern* string_pattern_;
// This class represents a filter for the URL scheme to be hooked up into a
// URLMatcherConditionSet.
class URL_MATCHER_EXPORT URLMatcherSchemeFilter {
explicit URLMatcherSchemeFilter(const std::string& filter);
explicit URLMatcherSchemeFilter(const std::vector<std::string>& filters);
bool IsMatch(const GURL& url) const;
std::vector<std::string> filters_;
// This class represents a filter for port numbers to be hooked up into a
// URLMatcherConditionSet.
class URL_MATCHER_EXPORT URLMatcherPortFilter {
// Boundaries of a port range (both ends are included).
typedef std::pair<int, int> Range;
explicit URLMatcherPortFilter(const std::vector<Range>& ranges);
bool IsMatch(const GURL& url) const;
// Creates a port range [from, to]; both ends are included.
static Range CreateRange(int from, int to);
// Creates a port range containing a single port.
static Range CreateRange(int port);
std::vector<Range> ranges_;
// This class represents a set of conditions that all need to match on a
// given URL in order to be considered a match.
class URL_MATCHER_EXPORT URLMatcherConditionSet
: public base::RefCounted<URLMatcherConditionSet> {
// Valid IDs will be >= 0.
typedef int ID;
typedef std::set<URLMatcherCondition> Conditions;
typedef std::set<URLQueryElementMatcherCondition> QueryConditions;
typedef std::vector<scoped_refptr<URLMatcherConditionSet> > Vector;
// Matches if all conditions in |conditions| are fulfilled.
URLMatcherConditionSet(ID id, const Conditions& conditions);
// Matches if all conditions in |conditions|, |scheme_filter| and
// |port_filter| are fulfilled. |scheme_filter| and |port_filter| may be NULL,
// in which case, no restrictions are imposed on the scheme/port of a URL.
URLMatcherConditionSet(ID id,
const Conditions& conditions,
std::unique_ptr<URLMatcherSchemeFilter> scheme_filter,
std::unique_ptr<URLMatcherPortFilter> port_filter);
// Matches if all conditions in |conditions|, |query_conditions|,
// |scheme_filter| and |port_filter| are fulfilled. |scheme_filter| and
// |port_filter| may be NULL, in which case, no restrictions are imposed on
// the scheme/port of a URL.
URLMatcherConditionSet(ID id,
const Conditions& conditions,
const QueryConditions& query_conditions,
std::unique_ptr<URLMatcherSchemeFilter> scheme_filter,
std::unique_ptr<URLMatcherPortFilter> port_filter);
ID id() const { return id_; }
const Conditions& conditions() const { return conditions_; }
const QueryConditions& query_conditions() const { return query_conditions_; }
bool IsMatch(const std::set<StringPattern::ID>& matching_patterns,
const GURL& url) const;
bool IsMatch(const std::set<StringPattern::ID>& matching_patterns,
const GURL& url,
const std::string& url_for_component_searches) const;
friend class base::RefCounted<URLMatcherConditionSet>;
ID id_;
Conditions conditions_;
QueryConditions query_conditions_;
std::unique_ptr<URLMatcherSchemeFilter> scheme_filter_;
std::unique_ptr<URLMatcherPortFilter> port_filter_;
// This class allows matching one URL against a large set of
// URLMatcherConditionSets at the same time.
// Adds new URLMatcherConditionSet to this URL Matcher. Each condition set
// must have a unique ID.
// This is an expensive operation as it triggers pre-calculations on the
// currently registered condition sets. Do not call this operation many
// times with a single condition set in each call.
void AddConditionSets(const URLMatcherConditionSet::Vector& condition_sets);
// Removes the listed condition sets. All |condition_set_ids| must be
// currently registered. This function should be called with large batches
// of |condition_set_ids| at a time to improve performance.
void RemoveConditionSets(
const std::vector<URLMatcherConditionSet::ID>& condition_set_ids);
// Removes all unused condition sets from the ConditionFactory.
void ClearUnusedConditionSets();
// Returns the IDs of all URLMatcherConditionSet that match to this |url|.
std::set<URLMatcherConditionSet::ID> MatchURL(const GURL& url) const;
// Returns the URLMatcherConditionFactory that must be used to create
// URLMatcherConditionSets for this URLMatcher.
URLMatcherConditionFactory* condition_factory() {
return &condition_factory_;
// Returns true if this object retains no allocated data. Only for debugging.
bool IsEmpty() const;
void UpdateSubstringSetMatcher(bool full_url_conditions);
void UpdateRegexSetMatcher();
void UpdateTriggers();
void UpdateConditionFactory();
void UpdateInternalDatastructures();
URLMatcherConditionFactory condition_factory_;
// Maps the ID of a URLMatcherConditionSet to the respective
// URLMatcherConditionSet.
typedef std::map<URLMatcherConditionSet::ID,
scoped_refptr<URLMatcherConditionSet> >
URLMatcherConditionSets url_matcher_condition_sets_;
// Maps a StringPattern ID to the URLMatcherConditions that need to
// be triggered in case of a StringPattern match.
typedef std::map<StringPattern::ID, std::set<URLMatcherConditionSet::ID> >
StringPatternTriggers substring_match_triggers_;
SubstringSetMatcher full_url_matcher_;
SubstringSetMatcher url_component_matcher_;
RegexSetMatcher regex_set_matcher_;
RegexSetMatcher origin_and_path_regex_set_matcher_;
std::set<const StringPattern*> registered_full_url_patterns_;
std::set<const StringPattern*> registered_url_component_patterns_;
} // namespace url_matcher