snippet.cc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309
  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 <stdint.h>
  6. #include <algorithm>
  7. #include <memory>
  8. #include "base/check.h"
  9. #include "base/strings/string_split.h"
  10. #include "base/strings/string_util.h"
  11. #include "base/strings/utf_string_conversions.h"
  12. #include "third_party/icu/source/common/unicode/brkiter.h"
  13. #include "third_party/icu/source/common/unicode/utext.h"
  14. #include "third_party/icu/source/common/unicode/utf8.h"
  15. namespace query_parser {
  16. namespace {
  17. bool PairFirstLessThan(const Snippet::MatchPosition& a,
  18. const Snippet::MatchPosition& b) {
  19. return a.first < b.first;
  20. }
  21. // Combines all pairs after offset in match_positions that are contained
  22. // or touch the pair at offset.
  23. void CoalescePositionsFrom(size_t offset,
  24. Snippet::MatchPositions* match_positions) {
  25. DCHECK(offset < match_positions->size());
  26. Snippet::MatchPosition& pair((*match_positions)[offset]);
  27. ++offset;
  28. while (offset < match_positions->size() &&
  29. pair.second >= (*match_positions)[offset].first) {
  30. pair.second = std::max(pair.second, (*match_positions)[offset].second);
  31. match_positions->erase(match_positions->begin() + offset);
  32. }
  33. }
  34. // Makes sure there is a pair in match_positions that contains the specified
  35. // range. This keeps the pairs ordered in match_positions by first, and makes
  36. // sure none of the pairs in match_positions touch each other.
  37. void AddMatch(size_t start,
  38. size_t end,
  39. Snippet::MatchPositions* match_positions) {
  40. DCHECK(start < end);
  41. DCHECK(match_positions);
  42. Snippet::MatchPosition pair(start, end);
  43. if (match_positions->empty()) {
  44. match_positions->push_back(pair);
  45. return;
  46. }
  47. // There's at least one match. Find the position of the new match,
  48. // potentially extending pairs around it.
  49. auto i = std::lower_bound(match_positions->begin(), match_positions->end(),
  50. pair, &PairFirstLessThan);
  51. if (i != match_positions->end() && i->first == start) {
  52. // Match not at the end and there is already a pair with the same
  53. // start.
  54. if (end > i->second) {
  55. // New pair extends beyond existing pair. Extend existing pair and
  56. // coalesce matches after it.
  57. i->second = end;
  58. CoalescePositionsFrom(i - match_positions->begin(), match_positions);
  59. } // else case, new pair completely contained in existing pair, nothing
  60. // to do.
  61. } else if (i == match_positions->begin()) {
  62. // Match at the beginning and the first pair doesn't have the same
  63. // start. Insert new pair and coalesce matches after it.
  64. match_positions->insert(i, pair);
  65. CoalescePositionsFrom(0, match_positions);
  66. } else {
  67. // Not at the beginning (but may be at the end).
  68. --i;
  69. if (start <= i->second && end > i->second) {
  70. // Previous element contains match. Extend it and coalesce.
  71. i->second = end;
  72. CoalescePositionsFrom(i - match_positions->begin(), match_positions);
  73. } else if (end > i->second) {
  74. // Region doesn't touch previous element. See if region touches current
  75. // element.
  76. ++i;
  77. if (i == match_positions->end() || end < i->first) {
  78. match_positions->insert(i, pair);
  79. } else {
  80. i->first = start;
  81. i->second = end;
  82. CoalescePositionsFrom(i - match_positions->begin(), match_positions);
  83. }
  84. }
  85. }
  86. }
  87. // Converts an index in a utf8 string into the index in the corresponding utf16
  88. // string and returns the utf16 index. This is intended to be called in a loop
  89. // iterating through a utf8 string.
  90. //
  91. // utf8_string: the utf8 string.
  92. // utf8_length: length of the utf8 string.
  93. // offset: the utf8 offset to convert.
  94. // utf8_pos: current offset in the utf8 string. This is modified and on return
  95. // matches offset.
  96. // wide_pos: current index in the wide string. This is the same as the return
  97. // value.
  98. size_t AdvanceAndReturnUTF16Pos(const char* utf8_string,
  99. int32_t utf8_length,
  100. int32_t offset,
  101. int32_t* utf8_pos,
  102. size_t* utf16_pos) {
  103. DCHECK(offset >= *utf8_pos && offset <= utf8_length);
  104. UChar32 wide_char;
  105. while (*utf8_pos < offset) {
  106. U8_NEXT(utf8_string, *utf8_pos, utf8_length, wide_char);
  107. *utf16_pos += (wide_char <= 0xFFFF) ? 1 : 2;
  108. }
  109. return *utf16_pos;
  110. }
  111. // Given a character break iterator over a UTF-8 string, set the iterator
  112. // position to |*utf8_pos| and move by |count| characters. |count| can
  113. // be either positive or negative.
  114. void MoveByNGraphemes(icu::BreakIterator* bi, int count, size_t* utf8_pos) {
  115. // Ignore the return value. A side effect of the current position
  116. // being set at or following |*utf8_pos| is exploited here.
  117. // It's simpler than calling following(n) and then previous().
  118. // isBoundary() is not very fast, but should be good enough for the
  119. // snippet generation. If not, revisit the way we scan in ComputeSnippet.
  120. bi->isBoundary(static_cast<int32_t>(*utf8_pos));
  121. bi->next(count);
  122. *utf8_pos = static_cast<size_t>(bi->current());
  123. }
  124. // The amount of context to include for a given hit. Note that it's counted
  125. // in terms of graphemes rather than bytes.
  126. const int kSnippetContext = 50;
  127. // Returns true if next match falls within a snippet window
  128. // from the previous match. The window size is counted in terms
  129. // of graphemes rather than bytes in UTF-8.
  130. bool IsNextMatchWithinSnippetWindow(icu::BreakIterator* bi,
  131. size_t previous_match_end,
  132. size_t next_match_start) {
  133. // If it's within a window in terms of bytes, it's certain
  134. // that it's within a window in terms of graphemes as well.
  135. if (next_match_start < previous_match_end + kSnippetContext)
  136. return true;
  137. bi->isBoundary(static_cast<int32_t>(previous_match_end));
  138. // An alternative to this is to call |bi->next()| at most
  139. // kSnippetContext times, compare |bi->current()| with |next_match_start|
  140. // after each call and return early if possible. There are other
  141. // heuristics to speed things up if necessary, but it's not likely that
  142. // we need to bother.
  143. bi->next(kSnippetContext);
  144. int64_t current = bi->current();
  145. return (next_match_start < static_cast<uint64_t>(current) ||
  146. current == icu::BreakIterator::DONE);
  147. }
  148. } // namespace
  149. // static
  150. void Snippet::ExtractMatchPositions(const std::string& offsets_str,
  151. const std::string& column_num,
  152. MatchPositions* match_positions) {
  153. DCHECK(match_positions);
  154. if (offsets_str.empty())
  155. return;
  156. std::vector<std::string> offsets = base::SplitString(
  157. offsets_str, " ", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
  158. // SQLite offsets are sets of four integers:
  159. // column, query term, match offset, match length
  160. // Matches within a string are marked by (start, end) pairs.
  161. for (size_t i = 0; i < offsets.size() - 3; i += 4) {
  162. if (offsets[i] != column_num)
  163. continue;
  164. const size_t start = atoi(offsets[i + 2].c_str());
  165. const size_t end = start + atoi(offsets[i + 3].c_str());
  166. // Switch to DCHECK after debugging http://crbug.com/15261.
  167. CHECK(end >= start);
  168. AddMatch(start, end, match_positions);
  169. }
  170. }
  171. // static
  172. void Snippet::ConvertMatchPositionsToWide(
  173. const std::string& utf8_string,
  174. Snippet::MatchPositions* match_positions) {
  175. DCHECK(match_positions);
  176. int32_t utf8_pos = 0;
  177. size_t utf16_pos = 0;
  178. const char* utf8_cstring = utf8_string.c_str();
  179. const int32_t utf8_length = static_cast<int32_t>(utf8_string.size());
  180. for (auto i = match_positions->begin(); i != match_positions->end(); ++i) {
  181. i->first = AdvanceAndReturnUTF16Pos(utf8_cstring, utf8_length,
  182. static_cast<int32_t>(i->first),
  183. &utf8_pos, &utf16_pos);
  184. i->second = AdvanceAndReturnUTF16Pos(utf8_cstring, utf8_length,
  185. static_cast<int32_t>(i->second),
  186. &utf8_pos, &utf16_pos);
  187. }
  188. }
  189. Snippet::Snippet() {
  190. }
  191. Snippet::Snippet(const Snippet& other) = default;
  192. Snippet::Snippet(Snippet&& other) noexcept = default;
  193. Snippet::~Snippet() {
  194. }
  195. Snippet& Snippet::operator=(const Snippet&) = default;
  196. void Snippet::ComputeSnippet(const MatchPositions& match_positions,
  197. const std::string& document) {
  198. // The length of snippets we try to produce.
  199. // We can generate longer snippets but stop once we cross kSnippetMaxLength.
  200. const size_t kSnippetMaxLength = 200;
  201. const std::u16string kEllipsis = u" ... ";
  202. UText* document_utext = nullptr;
  203. UErrorCode status = U_ZERO_ERROR;
  204. document_utext = utext_openUTF8(document_utext, document.data(),
  205. document.size(), &status);
  206. // Locale does not matter because there's no per-locale customization
  207. // for character iterator.
  208. std::unique_ptr<icu::BreakIterator> bi(
  209. icu::BreakIterator::createCharacterInstance(icu::Locale::getDefault(),
  210. status));
  211. bi->setText(document_utext, status);
  212. DCHECK(U_SUCCESS(status));
  213. // We build the snippet by iterating through the matches and then grabbing
  214. // context around each match. If matches are near enough each other (within
  215. // kSnippetContext), we skip the "..." between them.
  216. std::u16string snippet;
  217. size_t start = 0;
  218. for (size_t i = 0; i < match_positions.size(); ++i) {
  219. // Some shorter names for the current match.
  220. const size_t match_start = match_positions[i].first;
  221. const size_t match_end = match_positions[i].second;
  222. // Switch to DCHECK after debugging http://crbug.com/15261.
  223. CHECK(match_end > match_start);
  224. CHECK(match_end <= document.size());
  225. // Add the context, if any, to show before the match.
  226. size_t context_start = match_start;
  227. MoveByNGraphemes(bi.get(), -kSnippetContext, &context_start);
  228. start = std::max(start, context_start);
  229. if (start < match_start) {
  230. if (start > 0)
  231. snippet += kEllipsis;
  232. // Switch to DCHECK after debugging http://crbug.com/15261.
  233. CHECK(start < document.size());
  234. snippet += base::UTF8ToUTF16(document.substr(start, match_start - start));
  235. }
  236. // Add the match.
  237. const size_t first = snippet.size();
  238. snippet += base::UTF8ToUTF16(document.substr(match_start,
  239. match_end - match_start));
  240. matches_.push_back(std::make_pair(first, snippet.size()));
  241. // Compute the context, if any, to show after the match.
  242. size_t end;
  243. // Check if the next match falls within our snippet window.
  244. if (i + 1 < match_positions.size() &&
  245. IsNextMatchWithinSnippetWindow(bi.get(), match_end,
  246. match_positions[i + 1].first)) {
  247. // Yes, it's within the window. Make the end context extend just up
  248. // to the next match.
  249. end = match_positions[i + 1].first;
  250. // Switch to DCHECK after debugging http://crbug.com/15261.
  251. CHECK(end >= match_end);
  252. CHECK(end <= document.size());
  253. snippet += base::UTF8ToUTF16(document.substr(match_end, end - match_end));
  254. } else {
  255. // No, there's either no next match or the next match is too far away.
  256. end = match_end;
  257. MoveByNGraphemes(bi.get(), kSnippetContext, &end);
  258. // Switch to DCHECK after debugging http://crbug.com/15261.
  259. CHECK(end >= match_end);
  260. CHECK(end <= document.size());
  261. snippet += base::UTF8ToUTF16(document.substr(match_end, end - match_end));
  262. if (end < document.size())
  263. snippet += kEllipsis;
  264. }
  265. start = end;
  266. // Stop here if we have enough snippet computed.
  267. if (snippet.size() >= kSnippetMaxLength)
  268. break;
  269. }
  270. utext_close(document_utext);
  271. swap(text_, snippet);
  272. }
  273. void Snippet::Swap(Snippet* other) {
  274. text_.swap(other->text_);
  275. matches_.swap(other->matches_);
  276. }
  277. } // namespace query_parser