Implementation of a Matching strategy for URLs in the Declarative WebRequest API.

Implementation of a Matching strategy for URLs in the Declarative WebRequest API.

The Declarative WebRequest API needs to be able to match each outgoing
URLRequest against a large set of rules. This CL lays the foundation for this.
URLRequests can be matched using various criteria (e.g. "hostname ends in
foobar.com", or "URL contains 'secret'", or both). In order to match many of
these patterns very quickly we want to rely on the Aho-Corasick algorithm.

This CL is one step before the A.-C. algorithm: It implements the reduction of
URL Pattern matches to that of Substring matches. The SubstringSetMatcher is
implemented trivially and will be replaced with a A.-C. implementation in a
second CL.

BUG=112155
TEST=no


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=122503

[battre, 2012-02-13 21:39:26]

Hi,

may I ask you to review this CL, please?

The CL is pretty large (~1700 LoC), so I recommend to review it in the following
order:

- substring_set_matcher: The foundation, search for many substrings in one
string. This solves the problem "Find foobar.com in a string".

- url_component_patterns: Maps URL Pattern searches to the problem of finding
substrings in a string. This solves the problem "Find a hostname suffix
'foobar.com' in a GURL using substring search".

- url_matcher: Allows searching many URL Patterns as well as combinations
(conjunctions) of URL Patterns in a URL. This solves the problem "Determine
whether a GURL contains a hostname suffix 'foobar.com' plus at the same time an
occurrence of 'index.html' in the path.".

The CL is complicated because various elements contain IDs but I think if you
review it in this order, it makes sense.

The CL omits two big parts:

- The substring_set_matcher implementation is slow, I wanted to implement this
before the Aho-Corasick algorithm because I saw this as a bigger risk in my
design. (I know that Aho-Corasick can be implemented but I was not sure whether
the URLPattern->Substring matching reduction would work).

- The url_matcher is not hooked into the Declarative WebRequest API. This is
currently blocked on https://chromiumcodereview.appspot.com/9309044/. I decided
to continue the development bottom-up instead of waiting for that CL. There
might be some refactoring necessary to this CL depending on how we solve the
multi-threading problem in the Declarative WebRequest API: On which thread do we
want to do the preprocessing? if it happens on the IO thread, we are good. If we
do it on a WorkerPool thread, we probably need to follow a different approach,
where each modification instantiates a new url_matcher. Anyway, I think this
does not need to block this CL and we can do any refactoring later, if it is
necessary.

I think that this approach allows for a very fast implementation of the
WebRequest API. I validated the approach against the EasyList rules of AdBlock.

This is an example mapping of an AdBlock rule to the logic of this CL:
||example.com/images/*/webadverts/  ->  host_suffix(.example.com),
path_prefix(images/), url_contains(/webadverts/)

Note that we lose a tiny bit of precision here: For any content after a "*", we
have to rely on url_contains(). I.e. a pattern "/foo/*/bar/*/baz" will be mapped
to url_contains(/foo/), url_contains(/bar/), url_contains(/baz) and would match
also "/bar/_/foo/_/baz". But I think for practical purposes this is reasonable.

Please let me know if you have questions and want to resolve them in a VC.

Thanks and best regards,
Dominic

[Matt Perry, 2012-02-14 01:38:34]

How much memory do the EasyList strings take up? This implementation results in
a lot of duplication - at least 4x the size of all the strings, by my count:
1-2. URLComponentPatterns contains a map of pattern string -> pattern string,
which is 2x the string size already.
3. Each URLMatcherCondition contains a copy of of the substring pattern
contained in URLComponentPatterns.
4. URLMatcherCondition also contains the raw string value that the pattern was
generated from.

I also find the layering of the classes a bit weird. URLComponentPatterns is
useless without the layer above it that handles the special-case matching of
hosts and such.

What do you think of the following:
1. Move URLComponentPatterns up a layer, so that it creates URLMatcherConditions
rather than raw SubstringPatterns. These should then have all the proper logic
to handle URL component matching, like host_contains() and scheme/port matching
(the latter of which seems to be missing?).
2. Have URLMatcherConditions contain a pointer/reference to the
SubstringPatterns rather than a copy. It's invalid for an URLMatcherCondition to
exist without a SubstringPattern.
3. Stop storing the raw value in URLMatcherCondition. For the cases where you
need the raw value (IsMatch with HOST_CONTAINS, etc), the SubstringPattern's
value is already the same string, so you can just compare that.
4. Replace URLComponentPatterns map of pattern_string->pattern with a
base::hash_set. This allows for fast lookup without duplicating the pattern in
the key.

---

The rest is more specific feedback, which may be rendered obsolete by the above.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File chrome/browser/extensions/api/declarative/substring_set_matcher.cc (right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/substring_set_matcher.cc:35: return
pattern_ == other.pattern_ && id_ == other.id_;
compare IDs first for speed?

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File chrome/browser/extensions/api/declarative/substring_set_matcher.h (right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/substring_set_matcher.h:22: // in a
string in the SubstringSetMatcher.
I don't really follow this comment. Could you add some more explanation how the
identifier is related to the pattern? If 2 pattern strings are the same, will
the ID be the same? Or is it just a unique ID?

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/substring_set_matcher.h:63:
std::vector<SubstringPattern> patterns_;
If it really stores sets, you should use std::set instead. Ditto for the
methods.

Also, nit: use a typedef for the container type.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File chrome/browser/extensions/api/declarative/url_component_patterns.cc
(right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:46: // this
is not guarantee to be ASCII-7 encoded.
guaranteed*

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:46: // this
is not guarantee to be ASCII-7 encoded.
Forgive my ignorance, but are you sure that URLs are ASCII-7 in practice? Might
want to run this approach by brettw to see if you're making the right
assumptions.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:86: // ->
path_equals("/index.html") = ED /index.html EP
nit: good examples, but IMO less is more. 1 or 2 examples for step 3 is enough
to convey the idea.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:137: char
BEGINNING_OF_URL[] = {128, 0};
style: const char kBeginningOfURL[] = {128, 0};
and so on

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:247: if
(StartsWithASCII(hostname, ".", true))
nit: for this simple test, I'd just check hostname[0] == '.'

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File chrome/browser/extensions/api/declarative/url_component_patterns.h (right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.h:28: //
"/index.html" but the path of the URL does not start with "/index.html".
Typo: your example contains /images.html :)

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.h:34: class
UrlComponentPatterns {
Chrome style is to capitalize acronyms in class/method names:
URLComponentPatterns.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.h:87:
std::string CanonicalizeHostname(const std::string hostname) const;
missing ref on parameter

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns.h:90:
std::map<std::string, SubstringPattern> pattern_singletons_;
Please add a comment about what the key in this map represents.

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc
(right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:54:
EXPECT_TRUE(Matches(matcher.CreateHostPrefixPattern(""), url));
nit: take a look at EXPECT_PRED2, which I believe will output the parameters in
the event of a failure. Example:
http://code.google.com/codesearch#OAMlx_jo-ck/src/ui/base/clipboard/clipboard...

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:60:
EXPECT_FALSE(Matches(matcher.CreateHostPrefixPattern("webhp"), url));
Test that "google.com" does not match. In general, you could use more tests that
verify the URL component markers are being respected (e.g. below,
host_suffix("www") and path_prefix("webhp") do not match).

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:131:
EXPECT_FALSE(Matches(matcher.CreateHostPrefixPattern("webhp"), url));
did you mean CreateURLPrefixPattern?

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:144:
EXPECT_FALSE(Matches(matcher.CreateURLSuffixPattern("foobar"), url));
also test that url_contains("search") does not match (to verify #ref part is
stripped).

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_matcher.h:29: // between a
SubstringPattern created by UrlComponentPatterns is that also
s/between/from
"is that this* also"

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_matcher.h:32: class
UrlMatcherCondition {
URLMatcherCondition

https://chromiumcodereview.appspot.com/9390018/diff/1/chrome/browser/extensio...
chrome/browser/extensions/api/declarative/url_matcher.h:56:
UrlMatcherCondition(Criterion criterion, std::string value);
pass const-ref

[battre, 2012-02-14 19:32:20]

I will send a separate email for the refactoring.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File chrome/browser/extensions/api/declarative/substring_set_matcher.cc (right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/substring_set_matcher.cc:35: return
pattern_ == other.pattern_ && id_ == other.id_;
On 2012/02/14 01:38:34, Matt Perry wrote:
> compare IDs first for speed?

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File chrome/browser/extensions/api/declarative/substring_set_matcher.h (right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/substring_set_matcher.h:22: // in a
string in the SubstringSetMatcher.
On 2012/02/14 01:38:34, Matt Perry wrote:
> I don't really follow this comment. Could you add some more explanation how
the
> identifier is related to the pattern? If 2 pattern strings are the same, will
> the ID be the same? Or is it just a unique ID?

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/substring_set_matcher.h:63:
std::vector<SubstringPattern> patterns_;
On 2012/02/14 01:38:34, Matt Perry wrote:
> If it really stores sets, you should use std::set instead. Ditto for the
> methods.
> 
> Also, nit: use a typedef for the container type.

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File chrome/browser/extensions/api/declarative/url_component_patterns.cc
(right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:46: // this
is not guarantee to be ASCII-7 encoded.
On 2012/02/14 01:38:34, Matt Perry wrote:
> guaranteed*

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:46: // this
is not guarantee to be ASCII-7 encoded.
On 2012/02/14 01:38:34, Matt Perry wrote:
> Forgive my ignorance, but are you sure that URLs are ASCII-7 in practice?
Might
> want to run this approach by brettw to see if you're making the right
> assumptions.

According to GURL::spec():

  // Returns the raw spec, i.e., the full text of the URL, in canonical UTF-8,
  // if the URL is valid. If the URL is not valid, this will assert and return
  // the empty string (for safety in release builds, to keep them from being
  // misused which might be a security problem).
  //
  // The URL will be ASCII except the reference fragment, which may be UTF-8.
  // It is guaranteed to be valid UTF-8.

I added this unit test:

TEST(URLComponentPatternsTest, GURLCharacterSet) {
  // GURL guarantees that neither domain, nor path, nor query may contain
  // non ASCII-7 characters. We test this here, because a change to this
  // guarantee breaks this implementation horribly.
  GURL url("http://www.föö.com/föö?föö#föö");
  EXPECT_TRUE(IsStringASCII(url.host()));
  EXPECT_TRUE(IsStringASCII(url.path()));
  EXPECT_TRUE(IsStringASCII(url.query()));
  EXPECT_FALSE(IsStringASCII(url.ref()));
}

url.host() returns the punycode version of the host. path() and query() return
URL encoded characters. This also verifies that this is not ASCII-8, because ö
can be represented in ASCII-8 (see e.g.
http://homepage.cs.uri.edu/faculty/wolfe/book/Readings/R02%20Ascii/completeAS...)

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:86: // ->
path_equals("/index.html") = ED /index.html EP
On 2012/02/14 01:38:34, Matt Perry wrote:
> nit: good examples, but IMO less is more. 1 or 2 examples for step 3 is enough
> to convey the idea.

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:137: char
BEGINNING_OF_URL[] = {128, 0};
On 2012/02/14 01:38:34, Matt Perry wrote:
> style: const char kBeginningOfURL[] = {128, 0};
> and so on

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.cc:247: if
(StartsWithASCII(hostname, ".", true))
On 2012/02/14 01:38:34, Matt Perry wrote:
> nit: for this simple test, I'd just check hostname[0] == '.'

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File chrome/browser/extensions/api/declarative/url_component_patterns.h (right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.h:28: //
"/index.html" but the path of the URL does not start with "/index.html".
On 2012/02/14 01:38:34, Matt Perry wrote:
> Typo: your example contains /images.html :)

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.h:34: class
UrlComponentPatterns {
On 2012/02/14 01:38:34, Matt Perry wrote:
> Chrome style is to capitalize acronyms in class/method names:
> URLComponentPatterns.

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.h:87:
std::string CanonicalizeHostname(const std::string hostname) const;
On 2012/02/14 01:38:34, Matt Perry wrote:
> missing ref on parameter

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns.h:90:
std::map<std::string, SubstringPattern> pattern_singletons_;
On 2012/02/14 01:38:34, Matt Perry wrote:
> Please add a comment about what the key in this map represents.

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc
(right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:54:
EXPECT_TRUE(Matches(matcher.CreateHostPrefixPattern(""), url));
On 2012/02/14 01:38:34, Matt Perry wrote:
> nit: take a look at EXPECT_PRED2, which I believe will output the parameters
in
> the event of a failure. Example:
>
http://code.google.com/codesearch#OAMlx_jo-ck/src/ui/base/clipboard/clipboard...

It does, but:
- It is one character longer per line.
- There is no equivalent to EXPECT_FALSE.
- It requires a std::basic_ostream::operator<<(const SubstringPattern*)

I am not sure whether this change would be a net win.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:60:
EXPECT_FALSE(Matches(matcher.CreateHostPrefixPattern("webhp"), url));
On 2012/02/14 01:38:34, Matt Perry wrote:
> Test that "google.com" does not match. In general, you could use more tests
that
> verify the URL component markers are being respected (e.g. below,
> host_suffix("www") and path_prefix("webhp") do not match).

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:131:
EXPECT_FALSE(Matches(matcher.CreateHostPrefixPattern("webhp"), url));
On 2012/02/14 01:38:34, Matt Perry wrote:
> did you mean CreateURLPrefixPattern?

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_component_patterns_unittest.cc:144:
EXPECT_FALSE(Matches(matcher.CreateURLSuffixPattern("foobar"), url));
On 2012/02/14 01:38:34, Matt Perry wrote:
> also test that url_contains("search") does not match (to verify #ref part is
> stripped).

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_matcher.h:29: // between a
SubstringPattern created by UrlComponentPatterns is that also
On 2012/02/14 01:38:34, Matt Perry wrote:
> s/between/from
> "is that this* also"

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_matcher.h:32: class
UrlMatcherCondition {
On 2012/02/14 01:38:34, Matt Perry wrote:
> URLMatcherCondition

Done.

http://codereview.chromium.org/9390018/diff/1/chrome/browser/extensions/api/d...
chrome/browser/extensions/api/declarative/url_matcher.h:56:
UrlMatcherCondition(Criterion criterion, std::string value);
On 2012/02/14 01:38:34, Matt Perry wrote:
> pass const-ref

Done.

[battre, 2012-02-14 19:45:37]

This is a refactored version of the CL that should safe a significant amount of
memory. I am curious what you think of this, because it got somewhat more
complicated in my opinion.

This is the new memory structure:
- URLMatcherCondition has a weak ref to SubstringPattern
- URLMatcherConditionFactory creates URLMatcherConditions and owns their
SubstringPatterns
- URLMatcherConditionSet owns URLMatcherConditions
- URLMatcher owns URLMatcherConditionSet, the URLMatcherConditionFactory and two
SubstringSetMatchers.

SubstringSetMatcher has weak references to SubstringPatterns.

Initially I tried to give the ownership of the SubstringPatterns to the
SubstringSetMatcher but that turned out to be difficult because we want to allow
creating SubstringPatterns without registering them to the SubstringSetMatcher
at the same time.


Please let me know what you think of this memory model. The CL requires some
polishing: I have not refactored all old unit tests, yet, for example. But I
would like to get your opinion before investing time in the polishing.


If you have a creative idea on how to pass ownership of vectors of pointers, I'd
be curious to hear it. For the ownership of a single pointer, I think it is now
considered best practice to pass a scoped_ptr<T> parameter. I don't see how this
should be done for a vector of pointers. I have chosen
scoped_ptr<ScopedVector<T*>> but this looks pretty cumbersome. We could pass a
ScopedVector<T*>* or (non-const) ScopedVector<T*>&.

Thanks,
Dominic

[Matt Perry, 2012-02-14 19:56:16]

I think the transition to scoped_ptr and linked_ptr everywhere is unnecessary.
SubstringPattern is the only thing you want to avoid duplicating. Have one class
own the list of them, and have every other class keep a const-ref or const-ptr
to them. URLMatcherCondition can be copied and duplicated since it is now so
lightweight.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:109:
scoped_ptr<URLMatcherCondition> CreateHostPrefixCondition(
An URLMatcherCondition is now just a Criterion and a pointer to a
SubstringPattern. It's fine to pass copies of those around. No need to return a
pointer here.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:186: typedef
ScopedVector<const URLMatcherCondition> Conditions;
Likewise, this is overkill. Just make it a std::set<URLMatcherCondition>.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:209:
scoped_ptr<ScopedVector<const URLMatcherConditionSet> > condition_sets);
Ditto, overkill. Pass by const ref.

[Matt Perry, 2012-02-14 20:47:47]

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:178: PatternSingletons
pattern_singletons_;
Also, this should use a set, or a hash_set if you need fast lookup. That way the
pattern is not duplicated between keys and values.

[battre, 2012-02-14 21:56:42]

Still needs more polish, but the proposed modifications to use a base::hash_set
in one place and a std::set in the other  work.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:109:
scoped_ptr<URLMatcherCondition> CreateHostPrefixCondition(
On 2012/02/14 19:56:16, Matt Perry wrote:
> An URLMatcherCondition is now just a Criterion and a pointer to a
> SubstringPattern. It's fine to pass copies of those around. No need to return
a
> pointer here.

Done.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:178: PatternSingletons
pattern_singletons_;
On 2012/02/14 20:47:47, Matt Perry wrote:
> Also, this should use a set, or a hash_set if you need fast lookup. That way
the
> pattern is not duplicated between keys and values.

Done.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:186: typedef
ScopedVector<const URLMatcherCondition> Conditions;
On 2012/02/14 19:56:16, Matt Perry wrote:
> Likewise, this is overkill. Just make it a std::set<URLMatcherCondition>.

Done.

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:209:
scoped_ptr<ScopedVector<const URLMatcherConditionSet> > condition_sets);
On 2012/02/14 19:56:16, Matt Perry wrote:
> Ditto, overkill. Pass by const ref.

Done.

[Matt Perry, 2012-02-14 23:52:25]

There is a significant amount of logic to handle the case of identical
SubstringPatterns. Do you think that this will happen often enough that it's
worth optimizing for? Can you give an example of where we'd benefit from this
optimization?

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/6013/chrome/browser/extensions/ap...
chrome/browser/extensions/api/declarative/url_matcher.h:213:
std::set<URLMatcherConditionSet::ID> MatchUrl(const GURL& url);
MatchURL

[battre, 2012-02-15 18:05:01]

Hi Matt,

I have cleaned the CL. I think it is polished and feature complete now. Please
review it again.

Regarding your question of preventing duplicate SubstringPatterns. I am
concerned about a usecase, where we will have plenty of rules of the form:
host_suffix("mywebsite.com"), path_contains(path1)
host_suffix("mywebsite.com"), path_contains(path2)
host_suffix("mywebsite.com"), path_contains(path3)
host_suffix("mywebsite.com"), path_contains(path4)

These sets of rules can occur in several scenarios like providing HTTP Auth
credentials or white listing pages from AdBlock. If there are many (say 100) of
these rules, I am concerned that this starts showing in the performance.

If you open a website on "mywebsite.com" containing 100 resources, we are
dealing with 100 requests and each of these generates 100 matches according to
the condition sets above. I.e. we would test 10.000 times whether the respective
paths occurred in the URLs as well.

With the current strategy, we would generate only one match for
host_suffix("mywebsite.com"), i.e. there is less data that is passed from the
SubsetMatcher to the URLMatcher. But further more, we see that
host_suffix("mywebsite.com") occurs very frequently. Therefore, it would not be
used as a trigger for validating the URLMatcherConditionSets.

So... TL;DR: I am not 100% sure whether the current filtering of duplicate
SubstringPatterns pays off but I think there are scenarios where it does. I
would leave it in.

Best regards,
Dominic

[Matt Perry, 2012-02-15 22:45:17]

Getting close.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher.cc (right):

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:460: // Build the union
of both result sets.
Rather than doing this as a separate step, just pass the same set into both
matchers. Add a comment to the Match() method that says the set is not cleared
before adding to it (which is already the case - just make it explicit).

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:484:
result.insert(url_matcher_condition_sets_[*j].id());
Isn't *j the ID?

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:565: //
URLMatcherCondition occurs least frequently in this URLMatcher. We assume
s/URLMatcherCondition/SubstringPattern, right?

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:112: std::string
CanonlicalizeURLForComponentSearches(const GURL& url);
typo: Canonicalize*

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:138: std::string
CanonlicalizeURLForFullSearches(const GURL& url);
ditto typo

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:249: // be triggered in
case of a SubstringPatter match.
SubstringPattern*

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher_unittest.cc (right):

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher_unittest.cc:287:
TEST(URLMatcherConditionSetTest, Constructors) {
This kind of test is overkill IMO. It's basically testing that assignment worked
correctly. That sort of thing is implicitly covered by the more involved tests
later.

[battre, 2012-02-16 14:45:55]

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher.cc (right):

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:460: // Build the union
of both result sets.
On 2012/02/15 22:45:18, Matt Perry wrote:
> Rather than doing this as a separate step, just pass the same set into both
> matchers. Add a comment to the Match() method that says the set is not cleared
> before adding to it (which is already the case - just make it explicit).

Done.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:484:
result.insert(url_matcher_condition_sets_[*j].id());
On 2012/02/15 22:45:18, Matt Perry wrote:
> Isn't *j the ID?

Done.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.cc:565: //
URLMatcherCondition occurs least frequently in this URLMatcher. We assume
On 2012/02/15 22:45:18, Matt Perry wrote:
> s/URLMatcherCondition/SubstringPattern, right?

Done.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher.h (right):

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:112: std::string
CanonlicalizeURLForComponentSearches(const GURL& url);
On 2012/02/15 22:45:18, Matt Perry wrote:
> typo: Canonicalize*

Done.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:138: std::string
CanonlicalizeURLForFullSearches(const GURL& url);
On 2012/02/15 22:45:18, Matt Perry wrote:
> ditto typo

Done.

http://codereview.chromium.org/9390018/diff/13001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher.h:249: // be triggered in
case of a SubstringPatter match.
On 2012/02/15 22:45:18, Matt Perry wrote:
> SubstringPattern*

Done.

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher_unittest.cc (right):

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher_unittest.cc:287:
TEST(URLMatcherConditionSetTest, Constructors) {
On 2012/02/15 22:45:18, Matt Perry wrote:
> This kind of test is overkill IMO. It's basically testing that assignment
worked
> correctly. That sort of thing is implicitly covered by the more involved tests
> later.

Hm, are you sure whether the rest of the code uses the copy constructor or
operator=? I think if you don't feel strongly against it, it is nice to have
explicit full coverage.

[Matt Perry, 2012-02-16 19:25:46]

LGTM. (Aaron said you can commit with just my LGTM. He'll take a look later.)

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
File chrome/browser/extensions/api/declarative/url_matcher_unittest.cc (right):

http://codereview.chromium.org/9390018/diff/18001/chrome/browser/extensions/a...
chrome/browser/extensions/api/declarative/url_matcher_unittest.cc:287:
TEST(URLMatcherConditionSetTest, Constructors) {
On 2012/02/16 14:45:55, battre wrote:
> On 2012/02/15 22:45:18, Matt Perry wrote:
> > This kind of test is overkill IMO. It's basically testing that assignment
> worked
> > correctly. That sort of thing is implicitly covered by the more involved
tests
> > later.
> 
> Hm, are you sure whether the rest of the code uses the copy constructor or
> operator=? I think if you don't feel strongly against it, it is nice to have
> explicit full coverage.

Those are used implicitly by the STL containers (which I presume is why you
defined them in the first place). But, suit yourself :)

[commit-bot: I haz the power, 2012-02-17 12:42:36]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/battre@chromium.org/9390018/22003

[commit-bot: I haz the power, 2012-02-17 14:05:45]

Change committed as 122503