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 <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)
+    languages_ = profile_->GetPrefs()->GetString(prefs::kAcceptLanguages);
+}
+
+void BookmarkProvider::Start(const AutocompleteInput& input,
+                             bool minimal_changes) {
+  matches_.clear();

[Peter Kasting, 2012/10/04 20:40:31]

Seems like if |minimal_changes| is true we can just return immediately before
clearing this, no?

[mrossetti, 2012/10/05 22:10:04]

Ah! Excellent point.

+
+  // Only bother with UNKNOWN and QUERY.

[Peter Kasting, 2012/10/04 20:40:31]

What about REQUESTED_URL?  That's similar to UNKNOWN...

[mrossetti, 2012/10/05 22:10:04]

Done.

+  if ((input.type() != AutocompleteInput::UNKNOWN) &&
+      (input.type() != AutocompleteInput::QUERY))
+    return;
+
+  base::TimeTicks start_time = base::TimeTicks::Now();
+  DoAutocomplete(input,
+                 input.matches_requested() == AutocompleteInput::BEST_MATCH);

[Peter Kasting, 2012/10/04 20:40:31]

We should probably bail if BEST_MATCH and input.prevent_inline_autocomplete(),
the way the HQP does.

[mrossetti, 2012/10/05 22:10:04]

Done.

+  UMA_HISTOGRAM_TIMES("Autocomplete.BookmarkProviderMatchTime",
+                      base::TimeTicks::Now() - start_time);
+}
+
+BookmarkProvider::~BookmarkProvider() {}
+
+
+void BookmarkProvider::DoAutocomplete(const AutocompleteInput& input,
+                                      bool best_match) {
+  if (!bookmark_model_) {

[Peter Kasting, 2012/10/04 20:40:31]

Does setting this lazily here speed up startup?  If so, document that.  If not,
just do this in the constructor.

[mrossetti, 2012/10/05 22:10:04]

Done. (Premature optimization!)

+    // We may not have a profile or bookmark model for some unit tests.
+    if (!profile_)
+      return;
+    bookmark_model_ = BookmarkModelFactory::GetForProfile(profile_);
+    if (!bookmark_model_)
+      return;
+  }
+
+  TitleMatches matches;
+  // Retrieve enough bookmarks so that we can reasonably score the best.
+  const size_t kMaxBookmarkMatches = 50;
+  bookmark_model_->GetBookmarksWithTitlesMatching(input.text(),

[Peter Kasting, 2012/10/04 20:40:31]

Does this match only exact prefixes, or is it smarter than that?  The comments
on its declaration don't say, and this file doesn't really have any comments
about how the overall matching/sorting/scoring pipeline works.

[mrossetti, 2012/10/05 22:10:04]

Yes, you are correct. The BookmarkIndex::GetBookmarksWithTitlesMatching behavior
is not very well documented and has been a learning process. I will elaborate
here as I rework the scoring with mpearson's input.

+                                                  kMaxBookmarkMatches,
+                                                  &matches);
+  if (!matches.size())
+    return;  // There were no matches.
+
+  for (TitleMatches::const_iterator i = matches.begin(); i != matches.end();
+       ++i)
+    matches_.push_back(TitleMatchToACMatch(*i));
+
+  // 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 function that accumulates match term lengths and calculates
+// position disorders.
+class PositionFunctor {
+ public:
+  PositionFunctor() : length_(0), disorders_(0), last_pos_(0) {}
+  void operator() (const Snippet::MatchPosition& match) {
+    length_ += match.second - match.first;
+    if (last_pos_ >= match.second)
+      ++disorders_;
+  }
+  size_t TotalLength() { return length_; }
+  int TotalDisorders() { return disorders_; }
+
+ private:
+  long length_;
+  int disorders_;
+  size_t last_pos_;
+};
+
+}  // namespace
+
+AutocompleteMatch BookmarkProvider::TitleMatchToACMatch(

[Peter Kasting, 2012/10/04 20:40:31]

Nit: This function could really use a description of how, in general, it matches
and scores.

[mrossetti, 2012/10/05 22:10:04]

Forthcoming as I rework the scoring.

+    const bookmark_utils::TitleMatch& title_match) {
+  // Calculate the relevance.
+  // TODO(mpearson): Fix this very, very simplistic scoring method.
+  // Base score = 900. Add 100 for first match, 75 for next, 50, 25, 0.
+  const int kMatchCountBoost[4] = { 100, 175, 225, 250 };
+  size_t position_count =
+      std::min<size_t>(4, title_match.match_positions.size());
+  int relevance = 900 + kMatchCountBoost[position_count];
+  // Add 1199 - score * total match length / title length
+  PositionFunctor position_functor =
+      for_each(title_match.match_positions.begin(),
+               title_match.match_positions.end(), PositionFunctor());
+  int adjuster = ((AutocompleteResult::kLowestDefaultScore - relevance - 1) *
+                  static_cast<int>(position_functor.TotalLength())) /
+                  static_cast<int>(title_match.node->GetTitle().size());
+  relevance += adjuster;
+  // Subtract 50 for each out-of-order match.
+  relevance -= 50 * position_functor.TotalDisorders();
+
+  AutocompleteMatch match(this, relevance, false,
+                          AutocompleteMatch::BOOKMARK_TITLE);
+  const BookmarkNode& node(*(title_match.node));
+  match.destination_url = node.url();
+  match.contents = net::FormatUrl(node.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(node.url(),
+                                                              match.contents);
+  match.description = node.GetTitle();
+  match.description_class =
+      SpansFromMatch(title_match.match_positions, match.description.size());
+
+  match.starred = true;
+  return match;
+}
+
+namespace {
+
+bool MatchPositionSort(const Snippet::MatchPosition& p1,
+                       const Snippet::MatchPosition& p2) {
+  return p1.first < p2.first;
+}
+
+}  // namespace
+
+// static
+ACMatchClassifications BookmarkProvider::SpansFromMatch(
+    const Snippet::MatchPositions& positions,
+    size_t text_length) {

[Peter Kasting, 2012/10/04 20:40:31]

We do similar things in contact_provider_chromeos.cc:WordIsNamePrefix() and to a
lesser degree ShortcutsProvider::ClassifyAllMatchesInString().  Can we share
code somehow?

Especially the "collapse overlapping positions and convert to classifications"
part below can all be handled by repeated calls to
AutocompleteMatch::MergeClassifications() as the ContactsProvider does.

[mrossetti, 2012/10/05 22:10:04]

Done.

+  ACMatchClassifications spans;
+  if (positions.size() == 0) {

[Peter Kasting, 2012/10/04 20:40:31]

Nit: empty()

[mrossetti, 2012/10/05 22:10:04]

Gah!

+    spans.push_back(ACMatchClassification(0, ACMatchClassification::NONE));
+    return spans;
+  }
+
+  Snippet::MatchPositions distinct_positions;
+  if (positions.size() == 1) {
+    distinct_positions = positions;  // Can't use swap: positions is const.
+  } else {
+    // Sort the positions.
+    Snippet::MatchPositions sorted_positions(positions);
+    std::sort(sorted_positions.begin(), sorted_positions.end(),
+              MatchPositionSort);
+
+    // Collapse any positions that overlap.
+    Snippet::MatchPositions::const_iterator a_iter = sorted_positions.begin();
+    Snippet::MatchPosition a_pos(*a_iter);
+    for (Snippet::MatchPositions::const_iterator b_iter = ++a_iter;
+         b_iter != sorted_positions.end(); ++b_iter) {
+      if (a_pos.second >= b_iter->first) {
+        // Need collapsing.
+        a_pos.second = b_iter->second;
+      } else {
+        // |a| stands on its own.
+        distinct_positions.push_back(a_pos);
+        a_iter = b_iter;
+        a_pos = *a_iter;
+      }
+    }
+    distinct_positions.push_back(a_pos);
+  }
+
+  // Convert the positions into ACMatchClassifications.
+  Snippet::MatchPositions::const_iterator p = distinct_positions.begin();
+  if (p->first > 0)
+      spans.push_back(ACMatchClassification(0, ACMatchClassification::NONE));
+  for (; p != distinct_positions.end(); ++p) {
+    spans.push_back(ACMatchClassification(p->first,
+                                          ACMatchClassification::MATCH));
+    if (p->second < text_length) {
+      spans.push_back(ACMatchClassification(p->second,
+                                            ACMatchClassification::NONE));
+    }
+  }
+
+  return spans;
+}