Event matching by regular expression matching on URLs.

chrome/common/extensions/matcher/regex_set_matcher.h

+// Copyright (c) 2012 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 CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_
+#define CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_
+
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "base/memory/scoped_ptr.h"
+#include "chrome/common/extensions/matcher/string_pattern.h"
+#include "chrome/common/extensions/matcher/substring_set_matcher.h"
+
+namespace re2 {
+class FilteredRE2;
+}
+
+namespace extensions {
+
+// Efficiently matches URLs against a collection of regular expressions,
+// using FilteredRE2 to reduce the number of regexes that must be matched
+// by pre-filtering with substring matching. See:
+// http://swtch.com/~rsc/regexp/regexp3.html#analysis
+class RegexSetMatcher {
+ public:
+  RegexSetMatcher();
+  virtual ~RegexSetMatcher();
+
+  // Adds the regex patterns in |regex_list| to the matcher. Also rebuilds
+  // the FilteredRE2 matcher; thus, for efficiency, prefer adding multiple
+  // patterns at once.

[battre, 2012/09/11 21:49:48]

I think for consistency to SubStringMatcher, the ownership of the StringPatterns
should remain with the caller. (or it should be changed there as well)

[Yoyo Zhou, 2012/09/11 22:35:37]

It does. This is perhaps confusing -- the regex patterns are managed in
UrlMatcher's regex_pattern_singletons_ -- so I should add a note.

+  void AddPatterns(const std::vector<const StringPattern*>& regex_list);
+
+  // Removes all regex patterns.
+  void ClearPatterns();
+
+  // Appends the IDs of regular expressions in our set that match the |text|
+  // to |matches|.
+  bool Match(const std::string& text,
+             std::set<StringPattern::ID>* matches) const;
+
+ private:
+  // Use Aho-Corasick SubstringSetMatcher to find which literal patterns
+  // match the |text|.
+  std::vector<int> FindSubstringMatches(const std::string& text) const;

[battre, 2012/09/11 21:49:48]

int -> StringPattern::ID? I am not sure whether this is really a
StringPattern::ID. I think it is useful to distinguish the IDs by typedefs.

[Yoyo Zhou, 2012/09/11 22:35:37]

These ints are the FilteredRE2 IDs. I can make a typedef for those.

+
+  // Rebuild FilteredRE2 from scratch. Needs to be called whenever
+  // our set of regexes changes.
+  // TODO(yoz): investigate if it could be done incrementally;
+  // apparently not supported by FilteredRE2.
+  void RebuildMatcher();
+
+  // Clean up StringPatterns in |substring_patterns_|.
+  void DeleteSubstringPatterns();
+
+  // Mapping of regex IDs to regexes.
+  typedef std::map<StringPattern::ID, const StringPattern*> RegexMap;
+  // Mapping of IDs from FilteredRE2 (which are assigned in order)
+  // to regex IDs.
+  typedef std::vector<StringPattern::ID> RE2IdMap;
+  RegexMap regexes_;
+  RE2IdMap re2_id_map_;
+
+  scoped_ptr<re2::FilteredRE2> filtered_re2_;
+  scoped_ptr<SubstringSetMatcher> substring_matcher_;
+
+  // The substring patterns from FilteredRE2, which are used in
+  // |substring_matcher_| but whose lifetime is managed here.

[battre, 2012/09/11 21:49:48]

doesn't lifetime management imply that we delete the objects?

[Yoyo Zhou, 2012/09/11 22:35:37]

DeleteSubstringPatterns does that.

+  std::vector<const StringPattern*> substring_patterns_;
+};
+
+}  // namespace extensions
+
+#endif  // CHROME_COMMON_EXTENSIONS_MATCHER_REGEX_SET_MATCHER_H_