Reduce buggy usage of the registry controlled domain service.

net/base/registry_controlled_domains/registry_controlled_domain.cc

Index: net/base/registry_controlled_domains/registry_controlled_domain.cc
diff --git a/net/base/registry_controlled_domains/registry_controlled_domain.cc b/net/base/registry_controlled_domains/registry_controlled_domain.cc
index 607d735f3080be6b37354b5963064df6e78bd7fa..ece6c7927ef61388af59f98fbedea549158bdb8c 100644
--- a/net/base/registry_controlled_domains/registry_controlled_domain.cc
+++ b/net/base/registry_controlled_domains/registry_controlled_domain.cc
@@ -66,10 +66,19 @@ namespace {
 const unsigned char* g_graph = kDafsa;
 size_t g_graph_length = sizeof(kDafsa);
 
+struct MappedHostComponent {
+  size_t original_begin;
+  size_t original_end;
+
+  size_t canonical_begin;
+  size_t canonical_end;
+};
+
 size_t GetRegistryLengthImpl(base::StringPiece host,
                              UnknownRegistryFilter unknown_filter,
                              PrivateRegistryFilter private_filter) {
-  DCHECK(!host.empty());
+  if (host.empty())
+    return std::string::npos;
 
   // Skip leading dots.
   const size_t host_check_begin = host.find_first_not_of('.');
@@ -189,6 +198,106 @@ base::StringPiece GetDomainAndRegistryAsStringPiece(
   return GetDomainAndRegistryImpl(host, filter);
 }
 
+// Backend for PermissiveGetHostRegistryLength that handles both UTF-8 and
+// UTF-16 input. The template type is the std::string type to use (it makes the
+// typedefs easier than using the character type).
+template <typename Str>
+size_t DoPermissiveGetHostRegistryLength(base::BasicStringPiece<Str> host,
+                                         UnknownRegistryFilter unknown_filter,
+                                         PrivateRegistryFilter private_filter) {
+  std::string canonical_host;  // No not modify outside of canon_output.

[Peter Kasting, 2016/10/22 05:04:19]

Nit: No -> Do ?

+  canonical_host.reserve(host.size());

[Peter Kasting, 2016/10/22 05:04:19]

Nit: The rest of this file, and the majority of Chrome code I've seen, seems to
prefer length() to size() for strings.  (Several places)

[brettw, 2016/10/24 21:45:24]

I've always written size() but will use length() for file consistency.

+  url::StdStringCanonOutput canon_output(&canonical_host);
+
+  std::vector<MappedHostComponent> components;
+
+  size_t current = 0;
+  while (current < host.size()) {

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Shorter, narrows scope of |current|:

  for (size_t current = 0; current < host.size(); ++current) {

This also allows deleting the "current++" line near the bottom of the loop. 
(It's OK to increment |current| unconditionally since if we already hit the end
of the string, one past will still terminate the loop.)

[brettw, 2016/10/24 21:45:24]

Done.

+    // Advance to next "." or end.

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Technically, this comment belongs on the while() loop; |begin| is not
related.

[brettw, 2016/10/24 21:45:24]

Done.

+    size_t begin = current;

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Can be const

[brettw, 2016/10/24 21:45:24]

I prefer not to mark random local variables const just because they can be.

[Peter Kasting, 2016/10/24 23:04:32]

There's no Chromium-wide pattern, so that's fine.

However, note that both the Google Style Guide and Effective C++ recommend const
for local variables when it's possible to use it.  Consider changing your
personal patterns over time :)

+    while (current < host.size() && host[current] != '.')
+      current++;

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Shorter:

    current = std::min(host.find('.', begin), host.length());

[brettw, 2016/10/24 21:45:24]

This seems less readable to me.

[Peter Kasting, 2016/10/24 23:04:32]

What about:

current = host.find('.', begin);
if (current == std::string::npos)
  current = host.length();

This is longer, but I can tell immediately what it's trying to do, as opposed to
the while loop.

Although maybe now that the comment is moved down the existing code is good
enough.

[brettw, 2016/10/25 20:28:17]

I can live with this.

+
+    MappedHostComponent mapping;
+    mapping.original_begin = begin;
+    mapping.original_end = current;
+    mapping.canonical_begin = static_cast<size_t>(canon_output.length());

[Peter Kasting, 2016/10/22 05:04:19]

Nit: If you save this in a temp here instead of creating a whole
MappedHostComponent:

    size_t canonical_begin = static_cast<size_t>(canon_output.length());

Then you can remove the rest of this block and do something like this below:

    components.push_back({begin, current, canonical_begin,
                          static_cast<size_t>(canon_output.length())});

[brettw, 2016/10/24 21:45:24]

This feels icky to me, I don't like implicitly depending on the order of 4 ints
in the struct which is surprising to somebody changing the code. My current
structure felt cleaner than writing a constructor (which I would normally do for
this kind of thing) because it was only used in one place and that would be even
more code).

+
+    // Append the canonicalized version of this component.

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Append -> Try to append ?

[brettw, 2016/10/24 21:45:24]

Done.

+    if (!url::CanonicalizeHostSubstring(
+            host.data(), url::Component(static_cast<int>(begin),
+                                        static_cast<int>(current - begin)),
+            &canon_output)) {
+      // Failure to canonicalize this component, append as-is.

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Failure -> Failed; comma -> semicolon

+      for (size_t i = begin; i < current; i++)
+        canon_output.push_back(host[i]);

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Shorter and more efficient:

      canon_output.Append(&host[begin], static_cast<int>(current - begin));

(Probably makes sense to pull the "static_cast<int>(current - begin)" part out
to a temp given that this will be the second time you've done it)

[brettw, 2016/10/24 21:45:24]

Actually this old code was wrong in the UTF-16 case (not sure why it compiled).
I had to write a separate function to do this.

+    }
+
+    mapping.canonical_end = static_cast<size_t>(canon_output.length());
+    components.push_back(mapping);
+
+    if (current < host.size()) {
+      canon_output.push_back('.');
+      current++;  // Skip over '.' in input.
+    }
+  }
+  canon_output.Complete();
+
+  size_t canonical_rcd_len =
+      GetRegistryLengthImpl(canonical_host, unknown_filter, private_filter);
+  if (canonical_rcd_len == 0 || canonical_rcd_len == std::string::npos)
+    return canonical_rcd_len;  // Error or no registry controlled domain.
+
+  // Find which host component the result started in.
+  size_t canonical_rcd_begin = canonical_host.size() - canonical_rcd_len;
+  for (const auto& mapping : components) {
+    // In the common case, GetRegistryLengthImpl will identify the beginning
+    // of a component and we can just return where that component was in the
+    // original string.
+    if (canonical_rcd_begin == mapping.canonical_begin)
+      return host.size() - mapping.original_begin;
+
+    if (canonical_rcd_begin < mapping.canonical_end) {

[Peter Kasting, 2016/10/22 05:04:19]

Nit: If you change this to this, at the top of the loop:

  if (canonical_rcd_begin >= mapping.canonical_end)
    continue;

Then not only can you unindent this whole remaining section, but you probably
get a small efficiency win, since you'll be doing one comparison instead of two
for every skipped component.

[brettw, 2016/10/24 21:45:24]

Done.

+      // The registry controlled domain begin was identified as being in the
+      // middle of this dot-separated domain component in the non-canonical
+      // input. This indicates some form of escaped dot, or a non-ASCII
+      // character that was canonicalized to a dot.
+      //
+      // Brute-force search from the end by repeatedly canonicalizing longer
+      // substrings until we get a match for the canonicalized version. This
+      // depends on the canonicalization process not changing the order of the
+      // characters. Punycode can change the order of characters, but it
+      // doesn't work across dots so this is safe.
+
+      // Expected canonical registry controlled domain.
+      base::StringPiece canonical_rcd(&canonical_host[canonical_rcd_begin],
+                                      canonical_rcd_len);
+
+      for (int current_try = static_cast<int>(mapping.original_end) - 1;

[Peter Kasting, 2016/10/22 05:04:19]

Can't we binary-search this instead of linear-searching it, using the length of
the canonicalized output?

(This also implies, "can't we just compare string lengths and not full strings
below".)

[brettw, 2016/10/24 21:45:24]

That doesn't work. Canonicalization can make the result longer or shorter than
the original. Canonicalizing the last 3 characters of "%43om" gives "3om, but
canonicalizing the last 5 gives "com"

[Peter Kasting, 2016/10/24 23:04:32]

Yeah, you're right.  I thought about this some but not deeply enough.

Might be good to add a comment like "Note that the length of the canonical
output may both increase and decrease as we proceed through the string, so we
can't binary-search based on the output length; we need to do an exhaustive
linear search."

[brettw, 2016/10/25 20:28:17]

Done.

+           current_try >= static_cast<int>(mapping.original_begin);

[Peter Kasting, 2016/10/22 05:04:19]

Seems like we could get by with ">" instead of ">=" since we already checked the
== case above, right?

[Peter Kasting, 2016/10/25 01:33:32]

Still wondering about this.

[brettw, 2016/10/25 20:28:17]

You're correct, but in the context of a loop counting down ">" jumps out as a
bug to me so I think it's more clear to keep it in there.

[Peter Kasting, 2016/10/25 20:37:53]

Maybe write '>' with a comment saying we already checked the == case above?

It won't make any functional difference, but it really confused me while reading
it because I started going back over to see whether the "==" this loop would be
checking was functionally different than the "==" we were checking above.  I
never did completely convince myself one way or the other.  I just wouldn't want
anyone else to read this and go through the same process.

+           current_try--) {

[Peter Kasting, 2016/10/22 05:04:19]

Nit: Predecrement

[brettw, 2016/10/24 21:45:24]

I don't understand this comment. Are you asking because you prefer predecrement
generally (in which I case I think your comment is not helpful) or is there a
logic problem that I don't see?

[Peter Kasting, 2016/10/24 23:04:32]

There's no logic problem, I was suggesting using predecrement because you don't
need postdecrement form.

I thought the Google Style Guide mandated this, which it does, but only for
non-scalar types; it says you can use either form for scalar types.  Pretty much
all the rest of the Chromium code I've worked with uses prefix forms for scalars
as well for consistency, which seems wise to me (postfix form leaps out as "I'm
doing something clever!"), so I suggest (but do not require) using it here as
well for that reason.

(Or in other words "there are weak reasons to prefer prefix form here, are there
weak reasons to prefer postfix form?")

[brettw, 2016/10/25 20:28:17]

I always write postfix for scalars because I think prefix looks weird. There are
21K instances of "i++" and 27K instances of "++i" in the code base, so "pretty
much all" is an incorrect impression. Please be more careful about how you write
these comments, I actually spent some time questioning myself and reading about
increments in loops to make sure there wasn't something I was missing.

[Peter Kasting, 2016/10/25 20:37:53]

This surprised me so I tried to look myself:

https://cs.chromium.org/search/?q=i%5C%2B%5C%2B+-file:third_party+-file:v8+fi...
https://cs.chromium.org/search/?q=%5C%2B%5C%2Bi+-file:third_party+-file:v8+fi...

~1500 vs. ~5500, which is more postfix than I expected, but not so even as the
numbers above.  Did I do my searches wrong?
I'm sorry; I didn't even consider that you might interpret my original comment
as saying you had a logic bug, or I would have tried to be clearer.  (I also
would have tried to be clearer had I not been misremembering the Google style
guide as mandating this, but I figured since it did you would know what I was
referring to.)

+        std::string try_string;
+        url::StdStringCanonOutput try_output(&try_string);
+
+        if (!url::CanonicalizeHostSubstring(
+                host.data(),
+                url::Component(
+                    current_try,
+                    static_cast<int>(mapping.original_end) - current_try),
+                &try_output))
+          continue;  // Invalid substring, skip.
+
+        try_output.Complete();
+        if (try_string == canonical_rcd)
+          return host.size() - current_try;
+      }
+    }
+  }
+
+  NOTREACHED();
+  return canonical_rcd_len;
+}
+
 }  // namespace
 
 std::string GetDomainAndRegistry(const GURL& gurl,
@@ -238,26 +347,59 @@ size_t GetRegistryLength(
     const GURL& gurl,
     UnknownRegistryFilter unknown_filter,
     PrivateRegistryFilter private_filter) {
-  base::StringPiece host = gurl.host_piece();
-  if (host.empty())
-    return std::string::npos;
-  if (gurl.HostIsIPAddress())

[Peter Kasting, 2016/10/22 05:04:19]

I assume deleting this is not a behavior change because presumably we never have
TLDs that are numeric.  (I haven't thought about if IPv6 addresses cause
problems.)

Is it an efficiency change?  I'd hate to lose efficiency for IP addresses passed
here (but if we gain efficiency, yay?).

[brettw, 2016/10/24 21:45:24]

I did this because it can never match, and decoding the IP address is equivalent
to recanonicalizing the entire host again.

-    return 0;
-  return GetRegistryLengthImpl(host, unknown_filter, private_filter);
+  return GetRegistryLengthImpl(gurl.host_piece(), unknown_filter,
+                               private_filter);
 }
 
-size_t GetRegistryLength(base::StringPiece host,
-                         UnknownRegistryFilter unknown_filter,
-                         PrivateRegistryFilter private_filter) {
+bool HostHasRegistryControlledDomain(base::StringPiece host,
+                                     UnknownRegistryFilter unknown_filter,
+                                     PrivateRegistryFilter private_filter) {
   url::CanonHostInfo host_info;
   const std::string canon_host(CanonicalizeHost(host, &host_info));
-  if (canon_host.empty())
-    return std::string::npos;
-  if (host_info.IsIPAddress())
-    return 0;
+  switch (host_info.family) {
+    case url::CanonHostInfo::IPV4:
+    case url::CanonHostInfo::IPV6:
+      // IP addresses don't have R.C.D.'s.
+      return false;
+    case url::CanonHostInfo::BROKEN:
+      // Host is not canonicalizable. Fall back to the slower "permissive"
+      // version.
+      return PermissiveGetHostRegistryLength(host, unknown_filter,
+                                             private_filter) > 0;

[Peter Kasting, 2016/10/22 05:04:19]

"> 0" doesn't seem right; we want to return false for npos, don't we?

[brettw, 2016/10/24 21:45:23]

Doth done, thanks for catching. I added some unit test cases for the empty
string cases.

+    case url::CanonHostInfo::NEUTRAL:
+      return GetRegistryLengthImpl(host, unknown_filter, private_filter) > 0;

[Peter Kasting, 2016/10/22 05:04:19]

Same question.

+    default:
+      NOTREACHED();
+      return false

[Peter Kasting, 2016/10/22 05:04:19]

Semicolon

+  }
+}
+
+size_t GetCanonicalHostRegistryLength(base::StringPiece canon_host,
+                                      UnknownRegistryFilter unknown_filter,
+                                      PrivateRegistryFilter private_filter) {
+#ifndef NDEBUG
+  // Ensure passed-in host name is canonical.
+  url::CanonHostInfo host_info;
+  DCHECK_EQ(net::CanonicalizeHost(canon_host, &host_info), canon_host);
+#endif
+
   return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter);
 }
 
+size_t PermissiveGetHostRegistryLength(base::StringPiece host,
+                                       UnknownRegistryFilter unknown_filter,
+                                       PrivateRegistryFilter private_filter) {
+  return DoPermissiveGetHostRegistryLength<std::string>(host, unknown_filter,
+                                                        private_filter);
+}
+
+size_t PermissiveGetHostRegistryLength(base::StringPiece16 host,
+                                       UnknownRegistryFilter unknown_filter,
+                                       PrivateRegistryFilter private_filter) {
+  return DoPermissiveGetHostRegistryLength<base::string16>(host, unknown_filter,
+                                                           private_filter);
+}
+
 void SetFindDomainGraph() {
   g_graph = kDafsa;
   g_graph_length = sizeof(kDafsa);