[1 of 4] Support prefix queries against the effective_tld_names DAFSA

net/base/lookup_string_in_fixed_set.cc

Index: net/base/lookup_string_in_fixed_set.cc
diff --git a/net/base/lookup_string_in_fixed_set.cc b/net/base/lookup_string_in_fixed_set.cc
index 46497f3c47bb654c44e6aa34f9b72a2fd5820fb9..65b49340ae5c69d1f33240304874e888d9437664 100644
--- a/net/base/lookup_string_in_fixed_set.cc
+++ b/net/base/lookup_string_in_fixed_set.cc
@@ -10,19 +10,25 @@ namespace net {
 
 namespace {
 
-// 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) {
-  if (*pos == end)
+#if DCHECK_IS_ON()
+// TODO(nick): Workaround https://crbug.com/684105 (DCHECKs not optimized away)
+#define DCHECK_VALID_DAFSA_POSITION(position, end_position) \
+  DCHECK(((position) == nullptr) || ((position) < (end_position)))
+#else
+// Becomes a no-op in release builds.
+#define DCHECK_VALID_DAFSA_POSITION(position, end_position)
+#endif
+
+// Read next offset from |pos|, increment |offset| by that amount, and increment
+// |pos| either to point to the start of the next encoded offset in its node, or
+// nullptr, if there are no remaining offsets.
+//
+// Returns true if an offset could be read; false otherwise.
+inline bool GetNextOffset(const unsigned char** pos,

[Ryan Sleevi, 2017/01/25 19:11:04]

Pedantry: It doesn't seem "inline" reaches
https://google.github.io/styleguide/cppguide.html#Inline_Functions and given
that the compiler can ignore it, does this provide us any benefit? Also given
that it's an an unnamed namespace, can't the compiler fully optimize this
anyways?

I'm not going to push hard on this, just a remark though.

[ncarter (slow), 2017/01/26 23:29:11]

It wasn't done arbitrarily; it was a big win. I just re-measured; inlining this
function drops the first benchmark time (on Windows) from ~122ms to 96-98ms. 

Prior to this change, GetNextOffset was only called from one function, and was
getting inlined; now it's being called from both the Advance() and
GetResultForCurrentSequence(), and it seems that MSVC doesn't want to inline it
without the hint.

+                          const unsigned char** offset) {
+  if (*pos == nullptr)
     return false;
 
-  // 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_LT(*pos + 2, end);
   size_t bytes_consumed;
   switch (**pos & 0x60) {
     case 0x60:  // Read three byte offset
@@ -38,45 +44,33 @@ bool GetNextOffset(const unsigned char** pos,
       bytes_consumed = 1;
   }
   if ((**pos & 0x80) != 0) {
-    *pos = end;
+    *pos = nullptr;
   } else {
     *pos += bytes_consumed;
   }
   return true;
 }
 
-// Check if byte at offset is last in label.
-bool IsEOL(const unsigned char* offset, const unsigned char* end) {
-  CHECK_LT(offset, end);
+// Check if byte at |offset| is last in label.
+inline bool IsEOL(const unsigned char* offset) {

[ncarter (slow), 2017/01/26 23:29:11]

These inline hints seem to not matter anymore; I've dropped them.

   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_LT(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_LT(offset, end);
-  return *offset == (*key | 0x80);
+// Check if byte at |offset| matches key. This version matches both end-of-label
+// chars and not-end-of-label chars.
+inline bool IsMatch(const unsigned char* offset, char key) {
+  return (*offset & 0x7F) == key;
 }
 
-// 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_LT(offset, end);
+// Read return value at |offset|, if it is a return value. Returns true if a
+// return value could be read, false otherwise.
+inline bool GetReturnValue(const unsigned char* offset, int* return_value) {
+  // Return values are always encoded as end-of-label chars (so the high bit is
+  // set). So byte values in the inclusive range [0x80, 0x9F] encode the return
+  // values 0 through 31 (though make_dafsa.py doesn't currently encode values
+  // higher than 7). The following code does that translation.
   if ((*offset & 0xE0) == 0x80) {
-    *return_value = *offset & 0x0F;
+    *return_value = *offset & 0x1F;
     return true;
   }
   return false;
@@ -84,6 +78,114 @@ bool GetReturnValue(const unsigned char* offset,
 
 }  // namespace
 
+FixedSetIncrementalLookup::FixedSetIncrementalLookup(const unsigned char* graph,
+                                                     size_t length)
+    : pos_(graph), end_(graph + length), pos_is_label_character_(false) {}
+
+FixedSetIncrementalLookup::FixedSetIncrementalLookup(
+    const FixedSetIncrementalLookup& other) = default;
+FixedSetIncrementalLookup& FixedSetIncrementalLookup::operator=(
+    const FixedSetIncrementalLookup& other) = default;
+FixedSetIncrementalLookup::~FixedSetIncrementalLookup() {}

[Ryan Sleevi, 2017/01/25 19:11:04]

pedantry: newlines between each of these (at least when reading in the diff,
it's harder to parse)

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+
+bool FixedSetIncrementalLookup::Advance(char key) {
+  if (!pos_) {
+    // There are no possible matches because we've exhausted the graph.

[Ryan Sleevi, 2017/01/25 19:11:04]

There are no possible matches because the graph has been exhausted

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+    return false;
+  }
+
+  // Only ASCII printable chars are supported by the current DAFSA format -- the
+  // high bit (values 128 and above) are reserved as a label-end signifier, and
+  // the low values (31 and below) are reserved to encode the return values. So
+  // values outside this range will never be in the dictionary.
+  if (key >= 0x20) {
+    if (pos_is_label_character_) {
+      // We are currently in a label, so we just need to check the character
+      // encoded at |*pos| to see if it is equal to |key|.

[Ryan Sleevi, 2017/01/25 19:11:04]

Currently processing a label, so it is only necessary to check the character ...

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+      bool is_last_char_in_label = IsEOL(pos_);
+      bool is_match = IsMatch(pos_, key);
+      if (is_match) {
+        // If this is not the last character in the label, the next byte
+        // should be interpreted as a character or return value. Otherwise,
+        // the next byte should be interpreted as a list of child node
+        // offsets.
+        ++pos_;
+        DCHECK_VALID_DAFSA_POSITION(pos_, end_);
+        pos_is_label_character_ = !is_last_char_in_label;
+        return true;
+      }
+    } else {
+      const unsigned char* offset = pos_;
+      // Read offsets from |pos_| until we either run out of offsets, or until
+      // the label at |*offset| matches |key|.

[Ryan Sleevi, 2017/01/25 19:11:04]

Continue to read offsets from |pos_| until there are no more offsets, or until
...

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+      while (GetNextOffset(&pos_, &offset)) {
+        DCHECK_VALID_DAFSA_POSITION(pos_, end_);
+        DCHECK_VALID_DAFSA_POSITION(offset, end_);
+
+        // |offset| points to a DAFSA node that is a child of our original node.
+        //
+        // The low 7 bits of a node encodes a character value; the high bit
+        // indicates whether it's the last character in the label.
+        //
+        // Note that |*offset| could also be a result code value, but these are
+        // really just out-of-range ascii values, encoded the same way as
+        // characters. Since we've already validated that |key| is a printable
+        // ASCII value, IsMatch will never return true if |offset| is a result
+        // code.

[Ryan Sleevi, 2017/01/25 19:11:04]

Since |key| was already validated as a printable ASCII value, ...

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+        bool is_last_char_in_label = IsEOL(offset);
+        bool is_match = IsMatch(offset, key);
+
+        if (is_match) {
+          // If this is not the last character in the label, the next byte
+          // should be interpreted as a character or return value. Otherwise,
+          // the next byte should be interpreted as a list of child node
+          // offsets.
+          pos_ = offset + 1;
+          DCHECK_VALID_DAFSA_POSITION(pos_, end_);
+          pos_is_label_character_ = !is_last_char_in_label;
+          return true;
+        }
+      }
+    }
+  }
+
+  // If we didn't find a match, then we are off the end of the DAFSA.

[Ryan Sleevi, 2017/01/25 19:11:04]

If no match was found, then the end of the DAFSA has been reached.

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+  pos_ = nullptr;
+  pos_is_label_character_ = false;
+  return false;
+}
+
+int FixedSetIncrementalLookup::GetResultForCurrentSequence() const {
+  int value = kDafsaNotFound;
+  // Loking to see if there is a next character that's a return value.
+  if (pos_is_label_character_) {
+    // If |pos_| points to a position inside a label, then we just need to
+    // determine whether the character it holds is a result code instead
+    // of a normal character.

[Ryan Sleevi, 2017/01/25 19:11:04]

If |pos_| points to a position inside a label, then it is only necessary to
determine whether ...

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+    GetReturnValue(pos_, &value);
+  } else {
+    // Otherwise, |pos_| is an offset list (or nullptr). We need to explore
+    // the list of child nodes (given by their offsets) to find one whose label
+    // is a result code.

[Ryan Sleevi, 2017/01/25 19:11:04]

s/We need to explore/Explore/

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+    //
+    // We create a copy of |pos_| for this search, since mutating |pos_| could

[Ryan Sleevi, 2017/01/25 19:11:04]

A copy of |pos_| is created for this search, since ...

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+    // skip over a node that would be important to a subsequent Advance() call.
+    const unsigned char* temp_pos = pos_;
+
+    // Read offsets from |temp_pos| until either |temp_pos| is nullptr or until
+    // the byte at |offset| contains a result code (encoded as an ascii
+    // character below 0x20).
+    const unsigned char* offset = pos_;
+    while (GetNextOffset(&temp_pos, &offset)) {
+      DCHECK_VALID_DAFSA_POSITION(temp_pos, end_);
+      DCHECK_VALID_DAFSA_POSITION(offset, end_);
+      if (GetReturnValue(offset, &value))
+        break;
+    }
+  }
+  return value;
+}
+
 // Lookup a domain key in a byte array generated by make_dafsa.py.
 // The rule type is returned if key is found, otherwise kDafsaNotFound is
 // returned.
@@ -91,62 +193,19 @@ int LookupStringInFixedSet(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;
+  // Do an incremental lookup until either we exhaust the graph, or until we've
+  // appended every character in |key|.

[Ryan Sleevi, 2017/01/25 19:11:04]

Do an incremental lookup until the graph is exhausted or until every character
in |key| has been appended.

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+  FixedSetIncrementalLookup lookup(graph, length);
   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;
-      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 kDafsaNotFound;
-        ++key;
-        ++offset;
-      }
-    }
-    // Possible matches at this point:
-    // 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;
-      // The DAFSA guarantees that if the first char is a match, all
-      // remaining char elements MUST match if the key is truly present.
-      if (did_consume)
-        return kDafsaNotFound;
-      continue;
-    }
-    if (!IsEndCharMatch(offset, end, key)) {
-      if (did_consume)
-        return kDafsaNotFound;  // Unexpected
-      continue;
-    }
-    ++key;
-    pos = ++offset;  // Dive into child
+  while (key != key_end) {
+    if (!lookup.Advance(*key))
+      return kDafsaNotFound;
+    key++;
   }
-  return kDafsaNotFound;  // No match
+  // Check to see if the node we reached in the DAFSA search has a result code

[Ryan Sleevi, 2017/01/25 19:11:03]

s/we//

[ncarter (slow), 2017/01/26 23:29:11]

Done.

+  // (small non-negative integer) attached to it. Return it if it's there, or
+  // kDafsaNotFound if not.
+  return lookup.GetResultForCurrentSequence();
 }
 
 }  // namespace net