Speed improvements to SubstringSetMatcher

Speed improvements to SubstringSetMatcher 

This is a 2nd attempt to reland https://codereview.chromium.org/14780003/ which was reverted as https://codereview.chromium.org/15045002/, relanded as https://codereview.chromium.org/15059003 and reverted again as https://codereview.chromium.org/15027007/.

Patch set 1 here is identical with p.s. 2 in https://codereview.chromium.org/15059003.

This time it failed on Win XP debug bot's unit_tests, throwing assertions related to sorting patterns in the SubstringSetMatcher:
c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(3657) : Assertion failed: invalid operator<
c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xstring(78) : Assertion failed: string iterator not dereferencable
c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\xstring(79) : Assertion failed: "Standard C++ Libraries Out of Range" && 0

Affected unit tests: SubstringSetMatcherTest.TestMatcher and WebRequestRulesRegistryTest.GetMatchesCheckFulfilled



History of previous descriptions:

This is an attempt to reland https://codereview.chromium.org/14780003/ which was reverted as https://codereview.chromium.org/15045002/. 
Patch set 1 here is identical with p.s. 7 in https://codereview.chromium.org/14780003/. The failing buildbot was linux compile (dbg), so trying it here explicitly. 

Original description: 

The main one is coputing the Aho-Corasick tree size in advance. 

Also contained are code clean-ups and minor optimisations, like removing HasEdge/GetEdge sequences, or adding const to aid compiler optimisations. 

This was tested on a benchmark adding 20k+ patterns. It showed a reduction of the running time by 30%. 

BUG=236368
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=200253

[vabr (Chromium), 2013-05-15 06:58:59]

Hi Dominic,

Could you please take a quick look?
Note that you have already reviewed this (see the description for links to the
CLs), the only new thing is diff of PS2 versus PS1:
https://codereview.chromium.org/15027008/diff2/1:7001/extensions/common/match...

Thanks,
Vaclav

[vabr (Chromium), 2013-05-15 07:04:16]

https://codereview.chromium.org/15027008/diff/1/extensions/common/matcher/sub...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/15027008/diff/1/extensions/common/matcher/sub...
extensions/common/matcher/substring_set_matcher.cc:19: return a->pattern() <=
b->pattern();
This needs to be strict, otherwise the sort is not stable:
http://support.microsoft.com/kb/949171

https://codereview.chromium.org/15027008/diff/1/extensions/common/matcher/sub...
extensions/common/matcher/substring_set_matcher.cc:170: uint32 edge_from_current
= tree_[current_node].GetEdge(*i);
Here I indeed dereferenced an invalid iterator if |text| was empty. Wondering
how come only Win dbg showed that...

[battre, 2013-05-15 07:24:09]

Cool. LGTM.

[commit-bot: I haz the power, 2013-05-15 07:32:08]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/vabr@chromium.org/15027008/7001

[commit-bot: I haz the power, 2013-05-15 13:21:44]

Change committed as 200253