autocomplete: Make ContactProvider rank contacts by affinity

This adds an 'affinity' field to the contacts::Contact
protocol message and makes the ContactProvider class use it
to order matches.

BUG=141877
TEST=none


Review URL: https://chromiumcodereview.appspot.com/10916304

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@156883 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 114 insertions, 21 deletions

diff --git a/chrome/browser/autocomplete/contact_provider_chromeos.cc b/chrome/browser/autocomplete/contact_provider_chromeos.cc
index 2e7ff9a..2d1c489 100644
--- a/chrome/browser/autocomplete/contact_provider_chromeos.cc
+++ b/chrome/browser/autocomplete/contact_provider_chromeos.cc
@@ -5,6 +5,7 @@
 #include "chrome/browser/autocomplete/contact_provider_chromeos.h"
 
 #include <algorithm>
+#include <cmath>
 
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/string_search.h"
@@ -18,6 +19,17 @@
 
 namespace {
 
+// Default affinity assigned to contacts whose |affinity| field is unset.
+// TODO(derat): Set this to something reasonable (probably 0.0) once we're
+// getting affinity for contacts.
+float kDefaultAffinity = 1.0;
+
+// Base match relevance assigned to a contact with an affinity of 0.0.
+int kBaseRelevance = 1300;
+
+// Maximum boost to relevance for a contact with an affinity of 1.0.
+int kAffinityRelevanceBoost = 200;
+
 // 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
@@ -56,13 +68,15 @@ 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(
@@ -80,6 +94,9 @@ struct ContactProvider::ContactData {
 
   // 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(
@@ -115,8 +132,11 @@ void ContactProvider::Start(const AutocompleteInput& input,
     }
   }
 
+  // |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);
 }
 
@@ -133,6 +153,12 @@ ContactProvider::~ContactProvider() {
     contact_manager_->RemoveObserver(this, profile_);
 }
 
+// static
+bool ContactProvider::CompareAffinity(const ContactData& a,
+                                      const ContactData& b) {
+  return a.affinity > b.affinity;
+}
+
 void ContactProvider::RefreshContacts() {
   if (!contact_manager_.get())
     return;
@@ -141,6 +167,7 @@ void ContactProvider::RefreshContacts() {
       contact_manager_->GetAllContacts(profile_);
 
   contacts_.clear();
+  contacts_.reserve(contacts->size());
   for (contacts::ContactPointers::const_iterator it = contacts->begin();
        it != contacts->end(); ++it) {
     const contacts::Contact& contact = **it;
@@ -150,13 +177,16 @@ void ContactProvider::RefreshContacts() {
         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));
     }
   }
+  std::sort(contacts_.begin(), contacts_.end(), CompareAffinity);
 }
 
 void ContactProvider::AddContactIfMatched(
@@ -200,8 +230,8 @@ AutocompleteMatch ContactProvider::CreateAutocompleteMatch(
   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;
 }
diff --git a/chrome/browser/autocomplete/contact_provider_chromeos.h b/chrome/browser/autocomplete/contact_provider_chromeos.h
index 9880aa0..1a14a38 100644
--- a/chrome/browser/autocomplete/contact_provider_chromeos.h
+++ b/chrome/browser/autocomplete/contact_provider_chromeos.h
@@ -48,6 +48,9 @@ class ContactProvider : public AutocompleteProvider,
 
   virtual ~ContactProvider();
 
+  // Returns true if |a|'s affinity is greater than |b|'s affinity.
+  static bool CompareAffinity(const ContactData& a, const ContactData& b);
+
   // Updates |contacts_| to match the contacts currently reported by
   // ContactManager.
   void RefreshContacts();
@@ -65,7 +68,7 @@ class ContactProvider : public AutocompleteProvider,
 
   base::WeakPtr<contacts::ContactManagerInterface> contact_manager_;
 
-  // Contacts through which we search.
+  // Contacts through which we search, ordered by descending affinity.
   ContactDataVector contacts_;
 
   DISALLOW_COPY_AND_ASSIGN(ContactProvider);
diff --git a/chrome/browser/autocomplete/contact_provider_chromeos_unittest.cc b/chrome/browser/autocomplete/contact_provider_chromeos_unittest.cc
index 52700a2..b544dfd 100644
--- a/chrome/browser/autocomplete/contact_provider_chromeos_unittest.cc
+++ b/chrome/browser/autocomplete/contact_provider_chromeos_unittest.cc
@@ -4,12 +4,14 @@
 
 #include "chrome/browser/autocomplete/contact_provider_chromeos.h"
 
+#include <cmath>
 #include <map>
 #include <string>
 #include <vector>
 
 #include "base/memory/scoped_ptr.h"
 #include "base/message_loop.h"
+#include "base/string_number_conversions.h"
 #include "base/string16.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_input.h"
@@ -73,19 +75,26 @@ class ContactProviderTest : public testing::Test {
         false);  // minimal_changes
   }
 
