Reduce footprint of registry controlled domain table

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 56d5ed9d6a176864f6f4beb9af06d9d9cfafd485..63ffda1390f0695659db8444f65812de0b5ccfbf 100644
--- a/net/base/registry_controlled_domains/registry_controlled_domain.cc
+++ b/net/base/registry_controlled_domains/registry_controlled_domain.cc
@@ -45,6 +45,7 @@
 
 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
 
+#include <limits>
 #include "base/logging.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
@@ -53,26 +54,146 @@
 #include "url/gurl.h"
 #include "url/url_parse.h"
 
-#include "effective_tld_names.cc"
-
 namespace net {
 namespace registry_controlled_domains {
 
 namespace {
+#include "effective_tld_names-inc.cc"
+
+// See make_dafsa.py for documentation of the generated dafsa byte array.
+
+const unsigned char* graph = kDafsa;
+size_t graph_length = sizeof(kDafsa);

[Ryan Sleevi, 2014/04/23 01:52:18]

Per
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Variab...
, global variable names (even though this is semi-constant, save for testing),
are traditionally prefixed with a g_ to indicate so

const unsigned char* g_graph = kDafsa;
size_t g_graph_length = sizeof(kDafsa);

+
+// Read next offset from pos.
+// Returns true if an offset could be read, false otherwise.
+bool GetNextOffset(const unsigned char*& pos, const unsigned char* end,
+                   const unsigned char*& offset) {

[Ryan Sleevi, 2014/04/23 01:52:18]

Per
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Refere...
, all reference arguments are supposed to be const.

bool GetNextOffset(const unsigned char** pos,
                   const unsigned char** end,
                   const unsigned char** offset)

[Olle Liljenzin, 2014/04/24 09:30:00]

Then it should be "** pos, * end, ** offset". The style guide says output
parameters should be last in the parameter list. Is there a similar rule for
in-out parameters?

+  if (pos < end) {

[Ryan Sleevi, 2014/04/23 01:52:18]

Convention in Chromium is to handle errors early, to avoid nesting code too
deeply

if (pos == end)
  return false;

CHECK_LT(pos, end);
// When reading an offset ...
CHECK_LT(pos + 2, end);
size_t bytes_consumed;

+    // When reading an offset the byte array must always contain at least
+    // three more bytes to consume. First the offset to read, then a node
+    // to skip over and finally a destination node. No object can be smaller
+    // than one byte.
+    CHECK(pos + 2 < end);
+    size_t bytes_consumed;
+    switch (*pos & 0x60) {
+      case 0x60:  // Read three byte offset
+        offset += ((pos[0] & 0x1F) << 16) | (pos[1] << 8) | pos[2];
+        bytes_consumed = 3;
+        break;
+      case 0x40:  // Read two byte offset
+        offset += ((pos[0] & 0x1F) << 8) | pos[1];
+        bytes_consumed = 2;
+        break;
+      default:
+        offset += pos[0] & 0x3F;
+        bytes_consumed = 1;
+    }
+    if ((*pos & 0x80) != 0) {
+      pos = end;
+    } else {
+      pos += bytes_consumed;
+    }
+    return true;
+  }
+  CHECK(pos == end);
+  return false;
+}
 
-const int kExceptionRule = 1;
-const int kWildcardRule = 2;
-const int kPrivateRule = 4;
+// Check if byte at offset is last in label.
+bool IsEOL(const unsigned char* offset, const unsigned char* end) {
+  CHECK(offset < end);

[Ryan Sleevi, 2014/04/23 01:52:18]

CHECK_LT (and all other occurrences below)

+  return (*offset & 0x80) != 0;
+}
+
+// Check if byte at offset matches first character in key.
+// This version matches characters not last in label.
+bool IsMatch(const unsigned char* offset, const unsigned char* end,
+             const char* key) {
+  CHECK(offset < end);
+  return *offset == *key;
+}
+
+// Check if byte at offset matches first character in key.
+// This version matches characters last in label.
+bool IsEndCharMatch(const unsigned char* offset, const unsigned char* end,
+                    const char* key) {
+  CHECK(offset < end);
+  return *offset == (*key | 0x80);
+}
 
-const FindDomainPtr kDefaultFindDomainFunction = Perfect_Hash::FindDomain;
+// Read return value at offset.
+// Returns true if a return value could be read, false otherwise.
+bool GetReturnValue(const unsigned char* offset, const unsigned char* end,
+                    int* return_value) {
+  CHECK(offset < end);
+  if ((*offset & 0xe0) == 0x80) {

[Ryan Sleevi, 2014/04/23 01:52:18]

nit: If you're going to capitalize 0x0F (line 131) and 0x3F (line 89),
capitalize 0xE0

+    *return_value = *offset & 0x0F;
+    return true;
+  }
+  return false;
+}
 
-// 'stringpool' is defined as a macro by the gperf-generated
-// "effective_tld_names.cc". Provide a real constant value for it instead.
-const char* const kDefaultStringPool = stringpool;
-#undef stringpool
+int kFatal = -1;

[Ryan Sleevi, 2014/04/23 01:52:18]

const int

Having looked through this, I suspect this may make more sense as kKeyNotFound
(or simply kNotFound? NotPresent?) rather than kFatal.

+
+// Lookup a domain key in a byte array generated by make_dafsa.py.
+// The rule type is returned if key is found, otherwise kFatal is returned.
+int LookupString(const unsigned char* graph, size_t length, const char* key,
+                 size_t key_length) {
+  const unsigned char* pos = graph;
+  const unsigned char* end = graph + length;
+  const unsigned char* offset = pos;
+  const char* key_end = key + key_length;
+  while (GetNextOffset(pos, end, offset)) {
+    //   char <char>+ end_char offsets
+    //   char <char>+ return value
+    //   char end_char offsets
+    //   char return value
+    //   end_char offsets
+    //   return_value
+    bool did_consume = false;
+    if (key != key_end && !IsEOL(offset, end)) {
+      // Leading <char> is not a match. Don't dive into this child
+      if (!IsMatch(offset, end, key)) continue;

[Ryan Sleevi, 2014/04/23 01:52:18]

style nit: Convention has been to eschew the one-liners within net (though
permitted by the style guide), in favour of

if (!IsMatch())
  continue;
did_consume

Apologies for that. Ditto 168, 180, 181, 185

+      did_consume = true;
+      ++offset;
+      ++key;
+      // Possible matches at this point:
+      // <char>+ end_char offsets
+      // <char>+ return value
+      // end_char offsets
+      // return value
+      // Remove all remaining <char> nodes possible
+      while (!IsEOL(offset, end) && key != key_end) {
+        if (!IsMatch(offset, end, key)) return kFatal;

[Ryan Sleevi, 2014/04/23 01:52:18]

Should comment why this is kFatal. I'm not entirely sure how best to word this
(read: feel free to reword), but I suspect something along the lines of

// The DAFSA guarantees that if the first char is a match, all
// remaining char elements MUST match if the key is truly present.

+        ++key;
+        ++offset;
+      }
+    }
+    // Possible matches:

[Ryan Sleevi, 2014/04/23 01:52:18]

s/Possible matches/Possible matches at this point:/ (matching 161)

+    // end_char offsets
+    // return_value
+    // If one or more <char> elements were consumed, a failure
+    // to match is terminal. Otherwise, try the next node.
+    if (key == key_end) {
+      int return_value;
+      if (GetReturnValue(offset, end, &return_value)) return return_value;
+      if (did_consume) return kFatal;
+      continue;
+    }
+    if (!IsEndCharMatch(offset, end, key)) {
+      if (did_consume) return kFatal;  // Unexpected
+      continue;
+    }
+    ++key;
+    pos = ++offset;  // Dive into child
+  }
+  return kFatal;  // No match
+}
 
-FindDomainPtr g_find_domain_function = kDefaultFindDomainFunction;
-const char* g_stringpool = kDefaultStringPool;
+const int kExceptionRule = 1;
+const int kWildcardRule = 2;
+const int kPrivateRule = 4;

[Ryan Sleevi, 2014/04/23 01:52:18]

While this is not code within a class, convention is that constants are listed
before functions (typically at the top of the file), as that most matches the
class definition (
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Declar...
)

Move this (and line 137) up to 66

 
 size_t GetRegistryLengthImpl(
     const std::string& host,
@@ -105,46 +226,40 @@ size_t GetRegistryLengthImpl(
     return 0;  // This can't have a registry + domain.
   while (1) {
     const char* domain_str = host.data() + curr_start;
-    int domain_length = host_check_len - curr_start;
-    const DomainRule* rule = g_find_domain_function(domain_str, domain_length);
-
-    // We need to compare the string after finding a match because the
-    // no-collisions of perfect hashing only refers to items in the set.  Since
-    // we're searching for arbitrary domains, there could be collisions.
-    // Furthermore, if the apparent match is a private registry and we're not
-    // including those, it can't be an actual match.
-    if (rule) {
-      bool do_check = !(rule->type & kPrivateRule) ||
-                      private_filter == INCLUDE_PRIVATE_REGISTRIES;
-      if (do_check && base::strncasecmp(domain_str,
-                                        g_stringpool + rule->name_offset,
-                                        domain_length) == 0) {
-        // Exception rules override wildcard rules when the domain is an exact
-        // match, but wildcards take precedence when there's a subdomain.
-        if (rule->type & kWildcardRule && (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);
-        }
+    size_t domain_length = host_check_len - curr_start;
+    int type = LookupString(graph, graph_length, domain_str, domain_length);
+    bool do_check =
+        type != -1 && (!(type & kPrivateRule) ||

[Ryan Sleevi, 2014/04/23 01:52:18]

s/-1/kFatal

+                       private_filter == INCLUDE_PRIVATE_REGISTRIES);
+
+    // If the apparent match is a private registry and we're not including
+    //  those, it can't be an actual match.

[Ryan Sleevi, 2014/04/23 01:52:18]

s/  those/ those/

+    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 & kWildcardRule && (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 (rule->type & kExceptionRule) {
-          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 (type & kExceptionRule) {
+        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;
         }
-
-        // 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);
+        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.
@@ -264,10 +379,16 @@ size_t GetRegistryLength(
   return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter);
 }
 
-void SetFindDomainFunctionAndStringPoolForTesting(FindDomainPtr function,
-                                                  const char* stringpool) {
-  g_find_domain_function = function ? function : kDefaultFindDomainFunction;
-  g_stringpool = stringpool ? stringpool : kDefaultStringPool;
+void SetFindDomainGraph() {
+    graph = kDafsa;
+    graph_length = sizeof(kDafsa);
+}
+
+void SetFindDomainGraph(const unsigned char* domains, size_t length) {
+  CHECK(domains);
+  CHECK(length > 0);

[Ryan Sleevi, 2014/04/23 01:52:18]

CHECK_GT, although really, since it's size_t

CHECK_NE(0, length);

+  graph = domains;
+  graph_length = length;
 }
 
 }  // namespace registry_controlled_domains