lookup_string_in_fixed_set_unittest.cc 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251
  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. #include "net/base/lookup_string_in_fixed_set.h"
  5. #include <string.h>
  6. #include <algorithm>
  7. #include <limits>
  8. #include <ostream>
  9. #include <utility>
  10. #include <vector>
  11. #include "base/base_paths.h"
  12. #include "base/files/file_path.h"
  13. #include "base/files/file_util.h"
  14. #include "base/path_service.h"
  15. #include "base/strings/string_util.h"
  16. #include "base/strings/stringprintf.h"
  17. #include "testing/gtest/include/gtest/gtest.h"
  18. namespace net {
  19. namespace {
  20. namespace test1 {
  21. #include "net/base/registry_controlled_domains/effective_tld_names_unittest1-inc.cc"
  22. }
  23. namespace test3 {
  24. #include "net/base/registry_controlled_domains/effective_tld_names_unittest3-inc.cc"
  25. }
  26. namespace test4 {
  27. #include "net/base/registry_controlled_domains/effective_tld_names_unittest4-inc.cc"
  28. }
  29. namespace test5 {
  30. #include "net/base/registry_controlled_domains/effective_tld_names_unittest5-inc.cc"
  31. }
  32. namespace test6 {
  33. #include "net/base/registry_controlled_domains/effective_tld_names_unittest6-inc.cc"
  34. }
  35. struct Expectation {
  36. const char* const key;
  37. int value;
  38. };
  39. void PrintTo(const Expectation& expectation, std::ostream* os) {
  40. *os << "{\"" << expectation.key << "\", " << expectation.value << "}";
  41. }
  42. class LookupStringInFixedSetTest : public testing::TestWithParam<Expectation> {
  43. protected:
  44. template <size_t N>
  45. int LookupInGraph(const unsigned char(&graph)[N], const char* key) {
  46. return LookupStringInFixedSet(graph, N, key, strlen(key));
  47. }
  48. };
  49. class Dafsa1Test : public LookupStringInFixedSetTest {};
  50. TEST_P(Dafsa1Test, BasicTest) {
  51. const Expectation& param = GetParam();
  52. EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
  53. }
  54. const Expectation kBasicTestCases[] = {
  55. {"", -1}, {"j", -1}, {"jp", 0}, {"jjp", -1}, {"jpp", -1},
  56. {"bar.jp", 2}, {"pref.bar.jp", 1}, {"c", 2}, {"b.c", 1}, {"priv.no", 4},
  57. };
  58. // Helper function for EnumerateDafsaLanaguage.
  59. void RecursivelyEnumerateDafsaLanguage(const FixedSetIncrementalLookup& lookup,
  60. std::vector<char>* sequence,
  61. std::vector<std::string>* language) {
  62. int result = lookup.GetResultForCurrentSequence();
  63. if (result != kDafsaNotFound) {
  64. std::string line(sequence->begin(), sequence->end());
  65. line += base::StringPrintf(", %d", result);
  66. language->emplace_back(std::move(line));
  67. }
  68. // Try appending each char value.
  69. for (char c = std::numeric_limits<char>::min();; ++c) {
  70. FixedSetIncrementalLookup continued_lookup = lookup;
  71. if (continued_lookup.Advance(c)) {
  72. sequence->push_back(c);
  73. size_t saved_language_size = language->size();
  74. RecursivelyEnumerateDafsaLanguage(continued_lookup, sequence, language);
  75. CHECK_LT(saved_language_size, language->size())
  76. << "DAFSA includes a branch to nowhere at node: "
  77. << std::string(sequence->begin(), sequence->end());
  78. sequence->pop_back();
  79. }
  80. if (c == std::numeric_limits<char>::max())
  81. break;
  82. }
  83. }
  84. // Uses FixedSetIncrementalLookup to build a vector of every string in the
  85. // language of the DAFSA.
  86. template <typename Graph>
  87. std::vector<std::string> EnumerateDafsaLanguage(const Graph& graph) {
  88. FixedSetIncrementalLookup query(graph, sizeof(Graph));
  89. std::vector<char> sequence;
  90. std::vector<std::string> language;
  91. RecursivelyEnumerateDafsaLanguage(query, &sequence, &language);
  92. return language;
  93. }
  94. INSTANTIATE_TEST_SUITE_P(LookupStringInFixedSetTest,
  95. Dafsa1Test,
  96. ::testing::ValuesIn(kBasicTestCases));
  97. class Dafsa3Test : public LookupStringInFixedSetTest {};
  98. // This DAFSA is constructed so that labels begin and end with unique
  99. // characters, which makes it impossible to merge labels. Each inner node
  100. // is about 100 bytes and a one byte offset can at most add 64 bytes to
  101. // previous offset. Thus the paths must go over two byte offsets.
  102. TEST_P(Dafsa3Test, TestDafsaTwoByteOffsets) {
  103. const Expectation& param = GetParam();
  104. EXPECT_EQ(param.value, LookupInGraph(test3::kDafsa, param.key));
  105. }
  106. const Expectation kTwoByteOffsetTestCases[] = {
  107. {"0________________________________________________________________________"
  108. "____________________________0",
  109. 0},
  110. {"7________________________________________________________________________"
  111. "____________________________7",
  112. 4},
  113. {"a________________________________________________________________________"
  114. "____________________________8",
  115. -1},
  116. };
  117. INSTANTIATE_TEST_SUITE_P(LookupStringInFixedSetTest,
  118. Dafsa3Test,
  119. ::testing::ValuesIn(kTwoByteOffsetTestCases));
  120. class Dafsa4Test : public LookupStringInFixedSetTest {};
  121. // This DAFSA is constructed so that labels begin and end with unique
  122. // characters, which makes it impossible to merge labels. The byte array
  123. // has a size of ~54k. A two byte offset can add at most add 8k to the
  124. // previous offset. Since we can skip only forward in memory, the nodes
  125. // representing the return values must be located near the end of the byte
  126. // array. The probability that we can reach from an arbitrary inner node to
  127. // a return value without using a three byte offset is small (but not zero).
  128. // The test is repeated with some different keys and with a reasonable
  129. // probability at least one of the tested paths has go over a three byte
  130. // offset.
  131. TEST_P(Dafsa4Test, TestDafsaThreeByteOffsets) {
  132. const Expectation& param = GetParam();
  133. EXPECT_EQ(param.value, LookupInGraph(test4::kDafsa, param.key));
  134. }
  135. const Expectation kThreeByteOffsetTestCases[] = {
  136. {"Z6_______________________________________________________________________"
  137. "_____________________________Z6",
  138. 0},
  139. {"Z7_______________________________________________________________________"
  140. "_____________________________Z7",
  141. 4},
  142. {"Za_______________________________________________________________________"
  143. "_____________________________Z8",
  144. -1},
  145. };
  146. INSTANTIATE_TEST_SUITE_P(LookupStringInFixedSetTest,
  147. Dafsa4Test,
  148. ::testing::ValuesIn(kThreeByteOffsetTestCases));
  149. class Dafsa5Test : public LookupStringInFixedSetTest {};
  150. // This DAFSA is constructed from words with similar prefixes but distinct
  151. // suffixes. The DAFSA will then form a trie with the implicit source node
  152. // as root.
  153. TEST_P(Dafsa5Test, TestDafsaJoinedPrefixes) {
  154. const Expectation& param = GetParam();
  155. EXPECT_EQ(param.value, LookupInGraph(test5::kDafsa, param.key));
  156. }
  157. const Expectation kJoinedPrefixesTestCases[] = {
  158. {"ai", 0}, {"bj", 4}, {"aak", 0}, {"bbl", 4},
  159. {"aaa", -1}, {"bbb", -1}, {"aaaam", 0}, {"bbbbn", 0},
  160. };
  161. INSTANTIATE_TEST_SUITE_P(LookupStringInFixedSetTest,
  162. Dafsa5Test,
  163. ::testing::ValuesIn(kJoinedPrefixesTestCases));
  164. class Dafsa6Test : public LookupStringInFixedSetTest {};
  165. // This DAFSA is constructed from words with similar suffixes but distinct
  166. // prefixes. The DAFSA will then form a trie with the implicit sink node as
  167. // root.
  168. TEST_P(Dafsa6Test, TestDafsaJoinedSuffixes) {
  169. const Expectation& param = GetParam();
  170. EXPECT_EQ(param.value, LookupInGraph(test6::kDafsa, param.key));
  171. }
  172. const Expectation kJoinedSuffixesTestCases[] = {
  173. {"ia", 0}, {"jb", 4}, {"kaa", 0}, {"lbb", 4},
  174. {"aaa", -1}, {"bbb", -1}, {"maaaa", 0}, {"nbbbb", 0},
  175. };
  176. INSTANTIATE_TEST_SUITE_P(LookupStringInFixedSetTest,
  177. Dafsa6Test,
  178. ::testing::ValuesIn(kJoinedSuffixesTestCases));
  179. // Validates that the generated DAFSA contains exactly the same information as
  180. // effective_tld_names_unittest1.gperf.
  181. TEST(LookupStringInFixedSetTest, Dafsa1EnumerateLanguage) {
  182. auto language = EnumerateDafsaLanguage(test1::kDafsa);
  183. // These are the lines of effective_tld_names_unittest1.gperf, in sorted
  184. // order.
  185. std::vector<std::string> expected_language = {
  186. "ac.jp, 0", "b.c, 1", "bar.baz.com, 0", "bar.jp, 2",
  187. "baz.bar.jp, 2", "c, 2", "jp, 0", "no, 0",
  188. "pref.bar.jp, 1", "priv.no, 4", "private, 4", "xn--fiqs8s, 0",
  189. };
  190. EXPECT_EQ(expected_language, language);
  191. }
  192. // Validates that the generated DAFSA contains exactly the same information as
  193. // effective_tld_names_unittest5.gperf.
  194. TEST(LookupStringInFixedSetTest, Dafsa5EnumerateLanguage) {
  195. auto language = EnumerateDafsaLanguage(test5::kDafsa);
  196. std::vector<std::string> expected_language = {
  197. "aaaam, 0", "aak, 0", "ai, 0", "bbbbn, 0", "bbl, 4", "bj, 4",
  198. };
  199. EXPECT_EQ(expected_language, language);
  200. }
  201. // Validates that the generated DAFSA contains exactly the same information as
  202. // effective_tld_names_unittest6.gperf.
  203. TEST(LookupStringInFixedSetTest, Dafsa6EnumerateLanguage) {
  204. auto language = EnumerateDafsaLanguage(test6::kDafsa);
  205. std::vector<std::string> expected_language = {
  206. "ia, 0", "jb, 4", "kaa, 0", "lbb, 4", "maaaa, 0", "nbbbb, 0",
  207. };
  208. EXPECT_EQ(expected_language, language);
  209. }
  210. } // namespace
  211. } // namespace net