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

net/base/lookup_string_in_fixed_set.h

 // Copyright 2015 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.
 
 #ifndef NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
 #define NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
 
 #include <stddef.h>
 
 #include "net/base/net_export.h"
@@ skipping 17 matching lines @@
 // efficient (in time and space) lookup. The graph generated by make_dafsa.py
 // takes the form of a constant byte array which should be supplied via the
 // |graph| and |length| parameters.  The return value is kDafsaNotFound,
 // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule,
 // kDafsaWildcardRule and kDafsaPrivateRule ORed together.
 NET_EXPORT int LookupStringInFixedSet(const unsigned char* graph,
                                       size_t length,
                                       const char* key,
                                       size_t key_length);
 
+// The class FixedSetIncrementalLookup provides a generalized version of
+// LookupStringInFixedSet() where the query string is provided incrementally,
+// character by character. At each step, the lookup result can be cheaply
+// checked on the currently-provided prefix.
+//
+// This variant allows efficient (in time and space) prefix queries against a
+// set of strings that is known at compile time. Alternatively, longest-suffix
+// queries can be supported by constructing the DAFSA on reversed keys.

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

First Glance: Could you expand on this by including example calls between the
two and why one versus the other might be desirable?

I'm thinking something like
https://google.github.io/styleguide/cppguide.html#Class_Comments

Since we're effectively providing two different ways to do the same thing, my
hope is our documentation (for both) can explore how both ways accomplish the
same thing, and provide a bit of guidance on when one versus the other is more
appropriate.

In particular, if this is objectively better in all ways than the current code,
it seems like we'd want to deprecate the current code rather than offer both
ways. So I'm assuming there's some nuance here?

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

I've added examples to the class comment.

I've also added a TODO to LookupStringInFixedSet to eliminate that function.
I'll amend step 4 to actually do that.

And full disclosure, perf wise: the old lookup code definitely benefitted from
being able to iterate over the input directly -- when it had a run of adjacent
label chars it had a memcmp-like fast path. The reason this change is a net perf
win, is mostly due to the CHECK removal.

So, we might consider having a StringPiece variant of Advance, but we'd have to
add either a 'bool reverse' parameter once we want to treat the strings in
reverse, unless we construct our DAFSA labels-reversed, (e.g. com.appspot
instead of moc.topsppa), which approach actually there's something to be said
for; it's probably more human friendly.

+class NET_EXPORT FixedSetIncrementalLookup {
+ public:
+  // Creates a lookup into a set of strings, which must be known at compile
+  // time. |graph| and |length| describe a constant byte array holding a graph
+  // structure called a DAFSA (Deterministic Acyclic Finite State Automaton)
+  // which was generated by the script make_dafsa.py during compilation.

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

Can you reference the full path to make_dafsa.py here

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

Done.

+  FixedSetIncrementalLookup(const unsigned char* graph, size_t length);
+
+  // FixedSetIncrementalLookup is copyable so that callers can save/restore
+  // their position in the search. This is inexpensive.

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

Just from the header description, it's not entirely obvious when this is
desirable. But I'm still reading the header incrementally, so perhaps it becomes
clearer in subsequent CLs.

Just sharing first documentation remarks :)

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

Done.

+  FixedSetIncrementalLookup(const FixedSetIncrementalLookup&);
+  FixedSetIncrementalLookup& operator=(const FixedSetIncrementalLookup&);
+
+  ~FixedSetIncrementalLookup();
+
+  // Advance the query by adding a character to the input sequence. |input| can
+  // be any char value, but only ASCII printable characters will ever result in
+  // matches (since the DAFSA format is currently limited to those).

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

comment nit: I'm curious why we don't make that a stronger API contract
guarantee, since it's already an implicit requirement.

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

Historically, having input char values in the bad ranges (0x00-0x1F, and
0x80-0xFF) could have possibly caused memory errors; in particular values
0x80-0x87 which are result codes. Now there's explicit filtering, and it
guarantees a match failure.

(There's no reason we couldn't extend the dafsa format to [normalized] UTF-8,
but obviously we'd have to carve out bits for that, which would likely shift the
whole encoding scheme around. The wording of this comment was meant to leave
that possibility open.)

Let me know how you'd like this comment to read.

+  //
+  // Returns false once the search has exhausted the DAFSA, meaning that
+  // the currently-provided sequence is not a prefix of any string in the fixed
+  // set. Returns true otherwise.

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

Comment nit: Trying to work out the negative case, and then negating the
negative case (to figure out the true value) is a little bit of a pain.

I'm curious if you could simply express this in terms of the conditions it
returns true for, and omit the "Returns false otherwise".

It's also unclear whether it's legal to Advance() after false has been returned
- is that like advancing past the end of an iterator, or is that just a no-op?

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

Done.

+  bool Advance(char input);
+
+  // Returns the result code corresponding to the input sequence provided thus
+  // far to Advance().

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

So one thing that is left unclear is what happens if Advance() returned false -
presumably, kDafsaNotFound.

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

I've clarified the documentation of Advance() that talks about what a false
return value means.

+  //
+  // If the string does not appear in the fixed set, the return value is
+  // kDafsaNotFound. Otherwise, the value is a non-negative integer (currently
+  // limited to 0-7) corresponding to the result code for that string, as listed
+  // in the .gperf file from which the DAFSA was generated. For
+  // GetDomainAndRegistry DAFSAs, these values should be interpreted as a
+  // bitmask of kDafsaExceptionRule, kDafsaWildcardRule, and kDafsaPrivateRule.
+  //
+  // It is okay to call this function, and then extend the sequence further by
+  // calling Advance().
+  int GetResultForCurrentSequence() const;
+
+ private:
+  // Pointer to our current position in the graph, or nullptr if we've exhausted

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

s/our/the/
s/we've exhausted the graph/the graph is exhausted/

https://groups.google.com/a/chromium.org/d/msg/chromium-dev/NH-S6KCkr2M/yv0z3...
for context :)

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

I've rewritten the comments, since you asked. But the consensus at that link
actually seems to be that pronouns are okay.

+  // the graph.
+  const unsigned char* pos_;
+
+  // Pointer just past the end of the graph. |pos_| should never get here. This
+  // is used only in DCHECKs. When paired with a unittest that explores the
+  // entire graph, these DCHECKS ensure that the DAFSA contains no out-of-bounds
+  // offsets.

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

"When paired with" seems to be describing an implementation detail/usage of it,
not what it does. I think you can lose the entire sentence and still accomplish
the same.

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

Done.

+  const unsigned char* end_;
+
+  // Contains the current decoder state. If true, |pos_| points to a label
+  // character or a return code. If false, |pos_| points to a sequence of
+  // offsets that indicate the child nodes of the current state.
+  bool pos_is_label_character_;
+};
+
 }  // namespace net
 
 #endif  // NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_