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_quick_provider.h"
6
7 #include <vector>
8
9 #include "base/basictypes.h"
10 #include "base/i18n/break_iterator.h"
11 #include "base/logging.h"
12 #include "base/metrics/histogram.h"
13 #include "base/string_number_conversions.h"
14 #include "base/string_util.h"
15 #include "base/time.h"
16 #include "base/utf_string_conversions.h"
17 #include "chrome/browser/history/history.h"
18 #include "chrome/browser/history/in_memory_url_index.h"
19 #include "chrome/browser/net/url_fixer_upper.h"
20 #include "chrome/browser/prefs/pref_service.h"
21 #include "chrome/browser/profiles/profile.h"
22 #include "chrome/common/pref_names.h"
23 #include "chrome/common/url_constants.h"
24 #include "googleurl/src/url_parse.h"
25 #include "content/common/notification_source.h"
26 #include "content/common/notification_type.h"
27 #include "googleurl/src/url_util.h"
28 #include "net/base/escape.h"
29 #include "net/base/net_util.h"
30
31 using history::InMemoryURLIndex;
32 using history::ScoredHistoryMatch;
33 using history::ScoredHistoryMatches;
34
HistoryQuickProvider(ACProviderListener * listener,Profile * profile)35 HistoryQuickProvider::HistoryQuickProvider(ACProviderListener* listener,
36 Profile* profile)
37 : HistoryProvider(listener, profile, "HistoryQuickProvider"),
38 languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)) {}
39
~HistoryQuickProvider()40 HistoryQuickProvider::~HistoryQuickProvider() {}
41
Start(const AutocompleteInput & input,bool minimal_changes)42 void HistoryQuickProvider::Start(const AutocompleteInput& input,
43 bool minimal_changes) {
44 matches_.clear();
45
46 if ((input.type() == AutocompleteInput::INVALID) ||
47 (input.type() == AutocompleteInput::FORCED_QUERY))
48 return;
49
50 autocomplete_input_ = input;
51
52 // Do some fixup on the user input before matching against it, so we provide
53 // good results for local file paths, input with spaces, etc.
54 // NOTE: This purposefully doesn't take input.desired_tld() into account; if
55 // it did, then holding "ctrl" would change all the results from the
56 // HistoryQuickProvider provider, not just the What You Typed Result.
57 const string16 fixed_text(FixupUserInput(input));
58 if (fixed_text.empty()) {
59 // Conceivably fixup could result in an empty string (although I don't
60 // have cases where this happens offhand). We can't do anything with
61 // empty input, so just bail; otherwise we'd crash later.
62 return;
63 }
64 autocomplete_input_.set_text(fixed_text);
65
66 // TODO(pkasting): We should just block here until this loads. Any time
67 // someone unloads the history backend, we'll get inconsistent inline
68 // autocomplete behavior here.
69 if (GetIndex()) {
70 base::TimeTicks start_time = base::TimeTicks::Now();
71 DoAutocomplete();
72 if (input.text().size() < 6) {
73 base::TimeTicks end_time = base::TimeTicks::Now();
74 std::string name = "HistoryQuickProvider.QueryIndexTime." +
75 base::IntToString(input.text().size());
76 base::Histogram* counter = base::Histogram::FactoryGet(
77 name, 1, 1000, 50, base::Histogram::kUmaTargetedHistogramFlag);
78 counter->Add(static_cast<int>((end_time - start_time).InMilliseconds()));
79 }
80 UpdateStarredStateOfMatches();
81 }
82 }
83
84 // HistoryQuickProvider matches are currently not deletable.
85 // TODO(mrossetti): Determine when a match should be deletable.
DeleteMatch(const AutocompleteMatch & match)86 void HistoryQuickProvider::DeleteMatch(const AutocompleteMatch& match) {}
87
DoAutocomplete()88 void HistoryQuickProvider::DoAutocomplete() {
89 // Get the matching URLs from the DB.
90 string16 term_string = autocomplete_input_.text();
91 term_string = UnescapeURLComponent(term_string,
92 UnescapeRule::SPACES | UnescapeRule::URL_SPECIAL_CHARS);
93 history::InMemoryURLIndex::String16Vector terms(
94 InMemoryURLIndex::WordVectorFromString16(term_string, false));
95 ScoredHistoryMatches matches = GetIndex()->HistoryItemsForTerms(terms);
96 if (matches.empty())
97 return;
98
99 // Artificially reduce the score of high-scoring results which should not be
100 // inline autocompletd. Each such result gets the next available
101 // |next_dont_inline_score|. Upon use of next_dont_inline_score it is
102 // decremented.
103 int next_dont_inline_score = 1199;
104 size_t match_num = matches.size() - 1;
105 for (ScoredHistoryMatches::const_iterator match_iter = matches.begin();
106 match_iter != matches.end(); ++match_iter, --match_num) {
107 const ScoredHistoryMatch& history_match(*match_iter);
108 if (history_match.raw_score > 0) {
109 AutocompleteMatch ac_match =
110 QuickMatchToACMatch(history_match, match_num,
111 autocomplete_input_.prevent_inline_autocomplete(),
112 &next_dont_inline_score);
113 matches_.push_back(ac_match);
114 }
115 }
116 }
117
QuickMatchToACMatch(const ScoredHistoryMatch & history_match,size_t match_number,bool prevent_inline_autocomplete,int * next_dont_inline_score)118 AutocompleteMatch HistoryQuickProvider::QuickMatchToACMatch(
119 const ScoredHistoryMatch& history_match,
120 size_t match_number,
121 bool prevent_inline_autocomplete,
122 int* next_dont_inline_score) {
123 DCHECK(next_dont_inline_score);
124 const history::URLRow& info = history_match.url_info;
125 int score = CalculateRelevance(history_match.raw_score,
126 autocomplete_input_.type(),
127 NORMAL, match_number);
128
129 // Discount a very high score when a) a match doesn't start at the beginning
130 // of the URL, or b) there are more than one substring matches in the URL, or
131 // c) the type of request does not allow inline autocompletion. This prevents
132 // the URL from being offered as an inline completion.
133 const int kMaxDontInlineScore = 1199;
134 if (score > kMaxDontInlineScore &&
135 (prevent_inline_autocomplete || history_match.url_matches.size() > 1 ||
136 history_match.url_matches[0].offset > 0)) {
137 score = std::min(*next_dont_inline_score, score);
138 --*next_dont_inline_score;
139 }
140
141 AutocompleteMatch match(this, score, !!info.visit_count(),
142 history_match.url_matches.empty() ?
143 AutocompleteMatch::HISTORY_URL :
144 AutocompleteMatch::HISTORY_TITLE);
145
146 match.destination_url = info.url();
147 DCHECK(match.destination_url.is_valid());
148
149 // Format the fill_into_edit and determine its offset.
150 size_t inline_autocomplete_offset =
151 history_match.input_location + autocomplete_input_.text().length();
152 match.fill_into_edit =
153 AutocompleteInput::FormattedStringWithEquivalentMeaning(info.url(),
154 net::FormatUrl(info.url(), languages_, net::kFormatUrlOmitAll,
155 UnescapeRule::SPACES, NULL, NULL, &inline_autocomplete_offset));
156 if (!autocomplete_input_.prevent_inline_autocomplete())
157 match.inline_autocomplete_offset = inline_autocomplete_offset;
158 DCHECK((match.inline_autocomplete_offset == string16::npos) ||
159 (match.inline_autocomplete_offset <= match.fill_into_edit.length()));
160
161 // Format the URL autocomplete presentation.
162 std::vector<size_t> offsets =
163 InMemoryURLIndex::OffsetsFromTermMatches(history_match.url_matches);
164 match.contents =
165 net::FormatUrlWithOffsets(info.url(), languages_, net::kFormatUrlOmitAll,
166 UnescapeRule::SPACES, NULL, NULL, &offsets);
167 history::TermMatches new_matches =
168 InMemoryURLIndex::ReplaceOffsetsInTermMatches(history_match.url_matches,
169 offsets);
170 match.contents_class = SpansFromTermMatch(new_matches, match.contents.size());
171
172 // Format the description autocomplete presentation.
173 match.description = info.title();
174 match.description_class = SpansFromTermMatch(history_match.title_matches,
175 match.description.size());
176
177 return match;
178 }
179
GetIndex()180 history::InMemoryURLIndex* HistoryQuickProvider::GetIndex() {
181 if (index_for_testing_.get())
182 return index_for_testing_.get();
183
184 HistoryService* const history_service =
185 profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
186 if (!history_service)
187 return NULL;
188
189 return history_service->InMemoryIndex();
190 }
191
SetIndexForTesting(history::InMemoryURLIndex * index)192 void HistoryQuickProvider::SetIndexForTesting(
193 history::InMemoryURLIndex* index) {
194 DCHECK(index);
195 index_for_testing_.reset(index);
196 }
197
198 // static
CalculateRelevance(int raw_score,AutocompleteInput::Type input_type,MatchType match_type,size_t match_number)199 int HistoryQuickProvider::CalculateRelevance(int raw_score,
200 AutocompleteInput::Type input_type,
201 MatchType match_type,
202 size_t match_number) {
203 switch (match_type) {
204 case INLINE_AUTOCOMPLETE:
205 return 1400;
206
207 case WHAT_YOU_TYPED:
208 return 1200;
209
210 default:
211 return raw_score;
212 }
213 }
214
215 // static
SpansFromTermMatch(const history::TermMatches & matches,size_t text_length)216 ACMatchClassifications HistoryQuickProvider::SpansFromTermMatch(
217 const history::TermMatches& matches,
218 size_t text_length) {
219 ACMatchClassifications spans;
220 if (matches.empty()) {
221 if (text_length)
222 spans.push_back(ACMatchClassification(0, ACMatchClassification::DIM));
223 return spans;
224 }
225 if (matches[0].offset)
226 spans.push_back(ACMatchClassification(0, ACMatchClassification::NONE));
227 size_t match_count = matches.size();
228 for (size_t i = 0; i < match_count;) {
229 size_t offset = matches[i].offset;
230 spans.push_back(ACMatchClassification(offset,
231 ACMatchClassification::MATCH));
232 // Skip all adjacent matches.
233 do {
234 offset += matches[i].length;
235 ++i;
236 } while ((i < match_count) && (offset == matches[i].offset));
237 if (offset < text_length) {
238 spans.push_back(ACMatchClassification(offset,
239 ACMatchClassification::NONE));
240 }
241 }
242
243 return spans;
244 }
245