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

net/base/lookup_string_in_fixed_set_unittest.cc

 // 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.
 
 #include "net/base/lookup_string_in_fixed_set.h"
 
 #include <string.h>
+
+#include <algorithm>
+#include <limits>
 #include <ostream>
+#include <utility>
+#include <vector>
 
+#include "base/base_paths.h"
+#include "base/files/file_path.h"
+#include "base/files/file_util.h"
+#include "base/path_service.h"
+#include "base/strings/string_util.h"
+#include "base/strings/stringprintf.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
 namespace {
 namespace test1 {
 #include "net/base/registry_controlled_domains/effective_tld_names_unittest1-inc.cc"
 }
 namespace test3 {
 #include "net/base/registry_controlled_domains/effective_tld_names_unittest3-inc.cc"
 }
@@ skipping 29 matching lines @@
 TEST_P(Dafsa1Test, BasicTest) {
   const Expectation& param = GetParam();
   EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
 }
 
 const Expectation kBasicTestCases[] = {
     {"", -1},      {"j", -1},          {"jp", 0}, {"jjp", -1}, {"jpp", -1},
     {"bar.jp", 2}, {"pref.bar.jp", 1}, {"c", 2},  {"b.c", 1},  {"priv.no", 4},
 };
 
+// Helper function for EnumerateDafsaLanaguage.
+void RecursivelyEnumerateDafsaLanguage(const FixedSetIncrementalLookup& lookup,
+                                       std::vector<char>* sequence,
+                                       std::vector<std::string>* language) {
+  int result = lookup.GetResultForCurrentSequence();
+  if (result != kDafsaNotFound) {
+    std::string line(sequence->begin(), sequence->end());
+    line += base::StringPrintf(", %d", result);
+    language->emplace_back(std::move(line));
+  }
+  // Try appending each char value.
+  for (char c = std::numeric_limits<char>::min();; ++c) {
+    FixedSetIncrementalLookup continued_lookup = lookup;
+    if (continued_lookup.Advance(c)) {
+      sequence->push_back(c);
+      size_t saved_language_size = language->size();
+      RecursivelyEnumerateDafsaLanguage(continued_lookup, sequence, language);
+      CHECK_LT(saved_language_size, language->size())
+          << "DAFSA includes a branch to nowhere at node: "
+          << std::string(sequence->begin(), sequence->end());
+      sequence->pop_back();
+    }
+    if (c == std::numeric_limits<char>::max())
+      break;
+  }
+}
+
+// Uses FixedSetIncrementalLookup to build a vector of every string in the
+// language of the DAFSA.
+template <typename Graph>
+std::vector<std::string> EnumerateDafsaLanguage(const Graph& graph) {
+  FixedSetIncrementalLookup query(graph, sizeof(Graph));
+  std::vector<char> sequence;
+  std::vector<std::string> language;
+  RecursivelyEnumerateDafsaLanguage(query, &sequence, &language);
+  return language;
+}
+
 INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
                         Dafsa1Test,
                         ::testing::ValuesIn(kBasicTestCases));
 
 class Dafsa3Test : public LookupStringInFixedSetTest {};
 
 // This DAFSA is constructed so that labels begin and end with unique
 // characters, which makes it impossible to merge labels. Each inner node
 // is about 100 bytes and a one byte offset can at most add 64 bytes to
 // previous offset. Thus the paths must go over two byte offsets.
@@ skipping 82 matching lines @@
 
 const Expectation kJoinedSuffixesTestCases[] = {
     {"ia", 0},   {"jb", 4},   {"kaa", 0},   {"lbb", 4},
     {"aaa", -1}, {"bbb", -1}, {"maaaa", 0}, {"nbbbb", 0},
 };
 
 INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
                         Dafsa6Test,
                         ::testing::ValuesIn(kJoinedSuffixesTestCases));
 
+// Validates that the generated DAFSA contains exactly the same information as
+// effective_tld_names_unittest1.gperf.
+TEST(LookupStringInFixedSetTest, Dafsa1EnumerateLanguage) {
+  auto language = EnumerateDafsaLanguage(test1::kDafsa);
+
+  // These are the lines of effective_tld_names_unittest1.gperf, in sorted
+  // order.
+  std::vector<std::string> expected_language = {
+      "ac.jp, 0",       "b.c, 1",     "bar.baz.com, 0", "bar.jp, 2",
+      "baz.bar.jp, 2",  "c, 2",       "jp, 0",          "no, 0",
+      "pref.bar.jp, 1", "priv.no, 4", "private, 4",     "xn--fiqs8s, 0",
+  };
+
+  EXPECT_EQ(expected_language, language);
+}
+
+// Validates that the generated DAFSA contains exactly the same information as
+// effective_tld_names_unittest5.gperf.
+TEST(LookupStringInFixedSetTest, Dafsa5EnumerateLanguage) {
+  auto language = EnumerateDafsaLanguage(test5::kDafsa);
+
+  std::vector<std::string> expected_language = {
+      "aaaam, 0", "aak, 0", "ai, 0", "bbbbn, 0", "bbl, 4", "bj, 4",
+  };
+
+  EXPECT_EQ(expected_language, language);
+}
+
+// Validates that the generated DAFSA contains exactly the same information as
+// effective_tld_names_unittest6.gperf.
+TEST(LookupStringInFixedSetTest, Dafsa6EnumerateLanguage) {
+  auto language = EnumerateDafsaLanguage(test6::kDafsa);
+
+  std::vector<std::string> expected_language = {
+      "ia, 0", "jb, 4", "kaa, 0", "lbb, 4", "maaaa, 0", "nbbbb, 0",
+  };
+
+  EXPECT_EQ(expected_language, language);
+}
+
 }  // namespace
 }  // namespace net