url_matcher.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451
  1. // Copyright 2013 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_URL_MATCHER_URL_MATCHER_H_
  5. #define COMPONENTS_URL_MATCHER_URL_MATCHER_H_
  6. #include <stddef.h>
  7. #include <memory>
  8. #include <set>
  9. #include <vector>
  10. #include "base/memory/raw_ptr.h"
  11. #include "base/memory/ref_counted.h"
  12. #include "base/substring_set_matcher/substring_set_matcher.h"
  13. #include "components/url_matcher/regex_set_matcher.h"
  14. #include "components/url_matcher/url_matcher_export.h"
  15. class GURL;
  16. namespace url_matcher {
  17. // This class represents a single URL matching condition, e.g. a match on the
  18. // host suffix or the containment of a string in the query component of a GURL.
  19. //
  20. // The difference from a simple MatcherStringPattern is that this also supports
  21. // checking whether the {Host, Path, Query} of a URL contains a string. The
  22. // reduction of URL matching conditions to MatcherStringPatterns conducted by
  23. // URLMatcherConditionFactory is not capable of expressing that alone.
  24. //
  25. // Also supported is matching regular expressions against the URL (URL_MATCHES).
  26. class URL_MATCHER_EXPORT URLMatcherCondition {
  27. public:
  28. enum Criterion {
  29. HOST_PREFIX,
  30. HOST_SUFFIX,
  31. HOST_CONTAINS,
  32. HOST_EQUALS,
  33. PATH_PREFIX,
  34. PATH_SUFFIX,
  35. PATH_CONTAINS,
  36. PATH_EQUALS,
  37. QUERY_PREFIX,
  38. QUERY_SUFFIX,
  39. QUERY_CONTAINS,
  40. QUERY_EQUALS,
  41. HOST_SUFFIX_PATH_PREFIX,
  42. HOST_EQUALS_PATH_PREFIX,
  43. URL_PREFIX,
  44. URL_SUFFIX,
  45. URL_CONTAINS,
  46. URL_EQUALS,
  47. URL_MATCHES,
  48. ORIGIN_AND_PATH_MATCHES, // Matches the URL minus its query string.
  49. };
  50. URLMatcherCondition();
  51. ~URLMatcherCondition();
  52. URLMatcherCondition(Criterion criterion,
  53. const base::MatcherStringPattern* substring_pattern);
  54. URLMatcherCondition(const URLMatcherCondition& rhs);
  55. URLMatcherCondition& operator=(const URLMatcherCondition& rhs);
  56. bool operator<(const URLMatcherCondition& rhs) const;
  57. Criterion criterion() const { return criterion_; }
  58. const base::MatcherStringPattern* string_pattern() const {
  59. return string_pattern_;
  60. }
  61. // Returns whether this URLMatcherCondition needs to be executed on a
  62. // full URL rather than the individual components (see
  63. // URLMatcherConditionFactory).
  64. bool IsFullURLCondition() const;
  65. // Returns whether this URLMatcherCondition is a regular expression to be
  66. // handled by a regex matcher instead of a substring matcher.
  67. bool IsRegexCondition() const;
  68. // Returns whether this URLMatcherCondition is a regular expression that shall
  69. // be evaluated on the URL without the query parameter.
  70. bool IsOriginAndPathRegexCondition() const;
  71. // Returns whether this condition is fulfilled according to
  72. // |matching_patterns| and |url|.
  73. bool IsMatch(
  74. const std::set<base::MatcherStringPattern::ID>& matching_patterns,
  75. const GURL& url) const;
  76. private:
  77. // |criterion_| and |string_pattern_| describe together what property a URL
  78. // needs to fulfill to be considered a match.
  79. Criterion criterion_;
  80. // This is the MatcherStringPattern that is used in a SubstringSetMatcher.
  81. raw_ptr<const base::MatcherStringPattern> string_pattern_;
  82. };
  83. // Class to map the problem of finding {host, path, query} {prefixes, suffixes,
  84. // containments, and equality} in GURLs to the substring matching problem.
  85. //
  86. // Say, you want to check whether the path of a URL starts with "/index.html".
  87. // This class preprocesses a URL like "www.google.com/index.html" into something
  88. // like "www.google.com|/index.html". After preprocessing, you can search for
  89. // "|/index.html" in the string and see that this candidate URL actually has
  90. // a path that starts with "/index.html". On the contrary,
  91. // "www.google.com/images/index.html" would be normalized to
  92. // "www.google.com|/images/index.html". It is easy to see that it contains
  93. // "/index.html" but the path of the URL does not start with "/index.html".
  94. //
  95. // This preprocessing is important if you want to match a URL against many
  96. // patterns because it reduces the matching to a "discover all substrings
  97. // of a dictionary in a text" problem, which can be solved very efficiently
  98. // by the Aho-Corasick algorithm.
  99. //
  100. // IMPORTANT: The URLMatcherConditionFactory owns the MatcherStringPattern
  101. // referenced by created URLMatcherConditions. Therefore, it must outlive
  102. // all created URLMatcherCondition and the SubstringSetMatcher.
  103. class URL_MATCHER_EXPORT URLMatcherConditionFactory {
  104. public:
  105. URLMatcherConditionFactory();
  106. URLMatcherConditionFactory(const URLMatcherConditionFactory&) = delete;
  107. URLMatcherConditionFactory& operator=(const URLMatcherConditionFactory&) =
  108. delete;
  109. ~URLMatcherConditionFactory();
  110. // Canonicalizes a URL for "Create{Host,Path,Query}*Condition" searches.
  111. std::string CanonicalizeURLForComponentSearches(const GURL& url) const;
  112. // Factory methods for various condition types.
  113. //
  114. // Note that these methods fill the pattern_singletons_. If you create
  115. // conditions and don't register them to a URLMatcher, they will continue to
  116. // consume memory. You need to call ForgetUnusedPatterns() or
  117. // URLMatcher::ClearUnusedConditionSets() in this case.
  118. URLMatcherCondition CreateHostPrefixCondition(const std::string& prefix);
  119. URLMatcherCondition CreateHostSuffixCondition(const std::string& suffix);
  120. URLMatcherCondition CreateHostContainsCondition(const std::string& str);
  121. URLMatcherCondition CreateHostEqualsCondition(const std::string& str);
  122. URLMatcherCondition CreatePathPrefixCondition(const std::string& prefix);
  123. URLMatcherCondition CreatePathSuffixCondition(const std::string& suffix);
  124. URLMatcherCondition CreatePathContainsCondition(const std::string& str);
  125. URLMatcherCondition CreatePathEqualsCondition(const std::string& str);
  126. URLMatcherCondition CreateQueryPrefixCondition(const std::string& prefix);
  127. URLMatcherCondition CreateQuerySuffixCondition(const std::string& suffix);
  128. URLMatcherCondition CreateQueryContainsCondition(const std::string& str);
  129. URLMatcherCondition CreateQueryEqualsCondition(const std::string& str);
  130. // This covers the common case, where you don't care whether a domain
  131. // "foobar.com" is expressed as "foobar.com" or "www.foobar.com", and it
  132. // should be followed by a given |path_prefix|.
  133. URLMatcherCondition CreateHostSuffixPathPrefixCondition(
  134. const std::string& host_suffix,
  135. const std::string& path_prefix);
  136. URLMatcherCondition CreateHostEqualsPathPrefixCondition(
  137. const std::string& host,
  138. const std::string& path_prefix);
  139. // Canonicalizes a URL for "CreateURL*Condition" searches.
  140. std::string CanonicalizeURLForFullSearches(const GURL& url) const;
  141. // Canonicalizes a URL for "CreateURLMatchesCondition" searches.
  142. std::string CanonicalizeURLForRegexSearches(const GURL& url) const;
  143. // Canonicalizes a URL for "CreateOriginAndPathMatchesCondition" searches.
  144. std::string CanonicalizeURLForOriginAndPathRegexSearches(
  145. const GURL& url) const;
  146. URLMatcherCondition CreateURLPrefixCondition(const std::string& prefix);
  147. URLMatcherCondition CreateURLSuffixCondition(const std::string& suffix);
  148. URLMatcherCondition CreateURLContainsCondition(const std::string& str);
  149. URLMatcherCondition CreateURLEqualsCondition(const std::string& str);
  150. URLMatcherCondition CreateURLMatchesCondition(const std::string& regex);
  151. URLMatcherCondition CreateOriginAndPathMatchesCondition(
  152. const std::string& regex);
  153. // Removes all patterns from |pattern_singletons_| that are not listed in
  154. // |used_patterns|. These patterns are not referenced any more and get
  155. // freed.
  156. void ForgetUnusedPatterns(
  157. const std::set<base::MatcherStringPattern::ID>& used_patterns);
  158. // Returns true if this object retains no allocated data. Only for debugging.
  159. bool IsEmpty() const;
  160. private:
  161. // Creates a URLMatcherCondition according to the parameters passed.
  162. // The URLMatcherCondition will refer to a MatcherStringPattern that is
  163. // owned by |pattern_singletons_|.
  164. URLMatcherCondition CreateCondition(URLMatcherCondition::Criterion criterion,
  165. const std::string& pattern);
  166. // Prepends a "." to the prefix if it does not start with one.
  167. std::string CanonicalizeHostPrefix(const std::string& prefix) const;
  168. // Appends a "." to the hostname if it does not start with one.
  169. std::string CanonicalizeHostSuffix(const std::string& suffix) const;
  170. // Adds "." to either side of the hostname if not present yet.
  171. std::string CanonicalizeHostname(const std::string& hostname) const;
  172. // Convert the query string to canonical form suitable for key token search.
  173. std::string CanonicalizeQuery(std::string query,
  174. bool prepend_beginning_of_query_component,
  175. bool append_end_of_query_component) const;
  176. // Return the next MatcherStringPattern id to use.
  177. base::MatcherStringPattern::ID GetNextID();
  178. // Counter that ensures that all created MatcherStringPatterns have unique
  179. // IDs. Note that substring patterns and regex patterns will use different
  180. // IDs.
  181. base::MatcherStringPattern::ID id_counter_ = 0;
  182. // This comparison considers only the pattern() value of the
  183. // MatcherStringPatterns.
  184. struct MatcherStringPatternPointerCompare {
  185. bool operator()(base::MatcherStringPattern* lhs,
  186. base::MatcherStringPattern* rhs) const;
  187. };
  188. // Set to ensure that we generate only one MatcherStringPattern for each
  189. // content of MatcherStringPattern::pattern().
  190. using PatternSingletons =
  191. std::map<base::MatcherStringPattern*,
  192. std::unique_ptr<base::MatcherStringPattern>,
  193. MatcherStringPatternPointerCompare>;
  194. PatternSingletons substring_pattern_singletons_;
  195. PatternSingletons regex_pattern_singletons_;
  196. PatternSingletons origin_and_path_regex_pattern_singletons_;
  197. };
  198. // This class represents a single URL query matching condition. The query
  199. // matching is done as a search for a key and optionally a value.
  200. // The matching makes use of CanonicalizeURLForComponentSearches to ensure that
  201. // the key starts and ends (optionally) with the right marker.
  202. class URL_MATCHER_EXPORT URLQueryElementMatcherCondition {
  203. public:
  204. // Multiple occurrences of the same key can happen in a URL query. The type
  205. // ensures that every (MATCH_ALL), any (MATCH_ANY), first (MATCH_FIRST) or
  206. // last (MATCH_LAST) instance of the key occurrence matches the value.
  207. enum Type { MATCH_ANY, MATCH_FIRST, MATCH_LAST, MATCH_ALL };
  208. // Allows the match to be exact (QUERY_VALUE_MATCH_EXACT, starts and ends with
  209. // a delimiter or a border) or simply a prefix (QUERY_VALUE_MATCH_PREFIX,
  210. // starts with a delimiter or a border).
  211. enum QueryValueMatchType {
  212. QUERY_VALUE_MATCH_EXACT,
  213. QUERY_VALUE_MATCH_PREFIX
  214. };
  215. // Used to indicate if the query parameter is of type &key=value&
  216. // (ELEMENT_TYPE_KEY_VALUE) or simply &key& (ELEMENT_TYPE_KEY).
  217. enum QueryElementType { ELEMENT_TYPE_KEY_VALUE, ELEMENT_TYPE_KEY };
  218. URLQueryElementMatcherCondition(const std::string& key,
  219. const std::string& value,
  220. QueryValueMatchType query_value_match_type,
  221. QueryElementType query_element_type,
  222. Type match_type,
  223. URLMatcherConditionFactory* factory);
  224. URLQueryElementMatcherCondition(const URLQueryElementMatcherCondition& other);
  225. ~URLQueryElementMatcherCondition();
  226. bool operator<(const URLQueryElementMatcherCondition& rhs) const;
  227. // Returns whether the URL query satisfies the key value constraint.
  228. bool IsMatch(const std::string& canonical_url_query) const;
  229. const base::MatcherStringPattern* string_pattern() const {
  230. return string_pattern_;
  231. }
  232. private:
  233. Type match_type_;
  234. std::string key_;
  235. std::string value_;
  236. size_t key_length_;
  237. size_t value_length_;
  238. raw_ptr<const base::MatcherStringPattern> string_pattern_;
  239. };
  240. // This class represents a filter for the URL scheme to be hooked up into a
  241. // URLMatcherConditionSet.
  242. class URL_MATCHER_EXPORT URLMatcherSchemeFilter {
  243. public:
  244. explicit URLMatcherSchemeFilter(const std::string& filter);
  245. explicit URLMatcherSchemeFilter(const std::vector<std::string>& filters);
  246. URLMatcherSchemeFilter(const URLMatcherSchemeFilter&) = delete;
  247. URLMatcherSchemeFilter& operator=(const URLMatcherSchemeFilter&) = delete;
  248. ~URLMatcherSchemeFilter();
  249. bool IsMatch(const GURL& url) const;
  250. private:
  251. std::vector<std::string> filters_;
  252. };
  253. // This class represents a filter for port numbers to be hooked up into a
  254. // URLMatcherConditionSet.
  255. class URL_MATCHER_EXPORT URLMatcherPortFilter {
  256. public:
  257. // Boundaries of a port range (both ends are included).
  258. typedef std::pair<int, int> Range;
  259. explicit URLMatcherPortFilter(const std::vector<Range>& ranges);
  260. URLMatcherPortFilter(const URLMatcherPortFilter&) = delete;
  261. URLMatcherPortFilter& operator=(const URLMatcherPortFilter&) = delete;
  262. ~URLMatcherPortFilter();
  263. bool IsMatch(const GURL& url) const;
  264. // Creates a port range [from, to]; both ends are included.
  265. static Range CreateRange(int from, int to);
  266. // Creates a port range containing a single port.
  267. static Range CreateRange(int port);
  268. private:
  269. std::vector<Range> ranges_;
  270. };
  271. // This class represents a set of conditions that all need to match on a
  272. // given URL in order to be considered a match.
  273. class URL_MATCHER_EXPORT URLMatcherConditionSet
  274. : public base::RefCounted<URLMatcherConditionSet> {
  275. public:
  276. typedef std::set<URLMatcherCondition> Conditions;
  277. typedef std::set<URLQueryElementMatcherCondition> QueryConditions;
  278. typedef std::vector<scoped_refptr<URLMatcherConditionSet>> Vector;
  279. // Matches if all conditions in |conditions| are fulfilled.
  280. URLMatcherConditionSet(base::MatcherStringPattern::ID id,
  281. const Conditions& conditions);
  282. // Matches if all conditions in |conditions|, |scheme_filter| and
  283. // |port_filter| are fulfilled. |scheme_filter| and |port_filter| may be NULL,
  284. // in which case, no restrictions are imposed on the scheme/port of a URL.
  285. URLMatcherConditionSet(base::MatcherStringPattern::ID id,
  286. const Conditions& conditions,
  287. std::unique_ptr<URLMatcherSchemeFilter> scheme_filter,
  288. std::unique_ptr<URLMatcherPortFilter> port_filter);
  289. // Matches if all conditions in |conditions|, |query_conditions|,
  290. // |scheme_filter| and |port_filter| are fulfilled. |scheme_filter| and
  291. // |port_filter| may be NULL, in which case, no restrictions are imposed on
  292. // the scheme/port of a URL.
  293. URLMatcherConditionSet(base::MatcherStringPattern::ID id,
  294. const Conditions& conditions,
  295. const QueryConditions& query_conditions,
  296. std::unique_ptr<URLMatcherSchemeFilter> scheme_filter,
  297. std::unique_ptr<URLMatcherPortFilter> port_filter);
  298. URLMatcherConditionSet(const URLMatcherConditionSet&) = delete;
  299. URLMatcherConditionSet& operator=(const URLMatcherConditionSet&) = delete;
  300. base::MatcherStringPattern::ID id() const { return id_; }
  301. const Conditions& conditions() const { return conditions_; }
  302. const QueryConditions& query_conditions() const { return query_conditions_; }
  303. bool IsMatch(
  304. const std::set<base::MatcherStringPattern::ID>& matching_patterns,
  305. const GURL& url) const;
  306. bool IsMatch(
  307. const std::set<base::MatcherStringPattern::ID>& matching_patterns,
  308. const GURL& url,
  309. const std::string& url_for_component_searches) const;
  310. private:
  311. friend class base::RefCounted<URLMatcherConditionSet>;
  312. ~URLMatcherConditionSet();
  313. base::MatcherStringPattern::ID id_ = 0;
  314. Conditions conditions_;
  315. QueryConditions query_conditions_;
  316. std::unique_ptr<URLMatcherSchemeFilter> scheme_filter_;
  317. std::unique_ptr<URLMatcherPortFilter> port_filter_;
  318. };
  319. // This class allows matching one URL against a large set of
  320. // URLMatcherConditionSets at the same time.
  321. class URL_MATCHER_EXPORT URLMatcher {
  322. public:
  323. URLMatcher();
  324. URLMatcher(const URLMatcher&) = delete;
  325. URLMatcher& operator=(const URLMatcher&) = delete;
  326. ~URLMatcher();
  327. // Adds new URLMatcherConditionSet to this URL Matcher. Each condition set
  328. // must have a unique ID.
  329. // This is an expensive operation as it triggers pre-calculations on the
  330. // currently registered condition sets. Do not call this operation many
  331. // times with a single condition set in each call.
  332. void AddConditionSets(const URLMatcherConditionSet::Vector& condition_sets);
  333. // Removes the listed condition sets. All |condition_set_ids| must be
  334. // currently registered. This function should be called with large batches
  335. // of |condition_set_ids| at a time to improve performance.
  336. void RemoveConditionSets(
  337. const std::vector<base::MatcherStringPattern::ID>& condition_set_ids);
  338. // Removes all unused condition sets from the ConditionFactory.
  339. void ClearUnusedConditionSets();
  340. // Returns the IDs of all URLMatcherConditionSet that match to this |url|.
  341. std::set<base::MatcherStringPattern::ID> MatchURL(const GURL& url) const;
  342. // Returns the URLMatcherConditionFactory that must be used to create
  343. // URLMatcherConditionSets for this URLMatcher.
  344. URLMatcherConditionFactory* condition_factory() {
  345. return &condition_factory_;
  346. }
  347. // Returns true if this object retains no allocated data. Only for debugging.
  348. bool IsEmpty() const;
  349. private:
  350. void UpdateSubstringSetMatcher(bool full_url_conditions);
  351. void UpdateRegexSetMatcher();
  352. void UpdateTriggers();
  353. void UpdateConditionFactory();
  354. void UpdateInternalDatastructures();
  355. URLMatcherConditionFactory condition_factory_;
  356. // Maps the ID of a URLMatcherConditionSet to the respective
  357. // URLMatcherConditionSet.
  358. typedef std::map<base::MatcherStringPattern::ID,
  359. scoped_refptr<URLMatcherConditionSet>>
  360. URLMatcherConditionSets;
  361. URLMatcherConditionSets url_matcher_condition_sets_;
  362. // Maps a MatcherStringPattern ID to the URLMatcherConditions that need to
  363. // be triggered in case of a MatcherStringPattern match.
  364. typedef std::map<base::MatcherStringPattern::ID,
  365. std::set<base::MatcherStringPattern::ID>>
  366. MatcherStringPatternTriggers;
  367. MatcherStringPatternTriggers substring_match_triggers_;
  368. std::unique_ptr<base::SubstringSetMatcher> full_url_matcher_;
  369. std::unique_ptr<base::SubstringSetMatcher> url_component_matcher_;
  370. RegexSetMatcher regex_set_matcher_;
  371. RegexSetMatcher origin_and_path_regex_set_matcher_;
  372. };
  373. } // namespace url_matcher
  374. #endif // COMPONENTS_URL_MATCHER_URL_MATCHER_H_