15c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Copyright 2014 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "components/bookmarks/browser/bookmark_index.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include <functional> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <iterator> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <list> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/i18n/case_conversion.h" 135c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "base/logging.h" 145c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#include "base/strings/utf_offset_string_conversions.h" 15cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "components/bookmarks/browser/bookmark_client.h" 16cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "components/bookmarks/browser/bookmark_match.h" 17cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "components/bookmarks/browser/bookmark_node.h" 18cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "components/bookmarks/browser/bookmark_utils.h" 190529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch#include "components/query_parser/snippet.h" 20e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch#include "third_party/icu/source/common/unicode/normalizer2.h" 21e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace bookmarks { 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 245c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liutypedef BookmarkClient::NodeTypedCountPair NodeTypedCountPair; 255c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liutypedef BookmarkClient::NodeTypedCountPairs NodeTypedCountPairs; 265c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 27e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochnamespace { 28e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 29e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// Returns a normalized version of the UTF16 string |text|. If it fails to 30e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// normalize the string, returns |text| itself as a best-effort. 31e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochbase::string16 Normalize(const base::string16& text) { 32e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch UErrorCode status = U_ZERO_ERROR; 33e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch const icu::Normalizer2* normalizer2 = 34e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch icu::Normalizer2::getInstance(NULL, "nfkc", UNORM2_COMPOSE, status); 355c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu icu::UnicodeString unicode_text( 365c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu text.data(), static_cast<int32_t>(text.length())); 37e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch icu::UnicodeString unicode_normalized_text; 38e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch normalizer2->normalize(unicode_text, unicode_normalized_text, status); 39e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch if (U_FAILURE(status)) 40e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return text; 41e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch return base::string16(unicode_normalized_text.getBuffer(), 42e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch unicode_normalized_text.length()); 43e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch} 44e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 455c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Sort functor for NodeTypedCountPairs. We sort in decreasing order of typed 465c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// count so that the best matches will always be added to the results. 475c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liustruct NodeTypedCountPairSortFunctor 485c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu : std::binary_function<NodeTypedCountPair, NodeTypedCountPair, bool> { 495c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu bool operator()(const NodeTypedCountPair& a, 505c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu const NodeTypedCountPair& b) const { 515c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu return a.second > b.second; 525c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu } 535c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}; 545c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 555c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu// Extract the const Node* stored in a BookmarkClient::NodeTypedCountPair. 565c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liustruct NodeTypedCountPairExtractNodeFunctor 575c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu : std::unary_function<NodeTypedCountPair, const BookmarkNode*> { 585c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu const BookmarkNode* operator()(const NodeTypedCountPair& pair) const { 595c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu return pair.first; 605c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu } 615c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu}; 625c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu 63e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch} // namespace 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Used when finding the set of bookmarks that match a query. Each match 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// represents a set of terms (as an interator into the Index) matching the 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// query as well as the set of nodes that contain those terms in their titles. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct BookmarkIndex::Match { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // List of terms matching the query. 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::list<Index::const_iterator> terms; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The set of nodes matching the terms. As an optimization this is empty 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when we match only one term, and is filled in when we get more than one 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // term. We can do this as when we have only one matching term we know 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the set of matching nodes is terms.front()->second. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Use nodes_begin() and nodes_end() to get an iterator over the set as 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it handles the necessary switching between nodes and terms.front(). 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeSet nodes; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns an iterator to the beginning of the matching nodes. See 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // description of nodes for why this should be used over nodes.begin(). 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeSet::const_iterator nodes_begin() const; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns an iterator to the beginning of the matching nodes. See 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // description of nodes for why this should be used over nodes.end(). 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeSet::const_iterator nodes_end() const; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BookmarkIndex::NodeSet::const_iterator 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BookmarkIndex::Match::nodes_begin() const { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return nodes.empty() ? terms.front()->second.begin() : nodes.begin(); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BookmarkIndex::NodeSet::const_iterator BookmarkIndex::Match::nodes_end() const { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return nodes.empty() ? terms.front()->second.end() : nodes.end(); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo LiuBookmarkIndex::BookmarkIndex(BookmarkClient* client, 1000529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch const std::string& languages) 1015c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu : client_(client), 1021320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci languages_(languages) { 1035c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu DCHECK(client_); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BookmarkIndex::~BookmarkIndex() { 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::Add(const BookmarkNode* node) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!node->is_url()) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 112e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch std::vector<base::string16> terms = 113e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch ExtractQueryWords(Normalize(node->GetTitle())); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < terms.size(); ++i) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RegisterNode(terms[i], node); 1161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci terms = 1171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ExtractQueryWords(CleanUpUrlForMatching(node->url(), languages_, NULL)); 1181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (size_t i = 0; i < terms.size(); ++i) 1191320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci RegisterNode(terms[i], node); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::Remove(const BookmarkNode* node) { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!node->is_url()) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 126e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch std::vector<base::string16> terms = 127e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch ExtractQueryWords(Normalize(node->GetTitle())); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < terms.size(); ++i) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UnregisterNode(terms[i], node); 1301320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci terms = 1311320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci ExtractQueryWords(CleanUpUrlForMatching(node->url(), languages_, NULL)); 1321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (size_t i = 0; i < terms.size(); ++i) 1331320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci UnregisterNode(terms[i], node); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1360529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochvoid BookmarkIndex::GetBookmarksMatching(const base::string16& input_query, 1370529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch size_t max_count, 1380529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch std::vector<BookmarkMatch>* results) { 139e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch const base::string16 query = Normalize(input_query); 1405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::vector<base::string16> terms = ExtractQueryWords(query); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (terms.empty()) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches matches; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < terms.size(); ++i) { 1460529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (!GetBookmarksMatchingTerm(terms[i], i == 0, &matches)) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu Nodes sorted_nodes; 1515c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu SortMatches(matches, &sorted_nodes); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We use a QueryParser to fill in match positions for us. It's not the most 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // efficient way to go about this, but by the time we get here we know what 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // matches and so this shouldn't be performance critical. 1560529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::QueryParser parser; 1570529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch ScopedVector<query_parser::QueryNode> query_nodes; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) parser.ParseQueryNodes(query, &query_nodes.get()); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The highest typed counts should be at the beginning of the results vector 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // so that the best matches will always be included in the results. The loop 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that calculates result relevance in HistoryContentsProvider::ConvertResults 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will run backwards to assure higher relevance will be attributed to the 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // best matches. 1655c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu for (Nodes::const_iterator i = sorted_nodes.begin(); 1665c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu i != sorted_nodes.end() && results->size() < max_count; 1675c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu ++i) 1685c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu AddMatchToResults(*i, &parser, query_nodes.get(), results); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::SortMatches(const Matches& matches, 1725c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu Nodes* sorted_nodes) const { 1735c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu NodeSet nodes; 1745c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu for (Matches::const_iterator i = matches.begin(); i != matches.end(); ++i) { 1755c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#if !defined(OS_ANDROID) 1765c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu nodes.insert(i->nodes_begin(), i->nodes_end()); 1775c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#else 1785c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // Work around a bug in the implementation of std::set::insert in the STL 1795c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu // used on android (http://crbug.com/367050). 1805c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu for (NodeSet::const_iterator n = i->nodes_begin(); n != i->nodes_end(); ++n) 1815c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu nodes.insert(nodes.end(), *n); 1825c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu#endif 1835c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu } 1845c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu sorted_nodes->reserve(sorted_nodes->size() + nodes.size()); 1855c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu if (client_->SupportsTypedCountForNodes()) { 1865c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu NodeTypedCountPairs node_typed_counts; 1875c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu client_->GetTypedCountForNodes(nodes, &node_typed_counts); 1885c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu std::sort(node_typed_counts.begin(), 1895c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu node_typed_counts.end(), 1905c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu NodeTypedCountPairSortFunctor()); 1915c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu std::transform(node_typed_counts.begin(), 1925c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu node_typed_counts.end(), 1935c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu std::back_inserter(*sorted_nodes), 1945c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu NodeTypedCountPairExtractNodeFunctor()); 1955c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu } else { 1965c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu sorted_nodes->insert(sorted_nodes->end(), nodes.begin(), nodes.end()); 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::AddMatchToResults( 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BookmarkNode* node, 2020529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::QueryParser* parser, 2030529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch const query_parser::QueryNodeStarVector& query_nodes, 2040529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch std::vector<BookmarkMatch>* results) { 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check that the result matches the query. The previous search 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // was a simple per-word search, while the more complex matching 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of QueryParser may filter it out. For example, the query 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ["thi"] will match the bookmark titled [Thinking], but since 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ["thi"] is quoted we don't want to do a prefix match. 2100529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::QueryWordVector title_words, url_words; 2110529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch const base::string16 lower_title = 2120529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch base::i18n::ToLower(Normalize(node->GetTitle())); 2130529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch parser->ExtractQueryWords(lower_title, &title_words); 2145c02ac1a9c1b504631c0a3d2b6e737b5d738bae1Bo Liu base::OffsetAdjuster::Adjustments adjustments; 2151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci parser->ExtractQueryWords( 2161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci CleanUpUrlForMatching(node->url(), languages_, &adjustments), 2171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci &url_words); 2180529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::Snippet::MatchPositions title_matches, url_matches; 2190529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch for (size_t i = 0; i < query_nodes.size(); ++i) { 2200529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch const bool has_title_matches = 2210529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_nodes[i]->HasMatchIn(title_words, &title_matches); 2221320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const bool has_url_matches = 2230529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_nodes[i]->HasMatchIn(url_words, &url_matches); 2240529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (!has_title_matches && !has_url_matches) 2250529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return; 2260529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::QueryParser::SortAndCoalesceMatchPositions(&title_matches); 2271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci query_parser::QueryParser::SortAndCoalesceMatchPositions(&url_matches); 2280529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 2290529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch BookmarkMatch match; 2300529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (lower_title.length() == node->GetTitle().length()) { 2310529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // Only use title matches if the lowercase string is the same length 2320529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // as the original string, otherwise the matches are meaningless. 2330529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // TODO(mpearson): revise match positions appropriately. 2340529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch match.title_match_positions.swap(title_matches); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2361320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // Now that we're done processing this entry, correct the offsets of the 2371320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // matches in |url_matches| so they point to offsets in the original URL 2381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci // spec, not the cleaned-up URL string that we used for matching. 2391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci std::vector<size_t> offsets = 2401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BookmarkMatch::OffsetsFromMatchPositions(url_matches); 2411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci base::OffsetAdjuster::UnadjustOffsets(adjustments, &offsets); 2421320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci url_matches = 2431320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci BookmarkMatch::ReplaceOffsetsInMatchPositions(url_matches, offsets); 2441320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci match.url_match_positions.swap(url_matches); 2450529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch match.node = node; 2460529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch results->push_back(match); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2490529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochbool BookmarkIndex::GetBookmarksMatchingTerm(const base::string16& term, 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool first_term, 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* matches) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Index::const_iterator i = index_.lower_bound(term); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i == index_.end()) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2560529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (!query_parser::QueryParser::IsWordLongEnoughForPrefixSearch(term)) { 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Term is too short for prefix match, compare using exact match. 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i->first != term) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; // No bookmarks with this term. 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_term) { 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Match match; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.terms.push_back(i); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches->push_back(match); 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CombineMatchesInPlace(i, matches); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (first_term) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is the first term and we're doing a prefix match. Loop through 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // index adding all entries that start with term to matches. 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (i != index_.end() && 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i->first.size() >= term.size() && 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) term.compare(0, term.size(), i->first, 0, term.size()) == 0) { 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Match match; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match.terms.push_back(i); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches->push_back(match); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Prefix match and not the first term. Loop through index combining 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // current matches in matches with term, placing result in result. 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches result; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (i != index_.end() && 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i->first.size() >= term.size() && 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) term.compare(0, term.size(), i->first, 0, term.size()) == 0) { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CombineMatches(i, *matches, &result); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches->swap(result); 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !matches->empty(); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::CombineMatchesInPlace(const Index::const_iterator& index_i, 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* matches) { 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < matches->size(); ) { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Match* match = &((*matches)[i]); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeSet intersection; 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set_intersection(match->nodes_begin(), match->nodes_end(), 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_i->second.begin(), index_i->second.end(), 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::inserter(intersection, intersection.begin())); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (intersection.empty()) { 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) matches->erase(matches->begin() + i); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match->terms.push_back(index_i); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match->nodes.swap(intersection); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BookmarkIndex::CombineMatches(const Index::const_iterator& index_i, 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Matches& current_matches, 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Matches* result) { 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < current_matches.size(); ++i) { 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Match& match = current_matches[i]; 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeSet intersection; 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::set_intersection(match.nodes_begin(), match.nodes_end(), 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_i->second.begin(), index_i->second.end(), 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::inserter(intersection, intersection.begin())); 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!intersection.empty()) { 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->push_back(Match()); 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Match& combined_match = result->back(); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) combined_match.terms = match.terms; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) combined_match.terms.push_back(index_i); 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) combined_match.nodes.swap(intersection); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)std::vector<base::string16> BookmarkIndex::ExtractQueryWords( 3325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const base::string16& query) { 3335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::vector<base::string16> terms; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (query.empty()) 3355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return std::vector<base::string16>(); 3360529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch query_parser::QueryParser parser; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) parser.ParseQueryWords(base::i18n::ToLower(query), &terms); 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return terms; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 341a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)void BookmarkIndex::RegisterNode(const base::string16& term, 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BookmarkNode* node) { 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_[term].insert(node); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 346a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)void BookmarkIndex::UnregisterNode(const base::string16& term, 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BookmarkNode* node) { 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Index::iterator i = index_.find(term); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i == index_.end()) { 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We can get here if the node has the same term more than once. For 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // example, a bookmark with the title 'foo foo' would end up here. 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i->second.erase(node); 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i->second.empty()) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_.erase(i); 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 35846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 35946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)} // namespace bookmarks 360