[3 of 4] Speedup GetRegistryLengthImpl() by seeding the DAFSA in reverse

Speedup GetRegistryLengthImpl() by seeding the DAFSA in reverse.

Add an option to make_dafsa.py to reverse the input words during
encoding.

Adapt the implementation of GetRegistryLengthImpl to the
reverse-seeded DAFSA. The new implementation is more efficient,
because it needs to query the DAFSA only once.

Improve the documentation of GetRegistryLengthImpl, with links
to relevent steps of the pseudocode algorithm specified at
publicsuffix.org. Document the two places where we depart
from that spec (one is INCLUDE_UNKNOWN_DOMAINS being optional,
the other is the platform.sh problem).

Add a TODO regarding empty-label matches.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334

[ncarter (slow), 2017-01-24 15:27:01]

Description was changed from

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

[comment on effect on dafsa size]

RegistryControlledDomainTest.GetDomainAndRegistry 69ms
RegistryControlledDomainTest.SameDomainOrHost_Different 120ms
RegistryControlledDomainTest.SameDomainOrHost_Same 125ms

BUG=678334
==========

to

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

[comment on effect on dafsa size]

RegistryControlledDomainTest.GetDomainAndRegistry 69ms
RegistryControlledDomainTest.SameDomainOrHost_Different 120ms
RegistryControlledDomainTest.SameDomainOrHost_Same 125ms

BUG=678334
==========

[ncarter (slow), 2017-01-24 15:53:56]

Description was changed from

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

[comment on effect on dafsa size]

RegistryControlledDomainTest.GetDomainAndRegistry 69ms
RegistryControlledDomainTest.SameDomainOrHost_Different 120ms
RegistryControlledDomainTest.SameDomainOrHost_Same 125ms

BUG=678334
==========

to

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 69ms
RegistryControlledDomainTest.SameDomainOrHost_Different 120ms
RegistryControlledDomainTest.SameDomainOrHost_Same 125ms

BUG=678334
==========

[ncarter (slow), 2017-01-24 18:35:33]

Description was changed from

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 69ms
RegistryControlledDomainTest.SameDomainOrHost_Different 120ms
RegistryControlledDomainTest.SameDomainOrHost_Same 125ms

BUG=678334
==========

to

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334
==========

[Ryan Sleevi, 2017-01-25 22:13:25]

rsleevi@chromium.org changed reviewers:
+ rsleevi@chromium.org

[Ryan Sleevi, 2017-01-25 22:13:25]

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
File net/base/registry_controlled_domains/registry_controlled_domain.cc (right):

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:105: // as
part of a longer rule only?
"If no rules match, the prevailing rule is '*'"

I'm not sure how to interpret the second part of your question.

[ncarter (slow), 2017-01-26 00:33:02]

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
File net/base/registry_controlled_domains/registry_controlled_domain.cc (right):

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:105: // as
part of a longer rule only?
On 2017/01/25 22:13:25, Ryan Sleevi wrote:
> "If no rules match, the prevailing rule is '*'"
> 
> I'm not sure how to interpret the second part of your question.

Thanks for the clarification of the mapping between INCLUDE_UNKNOWN_REGISTRIES
and the "If no rules match, the prevailing rule is '*'" rule. That's what I had
gathered, but the comment elswhere about a "wildcard rule which would have to be
'*'" had me confused as to whether we did something different from the PSL spec
here.

The example I was getting at was is suppose the PSL contains the following
entries, but not a rule for "uk":

co.uk
ac.uk

My question was whether we return 0 or 2 for a lookup of "ltd.uk" in each
|unknown_filter| case.  Is "uk" considered a known registry because of its
appearance in the more specific co.uk rule? Or should we suppress the match for
of the implicit top-level '*' rule because of the existence of the more specific
co.uk rule?

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:120: //
there's a subdomain. Are there unittests of that behavior?
This TODO is about a concern I have with equivalence of new vs. old. In
particular, the old code had the following comment:

"""
Exception rules override wildcard rules when the domain is an exact match, but
wildcards take precedence when there's a subdomain.
"""

I'm not really sure how to interpret that; it sounds like it's different
behavior from the algorithm described on https://publicsuffix.org/list/, which
says that "An exception rule takes priority over any other matching rule."

If we assume a rule like:

 !pref.hokkaido.jp

Then the registry-controlled part of "www.zzz.pref.hokkaido.jp" ought to be
"hokkaido.jp", right, even if there also a rule of the form 
"*.pref.hokkaido.jp"?