+  // Returns the contact ID in |match|'s additional info, or an empty string if
+  // no ID is present.
+  std::string GetContactIdFromMatch(const AutocompleteMatch& match) {
+    AutocompleteMatch::AdditionalInfo::const_iterator it =
+        match.additional_info.find(ContactProvider::kMatchContactIdKey);
+    return it != match.additional_info.end() ? it->second : std::string();
+  }
+
   // Returns pointers to all of the Contact objects referenced in
   // |contact_provider_|'s current results.
   contacts::ContactPointers GetMatchedContacts() {
     contacts::ContactPointers contacts;
     const ACMatches& matches = contact_provider_->matches();
     for (size_t i = 0; i < matches.size(); ++i) {
-      std::map<std::string, std::string>::const_iterator id_it =
-          matches[i].additional_info.find(ContactProvider::kMatchContactIdKey);
-      CHECK(id_it != matches[i].additional_info.end());
-      const contacts::Contact* contact =
-          contact_manager_->GetContactById(profile_, id_it->second);
-      CHECK(contact) << "Unable to find contact with ID " << id_it->second;
-      contacts.push_back(contact);
+      const contacts::Contact* contact = contact_manager_->GetContactById(
+          profile_, GetContactIdFromMatch(matches[i]));
+      if (contact)
+        contacts.push_back(contact);
+      else
+        LOG(ERROR) << "Unable to find contact for match " << i;
     }
     return contacts;
   }
@@ -99,11 +108,13 @@ class ContactProviderTest : public testing::Test {
     StringMap contact_id_classifications;
     const ACMatches& matches = contact_provider_->matches();
     for (size_t i = 0; i < matches.size(); ++i) {
-      std::map<std::string, std::string>::const_iterator id_it =
-          matches[i].additional_info.find(ContactProvider::kMatchContactIdKey);
-      CHECK(id_it != matches[i].additional_info.end());
-      contact_id_classifications[id_it->second] =
-          AutocompleteMatch::ClassificationsToString(matches[i].contents_class);
+      std::string id = GetContactIdFromMatch(matches[i]);
+      if (id.empty()) {
+        LOG(ERROR) << "Match " << i << " lacks contact ID";
+      } else {
+        contact_id_classifications[id] = AutocompleteMatch::
+            ClassificationsToString(matches[i].contents_class);
+      }
     }
 
     std::string result;
@@ -227,3 +238,48 @@ TEST_F(ContactProviderTest, Collation) {
       contacts::test::ContactsToString(GetMatchedContacts()));
   EXPECT_EQ("0,0,6,2", GetMatchClassifications());
 }
+
+TEST_F(ContactProviderTest, Relevance) {
+  // Create more contacts than the maximum number of results that an
+  // AutocompleteProvider should return.  Give them all the same family name and
+  // ascending affinities from 0.0 to 1.0.
+  const size_t kNumContacts = AutocompleteProvider::kMaxMatches + 1;
+  const std::string kFamilyName = "Jones";
+
+  ScopedVector<contacts::Contact> contacts;
+  contacts::ContactPointers contact_pointers;
+  for (size_t i = 0; i < kNumContacts; ++i) {
+    contacts::Contact* contact = new contacts::Contact;
+    std::string id_string = base::IntToString(static_cast<int>(i));
+    InitContact(id_string, id_string, kFamilyName,
+                id_string + " " + kFamilyName, contact);
+    contact->set_affinity(static_cast<float>(i) / kNumContacts);
+    contacts.push_back(contact);
+    contact_pointers.push_back(contact);
+  }
+
+  contact_manager_->SetContacts(contact_pointers);
+  contact_manager_->NotifyObserversAboutUpdatedContacts();
+
+  // Do a search for the family name and check that the total number of results
+  // is limited as expected and that the results are ordered by descending
+  // affinity.
+  StartQuery(kFamilyName);
+  const ACMatches& matches = contact_provider_->matches();
+  ASSERT_EQ(AutocompleteProvider::kMaxMatches, matches.size());
+
+  int previous_relevance = 0;
+  for (size_t i = 0; i < matches.size(); ++i) {
+    const contacts::Contact& exp_contact =
+        *(contacts[kNumContacts - 1 - i]);
+    std::string match_id = GetContactIdFromMatch(matches[i]);
+    EXPECT_EQ(exp_contact.contact_id(), match_id)
+        << "Expected contact ID " << exp_contact.contact_id()
+        << " for match " << i << " but got " << match_id << " instead";
+    if (i > 0) {
+      EXPECT_LE(matches[i].relevance, previous_relevance)
+          << "Match " << i << " has greater relevance than previous match";
+    }
+    previous_relevance = matches[i].relevance;
+  }
+}
diff --git a/chrome/browser/chromeos/contacts/contact.proto b/chrome/browser/chromeos/contacts/contact.proto
index 0cd6705..3d605e2 100644
--- a/chrome/browser/chromeos/contacts/contact.proto
+++ b/chrome/browser/chromeos/contacts/contact.proto
@@ -14,7 +14,7 @@ package contacts;
 // https://developers.google.com/gdata/docs/2.0/elements#gdContactKind
 // All strings are UTF-8 with Unicode byte order marks stripped out.
 message Contact {
-  // Next ID to use: 15
+  // Next ID to use: 16
 
   // Provider-assigned unique identifier.
   optional string contact_id = 1;
@@ -26,6 +26,10 @@ message Contact {
   // Has the contact been deleted recently within the upstream provider?
   optional bool deleted = 3 [default = false];
 
+  // Affinity between the user and this contact, in the range [0.0, 1.0].
+  // Unset if the affinity is unknown.
+  optional float affinity = 15;
+
   // Taken from https://developers.google.com/gdata/docs/2.0/elements#gdName.
   optional string full_name = 4;
   optional string given_name = 5;