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

net/base/registry_controlled_domains/registry_controlled_domain.cc

 // 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.
 
 // NB: Modelled after Mozilla's code (originally written by Pamela Greene,
 // later modified by others), but almost entirely rewritten for Chrome.
 //   (netwerk/dns/src/nsEffectiveTLDService.cpp)
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
@@ skipping 79 matching lines @@
   // to be included in the final returned length.
   size_t host_check_len = host.length();
   if (host[host_check_len - 1] == '.') {
     --host_check_len;
     DCHECK(host_check_len > 0);  // If this weren't true, the host would be ".",
                                  // and we'd have already returned above.
     if (host[host_check_len - 1] == '.')
       return 0;  // Multiple trailing dots.
   }
 
-  // Walk up the domain tree, most specific to least specific,
-  // looking for matches at each level.
-  size_t prev_start = std::string::npos;
-  size_t curr_start = host_check_begin;
-  size_t next_dot = host.find('.', curr_start);
-  if (next_dot >= host_check_len)  // Catches std::string::npos as well.
-    return 0;  // This can't have a registry + domain.
-  while (1) {
-    const char* domain_str = host.data() + curr_start;
-    size_t domain_length = host_check_len - curr_start;
-    int type = LookupStringInFixedSet(g_graph, g_graph_length, domain_str,
-                                      domain_length);
-    bool do_check = type != kDafsaNotFound &&
-                    (!(type & kDafsaPrivateRule) ||
-                     private_filter == INCLUDE_PRIVATE_REGISTRIES);
+  // Feed |host| to the DAFSA in reverse character order.
+  size_t curr_pos = host_check_len - 1;
 
-    // If the apparent match is a private registry and we're not including
-    // those, it can't be an actual match.
-    if (do_check) {
-      // Exception rules override wildcard rules when the domain is an exact
-      // match, but wildcards take precedence when there's a subdomain.
-      if (type & kDafsaWildcardRule && (prev_start != std::string::npos)) {
-        // If prev_start == host_check_begin, then the host is the registry
-        // itself, so return 0.
-        return (prev_start == host_check_begin) ? 0
-                                                : (host.length() - prev_start);
+  // If INCLUDE_UNKNOWN_REGISTRIES is true, we allow any initial label to be a
+  // TLD. TODO(nick): is this right? Are there tests? What if a TLD appears
+  // as part of a longer rule only?

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

"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]

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?

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

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)
Nope.
Correct

+  size_t in_wildcard = (unknown_filter == INCLUDE_UNKNOWN_REGISTRIES);
+  size_t prevailing_rule_pos = in_wildcard ? host_check_len + 1 : host.length();
+  FixedSetIncrementalLookup tld_reverse_lookup(g_graph, g_graph_length);
+  while (curr_pos != host_check_begin - 1 &&
+         (tld_reverse_lookup.Advance(host[curr_pos]) || in_wildcard)) {
+    // Check the return value whenever we're at the end of a label.
+    if (curr_pos == host_check_begin || host[curr_pos - 1] == '.') {
+      int dafsa_result = tld_reverse_lookup.GetResultForCurrentSequence();
+      if (dafsa_result != kDafsaNotFound &&
+          ((dafsa_result & kDafsaPrivateRule) == 0 ||
+           private_filter == INCLUDE_PRIVATE_REGISTRIES)) {
+        if (dafsa_result & kDafsaExceptionRule) {
+          // Exception rules always win.
+          // TODO(nick): The old code talks about wildcards trumping when
+          // there's a subdomain. Are there unittests of that behavior?

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

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]

Yeah, I'm trying to figure out from the PSL maintainers their thought on better
clarifying how this works.
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 23:22:04]

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.

+          size_t previous_dot = host.find('.', curr_pos);
+          if (previous_dot == std::string::npos) {
+            // If we get here, we had an exception rule with no dots (e.g.
+            // "!foo").  This would only be valid if we had a corresponding
+            // wildcard rule, which would have to be "*".  But we explicitly
+            // disallow that case, so this kind of rule is invalid.
+            NOTREACHED() << "Invalid exception rule";
+            return 0;
+          }
+          DCHECK(in_wildcard);
+          DCHECK_EQ(previous_dot + 1, prevailing_rule_pos);
+          return host.length() - previous_dot - 1;
+        }
+        in_wildcard = (dafsa_result & kDafsaWildcardRule) != 0;
+        prevailing_rule_pos = curr_pos;
+      } else if (in_wildcard) {
+        in_wildcard = false;
+        prevailing_rule_pos = curr_pos;
       }
+    }
+    --curr_pos;
+  }
+  // If the entire hostname is registry-controlled, fail.
+  if (in_wildcard || prevailing_rule_pos == host_check_begin)
+    return 0;
 
