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();
+
+  // Only bother with UNKNOWN and QUERY.
+  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);
+  UMA_HISTOGRAM_TIMES("Autocomplete.BookmarkProviderMatchTime",
+                      base::TimeTicks::Now() - start_time);
+}
+
+BookmarkProvider::~BookmarkProvider() {}
+
+
+void BookmarkProvider::DoAutocomplete(const AutocompleteInput& input,
+                                      bool best_match) {
+  if (!bookmark_model_) {
+    // We may not have a profile or bookmark model for some unit tests.
+    if (!profile_)
+      return;
+    bookmark_model_ = BookmarkModelFactory::GetForProfile(profile_);

[Mark P, 2012/10/03 20:40:14]

This sounds fine to me.

Where is the 3 set in code?  I don't seem to see it in this file.

My question, however, was much simpler than you took it to mean.  I wanted to
know if this line in particular "BookmarkModelFactory::GetForProfile(profile_)"
is fast enough that it can be done synchronously on the first omnibox keystroke.
 Can it?
Ugh, what icky behavior.  Will this go away if you can resolve the 3 -> 1 issue?

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

Yes, because if the bookmark model has not been loaded then this will cause it
to be loaded. The data, however, will be loaded on the FILE thread so it won't
slow down omnibox response, it just won't be able to provide any data for this
particular query.
It's complicated behavior down in the BookmarkIndex. An exact match is performed
for queries with fewer than the minimum needed for a prefix match. That minimum
is determined by the QueryParser::IsWordLongEnoughForPrefixSearch(term) function
and has to do with optimizing SQLite queries. Minimizing this particular
irritation is the ShortcutsProvider, which should serve up historical searches
on foreshortened search strings. So for subsequent searches for "Country Lyrics"
merely typing a 'c' or 'co' ought to bring up the most frequently accessed
sites.

(Frankly, I'd like to get to a point where a single-word search term is also
considered as a possible acronym, matching the first letters in a list of words.
Typing something like 'qsb' could find results like "Quick Search Box". But this
is besides the point.)

+    if (!bookmark_model_)
+      return;
+  }
+
+  TitleMatches matches;
+  // Retrieve enough bookmarks so that we can reasonably score the best.

[Mark P, 2012/10/03 20:40:14]

we can reasonably score the best
->
we have a reasonable chance of getting one the user may have meant

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

Done.

+  const size_t kMaxBookmarkMatches = 50;
+  bookmark_model_->GetBookmarksWithTitlesMatching(input.text(),
+                                                  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 {

[Mark P, 2012/10/03 20:40:14]

When / how does last_pos_ get set?

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

Good catch! It _was_ in there, I swear.

I'll add a unit test that catches this once scoring is finalized.

+ 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_;
+  }
+  long TotalLength() { return length_; }
+  int TotalDisorders() { return disorders_; }
+
+ private:
+  long length_;
+  int disorders_;
+  size_t last_pos_;
+};

[Mark P, 2012/10/03 20:40:14]

What will happen with an omnibox input
foobar foobar
for input foobar foo?
Do we get two matches at each term foobar in the title or one?  How do they
sort?  How do we calculate disorders and total length of matches?  (Are we
overcounting length of matched text?)

I know I can answer all this by looking carefully at the code, but my job as a
code reviewer is to make sure you're doing the right thing and to have you make
it clear the code is doing the right thing (by adding comments or code as
appropriate). :)

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

The problem with relying on comments is that it's far too easy for the comments
to get out-of-synch with the implementation. Also, I was trying to avoid
influencing your thinking about how scoring ought to be done. In fact, I was
hesitant to put _any_ scoring at all into this function and was simply going to
give each result a score of 900. I don't know what came over me. :)

+
+}  // namespace
+
+AutocompleteMatch BookmarkProvider::TitleMatchToACMatch(
+    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.

[Mark P, 2012/10/03 20:40:14]

I like boosting for matching the URL in multiple *bookmarks*.  Is that what
you're doing here?  Or are you boosting for matching multiple times in the title
to one particular bookmark?  It's not clear to me from either the code or the
comments.  (I'd have to dive into other files to see how match_positions is
defined.)

Can you clarify this code 117-121?

Also, it's misleading to say base score = 900 because you know there will always
be at least one match.  Make the base score correspond to one match, then
increment from there.

P.S.  I prefer boosting for matching in multiple bookmarks and leaving the
percent coverage code to reflect the benefit of having multiple matches
(multiple coverage) within one particular title.

+  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

[Mark P, 2012/10/03 20:40:14]

I don't like this idea of using the magic number 1199 here.  I'm trying to move
away from this kind of stuff.  I also don't like how we can boost two different
matches that have 21% coverage differently depending on other factors (as I
explained in a different comment).  I'd prefer to see lines 122-131 be simpler,
something more like
relevance += (percent of title that's matched)
i.e., 100 points for a full title match, 50 for half.

To make this all stay under 1199 without having to explicitly use a cap, I'd
suggest compressing the 900-1150 range you currently have based on number of
matches.  Perhaps simply go from
900 (one match), 975 (two matches), 1025 (three matches), 1050 (four or more
matches).

+  PositionFunctor position_functor =
+      for_each(title_match.match_positions.begin(),
+               title_match.match_positions.end(), PositionFunctor());
+  int adjuster =
+      static_cast<int>((
+          static_cast<long>(AutocompleteResult::kLowestDefaultScore -
+                            relevance - 1) * position_functor.TotalLength()) /
+      static_cast<long>(title_match.node->GetTitle().size()));
+  relevance += adjuster;
+  // Subtract 50 for each out-of-order match.
+  relevance -= 50 * position_functor.TotalDisorders();

[Mark P, 2012/10/03 20:40:14]

Lines 132-133 are okay for now.  There's one thing I'm worried about.  Suppose
the user enters
aaa bbb
and you have two possible contenders with the same percent coverage):
aaa bbb aaa foo foo bar
and
aaa bbb foo bar

I'd think we should prefer the first because it has an extra match, even though
it's out-of-order.  This code prefers the second.

I'm comfortable leaving this as-is because people tend not to enter multiple
term inputs in the omnibox and because bookmark titles I think tend to be short,
so it's not worth spending much time on this.  However, for completeness I'd
like to mention that a plausible way to do this would be to count the number of
term pairs that never appear in the correct order in the title and only penalize
for those.  If a term pair appears at least once in the right order, we
shouldn't count it as a disorder.

+
+  AutocompleteMatch match(this, relevance, false,

[Mark P, 2012/10/03 20:40:14]

comment on the meaning of false

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

That's documented in the header comments for the AutocompleteMatch constructor.

The false means that the item to which the AutocompleteMatch refers cannot be
deleted. We don't want to allow the user to accidentally delete bookmarks from
the suggestions list.

+                          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) {
+  ACMatchClassifications spans;
+  if (positions.size() == 0) {
+    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;

[Mark P, 2012/10/03 20:40:14]

I think you can right this loop with only one iterator but if you want to leave
it as is that's okay with me.

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

OK, left as-is.

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