| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 5 #include "components/bookmarks/core/browser/bookmark_index.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <functional> | |
| 9 #include <iterator> | |
| 10 #include <list> | |
| 11 | |
| 12 #include "base/i18n/case_conversion.h" | |
| 13 #include "base/logging.h" | |
| 14 #include "base/strings/utf_offset_string_conversions.h" | |
| 15 #include "components/bookmarks/core/browser/bookmark_client.h" | |
| 16 #include "components/bookmarks/core/browser/bookmark_match.h" | |
| 17 #include "components/bookmarks/core/browser/bookmark_node.h" | |
| 18 #include "components/bookmarks/core/browser/bookmark_utils.h" | |
| 19 #include "components/query_parser/snippet.h" | |
| 20 #include "third_party/icu/source/common/unicode/normalizer2.h" | |
| 21 | |
| 22 typedef BookmarkClient::NodeTypedCountPair NodeTypedCountPair; | |
| 23 typedef BookmarkClient::NodeTypedCountPairs NodeTypedCountPairs; | |
| 24 | |
| 25 namespace { | |
| 26 | |
| 27 // Returns a normalized version of the UTF16 string |text|. If it fails to | |
| 28 // normalize the string, returns |text| itself as a best-effort. | |
| 29 base::string16 Normalize(const base::string16& text) { | |
| 30 UErrorCode status = U_ZERO_ERROR; | |
| 31 const icu::Normalizer2* normalizer2 = | |
| 32 icu::Normalizer2::getInstance(NULL, "nfkc", UNORM2_COMPOSE, status); | |
| 33 icu::UnicodeString unicode_text( | |
| 34 text.data(), static_cast<int32_t>(text.length())); | |
| 35 icu::UnicodeString unicode_normalized_text; | |
| 36 normalizer2->normalize(unicode_text, unicode_normalized_text, status); | |
| 37 if (U_FAILURE(status)) | |
| 38 return text; | |
| 39 return base::string16(unicode_normalized_text.getBuffer(), | |
| 40 unicode_normalized_text.length()); | |
| 41 } | |
| 42 | |
| 43 // Sort functor for NodeTypedCountPairs. We sort in decreasing order of typed | |
| 44 // count so that the best matches will always be added to the results. | |
| 45 struct NodeTypedCountPairSortFunctor | |
| 46 : std::binary_function<NodeTypedCountPair, NodeTypedCountPair, bool> { | |
| 47 bool operator()(const NodeTypedCountPair& a, | |
| 48 const NodeTypedCountPair& b) const { | |
| 49 return a.second > b.second; | |
| 50 } | |
| 51 }; | |
| 52 | |
| 53 // Extract the const Node* stored in a BookmarkClient::NodeTypedCountPair. | |
| 54 struct NodeTypedCountPairExtractNodeFunctor | |
| 55 : std::unary_function<NodeTypedCountPair, const BookmarkNode*> { | |
| 56 const BookmarkNode* operator()(const NodeTypedCountPair& pair) const { | |
| 57 return pair.first; | |
| 58 } | |
| 59 }; | |
| 60 | |
| 61 } // namespace | |
| 62 | |
| 63 // Used when finding the set of bookmarks that match a query. Each match | |
| 64 // represents a set of terms (as an interator into the Index) matching the | |
| 65 // query as well as the set of nodes that contain those terms in their titles. | |
| 66 struct BookmarkIndex::Match { | |
| 67 // List of terms matching the query. | |
| 68 std::list<Index::const_iterator> terms; | |
| 69 | |
| 70 // The set of nodes matching the terms. As an optimization this is empty | |
| 71 // when we match only one term, and is filled in when we get more than one | |
| 72 // term. We can do this as when we have only one matching term we know | |
| 73 // the set of matching nodes is terms.front()->second. | |
| 74 // | |
| 75 // Use nodes_begin() and nodes_end() to get an iterator over the set as | |
| 76 // it handles the necessary switching between nodes and terms.front(). | |
| 77 NodeSet nodes; | |
| 78 | |
| 79 // Returns an iterator to the beginning of the matching nodes. See | |
| 80 // description of nodes for why this should be used over nodes.begin(). | |
| 81 NodeSet::const_iterator nodes_begin() const; | |
| 82 | |
| 83 // Returns an iterator to the beginning of the matching nodes. See | |
| 84 // description of nodes for why this should be used over nodes.end(). | |
| 85 NodeSet::const_iterator nodes_end() const; | |
| 86 }; | |
| 87 | |
| 88 BookmarkIndex::NodeSet::const_iterator | |
| 89 BookmarkIndex::Match::nodes_begin() const { | |
| 90 return nodes.empty() ? terms.front()->second.begin() : nodes.begin(); | |
| 91 } | |
| 92 | |
| 93 BookmarkIndex::NodeSet::const_iterator BookmarkIndex::Match::nodes_end() const { | |
| 94 return nodes.empty() ? terms.front()->second.end() : nodes.end(); | |
| 95 } | |
| 96 | |
| 97 BookmarkIndex::BookmarkIndex(BookmarkClient* client, | |
| 98 bool index_urls, | |
| 99 const std::string& languages) | |
| 100 : client_(client), | |
| 101 languages_(languages), | |
| 102 index_urls_(index_urls) { | |
| 103 DCHECK(client_); | |
| 104 } | |
| 105 | |
| 106 BookmarkIndex::~BookmarkIndex() { | |
| 107 } | |
| 108 | |
| 109 void BookmarkIndex::Add(const BookmarkNode* node) { | |
| 110 if (!node->is_url()) | |
| 111 return; | |
| 112 std::vector<base::string16> terms = | |
| 113 ExtractQueryWords(Normalize(node->GetTitle())); | |
| 114 for (size_t i = 0; i < terms.size(); ++i) | |
| 115 RegisterNode(terms[i], node); | |
| 116 if (index_urls_) { | |
| 117 terms = ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching( | |
| 118 node->url(), languages_, NULL)); | |
| 119 for (size_t i = 0; i < terms.size(); ++i) | |
| 120 RegisterNode(terms[i], node); | |
| 121 } | |
| 122 } | |
| 123 | |
| 124 void BookmarkIndex::Remove(const BookmarkNode* node) { | |
| 125 if (!node->is_url()) | |
| 126 return; | |
| 127 | |
| 128 std::vector<base::string16> terms = | |
| 129 ExtractQueryWords(Normalize(node->GetTitle())); | |
| 130 for (size_t i = 0; i < terms.size(); ++i) | |
| 131 UnregisterNode(terms[i], node); | |
| 132 if (index_urls_) { | |
| 133 terms = ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching( | |
| 134 node->url(), languages_, NULL)); | |
| 135 for (size_t i = 0; i < terms.size(); ++i) | |
| 136 UnregisterNode(terms[i], node); | |
| 137 } | |
| 138 } | |
| 139 | |
| 140 void BookmarkIndex::GetBookmarksMatching(const base::string16& input_query, | |
| 141 size_t max_count, | |
| 142 std::vector<BookmarkMatch>* results) { | |
| 143 const base::string16 query = Normalize(input_query); | |
| 144 std::vector<base::string16> terms = ExtractQueryWords(query); | |
| 145 if (terms.empty()) | |
| 146 return; | |
| 147 | |
| 148 Matches matches; | |
| 149 for (size_t i = 0; i < terms.size(); ++i) { | |
| 150 if (!GetBookmarksMatchingTerm(terms[i], i == 0, &matches)) | |
| 151 return; | |
| 152 } | |
| 153 | |
| 154 Nodes sorted_nodes; | |
| 155 SortMatches(matches, &sorted_nodes); | |
| 156 | |
| 157 // We use a QueryParser to fill in match positions for us. It's not the most | |
| 158 // efficient way to go about this, but by the time we get here we know what | |
| 159 // matches and so this shouldn't be performance critical. | |
| 160 query_parser::QueryParser parser; | |
| 161 ScopedVector<query_parser::QueryNode> query_nodes; | |
| 162 parser.ParseQueryNodes(query, &query_nodes.get()); | |
| 163 | |
| 164 // The highest typed counts should be at the beginning of the results vector | |
| 165 // so that the best matches will always be included in the results. The loop | |
| 166 // that calculates result relevance in HistoryContentsProvider::ConvertResults | |
| 167 // will run backwards to assure higher relevance will be attributed to the | |
| 168 // best matches. | |
| 169 for (Nodes::const_iterator i = sorted_nodes.begin(); | |
| 170 i != sorted_nodes.end() && results->size() < max_count; | |
| 171 ++i) | |
| 172 AddMatchToResults(*i, &parser, query_nodes.get(), results); | |
| 173 } | |
| 174 | |
| 175 void BookmarkIndex::SortMatches(const Matches& matches, | |
| 176 Nodes* sorted_nodes) const { | |
| 177 NodeSet nodes; | |
| 178 for (Matches::const_iterator i = matches.begin(); i != matches.end(); ++i) { | |
| 179 #if !defined(OS_ANDROID) | |
| 180 nodes.insert(i->nodes_begin(), i->nodes_end()); | |
| 181 #else | |
| 182 // Work around a bug in the implementation of std::set::insert in the STL | |
| 183 // used on android (http://crbug.com/367050). | |
| 184 for (NodeSet::const_iterator n = i->nodes_begin(); n != i->nodes_end(); ++n) | |
| 185 nodes.insert(nodes.end(), *n); | |
| 186 #endif | |
| 187 } | |
| 188 sorted_nodes->reserve(sorted_nodes->size() + nodes.size()); | |
| 189 if (client_->SupportsTypedCountForNodes()) { | |
| 190 NodeTypedCountPairs node_typed_counts; | |
| 191 client_->GetTypedCountForNodes(nodes, &node_typed_counts); | |
| 192 std::sort(node_typed_counts.begin(), | |
| 193 node_typed_counts.end(), | |
| 194 NodeTypedCountPairSortFunctor()); | |
| 195 std::transform(node_typed_counts.begin(), | |
| 196 node_typed_counts.end(), | |
| 197 std::back_inserter(*sorted_nodes), | |
| 198 NodeTypedCountPairExtractNodeFunctor()); | |
| 199 } else { | |
| 200 sorted_nodes->insert(sorted_nodes->end(), nodes.begin(), nodes.end()); | |
| 201 } | |
| 202 } | |
| 203 | |
| 204 void BookmarkIndex::AddMatchToResults( | |
| 205 const BookmarkNode* node, | |
| 206 query_parser::QueryParser* parser, | |
| 207 const query_parser::QueryNodeStarVector& query_nodes, | |
| 208 std::vector<BookmarkMatch>* results) { | |
| 209 // Check that the result matches the query. The previous search | |
| 210 // was a simple per-word search, while the more complex matching | |
| 211 // of QueryParser may filter it out. For example, the query | |
| 212 // ["thi"] will match the bookmark titled [Thinking], but since | |
| 213 // ["thi"] is quoted we don't want to do a prefix match. | |
| 214 query_parser::QueryWordVector title_words, url_words; | |
| 215 const base::string16 lower_title = | |
| 216 base::i18n::ToLower(Normalize(node->GetTitle())); | |
| 217 parser->ExtractQueryWords(lower_title, &title_words); | |
| 218 base::OffsetAdjuster::Adjustments adjustments; | |
| 219 if (index_urls_) { | |
| 220 parser->ExtractQueryWords(bookmark_utils::CleanUpUrlForMatching( | |
| 221 node->url(), languages_, &adjustments), &url_words); | |
| 222 } | |
| 223 query_parser::Snippet::MatchPositions title_matches, url_matches; | |
| 224 for (size_t i = 0; i < query_nodes.size(); ++i) { | |
| 225 const bool has_title_matches = | |
| 226 query_nodes[i]->HasMatchIn(title_words, &title_matches); | |
| 227 const bool has_url_matches = index_urls_ && | |
| 228 query_nodes[i]->HasMatchIn(url_words, &url_matches); | |
| 229 if (!has_title_matches && !has_url_matches) | |
| 230 return; | |
| 231 query_parser::QueryParser::SortAndCoalesceMatchPositions(&title_matches); | |
| 232 if (index_urls_) | |
| 233 query_parser::QueryParser::SortAndCoalesceMatchPositions(&url_matches); | |
| 234 } | |
| 235 BookmarkMatch match; | |
| 236 if (lower_title.length() == node->GetTitle().length()) { | |
| 237 // Only use title matches if the lowercase string is the same length | |
| 238 // as the original string, otherwise the matches are meaningless. | |
| 239 // TODO(mpearson): revise match positions appropriately. | |
| 240 match.title_match_positions.swap(title_matches); | |
| 241 } | |
| 242 if (index_urls_) { | |
| 243 // Now that we're done processing this entry, correct the offsets of the | |
| 244 // matches in |url_matches| so they point to offsets in the original URL | |
| 245 // spec, not the cleaned-up URL string that we used for matching. | |
| 246 std::vector<size_t> offsets = | |
| 247 BookmarkMatch::OffsetsFromMatchPositions(url_matches); | |
| 248 base::OffsetAdjuster::UnadjustOffsets(adjustments, &offsets); | |
| 249 url_matches = | |
| 250 BookmarkMatch::ReplaceOffsetsInMatchPositions(url_matches, offsets); | |
| 251 match.url_match_positions.swap(url_matches); | |
| 252 } | |
| 253 match.node = node; | |
| 254 results->push_back(match); | |
| 255 } | |
| 256 | |
| 257 bool BookmarkIndex::GetBookmarksMatchingTerm(const base::string16& term, | |
| 258 bool first_term, | |
| 259 Matches* matches) { | |
| 260 Index::const_iterator i = index_.lower_bound(term); | |
| 261 if (i == index_.end()) | |
| 262 return false; | |
| 263 | |
| 264 if (!query_parser::QueryParser::IsWordLongEnoughForPrefixSearch(term)) { | |
| 265 // Term is too short for prefix match, compare using exact match. | |
| 266 if (i->first != term) | |
| 267 return false; // No bookmarks with this term. | |
| 268 | |
| 269 if (first_term) { | |
| 270 Match match; | |
| 271 match.terms.push_back(i); | |
| 272 matches->push_back(match); | |
| 273 return true; | |
| 274 } | |
| 275 CombineMatchesInPlace(i, matches); | |
| 276 } else if (first_term) { | |
| 277 // This is the first term and we're doing a prefix match. Loop through | |
| 278 // index adding all entries that start with term to matches. | |
| 279 while (i != index_.end() && | |
| 280 i->first.size() >= term.size() && | |
| 281 term.compare(0, term.size(), i->first, 0, term.size()) == 0) { | |
| 282 Match match; | |
| 283 match.terms.push_back(i); | |
| 284 matches->push_back(match); | |
| 285 ++i; | |
| 286 } | |
| 287 } else { | |
| 288 // Prefix match and not the first term. Loop through index combining | |
| 289 // current matches in matches with term, placing result in result. | |
| 290 Matches result; | |
| 291 while (i != index_.end() && | |
| 292 i->first.size() >= term.size() && | |
| 293 term.compare(0, term.size(), i->first, 0, term.size()) == 0) { | |
| 294 CombineMatches(i, *matches, &result); | |
| 295 ++i; | |
| 296 } | |
| 297 matches->swap(result); | |
| 298 } | |
| 299 return !matches->empty(); | |
| 300 } | |
| 301 | |
| 302 void BookmarkIndex::CombineMatchesInPlace(const Index::const_iterator& index_i, | |
| 303 Matches* matches) { | |
| 304 for (size_t i = 0; i < matches->size(); ) { | |
| 305 Match* match = &((*matches)[i]); | |
| 306 NodeSet intersection; | |
| 307 std::set_intersection(match->nodes_begin(), match->nodes_end(), | |
| 308 index_i->second.begin(), index_i->second.end(), | |
| 309 std::inserter(intersection, intersection.begin())); | |
| 310 if (intersection.empty()) { | |
| 311 matches->erase(matches->begin() + i); | |
| 312 } else { | |
| 313 match->terms.push_back(index_i); | |
| 314 match->nodes.swap(intersection); | |
| 315 ++i; | |
| 316 } | |
| 317 } | |
| 318 } | |
| 319 | |
| 320 void BookmarkIndex::CombineMatches(const Index::const_iterator& index_i, | |
| 321 const Matches& current_matches, | |
| 322 Matches* result) { | |
| 323 for (size_t i = 0; i < current_matches.size(); ++i) { | |
| 324 const Match& match = current_matches[i]; | |
| 325 NodeSet intersection; | |
| 326 std::set_intersection(match.nodes_begin(), match.nodes_end(), | |
| 327 index_i->second.begin(), index_i->second.end(), | |
| 328 std::inserter(intersection, intersection.begin())); | |
| 329 if (!intersection.empty()) { | |
| 330 result->push_back(Match()); | |
| 331 Match& combined_match = result->back(); | |
| 332 combined_match.terms = match.terms; | |
| 333 combined_match.terms.push_back(index_i); | |
| 334 combined_match.nodes.swap(intersection); | |
| 335 } | |
| 336 } | |
| 337 } | |
| 338 | |
| 339 std::vector<base::string16> BookmarkIndex::ExtractQueryWords( | |
| 340 const base::string16& query) { | |
| 341 std::vector<base::string16> terms; | |
| 342 if (query.empty()) | |
| 343 return std::vector<base::string16>(); | |
| 344 query_parser::QueryParser parser; | |
| 345 parser.ParseQueryWords(base::i18n::ToLower(query), &terms); | |
| 346 return terms; | |
| 347 } | |
| 348 | |
| 349 void BookmarkIndex::RegisterNode(const base::string16& term, | |
| 350 const BookmarkNode* node) { | |
| 351 index_[term].insert(node); | |
| 352 } | |
| 353 | |
| 354 void BookmarkIndex::UnregisterNode(const base::string16& term, | |
| 355 const BookmarkNode* node) { | |
| 356 Index::iterator i = index_.find(term); | |
| 357 if (i == index_.end()) { | |
| 358 // We can get here if the node has the same term more than once. For | |
| 359 // example, a bookmark with the title 'foo foo' would end up here. | |
| 360 return; | |
| 361 } | |
| 362 i->second.erase(node); | |
| 363 if (i->second.empty()) | |
| 364 index_.erase(i); | |
| 365 } | |
| OLD | NEW |
|---|
Chromium Code Reviews