-      if (type & kDafsaExceptionRule) {
-        if (next_dot == std::string::npos) {
-          // If we get here, we had an exception rule with no dots (e.g.
-          // "!foo").  This would only be valid if we had a corresponding
-          // wildcard rule, which would have to be "*".  But we explicitly
-          // disallow that case, so this kind of rule is invalid.
-          NOTREACHED() << "Invalid exception rule";
-          return 0;
-        }
-        return host.length() - next_dot - 1;
-      }
-
-      // If curr_start == host_check_begin, then the host is the registry
-      // itself, so return 0.
-      return (curr_start == host_check_begin) ? 0
-                                              : (host.length() - curr_start);
-    }
-
-    if (next_dot >= host_check_len)  // Catches std::string::npos as well.
-      break;
-
-    prev_start = curr_start;
-    curr_start = next_dot + 1;
-    next_dot = host.find('.', curr_start);
-  }
-
-  // No rule found in the registry.  curr_start now points to the first
-  // character of the last subcomponent of the host, so if we allow unknown
-  // registries, return the length of this subcomponent.
-  return unknown_filter == INCLUDE_UNKNOWN_REGISTRIES ?
-      (host.length() - curr_start) : 0;
+  return host.length() - prevailing_rule_pos;
 }
 
 base::StringPiece GetDomainAndRegistryImpl(
     base::StringPiece host,
     PrivateRegistryFilter private_filter) {
   DCHECK(!host.empty());
 
   // Find the length of the registry for this host.
   const size_t registry_length =
       GetRegistryLengthImpl(host, INCLUDE_UNKNOWN_REGISTRIES, private_filter);
   if ((registry_length == std::string::npos) || (registry_length == 0))
     return base::StringPiece();  // No registry.
   // The "2" in this next line is 1 for the dot, plus a 1-char minimum preceding
   // subcomponent length.
   DCHECK(host.length() >= 2);
   if (registry_length > (host.length() - 2)) {
     NOTREACHED() <<
         "Host does not have at least one subcomponent before registry!";
     return base::StringPiece();
   }
 
-  // Move past the dot preceding the registry, and search for the next previous
-  // dot.  Return the host from after that dot, or the whole host when there is
+  // Move past the dot preceding the registry, and search for the dot before
+  // that.  Return the host from after that dot, or the whole host when there is
   // no dot.
   const size_t dot = host.rfind('.', host.length() - registry_length - 2);
   if (dot == std::string::npos)
     return host;
   return host.substr(dot + 1);
 }
 
 // Same as GetDomainAndRegistry, but returns the domain and registry as a
 // StringPiece that references the underlying string of the passed-in |gurl|.
 // TODO(pkalinnikov): Eliminate this helper by exposing StringPiece as the
@@ skipping 249 matching lines @@
 
 void SetFindDomainGraph(const unsigned char* domains, size_t length) {
   CHECK(domains);
   CHECK_NE(length, 0u);
   g_graph = domains;
   g_graph_length = length;
 }
 
 }  // namespace registry_controlled_domains
 }  // namespace net