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