url_pattern.cc 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402
  1. // Copyright 2016 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. // The matching logic distinguishes between the terms URL pattern and
  5. // subpattern. A URL pattern usually stands for the full thing, e.g.
  6. // "example.com^*path*par=val^", whereas subpattern denotes a maximal substring
  7. // of a pattern not containing the wildcard '*' character. For the example above
  8. // the subpatterns are: "example.com^", "path" and "par=val^".
  9. //
  10. // The separator placeholder '^' symbol is used in subpatterns to match any
  11. // separator character, which is any ASCII symbol except letters, digits, and
  12. // the following: '_', '-', '.', '%'. Note that the separator placeholder
  13. // character '^' is itself a separator, as well as '\0'.
  14. #include "components/url_pattern_index/url_pattern.h"
  15. #include <stddef.h>
  16. #include <algorithm>
  17. #include <ostream>
  18. #include "base/check_op.h"
  19. #include "base/notreached.h"
  20. #include "base/numerics/checked_math.h"
  21. #include "base/strings/string_util.h"
  22. #include "components/url_pattern_index/flat/url_pattern_index_generated.h"
  23. #include "components/url_pattern_index/fuzzy_pattern_matching.h"
  24. #include "components/url_pattern_index/string_splitter.h"
  25. #include "url/gurl.h"
  26. #include "url/third_party/mozilla/url_parse.h"
  27. namespace url_pattern_index {
  28. namespace {
  29. constexpr char kWildcard = '*';
  30. class IsWildcard {
  31. public:
  32. bool operator()(char c) const { return c == kWildcard; }
  33. };
  34. proto::UrlPatternType ConvertUrlPatternType(flat::UrlPatternType type) {
  35. switch (type) {
  36. case flat::UrlPatternType_SUBSTRING:
  37. return proto::URL_PATTERN_TYPE_SUBSTRING;
  38. case flat::UrlPatternType_WILDCARDED:
  39. return proto::URL_PATTERN_TYPE_WILDCARDED;
  40. case flat::UrlPatternType_REGEXP:
  41. return proto::URL_PATTERN_TYPE_REGEXP;
  42. default:
  43. return proto::URL_PATTERN_TYPE_UNSPECIFIED;
  44. }
  45. }
  46. proto::AnchorType ConvertAnchorType(flat::AnchorType type) {
  47. switch (type) {
  48. case flat::AnchorType_NONE:
  49. return proto::ANCHOR_TYPE_NONE;
  50. case flat::AnchorType_BOUNDARY:
  51. return proto::ANCHOR_TYPE_BOUNDARY;
  52. case flat::AnchorType_SUBDOMAIN:
  53. return proto::ANCHOR_TYPE_SUBDOMAIN;
  54. default:
  55. return proto::ANCHOR_TYPE_UNSPECIFIED;
  56. }
  57. }
  58. base::StringPiece ConvertString(const flatbuffers::String* string) {
  59. return string ? base::StringPiece(string->data(), string->size())
  60. : base::StringPiece();
  61. }
  62. bool HasAnyUpperAscii(base::StringPiece string) {
  63. return std::any_of(string.begin(), string.end(), base::IsAsciiUpper<char>);
  64. }
  65. // Returns whether |position| within the |url| belongs to its |host| component
  66. // and corresponds to the beginning of a (sub-)domain.
  67. inline bool IsSubdomainAnchored(base::StringPiece url,
  68. url::Component host,
  69. size_t position) {
  70. DCHECK_LE(position, url.size());
  71. const size_t host_begin = static_cast<size_t>(host.begin);
  72. const size_t host_end = static_cast<size_t>(host.end());
  73. DCHECK_LE(host_end, url.size());
  74. return position == host_begin ||
  75. (position > host_begin && position <= host_end &&
  76. url[position - 1] == '.');
  77. }
  78. // Returns the position of the leftmost occurrence of a |subpattern| in the
  79. // |text| starting no earlier than |from| the specified position. If the
  80. // |subpattern| has separator placeholders, searches for a fuzzy occurrence.
  81. size_t FindSubpattern(base::StringPiece text,
  82. base::StringPiece subpattern,
  83. size_t from = 0) {
  84. const bool is_fuzzy =
  85. (subpattern.find(kSeparatorPlaceholder) != base::StringPiece::npos);
  86. return is_fuzzy ? FindFuzzy(text, subpattern, from)
  87. : text.find(subpattern, from);
  88. }
  89. // Same as FindSubpattern(url, subpattern), but searches for an occurrence that
  90. // starts at the beginning of a (sub-)domain within the url's |host| component.
  91. size_t FindSubdomainAnchoredSubpattern(base::StringPiece url,
  92. url::Component host,
  93. base::StringPiece subpattern) {
  94. const bool is_fuzzy =
  95. (subpattern.find(kSeparatorPlaceholder) != base::StringPiece::npos);
  96. // Any match found after the end of the host will be discarded, so just
  97. // avoid searching there for the subpattern to begin with.
  98. //
  99. // Check for overflow.
  100. size_t max_match_end = 0;
  101. if (!base::CheckAdd(host.end(), subpattern.length())
  102. .AssignIfValid(&max_match_end)) {
  103. return base::StringPiece::npos;
  104. }
  105. const base::StringPiece url_match_candidate = url.substr(0, max_match_end);
  106. const base::StringPiece url_host = url.substr(0, host.end());
  107. for (size_t position = static_cast<size_t>(host.begin);
  108. position <= static_cast<size_t>(host.end()); ++position) {
  109. // Enforce as a loop precondition that we are always anchored at a
  110. // sub-domain before calling find. This is to reduce the number of potential
  111. // searches for |subpattern|.
  112. DCHECK(IsSubdomainAnchored(url, host, position));
  113. position = is_fuzzy ? FindFuzzy(url_match_candidate, subpattern, position)
  114. : url_match_candidate.find(subpattern, position);
  115. if (position == base::StringPiece::npos ||
  116. IsSubdomainAnchored(url, host, position)) {
  117. return position;
  118. }
  119. // Enforce the loop precondition. This skips |position| to the next '.',
  120. // within the host, which the loop itself increments to the anchored
  121. // sub-domain.
  122. position = url_host.find('.', position);
  123. if (position == base::StringPiece::npos)
  124. break;
  125. }
  126. return base::StringPiece::npos;
  127. }
  128. // Helper for DoesTextMatchLastSubpattern. Treats kSeparatorPlaceholder as not
  129. // matching the end of the text.
  130. bool DoesTextMatchLastSubpatternInternal(proto::AnchorType anchor_left,
  131. proto::AnchorType anchor_right,
  132. base::StringPiece text,
  133. url::Component url_host,
  134. base::StringPiece subpattern) {
  135. // Enumerate all possible combinations of |anchor_left| and |anchor_right|.
  136. if (anchor_left == proto::ANCHOR_TYPE_NONE &&
  137. anchor_right == proto::ANCHOR_TYPE_NONE) {
  138. return FindSubpattern(text, subpattern) != base::StringPiece::npos;
  139. }
  140. if (anchor_left == proto::ANCHOR_TYPE_NONE &&
  141. anchor_right == proto::ANCHOR_TYPE_BOUNDARY) {
  142. return EndsWithFuzzy(text, subpattern);
  143. }
  144. if (anchor_left == proto::ANCHOR_TYPE_BOUNDARY &&
  145. anchor_right == proto::ANCHOR_TYPE_NONE) {
  146. return StartsWithFuzzy(text, subpattern);
  147. }
  148. if (anchor_left == proto::ANCHOR_TYPE_BOUNDARY &&
  149. anchor_right == proto::ANCHOR_TYPE_BOUNDARY) {
  150. return text.size() == subpattern.size() &&
  151. StartsWithFuzzy(text, subpattern);
  152. }
  153. if (anchor_left == proto::ANCHOR_TYPE_SUBDOMAIN &&
  154. anchor_right == proto::ANCHOR_TYPE_NONE) {
  155. return url_host.is_nonempty() &&
  156. FindSubdomainAnchoredSubpattern(text, url_host, subpattern) !=
  157. base::StringPiece::npos;
  158. }
  159. if (anchor_left == proto::ANCHOR_TYPE_SUBDOMAIN &&
  160. anchor_right == proto::ANCHOR_TYPE_BOUNDARY) {
  161. return url_host.is_nonempty() && text.size() >= subpattern.size() &&
  162. IsSubdomainAnchored(text, url_host,
  163. text.size() - subpattern.size()) &&
  164. EndsWithFuzzy(text, subpattern);
  165. }
  166. NOTREACHED();
  167. return false;
  168. }
  169. // Matches the last |subpattern| against |text|. Special treatment is required
  170. // for the last subpattern since |kSeparatorPlaceholder| can also match the end
  171. // of the text.
  172. bool DoesTextMatchLastSubpattern(proto::AnchorType anchor_left,
  173. proto::AnchorType anchor_right,
  174. base::StringPiece text,
  175. url::Component url_host,
  176. base::StringPiece subpattern) {
  177. DCHECK(!subpattern.empty());
  178. if (DoesTextMatchLastSubpatternInternal(anchor_left, anchor_right, text,
  179. url_host, subpattern)) {
  180. return true;
  181. }
  182. // If the last |subpattern| ends with kSeparatorPlaceholder, then it can also
  183. // match the end of text.
  184. if (subpattern.back() == kSeparatorPlaceholder) {
  185. subpattern.remove_suffix(1);
  186. return DoesTextMatchLastSubpatternInternal(
  187. anchor_left, proto::ANCHOR_TYPE_BOUNDARY, text, url_host, subpattern);
  188. }
  189. return false;
  190. }
  191. // Returns whether the given |url_pattern| matches the given |url_spec|.
  192. // Compares the pattern the the url in a case-sensitive manner.
  193. bool IsCaseSensitiveMatch(base::StringPiece url_pattern,
  194. proto::AnchorType anchor_left,
  195. proto::AnchorType anchor_right,
  196. base::StringPiece url_spec,
  197. url::Component url_host) {
  198. DCHECK(!url_spec.empty());
  199. StringSplitter<IsWildcard> subpatterns(url_pattern);
  200. auto subpattern_it = subpatterns.begin();
  201. auto subpattern_end = subpatterns.end();
  202. // No subpatterns.
  203. if (subpattern_it == subpattern_end) {
  204. return anchor_left == proto::ANCHOR_TYPE_NONE ||
  205. anchor_right == proto::ANCHOR_TYPE_NONE;
  206. }
  207. base::StringPiece subpattern = *subpattern_it;
  208. ++subpattern_it;
  209. // There is only one |subpattern|.
  210. if (subpattern_it == subpattern_end) {
  211. return DoesTextMatchLastSubpattern(anchor_left, anchor_right, url_spec,
  212. url_host, subpattern);
  213. }
  214. // Otherwise, the first |subpattern| does not have to be a suffix. But it
  215. // still can have a left anchor. Check and handle that.
  216. base::StringPiece text = url_spec;
  217. if (anchor_left == proto::ANCHOR_TYPE_BOUNDARY) {
  218. if (!StartsWithFuzzy(url_spec, subpattern))
  219. return false;
  220. text.remove_prefix(subpattern.size());
  221. } else if (anchor_left == proto::ANCHOR_TYPE_SUBDOMAIN) {
  222. if (!url_host.is_nonempty())
  223. return false;
  224. const size_t match_begin =
  225. FindSubdomainAnchoredSubpattern(url_spec, url_host, subpattern);
  226. if (match_begin == base::StringPiece::npos)
  227. return false;
  228. text.remove_prefix(match_begin + subpattern.size());
  229. } else {
  230. DCHECK_EQ(anchor_left, proto::ANCHOR_TYPE_NONE);
  231. // Get back to the initial |subpattern|, process it in the loop below.
  232. subpattern_it = subpatterns.begin();
  233. }
  234. DCHECK(subpattern_it != subpattern_end);
  235. subpattern = *subpattern_it;
  236. // Consecutively find all the remaining subpatterns in the |text|. Handle the
  237. // last subpattern outside the loop.
  238. while (++subpattern_it != subpattern_end) {
  239. DCHECK(!subpattern.empty());
  240. const size_t match_position = FindSubpattern(text, subpattern);
  241. if (match_position == base::StringPiece::npos)
  242. return false;
  243. text.remove_prefix(match_position + subpattern.size());
  244. subpattern = *subpattern_it;
  245. }
  246. return DoesTextMatchLastSubpattern(proto::ANCHOR_TYPE_NONE, anchor_right,
  247. text, url::Component(), subpattern);
  248. }
  249. } // namespace
  250. UrlPattern::UrlInfo::UrlInfo(const GURL& url)
  251. : spec_(url.possibly_invalid_spec()),
  252. host_(url.parsed_for_possibly_invalid_spec().host) {
  253. DCHECK(url.is_valid());
  254. }
  255. base::StringPiece UrlPattern::UrlInfo::GetLowerCaseSpec() const {
  256. if (lower_case_spec_cached_)
  257. return *lower_case_spec_cached_;
  258. if (!HasAnyUpperAscii(spec_)) {
  259. lower_case_spec_cached_ = spec_;
  260. } else {
  261. lower_case_spec_owner_ = base::ToLowerASCII(spec_);
  262. lower_case_spec_cached_ = lower_case_spec_owner_;
  263. }
  264. return *lower_case_spec_cached_;
  265. }
  266. base::StringPiece UrlPattern::UrlInfo::GetStringHost() const {
  267. if (host().len <= 0)
  268. return base::StringPiece();
  269. return base::StringPiece(&spec_[host().begin], host().len);
  270. }
  271. UrlPattern::UrlInfo::~UrlInfo() = default;
  272. UrlPattern::UrlPattern() = default;
  273. UrlPattern::UrlPattern(base::StringPiece url_pattern,
  274. proto::UrlPatternType type,
  275. MatchCase match_case)
  276. : type_(type), url_pattern_(url_pattern), match_case_(match_case) {}
  277. UrlPattern::UrlPattern(base::StringPiece url_pattern,
  278. proto::AnchorType anchor_left,
  279. proto::AnchorType anchor_right)
  280. : type_(proto::URL_PATTERN_TYPE_WILDCARDED),
  281. url_pattern_(url_pattern),
  282. anchor_left_(anchor_left),
  283. anchor_right_(anchor_right) {}
  284. UrlPattern::UrlPattern(const flat::UrlRule& rule)
  285. : type_(ConvertUrlPatternType(rule.url_pattern_type())),
  286. url_pattern_(ConvertString(rule.url_pattern())),
  287. anchor_left_(ConvertAnchorType(rule.anchor_left())),
  288. anchor_right_(ConvertAnchorType(rule.anchor_right())),
  289. match_case_(rule.options() & flat::OptionFlag_IS_CASE_INSENSITIVE
  290. ? MatchCase::kFalse
  291. : MatchCase::kTrue) {}
  292. UrlPattern::~UrlPattern() = default;
  293. bool UrlPattern::MatchesUrl(const UrlInfo& url) const {
  294. DCHECK(type_ == proto::URL_PATTERN_TYPE_SUBSTRING ||
  295. type_ == proto::URL_PATTERN_TYPE_WILDCARDED);
  296. DCHECK(base::IsStringASCII(url_pattern_));
  297. DCHECK(base::IsStringASCII(url.spec()));
  298. DCHECK(base::IsStringASCII(url.GetLowerCaseSpec()));
  299. // Pre-process patterns to ensure left anchored and right anchored patterns
  300. // don't begin and end with a wildcard respectively i.e. change "|*xyz" to
  301. // "*xyz" and "xyz*|" to "xyz*".
  302. proto::AnchorType anchor_left = anchor_left_;
  303. proto::AnchorType anchor_right = anchor_right_;
  304. if (!url_pattern_.empty()) {
  305. if (url_pattern_.front() == kWildcard) {
  306. // Note: We don't handle "||*" and expect clients to disallow it.
  307. DCHECK_NE(proto::ANCHOR_TYPE_SUBDOMAIN, anchor_left_);
  308. anchor_left = proto::ANCHOR_TYPE_NONE;
  309. }
  310. if (url_pattern_.back() == kWildcard)
  311. anchor_right = proto::ANCHOR_TYPE_NONE;
  312. }
  313. if (match_case()) {
  314. return IsCaseSensitiveMatch(url_pattern_, anchor_left, anchor_right,
  315. url.spec(), url.host());
  316. }
  317. // Use the lower-cased url for case-insensitive comparison. Case-insensitive
  318. // patterns should already be lower-cased.
  319. DCHECK(!HasAnyUpperAscii(url_pattern_));
  320. return IsCaseSensitiveMatch(url_pattern_, anchor_left, anchor_right,
  321. url.GetLowerCaseSpec(), url.host());
  322. }
  323. std::ostream& operator<<(std::ostream& out, const UrlPattern& pattern) {
  324. switch (pattern.anchor_left()) {
  325. case proto::ANCHOR_TYPE_SUBDOMAIN:
  326. out << '|';
  327. [[fallthrough]];
  328. case proto::ANCHOR_TYPE_BOUNDARY:
  329. out << '|';
  330. [[fallthrough]];
  331. default:
  332. break;
  333. }
  334. out << pattern.url_pattern();
  335. if (pattern.anchor_right() == proto::ANCHOR_TYPE_BOUNDARY)
  336. out << '|';
  337. if (pattern.match_case())
  338. out << "$match-case";
  339. return out;
  340. }
  341. } // namespace url_pattern_index