substring_set_matcher_unittest.cc 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. // Copyright 2013 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 "base/substring_set_matcher/substring_set_matcher.h"
  5. #include <stddef.h>
  6. #include <set>
  7. #include <string>
  8. #include <vector>
  9. #include "testing/gmock/include/gmock/gmock.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. namespace base {
  12. namespace {
  13. void TestOnePattern(const std::string& test_string,
  14. const std::string& pattern,
  15. bool is_match) {
  16. std::string test = "TestOnePattern(" + test_string + ", " + pattern + ", " +
  17. (is_match ? "1" : "0") + ")";
  18. std::vector<MatcherStringPattern> patterns;
  19. patterns.emplace_back(pattern, 1);
  20. SubstringSetMatcher matcher;
  21. ASSERT_TRUE(matcher.Build(patterns));
  22. std::set<MatcherStringPattern::ID> matches;
  23. matcher.Match(test_string, &matches);
  24. size_t expected_matches = (is_match ? 1 : 0);
  25. EXPECT_EQ(expected_matches, matches.size()) << test;
  26. EXPECT_EQ(is_match, matches.find(1) != matches.end()) << test;
  27. }
  28. void TestTwoPatterns(const std::string& test_string,
  29. const std::string& pattern_1,
  30. const std::string& pattern_2,
  31. bool is_match_1,
  32. bool is_match_2) {
  33. std::string test = "TestTwoPatterns(" + test_string + ", " + pattern_1 +
  34. ", " + pattern_2 + ", " + (is_match_1 ? "1" : "0") + ", " +
  35. (is_match_2 ? "1" : "0") + ")";
  36. ASSERT_NE(pattern_1, pattern_2);
  37. MatcherStringPattern substring_pattern_1(pattern_1, 1);
  38. MatcherStringPattern substring_pattern_2(pattern_2, 2);
  39. // In order to make sure that the order in which patterns are registered
  40. // does not make any difference we try both permutations.
  41. for (int permutation = 0; permutation < 2; ++permutation) {
  42. std::vector<const MatcherStringPattern*> patterns;
  43. if (permutation == 0) {
  44. patterns.push_back(&substring_pattern_1);
  45. patterns.push_back(&substring_pattern_2);
  46. } else {
  47. patterns.push_back(&substring_pattern_2);
  48. patterns.push_back(&substring_pattern_1);
  49. }
  50. SubstringSetMatcher matcher;
  51. ASSERT_TRUE(matcher.Build(patterns));
  52. std::set<MatcherStringPattern::ID> matches;
  53. matcher.Match(test_string, &matches);
  54. size_t expected_matches = (is_match_1 ? 1 : 0) + (is_match_2 ? 1 : 0);
  55. EXPECT_EQ(expected_matches, matches.size()) << test;
  56. EXPECT_EQ(is_match_1, matches.find(1) != matches.end()) << test;
  57. EXPECT_EQ(is_match_2, matches.find(2) != matches.end()) << test;
  58. }
  59. }
  60. } // namespace
  61. TEST(SubstringSetMatcherTest, TestMatcher) {
  62. // Test overlapping patterns
  63. // String abcde
  64. // Pattern 1 bc
  65. // Pattern 2 cd
  66. TestTwoPatterns("abcde", "bc", "cd", true, true);
  67. if (HasFatalFailure())
  68. return;
  69. // Test subpatterns - part 1
  70. // String abcde
  71. // Pattern 1 bc
  72. // Pattern 2 b
  73. TestTwoPatterns("abcde", "bc", "b", true, true);
  74. if (HasFatalFailure())
  75. return;
  76. // Test subpatterns - part 2
  77. // String abcde
  78. // Pattern 1 bc
  79. // Pattern 2 c
  80. TestTwoPatterns("abcde", "bc", "c", true, true);
  81. if (HasFatalFailure())
  82. return;
  83. // Test identical matches
  84. // String abcde
  85. // Pattern 1 abcde
  86. TestOnePattern("abcde", "abcde", true);
  87. if (HasFatalFailure())
  88. return;
  89. // Test multiple matches
  90. // String aaaaa
  91. // Pattern 1 a
  92. TestOnePattern("abcde", "a", true);
  93. if (HasFatalFailure())
  94. return;
  95. // Test matches at beginning and end
  96. // String abcde
  97. // Pattern 1 ab
  98. // Pattern 2 de
  99. TestTwoPatterns("abcde", "ab", "de", true, true);
  100. if (HasFatalFailure())
  101. return;
  102. // Test non-match
  103. // String abcde
  104. // Pattern 1 fg
  105. TestOnePattern("abcde", "fg", false);
  106. if (HasFatalFailure())
  107. return;
  108. // Test empty pattern and too long pattern
  109. // String abcde
  110. // Pattern 1
  111. // Pattern 2 abcdef
  112. TestTwoPatterns("abcde", std::string(), "abcdef", true, false);
  113. if (HasFatalFailure())
  114. return;
  115. }
  116. TEST(SubstringSetMatcherTest, TestMatcher2) {
  117. MatcherStringPattern pattern_1("a", 1);
  118. MatcherStringPattern pattern_2("b", 2);
  119. MatcherStringPattern pattern_3("c", 3);
  120. std::vector<const MatcherStringPattern*> patterns = {&pattern_1, &pattern_2,
  121. &pattern_3};
  122. auto matcher = std::make_unique<SubstringSetMatcher>();
  123. ASSERT_TRUE(matcher->Build(patterns));
  124. std::set<MatcherStringPattern::ID> matches;
  125. matcher->Match("abd", &matches);
  126. EXPECT_EQ(2u, matches.size());
  127. EXPECT_TRUE(matches.end() != matches.find(1));
  128. EXPECT_TRUE(matches.end() != matches.find(2));
  129. patterns = {&pattern_1, &pattern_3};
  130. matcher = std::make_unique<SubstringSetMatcher>();
  131. ASSERT_TRUE(matcher->Build(patterns));
  132. matches.clear();
  133. matcher->Match("abd", &matches);
  134. EXPECT_EQ(1u, matches.size());
  135. EXPECT_TRUE(matches.end() != matches.find(1));
  136. EXPECT_TRUE(matches.end() == matches.find(2));
  137. matcher = std::make_unique<SubstringSetMatcher>();
  138. ASSERT_TRUE(matcher->Build(std::vector<const MatcherStringPattern*>()));
  139. EXPECT_TRUE(matcher->IsEmpty());
  140. }
  141. TEST(SubstringSetMatcherTest, TestMatcher3) {
  142. std::string text = "abcde";
  143. std::vector<MatcherStringPattern> patterns;
  144. int id = 0;
  145. // Add all substrings of this string, including empty string.
  146. patterns.emplace_back("", id++);
  147. for (size_t i = 0; i < text.length(); i++) {
  148. for (size_t j = i; j < text.length(); j++) {
  149. patterns.emplace_back(text.substr(i, j - i + 1), id++);
  150. }
  151. }
  152. SubstringSetMatcher matcher;
  153. matcher.Build(patterns);
  154. std::set<MatcherStringPattern::ID> matches;
  155. matcher.Match(text, &matches);
  156. EXPECT_EQ(patterns.size(), matches.size());
  157. for (const MatcherStringPattern& pattern : patterns) {
  158. EXPECT_TRUE(matches.find(pattern.id()) != matches.end())
  159. << pattern.pattern();
  160. }
  161. }
  162. TEST(SubstringSetMatcherTest, TestEmptyMatcher) {
  163. std::vector<MatcherStringPattern> patterns;
  164. SubstringSetMatcher matcher;
  165. matcher.Build(patterns);
  166. std::set<MatcherStringPattern::ID> matches;
  167. matcher.Match("abd", &matches);
  168. EXPECT_TRUE(matches.empty());
  169. EXPECT_TRUE(matcher.IsEmpty());
  170. }
  171. } // namespace base