| // Copyright 2010-2015, Google Inc. |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following disclaimer |
| // in the documentation and/or other materials provided with the |
| // distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived from |
| // this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include "storage/louds/louds_trie.h" |
| |
| #include <limits> |
| #include <string> |
| |
| #include "base/port.h" |
| #include "storage/louds/key_expansion_table.h" |
| #include "storage/louds/louds_trie_builder.h" |
| #include "testing/base/public/gunit.h" |
| |
| // undef max macro if defined. |
| #ifdef max |
| #undef max |
| #endif // max |
| |
| namespace mozc { |
| namespace storage { |
| namespace louds { |
| namespace { |
| |
| class LoudsTrieTest : public ::testing::Test { |
| }; |
| |
| class TestCallback : public LoudsTrie::Callback { |
| public: |
| TestCallback() : current_index_(0), limit_(numeric_limits<size_t>::max()) { |
| } |
| |
| void AddExpectation( |
| const string &s, size_t len, int id, ResultType result_type) { |
| expectation_list_.push_back(Expectation()); |
| Expectation &expectation = expectation_list_.back(); |
| expectation.s = s; |
| expectation.len = len; |
| expectation.id = id; |
| expectation.result_type = result_type; |
| } |
| |
| virtual ResultType Run(const char *s, size_t len, int id) { |
| if (current_index_ >= expectation_list_.size()) { |
| ADD_FAILURE() << "Too many invocations: " << expectation_list_.size() |
| << " vs " << current_index_; |
| // Quit the callback. |
| return SEARCH_DONE; |
| } |
| const Expectation &expectation = expectation_list_[current_index_]; |
| EXPECT_EQ(expectation.s, string(s, len)) << current_index_; |
| EXPECT_EQ(expectation.len, len) << current_index_; |
| EXPECT_EQ(expectation.id, id) << current_index_; |
| ++current_index_; |
| return expectation.result_type; |
| } |
| |
| size_t num_invoked() const { return current_index_; } |
| |
| private: |
| struct Expectation { |
| string s; |
| size_t len; |
| int id; |
| ResultType result_type; |
| }; |
| vector<Expectation> expectation_list_; |
| size_t current_index_; |
| size_t limit_; |
| |
| DISALLOW_COPY_AND_ASSIGN(TestCallback); |
| }; |
| |
| TEST_F(LoudsTrieTest, ExactSearch) { |
| LoudsTrieBuilder builder; |
| builder.Add("a"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("ae"); |
| builder.Add("aecd"); |
| builder.Add("b"); |
| builder.Add("bcx"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| EXPECT_EQ(builder.GetId("a"), trie.ExactSearch("a")); |
| EXPECT_EQ(builder.GetId("abc"), trie.ExactSearch("abc")); |
| EXPECT_EQ(builder.GetId("abcd"), trie.ExactSearch("abcd")); |
| EXPECT_EQ(builder.GetId("ae"), trie.ExactSearch("ae")); |
| EXPECT_EQ(builder.GetId("aecd"), trie.ExactSearch("aecd")); |
| EXPECT_EQ(builder.GetId("b"), trie.ExactSearch("b")); |
| EXPECT_EQ(builder.GetId("bcx"), trie.ExactSearch("bcx")); |
| EXPECT_EQ(-1, trie.ExactSearch("")); |
| EXPECT_EQ(-1, trie.ExactSearch("ab")); |
| EXPECT_EQ(-1, trie.ExactSearch("aa")); |
| EXPECT_EQ(-1, trie.ExactSearch("aec")); |
| EXPECT_EQ(-1, trie.ExactSearch("aecx")); |
| EXPECT_EQ(-1, trie.ExactSearch("aecdf")); |
| EXPECT_EQ(-1, trie.ExactSearch("abcdefghi")); |
| EXPECT_EQ(-1, trie.ExactSearch("bc")); |
| EXPECT_EQ(-1, trie.ExactSearch("bca")); |
| EXPECT_EQ(-1, trie.ExactSearch("bcxyz")); |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PrefixSearch) { |
| LoudsTrieBuilder builder; |
| builder.Add("aa"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abd"); |
| builder.Add("ebd"); |
| builder.Add("\x01\xFF"); |
| builder.Add("\x01\xFF\xFF"); |
| |
| builder.Build(); |
| |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation( |
| "ab", 2, builder.GetId("ab"), LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation( |
| "abc", 3, builder.GetId("abc"), LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PrefixSearch("abc", &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation( |
| "ab", 2, builder.GetId("ab"), LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PrefixSearch("abxxxxxxx", &callback); |
| EXPECT_EQ(1, callback.num_invoked()); |
| } |
| |
| { |
| // Make sure that non-ascii characters can be found, too. |
| TestCallback callback; |
| callback.AddExpectation("\x01\xFF", 2, builder.GetId("\x01\xFF"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("\x01\xFF\xFF", 3, builder.GetId("\x01\xFF\xFF"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PrefixSearch("\x01\xFF\xFF", &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PrefixSearchWithLimit) { |
| LoudsTrieBuilder builder; |
| builder.Add("aa"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abcde"); |
| builder.Add("abcdef"); |
| builder.Add("abd"); |
| builder.Add("ebd"); |
| |
| builder.Build(); |
| |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_DONE); |
| |
| trie.PrefixSearch("abcdef", &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_DONE); |
| |
| trie.PrefixSearch("abdxxx", &callback); |
| EXPECT_EQ(1, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PrefixSearchWithKeyExpansion) { |
| LoudsTrieBuilder builder; |
| builder.Add("abc"); |
| builder.Add("adc"); |
| builder.Add("cbc"); |
| builder.Add("ddc"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| KeyExpansionTable key_expansion_table; |
| key_expansion_table.Add('b', "d"); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("adc", 3, builder.GetId("adc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PrefixSearchWithKeyExpansion("abc", key_expansion_table, &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("adc", 3, builder.GetId("adc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| trie.PrefixSearchWithKeyExpansion("adc", key_expansion_table, &callback); |
| EXPECT_EQ(1, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PrefixSearchCulling) { |
| LoudsTrieBuilder builder; |
| builder.Add("a"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("ae"); |
| builder.Add("aec"); |
| builder.Add("aecd"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| KeyExpansionTable key_expansion_table; |
| key_expansion_table.Add('b', "e"); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("a", 1, builder.GetId("a"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CULL); |
| // No callback for abcd, but ones for ae... should be found. |
| callback.AddExpectation("ae", 2, builder.GetId("ae"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("aec", 3, builder.GetId("aec"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("aecd", 4, builder.GetId("aecd"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PrefixSearchWithKeyExpansion("abcd", key_expansion_table, &callback); |
| EXPECT_EQ(6, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PredictiveSearch) { |
| LoudsTrieBuilder builder; |
| builder.Add("aa"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abcde"); |
| builder.Add("abcdef"); |
| builder.Add("abcea"); |
| builder.Add("abcef"); |
| builder.Add("abd"); |
| builder.Add("ebd"); |
| builder.Add("\x01\xFF"); |
| builder.Add("\x01\xFF\xFF"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcd", 4, builder.GetId("abcd"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcde", 5, builder.GetId("abcde"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcdef", 6, builder.GetId("abcdef"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcea", 5, builder.GetId("abcea"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcef", 5, builder.GetId("abcef"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearch("abc", &callback); |
| EXPECT_EQ(6, callback.num_invoked()); |
| } |
| { |
| TestCallback callback; |
| callback.AddExpectation("aa", 2, builder.GetId("aa"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcd", 4, builder.GetId("abcd"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcde", 5, builder.GetId("abcde"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcdef", 6, builder.GetId("abcdef"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcea", 5, builder.GetId("abcea"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcef", 5, builder.GetId("abcef"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abd", 3, builder.GetId("abd"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearch("a", &callback); |
| EXPECT_EQ(9, callback.num_invoked()); |
| } |
| { |
| // Make sure non-ascii characters can be found. |
| TestCallback callback; |
| callback.AddExpectation("\x01\xFF", 2, builder.GetId("\x01\xFF"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("\x01\xFF\xFF", 3, builder.GetId("\x01\xFF\xFF"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearch("\x01", &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PredictiveSearchWithLimit) { |
| LoudsTrieBuilder builder; |
| builder.Add("aa"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abcde"); |
| builder.Add("abcdef"); |
| builder.Add("abcea"); |
| builder.Add("abcef"); |
| builder.Add("abd"); |
| builder.Add("ebd"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abcd", 4, builder.GetId("abcd"), |
| LoudsTrie::Callback::SEARCH_DONE); |
| |
| trie.PredictiveSearch("abc", &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| { |
| TestCallback callback; |
| callback.AddExpectation("aa", 2, builder.GetId("aa"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_DONE); |
| |
| trie.PredictiveSearch("a", &callback); |
| EXPECT_EQ(3, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PredictiveSearchWithKeyExpansion) { |
| LoudsTrieBuilder builder; |
| builder.Add("abc"); |
| builder.Add("adc"); |
| builder.Add("cbc"); |
| builder.Add("ddc"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| KeyExpansionTable key_expansion_table; |
| key_expansion_table.Add('b', "d"); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("adc", 3, builder.GetId("adc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearchWithKeyExpansion( |
| "ab", key_expansion_table, &callback); |
| EXPECT_EQ(2, callback.num_invoked()); |
| } |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("adc", 3, builder.GetId("adc"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| trie.PredictiveSearchWithKeyExpansion( |
| "ad", key_expansion_table, &callback); |
| EXPECT_EQ(1, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PredictiveSearchCulling) { |
| LoudsTrieBuilder builder; |
| builder.Add("a"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("ae"); |
| builder.Add("aec"); |
| builder.Add("aecd"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("a", 1, builder.GetId("a"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("ab", 2, builder.GetId("ab"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CULL); |
| // No callback for abcd. |
| callback.AddExpectation("ae", 2, builder.GetId("ae"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("aec", 3, builder.GetId("aec"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("aecd", 4, builder.GetId("aecd"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearch("a", &callback); |
| EXPECT_EQ(6, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, PredictiveSearchCulling2) { |
| LoudsTrieBuilder builder; |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abcde"); |
| builder.Add("abxy"); |
| builder.Add("abxyz"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| { |
| TestCallback callback; |
| callback.AddExpectation("abc", 3, builder.GetId("abc"), |
| LoudsTrie::Callback::SEARCH_CULL); |
| callback.AddExpectation("abxy", 4, builder.GetId("abxy"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| callback.AddExpectation("abxyz", 5, builder.GetId("abxyz"), |
| LoudsTrie::Callback::SEARCH_CONTINUE); |
| |
| trie.PredictiveSearch("a", &callback); |
| EXPECT_EQ(3, callback.num_invoked()); |
| } |
| |
| trie.Close(); |
| } |
| |
| TEST_F(LoudsTrieTest, Reverse) { |
| LoudsTrieBuilder builder; |
| builder.Add("aa"); |
| builder.Add("ab"); |
| builder.Add("abc"); |
| builder.Add("abcd"); |
| builder.Add("abcde"); |
| builder.Add("abcdef"); |
| builder.Add("abcea"); |
| builder.Add("abcef"); |
| builder.Add("abd"); |
| builder.Add("ebd"); |
| |
| builder.Build(); |
| LoudsTrie trie; |
| trie.Open(reinterpret_cast<const uint8 *>(builder.image().data())); |
| |
| char buffer[LoudsTrie::kMaxDepth + 1]; |
| EXPECT_STREQ("aa", trie.Reverse(builder.GetId("aa"), buffer)); |
| EXPECT_STREQ("ab", trie.Reverse(builder.GetId("ab"), buffer)); |
| EXPECT_STREQ("abc", trie.Reverse(builder.GetId("abc"), buffer)); |
| EXPECT_STREQ("abcd", trie.Reverse(builder.GetId("abcd"), buffer)); |
| EXPECT_STREQ("abcde", trie.Reverse(builder.GetId("abcde"), buffer)); |
| EXPECT_STREQ("abcdef", trie.Reverse(builder.GetId("abcdef"), buffer)); |
| EXPECT_STREQ("abcea", trie.Reverse(builder.GetId("abcea"), buffer)); |
| EXPECT_STREQ("abcef", trie.Reverse(builder.GetId("abcef"), buffer)); |
| EXPECT_STREQ("abd", trie.Reverse(builder.GetId("abd"), buffer)); |
| EXPECT_STREQ("ebd", trie.Reverse(builder.GetId("ebd"), buffer)); |
| EXPECT_STREQ("", trie.Reverse(-1, buffer)); |
| trie.Close(); |
| } |
| |
| } // namespace |
| } // namespace louds |
| } // namespace storage |
| } // namespace mozc |
