autocomplete: Make ContactProvider rank contacts by affinity

chrome/browser/autocomplete/contact_provider_chromeos.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/contact_provider_chromeos.h"
 
 #include <algorithm>
+#include <cmath>
 
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/string_search.h"
 #include "base/string_split.h"
 #include "base/string16.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_input.h"
 #include "chrome/browser/chromeos/contacts/contact.pb.h"
 #include "chrome/browser/chromeos/contacts/contact_manager.h"
 #include "chrome/browser/profiles/profile.h"
 
 namespace {
 
+// Default affinity assigned to contacts whose |affinity| field is unset.
+float kDefaultAffinity = 1.0;

[Peter Kasting, 2012/09/13 23:32:37]

Isn't this kind of high?  I guess I don't totally understand how affinity is
calculated.

[Daniel Erat, 2012/09/14 15:31:50]

Dirty secret: We're not getting affinity data yet, so I set this high so we'll
see contacts in the app list results when the flag is set.  Added a TODO.

+
 // Returns true if |word_to_find| is a prefix of |name_to_search| and marks the
 // matching text in |classifications| (which corresponds to the contact's full
 // name).  |name_index_in_full_name| contains |name_to_search|'s index within
 // the full name or string16::npos if it doesn't appear in it.
 bool WordIsNamePrefix(const string16& word_to_find,
                       const string16& name_to_search,
                       size_t name_index_in_full_name,
                       size_t full_name_length,
                       ACMatchClassifications* classifications) {
   DCHECK(classifications);
 
   size_t match_index = 0;
   size_t match_length = 0;
   if (!base::i18n::StringSearchIgnoringCaseAndAccents(word_to_find,
       name_to_search, &match_index, &match_length) || (match_index != 0))
     return false;
 
   if (name_index_in_full_name != string16::npos) {
     AutocompleteMatch::ACMatchClassifications new_class;
     AutocompleteMatch::ClassifyLocationInString(name_index_in_full_name,
         match_length, full_name_length, 0, &new_class);
     *classifications = AutocompleteMatch::MergeClassifications(
         *classifications, new_class);
   }
 
   return true;
 }
 
+// Returns true if |a|'s affinity is greater than |b|'s affinity.
+bool CompareContactAffinity(const contacts::Contact* a,
+                            const contacts::Contact* b) {
+  float affinity_a = a->has_affinity() ? a->affinity() : kDefaultAffinity;

[Peter Kasting, 2012/09/13 23:32:37]

Super tiny nit: Seems like |a_affinity| would be just a teensy bit better than
|affinity_a|

[Daniel Erat, 2012/09/14 15:31:50]

Done.

+  float affinity_b = b->has_affinity() ? b->affinity() : kDefaultAffinity;
+  return affinity_a > affinity_b;
+}
+
 }  // namespace
 
 // static
 const char ContactProvider::kMatchContactIdKey[] = "contact_id";
+const int ContactProvider::kBaseRelevance = 1300;

[Daniel Erat, 2012/09/13 23:10:08]

I just pulled numbers out of the air for this.  Since this is off by default and
we have no plans to expose these results anywhere outside the app list (which
itself will soon only return apps rather than giving the full omnibox
experience), I'm not sure how much these numbers matter.

+const int ContactProvider::kAffinityRelevanceBoost = 200;
 
 // Cached information about a contact.
 struct ContactProvider::ContactData {
   ContactData(const string16& full_name,
               const string16& given_name,
               const string16& family_name,
-              const std::string& contact_id)
+              const std::string& contact_id,
+              float affinity)
       : full_name(full_name),
         given_name(given_name),
         family_name(family_name),
         given_name_index(string16::npos),
         family_name_index(string16::npos),
