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