lookup_string_in_fixed_set.h 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160
  1. // Copyright 2015 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
  5. #define NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_
  6. #include <stddef.h>
  7. #include "base/strings/string_piece.h"
  8. #include "net/base/net_export.h"
  9. namespace net {
  10. enum {
  11. kDafsaNotFound = -1, // key is not in set
  12. kDafsaFound = 0, // key is in set
  13. // The following return values are used by the implementation of
  14. // GetDomainAndRegistry() and are probably not generally useful.
  15. kDafsaExceptionRule = 1, // key excluded from set via exception
  16. kDafsaWildcardRule = 2, // key matched a wildcard rule
  17. kDafsaPrivateRule = 4, // key matched a private rule
  18. };
  19. // Looks up the string |key| with length |key_length| in a fixed set of
  20. // strings. The set of strings must be known at compile time. It is converted to
  21. // a graph structure named a DAFSA (Deterministic Acyclic Finite State
  22. // Automaton) by the script make_dafsa.py during compilation. This permits
  23. // efficient (in time and space) lookup. The graph generated by make_dafsa.py
  24. // takes the form of a constant byte array which should be supplied via the
  25. // |graph| and |length| parameters. The return value is kDafsaNotFound,
  26. // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule,
  27. // kDafsaWildcardRule and kDafsaPrivateRule ORed together.
  28. //
  29. // TODO(nick): Replace this with FixedSetIncrementalLookup everywhere.
  30. NET_EXPORT int LookupStringInFixedSet(const unsigned char* graph,
  31. size_t length,
  32. const char* key,
  33. size_t key_length);
  34. // Looks up the longest matching suffix for |host| with length |length| in a
  35. // reversed DAFSA. Partial matches must begin at a new component, i.e. host
  36. // itself could match or a host part starting after a dot could match.
  37. // If no match was found a value of 0 is written to |suffix_length| and the
  38. // value kDafsaNotFound is returned, otherwise the length of the longest match
  39. // is written to |suffix_length| and the type of the longest match is returned.
  40. int LookupSuffixInReversedSet(const unsigned char* graph,
  41. size_t length,
  42. bool include_private,
  43. base::StringPiece host,
  44. size_t* suffix_length);
  45. // FixedSetIncrementalLookup provides efficient membership and prefix queries
  46. // against a fixed set of strings. The set of strings must be known at compile
  47. // time. The set is converted to a graph structure named a DAFSA (Deterministic
  48. // Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py
  49. // during compilation. The conversion generates a C++ header file defining the
  50. // encoded graph as a constant byte array. This class provides a fast, constant-
  51. // space lookup operation against such byte arrays.
  52. //
  53. // The lookup proceeds incrementally, with input characters provided one at a
  54. // time. This approach allow queries of the form: "given an input string, which
  55. // prefixes of that string that appear in the fixed set?" As the matching
  56. // prefixes (and their result codes) are enumerated, the most suitable match
  57. // among them can be selected in a single pass.
  58. //
  59. // This class can also be used to perform suffix queries (instead of prefix
  60. // queries) against a fixed set, so long as the DAFSA is constructed on reversed
  61. // values, and the input is provided in reverse order.
  62. //
  63. // Example usage for simple membership query; |input| is a std::string:
  64. //
  65. // FixedSetIncrementalLookup lookup(kDafsa, sizeof(kDafsa));
  66. // for (char c : input) {
  67. // if (!lookup.Advance(c))
  68. // return false;
  69. // }
  70. // return lookup.GetResultForCurrentSequence() != kDafsaNotFound;
  71. //
  72. // Example usage for 'find longest prefix in set with result code == 3' query:
  73. //
  74. // FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa));
  75. // size_t longest_match_end = 0;
  76. // for (size_t i = 0; i < input.length(); ++i) {
  77. // if (!prefix_lookup.Advance(input[i]))
  78. // break;
  79. // if (prefix_lookup.GetResultForCurrentSequence() == 3)
  80. // longest_match_end = (i + 1);
  81. // }
  82. // return input.substr(0, longest_match_end);
  83. //
  84. class NET_EXPORT FixedSetIncrementalLookup {
  85. public:
  86. // Begin a lookup against the provided fixed set. |graph| and |length|
  87. // describe a byte buffer generated by the make_dafsa.py script, as described
  88. // in the class comment.
  89. //
  90. // FixedSetIncrementalLookup is initialized to a state corresponding to the
  91. // empty input sequence. Calling GetResultForCurrentSequence() in the initial
  92. // state would indicate whether the empty string appears in the fixed set.
  93. // Characters can be added to the sequence by calling Advance(), and the
  94. // lookup result can be checked after each addition by calling
  95. // GetResultForCurrentSequence().
  96. FixedSetIncrementalLookup(const unsigned char* graph, size_t length);
  97. // FixedSetIncrementalLookup is copyable so that callers can save/restore
  98. // their position in the search. This is for cases where branching or
  99. // backtracking might be required (e.g. to probe for the presence of a
  100. // designated wildcard character).
  101. FixedSetIncrementalLookup(const FixedSetIncrementalLookup&);
  102. FixedSetIncrementalLookup& operator=(const FixedSetIncrementalLookup&);
  103. ~FixedSetIncrementalLookup();
  104. // Advance the query by adding a character to the input sequence. |input| can
  105. // be any char value, but only ASCII characters will ever result in matches,
  106. // since the fixed set itself is limited to ASCII strings.
  107. //
  108. // Returns true if the resulting input sequence either appears in the fixed
  109. // set itself, or is a prefix of some longer string in the fixed set. Returns
  110. // false otherwise, implying that the graph is exhausted and
  111. // GetResultForCurrentSequence() will return kDafsaNotFound.
  112. //
  113. // Once Advance() has returned false, the caller can safely stop feeding more
  114. // characters, as subsequent calls to Advance() will return false and have no
  115. // effect.
  116. bool Advance(char input);
  117. // Returns the result code corresponding to the input sequence provided thus
  118. // far to Advance().
  119. //
  120. // If the sequence does not appear in the fixed set, the return value is
  121. // kDafsaNotFound. Otherwise, the value is a non-negative integer (currently
  122. // limited to 0-7) corresponding to the result code for that string, as listed
  123. // in the .gperf file from which the DAFSA was generated. For
  124. // GetDomainAndRegistry DAFSAs, these values should be interpreted as a
  125. // bitmask of kDafsaExceptionRule, kDafsaWildcardRule, and kDafsaPrivateRule.
  126. //
  127. // It is okay to call this function, and then extend the sequence further by
  128. // calling Advance().
  129. int GetResultForCurrentSequence() const;
  130. private:
  131. // Pointer to the current position in the graph indicating the current state
  132. // of the automaton, or nullptr if the graph is exhausted.
  133. const unsigned char* pos_;
  134. // Pointer just past the end of the graph. |pos_| should never get here. This
  135. // is used only in DCHECKs.
  136. const unsigned char* end_;
  137. // Contains the current decoder state. If true, |pos_| points to a label
  138. // character or a return code. If false, |pos_| points to a sequence of
  139. // offsets that indicate the child nodes of the current state.
  140. bool pos_is_label_character_ = false;
  141. };
  142. } // namespace net
  143. #endif // NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_