Implement Bookmark Autocomplete Provider

chrome/browser/autocomplete/bookmark_provider.cc

+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/autocomplete/bookmark_provider.h"
+
+#include <algorithm>
+#include <functional>
+#include <vector>
+
+#include "base/metrics/histogram.h"
+#include "base/time.h"
+#include "chrome/browser/autocomplete/autocomplete_result.h"
+#include "chrome/browser/bookmarks/bookmark_model.h"
+#include "chrome/browser/bookmarks/bookmark_model_factory.h"
+#include "chrome/browser/prefs/pref_service.h"
+#include "chrome/browser/profiles/profile.h"
+#include "chrome/common/pref_names.h"
+#include "net/base/net_util.h"
+
+typedef std::vector<bookmark_utils::TitleMatch> TitleMatches;
+
+// BookmarkProvider ------------------------------------------------------------
+
+BookmarkProvider::BookmarkProvider(
+    AutocompleteProviderListener* listener,
+    Profile* profile)
+    : AutocompleteProvider(listener, profile,
+                           AutocompleteProvider::TYPE_BOOKMARK),
+      bookmark_model_(NULL) {
+  if (profile) {
+    bookmark_model_ = BookmarkModelFactory::GetForProfile(profile);
+    languages_ = profile_->GetPrefs()->GetString(prefs::kAcceptLanguages);
+  }
+}
+
+void BookmarkProvider::Start(const AutocompleteInput& input,
+                             bool minimal_changes) {
+  if (minimal_changes)
+    return;
+  matches_.clear();
+
+  // Short-circuit any matching when inline autocompletion is disabled because
+  // none of the BookmarkProvider's matches can score high enough to qualify.

[Peter Kasting, 2012/10/15 22:17:22]

Nit: This comment is not actually technically accurate -- you mean something
like "...when looking for BEST_MATCH and inline autocompletion is disabled..."

[mrossetti, 2012/10/16 16:38:05]

Ah, but of course.

+  if (input.text().empty() ||
+      ((input.type() != AutocompleteInput::UNKNOWN) &&
+       (input.type() != AutocompleteInput::REQUESTED_URL) &&
+       (input.type() != AutocompleteInput::QUERY)) ||
+      ((input.matches_requested() == AutocompleteInput::BEST_MATCH) &&
+       input.prevent_inline_autocomplete()))
+    return;
+
+  base::TimeTicks start_time = base::TimeTicks::Now();
+  DoAutocomplete(input,
+                 input.matches_requested() == AutocompleteInput::BEST_MATCH);
+  UMA_HISTOGRAM_TIMES("Autocomplete.BookmarkProviderMatchTime",
+                      base::TimeTicks::Now() - start_time);
+}
+
+BookmarkProvider::~BookmarkProvider() {}
+
+void BookmarkProvider::DoAutocomplete(const AutocompleteInput& input,
+                                      bool best_match) {
+  // We may not have a bookmark model for some unit tests.
+  if (!bookmark_model_)
+    return;
+
+  TitleMatches matches;
+  // Retrieve enough bookmarks so that we have a reasonable probability of
+  // suggesting the one that the user desires.
+  const size_t kMaxBookmarkMatches = 50;
+
+  // GetBookmarksWithTitlesMatching returns bookmarks matching the user's
+  // search terms using the following rules:
+  //  - The search text is broken up into search terms. Each term is searched
+  //    for separately.
+  //  - Term matches are always performed against the start of a word. 'def'
+  //    will match against 'define' but not against 'indefinite'.
+  //  - Terms must be at least three characters in length in order to perform
+  //    partial word matches. Any term of lesser length will only be used as an
+  //    exact match. 'def' will match against 'define' but 'de' will not match.
+  //  - A search containing multiple terms will return results with those words
+  //    occuring in any order.
+  //  - Terms enclosed in quotes comprises a phrase that must match exactly.
+  //  - Multiple terms enclosed in quotes will require those exact words in that
+  //    exact order to match.
+  //
+  // Note: GetBookmarksWithTitlesMatching() will never return a match span
+  // greater than the length of the title against which it is being matched,
+  // nor can those spans ever overlap because the match spans are coalesced
+  // for all matched terms.
+  //
+  // Please refer to the code for BookmarkIndex::GetBookmarksWithTitlesMatching
+  // for complete details of how title searches are performed against the user's
+  // bookmarks.
+  bookmark_model_->GetBookmarksWithTitlesMatching(input.text(),
+                                                  kMaxBookmarkMatches,
+                                                  &matches);
+  if (matches.empty())
+    return;  // There were no matches.
+  for (TitleMatches::const_iterator i = matches.begin(); i != matches.end();
+       ++i) {
+    AutocompleteMatch match(TitleMatchToACMatch(*i));
+    if (match.relevance > 0)
+      matches_.push_back(match);
+  }
+
+  // Sort and clip the resulting matches.
+  size_t max_matches = best_match ? 1 : AutocompleteProvider::kMaxMatches;
+  if (matches_.size() > max_matches) {
+    std::partial_sort(matches_.begin(), matches_.end(),
+                      matches_.begin() + max_matches,
+                      AutocompleteMatch::MoreRelevant);
+    matches_.resize(max_matches);
+  } else {
+    std::sort(matches_.begin(), matches_.end(),
+              AutocompleteMatch::MoreRelevant);
+  }
+}
+
+namespace {
+
+// for_each helper functor that calculates a match factor for each query term
+// when calculating the final score.
+//
+// Calculate a 'factor' from 0.0 to 1.0 based on 1) how much of the bookmark's
+// title the term matches, and 2) where the match is positioned within the
+// bookmark's title. A full length match earns a 1.0. A half-length match earns
+// at most a 0.5 and at least a 0.25. A single character match against a title
+// that is 100 characters long where the match is at the first character will
+// earn a 0.01 and at the last character will earn a 0.0001.
+class ScoringFunctor {
+ public:
+  // |title_length| is the length of the bookmark title against which this
+  // match will be scored.
+  explicit ScoringFunctor(size_t title_length)
+      : title_length_(static_cast<double>(title_length)),
+        scoring_factor_(0.0) {
+  }
+
+  void operator()(const Snippet::MatchPosition& match) {
+    double term_length = static_cast<double>(match.second - match.first);
+    scoring_factor_ += term_length / title_length_ *
+        (title_length_ - match.first) / title_length_;
+  }
+
+  double ScoringFactor() { return scoring_factor_; }
+
+ private:
+  double title_length_;
+  double scoring_factor_;
+};
+
+}  // namespace
+
+AutocompleteMatch BookmarkProvider::TitleMatchToACMatch(
+    const bookmark_utils::TitleMatch& title_match) {
+  // Compose a match that has 1) the URL of the bookmark, and 2) the bookmark's
+  // title, not the URL's page title, as the description. The match will be
+  // discarded if its relevance is never increased from 0. We always pass false
+  // for the |deletable| parameter in the following constructor to indicate
+  // that the AutocompleteMatch we construct is non-deletable because the only

[Peter Kasting, 2012/10/15 22:17:22]

Nit: For clarity, I'd remove everything in this sentence before the words
"...the AutocompleteMatch we construct...".

[mrossetti, 2012/10/16 16:38:05]

Sounds good.

+  // way to support this would be to delete the underlying bookmark, which is
+  // unlikely to be what the user intends.
+  AutocompleteMatch match(this, 0, false, AutocompleteMatch::BOOKMARK_TITLE);
+  const string16& title(title_match.node->GetTitle());
+  DCHECK(!title.empty());
+  const GURL& url(title_match.node->url());
+  match.destination_url = url;
+  match.contents = net::FormatUrl(url, languages_,
+      net::kFormatUrlOmitAll & net::kFormatUrlOmitHTTP,
+      net::UnescapeRule::SPACES, NULL, NULL, NULL);
+  match.contents_class.push_back(
+      ACMatchClassification(0, ACMatchClassification::NONE));
+  match.fill_into_edit =
+      AutocompleteInput::FormattedStringWithEquivalentMeaning(url,
+                                                              match.contents);
+  match.description = title;
+  match.description_class =
+      ClassificationsFromMatch(title_match.match_positions,
+                               match.description.size());
+  match.starred = true;
+
+  // Summary on how a relevance score is determined for the match:
+  //
+  // For each term matching within the bookmark's title (as given by the set of
+  // Snippet::MatchPositions) calculate a 'factor', sum up those factors, then
+  // use the sum to figure out a value between the base score and the maximum
+  // score.
+  //
+  // The factor for each term is calculated based on:
+  //
+  //  1) how much of the bookmark's title has been matched by the term:
+  //       (term length / title length).
+  //
+  //  Example: Given a bookmark title of 'abcde fghijklm' and two different
+  //     search terms, 'abcde' and 'fghijklm', 'fghijklm' will score higher
+  //     (with a partial factor of 8/14 = 0.571) than 'abcde' (5/14 = 0.357).
+  //
+  //  2) where the term match occurs within the bookmark's title, giving more
+  //     points for matches that appear earlier in the title:
+  //       ((title length - position of match start) / title_length).
+  //
+  //  Example: Given a bookmark title of 'abcde fghijklm' and two different
+  //     search terms, 'abcde' and 'fghij', 'abcde' will score higher (with a
+  //     match start position of 0 giving a partial factor of
+  //     (14-0)/14 = 1.000 ) than 'fghij' (with a match start position of 6
+  //     giving (14-6)/14 = 0.571 ).
+  //
+  // Once all term factors have been calculated they are summed. The resulting
+  // sum will never be greater than 1.0. This sum is then multiplied against
+  // the scoring range available, which is 299. The 299 is calculated by
+  // subtracting the minimum possible score, 900, from the maximum possible
+  // score, 1199. This product, ranging from 0 to 299, is added to the minimum
+  // possible score, 900, giving the preliminary score.
+  //
+  // If the preliminary score is less than the maximum possible score, 1199,
+  // it can be boosted if the URL referenced by the bookmark is also referenced
+  // by any of the user's other bookmarks. A count of how many times the
+  // bookmark's URL is referenced is determined and for each additional
+  // reference beyond the one for the bookmark being scored up to a maximum
+  // of three, the score is boosted by a fixed amount given by |kURLCountBoost|,
+  // below. As it is possible for this boost to cause the score to exceed the
+  // maximum possible score, the score is capped to that maximum possible.
+  //
+  ScoringFunctor position_functor =
+      for_each(title_match.match_positions.begin(),
+               title_match.match_positions.end(), ScoringFunctor(title.size()));
+  const int kBaseBookmarkScore = 900;
+  const int kMaxBookmarkScore = AutocompleteResult::kLowestDefaultScore - 1;
+  const double kBookmarkScoreRange =
+      static_cast<double>(kMaxBookmarkScore - kBaseBookmarkScore);
+  // It's not likely that GetBookmarksWithTitlesMatching will return overlapping
+  // matches but let's play it safe.
+  match.relevance = std::min(kMaxBookmarkScore,
+      static_cast<int>(position_functor.ScoringFactor() * kBookmarkScoreRange) +
+      kBaseBookmarkScore);
+  // Don't waste any time searching for additional referenced URLs if we
+  // already have a perfect title match.
+  if (match.relevance >= kMaxBookmarkScore)
+    return match;
+  // Boost the score if the bookmark's URL is referenced by other bookmarks.
+  const int kURLCountBoost[4] = { 0, 75, 125, 150 };
+  std::vector<const BookmarkNode*> nodes;
+  bookmark_model_->GetNodesByURL(url, &nodes);
+  DCHECK_GE(std::min(arraysize(kURLCountBoost), nodes.size()), 1U);
+  match.relevance +=
+      kURLCountBoost[std::min(arraysize(kURLCountBoost), nodes.size()) - 1];
+  match.relevance = std::min(kMaxBookmarkScore, match.relevance);
+  return match;
+}
+
+// static
+ACMatchClassifications BookmarkProvider::ClassificationsFromMatch(
+    const Snippet::MatchPositions& positions,
+    size_t text_length) {
+  ACMatchClassifications classifications;
+  if (positions.empty()) {
+    classifications.push_back(
+        ACMatchClassification(0, ACMatchClassification::NONE));
+    return classifications;
+  }
+
+  for (Snippet::MatchPositions::const_iterator i = positions.begin();
+       i != positions.end(); ++i) {
+    AutocompleteMatch::ACMatchClassifications new_class;
+    AutocompleteMatch::ClassifyLocationInString(i->first, i->second - i->first,
+        text_length, 0, &new_class);
+    classifications = AutocompleteMatch::MergeClassifications(
+        classifications, new_class);
+  }
+  return classifications;
+}