snippet_unittest.cc 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255
  1. // Copyright 2014 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 "components/query_parser/snippet.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include "base/strings/string_split.h"
  8. #include "base/strings/string_util.h"
  9. #include "base/strings/utf_string_conversions.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. namespace query_parser {
  12. namespace {
  13. // A sample document to compute snippets of.
  14. // The \x bits after the first "Google" are UTF-8 of U+2122 TRADE MARK SIGN,
  15. // and are useful for verifying we don't screw up in UTF-8/UTF-16 conversion.
  16. const char kSampleDocument[] =
  17. "Google\xe2\x84\xa2 Terms of Service "
  18. "Welcome to Google! "
  19. "1. Your relationship with Google "
  20. "1.1 Your use of Google's products, software, services and web sites "
  21. "(referred to collectively as the \"Services\" in this document and "
  22. "excluding any services provided to you by Google under a separate "
  23. " written agreement) is subject to the terms of a legal agreement "
  24. "between you and Google. \"Google\" means Google Inc., whose principal "
  25. "place of business is at 1600 Amphitheatre Parkway, Mountain View, "
  26. "CA 94043, United States. This document explains how the agreement is "
  27. "made up, and sets out some of the terms of that agreement.";
  28. } // namespace
  29. // Thai sample taken from http://www.google.co.th/intl/th/privacy.html
  30. // TODO(jungshik) : Add more samples (e.g. Hindi) after porting
  31. // ICU 4.0's character iterator changes to our copy of ICU 3.8 to get
  32. // grapheme clusters in Indic scripts handled more reasonably.
  33. const char* kThaiSample = "Google \xE0\xB9\x80\xE0\xB8\x81\xE0\xB9\x87"
  34. "\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7"
  35. "\xE0\xB8\xA1 \xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  36. "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99\xE0\xB8\x9A"
  37. "\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5 \xE0\xB9\x80\xE0\xB8\xA1"
  38. "\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93"
  39. "\xE0\xB8\xA5\xE0\xB8\x87\xE0\xB8\x97\xE0\xB8\xB0\xE0\xB9\x80\xE0\xB8\x9A"
  40. "\xE0\xB8\xB5\xE0\xB8\xA2\xE0\xB8\x99\xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7"
  41. "\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89\xE0\xB8\x9A"
  42. "\xE0\xB8\xA3\xE0\xB8\xB4\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\x82"
  43. "\xE0\xB8\xAD\xE0\xB8\x87 Google \xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7"
  44. "\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89\xE0\xB8\x82\xE0\xB9\x89"
  45. "\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\x94\xE0\xB8\xB1"
  46. "\xE0\xB8\x87\xE0\xB8\x81\xE0\xB8\xA5\xE0\xB9\x88\xE0\xB8\xB2\xE0\xB8\xA7"
  47. "\xE0\xB9\x82\xE0\xB8\x94\xE0\xB8\xA2\xE0\xB8\xAA\xE0\xB8\xA1\xE0\xB8\xB1"
  48. "\xE0\xB8\x84\xE0\xB8\xA3\xE0\xB9\x83\xE0\xB8\x88 \xE0\xB9\x80\xE0\xB8\xA3"
  49. "\xE0\xB8\xB2\xE0\xB8\xAD\xE0\xB8\xB2\xE0\xB8\x88\xE0\xB8\xA3\xE0\xB8\xA7"
  50. "\xE0\xB8\xA1\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  51. "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99\xE0\xB8\x9A"
  52. "\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5"
  53. "\xE0\xB9\x88\xE0\xB9\x80\xE0\xB8\x81\xE0\xB9\x87\xE0\xB8\x9A\xE0\xB8\xA3"
  54. "\xE0\xB8\xA7\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x88"
  55. "\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93\xE0\xB9\x80"
  56. "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\xB1\xE0\xB8\x9A"
  57. "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5"
  58. "\xE0\xB8\x88\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xB4"
  59. "\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\xAD\xE0\xB8\xB7\xE0\xB9\x88"
  60. "\xE0\xB8\x99\xE0\xB8\x82\xE0\xB8\xAD\xE0\xB8\x87 Google \xE0\xB8\xAB"
  61. "\xE0\xB8\xA3\xE0\xB8\xB7\xE0\xB8\xAD\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84"
  62. "\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\xAA"
  63. "\xE0\xB8\xB2\xE0\xB8\xA1 \xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7\xE0\xB9\x88"
  64. "\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89\xE0\xB8\x9C\xE0\xB8\xB9"
  65. "\xE0\xB9\x89\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89\xE0\xB9\x84\xE0\xB8\x94"
  66. "\xE0\xB9\x89\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x9B\xE0\xB8\xA3"
  67. "\xE0\xB8\xB0\xE0\xB8\xAA\xE0\xB8\x9A\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3"
  68. "\xE0\xB8\x93\xE0\xB9\x8C\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\x94"
  69. "\xE0\xB8\xB5\xE0\xB8\x82\xE0\xB8\xB6\xE0\xB9\x89\xE0\xB8\x99 \xE0\xB8\xA3"
  70. "\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x97\xE0\xB8\xB1\xE0\xB9\x89\xE0\xB8\x87"
  71. "\xE0\xB8\x9B\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB9\x81\xE0\xB8\x95"
  72. "\xE0\xB9\x88\xE0\xB8\x87\xE0\xB9\x80\xE0\xB8\x99\xE0\xB8\xB7\xE0\xB9\x89"
  73. "\xE0\xB8\xAD\xE0\xB8\xAB\xE0\xB8\xB2\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89"
  74. "\xE0\xB9\x80\xE0\xB8\xAB\xE0\xB8\xA1\xE0\xB8\xB2\xE0\xB8\xB0\xE0\xB8\xAA"
  75. "\xE0\xB8\xB3\xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x84"
  76. "\xE0\xB8\xB8\xE0\xB8\x93";
  77. // Comparator for sorting by the first element in a pair.
  78. bool ComparePair1st(const Snippet::MatchPosition& a,
  79. const Snippet::MatchPosition& b) {
  80. return a.first < b.first;
  81. }
  82. // For testing, we'll compute the match positions manually instead of using
  83. // sqlite's FTS matching. BuildSnippet returns the snippet for matching
  84. // |query| against |document|. Matches are surrounded by "**".
  85. std::u16string BuildSnippet(const std::string& document,
  86. const std::string& query) {
  87. // This function assumes that |document| does not contain
  88. // any character for which lowercasing changes its length. Further,
  89. // it's assumed that lowercasing only the ASCII-portion works for
  90. // |document|. We need to add more test cases and change this function
  91. // to be more generic depending on how we deal with 'folding for match'
  92. // in history.
  93. const std::string document_folded = base::ToLowerASCII(document);
  94. // Manually construct match_positions of the document.
  95. Snippet::MatchPositions match_positions;
  96. match_positions.clear();
  97. for (const std::string& word : base::SplitString(
  98. query, " ", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL)) {
  99. // Insert all instances of this word into match_pairs.
  100. size_t ofs = 0;
  101. while ((ofs = document_folded.find(word, ofs)) != std::string::npos) {
  102. match_positions.push_back(std::make_pair(ofs, ofs + word.size()));
  103. ofs += word.size();
  104. }
  105. }
  106. // Sort match_positions in order of increasing offset.
  107. std::sort(match_positions.begin(), match_positions.end(), ComparePair1st);
  108. // Compute the snippet.
  109. Snippet snippet;
  110. snippet.ComputeSnippet(match_positions, document);
  111. // Now "highlight" all matches in the snippet with **.
  112. std::u16string star_snippet;
  113. Snippet::MatchPositions::const_iterator match;
  114. size_t pos = 0;
  115. for (match = snippet.matches().begin();
  116. match != snippet.matches().end(); ++match) {
  117. star_snippet += snippet.text().substr(pos, match->first - pos);
  118. star_snippet += u"**";
  119. star_snippet += snippet.text().substr(match->first,
  120. match->second - match->first);
  121. star_snippet += u"**";
  122. pos = match->second;
  123. }
  124. star_snippet += snippet.text().substr(pos);
  125. return star_snippet;
  126. }
  127. TEST(Snippets, SimpleQuery) {
  128. ASSERT_EQ(" ... eferred to collectively as the \"Services\" in this "
  129. "**document** and excluding any services provided to you by "
  130. "Goo ... ... way, Mountain View, CA 94043, United States. This "
  131. "**document** explains how the agreement is made up, and sets "
  132. "o ... ",
  133. base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "document")));
  134. }
  135. // Test that two words that are near each other don't produce two elided bits.
  136. TEST(Snippets, NearbyWords) {
  137. ASSERT_EQ(" ... lace of business is at 1600 Amphitheatre Parkway, "
  138. "**Mountain** **View**, CA 94043, United States. This "
  139. "document explains ... ",
  140. base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "mountain view")));
  141. }
  142. // The above tests already test that we get byte offsets correct, but here's
  143. // one that gets the "TM" in its snippet.
  144. TEST(Snippets, UTF8) {
  145. ASSERT_EQ(" ... ogle\xe2\x84\xa2 Terms of Service Welcome to Google! "
  146. "1. Your **relationship** with Google 1.1 Your use of Google's "
  147. "products, so ... ",
  148. base::UTF16ToUTF8(BuildSnippet(kSampleDocument, "relationship")));
  149. }
  150. TEST(Snippets, ThaiUTF8) {
  151. // There are 3 instances of '\u0E43\u0E2B\u0E49'
  152. // (\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89) in kThaiSample.
  153. // The 1st is more than |kSniipetContext| graphemes away from the
  154. // 2nd while the 2nd and 3rd are within that window. However, with
  155. // the 2nd match added, the snippet goes over the size limit so that
  156. // the snippet ends right before the 3rd match.
  157. ASSERT_EQ(" ... "
  158. "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  159. "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99"
  160. "\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5 "
  161. "\xE0\xB9\x80\xE0\xB8\xA1\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\xAD"
  162. "\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93\xE0\xB8\xA5\xE0\xB8\x87"
  163. "\xE0\xB8\x97\xE0\xB8\xB0\xE0\xB9\x80\xE0\xB8\x9A\xE0\xB8\xB5"
  164. "\xE0\xB8\xA2\xE0\xB8\x99\xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7"
  165. "\xE0\xB9\x88\xE0\xB8\xAD\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89"
  166. "\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xB4\xE0\xB8\x81\xE0\xB8\xB2"
  167. "\xE0\xB8\xA3\xE0\xB8\x82\xE0\xB8\xAD\xE0\xB8\x87 Google "
  168. "\xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7\xE0\xB8\xAD**\xE0\xB9\x83"
  169. "\xE0\xB8\xAB\xE0\xB9\x89**\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD"
  170. "\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\x94\xE0\xB8\xB1"
  171. "\xE0\xB8\x87\xE0\xB8\x81\xE0\xB8\xA5\xE0\xB9\x88\xE0\xB8\xB2"
  172. "\xE0\xB8\xA7\xE0\xB9\x82\xE0\xB8\x94\xE0\xB8\xA2\xE0\xB8\xAA"
  173. "\xE0\xB8\xA1\xE0\xB8\xB1\xE0\xB8\x84\xE0\xB8\xA3\xE0\xB9\x83"
  174. "\xE0\xB8\x88 \xE0\xB9\x80\xE0\xB8\xA3\xE0\xB8\xB2\xE0\xB8\xAD"
  175. "\xE0\xB8\xB2\xE0\xB8\x88\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1"
  176. "\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xA1\xE0\xB8\xB9"
  177. "\xE0\xB8\xA5\xE0\xB8\xAA\xE0\xB9\x88\xE0\xB8\xA7\xE0\xB8\x99"
  178. "\xE0\xB8\x9A\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5"
  179. "\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB9\x80\xE0\xB8\x81"
  180. "\xE0\xB9\x87\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\x9A"
  181. "\xE0\xB8\xA3\xE0\xB8\xA7\xE0\xB8\xA1 ... ... \xE0\xB8\x88"
  182. "\xE0\xB8\xB2\xE0\xB8\x81\xE0\xB8\x84\xE0\xB8\xB8\xE0\xB8\x93"
  183. "\xE0\xB9\x80\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xB2\xE0\xB8\x81"
  184. "\xE0\xB8\xB1\xE0\xB8\x9A\xE0\xB8\x82\xE0\xB9\x89\xE0\xB8\xAD"
  185. "\xE0\xB8\xA1\xE0\xB8\xB9\xE0\xB8\xA5\xE0\xB8\x88\xE0\xB8\xB2"
  186. "\xE0\xB8\x81\xE0\xB8\x9A\xE0\xB8\xA3\xE0\xB8\xB4\xE0\xB8\x81"
  187. "\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\xAD\xE0\xB8\xB7\xE0\xB9\x88"
  188. "\xE0\xB8\x99\xE0\xB8\x82\xE0\xB8\xAD\xE0\xB8\x87 Google "
  189. "\xE0\xB8\xAB\xE0\xB8\xA3\xE0\xB8\xB7\xE0\xB8\xAD\xE0\xB8\x9A"
  190. "\xE0\xB8\xB8\xE0\xB8\x84\xE0\xB8\x84\xE0\xB8\xA5\xE0\xB8\x97"
  191. "\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\xAA\xE0\xB8\xB2\xE0\xB8\xA1 "
  192. "\xE0\xB9\x80\xE0\xB8\x9E\xE0\xB8\xB7\xE0\xB9\x88\xE0\xB8\xAD**"
  193. "\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89**\xE0\xB8\x9C\xE0\xB8\xB9"
  194. "\xE0\xB9\x89\xE0\xB9\x83\xE0\xB8\x8A\xE0\xB9\x89\xE0\xB9\x84"
  195. "\xE0\xB8\x94\xE0\xB9\x89\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A"
  196. "\xE0\xB8\x9B\xE0\xB8\xA3\xE0\xB8\xB0\xE0\xB8\xAA\xE0\xB8\x9A"
  197. "\xE0\xB8\x81\xE0\xB8\xB2\xE0\xB8\xA3\xE0\xB8\x93\xE0\xB9\x8C"
  198. "\xE0\xB8\x97\xE0\xB8\xB5\xE0\xB9\x88\xE0\xB8\x94\xE0\xB8\xB5"
  199. "\xE0\xB8\x82\xE0\xB8\xB6\xE0\xB9\x89\xE0\xB8\x99 \xE0\xB8\xA3"
  200. "\xE0\xB8\xA7\xE0\xB8\xA1\xE0\xB8\x97\xE0\xB8\xB1\xE0\xB9\x89"
  201. "\xE0\xB8\x87\xE0\xB8\x9B\xE0\xB8\xA3\xE0\xB8\xB1\xE0\xB8\x9A"
  202. "\xE0\xB9\x81\xE0\xB8\x95\xE0\xB9\x88\xE0\xB8\x87\xE0\xB9\x80"
  203. "\xE0\xB8\x99\xE0\xB8\xB7\xE0\xB9\x89\xE0\xB8\xAD\xE0\xB8\xAB"
  204. "\xE0\xB8\xB2",
  205. base::UTF16ToUTF8(BuildSnippet(kThaiSample,
  206. "\xE0\xB9\x83\xE0\xB8\xAB\xE0\xB9\x89")));
  207. }
  208. TEST(Snippets, ExtractMatchPositions) {
  209. struct TestData {
  210. const std::string offsets_string;
  211. const size_t expected_match_count;
  212. const size_t expected_matches[10];
  213. } data[] = {
  214. { "0 0 1 2 0 0 4 1 0 0 1 5", 1, { 1, 6 } },
  215. { "0 0 1 4 0 0 2 1", 1, { 1, 5 } },
  216. { "0 0 4 1 0 0 2 1", 2, { 2, 3, 4, 5 } },
  217. { "0 0 0 1", 1, { 0, 1 } },
  218. { "0 0 0 1 0 0 0 2", 1, { 0, 2 } },
  219. { "0 0 1 1 0 0 1 2", 1, { 1, 3 } },
  220. { "0 0 1 2 0 0 4 3 0 0 3 1", 1, { 1, 7 } },
  221. { "0 0 1 4 0 0 2 5", 1, { 1, 7 } },
  222. { "0 0 1 2 0 0 1 1", 1, { 1, 3 } },
  223. { "0 0 1 1 0 0 5 2 0 0 10 1 0 0 3 10", 2, { 1, 2, 3, 13 } },
  224. };
  225. for (size_t i = 0; i < std::size(data); ++i) {
  226. Snippet::MatchPositions matches;
  227. Snippet::ExtractMatchPositions(data[i].offsets_string, "0", &matches);
  228. EXPECT_EQ(data[i].expected_match_count, matches.size());
  229. for (size_t j = 0; j < data[i].expected_match_count; ++j) {
  230. EXPECT_EQ(data[i].expected_matches[2 * j], matches[j].first);
  231. EXPECT_EQ(data[i].expected_matches[2 * j + 1], matches[j].second);
  232. }
  233. }
  234. }
  235. } // namespace query_parser