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