Don't autocomplete searches of >1 word if they've only been visited once and the user has not yet...

Don't autocomplete searches of >1 word if they've only been visited once and the user has not yet typed more than one word.

Subtleties:
* To avoid "crowding out" issues where penalized multiword searches prevent us finding better earlier searches, this gets kMaxMatches * 5 history matches per search provider before trimming to the final list.
* To avoid penalized searches preventing completion of prior searches, or sudden changes of autocompletion when going from one to two words typed, this changes the relevance uniquifying algorithm to first do a stable_sort().  One consequence of this is that we'll now be willing to modify the order of results from history, so e.g. we'll now complete "go" -> "goog" even with a newer history result "google.com" (penalized, looks like URL).

This change also adds AutocompleteResult::kLowestDefaultScore since a lot of files want to do something different for "possibly default" matches versus "guaranteed not to be default".  It also refactors search_provider_unittest.cc so I can add a lot of tests without so much boilerplate code.

BUG=79487
TEST=Search for "ghi jkl".  Now type that again and notice that it doesn't autocomplete until after "j".
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=92778

[sky, 2011-07-07 02:49:15]

One down side of this approach is that if you type in a bunch of multi-word
queries all starting with the same thing you're going to starve out the
non-multi-word queries. It would be nice to do a second pass in this case for
single word matches. Maybe shess or Brett has a good idea how to accomplish
something like that. Worse case we could add a column indicating if multi-word.
Maybe I'm being too worried? What do you think?

  -Scott

http://codereview.chromium.org/7314018/diff/1/chrome/browser/autocomplete/sea...
File chrome/browser/autocomplete/search_provider.cc (right):

http://codereview.chromium.org/7314018/diff/1/chrome/browser/autocomplete/sea...
chrome/browser/autocomplete/search_provider.cc:45: bool found_word = false;
nit: move this inside the if.

http://codereview.chromium.org/7314018/diff/1/chrome/browser/history/history_...
File chrome/browser/history/history_types.h (right):

http://codereview.chromium.org/7314018/diff/1/chrome/browser/history/history_...
chrome/browser/history/history_types.h:532: int visits;       // The visit
count.
Make sure to initialize visits to 0 in the member initializer list.

[Peter Kasting, 2011-07-12 20:42:03]

On 2011/07/07 02:49:15, sky wrote:
> One down side of this approach is that if you type in a bunch of multi-word
> queries all starting with the same thing you're going to starve out the
> non-multi-word queries.

Let me make sure I understand what you're saying.

With this method we now effectively have a scoring algorithm that is more
complex than just "sort by last visit", so the ORDER BY part of the SQL query
doesn't guarantee we get the "best" results in terms of what the search provider
would score.  Right?

If so, I agree this is an issue; I'm not sure how to address it.

[sky, 2011-07-12 20:52:25]

On Tue, Jul 12, 2011 at 1:42 PM,  <pkasting@chromium.org> wrote:
> On 2011/07/07 02:49:15, sky wrote:
>>
>> One down side of this approach is that if you type in a bunch of
>> multi-word
>> queries all starting with the same thing you're going to starve out the
>> non-multi-word queries.
>
> Let me make sure I understand what you're saying.
>
> With this method we now effectively have a scoring algorithm that is more
> complex than just "sort by last visit", so the ORDER BY part of the SQL
> query
> doesn't guarantee we get the "best" results in terms of what the search
> provider
> would score.  Right?

Exactly.

> If so, I agree this is an issue; I'm not sure how to address it.

Seems like if you have less than one word we need to do two queries.
One for multi-word searches with visits > 1, and the other with
single-world searches. Maybe shess or brettw has ideas on how to
actually implement that.

  -Scott

[Peter Kasting, 2011-07-12 20:56:54]

On 2011/07/12 20:52:25, sky wrote:
> Seems like if you have less than one word we need to do two queries.
> One for multi-word searches with visits > 1, and the other with
> single-world searches.

It's more complex than that.  Those two sets of items will be scored the same
for the same last visit time.  But they're not guaranteed to be scored higher
than a multi-word, 1-visit query, if they're a lot older than it is.  So you'd
need to make three history queries: two for the cases you name above, merging
the results into one set; and one for multi-word, 1-visit queries.  Then return
both sets, score them all in the provider, and sort.

Or we can take the route the HUP takes, which is to try and get way too many
results back from the history system, in hopes we'll have enough to avoid the
crowding-out issue.

[Peter Kasting, 2011-07-15 22:42:41]

Take another look.

[sky, 2011-07-15 23:01:33]

LGTM

http://codereview.chromium.org/7314018/diff/9001/chrome/browser/autocomplete/...
File chrome/browser/autocomplete/shortcuts_provider.cc (right):

http://codereview.chromium.org/7314018/diff/9001/chrome/browser/autocomplete/...
chrome/browser/autocomplete/shortcuts_provider.cc:79:
(AutocompleteResult::kLowestDefaultScore - 1) & ~3;
Wow, that's obscure (the & ~3)