Save failure function to FlatBuffer.

Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
Committed: https://crrev.com/37fe37e9232fe2571650e8a7ab370d1ec554059a
Cr-Commit-Position: refs/heads/master@{#405986}

[pkalinnikov, 2016-07-15 11:36:55]

Description was changed from

==========
Add type parameter to KMP and fuzzy matching tools.

BUG=609747
==========

to

==========
Add type parameter to KMP, fuzzy and URL pattern matching.

The introduces IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

[pkalinnikov, 2016-07-15 11:36:56]

pkalinnikov@chromium.org changed reviewers:
+ engedy@chromium.org

[pkalinnikov, 2016-07-15 11:37:33]

Description was changed from

==========
Add type parameter to KMP, fuzzy and URL pattern matching.

The introduces IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

to

==========
Add type parameter to KMP, fuzzy and URL pattern matching.

The introduced IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

[pkalinnikov, 2016-07-15 11:52:35]

Description was changed from

==========
Add type parameter to KMP, fuzzy and URL pattern matching.

The introduced IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

to

==========
Save failure function to FlatBuffer.

Add type parameter to KMP, fuzzy and URL pattern matching. The introduced
IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

[pkalinnikov, 2016-07-15 11:54:06]

Description was changed from

==========
Save failure function to FlatBuffer.

Add type parameter to KMP, fuzzy and URL pattern matching. The introduced
IntType template parameter denotes the type of the failure
function elements. Use uint8_t to store failure functions of URL patterns in the
FlatBuffer.

BUG=609747
==========

to

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools.  The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

[pkalinnikov, 2016-07-15 11:54:16]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[pkalinnikov, 2016-07-15 11:54:24]

PTAL.

[commit-bot: I haz the power, 2016-07-15 11:54:36]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2016-07-15 11:55:43]

Description was changed from

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools.  The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

to

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

[pkalinnikov, 2016-07-15 11:58:51]

https://codereview.chromium.org/2153743002/diff/30001/components/subresource_...
File components/subresource_filter/core/common/indexed_ruleset.cc (right):

https://codereview.chromium.org/2153743002/diff/30001/components/subresource_...
components/subresource_filter/core/common/indexed_ruleset.cc:30: if
(rule.url_pattern().size() >=
selfnit: replace ">=" by ">".

[pkalinnikov, 2016-07-15 12:11:10]

Patchset #4 (id:50001) has been deleted

[pkalinnikov, 2016-07-15 12:11:35]

https://codereview.chromium.org/2153743002/diff/30001/components/subresource_...
File components/subresource_filter/core/common/indexed_ruleset.cc (right):

https://codereview.chromium.org/2153743002/diff/30001/components/subresource_...
components/subresource_filter/core/common/indexed_ruleset.cc:30: if
(rule.url_pattern().size() >=
On 2016/07/15 11:58:51, pkalinnikov wrote:
> selfnit: replace ">=" by ">".

Done.

[pkalinnikov, 2016-07-15 12:11:42]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-15 12:11:56]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2016-07-15 12:23:53]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-15 12:24:07]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-15 13:35:29]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-15 13:35:30]

Dry run: Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[pkalinnikov, 2016-07-15 14:08:30]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-15 14:08:54]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-15 15:26:47]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-15 15:26:50]

Dry run: Try jobs failed on following builders:
  linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)

[pkalinnikov, 2016-07-15 15:42:20]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-15 15:42:56]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-15 16:49:46]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-15 16:49:49]

Dry run: This issue passed the CQ dry run.

[engedy, 2016-07-18 10:47:17]

