query_parser.h 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
  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. #ifndef COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_
  5. #define COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_
  6. #include <stddef.h>
  7. #include <memory>
  8. #include <string>
  9. #include <vector>
  10. #include "components/query_parser/snippet.h"
  11. namespace query_parser {
  12. class QueryNodeList;
  13. // Used by HasMatchIn.
  14. struct QueryWord {
  15. // The word to match against.
  16. std::u16string word;
  17. // The starting position of the word in the original text.
  18. size_t position;
  19. };
  20. enum class MatchingAlgorithm {
  21. // Only words long enough are considered for prefix search. Shorter words are
  22. // considered for exact matches.
  23. DEFAULT,
  24. // All words are considered for a prefix search.
  25. ALWAYS_PREFIX_SEARCH,
  26. kMaxValue = ALWAYS_PREFIX_SEARCH,
  27. };
  28. using QueryWordVector = std::vector<query_parser::QueryWord>;
  29. // `QueryNode` is used by `QueryParser` to represent the elements that
  30. // constitute a query. While `QueryNode` is exposed by way of `ParseQuery`, it
  31. // really isn't meant for external usage.
  32. class QueryNode {
  33. public:
  34. virtual ~QueryNode() {}
  35. // Serialize ourselves out to a string that can be passed to SQLite. Returns
  36. // the number of words in this node.
  37. virtual int AppendToSQLiteQuery(std::u16string* query) const = 0;
  38. // Return true if this is a `QueryNodeWord`, false if it's a `QueryNodeList`.
  39. virtual bool IsWord() const = 0;
  40. // Returns true if this node matches `word`. If `exact` is true, the string
  41. // must exactly match. Otherwise, this uses a starts-with comparison.
  42. virtual bool Matches(const std::u16string& word, bool exact) const = 0;
  43. // Returns true if this node matches at least one of the words in `words`. An
  44. // entry is added to `match_positions` for all matching words giving the
  45. // matching regions. Uses a starts-with comparison.
  46. virtual bool HasMatchIn(const QueryWordVector& words,
  47. Snippet::MatchPositions* match_positions) const = 0;
  48. // Returns true if this node matches at least one of the words in `words`.
  49. // If `exact` is true, at least one of the words must be an exact match.
  50. virtual bool HasMatchIn(const QueryWordVector& words, bool exact) const = 0;
  51. // Appends the words that make up this node in `words`.
  52. virtual void AppendWords(std::vector<std::u16string>* words) const = 0;
  53. };
  54. using QueryNodeVector = std::vector<std::unique_ptr<query_parser::QueryNode>>;
  55. // This class is used to parse queries entered into the history search into more
  56. // normalized queries that can be passed to the SQLite backend.
  57. class QueryParser {
  58. public:
  59. QueryParser() = delete;
  60. QueryParser(const QueryParser&) = delete;
  61. QueryParser& operator=(const QueryParser&) = delete;
  62. ~QueryParser() = delete;
  63. // For CJK ideographs and Korean Hangul, even a single character
  64. // can be useful in prefix matching, but that may give us too many
  65. // false positives. Moreover, the current ICU word breaker gives us
  66. // back every single Chinese character as a word so that there's no
  67. // point doing anything for them and we only adjust the minimum length
  68. // to 2 for Korean Hangul while using 3 for others. This is a temporary
  69. // hack until we have a segmentation support.
  70. static bool IsWordLongEnoughForPrefixSearch(
  71. const std::u16string& word,
  72. MatchingAlgorithm matching_algorithm);
  73. // Parse a query into a SQLite query. The resulting query is placed in
  74. // |sqlite_query| and the number of words is returned.
  75. static int ParseQuery(const std::u16string& query,
  76. MatchingAlgorithm matching_algorithm,
  77. std::u16string* sqlite_query);
  78. // Parses |query|, returning the words that make up it. Any words in quotes
  79. // are put in |words| without the quotes. For example, the query text
  80. // "foo bar" results in two entries being added to words, one for foo and one
  81. // for bar.
  82. static void ParseQueryWords(const std::u16string& query,
  83. MatchingAlgorithm matching_algorithm,
  84. std::vector<std::u16string>* words);
  85. // Parses |query|, returning the nodes that constitute the valid words in the
  86. // query. This is intended for later usage with DoesQueryMatch. Ownership of
  87. // the nodes passes to the caller.
  88. static void ParseQueryNodes(const std::u16string& query,
  89. MatchingAlgorithm matching_algorithm,
  90. QueryNodeVector* nodes);
  91. // Returns true if all of the |find_nodes| are found in |find_in_text|.
  92. // |find_nodes| should have been created by calling |ParseQuery()|. If all
  93. // nodes were successfully found, each of the matching positions in the text
  94. // is added to |match_positions|.
  95. static bool DoesQueryMatch(const std::u16string& find_in_text,
  96. const QueryNodeVector& find_nodes,
  97. Snippet::MatchPositions* match_positions);
  98. // Returns true if all of the |find_nodes| are found in |find_in_words|.
  99. // |find_nodes| should have been created by calling |ParseQuery()|.
  100. // If |exact| is set to true, only exact matches are considered matches.
  101. static bool DoesQueryMatch(const QueryWordVector& find_in_words,
  102. const QueryNodeVector& find_nodes,
  103. bool exact = false);
  104. // Extracts the words from |text|, placing each word into |words|.
  105. // |text| must already be lowercased by the caller, as otherwise the output
  106. // will NEVER match anything.
  107. static void ExtractQueryWords(const std::u16string& text,
  108. QueryWordVector* words);
  109. // Sorts the match positions in |matches| by their first index, then
  110. // coalesces any match positions that intersect each other.
  111. static void SortAndCoalesceMatchPositions(Snippet::MatchPositions* matches);
  112. private:
  113. // Does the work of parsing |query|; creates nodes in |root| as appropriate.
  114. // This is invoked from both of the ParseQuery methods.
  115. static bool ParseQueryImpl(const std::u16string& query,
  116. MatchingAlgorithm matching_algorithm,
  117. QueryNodeList* root);
  118. };
  119. } // namespace query_parser
  120. #endif // COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_