Factor out the string lookup code from registry_controlled_domains

net/base/lookup_string_in_fixed_set_unittest.cc

Index: net/base/lookup_string_in_fixed_set_unittest.cc
diff --git a/components/data_reduction_proxy/core/common/data_reduction_proxy_client_config_parser_unittest.cc b/net/base/lookup_string_in_fixed_set_unittest.cc
similarity index 5%
copy from components/data_reduction_proxy/core/common/data_reduction_proxy_client_config_parser_unittest.cc
copy to net/base/lookup_string_in_fixed_set_unittest.cc
index e852651195443cdf71fda389a52e2460b14b720d..82e6c22d84be20d215c7667ea39ee9127d8f37ff 100644
--- a/components/data_reduction_proxy/core/common/data_reduction_proxy_client_config_parser_unittest.cc
+++ b/net/base/lookup_string_in_fixed_set_unittest.cc
@@ -2,130 +2,161 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "components/data_reduction_proxy/core/common/data_reduction_proxy_client_config_parser.h"
+#include "net/base/lookup_string_in_fixed_set.h"
 
-#include <string>
+#include <string.h>
+#include <ostream>
 
-#include "base/time/time.h"
-#include "components/data_reduction_proxy/proto/client_config.pb.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
-namespace data_reduction_proxy {
-
+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"
+}
+namespace test4 {
+#include "net/base/registry_controlled_domains/effective_tld_names_unittest4-inc.cc"
+}
+namespace test5 {
+#include "net/base/registry_controlled_domains/effective_tld_names_unittest5-inc.cc"
+}
+namespace test6 {
+#include "net/base/registry_controlled_domains/effective_tld_names_unittest6-inc.cc"
+}
 
-const char kFutureTime[] = "31 Dec 2020 23:59:59.001";
+struct Expectation {
+  const char* const key;
+  int value;
+};
 
-}  // namespace
+void PrintTo(const Expectation& expectation, std::ostream* os) {
+  *os << "{\"" << expectation.key << "\", " << expectation.value << "}";
+}
 
-class DataReductionProxyClientConfigParserTest : public testing::Test {
+class LookupStringInFixedSetTest : public testing::TestWithParam<Expectation> {
  protected:
-  void SetUp() override {
-    EXPECT_TRUE(base::Time::FromUTCString(kFutureTime, &future_time_));
+  template <size_t N>
+  int LookupInGraph(const unsigned char(&graph)[N], const char* key) {
+    return LookupStringInFixedSet(graph, N, key, strlen(key));
   }
+};
 
-  const base::Time& GetFutureTime() {
-    return future_time_;
-  }
+class Dafsa1Test : public LookupStringInFixedSetTest {};
+
+TEST_P(Dafsa1Test, BasicTest) {
+  const Expectation& param = GetParam();
+  EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
+}
 
- private:
-  base::Time future_time_;
+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},
 };
 
