1// Copyright (c) 2011 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/autocomplete/history_contents_provider.h"
6
7#include "base/callback.h"
8#include "base/metrics/histogram.h"
9#include "base/string_util.h"
10#include "base/utf_string_conversions.h"
11#include "chrome/browser/autocomplete/autocomplete_match.h"
12#include "chrome/browser/bookmarks/bookmark_model.h"
13#include "chrome/browser/bookmarks/bookmark_utils.h"
14#include "chrome/browser/history/query_parser.h"
15#include "chrome/browser/profiles/profile.h"
16#include "chrome/common/url_constants.h"
17#include "googleurl/src/url_util.h"
18#include "net/base/net_util.h"
19
20using base::TimeTicks;
21
22namespace {
23
24// Number of days to search for full text results. The longer this is, the more
25// time it will take.
26const int kDaysToSearch = 30;
27
28// When processing the results from the history query, this structure points to
29// a single result. It allows the results to be sorted and processed without
30// modifying the larger and slower results structure.
31struct MatchReference {
32  MatchReference(const history::URLResult* result, int relevance)
33      : result(result),
34        relevance(relevance) {
35  }
36
37  const history::URLResult* result;
38  int relevance;  // Score of relevance computed by CalculateRelevance.
39};
40
41// This is a > operator for MatchReference.
42bool CompareMatchRelevance(const MatchReference& a, const MatchReference& b) {
43  if (a.relevance != b.relevance)
44    return a.relevance > b.relevance;
45
46  // Want results in reverse-chronological order all else being equal.
47  return a.result->last_visit() > b.result->last_visit();
48}
49
50}  // namespace
51
52using history::HistoryDatabase;
53
54HistoryContentsProvider::HistoryContentsProvider(ACProviderListener* listener,
55                                                 Profile* profile)
56    : HistoryProvider(listener, profile, "HistoryContents"),
57      star_title_count_(0),
58      star_contents_count_(0),
59      title_count_(0),
60      contents_count_(0),
61      input_type_(AutocompleteInput::INVALID),
62      trim_http_(false),
63      have_results_(false) {
64}
65
66void HistoryContentsProvider::Start(const AutocompleteInput& input,
67                                    bool minimal_changes) {
68  matches_.clear();
69
70  if (input.text().empty() || (input.type() == AutocompleteInput::INVALID) ||
71      !profile_ ||
72      // The history service or bookmark bar model must exist.
73      !(profile_->GetHistoryService(Profile::EXPLICIT_ACCESS) ||
74        profile_->GetBookmarkModel())) {
75    Stop();
76    return;
77  }
78
79  // TODO(pkasting): http://b/888148 We disallow URL input and "URL-like" input
80  // (REQUESTED_URL or UNKNOWN with dots) because we get poor results for it,
81  // but we could get better results if we did better tokenizing instead.
82  if ((input.type() == AutocompleteInput::URL) ||
83      (((input.type() == AutocompleteInput::REQUESTED_URL) ||
84        (input.type() == AutocompleteInput::UNKNOWN)) &&
85       (input.text().find('.') != string16::npos))) {
86    Stop();
87    return;
88  }
89
90  if (input.matches_requested() == AutocompleteInput::BEST_MATCH) {
91    // None of our results are applicable for best match.
92    Stop();
93    return;
94  }
95
96  // Change input type so matches will be marked up properly.
97  input_type_ = input.type();
98  trim_http_ = !HasHTTPScheme(input.text());
99
100  // Decide what to do about any previous query/results.
101  if (!minimal_changes) {
102    // Any in-progress request is irrelevant, cancel it.
103    Stop();
104  } else if (have_results_) {
105    // We finished the previous query and still have its results.  Mark them up
106    // again for the new input.
107    ConvertResults();
108    return;
109  } else if (!done_) {
110    // We're still running the previous query on the HistoryService.  If we're
111    // allowed to keep running it, do so, and when it finishes, its results will
112    // get marked up for this new input.  In synchronous_only mode, cancel the
113    // history query.
114    if (input.matches_requested() != AutocompleteInput::ALL_MATCHES) {
115      done_ = true;
116      request_consumer_.CancelAllRequests();
117    }
118    ConvertResults();
119    return;
120  }
121
122  if (!results_.empty()) {
123    // Clear the results. We swap in an empty one as the easy way to clear it.
124    history::QueryResults empty_results;
125    results_.Swap(&empty_results);
126  }
127
128  // Querying bookmarks is synchronous, so we always do it.
129  QueryBookmarks(input);
130
131  // Convert the bookmark results.
132  ConvertResults();
133
134  if (input.matches_requested() == AutocompleteInput::ALL_MATCHES) {
135    HistoryService* history =
136        profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
137    if (history) {
138      done_ = false;
139
140      history::QueryOptions options;
141      options.SetRecentDayRange(kDaysToSearch);
142      options.max_count = kMaxMatches;
143      history->QueryHistory(input.text(), options,
144          &request_consumer_,
145          NewCallback(this, &HistoryContentsProvider::QueryComplete));
146    }
147  }
148}
149
150void HistoryContentsProvider::Stop() {
151  done_ = true;
152  request_consumer_.CancelAllRequests();
153
154  // Clear the results. We swap in an empty one as the easy way to clear it.
155  history::QueryResults empty_results;
156  results_.Swap(&empty_results);
157  have_results_ = false;
158}
159
160HistoryContentsProvider::~HistoryContentsProvider() {
161}
162
163void HistoryContentsProvider::QueryComplete(HistoryService::Handle handle,
164                                            history::QueryResults* results) {
165  results_.AppendResultsBySwapping(results, true);
166  have_results_ = true;
167  ConvertResults();
168
169  done_ = true;
170  if (listener_)
171    listener_->OnProviderUpdate(!matches_.empty());
172}
173
174void HistoryContentsProvider::ConvertResults() {
175  // Reset the relevance counters so that result relevance won't vary on
176  // subsequent passes of ConvertResults.
177  star_title_count_ = star_contents_count_ = title_count_ = contents_count_ = 0;
178
179  // Make the result references and score the results.
180  std::vector<MatchReference> result_refs;
181  result_refs.reserve(results_.size());
182
183  // Results are sorted in decreasing order so we run the loop backwards so that
184  // the relevance increment favors the higher ranked results.
185  for (std::vector<history::URLResult*>::const_reverse_iterator i =
186       results_.rbegin(); i != results_.rend(); ++i) {
187    history::URLResult* result = *i;
188    MatchReference ref(result, CalculateRelevance(*result));
189    result_refs.push_back(ref);
190  }
191
192  // Get the top matches and add them.
193  size_t max_for_provider = std::min(kMaxMatches, result_refs.size());
194  std::partial_sort(result_refs.begin(), result_refs.begin() + max_for_provider,
195                    result_refs.end(), &CompareMatchRelevance);
196  matches_.clear();
197  for (size_t i = 0; i < max_for_provider; i++) {
198    matches_.push_back(ResultToMatch(*result_refs[i].result,
199                                     result_refs[i].relevance));
200  }
201}
202
203static bool MatchInTitle(const history::URLResult& result) {
204  return !result.title_match_positions().empty();
205}
206
207AutocompleteMatch HistoryContentsProvider::ResultToMatch(
208    const history::URLResult& result,
209    int score) {
210  // TODO(sky): if matched title highlight matching words in title.
211  // Also show star in popup.
212  AutocompleteMatch match(this, score, true, MatchInTitle(result) ?
213      AutocompleteMatch::HISTORY_TITLE : AutocompleteMatch::HISTORY_BODY);
214  match.contents = StringForURLDisplay(result.url(), true, trim_http_);
215  match.fill_into_edit =
216      AutocompleteInput::FormattedStringWithEquivalentMeaning(result.url(),
217                                                              match.contents);
218  match.destination_url = result.url();
219  match.contents_class.push_back(
220      ACMatchClassification(0, ACMatchClassification::URL));
221  match.description = result.title();
222  match.starred =
223      (profile_->GetBookmarkModel() &&
224       profile_->GetBookmarkModel()->IsBookmarked(result.url()));
225
226  ClassifyDescription(result, &match);
227  return match;
228}
229
230void HistoryContentsProvider::ClassifyDescription(
231    const history::URLResult& result,
232    AutocompleteMatch* match) const {
233  const Snippet::MatchPositions& title_matches = result.title_match_positions();
234
235  size_t offset = 0;
236  if (!title_matches.empty()) {
237    // Classify matches in the title.
238    for (Snippet::MatchPositions::const_iterator i = title_matches.begin();
239         i != title_matches.end(); ++i) {
240      if (i->first != offset) {
241        match->description_class.push_back(
242            ACMatchClassification(offset, ACMatchClassification::NONE));
243      }
244      match->description_class.push_back(
245            ACMatchClassification(i->first, ACMatchClassification::MATCH));
246      offset = i->second;
247    }
248  }
249  if (offset != result.title().size()) {
250    match->description_class.push_back(
251        ACMatchClassification(offset, ACMatchClassification::NONE));
252  }
253}
254
255int HistoryContentsProvider::CalculateRelevance(
256    const history::URLResult& result) {
257  const bool in_title = MatchInTitle(result);
258  if (!profile_->GetBookmarkModel() ||
259      !profile_->GetBookmarkModel()->IsBookmarked(result.url()))
260    return in_title ? (700 + title_count_++) : (500 + contents_count_++);
261  return in_title ?
262      (1000 + star_title_count_++) : (550 + star_contents_count_++);
263}
264
265void HistoryContentsProvider::QueryBookmarks(const AutocompleteInput& input) {
266  BookmarkModel* bookmark_model = profile_->GetBookmarkModel();
267  if (!bookmark_model)
268    return;
269
270  DCHECK(results_.empty());
271
272  TimeTicks start_time = TimeTicks::Now();
273  std::vector<bookmark_utils::TitleMatch> matches;
274  bookmark_model->GetBookmarksWithTitlesMatching(input.text(),
275                                                 kMaxMatches, &matches);
276  for (size_t i = 0; i < matches.size(); ++i)
277    AddBookmarkTitleMatchToResults(matches[i]);
278  UMA_HISTOGRAM_TIMES("Omnibox.QueryBookmarksTime",
279                      TimeTicks::Now() - start_time);
280}
281
282void HistoryContentsProvider::AddBookmarkTitleMatchToResults(
283    const bookmark_utils::TitleMatch& match) {
284  history::URLResult url_result(match.node->GetURL(), match.match_positions);
285  url_result.set_title(match.node->GetTitle());
286  results_.AppendURLBySwapping(&url_result);
287}
288