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 "base/utf_string_conversions.h"

[Mark P, 2012/10/08 22:51:59]

What do you need this for?

[mrossetti, 2012/10/10 02:26:42]

Don't. Removed.

On 2012/10/08 22:51:59, Mark P wrote:

+#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();
+
+  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
+  // retrieving 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 words. Each word is searched for
+  //    separately. In the following I use the 'term' to refer to a search word.

[Mark P, 2012/10/08 22:51:59]

Perhaps replace this bullet with
- The search text is broken up into search terms.

[mrossetti, 2012/10/10 02:26:42]

Done.

+  //  - 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 will be used as exact matches.
+  //  - Multiple terms enclosed in quotes will require those exact words in that
+  //    exact order to match.

[Mark P, 2012/10/08 22:51:59]

with no intervening words
(I assume)

[mrossetti, 2012/10/10 02:26:42]

Yes.

On 2012/10/08 22:51:59, Mark P wrote:

+  //  - There are no wildcards.

[Mark P, 2012/10/08 22:51:59]

Consider dropping this bullet.

[mrossetti, 2012/10/10 02:26:42]

Done.

+  // Please refer to the code for BookmarkIndex::GetBookmarksWithTitlesMatching
+  // in order to gain a good understanding of how title searches are performed

[Mark P, 2012/10/08 22:51:59]

gain a good understanding of
->
understand
or perhaps
learn

[mrossetti, 2012/10/10 02:26:42]

Reworded.

On 2012/10/08 22:51:59, Mark P wrote:

+  // 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 used to 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.
+  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 the URL of the bookmar and the bookmark's title,

[Mark P, 2012/10/08 22:51:59]

bookmark

[mrossetti, 2012/10/10 02:26:42]

Oops.

On 2012/10/08 22:51:59, Mark P wrote:

+  // not the URL's page title, as the description. Note that if the relevance
+  // is never changed from 0 that the match will be discarded.
+  AutocompleteMatch match(this, 0, false, AutocompleteMatch::BOOKMARK_TITLE);

[Mark P, 2012/10/08 22:51:59]

Perhaps I wasn't clear.  Please add a comment here that you pass false to make
the item not deletable because you don't want to let user delete a bookmark by
deleting the autocomplete entry (and you don't want to add a class of bookmarks
that cannot be searched).

[mrossetti, 2012/10/10 02:26:42]

I've added some comments. Please note that deletable really means that the
source of the suggestion, the bookmark in this case, can or cannot be deleted.
When a history item suggestion is deleted that underlying history record is
deleted from the HUP and/or HQP.

On 2012/10/08 22:51:59, Mark P wrote:

+  const string16& title(title_match.node->GetTitle());
+  if (title.empty())

[Mark P, 2012/10/08 22:51:59]

How can this happen?

[mrossetti, 2012/10/10 02:26:42]

It probably cannot happen. I'll change it to a DCHECK.

On 2012/10/08 22:51:59, Mark P wrote:

+    return match;
+  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;
+
+  // Calculate the relevance based on:
+  //  1) how much of the bookmark's title has been matched by the input text,
+  //  2) where the matches occurs within the bookmark's title, and
+  //  2) how many times the bookmark's URL is referenced by other bookmarks.

[Mark P, 2012/10/08 22:51:59]

3)

[mrossetti, 2012/10/10 02:26:42]

I'm glad one of us can count!

On 2012/10/08 22:51:59, Mark P wrote:

+  // For each match calculate a 'factor' (see ScoringFunctor for details on
+  // how the factor is calculated), sum up those factors, then use the sum to
+  // figure out a score between the base and the maximum.
+  ScoringFunctor position_functor =
+      for_each(title_match.match_positions.begin(),
+               title_match.match_positions.end(), ScoringFunctor(title.size()));

[Mark P, 2012/10/08 22:51:59]

Can you please comment here or elsewhere what will match_position look like for
an omnibox input
foobar foobar
for input foobar foobar foo?  I'm trying to figure out what score this will get
(e.g., could it get something >1.0, which it sounds like you might be worried
about--see lines 189-190.)

A good comment will also help explain in general how match_position looks when
the omnibox input is multiple terms.  This will help a reader estimate the value
of the factor you calculate.

[mrossetti, 2012/10/10 02:26:42]

I don't think I'll add any consideration for repeated search terms. The case of
a search query of "foobar foobar" will be equivalent to a search query of
"foobar" and both will have the same score when thrown against "foobar foobar
foo". This means that a query of "foobar foobar" will match against a bookmark
with a single instance of the word "foobar". If this causes the user any
consternation then we could certainly add logic that would require two separate
instances of 'foobar' to occur in the bookmark name but I'm not anxious to add
that logic unless necessary. (Note that a quoted query of "\"foobar foobar\""
_will_ require both words.)
 
I'll add some comments, but comments, even good ones, do not substitute for a
serious reading of the code.

A relevant comment on ACMatchClassification being compressed and combined was
added just above the call to GetBookmarksWithTitlesMatching in
BookmarkProvider::DoAutocomplete.

+  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);
+  match.relevance +=
+      kURLCountBoost[std::min(arraysize(kURLCountBoost), nodes.size()) - 1];

[Mark P, 2012/10/08 22:51:59]

Do you want a max(, 0) in there as a precaution, or do you trust the bookmark
model will always still exist and be able to re-find your URL (and hence the
count will always be at least 1)?

[mrossetti, 2012/10/10 02:26:42]

I'm sure we can trust that there will always be at least 1 bookmark with the
given URL, but I'll add a DCHECK just to be safe.

On 2012/10/08 22:51:59, Mark P wrote:

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