-TEST_F(DataReductionProxyClientConfigParserTest, TimetoTimestamp) {
-  const struct {
-    std::string test_name;
-    base::Time time;
-    int64 expected_seconds;
-    int32 expected_nanos;
-  } tests[] = {
-      {
-       "Epoch", base::Time::UnixEpoch(), 0, 0,
-      },
-      {
-       "One day minus one second",
-       base::Time::UnixEpoch() + base::TimeDelta::FromDays(1) -
-           base::TimeDelta::FromMicroseconds(1),
-       24 * 60 * 60 - 1,
-       0,
-      },
-      {
-       "Future time",
-       GetFutureTime(),
-       // 2020-12-31T23:59:59.001Z
-       1609459199,
-       0,
-      },
-  };
-
-  for (const auto& test : tests) {
-    Timestamp ts;
-    config_parser::TimetoTimestamp(test.time, &ts);
-    EXPECT_EQ(test.expected_seconds, ts.seconds()) << test.test_name;
-    EXPECT_EQ(test.expected_nanos, ts.nanos()) << test.test_name;
-  }
+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.
+TEST_P(Dafsa3Test, TestDafsaTwoByteOffsets) {
+  const Expectation& param = GetParam();
+  EXPECT_EQ(param.value, LookupInGraph(test3::kDafsa, param.key));
 }
 
-TEST_F(DataReductionProxyClientConfigParserTest, TimeDeltaToFromDuration) {
-  const struct {
-    std::string test_name;
-    base::TimeDelta time_delta;
-    int64 seconds;
-    int32 nanos;
-  } tests[] = {
-      {
-          "Second", base::TimeDelta::FromSeconds(1), 1, 0,
-      },
-      {
-          "-1 Second", base::TimeDelta::FromSeconds(-1), -1, 0,
-      },
-  };
-
-  for (const auto& test : tests) {
-    Duration duration;
-    config_parser::TimeDeltatoDuration(test.time_delta, &duration);
-    EXPECT_EQ(test.seconds, duration.seconds()) << test.test_name;
-    EXPECT_EQ(test.nanos, duration.nanos()) << test.test_name;
-    duration.set_seconds(test.seconds);
-    duration.set_nanos(test.nanos);
-    EXPECT_EQ(test.time_delta, config_parser::DurationToTimeDelta(duration))
-        << test.test_name;
-  }
+const Expectation kTwoByteOffsetTestCases[] = {
+    {"0________________________________________________________________________"
+     "____________________________0",
+     0},
+    {"7________________________________________________________________________"
+     "____________________________7",
+     4},
+    {"a________________________________________________________________________"
+     "____________________________8",
+     -1},
+};
+
+INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
+                        Dafsa3Test,
+                        ::testing::ValuesIn(kTwoByteOffsetTestCases));
+
+class Dafsa4Test : public LookupStringInFixedSetTest {};
+
+// This DAFSA is constructed so that labels begin and end with unique
+// characters, which makes it impossible to merge labels. The byte array
+// has a size of ~54k. A two byte offset can add at most add 8k to the
+// previous offset. Since we can skip only forward in memory, the nodes
+// representing the return values must be located near the end of the byte
+// array. The probability that we can reach from an arbitrary inner node to
+// a return value without using a three byte offset is small (but not zero).
+// The test is repeated with some different keys and with a reasonable
+// probability at least one of the tested paths has go over a three byte
+// offset.
+TEST_P(Dafsa4Test, TestDafsaThreeByteOffsets) {
+  const Expectation& param = GetParam();
+  EXPECT_EQ(param.value, LookupInGraph(test4::kDafsa, param.key));
 }
 
-TEST_F(DataReductionProxyClientConfigParserTest, TimestampToTime) {
-  const struct {
-    std::string test_name;
-    int64 timestamp_seconds;
-    int32 timestamp_nanos;
-    base::Time expected_time;
-  } tests[] = {
-      {
-       "Epoch", 0, 0, base::Time::UnixEpoch(),
-      },
-      {
-       "One day minus one second",
-       24 * 60 * 60 - 1,
-       base::Time::kNanosecondsPerSecond - 1,
-       base::Time::UnixEpoch() + base::TimeDelta::FromDays(1) -
-           base::TimeDelta::FromMicroseconds(1),
-      },
-      {
-       "Future time",
-       // 2020-12-31T23:59:59.001Z
-       1609459199,
-       1000000,
-       GetFutureTime(),
-      },
-  };
-
-  for (const auto& test : tests) {
-    Timestamp ts;
-    ts.set_seconds(test.timestamp_seconds);
-    ts.set_nanos(test.timestamp_nanos);
-    EXPECT_EQ(test.expected_time, config_parser::TimestampToTime(ts))
-        << test.test_name;
-  }
+const Expectation kThreeByteOffsetTestCases[] = {
+    {"Z6_______________________________________________________________________"
+     "_____________________________Z6",
+     0},
+    {"Z7_______________________________________________________________________"
+     "_____________________________Z7",
+     4},
+    {"Za_______________________________________________________________________"
+     "_____________________________Z8",
+     -1},
+};
+
+INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
+                        Dafsa4Test,
+                        ::testing::ValuesIn(kThreeByteOffsetTestCases));
+
+class Dafsa5Test : public LookupStringInFixedSetTest {};
+
+// This DAFSA is constructed from words with similar prefixes but distinct
+// suffixes. The DAFSA will then form a trie with the implicit source node
+// as root.
+TEST_P(Dafsa5Test, TestDafsaJoinedPrefixes) {
+  const Expectation& param = GetParam();
+  EXPECT_EQ(param.value, LookupInGraph(test5::kDafsa, param.key));
 }
 
-}  // namespace data_reduction_proxy
+const Expectation kJoinedPrefixesTestCases[] = {
+    {"ai", 0},   {"bj", 4},   {"aak", 0},   {"bbl", 4},
+    {"aaa", -1}, {"bbb", -1}, {"aaaam", 0}, {"bbbbn", 0},
+};
+
+INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
+                        Dafsa5Test,
+                        ::testing::ValuesIn(kJoinedPrefixesTestCases));
+
+class Dafsa6Test : public LookupStringInFixedSetTest {};
+
+// This DAFSA is constructed from words with similar suffixes but distinct
+// prefixes. The DAFSA will then form a trie with the implicit sink node as
+// root.
+TEST_P(Dafsa6Test, TestDafsaJoinedSuffixes) {
+  const Expectation& param = GetParam();
+  EXPECT_EQ(param.value, LookupInGraph(test6::kDafsa, param.key));
+}
+
+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));
+
+}  // namespace
+}  // namespace net