string_search_unittest.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396
  1. // Copyright (c) 2011 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/i18n/string_search.h"
  5. #include <stddef.h>
  6. #include <string>
  7. #include <vector>
  8. #include "base/i18n/rtl.h"
  9. #include "base/strings/utf_string_conversions.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. #include "third_party/icu/source/i18n/unicode/usearch.h"
  12. namespace base {
  13. namespace i18n {
  14. #define EXPECT_MATCH_IGNORE_CASE(find_this, in_this, ex_start, ex_len) \
  15. { \
  16. size_t index = 0; \
  17. size_t length = 0; \
  18. EXPECT_TRUE(StringSearchIgnoringCaseAndAccents(find_this, in_this, &index, \
  19. &length)); \
  20. EXPECT_EQ(ex_start, index); \
  21. EXPECT_EQ(ex_len, length); \
  22. index = 0; \
  23. length = 0; \
  24. EXPECT_TRUE( \
  25. StringSearch(find_this, in_this, &index, &length, false, true)); \
  26. EXPECT_EQ(ex_start, index); \
  27. EXPECT_EQ(ex_len, length); \
  28. }
  29. #define EXPECT_MATCH_SENSITIVE(find_this, in_this, ex_start, ex_len) \
  30. { \
  31. size_t index = 0; \
  32. size_t length = 0; \
  33. EXPECT_TRUE( \
  34. StringSearch(find_this, in_this, &index, &length, true, true)); \
  35. EXPECT_EQ(ex_start, index); \
  36. EXPECT_EQ(ex_len, length); \
  37. }
  38. #define EXPECT_MATCH_IGNORE_CASE_BACKWARDS(find_this, in_this, ex_start, \
  39. ex_len) \
  40. { \
  41. size_t index = 0; \
  42. size_t length = 0; \
  43. EXPECT_TRUE( \
  44. StringSearch(find_this, in_this, &index, &length, false, false)); \
  45. EXPECT_EQ(ex_start, index); \
  46. EXPECT_EQ(ex_len, length); \
  47. }
  48. #define EXPECT_MATCH_SENSITIVE_BACKWARDS(find_this, in_this, ex_start, ex_len) \
  49. { \
  50. size_t index = 0; \
  51. size_t length = 0; \
  52. EXPECT_TRUE( \
  53. StringSearch(find_this, in_this, &index, &length, true, false)); \
  54. EXPECT_EQ(ex_start, index); \
  55. EXPECT_EQ(ex_len, length); \
  56. }
  57. #define EXPECT_MISS_IGNORE_CASE(find_this, in_this) \
  58. { \
  59. size_t index = 0; \
  60. size_t length = 0; \
  61. EXPECT_FALSE(StringSearchIgnoringCaseAndAccents(find_this, in_this, \
  62. &index, &length)); \
  63. index = 0; \
  64. length = 0; \
  65. EXPECT_FALSE( \
  66. StringSearch(find_this, in_this, &index, &length, false, true)); \
  67. }
  68. #define EXPECT_MISS_SENSITIVE(find_this, in_this) \
  69. { \
  70. size_t index = 0; \
  71. size_t length = 0; \
  72. EXPECT_FALSE( \
  73. StringSearch(find_this, in_this, &index, &length, true, true)); \
  74. }
  75. #define EXPECT_MISS_IGNORE_CASE_BACKWARDS(find_this, in_this) \
  76. { \
  77. size_t index = 0; \
  78. size_t length = 0; \
  79. EXPECT_FALSE( \
  80. StringSearch(find_this, in_this, &index, &length, false, false)); \
  81. }
  82. #define EXPECT_MISS_SENSITIVE_BACKWARDS(find_this, in_this) \
  83. { \
  84. size_t index = 0; \
  85. size_t length = 0; \
  86. EXPECT_FALSE( \
  87. StringSearch(find_this, in_this, &index, &length, true, false)); \
  88. }
  89. // Note on setting default locale for testing: The current default locale on
  90. // the Mac trybot is en_US_POSIX, with which primary-level collation strength
  91. // string search is case-sensitive, when normally it should be
  92. // case-insensitive. In other locales (including en_US which English speakers
  93. // in the U.S. use), this search would be case-insensitive as expected.
  94. TEST(StringSearchTest, ASCII) {
  95. std::string default_locale(uloc_getDefault());
  96. bool locale_is_posix = (default_locale == "en_US_POSIX");
  97. if (locale_is_posix)
  98. SetICUDefaultLocale("en_US");
  99. EXPECT_MATCH_IGNORE_CASE(u"hello", u"hello world", 0U, 5U);
  100. EXPECT_MISS_IGNORE_CASE(u"h e l l o", u"h e l l o");
  101. EXPECT_MATCH_IGNORE_CASE(u"aabaaa", u"aaabaabaaa", 4U, 6U);
  102. EXPECT_MISS_IGNORE_CASE(u"searching within empty string", std::u16string());
  103. EXPECT_MATCH_IGNORE_CASE(std::u16string(), u"searching for empty string", 0U,
  104. 0U);
  105. EXPECT_MATCH_IGNORE_CASE(u"case insensitivity", u"CaSe InSeNsItIvItY", 0U,
  106. 18U);
  107. EXPECT_MATCH_SENSITIVE(u"aabaaa", u"aaabaabaaa", 4U, 6U);
  108. EXPECT_MISS_SENSITIVE(u"searching within empty string", std::u16string());
  109. EXPECT_MATCH_SENSITIVE(std::u16string(), u"searching for empty string", 0U,
  110. 0U);
  111. EXPECT_MISS_SENSITIVE(u"case insensitivity", u"CaSe InSeNsItIvItY");
  112. if (locale_is_posix)
  113. SetICUDefaultLocale(default_locale.data());
  114. }
  115. TEST(StringSearchTest, UnicodeLocaleIndependent) {
  116. // Base characters
  117. const std::u16string e_base = u"e";
  118. const std::u16string E_base = u"E";
  119. const std::u16string a_base = u"a";
  120. // Composed characters
  121. const std::u16string e_with_acute_accent = u"\u00e9";
  122. const std::u16string E_with_acute_accent = u"\u00c9";
  123. const std::u16string e_with_grave_accent = u"\u00e8";
  124. const std::u16string E_with_grave_accent = u"\u00c8";
  125. const std::u16string a_with_acute_accent = u"\u00e1";
  126. // Decomposed characters
  127. const std::u16string e_with_acute_combining_mark = u"e\u0301";
  128. const std::u16string E_with_acute_combining_mark = u"E\u0301";
  129. const std::u16string e_with_grave_combining_mark = u"e\u0300";
  130. const std::u16string E_with_grave_combining_mark = u"E\u0300";
  131. const std::u16string a_with_acute_combining_mark = u"a\u0301";
  132. std::string default_locale(uloc_getDefault());
  133. bool locale_is_posix = (default_locale == "en_US_POSIX");
  134. if (locale_is_posix)
  135. SetICUDefaultLocale("en_US");
  136. EXPECT_MATCH_IGNORE_CASE(e_base, e_with_acute_accent, 0U,
  137. e_with_acute_accent.size());
  138. EXPECT_MATCH_IGNORE_CASE(e_with_acute_accent, e_base, 0U, e_base.size());
  139. EXPECT_MATCH_IGNORE_CASE(e_base, e_with_acute_combining_mark, 0U,
  140. e_with_acute_combining_mark.size());
  141. EXPECT_MATCH_IGNORE_CASE(e_with_acute_combining_mark, e_base, 0U,
  142. e_base.size());
  143. EXPECT_MATCH_IGNORE_CASE(e_with_acute_combining_mark, e_with_acute_accent, 0U,
  144. e_with_acute_accent.size());
  145. EXPECT_MATCH_IGNORE_CASE(e_with_acute_accent, e_with_acute_combining_mark, 0U,
  146. e_with_acute_combining_mark.size());
  147. EXPECT_MATCH_IGNORE_CASE(e_with_acute_combining_mark,
  148. e_with_grave_combining_mark, 0U,
  149. e_with_grave_combining_mark.size());
  150. EXPECT_MATCH_IGNORE_CASE(e_with_grave_combining_mark,
  151. e_with_acute_combining_mark, 0U,
  152. e_with_acute_combining_mark.size());
  153. EXPECT_MATCH_IGNORE_CASE(e_with_acute_combining_mark, e_with_grave_accent, 0U,
  154. e_with_grave_accent.size());
  155. EXPECT_MATCH_IGNORE_CASE(e_with_grave_accent, e_with_acute_combining_mark, 0U,
  156. e_with_acute_combining_mark.size());
  157. EXPECT_MATCH_IGNORE_CASE(E_with_acute_accent, e_with_acute_accent, 0U,
  158. e_with_acute_accent.size());
  159. EXPECT_MATCH_IGNORE_CASE(E_with_grave_accent, e_with_acute_accent, 0U,
  160. e_with_acute_accent.size());
  161. EXPECT_MATCH_IGNORE_CASE(E_with_acute_combining_mark, e_with_grave_accent, 0U,
  162. e_with_grave_accent.size());
  163. EXPECT_MATCH_IGNORE_CASE(E_with_grave_combining_mark, e_with_acute_accent, 0U,
  164. e_with_acute_accent.size());
  165. EXPECT_MATCH_IGNORE_CASE(E_base, e_with_grave_accent, 0U,
  166. e_with_grave_accent.size());
  167. EXPECT_MISS_IGNORE_CASE(a_with_acute_accent, e_with_acute_accent);
  168. EXPECT_MISS_IGNORE_CASE(a_with_acute_combining_mark,
  169. e_with_acute_combining_mark);
  170. EXPECT_MISS_SENSITIVE(e_base, e_with_acute_accent);
  171. EXPECT_MISS_SENSITIVE(e_with_acute_accent, e_base);
  172. EXPECT_MISS_SENSITIVE(e_base, e_with_acute_combining_mark);
  173. EXPECT_MISS_SENSITIVE(e_with_acute_combining_mark, e_base);
  174. EXPECT_MATCH_SENSITIVE(e_with_acute_combining_mark, e_with_acute_accent, 0U,
  175. 1U);
  176. EXPECT_MATCH_SENSITIVE(e_with_acute_accent, e_with_acute_combining_mark, 0U,
  177. 2U);
  178. EXPECT_MISS_SENSITIVE(e_with_acute_combining_mark,
  179. e_with_grave_combining_mark);
  180. EXPECT_MISS_SENSITIVE(e_with_grave_combining_mark,
  181. e_with_acute_combining_mark);
  182. EXPECT_MISS_SENSITIVE(e_with_acute_combining_mark, e_with_grave_accent);
  183. EXPECT_MISS_SENSITIVE(e_with_grave_accent, e_with_acute_combining_mark);
  184. EXPECT_MISS_SENSITIVE(E_with_acute_accent, e_with_acute_accent);
  185. EXPECT_MISS_SENSITIVE(E_with_grave_accent, e_with_acute_accent);
  186. EXPECT_MISS_SENSITIVE(E_with_acute_combining_mark, e_with_grave_accent);
  187. EXPECT_MISS_SENSITIVE(E_with_grave_combining_mark, e_with_acute_accent);
  188. EXPECT_MISS_SENSITIVE(E_base, e_with_grave_accent);
  189. EXPECT_MISS_SENSITIVE(a_with_acute_accent, e_with_acute_accent);
  190. EXPECT_MISS_SENSITIVE(a_with_acute_combining_mark,
  191. e_with_acute_combining_mark);
  192. EXPECT_MATCH_SENSITIVE(a_with_acute_combining_mark,
  193. a_with_acute_combining_mark, 0U, 2U);
  194. if (locale_is_posix)
  195. SetICUDefaultLocale(default_locale.data());
  196. }
  197. TEST(StringSearchTest, UnicodeLocaleDependent) {
  198. // Base characters
  199. const std::u16string a_base = u"a";
  200. // Composed characters
  201. const std::u16string a_with_ring = u"\u00e5";
  202. EXPECT_TRUE(StringSearchIgnoringCaseAndAccents(a_base, a_with_ring, nullptr,
  203. nullptr));
  204. EXPECT_TRUE(StringSearch(a_base, a_with_ring, nullptr, nullptr, false, true));
  205. const char* default_locale = uloc_getDefault();
  206. SetICUDefaultLocale("da");
  207. EXPECT_FALSE(StringSearchIgnoringCaseAndAccents(a_base, a_with_ring, nullptr,
  208. nullptr));
  209. EXPECT_FALSE(
  210. StringSearch(a_base, a_with_ring, nullptr, nullptr, false, true));
  211. SetICUDefaultLocale(default_locale);
  212. }
  213. TEST(StringSearchTest, SearchBackwards) {
  214. std::string default_locale(uloc_getDefault());
  215. bool locale_is_posix = (default_locale == "en_US_POSIX");
  216. if (locale_is_posix)
  217. SetICUDefaultLocale("en_US");
  218. EXPECT_MATCH_IGNORE_CASE_BACKWARDS(u"ab", u"ABAB", 2U, 2U);
  219. EXPECT_MATCH_SENSITIVE_BACKWARDS(u"ab", u"abab", 2U, 2U);
  220. EXPECT_MISS_SENSITIVE_BACKWARDS(u"ab", u"ABAB");
  221. if (locale_is_posix)
  222. SetICUDefaultLocale(default_locale.data());
  223. }
  224. TEST(StringSearchTest, FixedPatternMultipleSearch) {
  225. std::string default_locale(uloc_getDefault());
  226. bool locale_is_posix = (default_locale == "en_US_POSIX");
  227. if (locale_is_posix)
  228. SetICUDefaultLocale("en_US");
  229. size_t index = 0;
  230. size_t length = 0;
  231. // Search "foo" over multiple texts.
  232. FixedPatternStringSearch query1(u"foo", true);
  233. EXPECT_TRUE(query1.Search(u"12foo34", &index, &length, true));
  234. EXPECT_EQ(2U, index);
  235. EXPECT_EQ(3U, length);
  236. EXPECT_FALSE(query1.Search(u"bye", &index, &length, true));
  237. EXPECT_FALSE(query1.Search(u"FOO", &index, &length, true));
  238. EXPECT_TRUE(query1.Search(u"foobarfoo", &index, &length, true));
  239. EXPECT_EQ(0U, index);
  240. EXPECT_EQ(3U, length);
  241. EXPECT_TRUE(query1.Search(u"foobarfoo", &index, &length, false));
  242. EXPECT_EQ(6U, index);
  243. EXPECT_EQ(3U, length);
  244. // Search "hello" over multiple texts.
  245. FixedPatternStringSearchIgnoringCaseAndAccents query2(u"hello");
  246. EXPECT_TRUE(query2.Search(u"12hello34", &index, &length));
  247. EXPECT_EQ(2U, index);
  248. EXPECT_EQ(5U, length);
  249. EXPECT_FALSE(query2.Search(u"bye", &index, &length));
  250. EXPECT_TRUE(query2.Search(u"hELLo", &index, &length));
  251. EXPECT_EQ(0U, index);
  252. EXPECT_EQ(5U, length);
  253. if (locale_is_posix)
  254. SetICUDefaultLocale(default_locale.data());
  255. }
  256. TEST(StringSearchTest, RepeatingStringSearch) {
  257. struct MatchResult {
  258. int match_index;
  259. int match_length;
  260. };
  261. std::string default_locale(uloc_getDefault());
  262. bool locale_is_posix = (default_locale == "en_US_POSIX");
  263. if (locale_is_posix)
  264. SetICUDefaultLocale("en_US");
  265. const char16_t kPattern[] = u"fox";
  266. const char16_t kTarget[] = u"The quick brown fox jumped over the lazy Fox";
  267. // Case sensitive.
  268. {
  269. const MatchResult kExpectation[] = {{16, 3}};
  270. RepeatingStringSearch searcher(kPattern, kTarget, /*case_sensitive=*/true);
  271. std::vector<MatchResult> results;
  272. int match_index;
  273. int match_length;
  274. while (searcher.NextMatchResult(match_index, match_length)) {
  275. results.push_back(
  276. {.match_index = match_index, .match_length = match_length});
  277. }
  278. ASSERT_EQ(std::size(kExpectation), results.size());
  279. for (size_t i = 0; i < results.size(); ++i) {
  280. EXPECT_EQ(results[i].match_index, kExpectation[i].match_index);
  281. EXPECT_EQ(results[i].match_length, kExpectation[i].match_length);
  282. }
  283. }
  284. // Case insensitive.
  285. {
  286. const MatchResult kExpectation[] = {{16, 3}, {41, 3}};
  287. RepeatingStringSearch searcher(kPattern, kTarget, /*case_sensitive=*/false);
  288. std::vector<MatchResult> results;
  289. int match_index;
  290. int match_length;
  291. while (searcher.NextMatchResult(match_index, match_length)) {
  292. results.push_back(
  293. {.match_index = match_index, .match_length = match_length});
  294. }
  295. ASSERT_EQ(std::size(kExpectation), results.size());
  296. for (size_t i = 0; i < results.size(); ++i) {
  297. EXPECT_EQ(results[i].match_index, kExpectation[i].match_index);
  298. EXPECT_EQ(results[i].match_length, kExpectation[i].match_length);
  299. }
  300. }
  301. if (locale_is_posix)
  302. SetICUDefaultLocale(default_locale.data());
  303. }
  304. } // namespace i18n
  305. } // namespace base