url_pattern_index.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288
  1. // Copyright 2017 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_PATTERN_INDEX_URL_PATTERN_INDEX_H_
  5. #define COMPONENTS_URL_PATTERN_INDEX_URL_PATTERN_INDEX_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <map>
  9. #include <vector>
  10. #include "base/callback_forward.h"
  11. #include "base/memory/raw_ptr.h"
  12. #include "base/strings/string_piece_forward.h"
  13. #include "components/url_pattern_index/closed_hash_map.h"
  14. #include "components/url_pattern_index/flat/url_pattern_index_generated.h"
  15. #include "components/url_pattern_index/proto/rules.pb.h"
  16. #include "components/url_pattern_index/uint64_hasher.h"
  17. #include "components/url_pattern_index/url_pattern.h"
  18. #include "third_party/abseil-cpp/absl/types/optional.h"
  19. #include "third_party/flatbuffers/src/include/flatbuffers/flatbuffers.h"
  20. class GURL;
  21. namespace url {
  22. class Origin;
  23. }
  24. namespace url_pattern_index {
  25. // The integer type used to represent N-grams.
  26. using NGram = uint64_t;
  27. // The hasher used for hashing N-grams.
  28. using NGramHasher = Uint64ToUint32Hasher;
  29. // The hash table probe sequence used both by UrlPatternIndex and its builder.
  30. using NGramHashTableProber = DefaultProber<NGram, NGramHasher>;
  31. // FlatBuffer offset aliases.
  32. using UrlRuleOffset = flatbuffers::Offset<flat::UrlRule>;
  33. using UrlPatternIndexOffset = flatbuffers::Offset<flat::UrlPatternIndex>;
  34. using FlatStringOffset = flatbuffers::Offset<flatbuffers::String>;
  35. using FlatDomains = flatbuffers::Vector<FlatStringOffset>;
  36. using FlatDomainsOffset = flatbuffers::Offset<FlatDomains>;
  37. struct OffsetVectorCompare {
  38. bool operator()(const std::vector<FlatStringOffset>& a,
  39. const std::vector<FlatStringOffset>& b) const;
  40. };
  41. using FlatDomainMap = std::
  42. map<std::vector<FlatStringOffset>, FlatDomainsOffset, OffsetVectorCompare>;
  43. constexpr size_t kNGramSize = 5;
  44. static_assert(kNGramSize <= sizeof(NGram), "NGram type is too narrow.");
  45. // The default element types mask as specified by the flatbuffer schema.
  46. constexpr uint16_t kDefaultFlatElementTypesMask =
  47. flat::ElementType_ANY & ~flat::ElementType_MAIN_FRAME;
  48. // The default element types mask used by a proto::UrlRule.
  49. constexpr uint32_t kDefaultProtoElementTypesMask =
  50. proto::ELEMENT_TYPE_ALL & ~proto::ELEMENT_TYPE_POPUP;
  51. // Serializes the |rule| to the FlatBuffer |builder|, and returns an offset to
  52. // it in the resulting buffer. Returns null offset iff the |rule| could not be
  53. // serialized because of unsupported options or it is otherwise invalid.
  54. //
  55. // |domain_map| Should point to a non-nullptr map of domain vectors to their
  56. // existing offsets. It is used to de-dupe domain vectors in the serialized
  57. // rules.
  58. UrlRuleOffset SerializeUrlRule(const proto::UrlRule& rule,
  59. flatbuffers::FlatBufferBuilder* builder,
  60. FlatDomainMap* domain_map);
  61. // Performs three-way comparison between two domains. In the total order defined
  62. // by this predicate, the lengths of domains will be monotonically decreasing.
  63. // Domains of same length are ordered in lexicographic order.
  64. // Returns a negative value if |lhs_domain| should be ordered before
  65. // |rhs_domain|, zero if |lhs_domain| is equal to |rhs_domain| and a positive
  66. // value if |lhs_domain| should be ordered after |rhs_domain|.
  67. int CompareDomains(base::StringPiece lhs_domain, base::StringPiece rhs_domain);
  68. // The current format version of UrlPatternIndex.
  69. // Increase this value when introducing an incompatible change to the
  70. // UrlPatternIndex schema (flat/url_pattern_index.fbs). url_pattern_index
  71. // clients can use this as a signal to rebuild rulesets.
  72. constexpr int kUrlPatternIndexFormatVersion = 14;
  73. // The class used to construct an index over the URL patterns of a set of URL
  74. // rules. The rules themselves need to be converted to FlatBuffers format by the
  75. // client of this class, as well as persisted into the |flat_builder| that is
  76. // supplied in the constructor.
  77. class UrlPatternIndexBuilder {
  78. public:
  79. explicit UrlPatternIndexBuilder(flatbuffers::FlatBufferBuilder* flat_builder);
  80. UrlPatternIndexBuilder(const UrlPatternIndexBuilder&) = delete;
  81. UrlPatternIndexBuilder& operator=(const UrlPatternIndexBuilder&) = delete;
  82. ~UrlPatternIndexBuilder();
  83. // Adds a UrlRule to the index. The caller should have already persisted the
  84. // rule into the same |flat_builder| by a call to SerializeUrlRule returning a
  85. // non-null |offset|, and should pass in the resulting |offset| here.
  86. void IndexUrlRule(UrlRuleOffset offset);
  87. // Finalizes construction of the index, serializes it using |flat_builder|,
  88. // and returns an offset to it in the resulting FlatBuffer.
  89. UrlPatternIndexOffset Finish();
  90. private:
  91. using MutableUrlRuleList = std::vector<UrlRuleOffset>;
  92. using MutableNGramIndex =
  93. ClosedHashMap<NGram, MutableUrlRuleList, NGramHashTableProber>;
  94. // Returns an N-gram of the |pattern| encoded into the NGram integer type. The
  95. // N-gram is picked using a greedy heuristic, i.e. the one is chosen which
  96. // corresponds to the shortest list of rules within the index. If there are no
  97. // valid N-grams in the |pattern|, the return value is 0.
  98. NGram GetMostDistinctiveNGram(base::StringPiece pattern);
  99. // This index contains all non-REGEXP rules that have at least one acceptable
  100. // N-gram. For each given rule, the N-gram used as an index key is picked
  101. // greedily (see GetMostDistinctiveNGram).
  102. MutableNGramIndex ngram_index_;
  103. // A fallback list that contains all the rules with no acceptable N-gram.
  104. MutableUrlRuleList fallback_rules_;
  105. // Must outlive this instance.
  106. raw_ptr<flatbuffers::FlatBufferBuilder> flat_builder_;
  107. };
  108. // Encapsulates a read-only index built over the URL patterns of a set of URL
  109. // rules, and provides fast matching of network requests against these rules.
  110. class UrlPatternIndexMatcher {
  111. public:
  112. enum class FindRuleStrategy {
  113. // Any rule is returned in case multiple rules match.
  114. kAny,
  115. // If multiple rules match, any of the rules with the highest priority is
  116. // returned.
  117. kHighestPriority,
  118. // All matching rules are returned.
  119. kAll,
  120. };
  121. // Matches the request against `embedder_conditions` and returns true if the
  122. // request matched.
  123. using EmbedderConditionsMatcher = base::RepeatingCallback<bool(
  124. const flatbuffers::Vector<uint8_t>& embedder_conditions)>;
  125. // Creates an instance to access the given |flat_index|. If |flat_index| is
  126. // nullptr, then all requests return no match.
  127. explicit UrlPatternIndexMatcher(const flat::UrlPatternIndex* flat_index);
  128. UrlPatternIndexMatcher(const UrlPatternIndexMatcher&) = delete;
  129. UrlPatternIndexMatcher& operator=(const UrlPatternIndexMatcher&) = delete;
  130. ~UrlPatternIndexMatcher();
  131. UrlPatternIndexMatcher(UrlPatternIndexMatcher&&);
  132. UrlPatternIndexMatcher& operator=(UrlPatternIndexMatcher&&);
  133. // Returns the number of rules in this index. Lazily computed, the first call
  134. // to this method will scan the entire index.
  135. size_t GetRulesCount() const;
  136. // If the index contains one or more UrlRules that match the request, returns
  137. // one of them, depending on the `strategy`. Otherwise, returns nullptr.
  138. //
  139. // Notes on parameters:
  140. // - `url` should be valid and not longer than url::kMaxURLChars, otherwise
  141. // the return value is nullptr. The length limit is chosen due to
  142. // performance implications of matching giant URLs, along with the fact
  143. // that in many places in Chrome (e.g. at the IPC layer), URLs longer than
  144. // this are dropped already.
  145. // - Exactly one of `element_type` and `activation_type` should be specified,
  146. // i.e., not equal to *_UNSPECIFIED, otherwise the return value is nullptr.
  147. // - `request_method` can only be specified when using flat::* types. Matches
  148. // are not filtered by request method when using proto::* types.
  149. // - `is_third_party` should be pre-computed by the caller, e.g. using the
  150. // registry_controlled_domains library, to reflect the relation between
  151. // `url` and `first_party_origin`.
  152. //
  153. // A rule is deemed to match the request iff all of the following applies:
  154. // - The `url` matches the rule's UrlPattern (see url_pattern.h).
  155. // - The `first_party_origin` matches the rule's targeted domains list.
  156. // - `element_type` or `activation_type` is among the rule's targeted types.
  157. // - The `is_third_party` bit matches the rule's requirement on the requested
  158. // `url` being first-/third-party w.r.t. its `first_party_origin`.
  159. // - The rule is not generic if `disable_generic_rules` is true.
  160. const flat::UrlRule* FindMatch(
  161. const GURL& url,
  162. const url::Origin& first_party_origin,
  163. proto::ElementType element_type,
  164. proto::ActivationType activation_type,
  165. bool is_third_party,
  166. bool disable_generic_rules,
  167. const EmbedderConditionsMatcher& embedder_conditions_matcher,
  168. FindRuleStrategy strategy) const;
  169. // Helper function to work with flat::*Type(s). If the index contains one or
  170. // more UrlRules that match the request, returns one of them depending on
  171. // |strategy|. Otherwise, returns nullptr.
  172. const flat::UrlRule* FindMatch(
  173. const GURL& url,
  174. const url::Origin& first_party_origin,
  175. flat::ElementType element_type,
  176. flat::ActivationType activation_type,
  177. flat::RequestMethod request_method,
  178. bool is_third_party,
  179. bool disable_generic_rules,
  180. const EmbedderConditionsMatcher& embedder_conditions_matcher,
  181. FindRuleStrategy strategy) const;
  182. // Same as FindMatch, except this function returns all UrlRules that match the
  183. // request for the index. If no UrlRules match, returns an empty vector.
  184. std::vector<const flat::UrlRule*> FindAllMatches(
  185. const GURL& url,
  186. const url::Origin& first_party_origin,
  187. proto::ElementType element_type,
  188. proto::ActivationType activation_type,
  189. bool is_third_party,
  190. bool disable_generic_rules,
  191. const EmbedderConditionsMatcher& embedder_conditions_matcher) const;
  192. // Helper function to work with flat::*Type(s). Returns all UrlRules that
  193. // match the request for the index. If no UrlRules match, returns an empty
  194. // vector.
  195. std::vector<const flat::UrlRule*> FindAllMatches(
  196. const GURL& url,
  197. const url::Origin& first_party_origin,
  198. flat::ElementType element_type,
  199. flat::ActivationType activation_type,
  200. flat::RequestMethod request_method,
  201. bool is_third_party,
  202. bool disable_generic_rules,
  203. const EmbedderConditionsMatcher& embedder_conditions_matcher) const;
  204. private:
  205. // Must outlive this instance.
  206. const flat::UrlPatternIndex* flat_index_;
  207. // The number of rules in this index. Mutable since this is lazily computed.
  208. mutable absl::optional<size_t> rules_count_;
  209. };
  210. // Returns whether the `rule` is considered "generic". A generic rule is one
  211. // whose initator domain list is either empty or contains only negative domains.
  212. bool IsRuleGeneric(const flat::UrlRule& rule);
  213. // Returns whether the `origin` matches the initiator domain list of the `rule`.
  214. // A match means that the longest domain in `domains` that `origin` is a
  215. // sub-domain of is not an exception OR all the `domains` are exceptions and
  216. // neither matches the `origin`. Thus, domain filters with more domain
  217. // components trump filters with fewer domain components, i.e. the more specific
  218. // a filter is, the higher the priority.
  219. bool DoesOriginMatchInitiatorDomainList(const url::Origin& origin,
  220. const flat::UrlRule& rule);
  221. // Returns whether the request URL matches the request domain list of the
  222. // `rule`. See `DoesOriginMatchInitiatorDomainList` for an explanation of the
  223. // matching logic.
  224. bool DoesURLMatchRequestDomainList(const UrlPattern::UrlInfo& url,
  225. const flat::UrlRule& rule);
  226. // Returns whether the request matches flags of the specified `rule`. Takes into
  227. // account:
  228. // - `element_type` of the requested resource, if not *_NONE.
  229. // - `activation_type` for a subdocument request, if not *_NONE.
  230. // - `request_method` of the request, if not *_NONE.
  231. // - Whether the resource `is_third_party` w.r.t. its embedding document.
  232. // - Options specified by the embedder via `embedder_conditions_matcher`.
  233. bool DoesRuleFlagsMatch(const flat::UrlRule& rule,
  234. flat::ElementType element_type,
  235. flat::ActivationType activation_type,
  236. flat::RequestMethod request_method,
  237. bool is_third_party,
  238. const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
  239. embedder_conditions_matcher);
  240. } // namespace url_pattern_index
  241. #endif // COMPONENTS_URL_PATTERN_INDEX_URL_PATTERN_INDEX_H_