[Ryan Sleevi, 2017-01-26 00:41:45]

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
File net/base/registry_controlled_domains/registry_controlled_domain.cc (right):

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:105: // as
part of a longer rule only?
On 2017/01/26 00:33:02, ncarter wrote:
> The example I was getting at was is suppose the PSL contains the following
> entries, but not a rule for "uk":
> 
> co.uk
> ac.uk
> 
> My question was whether we return 0 or 2 for a lookup of "ltd.uk" in each
> |unknown_filter| case.  

If INCLUDE_UNKNOWN_REGISTRIES is set, we return "uk" (wildcard match)
If INCLUDE_UNKNOWN_REGISTRIES is not set, then it should return nothing (no
match)

> Is "uk" considered a known registry because of its
> appearance in the more specific co.uk rule? 

Nope.

> Or should we suppress the match for
> of the implicit top-level '*' rule because of the existence of the more
specific
> co.uk rule?

Correct

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:120: //
there's a subdomain. Are there unittests of that behavior?
On 2017/01/26 00:33:02, ncarter wrote:
> This TODO is about a concern I have with equivalence of new vs. old. In
> particular, the old code had the following comment:
> 
> """
> Exception rules override wildcard rules when the domain is an exact match, but
> wildcards take precedence when there's a subdomain.
> """
> 
> I'm not really sure how to interpret that; it sounds like it's different
> behavior from the algorithm described on https://publicsuffix.org/list/, which
> says that "An exception rule takes priority over any other matching rule."

Yeah, I'm trying to figure out from the PSL maintainers their thought on better
clarifying how this works.

> 
> If we assume a rule like:
> 
>  !pref.hokkaido.jp
> 
> Then the registry-controlled part of "www.zzz.pref.hokkaido.jp" ought to be
> "hokkaido.jp", right, even if there also a rule of the form 
> "*.pref.hokkaido.jp"?

From the major implementations I'm aware of (although I'm still double
checking), my understanding is that if there were rules

!pref.hokkaido.jp
*.pref.hokkaido.jp

Then we'd actually return zzz.pref.hokkaido.jp

That is, the exception rule should only exclude the wildcard level for which it
applies.

[ncarter (slow), 2017-02-27 22:27:26]

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

[commit-bot: I haz the power, 2017-02-27 22:28:21]

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

[ncarter (slow), 2017-02-27 23:05:55]

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

[commit-bot: I haz the power, 2017-02-27 23:07:12]

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

[ncarter (slow), 2017-02-27 23:18:38]

Description was changed from

==========
Improve GetRegistryLengthImpl() performance by seeding the DAFSA in reverse.

This allows us to implement GetRegistryLengthImpl using just a single query.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334
==========

to

==========
Speedup GetRegistryLengthImpl() by seeding the DAFSA in reverse.

Add an option to make_dafsa.py to reverse the input words during
encoding.

Adapt the implementation of GetRegistryLengthImpl to the
reverse-seeded DAFSA. The new implementation is more efficient,
because it needs to query the DAFSA only once.

Improve the documentation of GetRegistryLengthImpl, with links
to relevent steps of the pseudocode algorithm specified at
publicsuffix.org. Document the two places where we depart
from the spec (one is INCLUDE_UNKNOWN_DOMAINS being optional,
the other is the platform.sh problem).

Add a TODO regarding empty-label matches.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334
==========

[ncarter (slow), 2017-02-27 23:19:37]

Description was changed from

==========
Speedup GetRegistryLengthImpl() by seeding the DAFSA in reverse.

Add an option to make_dafsa.py to reverse the input words during
encoding.

Adapt the implementation of GetRegistryLengthImpl to the
reverse-seeded DAFSA. The new implementation is more efficient,
because it needs to query the DAFSA only once.

Improve the documentation of GetRegistryLengthImpl, with links
to relevent steps of the pseudocode algorithm specified at
publicsuffix.org. Document the two places where we depart
from the spec (one is INCLUDE_UNKNOWN_DOMAINS being optional,
the other is the platform.sh problem).

Add a TODO regarding empty-label matches.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334
==========

to

==========
Speedup GetRegistryLengthImpl() by seeding the DAFSA in reverse.

Add an option to make_dafsa.py to reverse the input words during
encoding.

Adapt the implementation of GetRegistryLengthImpl to the
reverse-seeded DAFSA. The new implementation is more efficient,
because it needs to query the DAFSA only once.

Improve the documentation of GetRegistryLengthImpl, with links
to relevent steps of the pseudocode algorithm specified at
publicsuffix.org. Document the two places where we depart
from that spec (one is INCLUDE_UNKNOWN_DOMAINS being optional,
the other is the platform.sh problem).