-        contact_id(contact_id) {
+        contact_id(contact_id),
+        affinity(affinity) {
     base::i18n::StringSearchIgnoringCaseAndAccents(
         given_name, full_name, &given_name_index, NULL);
     base::i18n::StringSearchIgnoringCaseAndAccents(
         family_name, full_name, &family_name_index, NULL);
   }
 
   string16 full_name;
   string16 given_name;
   string16 family_name;
 
   // Indices into |full_name| where |given_name| and |family_name| first appear,
   // or string16::npos if they don't appear in it.
   size_t given_name_index;
   size_t family_name_index;
 
   // Unique ID used to look up additional contact information.
   std::string contact_id;
+
+  // Affinity between the user and this contact, in the range [0.0, 1.0].
+  float affinity;
 };
 
 ContactProvider::ContactProvider(
     AutocompleteProviderListener* listener,
     Profile* profile,
     base::WeakPtr<contacts::ContactManagerInterface> contact_manager)
     : AutocompleteProvider(listener, profile, TYPE_CONTACT),
       contact_manager_(contact_manager) {
   contact_manager_->AddObserver(this, profile);
   RefreshContacts();
@@ skipping 15 matching lines @@
   base::i18n::BreakIterator break_iterator(
       input.text(),
       base::i18n::BreakIterator::BREAK_WORD);
   if (break_iterator.Init()) {
     while (break_iterator.Advance()) {
       if (break_iterator.IsWord())
         input_words.push_back(break_iterator.GetString());
     }
   }
 
+  // |contacts_| is ordered by descending affinity.  Since affinity is currently
+  // the only signal used for computing relevance, we can stop after we've found
+  // kMaxMatches results.
   for (ContactDataVector::const_iterator it = contacts_.begin();
-       it != contacts_.end(); ++it)
+       it != contacts_.end() && matches_.size() < kMaxMatches; ++it)
     AddContactIfMatched(input, input_words, *it);
 }
 
 void ContactProvider::OnContactsUpdated(Profile* profile) {
   DCHECK_EQ(profile, profile_);
   RefreshContacts();
 }
 
 ContactProvider::~ContactProvider() {
   // Like ContactProvider, ContactManager gets destroyed at profile destruction.
   // Make sure that this class doesn't try to access ContactManager after
   // ContactManager is gone.
   if (contact_manager_.get())
     contact_manager_->RemoveObserver(this, profile_);
 }
 
 void ContactProvider::RefreshContacts() {
   if (!contact_manager_.get())
     return;
 
   scoped_ptr<contacts::ContactPointers> contacts =
       contact_manager_->GetAllContacts(profile_);
+  std::sort(contacts->begin(), contacts->end(), CompareContactAffinity);

[Peter Kasting, 2012/09/13 23:32:37]

Nit: If we move this down to the bottom of the function, we can get rid of the
need to check for missing affinity from CompareContactAffinity(), because the
code below will have taken care of that

[Daniel Erat, 2012/09/14 15:31:50]

I went back and forth on this.  Sorting pointers seemed better than sorting
structs, but that's a pretty specious argument for me to take (if it were really
a big deal performance-wise, I shouldn't be storing the structs directly in a
vector, or I should at least be calling reserve() first).  Updated.

 
   contacts_.clear();
   for (contacts::ContactPointers::const_iterator it = contacts->begin();
        it != contacts->end(); ++it) {
     const contacts::Contact& contact = **it;
     string16 full_name =
         AutocompleteMatch::SanitizeString(UTF8ToUTF16(contact.full_name()));
     string16 given_name =
         AutocompleteMatch::SanitizeString(UTF8ToUTF16(contact.given_name()));
     string16 family_name =
         AutocompleteMatch::SanitizeString(UTF8ToUTF16(contact.family_name()));
+    float affinity =
+        contact.has_affinity() ? contact.affinity() : kDefaultAffinity;
 
     if (!full_name.empty()) {
       contacts_.push_back(
-          ContactData(
-              full_name, given_name, family_name, contact.contact_id()));
+          ContactData(full_name, given_name, family_name, contact.contact_id(),
+                      affinity));
     }
   }
 }
 
 void ContactProvider::AddContactIfMatched(
     const AutocompleteInput& input,
     const std::vector<string16>& input_words,
     const ContactData& contact) {
   // First, check if the whole input string is a prefix of the full name.
   // TODO(derat): Consider additionally segmenting the full name so we can match
@@ skipping 25 matching lines @@
   matches_.back().contents_class = classifications;
 }
 
 AutocompleteMatch ContactProvider::CreateAutocompleteMatch(
     const AutocompleteInput& input,
     const ContactData& contact) {
   AutocompleteMatch match(this, 0, false, AutocompleteMatch::CONTACT);
   match.inline_autocomplete_offset = string16::npos;
   match.contents = contact.full_name;
   match.fill_into_edit = match.contents;
-  // TODO(derat): Implement ranking.
-  match.relevance = 1;
+  match.relevance = kBaseRelevance +
+      static_cast<int>(roundf(kAffinityRelevanceBoost * contact.affinity));
   match.RecordAdditionalInfo(kMatchContactIdKey, contact.contact_id);
   return match;
 }