Omnibox: Make the Controller Reorder Matches for Inlining

chrome/browser/autocomplete/autocomplete_result.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/autocomplete_result.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/logging.h"
 #include "chrome/browser/autocomplete/autocomplete_input.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
+#include "chrome/browser/omnibox/omnibox_field_trial.h"
 
 // static
 const size_t AutocompleteResult::kMaxMatches = 6;
 const int AutocompleteResult::kLowestDefaultScore = 1200;
 
 void AutocompleteResult::Selection::Clear() {
   destination_url = GURL();
   provider_affinity = NULL;
   is_history_what_you_typed_match = false;
 }
 
-AutocompleteResult::AutocompleteResult() {
+AutocompleteResult::AutocompleteResult()
+    : reorder_for_inlining_(OmniboxFieldTrial::InReorderForInliningGroup()) {
   // Reserve space for the max number of matches we'll show.
   matches_.reserve(kMaxMatches);
 
   // It's probably safe to do this in the initializer list, but there's little
   // penalty to doing it here and it ensures our object is fully constructed
   // before calling member functions.
   default_match_ = end();
 }
 
 AutocompleteResult::~AutocompleteResult() {}
@@ skipping 60 matching lines @@
   std::sort(matches_.begin(), matches_.end(),
             &AutocompleteMatch::DestinationSortFunc);
   matches_.erase(std::unique(matches_.begin(), matches_.end(),
                              &AutocompleteMatch::DestinationsEqual),
                  matches_.end());
 
   // Sort and trim to the most relevant kMaxMatches matches.
   const size_t num_matches = std::min(kMaxMatches, matches_.size());
   std::partial_sort(matches_.begin(), matches_.begin() + num_matches,
                     matches_.end(), &AutocompleteMatch::MoreRelevant);
+  if ((begin()->inline_autocomplete_offset == string16::npos) &&
+      reorder_for_inlining_) {
+    // Top match is not inlineable.  Find the most relevant inlineable
+    // match and shift it to the front.
+    AutocompleteResult::iterator best_inlineable_match = end();
+    for (AutocompleteResult::iterator it = begin(); it != end(); ++it) {
+      if ((it->inline_autocomplete_offset != string16::npos) &&
+          ((best_inlineable_match == end()) ||
+           AutocompleteMatch::MoreRelevant(*it, *best_inlineable_match))) {

[Peter Kasting, 2013/07/13 01:31:40]

Seems like we don't need the MoreRelevant() check if we replace the
partial_sort() above with a complete sort.

[Mark P, 2013/07/17 15:45:18]

I thought about this.

For long inputs, the set of matches will be small (say, 5) so the difference
between full sort and partial sort is zero.  Under this condition, we probably
end up with a few (say, 4) MoreRelevant calls.  This is fast so this condition
doesn't matter.

For short inputs, we have larger results set, more on the order of 20.  Sorting
the extra 14 elements (after the first 6) will take something like 50 calls to
MoreRelevant.  This is substantially more than the at-most 20 that will happen
with this extra loop to find the most relevant inlineable result.

I think it's better leave it the way it is.

[Peter Kasting, 2013/07/17 18:29:48]

50 calls to MoreRelevant seems immaterial.  Each one is a string equality check
and a numeric compare.  Doing 50 of those shouldn't take measurable time, even
if we have to run SortAndCull a dozen times for each keystroke, especially if
the alternative is that we're already doing 20.  And it would make the code less
confusing.

If you were really worried, you could locally put a small timing block around
this and then type a few short inputs into your omnibox to check how long this
takes.  I bet it will be tremendously short.

[Mark P, 2013/07/17 20:39:18]

Okay, I trust your judgement.

+        best_inlineable_match = it;
+      }
+    }
+    DCHECK(best_inlineable_match != end());
+    std::rotate(matches_.begin(), best_inlineable_match,
+                best_inlineable_match + 1);
+  }
   matches_.resize(num_matches);
 
   default_match_ = begin();
 
   // Set the alternate nav URL.
   alternate_nav_url_ = (default_match_ == end()) ?
       GURL() : ComputeAlternateNavUrl(input, *default_match_);
 }
 
 bool AutocompleteResult::HasCopiedMatches() const {
@@ skipping 133 matching lines @@
        i != old_matches.rend() && delta > 0; ++i) {
     if (!HasMatchByDestination(*i, new_matches)) {
       AutocompleteMatch match = *i;
       match.relevance = std::min(max_relevance, match.relevance);
       match.from_previous = true;
       AddMatch(match);
       delta--;
     }
   }
 }