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 and
+  // we're looking for BEST_MATCH because none of the BookmarkProvider's
+  // matches can score high enough to qualify.
+  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(

[Mark P, 2012/10/18 18:37:54]

I found this comment that you deleted useful: Note that if the relevance is
never changed from 0 that the match will be discarded.

Please restore it somewhere.

[mrossetti, 2012/10/19 17:33:07]

I moved part of the original comment you liked to the header where
TitleMatchToACMatch() is declared and another part to where
TitleMatchToACMatch() is called in DoAutocomplete().

+    const bookmark_utils::TitleMatch& title_match) {
+  // The AutocompleteMatch we construct is non-deletable because the only
+  // 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 'abcde fghijklm', with a title length
+  //     of 14, and two different search terms, 'abcde' and 'fghijklm', with
+  //     term lengths of 5 and 8, respectively, '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', with a title length
+  //     of 14, and two different search terms, 'abcde' and 'fghij', with
+  //     start positions of 0 and 6, respectively, 'abcde' will score higher
+  //     (with a a partial factor of (14-0)/14 = 1.000 ) than 'fghij' (with
+  //     a partial factor of (14-6)/14 = 0.571 ).
+  //
+  // Once all term factors have been calculated they are summed. The resulting

[Mark P, 2012/10/18 18:37:54]

This first sentence isn't true.  You multiple the factors, then sum those
products over all matches.

[mrossetti, 2012/10/19 17:33:07]

Please take a look at ScoringFunctor::operator() above, specifically line
144-145:

144     scoring_factor_ += term_length / title_length_ *
145         (title_length_ - match.first) / title_length_;
 
the "+=" is doing the summing.

A factor is calculated for each _term_ in the query. Those factors are summed.

We're running into an inadequate lexicon I believe.  It's easy to mix up 'term',
'word', 'match', 'result', etc.

[Mark P, 2012/10/19 17:50:44]

Ah, I see why I thought your comment was misleading.  I read the above list (1 &
2) as a list of factors, then when I saw this sentence "Once all term factors
have been calculated they are summed." I said "oh no, they're multiplied first,
then summed."

Perhaps change line 188 from
The factor for each term is calculated based on:
to
The factor for each term is the product of:

+  // sum will never be greater than 1.0. This sum is then multiplied against

[Mark P, 2012/10/18 18:37:54]

Why will it never be greater than 1.0?

I think it has to do with how duplicates/overlaps are eliminated in
GetBookmarksWithTitlesMatching(), but it would help to claim that directly if
that's what you're relying in.

And if indeed it's true, please DCHECK it.

[mrossetti, 2012/10/19 17:33:07]

The math is pure. It can never be greater than 1.0 other than the potential for
a very minor fractional rounding error that might make it 1.0+epsilon. Even with
that very slight difference the resulting partial score will always be clamped
to the maximum possible of 299.

[Mark P, 2012/10/19 17:50:44]

Consider the title "food" and omnibox input "foo ood".  If term matches ends up
with a three character match foo and a three character match ood, then your
factors will be
3/4 * 1
3/4 * 3/4
The sum of these is 1.3125 > 1.0.

The only way the match works out ("is pure") is the bookmarks search never
reports overlapping matching.  If this is true, you should assert it in comments
and claim that the math works out precisely for this reason.

Regardless, I think a DCHECK is appropriate. (Even if it's true, the DCHECK may
help prevent regressions in how the bookmark search works.)

+  // 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

[Mark P, 2012/10/18 18:37:54]

boosted if
->
boosted up to the maximum possible score if

If you make this change, drop the last sentence of the paragraph.

[mrossetti, 2012/10/19 17:33:07]

Done.

+  // 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;
+}