Add a TODO regarding empty-label matches.

Dafsa size after this change: 40861 bytes

RegistryControlledDomainTest.GetDomainAndRegistry 55ms
RegistryControlledDomainTest.SameDomainOrHost_Different 95ms
RegistryControlledDomainTest.SameDomainOrHost_Same 100ms

BUG=678334
==========

[ncarter (slow), 2017-02-27 23:22:05]

PTAL

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
File net/base/registry_controlled_domains/registry_controlled_domain.cc (right):

https://codereview.chromium.org/2649033004/diff/20001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:120: //
there's a subdomain. Are there unittests of that behavior?
On 2017/01/26 00:41:45, Ryan Sleevi (overloaded) wrote:
> On 2017/01/26 00:33:02, ncarter wrote:
> > This TODO is about a concern I have with equivalence of new vs. old. In
> > particular, the old code had the following comment:
> > 
> > """
> > Exception rules override wildcard rules when the domain is an exact match,
but
> > wildcards take precedence when there's a subdomain.
> > """
> > 
> > I'm not really sure how to interpret that; it sounds like it's different
> > behavior from the algorithm described on https://publicsuffix.org/list/,
which
> > says that "An exception rule takes priority over any other matching rule."
> 
> Yeah, I'm trying to figure out from the PSL maintainers their thought on
better
> clarifying how this works.
> 
> > 
> > If we assume a rule like:
> > 
> >  !pref.hokkaido.jp
> > 
> > Then the registry-controlled part of "www.zzz.pref.hokkaido.jp" ought to be
> > "hokkaido.jp", right, even if there also a rule of the form 
> > "*.pref.hokkaido.jp"?
> 
> From the major implementations I'm aware of (although I'm still double
> checking), my understanding is that if there were rules
> 
> !pref.hokkaido.jp
> *.pref.hokkaido.jp
> 
> Then we'd actually return zzz.pref.hokkaido.jp
> 
> That is, the exception rule should only exclude the wildcard level for which
it
> applies. 

Shall I add a test for this case? It doesn't appear to occur in practice today,
but if it matters, this CL needs be tweaked a bit.

[Ryan Sleevi, 2017-03-06 17:20:04]

Mostly LG... I think the one thing we may want to add is something I should have
done sooner, which is the tests from publicsuffix.org -
https://github.com/publicsuffix/list/blob/master/tests/tests.txt and/or
https://github.com/publicsuffix/list/blob/master/tests/test_psl.txt

We should pass all of those, with the INCLUDE_UNKNOWN_REGISTRIES flag passed.

https://codereview.chromium.org/2649033004/diff/80001/net/base/lookup_string_...
File net/base/lookup_string_in_fixed_set_unittest.cc (right):

https://codereview.chromium.org/2649033004/diff/80001/net/base/lookup_string_...
net/base/lookup_string_in_fixed_set_unittest.cc:53: std::string
rev_key(key.rbegin(), key.rend());
Is it worth documenting why this is reversed?

https://codereview.chromium.org/2649033004/diff/80001/net/base/lookup_string_...
net/base/lookup_string_in_fixed_set_unittest.cc:76: std::string
line(sequence->rbegin(), sequence->rend());
Similarly

https://codereview.chromium.org/2649033004/diff/80001/net/base/registry_contr...
File net/base/registry_controlled_domains/registry_controlled_domain.cc (right):

https://codereview.chromium.org/2649033004/diff/80001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:104: size_t
in_wildcard = (unknown_filter == INCLUDE_UNKNOWN_REGISTRIES);
Based on your usage (155/162/172), this should be bool, right?

https://codereview.chromium.org/2649033004/diff/80001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:125: if
(is_last_char_in_label) {
Does it make more sense to do

if (!is_last_char_in_label)
  continue;

?

This should allow removing a level of indentation for the remaining code.

https://codereview.chromium.org/2649033004/diff/80001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:141: // this
case would have to be '*', which is explicitly disallowed.
Maybe it's because I haven't had my morning coffee, but I'm trying to determine
the source of the "which is explicitly disallowed" case? Is it because the
implicit '*'?

(Not saying I disagree, just having trouble parsing the why)

https://codereview.chromium.org/2649033004/diff/80001/net/base/registry_contr...
net/base/registry_controlled_domains/registry_controlled_domain.cc:171: //
"a..b.c". This is unnecessarily permissive.
Can you clarify the 'currently' - do you mean in this code or the previous code?