query_parser.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496
  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/query_parser.h"
  5. #include <algorithm>
  6. #include <memory>
  7. #include <ostream>
  8. #include "base/check.h"
  9. #include "base/compiler_specific.h"
  10. #include "base/i18n/break_iterator.h"
  11. #include "base/i18n/case_conversion.h"
  12. #include "base/notreached.h"
  13. #include "base/ranges/algorithm.h"
  14. #include "base/strings/utf_string_conversions.h"
  15. namespace query_parser {
  16. namespace {
  17. // Returns true if |mp1.first| is less than |mp2.first|. This is used to
  18. // sort match positions.
  19. int CompareMatchPosition(const Snippet::MatchPosition& mp1,
  20. const Snippet::MatchPosition& mp2) {
  21. return mp1.first < mp2.first;
  22. }
  23. // Returns true if |mp2| intersects |mp1|. This is intended for use by
  24. // CoalesceMatchesFrom and isn't meant as a general intersection comparison
  25. // function.
  26. bool SnippetIntersects(const Snippet::MatchPosition& mp1,
  27. const Snippet::MatchPosition& mp2) {
  28. return mp2.first >= mp1.first && mp2.first <= mp1.second;
  29. }
  30. // Coalesces match positions in |matches| after index that intersect the match
  31. // position at |index|.
  32. void CoalesceMatchesFrom(size_t index, Snippet::MatchPositions* matches) {
  33. Snippet::MatchPosition& mp = (*matches)[index];
  34. for (auto i = matches->begin() + index + 1; i != matches->end();) {
  35. if (SnippetIntersects(mp, *i)) {
  36. mp.second = std::max(mp.second, i->second);
  37. i = matches->erase(i);
  38. } else {
  39. return;
  40. }
  41. }
  42. }
  43. // Returns true if the character is considered a quote.
  44. bool IsQueryQuote(wchar_t ch) {
  45. return ch == '"' ||
  46. ch == 0xab || // left pointing double angle bracket
  47. ch == 0xbb || // right pointing double angle bracket
  48. ch == 0x201c || // left double quotation mark
  49. ch == 0x201d || // right double quotation mark
  50. ch == 0x201e; // double low-9 quotation mark
  51. }
  52. } // namespace
  53. // Inheritance structure:
  54. // Queries are represented as trees of QueryNodes.
  55. // QueryNodes are either a collection of subnodes (a QueryNodeList)
  56. // or a single word (a QueryNodeWord).
  57. // A QueryNodeWord is a single word in the query.
  58. class QueryNodeWord : public QueryNode {
  59. public:
  60. explicit QueryNodeWord(const std::u16string& word,
  61. MatchingAlgorithm matching_algorithm);
  62. QueryNodeWord(const QueryNodeWord&) = delete;
  63. QueryNodeWord& operator=(const QueryNodeWord&) = delete;
  64. ~QueryNodeWord() override;
  65. const std::u16string& word() const { return word_; }
  66. bool literal() const { return literal_; }
  67. void set_literal(bool literal) { literal_ = literal; }
  68. // QueryNode:
  69. int AppendToSQLiteQuery(std::u16string* query) const override;
  70. bool IsWord() const override;
  71. bool Matches(const std::u16string& word, bool exact) const override;
  72. bool HasMatchIn(const QueryWordVector& words,
  73. Snippet::MatchPositions* match_positions) const override;
  74. bool HasMatchIn(const QueryWordVector& words, bool exact) const override;
  75. void AppendWords(std::vector<std::u16string>* words) const override;
  76. private:
  77. std::u16string word_;
  78. bool literal_;
  79. const MatchingAlgorithm matching_algorithm_;
  80. };
  81. QueryNodeWord::QueryNodeWord(const std::u16string& word,
  82. MatchingAlgorithm matching_algorithm)
  83. : word_(word), literal_(false), matching_algorithm_(matching_algorithm) {}
  84. QueryNodeWord::~QueryNodeWord() {}
  85. int QueryNodeWord::AppendToSQLiteQuery(std::u16string* query) const {
  86. query->append(word_);
  87. // Use prefix search if we're not literal and long enough.
  88. if (!literal_ &&
  89. QueryParser::IsWordLongEnoughForPrefixSearch(word_, matching_algorithm_))
  90. *query += L'*';
  91. return 1;
  92. }
  93. bool QueryNodeWord::IsWord() const {
  94. return true;
  95. }
  96. bool QueryNodeWord::Matches(const std::u16string& word, bool exact) const {
  97. if (exact ||
  98. !QueryParser::IsWordLongEnoughForPrefixSearch(word_, matching_algorithm_))
  99. return word == word_;
  100. return word.size() >= word_.size() &&
  101. (word_.compare(0, word_.size(), word, 0, word_.size()) == 0);
  102. }
  103. bool QueryNodeWord::HasMatchIn(const QueryWordVector& words,
  104. Snippet::MatchPositions* match_positions) const {
  105. bool matched = false;
  106. for (const auto& queryWord : words) {
  107. if (Matches(queryWord.word, false)) {
  108. size_t match_start = queryWord.position;
  109. match_positions->push_back(Snippet::MatchPosition(
  110. match_start, match_start + static_cast<int>(word_.size())));
  111. matched = true;
  112. }
  113. }
  114. return matched;
  115. }
  116. bool QueryNodeWord::HasMatchIn(const QueryWordVector& words, bool exact) const {
  117. return base::ranges::any_of(words, [&](const auto& query_word) {
  118. return Matches(query_word.word, exact);
  119. });
  120. }
  121. void QueryNodeWord::AppendWords(std::vector<std::u16string>* words) const {
  122. words->push_back(word_);
  123. }
  124. // A QueryNodeList has a collection of QueryNodes which are deleted in the end.
  125. class QueryNodeList : public QueryNode {
  126. public:
  127. QueryNodeList();
  128. QueryNodeList(const QueryNodeList&) = delete;
  129. QueryNodeList& operator=(const QueryNodeList&) = delete;
  130. ~QueryNodeList() override;
  131. QueryNodeVector* children() { return &children_; }
  132. void AddChild(std::unique_ptr<QueryNode> node);
  133. // Remove empty subnodes left over from other parsing.
  134. void RemoveEmptySubnodes();
  135. // QueryNode:
  136. int AppendToSQLiteQuery(std::u16string* query) const override;
  137. bool IsWord() const override;
  138. bool Matches(const std::u16string& word, bool exact) const override;
  139. bool HasMatchIn(const QueryWordVector& words,
  140. Snippet::MatchPositions* match_positions) const override;
  141. bool HasMatchIn(const QueryWordVector& words, bool exact) const override;
  142. void AppendWords(std::vector<std::u16string>* words) const override;
  143. protected:
  144. int AppendChildrenToString(std::u16string* query) const;
  145. QueryNodeVector children_;
  146. };
  147. QueryNodeList::QueryNodeList() {}
  148. QueryNodeList::~QueryNodeList() {
  149. }
  150. void QueryNodeList::AddChild(std::unique_ptr<QueryNode> node) {
  151. children_.push_back(std::move(node));
  152. }
  153. void QueryNodeList::RemoveEmptySubnodes() {
  154. QueryNodeVector kept_children;
  155. for (size_t i = 0; i < children_.size(); ++i) {
  156. if (children_[i]->IsWord()) {
  157. kept_children.push_back(std::move(children_[i]));
  158. continue;
  159. }
  160. QueryNodeList* list_node = static_cast<QueryNodeList*>(children_[i].get());
  161. list_node->RemoveEmptySubnodes();
  162. if (!list_node->children()->empty())
  163. kept_children.push_back(std::move(children_[i]));
  164. }
  165. children_.swap(kept_children);
  166. }
  167. int QueryNodeList::AppendToSQLiteQuery(std::u16string* query) const {
  168. return AppendChildrenToString(query);
  169. }
  170. bool QueryNodeList::IsWord() const {
  171. return false;
  172. }
  173. bool QueryNodeList::Matches(const std::u16string& word, bool exact) const {
  174. NOTREACHED();
  175. return false;
  176. }
  177. bool QueryNodeList::HasMatchIn(const QueryWordVector& words,
  178. Snippet::MatchPositions* match_positions) const {
  179. NOTREACHED();
  180. return false;
  181. }
  182. bool QueryNodeList::HasMatchIn(const QueryWordVector& words, bool exact) const {
  183. NOTREACHED();
  184. return false;
  185. }
  186. void QueryNodeList::AppendWords(std::vector<std::u16string>* words) const {
  187. for (size_t i = 0; i < children_.size(); ++i)
  188. children_[i]->AppendWords(words);
  189. }
  190. int QueryNodeList::AppendChildrenToString(std::u16string* query) const {
  191. int num_words = 0;
  192. for (auto node = children_.begin(); node != children_.end(); ++node) {
  193. if (node != children_.begin())
  194. query->push_back(L' ');
  195. num_words += (*node)->AppendToSQLiteQuery(query);
  196. }
  197. return num_words;
  198. }
  199. // A QueryNodePhrase is a phrase query ("quoted").
  200. class QueryNodePhrase : public QueryNodeList {
  201. public:
  202. QueryNodePhrase();
  203. QueryNodePhrase(const QueryNodePhrase&) = delete;
  204. QueryNodePhrase& operator=(const QueryNodePhrase&) = delete;
  205. ~QueryNodePhrase() override;
  206. // QueryNodeList:
  207. int AppendToSQLiteQuery(std::u16string* query) const override;
  208. bool HasMatchIn(const QueryWordVector& words,
  209. Snippet::MatchPositions* match_positions) const override;
  210. bool HasMatchIn(const QueryWordVector& words, bool exact) const override;
  211. private:
  212. bool MatchesAll(const QueryWordVector& words,
  213. const QueryWord** first_word,
  214. const QueryWord** last_word) const;
  215. };
  216. QueryNodePhrase::QueryNodePhrase() {}
  217. QueryNodePhrase::~QueryNodePhrase() {}
  218. int QueryNodePhrase::AppendToSQLiteQuery(std::u16string* query) const {
  219. query->push_back(L'"');
  220. int num_words = AppendChildrenToString(query);
  221. query->push_back(L'"');
  222. return num_words;
  223. }
  224. bool QueryNodePhrase::MatchesAll(const QueryWordVector& words,
  225. const QueryWord** first_word,
  226. const QueryWord** last_word) const {
  227. if (words.size() < children_.size())
  228. return false;
  229. for (size_t i = 0, max = words.size() - children_.size() + 1; i < max; ++i) {
  230. bool matched_all = true;
  231. for (size_t j = 0; j < children_.size(); ++j) {
  232. if (!children_[j]->Matches(words[i + j].word, true)) {
  233. matched_all = false;
  234. break;
  235. }
  236. }
  237. if (matched_all) {
  238. *first_word = &words[i];
  239. *last_word = &words[i + children_.size() - 1];
  240. return true;
  241. }
  242. }
  243. return false;
  244. }
  245. bool QueryNodePhrase::HasMatchIn(
  246. const QueryWordVector& words,
  247. Snippet::MatchPositions* match_positions) const {
  248. const QueryWord* first_word;
  249. const QueryWord* last_word;
  250. if (MatchesAll(words, &first_word, &last_word)) {
  251. match_positions->push_back(
  252. Snippet::MatchPosition(first_word->position,
  253. last_word->position + last_word->word.length()));
  254. return true;
  255. }
  256. return false;
  257. }
  258. bool QueryNodePhrase::HasMatchIn(const QueryWordVector& words,
  259. bool exact) const {
  260. const QueryWord* first_word;
  261. const QueryWord* last_word;
  262. return MatchesAll(words, &first_word, &last_word);
  263. }
  264. // static
  265. bool QueryParser::IsWordLongEnoughForPrefixSearch(
  266. const std::u16string& word,
  267. MatchingAlgorithm matching_algorithm) {
  268. if (matching_algorithm == MatchingAlgorithm::ALWAYS_PREFIX_SEARCH)
  269. return true;
  270. DCHECK(!word.empty());
  271. size_t minimum_length = 3;
  272. // We intentionally exclude Hangul Jamos (both Conjoining and compatibility)
  273. // because they 'behave like' Latin letters. Moreover, we should
  274. // normalize the former before reaching here.
  275. if (0xAC00 <= word[0] && word[0] <= 0xD7A3)
  276. minimum_length = 2;
  277. return word.size() >= minimum_length;
  278. }
  279. // static
  280. int QueryParser::ParseQuery(const std::u16string& query,
  281. MatchingAlgorithm matching_algorithm,
  282. std::u16string* sqlite_query) {
  283. QueryNodeList root;
  284. if (!ParseQueryImpl(query, matching_algorithm, &root))
  285. return 0;
  286. return root.AppendToSQLiteQuery(sqlite_query);
  287. }
  288. // static
  289. void QueryParser::ParseQueryWords(const std::u16string& query,
  290. MatchingAlgorithm matching_algorithm,
  291. std::vector<std::u16string>* words) {
  292. QueryNodeList root;
  293. if (!ParseQueryImpl(query, matching_algorithm, &root))
  294. return;
  295. root.AppendWords(words);
  296. }
  297. // static
  298. void QueryParser::ParseQueryNodes(const std::u16string& query,
  299. MatchingAlgorithm matching_algorithm,
  300. QueryNodeVector* nodes) {
  301. QueryNodeList root;
  302. if (ParseQueryImpl(base::i18n::ToLower(query), matching_algorithm, &root))
  303. nodes->swap(*root.children());
  304. }
  305. // static
  306. bool QueryParser::DoesQueryMatch(const std::u16string& find_in_text,
  307. const QueryNodeVector& find_nodes,
  308. Snippet::MatchPositions* match_positions) {
  309. if (find_nodes.empty())
  310. return false;
  311. QueryWordVector query_words;
  312. std::u16string lower_find_in_text = base::i18n::ToLower(find_in_text);
  313. ExtractQueryWords(lower_find_in_text, &query_words);
  314. if (query_words.empty())
  315. return false;
  316. Snippet::MatchPositions matches;
  317. for (auto& find_node : find_nodes) {
  318. if (!find_node->HasMatchIn(query_words, &matches))
  319. return false;
  320. }
  321. if (lower_find_in_text.length() != find_in_text.length()) {
  322. // The lower case string differs from the original string. The matches are
  323. // meaningless.
  324. // TODO(sky): we need a better way to align the positions so that we don't
  325. // completely punt here.
  326. match_positions->clear();
  327. } else {
  328. SortAndCoalesceMatchPositions(&matches);
  329. match_positions->swap(matches);
  330. }
  331. return true;
  332. }
  333. // static
  334. bool QueryParser::DoesQueryMatch(const QueryWordVector& find_in_words,
  335. const QueryNodeVector& find_nodes,
  336. bool exact) {
  337. if (find_nodes.empty() || find_in_words.empty())
  338. return false;
  339. return base::ranges::all_of(find_nodes, [&](const auto& find_node) {
  340. return find_node->HasMatchIn(find_in_words, exact);
  341. });
  342. }
  343. // static
  344. bool QueryParser::ParseQueryImpl(const std::u16string& query,
  345. MatchingAlgorithm matching_algorithm,
  346. QueryNodeList* root) {
  347. base::i18n::BreakIterator iter(query, base::i18n::BreakIterator::BREAK_WORD);
  348. // TODO(evanm): support a locale here
  349. if (!iter.Init())
  350. return false;
  351. // To handle nesting, we maintain a stack of QueryNodeLists.
  352. // The last element (back) of the stack contains the current, deepest node.
  353. std::vector<QueryNodeList*> query_stack;
  354. query_stack.push_back(root);
  355. bool in_quotes = false; // whether we're currently in a quoted phrase
  356. while (iter.Advance()) {
  357. // Just found a span between 'prev' (inclusive) and 'pos' (exclusive). It
  358. // is not necessarily a word, but could also be a sequence of punctuation
  359. // or whitespace.
  360. if (iter.IsWord()) {
  361. std::unique_ptr<QueryNodeWord> word_node =
  362. std::make_unique<QueryNodeWord>(iter.GetString(), matching_algorithm);
  363. if (in_quotes)
  364. word_node->set_literal(true);
  365. query_stack.back()->AddChild(std::move(word_node));
  366. } else { // Punctuation.
  367. if (IsQueryQuote(query[iter.prev()])) {
  368. if (!in_quotes) {
  369. std::unique_ptr<QueryNodeList> quotes_node =
  370. std::make_unique<QueryNodePhrase>();
  371. QueryNodeList* quotes_node_ptr = quotes_node.get();
  372. query_stack.back()->AddChild(std::move(quotes_node));
  373. query_stack.push_back(quotes_node_ptr);
  374. in_quotes = true;
  375. } else {
  376. query_stack.pop_back(); // Stop adding to the quoted phrase.
  377. in_quotes = false;
  378. }
  379. }
  380. }
  381. }
  382. root->RemoveEmptySubnodes();
  383. return true;
  384. }
  385. // static
  386. void QueryParser::ExtractQueryWords(const std::u16string& text,
  387. QueryWordVector* words) {
  388. DCHECK(text == base::i18n::ToLower(text))
  389. << "The caller must have already lowercased `text`. Value = "
  390. << base::UTF16ToUTF8(text);
  391. base::i18n::BreakIterator iter(text, base::i18n::BreakIterator::BREAK_WORD);
  392. // TODO(evanm): support a locale here
  393. if (!iter.Init())
  394. return;
  395. while (iter.Advance()) {
  396. // Just found a span between 'prev' (inclusive) and 'pos' (exclusive). It
  397. // is not necessarily a word, but could also be a sequence of punctuation
  398. // or whitespace.
  399. if (iter.IsWord()) {
  400. std::u16string word = iter.GetString();
  401. if (!word.empty()) {
  402. words->push_back(QueryWord());
  403. words->back().word = word;
  404. words->back().position = iter.prev();
  405. }
  406. }
  407. }
  408. }
  409. // static
  410. void QueryParser::SortAndCoalesceMatchPositions(
  411. Snippet::MatchPositions* matches) {
  412. std::sort(matches->begin(), matches->end(), &CompareMatchPosition);
  413. // WARNING: we don't use iterator here as CoalesceMatchesFrom may remove
  414. // from matches.
  415. for (size_t i = 0; i < matches->size(); ++i)
  416. CoalesceMatchesFrom(i, matches);
  417. }
  418. } // namespace query_parser