Implement Bookmark Autocomplete Provider

chrome/browser/autocomplete/bookmark_provider.cc

+#include "chrome/browser/autocomplete/bookmark_provider.h"
+
+#include <functional>
+#include <vector>
+
+#include "base/metrics/histogram.h"
+#include "base/string_number_conversions.h"

[Mark P, 2012/09/28 23:10:22]

Why do you need this?

[mrossetti, 2012/10/02 00:44:16]

I don't any longer. Removed. Good catch.

+#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",

[Mark P, 2012/09/28 23:10:22]

Perhaps you want two different histograms, one for searching for the best match
and one for all other cases?

[mrossetti, 2012/10/02 00:44:16]

It doesn't make a significant difference in execution time so I don't see a need
to differentiate.

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

Okay.

+                      base::TimeTicks::Now() - start_time);
+}
+
+BookmarkProvider::~BookmarkProvider() {}
+
+
+void BookmarkProvider::DoAutocomplete(const AutocompleteInput& input,
+                                      bool best_match) {
+  // Get the matching bookmarks from the bookmark model.
+  string16 search_string = input.text();

[Mark P, 2012/09/28 23:10:22]

It makes more sense (to me) to have these two lines closer to where the first
use of this variable is.

[mrossetti, 2012/10/02 00:44:16]

Good point! And I was able to get rid of the temporary completely.

+
+  if (!bookmark_model_) {
+    bookmark_model_ = BookmarkModelFactory::GetForProfile(profile_);

[Mark P, 2012/09/28 23:10:22]

Is this fast enough that it can be done synchronously on the first omnibox
keystroke?

[mrossetti, 2012/10/02 00:44:16]

Right now, the BookmarkProvider will returning suggestions for search terms with
at least 3 characters. The response time where there are hundreds of bookmarks
(I don't have an exact number for my test set but it's close to a thousand) is
under 10 ms. I'd like to get this settled with the 3 limit and then experiment
with reducing it to 1 after this is stable.

There is one gotcha with the 3 limit tho: All search terms must be at least 3
characters long. So if 'cou' brings up your favorite bookmark with a title of
"Country Lyrics" and you then type an 'l' as in "cou l" or even "cou ly" then
the BP will return no results. Once the 'r' is typed, "cou lyr", the BP will
once again start showing results.

+    if (!bookmark_model_)
+      return;

[Mark P, 2012/09/28 23:10:22]

Is this worth a DCHECK NOT REACHED?

[mrossetti, 2012/10/02 00:44:16]

Not really, because there might not be a bookmark model for some unit tests. I
did, however, add a check for |profile_| which might also be NULL for some unit
tests.

+  }
+
+  TitleMatches matches;
+  bookmark_model_->GetBookmarksWithTitlesMatching(search_string, 99, &matches);

[Mark P, 2012/09/28 23:10:22]

Comment on the meaning of 99.

[mrossetti, 2012/10/02 00:44:16]

Done.

+  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_;
+  }
+  long TotalLength() { return length_; }
+  int TotalDisorders() { return disorders_; }
+
+ private:
+  long length_;
+  int disorders_;
+  size_t last_pos_;
+};
+
+}  // 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.
+  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/09/28 00:55:13]

I can't follow this code from 114-125.  Perhaps in this comment you meant to
have an open parenthesis before the 1199 and a close one before the slash?  Then
I think that makes sense with the code.

But I still find the structure of this scoring odd.  In particular, you're
computing (base score + #bookmark boost) and then subtracting off a discounted
version of this.  I find it hard to wrap my head around what effect this has. 
Can you simplify this / decompose this quantity of title match code?

[mrossetti, 2012/10/02 00:44:16]

I threw in a very simple scoring algorithm here as a placeholder in hopes you
would suggest a more appropriate approach. Scoring of suggestions is already
totally wacky so any stab I take at it couldn't be much worse but,
unfortunately, not any better either. That is the whole purpose of my asking if
you could suggest a general approach and I'll fill in the code. On the other
hand, I could use the HUP approach and simply boost the score because it's a
bookmark. But, frankly, I didn't not want to take any historical usage into
consideration for the BookmarkProvider simply because that is already being done
by the HQP. _This_ provider will probably be most valuable for picking up
bookmarks that have not been visited for a while.

With all of that said, here was the (simple-minded) thinking I put into this
placeholder scoring scheme:

1. If it's a bookmark start with a base score of 900. (Line 115)
2. If the URL in the bookmark is referenced by other bookmarks then boost the
score. (Lines 112-115)
3. The maximum possible score is 1199 so take the difference of the current
score and that max. Calculate the fraction of the bookmark's title that is
spanned by the search terms and boost the score by multiplying that fraction by
the difference in the max and current score. For example, if the current score
is 900 and the search terms span 21% of the bookmark title that gives (1199 -
900) * 21% ==> 63 points. (Lines 116-125)
4. If there were multiple search terms and they appeared out of order in the
bookmark title then 50 points for each out-of-order search term.

As I said, simple-minded. I'm sure you can proposed a much more rational
approach!

On 2012/09/28 00:55:13, Mark P wrote:

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

I don't think I can.  :)  Your approach sounds reasonable.

I mainly was complaining about step 3.  It seems conceptually odd to me that an
input that matches one bookmark and covers the bookmark text by 21% should get
more credit for covering it than an input that matches two bookmarks and covers
them by 21%.  I know the scores end up in a reasonable order, but it seems odd
that you give the first a larger boost than the second because the first has
more headroom before it hits 1199.

I'll give specific suggestions to this on patchset 3.

+  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();
+
+  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) {
+  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;
+         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;
+}

[Mark P, 2012/09/28 23:10:22]

I don't see you ever touching |done_|.  Does it get set correctly even if you're
not doing anything to it explicitly?

[mrossetti, 2012/10/02 00:44:16]

Excellent question. |done_| is always true unless the provider specifically sets
it to false so it is irrelevant in the case of a synchronous-only provider.