LGTM % comments.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:78: template
<typename IntType>
The name `IntType` is a bit too generic and does not make it is not very clear
what purpose the type serves. I would suggest capturing the semantic meaning in
the name, and maybe adding a static_assert if we want to enforce it is an
integral type.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/indexed_ruleset.cc (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/indexed_ruleset.cc:32: // The URL
pattern is too long.
This comment does not provide much information as it is. Could you please
explain here in what sense the pattern is too long and why this matters?

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/knuth_morris_pratt.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/knuth_morris_pratt.h:46:
DCHECK_LE(pattern.size(),
Can you please do a bit of investigation of the code this macro expands to, and
see what conversions will be performed? If it is safe to do so, it would be nice
if we could avoid the explicit casts.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_matching.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:66: //
-----------------------------------------------------------------------------
For clarity, could you please add a section above as well, and name these
sections, like:

// Public interface declaration -----...

// Implementation ---...

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:78: return
*AllOccurrencesFuzzy<IntType>(text, subpattern, failure).begin();
Although you haven't changed this, but caught my eye: can you please either
check end() here, or document in AllOccurrencesFuzzy the behavior of derefing
begin() in case there are no matches?

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:81: }  //
namespace
nit: namespace impl

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:163:
CHECK(failure_begin + subpattern.size() <= failure_end);
This is not new either, but this seems to be potentially creating an
out-of-bounds iterator. How about: failure_end - failure_begin >=
subpattern.size()?

[engedy, 2016-07-18 11:00:32]

In the long term, I would like us to think about how we could structure all this
logic a bit better.  What I would like to improve upon is to:
 -- have less duplicated static_asserts (and less DCHECKS),
 -- turn functions either into class members or let them take arguments of a
named type (e.g. have FailureArray instead of std::vector<IntType>), so it is
essentially obvious just from the types in which order and how the functions
need to be used, and very difficult to misuse them.
 -- have some central place where concrete types used by the current
implementation is defined.

[pkalinnikov, 2016-07-18 12:08:42]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[pkalinnikov, 2016-07-18 12:08:51]

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:78: template
<typename IntType>
On 2016/07/18 10:47:16, engedy wrote:
> The name `IntType` is a bit too generic and does not make it is not very clear
> what purpose the type serves. I would suggest capturing the semantic meaning
in
> the name, and maybe adding a static_assert if we want to enforce it is an
> integral type.

Done.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/indexed_ruleset.cc (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/indexed_ruleset.cc:32: // The URL
pattern is too long.
On 2016/07/18 10:47:16, engedy wrote:
> This comment does not provide much information as it is. Could you please
> explain here in what sense the pattern is too long and why this matters?

Done.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/knuth_morris_pratt.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/knuth_morris_pratt.h:46:
DCHECK_LE(pattern.size(),
On 2016/07/18 10:47:16, engedy wrote:
> Can you please do a bit of investigation of the code this macro expands to,
and
> see what conversions will be performed? If it is safe to do so, it would be
nice
> if we could avoid the explicit casts.

Done.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_matching.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:66: //
-----------------------------------------------------------------------------
On 2016/07/18 10:47:16, engedy wrote:
> For clarity, could you please add a section above as well, and name these
> sections, like:
> 
> // Public interface declaration -----...
> 
> // Implementation ---...

Done.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:78: return
*AllOccurrencesFuzzy<IntType>(text, subpattern, failure).begin();
On 2016/07/18 10:47:17, engedy wrote:
> Although you haven't changed this, but caught my eye: can you please either
> check end() here, or document in AllOccurrencesFuzzy the behavior of derefing
> begin() in case there are no matches?

Documented dereferencing out-of-range iterators.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:81: }  //
namespace
On 2016/07/18 10:47:16, engedy wrote:
> nit: namespace impl

Done.

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/url_pattern_matching.h:163:
CHECK(failure_begin + subpattern.size() <= failure_end);
On 2016/07/18 10:47:17, engedy wrote:
> This is not new either, but this seems to be potentially creating an
> out-of-bounds iterator. How about: failure_end - failure_begin >=
> subpattern.size()?

Done.

[commit-bot: I haz the power, 2016-07-18 12:08:54]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[engedy, 2016-07-18 12:12:46]

Still LGTM % nit. Thanks!

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/knuth_morris_pratt.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/knuth_morris_pratt.h:46:
DCHECK_LE(pattern.size(),
On 2016/07/18 12:08:51, pkalinnikov wrote:
> On 2016/07/18 10:47:16, engedy wrote:
> > Can you please do a bit of investigation of the code this macro expands to,
> and
> > see what conversions will be performed? If it is safe to do so, it would be
> nice
> > if we could avoid the explicit casts.
> 
> Done.

Cool. Could you please do the same in other DCHECKs touched in this CL?

[pkalinnikov, 2016-07-18 12:39:34]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-18 12:39:46]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2016-07-18 12:40:31]

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
File components/subresource_filter/core/common/knuth_morris_pratt.h (right):

https://codereview.chromium.org/2153743002/diff/90001/components/subresource_...
components/subresource_filter/core/common/knuth_morris_pratt.h:46:
DCHECK_LE(pattern.size(),
On 2016/07/18 12:12:46, engedy wrote:
> On 2016/07/18 12:08:51, pkalinnikov wrote:
> > On 2016/07/18 10:47:16, engedy wrote:
> > > Can you please do a bit of investigation of the code this macro expands
to,
> > and
> > > see what conversions will be performed? If it is safe to do so, it would
be
> > nice
> > > if we could avoid the explicit casts.
> > 
> > Done.
> 
> Cool. Could you please do the same in other DCHECKs touched in this CL?

Done.

[engedy, 2016-07-18 12:46:49]

Thanks, LGTM.

[pkalinnikov, 2016-07-18 12:47:24]

The CQ bit was checked by pkalinnikov@chromium.org

[commit-bot: I haz the power, 2016-07-18 12:47:34]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-18 14:43:43]

Description was changed from

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

to

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

[commit-bot: I haz the power, 2016-07-18 14:43:45]

Committed patchset #8 (id:150001)

[commit-bot: I haz the power, 2016-07-18 14:44:46]

Description was changed from

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747
==========

to

==========
Save failure function to FlatBuffer.

Add template type parameter to KMP, fuzzy and URL pattern matching tools. The
introduced IntType parameter denotes the type of the failure function elements.
Use uint8_t to store failure functions of URL patterns in the FlatBuffer.

BUG=609747

Committed: https://crrev.com/37fe37e9232fe2571650e8a7ab370d1ec554059a
Cr-Commit-Position: refs/heads/master@{#405986}
==========

[commit-bot: I haz the power, 2016-07-18 14:44:47]

Patchset 8 (id:??) landed as
https://crrev.com/37fe37e9232fe2571650e8a7ab370d1ec554059a
Cr-Commit-Position: refs/heads/master@{#405986}