url_pattern_index.cc 37 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998
  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. #include "components/url_pattern_index/url_pattern_index.h"
  5. #include <algorithm>
  6. #include <limits>
  7. #include <string>
  8. #include <utility>
  9. #include "base/callback.h"
  10. #include "base/check_op.h"
  11. #include "base/containers/flat_map.h"
  12. #include "base/no_destructor.h"
  13. #include "base/notreached.h"
  14. #include "base/numerics/safe_conversions.h"
  15. #include "base/strings/string_piece.h"
  16. #include "base/strings/string_util.h"
  17. #include "base/trace_event/trace_event.h"
  18. #include "components/url_pattern_index/ngram_extractor.h"
  19. #include "components/url_pattern_index/url_pattern.h"
  20. #include "components/url_pattern_index/url_rule_util.h"
  21. #include "third_party/abseil-cpp/absl/types/optional.h"
  22. #include "url/gurl.h"
  23. #include "url/origin.h"
  24. #include "url/url_constants.h"
  25. #include "url/url_util.h"
  26. namespace url_pattern_index {
  27. namespace {
  28. using FlatUrlRuleList = flatbuffers::Vector<flatbuffers::Offset<flat::UrlRule>>;
  29. using ActivationTypeMap =
  30. base::flat_map<proto::ActivationType, flat::ActivationType>;
  31. using ElementTypeMap = base::flat_map<proto::ElementType, flat::ElementType>;
  32. // Maps proto::ActivationType to flat::ActivationType.
  33. const ActivationTypeMap& GetActivationTypeMap() {
  34. static base::NoDestructor<ActivationTypeMap> activation_type_map(
  35. std::initializer_list<ActivationTypeMap::value_type>{
  36. {proto::ACTIVATION_TYPE_UNSPECIFIED, flat::ActivationType_NONE},
  37. {proto::ACTIVATION_TYPE_DOCUMENT, flat::ActivationType_DOCUMENT},
  38. // ELEMHIDE is not supported.
  39. {proto::ACTIVATION_TYPE_ELEMHIDE, flat::ActivationType_NONE},
  40. // GENERICHIDE is not supported.
  41. {proto::ACTIVATION_TYPE_GENERICHIDE, flat::ActivationType_NONE},
  42. {proto::ACTIVATION_TYPE_GENERICBLOCK,
  43. flat::ActivationType_GENERIC_BLOCK},
  44. });
  45. return *activation_type_map;
  46. }
  47. // Maps proto::ElementType to flat::ElementType.
  48. const ElementTypeMap& GetElementTypeMap() {
  49. static base::NoDestructor<ElementTypeMap> element_type_map(
  50. std::initializer_list<ElementTypeMap::value_type>{
  51. {proto::ELEMENT_TYPE_UNSPECIFIED, flat::ElementType_NONE},
  52. {proto::ELEMENT_TYPE_OTHER, flat::ElementType_OTHER},
  53. {proto::ELEMENT_TYPE_SCRIPT, flat::ElementType_SCRIPT},
  54. {proto::ELEMENT_TYPE_IMAGE, flat::ElementType_IMAGE},
  55. {proto::ELEMENT_TYPE_STYLESHEET, flat::ElementType_STYLESHEET},
  56. {proto::ELEMENT_TYPE_OBJECT, flat::ElementType_OBJECT},
  57. {proto::ELEMENT_TYPE_XMLHTTPREQUEST,
  58. flat::ElementType_XMLHTTPREQUEST},
  59. {proto::ELEMENT_TYPE_OBJECT_SUBREQUEST,
  60. flat::ElementType_OBJECT_SUBREQUEST},
  61. {proto::ELEMENT_TYPE_SUBDOCUMENT, flat::ElementType_SUBDOCUMENT},
  62. {proto::ELEMENT_TYPE_PING, flat::ElementType_PING},
  63. {proto::ELEMENT_TYPE_MEDIA, flat::ElementType_MEDIA},
  64. {proto::ELEMENT_TYPE_FONT, flat::ElementType_FONT},
  65. // Filtering popups is not supported.
  66. {proto::ELEMENT_TYPE_POPUP, flat::ElementType_NONE},
  67. {proto::ELEMENT_TYPE_WEBSOCKET, flat::ElementType_WEBSOCKET},
  68. {proto::ELEMENT_TYPE_WEBTRANSPORT, flat::ElementType_WEBTRANSPORT},
  69. {proto::ELEMENT_TYPE_WEBBUNDLE, flat::ElementType_WEBBUNDLE},
  70. });
  71. return *element_type_map;
  72. }
  73. flat::ActivationType ProtoToFlatActivationType(proto::ActivationType type) {
  74. const auto it = GetActivationTypeMap().find(type);
  75. DCHECK(it != GetActivationTypeMap().end());
  76. return it->second;
  77. }
  78. flat::ElementType ProtoToFlatElementType(proto::ElementType type) {
  79. const auto it = GetElementTypeMap().find(type);
  80. DCHECK(it != GetElementTypeMap().end());
  81. return it->second;
  82. }
  83. base::StringPiece ToStringPiece(const flatbuffers::String* string) {
  84. DCHECK(string);
  85. return base::StringPiece(string->c_str(), string->size());
  86. }
  87. bool HasNoUpperAscii(base::StringPiece string) {
  88. return std::none_of(string.begin(), string.end(), base::IsAsciiUpper<char>);
  89. }
  90. // Comparator to sort UrlRule. Sorts rules by descending order of rule priority.
  91. bool UrlRuleDescendingPriorityComparator(const flat::UrlRule* lhs,
  92. const flat::UrlRule* rhs) {
  93. DCHECK(lhs);
  94. DCHECK(rhs);
  95. return lhs->priority() > rhs->priority();
  96. }
  97. // Returns a bitmask of all the keys of the |map| passed.
  98. template <typename T>
  99. int GetKeysMask(const T& map) {
  100. int mask = 0;
  101. for (const auto& pair : map)
  102. mask |= pair.first;
  103. return mask;
  104. }
  105. // Checks whether a URL |rule| can be converted to its FlatBuffers equivalent,
  106. // and performs the actual conversion.
  107. class UrlRuleFlatBufferConverter {
  108. public:
  109. // Creates the converter, and initializes |is_convertible| bit. If
  110. // |is_convertible| == true, then all the fields, needed for serializing the
  111. // |rule| to FlatBuffer, are initialized (|options|, |anchor_right|, etc.).
  112. explicit UrlRuleFlatBufferConverter(const proto::UrlRule& rule)
  113. : rule_(rule) {
  114. is_convertible_ = InitializeOptions() && InitializeElementTypes() &&
  115. InitializeActivationTypes() && InitializeUrlPattern() &&
  116. IsMeaningful();
  117. }
  118. // Writes the URL |rule| to the FlatBuffer using the |builder|, and returns
  119. // the offset to the serialized rule. Returns an empty offset in case the rule
  120. // can't be converted. The conversion is not possible if the rule has
  121. // attributes not supported by this client version.
  122. //
  123. // |domain_map| Should point to a non-nullptr map of domain vectors to their
  124. // existing offsets. It is used to de-dupe domain vectors in the serialized
  125. // rules.
  126. UrlRuleOffset SerializeConvertedRule(flatbuffers::FlatBufferBuilder* builder,
  127. FlatDomainMap* domain_map) const {
  128. if (!is_convertible_)
  129. return UrlRuleOffset();
  130. DCHECK_NE(rule_.url_pattern_type(), proto::URL_PATTERN_TYPE_REGEXP);
  131. FlatDomainsOffset initiator_domains_included_offset;
  132. FlatDomainsOffset initiator_domains_excluded_offset;
  133. FlatDomainsOffset request_domains_included_offset;
  134. FlatDomainsOffset request_domains_excluded_offset;
  135. if (!PopulateIncludedAndExcludedDomains(
  136. rule_.initiator_domains_size(), rule_.initiator_domains(), builder,
  137. domain_map, &initiator_domains_included_offset,
  138. &initiator_domains_excluded_offset)) {
  139. return UrlRuleOffset();
  140. }
  141. if (!PopulateIncludedAndExcludedDomains(
  142. rule_.request_domains_size(), rule_.request_domains(), builder,
  143. domain_map, &request_domains_included_offset,
  144. &request_domains_excluded_offset)) {
  145. return UrlRuleOffset();
  146. }
  147. // Non-ascii characters in patterns are unsupported.
  148. if (!base::IsStringASCII(rule_.url_pattern()))
  149. return UrlRuleOffset();
  150. // TODO(crbug.com/884063): Lower case case-insensitive patterns here if we
  151. // want to support case-insensitive rules for subresource filter.
  152. auto url_pattern_offset = builder->CreateSharedString(rule_.url_pattern());
  153. return flat::CreateUrlRule(
  154. *builder, options_, element_types_, flat::RequestMethod_ANY,
  155. activation_types_, url_pattern_type_, anchor_left_, anchor_right_,
  156. initiator_domains_included_offset, initiator_domains_excluded_offset,
  157. request_domains_included_offset, request_domains_excluded_offset,
  158. url_pattern_offset);
  159. }
  160. private:
  161. FlatDomainsOffset SerializeDomainList(std::vector<FlatStringOffset> domains,
  162. flatbuffers::FlatBufferBuilder* builder,
  163. FlatDomainMap* domain_map) const {
  164. // The comparator ensuring the domains order necessary for fast matching.
  165. auto precedes = [&builder](FlatStringOffset lhs, FlatStringOffset rhs) {
  166. return CompareDomains(
  167. ToStringPiece(flatbuffers::GetTemporaryPointer(*builder, lhs)),
  168. ToStringPiece(
  169. flatbuffers::GetTemporaryPointer(*builder, rhs))) < 0;
  170. };
  171. if (domains.empty())
  172. return FlatDomainsOffset();
  173. std::sort(domains.begin(), domains.end(), precedes);
  174. // Share domain lists if we've already serialized an exact duplicate. Note
  175. // that this can share excluded and included domain lists.
  176. DCHECK(domain_map);
  177. auto it = domain_map->find(domains);
  178. if (it == domain_map->end()) {
  179. auto offset = builder->CreateVector(domains);
  180. (*domain_map)[domains] = offset;
  181. return offset;
  182. }
  183. return it->second;
  184. }
  185. // Returns true on success, false on an invalid domain entry.
  186. bool PopulateIncludedAndExcludedDomains(
  187. int domains_size,
  188. google::protobuf::RepeatedPtrField<
  189. ::url_pattern_index::proto::DomainListItem> domain_list_items,
  190. flatbuffers::FlatBufferBuilder* builder,
  191. FlatDomainMap* domain_map,
  192. FlatDomainsOffset* domains_included_offset,
  193. FlatDomainsOffset* domains_excluded_offset) const {
  194. if (domains_size == 0)
  195. return true;
  196. std::vector<FlatStringOffset> domains_included;
  197. std::vector<FlatStringOffset> domains_excluded;
  198. // Reserve only for `domains_included` because it is expected to
  199. // be the one used more frequently.
  200. domains_included.reserve(domains_size);
  201. for (const auto& domain_list_item : domain_list_items) {
  202. const std::string& domain = domain_list_item.domain();
  203. // Non-ascii characters in domains are unsupported.
  204. if (!base::IsStringASCII(domain))
  205. return false;
  206. // Note: This is not always correct. Chrome's URL parser uses upper-case
  207. // for percent encoded hosts. E.g. https://,.com is encoded as
  208. // https://%2C.com.
  209. auto offset = builder->CreateSharedString(
  210. HasNoUpperAscii(domain) ? domain : base::ToLowerASCII(domain));
  211. if (domain_list_item.exclude())
  212. domains_excluded.push_back(offset);
  213. else
  214. domains_included.push_back(offset);
  215. }
  216. // The domains are stored in sorted order to support fast matching.
  217. *domains_included_offset =
  218. SerializeDomainList(std::move(domains_included), builder, domain_map);
  219. *domains_excluded_offset =
  220. SerializeDomainList(std::move(domains_excluded), builder, domain_map);
  221. return true;
  222. }
  223. static bool ConvertAnchorType(proto::AnchorType anchor_type,
  224. flat::AnchorType* result) {
  225. switch (anchor_type) {
  226. case proto::ANCHOR_TYPE_NONE:
  227. *result = flat::AnchorType_NONE;
  228. break;
  229. case proto::ANCHOR_TYPE_BOUNDARY:
  230. *result = flat::AnchorType_BOUNDARY;
  231. break;
  232. case proto::ANCHOR_TYPE_SUBDOMAIN:
  233. *result = flat::AnchorType_SUBDOMAIN;
  234. break;
  235. default:
  236. return false; // Unsupported anchor type.
  237. }
  238. return true;
  239. }
  240. bool InitializeOptions() {
  241. static_assert(flat::OptionFlag_ANY <= std::numeric_limits<uint8_t>::max(),
  242. "Option flags can not be stored in uint8_t.");
  243. static_assert(
  244. flat::RequestMethod_ANY <= std::numeric_limits<uint16_t>::max(),
  245. "Request methods can not be stored in uint16_t.");
  246. if (rule_.semantics() == proto::RULE_SEMANTICS_ALLOWLIST) {
  247. options_ |= flat::OptionFlag_IS_ALLOWLIST;
  248. } else if (rule_.semantics() != proto::RULE_SEMANTICS_BLOCKLIST) {
  249. return false; // Unsupported semantics.
  250. }
  251. switch (rule_.source_type()) {
  252. case proto::SOURCE_TYPE_ANY:
  253. options_ |= flat::OptionFlag_APPLIES_TO_THIRD_PARTY;
  254. [[fallthrough]];
  255. case proto::SOURCE_TYPE_FIRST_PARTY:
  256. options_ |= flat::OptionFlag_APPLIES_TO_FIRST_PARTY;
  257. break;
  258. case proto::SOURCE_TYPE_THIRD_PARTY:
  259. options_ |= flat::OptionFlag_APPLIES_TO_THIRD_PARTY;
  260. break;
  261. default:
  262. return false; // Unsupported source type.
  263. }
  264. // TODO(crbug.com/884063): Consider setting IS_CASE_INSENSITIVE here if we
  265. // want to support case insensitive rules for subresource_filter.
  266. return true;
  267. }
  268. bool InitializeElementTypes() {
  269. static_assert(flat::ElementType_ANY <= std::numeric_limits<uint16_t>::max(),
  270. "Element types can not be stored in uint16_t.");
  271. // Handle the default case. Note this means we end up adding
  272. // flat::ElementType_CSP_REPORT as an element type when there is no
  273. // corresponding proto::ElementType for it. However this should not matter
  274. // in practice since subresource_filter does not do matching on CSP reports
  275. // currently. If subresource_filter started to do so, add support for CSP
  276. // reports in proto::ElementType.
  277. if (rule_.element_types() == kDefaultProtoElementTypesMask) {
  278. element_types_ = kDefaultFlatElementTypesMask;
  279. return true;
  280. }
  281. const ElementTypeMap& element_type_map = GetElementTypeMap();
  282. // Ensure all proto::ElementType(s) are mapped in |element_type_map|.
  283. DCHECK_EQ(proto::ELEMENT_TYPE_ALL, GetKeysMask(element_type_map));
  284. element_types_ = flat::ElementType_NONE;
  285. for (const auto& pair : element_type_map)
  286. if (rule_.element_types() & pair.first)
  287. element_types_ |= pair.second;
  288. // Normally we can not distinguish between the main plugin resource and any
  289. // other loads it makes. We treat them both as OBJECT requests. Hence an
  290. // OBJECT request would also match OBJECT_SUBREQUEST rules, but not the
  291. // the other way round.
  292. if (element_types_ & flat::ElementType_OBJECT_SUBREQUEST)
  293. element_types_ |= flat::ElementType_OBJECT;
  294. return true;
  295. }
  296. bool InitializeActivationTypes() {
  297. static_assert(
  298. flat::ActivationType_ANY <= std::numeric_limits<uint8_t>::max(),
  299. "Activation types can not be stored in uint8_t.");
  300. const ActivationTypeMap& activation_type_map = GetActivationTypeMap();
  301. // Ensure all proto::ActivationType(s) are mapped in |activation_type_map|.
  302. DCHECK_EQ(proto::ACTIVATION_TYPE_ALL, GetKeysMask(activation_type_map));
  303. activation_types_ = flat::ActivationType_NONE;
  304. for (const auto& pair : activation_type_map)
  305. if (rule_.activation_types() & pair.first)
  306. activation_types_ |= pair.second;
  307. return true;
  308. }
  309. bool InitializeUrlPattern() {
  310. switch (rule_.url_pattern_type()) {
  311. case proto::URL_PATTERN_TYPE_SUBSTRING:
  312. url_pattern_type_ = flat::UrlPatternType_SUBSTRING;
  313. break;
  314. case proto::URL_PATTERN_TYPE_WILDCARDED:
  315. url_pattern_type_ = flat::UrlPatternType_WILDCARDED;
  316. break;
  317. // TODO(pkalinnikov): Implement REGEXP rules matching.
  318. case proto::URL_PATTERN_TYPE_REGEXP:
  319. default:
  320. return false; // Unsupported URL pattern type.
  321. }
  322. if (!ConvertAnchorType(rule_.anchor_left(), &anchor_left_) ||
  323. !ConvertAnchorType(rule_.anchor_right(), &anchor_right_)) {
  324. return false;
  325. }
  326. if (anchor_right_ == flat::AnchorType_SUBDOMAIN)
  327. return false; // Unsupported right anchor.
  328. // We disallow patterns like "||*xyz" because it isn't clear how to match
  329. // them.
  330. if (anchor_left_ == flat::AnchorType_SUBDOMAIN &&
  331. (!rule_.url_pattern().empty() && rule_.url_pattern().front() == '*')) {
  332. return false;
  333. }
  334. return true;
  335. }
  336. // Returns whether the rule is not a no-op after all the modifications above.
  337. bool IsMeaningful() const { return element_types_ || activation_types_; }
  338. const proto::UrlRule& rule_;
  339. uint8_t options_ = 0;
  340. uint16_t element_types_ = 0;
  341. uint8_t activation_types_ = 0;
  342. flat::UrlPatternType url_pattern_type_ = flat::UrlPatternType_WILDCARDED;
  343. flat::AnchorType anchor_left_ = flat::AnchorType_NONE;
  344. flat::AnchorType anchor_right_ = flat::AnchorType_NONE;
  345. bool is_convertible_ = true;
  346. };
  347. } // namespace
  348. // Helpers. --------------------------------------------------------------------
  349. bool OffsetVectorCompare::operator()(
  350. const std::vector<FlatStringOffset>& a,
  351. const std::vector<FlatStringOffset>& b) const {
  352. auto compare = [](const FlatStringOffset a_offset,
  353. const FlatStringOffset b_offset) {
  354. DCHECK(!a_offset.IsNull());
  355. DCHECK(!b_offset.IsNull());
  356. return a_offset.o < b_offset.o;
  357. };
  358. // |lexicographical_compare| is how vector::operator< is implemented.
  359. return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),
  360. compare);
  361. }
  362. UrlRuleOffset SerializeUrlRule(const proto::UrlRule& rule,
  363. flatbuffers::FlatBufferBuilder* builder,
  364. FlatDomainMap* domain_map) {
  365. DCHECK(builder);
  366. UrlRuleFlatBufferConverter converter(rule);
  367. return converter.SerializeConvertedRule(builder, domain_map);
  368. }
  369. int CompareDomains(base::StringPiece lhs_domain, base::StringPiece rhs_domain) {
  370. if (lhs_domain.size() != rhs_domain.size())
  371. return lhs_domain.size() > rhs_domain.size() ? -1 : 1;
  372. return lhs_domain.compare(rhs_domain);
  373. }
  374. // UrlPatternIndexBuilder ------------------------------------------------------
  375. UrlPatternIndexBuilder::UrlPatternIndexBuilder(
  376. flatbuffers::FlatBufferBuilder* flat_builder)
  377. : flat_builder_(flat_builder) {
  378. DCHECK(flat_builder_);
  379. }
  380. UrlPatternIndexBuilder::~UrlPatternIndexBuilder() = default;
  381. void UrlPatternIndexBuilder::IndexUrlRule(UrlRuleOffset offset) {
  382. DCHECK(offset.o);
  383. const auto* rule = flatbuffers::GetTemporaryPointer(*flat_builder_, offset);
  384. DCHECK(rule);
  385. #if DCHECK_IS_ON()
  386. // Sanity check that the rule does not have fields with non-ascii characters.
  387. DCHECK(base::IsStringASCII(ToStringPiece(rule->url_pattern())));
  388. if (rule->initiator_domains_included()) {
  389. for (auto* domain : *rule->initiator_domains_included())
  390. DCHECK(base::IsStringASCII(ToStringPiece(domain)));
  391. }
  392. if (rule->initiator_domains_excluded()) {
  393. for (auto* domain : *rule->initiator_domains_excluded())
  394. DCHECK(base::IsStringASCII(ToStringPiece(domain)));
  395. }
  396. if (rule->request_domains_included()) {
  397. for (auto* domain : *rule->request_domains_included())
  398. DCHECK(base::IsStringASCII(ToStringPiece(domain)));
  399. }
  400. if (rule->request_domains_excluded()) {
  401. for (auto* domain : *rule->request_domains_excluded())
  402. DCHECK(base::IsStringASCII(ToStringPiece(domain)));
  403. }
  404. // Case-insensitive patterns should be lower-cased.
  405. if (rule->options() & flat::OptionFlag_IS_CASE_INSENSITIVE)
  406. DCHECK(HasNoUpperAscii(ToStringPiece(rule->url_pattern())));
  407. #endif
  408. NGram ngram = GetMostDistinctiveNGram(ToStringPiece(rule->url_pattern()));
  409. if (ngram) {
  410. ngram_index_[ngram].push_back(offset);
  411. } else {
  412. // TODO(pkalinnikov): Index fallback rules as well.
  413. fallback_rules_.push_back(offset);
  414. }
  415. }
  416. UrlPatternIndexOffset UrlPatternIndexBuilder::Finish() {
  417. std::vector<flatbuffers::Offset<flat::NGramToRules>> flat_hash_table(
  418. ngram_index_.table_size());
  419. flatbuffers::Offset<flat::NGramToRules> empty_slot_offset =
  420. flat::CreateNGramToRules(*flat_builder_);
  421. auto rules_comparator = [this](const UrlRuleOffset& lhs,
  422. const UrlRuleOffset& rhs) {
  423. return UrlRuleDescendingPriorityComparator(
  424. flatbuffers::GetTemporaryPointer(*flat_builder_, lhs),
  425. flatbuffers::GetTemporaryPointer(*flat_builder_, rhs));
  426. };
  427. for (size_t i = 0, size = ngram_index_.table_size(); i != size; ++i) {
  428. const uint32_t entry_index = ngram_index_.hash_table()[i];
  429. if (entry_index >= ngram_index_.size()) {
  430. flat_hash_table[i] = empty_slot_offset;
  431. continue;
  432. }
  433. const MutableNGramIndex::EntryType& entry =
  434. ngram_index_.entries()[entry_index];
  435. // Retrieve a mutable reference to |entry.second| and sort it in descending
  436. // order of priority.
  437. MutableUrlRuleList& rule_list = ngram_index_[entry.first];
  438. std::sort(rule_list.begin(), rule_list.end(), rules_comparator);
  439. auto rules_offset = flat_builder_->CreateVector(rule_list);
  440. flat_hash_table[i] =
  441. flat::CreateNGramToRules(*flat_builder_, entry.first, rules_offset);
  442. }
  443. auto ngram_index_offset = flat_builder_->CreateVector(flat_hash_table);
  444. // Sort |fallback_rules_| in descending order of priority.
  445. std::sort(fallback_rules_.begin(), fallback_rules_.end(), rules_comparator);
  446. auto fallback_rules_offset = flat_builder_->CreateVector(fallback_rules_);
  447. return flat::CreateUrlPatternIndex(*flat_builder_, kNGramSize,
  448. ngram_index_offset, empty_slot_offset,
  449. fallback_rules_offset);
  450. }
  451. NGram UrlPatternIndexBuilder::GetMostDistinctiveNGram(
  452. base::StringPiece pattern) {
  453. size_t min_list_size = std::numeric_limits<size_t>::max();
  454. NGram best_ngram = 0;
  455. // To support case-insensitive matching, make sure the n-grams for |pattern|
  456. // are lower-cased.
  457. DCHECK(base::IsStringASCII(pattern));
  458. auto ngrams =
  459. CreateNGramExtractor<kNGramSize, NGram, NGramCaseExtraction::kLowerCase>(
  460. pattern, [](char c) { return c == '*' || c == '^'; });
  461. for (uint64_t ngram : ngrams) {
  462. const MutableUrlRuleList* rules = ngram_index_.Get(ngram);
  463. const size_t list_size = rules ? rules->size() : 0;
  464. if (list_size < min_list_size) {
  465. // TODO(pkalinnikov): Pick random of the same-sized lists.
  466. min_list_size = list_size;
  467. best_ngram = ngram;
  468. if (list_size == 0)
  469. break;
  470. }
  471. }
  472. return best_ngram;
  473. }
  474. // UrlPatternIndex -------------------------------------------------------------
  475. namespace {
  476. using FlatNGramIndex =
  477. flatbuffers::Vector<flatbuffers::Offset<flat::NGramToRules>>;
  478. // Returns the size of the longest (sub-)domain of `host` matching one of the
  479. // `domains` in the list.
  480. //
  481. // The `domains` should be sorted in descending order of their length, and
  482. // ascending alphabetical order within the groups of same-length domains.
  483. size_t GetLongestMatchingSubdomain(base::StringPiece host,
  484. const FlatDomains& domains) {
  485. if (host.empty())
  486. return 0;
  487. // If the |domains| list is short, then the simple strategy is usually faster.
  488. if (domains.size() <= 5) {
  489. for (auto* domain : domains) {
  490. const base::StringPiece domain_piece = ToStringPiece(domain);
  491. if (url::DomainIs(host, domain_piece))
  492. return domain_piece.size();
  493. }
  494. return 0;
  495. }
  496. // Otherwise look for each subdomain of the `host` using binary search.
  497. // If the host name ends with a dot, then ignore it.
  498. if (host.back() == '.')
  499. host.remove_suffix(1);
  500. // The |left| bound of the search is shared between iterations, because
  501. // subdomains are considered in decreasing order of their lengths, therefore
  502. // each consecutive lower_bound will be at least as far as the previous.
  503. flatbuffers::uoffset_t left = 0;
  504. for (size_t position = 0;; ++position) {
  505. const base::StringPiece subdomain = host.substr(position);
  506. flatbuffers::uoffset_t right = domains.size();
  507. while (left + 1 < right) {
  508. auto middle = left + (right - left) / 2;
  509. DCHECK_LT(middle, domains.size());
  510. if (CompareDomains(ToStringPiece(domains[middle]), subdomain) <= 0)
  511. left = middle;
  512. else
  513. right = middle;
  514. }
  515. DCHECK_LT(left, domains.size());
  516. if (ToStringPiece(domains[left]) == subdomain)
  517. return subdomain.size();
  518. position = host.find('.', position);
  519. if (position == base::StringPiece::npos)
  520. break;
  521. }
  522. return 0;
  523. }
  524. // |sorted_candidates| is sorted in descending order by priority. If
  525. // |matched_rules| is specified, then all rule matches in |sorted_candidates|
  526. // will be added to |matched_rules| and null is returned. If |matched_rules| is
  527. // not specified, then this returns the first matching rule i.e. the rule with
  528. // the highest priority in |sorted_candidates| or null if no rule matches.
  529. const flat::UrlRule* FindMatchAmongCandidates(
  530. const FlatUrlRuleList* sorted_candidates,
  531. const UrlPattern::UrlInfo& url,
  532. const url::Origin& document_origin,
  533. flat::ElementType element_type,
  534. flat::ActivationType activation_type,
  535. flat::RequestMethod request_method,
  536. bool is_third_party,
  537. bool disable_generic_rules,
  538. const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
  539. embedder_conditions_matcher,
  540. std::vector<const flat::UrlRule*>* matched_rules) {
  541. if (!sorted_candidates)
  542. return nullptr;
  543. DCHECK(std::is_sorted(sorted_candidates->begin(), sorted_candidates->end(),
  544. &UrlRuleDescendingPriorityComparator));
  545. for (const flat::UrlRule* rule : *sorted_candidates) {
  546. DCHECK_NE(rule, nullptr);
  547. DCHECK_NE(rule->url_pattern_type(), flat::UrlPatternType_REGEXP);
  548. if (!DoesRuleFlagsMatch(*rule, element_type, activation_type,
  549. request_method, is_third_party,
  550. embedder_conditions_matcher)) {
  551. continue;
  552. }
  553. if (disable_generic_rules && IsRuleGeneric(*rule))
  554. continue;
  555. if (!UrlPattern(*rule).MatchesUrl(url))
  556. continue;
  557. if (!DoesOriginMatchInitiatorDomainList(document_origin, *rule))
  558. continue;
  559. if (!DoesURLMatchRequestDomainList(url, *rule))
  560. continue;
  561. if (matched_rules)
  562. matched_rules->push_back(rule);
  563. else
  564. return rule;
  565. }
  566. return nullptr;
  567. }
  568. // Returns whether the network request matches a UrlPattern |index| represented
  569. // in its FlatBuffers format. |is_third_party| should reflect the relation
  570. // between |url| and |document_origin|. If |strategy| is kAll, then
  571. // |matched_rules| will be populated with all matching UrlRules and nullptr is
  572. // returned.
  573. const flat::UrlRule* FindMatchInFlatUrlPatternIndex(
  574. const flat::UrlPatternIndex& index,
  575. const UrlPattern::UrlInfo& url,
  576. const url::Origin& document_origin,
  577. flat::ElementType element_type,
  578. flat::ActivationType activation_type,
  579. flat::RequestMethod request_method,
  580. bool is_third_party,
  581. bool disable_generic_rules,
  582. const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
  583. embedder_conditions_matcher,
  584. UrlPatternIndexMatcher::FindRuleStrategy strategy,
  585. std::vector<const flat::UrlRule*>* matched_rules) {
  586. using FindRuleStrategy = UrlPatternIndexMatcher::FindRuleStrategy;
  587. // Check that the outparam |matched_rules| is specified if and only if
  588. // |strategy| is kAll.
  589. DCHECK_EQ(strategy == FindRuleStrategy::kAll, !!matched_rules);
  590. const FlatNGramIndex* hash_table = index.ngram_index();
  591. const flat::NGramToRules* empty_slot = index.ngram_index_empty_slot();
  592. DCHECK_NE(hash_table, nullptr);
  593. NGramHashTableProber prober;
  594. // |hash_table| contains lower-cased n-grams. Use lower-cased extraction to
  595. // find prospective matches.
  596. auto ngrams = CreateNGramExtractor<kNGramSize, uint64_t,
  597. NGramCaseExtraction::kLowerCase>(
  598. url.spec(), [](char) { return false; });
  599. auto get_max_priority_rule = [](const flat::UrlRule* lhs,
  600. const flat::UrlRule* rhs) {
  601. if (!lhs)
  602. return rhs;
  603. if (!rhs)
  604. return lhs;
  605. return lhs->priority() > rhs->priority() ? lhs : rhs;
  606. };
  607. const flat::UrlRule* max_priority_rule = nullptr;
  608. for (uint64_t ngram : ngrams) {
  609. const uint32_t slot_index = prober.FindSlot(
  610. ngram, hash_table->size(),
  611. [hash_table, empty_slot](NGram ngram, uint32_t slot_index) {
  612. const flat::NGramToRules* entry = hash_table->Get(slot_index);
  613. DCHECK_NE(entry, nullptr);
  614. return entry == empty_slot || entry->ngram() == ngram;
  615. });
  616. DCHECK_LT(slot_index, hash_table->size());
  617. const flat::NGramToRules* entry = hash_table->Get(slot_index);
  618. if (entry == empty_slot)
  619. continue;
  620. const flat::UrlRule* rule = FindMatchAmongCandidates(
  621. entry->rule_list(), url, document_origin, element_type, activation_type,
  622. request_method, is_third_party, disable_generic_rules,
  623. embedder_conditions_matcher, matched_rules);
  624. if (!rule)
  625. continue;
  626. // |rule| is a matching rule with the highest priority amongst
  627. // |entry->rule_list()|.
  628. switch (strategy) {
  629. case FindRuleStrategy::kAny:
  630. return rule;
  631. case FindRuleStrategy::kHighestPriority:
  632. max_priority_rule = get_max_priority_rule(max_priority_rule, rule);
  633. break;
  634. case FindRuleStrategy::kAll:
  635. continue;
  636. }
  637. }
  638. const flat::UrlRule* rule = FindMatchAmongCandidates(
  639. index.fallback_rules(), url, document_origin, element_type,
  640. activation_type, request_method, is_third_party, disable_generic_rules,
  641. embedder_conditions_matcher, matched_rules);
  642. switch (strategy) {
  643. case FindRuleStrategy::kAny:
  644. return rule;
  645. case FindRuleStrategy::kHighestPriority:
  646. return get_max_priority_rule(max_priority_rule, rule);
  647. case FindRuleStrategy::kAll:
  648. return nullptr;
  649. }
  650. NOTREACHED();
  651. return nullptr;
  652. }
  653. } // namespace
  654. bool IsRuleGeneric(const flat::UrlRule& rule) {
  655. return !rule.initiator_domains_included();
  656. }
  657. // Returns whether the `host` matches the domain conditions. It's considered a
  658. // match if both:
  659. // 1. An included domain matches the `host`, or `domains_included` is omitted
  660. // entirely (since rules match all domains by default).
  661. // 2. No excluded domain match the `host`, or the longest matching excluded
  662. // domain is shorter than the longest matching included domain (since
  663. // longer, more specific domain matches take precedence).
  664. bool DoesHostMatchDomainLists(
  665. base::StringPiece host,
  666. const flatbuffers::Vector<flatbuffers::Offset<flatbuffers::String>>*
  667. domains_included,
  668. const flatbuffers::Vector<flatbuffers::Offset<flatbuffers::String>>*
  669. domains_excluded) {
  670. DCHECK(!domains_included || domains_included->size());
  671. size_t longest_matching_included_domain_length = 1;
  672. if (domains_included) {
  673. longest_matching_included_domain_length =
  674. GetLongestMatchingSubdomain(host, *domains_included);
  675. }
  676. if (longest_matching_included_domain_length && domains_excluded) {
  677. return GetLongestMatchingSubdomain(host, *domains_excluded) <
  678. longest_matching_included_domain_length;
  679. }
  680. return !!longest_matching_included_domain_length;
  681. }
  682. bool DoesURLMatchRequestDomainList(const UrlPattern::UrlInfo& url,
  683. const flat::UrlRule& rule) {
  684. return DoesHostMatchDomainLists(url.GetStringHost(),
  685. rule.request_domains_included(),
  686. rule.request_domains_excluded());
  687. }
  688. bool DoesOriginMatchInitiatorDomainList(const url::Origin& origin,
  689. const flat::UrlRule& rule) {
  690. // Unique `origin` matches lists of exception domains only.
  691. if (origin.opaque())
  692. return IsRuleGeneric(rule);
  693. return DoesHostMatchDomainLists(origin.host(),
  694. rule.initiator_domains_included(),
  695. rule.initiator_domains_excluded());
  696. }
  697. bool DoesRuleFlagsMatch(const flat::UrlRule& rule,
  698. flat::ElementType element_type,
  699. flat::ActivationType activation_type,
  700. flat::RequestMethod request_method,
  701. bool is_third_party,
  702. const UrlPatternIndexMatcher::EmbedderConditionsMatcher&
  703. embedder_conditions_matcher) {
  704. DCHECK((element_type == flat::ElementType_NONE) !=
  705. (activation_type == flat::ActivationType_NONE));
  706. if (element_type != flat::ElementType_NONE &&
  707. !(rule.element_types() & element_type)) {
  708. return false;
  709. }
  710. if (activation_type != flat::ActivationType_NONE &&
  711. !(rule.activation_types() & activation_type)) {
  712. return false;
  713. }
  714. if (request_method != flat::RequestMethod_NONE &&
  715. !(rule.request_methods() & request_method)) {
  716. return false;
  717. }
  718. if (is_third_party &&
  719. !(rule.options() & flat::OptionFlag_APPLIES_TO_THIRD_PARTY)) {
  720. return false;
  721. }
  722. if (!is_third_party &&
  723. !(rule.options() & flat::OptionFlag_APPLIES_TO_FIRST_PARTY)) {
  724. return false;
  725. }
  726. if (rule.embedder_conditions() && !embedder_conditions_matcher.is_null() &&
  727. !embedder_conditions_matcher.Run(*rule.embedder_conditions())) {
  728. return false;
  729. }
  730. return true;
  731. }
  732. UrlPatternIndexMatcher::UrlPatternIndexMatcher(
  733. const flat::UrlPatternIndex* flat_index)
  734. : flat_index_(flat_index) {
  735. DCHECK(!flat_index || flat_index->n() == kNGramSize);
  736. // Speculative investigation for crash (see crbug.com/1286207): check that we
  737. // can access the ngram_index on each UrlPatternIndexMatcher without failure.
  738. if (flat_index) {
  739. CHECK_GT(flat_index->ngram_index()->size(), 0u);
  740. }
  741. }
  742. UrlPatternIndexMatcher::~UrlPatternIndexMatcher() = default;
  743. UrlPatternIndexMatcher::UrlPatternIndexMatcher(UrlPatternIndexMatcher&&) =
  744. default;
  745. UrlPatternIndexMatcher& UrlPatternIndexMatcher::operator=(
  746. UrlPatternIndexMatcher&&) = default;
  747. size_t UrlPatternIndexMatcher::GetRulesCount() const {
  748. if (rules_count_)
  749. return *rules_count_;
  750. if (!flat_index_) {
  751. rules_count_ = 0;
  752. return 0;
  753. }
  754. rules_count_ = flat_index_->fallback_rules()->size();
  755. // Iterate over all ngrams and check their corresponding rules.
  756. for (auto* ngram_to_rules : *flat_index_->ngram_index()) {
  757. if (ngram_to_rules == flat_index_->ngram_index_empty_slot())
  758. continue;
  759. *rules_count_ += ngram_to_rules->rule_list()->size();
  760. }
  761. return *rules_count_;
  762. }
  763. const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
  764. const GURL& url,
  765. const url::Origin& first_party_origin,
  766. proto::ElementType element_type,
  767. proto::ActivationType activation_type,
  768. bool is_third_party,
  769. bool disable_generic_rules,
  770. const EmbedderConditionsMatcher& embedder_conditions_matcher,
  771. FindRuleStrategy strategy) const {
  772. return FindMatch(
  773. url, first_party_origin, ProtoToFlatElementType(element_type),
  774. ProtoToFlatActivationType(activation_type), flat::RequestMethod_NONE,
  775. is_third_party, disable_generic_rules, embedder_conditions_matcher,
  776. strategy);
  777. }
  778. const flat::UrlRule* UrlPatternIndexMatcher::FindMatch(
  779. const GURL& url,
  780. const url::Origin& first_party_origin,
  781. flat::ElementType element_type,
  782. flat::ActivationType activation_type,
  783. flat::RequestMethod request_method,
  784. bool is_third_party,
  785. bool disable_generic_rules,
  786. const EmbedderConditionsMatcher& embedder_conditions_matcher,
  787. FindRuleStrategy strategy) const {
  788. // Ignore URLs that are greater than the max URL length. Since those will be
  789. // disallowed elsewhere in the loading stack, we can save compute time by
  790. // avoiding matching here.
  791. if (!flat_index_ || !url.is_valid() ||
  792. url.spec().length() > url::kMaxURLChars) {
  793. return nullptr;
  794. }
  795. if ((element_type == flat::ElementType_NONE) ==
  796. (activation_type == flat::ActivationType_NONE)) {
  797. return nullptr;
  798. }
  799. // FindAllMatches should be used instead to find all matches.
  800. DCHECK_NE(strategy, FindRuleStrategy::kAll);
  801. auto* rule = FindMatchInFlatUrlPatternIndex(
  802. *flat_index_, UrlPattern::UrlInfo(url), first_party_origin, element_type,
  803. activation_type, request_method, is_third_party, disable_generic_rules,
  804. embedder_conditions_matcher, strategy, nullptr /* matched_rules */);
  805. if (rule) {
  806. TRACE_EVENT1(TRACE_DISABLED_BY_DEFAULT("loading"),
  807. "UrlPatternIndexMatcher::FindMatch", "pattern",
  808. FlatUrlRuleToFilterlistString(rule));
  809. }
  810. return rule;
  811. }
  812. std::vector<const flat::UrlRule*> UrlPatternIndexMatcher::FindAllMatches(
  813. const GURL& url,
  814. const url::Origin& first_party_origin,
  815. proto::ElementType element_type,
  816. proto::ActivationType activation_type,
  817. bool is_third_party,
  818. bool disable_generic_rules,
  819. const EmbedderConditionsMatcher& embedder_conditions_matcher) const {
  820. return FindAllMatches(
  821. url, first_party_origin, ProtoToFlatElementType(element_type),
  822. ProtoToFlatActivationType(activation_type), flat::RequestMethod_NONE,
  823. is_third_party, disable_generic_rules, embedder_conditions_matcher);
  824. }
  825. std::vector<const flat::UrlRule*> UrlPatternIndexMatcher::FindAllMatches(
  826. const GURL& url,
  827. const url::Origin& first_party_origin,
  828. flat::ElementType element_type,
  829. flat::ActivationType activation_type,
  830. flat::RequestMethod request_method,
  831. bool is_third_party,
  832. bool disable_generic_rules,
  833. const EmbedderConditionsMatcher& embedder_conditions_matcher) const {
  834. // Ignore URLs that are greater than the max URL length. Since those will be
  835. // disallowed elsewhere in the loading stack, we can save compute time by
  836. // avoiding matching here.
  837. if (!flat_index_ || !url.is_valid() ||
  838. url.spec().length() > url::kMaxURLChars) {
  839. return std::vector<const flat::UrlRule*>();
  840. }
  841. if ((element_type == flat::ElementType_NONE) ==
  842. (activation_type == flat::ActivationType_NONE)) {
  843. return std::vector<const flat::UrlRule*>();
  844. }
  845. std::vector<const flat::UrlRule*> rules;
  846. FindMatchInFlatUrlPatternIndex(
  847. *flat_index_, UrlPattern::UrlInfo(url), first_party_origin, element_type,
  848. activation_type, request_method, is_third_party, disable_generic_rules,
  849. embedder_conditions_matcher, FindRuleStrategy::kAll, &rules);
  850. return rules;
  851. }
  852. } // namespace url_pattern_index