text: // 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 <ostream>
  
  #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"
  }
  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"
  }
  
  struct Expectation {
    const char* const key;
    int value;
  };
  
  void PrintTo(const Expectation& expectation, std::ostream* os) {
    *os << "{\"" << expectation.key << "\", " << expectation.value << "}";
  }
  
  class LookupStringInFixedSetTest : public testing::TestWithParam<Expectation> {
   protected:
    template <size_t N>
    int LookupInGraph(const unsigned char(&graph)[N], const char* key) {
      return LookupStringInFixedSet(graph, N, key, strlen(key));
    }
  };
  
  class Dafsa1Test : public LookupStringInFixedSetTest {};
  
  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},
  };
  
  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));
  }
  
  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));
  }
  
  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));
  }
  
  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
  