OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2012 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 | |
5 #ifndef CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_ | |
6 #define CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_ | |
7 | |
8 #include <map> | |
9 #include <set> | |
10 #include <string> | |
11 #include <vector> | |
12 | |
13 #include "base/memory/scoped_ptr.h" | |
14 #include "chrome/common/extensions/matcher/string_pattern.h" | |
15 #include "chrome/common/extensions/matcher/substring_set_matcher.h" | |
16 | |
17 namespace re2 { | |
18 class FilteredRE2; | |
19 } | |
20 | |
21 namespace extensions { | |
22 | |
23 // Efficiently matches URLs against a collection of regular expressions, | |
24 // using FilteredRE2 to reduce the number of regexes that must be matched | |
25 // by pre-filtering with substring matching. See: | |
26 // http://swtch.com/~rsc/regexp/regexp3.html#analysis | |
27 class RegexSetMatcher { | |
28 public: | |
29 RegexSetMatcher(); | |
30 virtual ~RegexSetMatcher(); | |
31 | |
32 // Adds the regex patterns in |regex_list| to the matcher. Also rebuilds | |
33 // the FilteredRE2 matcher; thus, for efficiency, prefer adding multiple | |
34 // patterns at once. | |
35 // Ownership of the patterns remains with the caller. | |
36 void AddPatterns(const std::vector<const StringPattern*>& regex_list); | |
37 | |
38 // Removes all regex patterns. | |
39 void ClearPatterns(); | |
40 | |
41 // Appends the IDs of regular expressions in our set that match the |text| | |
42 // to |matches|. | |
43 bool Match(const std::string& text, | |
44 std::set<StringPattern::ID>* matches) const; | |
45 | |
46 private: | |
47 typedef int RE2ID; | |
48 typedef std::map<StringPattern::ID, const StringPattern*> RegexMap; | |
49 typedef std::vector<StringPattern::ID> RE2IDMap; | |
50 | |
51 // Use Aho-Corasick SubstringSetMatcher to find which literal patterns | |
52 // match the |text|. | |
53 std::vector<RE2ID> FindSubstringMatches(const std::string& text) const; | |
54 | |
55 // Rebuild FilteredRE2 from scratch. Needs to be called whenever | |
56 // our set of regexes changes. | |
57 // TODO(yoz): investigate if it could be done incrementally; | |
58 // apparently not supported by FilteredRE2. | |
59 void RebuildMatcher(); | |
60 | |
61 // Clean up StringPatterns in |substring_patterns_|. | |
62 void DeleteSubstringPatterns(); | |
63 | |
64 // Mapping of regex IDs to regexes. | |
65 RegexMap regexes_; | |
66 // Mapping of IDs from FilteredRE2 (which are assigned in order) | |
battre
2012/09/12 18:04:50
nit: Mapping of RE2IDs from ...
Yoyo Zhou
2012/09/12 20:25:56
Done. Expanded "regex IDs" to "regex StringPattern
| |
67 // to regex IDs. | |
68 RE2IDMap re2_id_map_; | |
69 | |
70 scoped_ptr<re2::FilteredRE2> filtered_re2_; | |
71 scoped_ptr<SubstringSetMatcher> substring_matcher_; | |
72 | |
73 // The substring patterns from FilteredRE2, which are used in | |
74 // |substring_matcher_| but whose lifetime is managed here. | |
75 std::vector<const StringPattern*> substring_patterns_; | |
76 }; | |
77 | |
78 } // namespace extensions | |
79 | |
80 #endif // CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_ | |
OLD | NEW |