| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ | 5 #ifndef COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ |
| 6 #define COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ | 6 #define COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ |
| 7 | 7 |
| 8 #include <stddef.h> | 8 #include <stddef.h> |
| 9 | 9 |
| 10 #include <memory> |
| 10 #include <vector> | 11 #include <vector> |
| 11 | 12 |
| 12 #include "base/macros.h" | 13 #include "base/macros.h" |
| 13 #include "base/strings/string16.h" | 14 #include "base/strings/string16.h" |
| 14 #include "components/query_parser/snippet.h" | 15 #include "components/query_parser/snippet.h" |
| 15 | 16 |
| 16 namespace query_parser { | 17 namespace query_parser { |
| 17 | 18 |
| 18 class QueryNodeList; | 19 class QueryNodeList; |
| 19 | 20 |
| 20 // Used by HasMatchIn. | 21 // Used by HasMatchIn. |
| 21 struct QueryWord { | 22 struct QueryWord { |
| 22 // The work to match against. | 23 // The work to match against. |
| 23 base::string16 word; | 24 base::string16 word; |
| 24 | 25 |
| 25 // The starting position of the word in the original text. | 26 // The starting position of the word in the original text. |
| 26 size_t position; | 27 size_t position; |
| 27 }; | 28 }; |
| 28 | 29 |
| 29 enum class MatchingAlgorithm { | 30 enum class MatchingAlgorithm { |
| 30 // Only words long enough are considered for prefix search. Shorter words are | 31 // Only words long enough are considered for prefix search. Shorter words are |
| 31 // considered for exact matches. | 32 // considered for exact matches. |
| 32 DEFAULT, | 33 DEFAULT, |
| 33 // All words are considered for a prefix search. | 34 // All words are considered for a prefix search. |
| 34 ALWAYS_PREFIX_SEARCH, | 35 ALWAYS_PREFIX_SEARCH, |
| 35 }; | 36 }; |
| 36 | 37 |
| 37 typedef std::vector<query_parser::QueryWord> QueryWordVector; | 38 using QueryWordVector = std::vector<query_parser::QueryWord>; |
| 38 | 39 |
| 39 // QueryNode is used by QueryParser to represent the elements that constitute a | 40 // QueryNode is used by QueryParser to represent the elements that constitute a |
| 40 // query. While QueryNode is exposed by way of ParseQuery, it really isn't meant | 41 // query. While QueryNode is exposed by way of ParseQuery, it really isn't meant |
| 41 // for external usage. | 42 // for external usage. |
| 42 class QueryNode { | 43 class QueryNode { |
| 43 public: | 44 public: |
| 44 virtual ~QueryNode() {} | 45 virtual ~QueryNode() {} |
| 45 | 46 |
| 46 // Serialize ourselves out to a string that can be passed to SQLite. Returns | 47 // Serialize ourselves out to a string that can be passed to SQLite. Returns |
| 47 // the number of words in this node. | 48 // the number of words in this node. |
| (...skipping 12 matching lines...) Expand all Loading... |
| 60 virtual bool HasMatchIn(const QueryWordVector& words, | 61 virtual bool HasMatchIn(const QueryWordVector& words, |
| 61 Snippet::MatchPositions* match_positions) const = 0; | 62 Snippet::MatchPositions* match_positions) const = 0; |
| 62 | 63 |
| 63 // Returns true if this node matches at least one of the words in |words|. | 64 // Returns true if this node matches at least one of the words in |words|. |
| 64 virtual bool HasMatchIn(const QueryWordVector& words) const = 0; | 65 virtual bool HasMatchIn(const QueryWordVector& words) const = 0; |
| 65 | 66 |
| 66 // Appends the words that make up this node in |words|. | 67 // Appends the words that make up this node in |words|. |
| 67 virtual void AppendWords(std::vector<base::string16>* words) const = 0; | 68 virtual void AppendWords(std::vector<base::string16>* words) const = 0; |
| 68 }; | 69 }; |
| 69 | 70 |
| 70 typedef std::vector<query_parser::QueryNode*> QueryNodeStarVector; | 71 using QueryNodeVector = std::vector<std::unique_ptr<query_parser::QueryNode>>; |
| 71 | 72 |
| 72 // This class is used to parse queries entered into the history search into more | 73 // This class is used to parse queries entered into the history search into more |
| 73 // normalized queries that can be passed to the SQLite backend. | 74 // normalized queries that can be passed to the SQLite backend. |
| 74 class QueryParser { | 75 class QueryParser { |
| 75 public: | 76 public: |
| 76 QueryParser(); | 77 QueryParser(); |
| 77 | 78 |
| 78 // For CJK ideographs and Korean Hangul, even a single character | 79 // For CJK ideographs and Korean Hangul, even a single character |
| 79 // can be useful in prefix matching, but that may give us too many | 80 // can be useful in prefix matching, but that may give us too many |
| 80 // false positives. Moreover, the current ICU word breaker gives us | 81 // false positives. Moreover, the current ICU word breaker gives us |
| (...skipping 17 matching lines...) Expand all Loading... |
| 98 // for bar. | 99 // for bar. |
| 99 void ParseQueryWords(const base::string16& query, | 100 void ParseQueryWords(const base::string16& query, |
| 100 MatchingAlgorithm matching_algorithm, | 101 MatchingAlgorithm matching_algorithm, |
| 101 std::vector<base::string16>* words); | 102 std::vector<base::string16>* words); |
| 102 | 103 |
| 103 // Parses |query|, returning the nodes that constitute the valid words in the | 104 // Parses |query|, returning the nodes that constitute the valid words in the |
| 104 // query. This is intended for later usage with DoesQueryMatch. Ownership of | 105 // query. This is intended for later usage with DoesQueryMatch. Ownership of |
| 105 // the nodes passes to the caller. | 106 // the nodes passes to the caller. |
| 106 void ParseQueryNodes(const base::string16& query, | 107 void ParseQueryNodes(const base::string16& query, |
| 107 MatchingAlgorithm matching_algorithm, | 108 MatchingAlgorithm matching_algorithm, |
| 108 QueryNodeStarVector* nodes); | 109 QueryNodeVector* nodes); |
| 109 | 110 |
| 110 // Returns true if the string text matches the query nodes created by a call | 111 // Returns true if the string text matches the query nodes created by a call |
| 111 // to ParseQuery. If the query does match, each of the matching positions in | 112 // to ParseQuery. If the query does match, each of the matching positions in |
| 112 // the text is added to |match_positions|. | 113 // the text is added to |match_positions|. |
| 113 bool DoesQueryMatch(const base::string16& text, | 114 bool DoesQueryMatch(const base::string16& text, |
| 114 const QueryNodeStarVector& nodes, | 115 const QueryNodeVector& nodes, |
| 115 Snippet::MatchPositions* match_positions); | 116 Snippet::MatchPositions* match_positions); |
| 116 | 117 |
| 117 // Returns true if all of the |words| match the query |nodes| created by a | 118 // Returns true if all of the |words| match the query |nodes| created by a |
| 118 // call to ParseQuery. | 119 // call to ParseQuery. |
| 119 bool DoesQueryMatch(const QueryWordVector& words, | 120 bool DoesQueryMatch(const QueryWordVector& words, |
| 120 const QueryNodeStarVector& nodes); | 121 const QueryNodeVector& nodes); |
| 121 | 122 |
| 122 // Extracts the words from |text|, placing each word into |words|. | 123 // Extracts the words from |text|, placing each word into |words|. |
| 123 void ExtractQueryWords(const base::string16& text, | 124 void ExtractQueryWords(const base::string16& text, |
| 124 QueryWordVector* words); | 125 QueryWordVector* words); |
| 125 | 126 |
| 126 // Sorts the match positions in |matches| by their first index, then | 127 // Sorts the match positions in |matches| by their first index, then |
| 127 // coalesces any match positions that intersect each other. | 128 // coalesces any match positions that intersect each other. |
| 128 static void SortAndCoalesceMatchPositions(Snippet::MatchPositions* matches); | 129 static void SortAndCoalesceMatchPositions(Snippet::MatchPositions* matches); |
| 129 | 130 |
| 130 private: | 131 private: |
| 131 // Does the work of parsing |query|; creates nodes in |root| as appropriate. | 132 // Does the work of parsing |query|; creates nodes in |root| as appropriate. |
| 132 // This is invoked from both of the ParseQuery methods. | 133 // This is invoked from both of the ParseQuery methods. |
| 133 bool ParseQueryImpl(const base::string16& query, | 134 bool ParseQueryImpl(const base::string16& query, |
| 134 MatchingAlgorithm matching_algorithm, | 135 MatchingAlgorithm matching_algorithm, |
| 135 QueryNodeList* root); | 136 QueryNodeList* root); |
| 136 | 137 |
| 137 DISALLOW_COPY_AND_ASSIGN(QueryParser); | 138 DISALLOW_COPY_AND_ASSIGN(QueryParser); |
| 138 }; | 139 }; |
| 139 | 140 |
| 140 } // namespace query_parser | 141 } // namespace query_parser |
| 141 | 142 |
| 142 #endif // COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ | 143 #endif // COMPONENTS_QUERY_PARSER_QUERY_PARSER_H_ |
| OLD | NEW |