Home | History | Annotate | Download | only in autocomplete 
      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 
     35 HistoryQuickProvider::HistoryQuickProvider(ACProviderListener* listener,
     36                                            Profile* profile)
     37     : HistoryProvider(listener, profile, "HistoryQuickProvider"),
     38       languages_(profile_->GetPrefs()->GetString(prefs::kAcceptLanguages)) {}
     39 
     40 HistoryQuickProvider::~HistoryQuickProvider() {}
     41 
     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.
     86 void HistoryQuickProvider::DeleteMatch(const AutocompleteMatch& match) {}
     87 
     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 
    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 
    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 
    192 void HistoryQuickProvider::SetIndexForTesting(
    193     history::InMemoryURLIndex* index) {
    194   DCHECK(index);
    195   index_for_testing_.reset(index);
    196 }
    197 
    198 // static
    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
    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