Omnibox: Add Mid-Input Matching to HistoryQuick Provider

Omnibox: Add Mid-Input Matching to HistoryQuick Provider

The idea:

Suppose I've previously visited
http://www.foobar.com/~mpearson/resume.html
http://www.foobar.com/~sky/resume.html
http://www.foobar.com/~pkasting/resume.html
http://www.foobar.com/~swedish-chef/resume.html

Suppose I have
http://www.foobar.com/~mpearson/resume.html
in the omnibox and then highlight "~mpearson" and press delete, leaving
http://www.foobar.com//resume.html
in the omnibox with the cursor between the two slashes.

I want to see some/all of those URLs I listed.

The current behavior of HistoryQuick provider doesn't show any matches in this situation.


This change remedies this issue.

It also adds a field trial to enable and test this new behavior.


There are some oddities that can happen by allowing the text to break at the cursor.  For instance, suppose the text is google.com.  This clearly matches the URL http://www.google.com/.  Now suppose the user puts his cursor after the "goo" and types "gle", leaving the omnibox with googlegle.com with the cursor between the two "gle"s.  This will still match http://www.google.com/, as before, because both the two terms match (google and gle.com), just in an overlapping fashion.

I played around with this and it's not as surprising as it sounds.  In effect, this means that if you put the cursor in the middle of a URL and "type through" the URL, the URL will always remain as a suggestion.  That kind of makes some sense.

BUG=163932
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=181065

[Mark P, 2013-01-04 01:47:39]

This change currently only contains the interface-level changes and a comment
update to describe what the code will do.  I'm looking for early feedback on
whether this is a good thing to do and a good way to do it before I go write the
implementation and the tests.

thanks,
mark

[Peter Kasting, 2013-01-04 20:04:32]

I don't see what one could really object to about this.

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/in_mem...
File chrome/browser/history/in_memory_url_index.h (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/in_mem...
chrome/browser/history/in_memory_url_index.h:122: const size_t cursor_position);
Passing by const value is weird.

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
chrome/browser/history/url_index_private_data.cc:81: const size_t
cursor_position,
Doesn't match header prototype (and again, const value is weird)

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
File chrome/browser/history/url_index_private_data.h (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
chrome/browser/history/url_index_private_data.h:55: // set). Once we have a set
of candidates, they are filtered to insure
Nit: ensure

[Mark P, 2013-01-04 23:38:58]

Added actual code.  (It's easy.)

Still needs tests, but seems to behave as I'd want, highlighting and all.

--mark

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/in_mem...
File chrome/browser/history/in_memory_url_index.h (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/in_mem...
chrome/browser/history/in_memory_url_index.h:122: const size_t cursor_position);
On 2013/01/04 20:04:32, Peter Kasting wrote:
> Passing by const value is weird.

Done.

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
chrome/browser/history/url_index_private_data.cc:81: const size_t
cursor_position,
On 2013/01/04 20:04:32, Peter Kasting wrote:
> Doesn't match header prototype (and again, const value is weird)

Done.

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
File chrome/browser/history/url_index_private_data.h (right):

https://codereview.chromium.org/11757004/diff/1/chrome/browser/history/url_in...
chrome/browser/history/url_index_private_data.h:55: // set). Once we have a set
of candidates, they are filtered to insure
On 2013/01/04 20:04:32, Peter Kasting wrote:
> Nit: ensure

Done.

[Peter Kasting, 2013-01-04 23:47:39]

https://codereview.chromium.org/11757004/diff/7001/chrome/browser/history/url...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/7001/chrome/browser/history/url...
chrome/browser/history/url_index_private_data.cc:92: search_string.substr(0,
cursor_position) + kWhitespaceUTF16 +
This doesn't insert a space, it inserts a whole string of whitespace characters.

I think you want ASCIIToUTF16(" ").

This could be done most simply by passing |search_string| by value and then
doing:

  if (...)
    search_string.insert(cursor_position, ASCIIToUTF16(" ");
  ...

[Mark P, 2013-01-09 19:51:53]

Still todo:
* double-check highlighting
* add unit tests
* get sky@'s okay
* decide if this be evaluated with a field trial or simply launched.

--mark

https://codereview.chromium.org/11757004/diff/7001/chrome/browser/history/url...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/7001/chrome/browser/history/url...
chrome/browser/history/url_index_private_data.cc:92: search_string.substr(0,
cursor_position) + kWhitespaceUTF16 +
On 2013/01/04 23:47:39, Peter Kasting wrote:
> This doesn't insert a space, it inserts a whole string of whitespace
characters.
> 
> I think you want ASCIIToUTF16(" ").
> 
> This could be done most simply by passing |search_string| by value and then
> doing:
> 
>   if (...)
>     search_string.insert(cursor_position, ASCIIToUTF16(" ");
>   ...

Done.

[Mark P, 2013-02-06 01:21:17]

Hi Peter and Scott,

This is now ready for a real review.  I'd very much like this to be in by the
end of the week.

Scott, since you're probably be gone Thursday/Friday and this change needs your
approval stamp, can you please take the lead on this review?

It should be easy: the changes to HQP/InMemoryIndex are remarkably little (~5
lines, plus interface changes and tests), and the additions to
AutocompleteFieldTrial are simplistic (about a dozen lines of very obvious
code).

(FYI, I finished the TODOs that I had after Peter's tentative review:
- I double-checked that highlighting works
- I revised and added unit tests
- I added a field trial to control this behavior
- I updated the changelist description)

thanks,
mark

[sky, 2013-02-06 04:59:43]

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/autocomple...
File chrome/browser/autocomplete/history_quick_provider.cc (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/autocomple...
chrome/browser/autocomplete/history_quick_provider.cc:168:
autocomplete_input_.cursor_position());
If the cursor position factors into the results does this mean the query needs
to be rerun when the cursor position changes?

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/in...
File chrome/browser/history/in_memory_url_index.h (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/in...
chrome/browser/history/in_memory_url_index.h:122: size_t cursor_position);
Document what string16::npos means.

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/ur...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/ur...
chrome/browser/history/url_index_private_data.cc:96:
search_string.insert(cursor_position, ASCIIToUTF16(" "));
Is a space the right thing for all languages?

[Mark P, 2013-02-06 17:53:34]

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/autocomple...
File chrome/browser/autocomplete/history_quick_provider.cc (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/autocomple...
chrome/browser/autocomplete/history_quick_provider.cc:168:
autocomplete_input_.cursor_position());
On 2013/02/06 04:59:43, sky wrote:
> If the cursor position factors into the results does this mean the query needs
> to be rerun when the cursor position changes?

Kind of, yes.  But we decided that in order to avoid disruptive visual changes,
we'd only resend the omnibox query when the input text changes.  This means if
the user puts the cursor in the middle and deletes a character or types a new
character, we'd send a new query, but simply pressing left arrow to get the
middle will not go through tons of changing autocomplete suggestions.  This is
already how the omnibox edit model works, so this changelist needs no additional
changes for that.

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/in...
File chrome/browser/history/in_memory_url_index.h (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/in...
chrome/browser/history/in_memory_url_index.h:122: size_t cursor_position);
On 2013/02/06 04:59:43, sky wrote:
> Document what string16::npos means.

Done.

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/ur...
File chrome/browser/history/url_index_private_data.cc (right):

https://codereview.chromium.org/11757004/diff/21001/chrome/browser/history/ur...
chrome/browser/history/url_index_private_data.cc:96:
search_string.insert(cursor_position, ASCIIToUTF16(" "));
On 2013/02/06 04:59:43, sky wrote:
> Is a space the right thing for all languages?

Good question.

The answer is yes.  It's yes because of how the code below works--it first
breaks the string on character to non-character transitions and searches for
each substring (each word-like thing) separately.  This searching for word works
in all languages (the private_data data structures were built for this) and
words regardless of whether the breaks are at normal word boundaries or involve
searching for a few characters in the middle of a word.

The only funkiness I can imagine is if the cursor position is in the middle of a
character.  Is that possible in some IMEs?  Regardless, even if it's possible,
I'm not worried--the worst that can happen is that one gets weird or (more
likely) non-existent results when searching with a cursor in that position. 
(You'll need a match that involves the last half of the character followed by
the remaining text in the term.  This isn't likely to match anything.)

[sky, 2013-02-06 18:13:15]

LGTM

[Peter Kasting, 2013-02-06 18:34:27]

The "googlegle.com" case you describe seems to arise because, while we break the
user's input at the cursor position, we make no attempt to enforce that the
input substrings appear in order, non-overlapping.  Should we?  Or does the HQP
scoring mechanism produce a higher score for such cases, so we already sort of
have this condition, just as a relative scoring factor as opposed to an absolute
filter?

https://codereview.chromium.org/11757004/diff/20006/chrome/browser/autocomple...
File chrome/browser/autocomplete/autocomplete_field_trial.h (right):

https://codereview.chromium.org/11757004/diff/20006/chrome/browser/autocomple...
chrome/browser/autocomplete/autocomplete_field_trial.h:121: // Returns whether
HistoryQuick provider shoudl allow breaking the
Nit: shoudl

[Mark P, 2013-02-06 18:49:17]

On 2013/02/06 18:34:27, Peter Kasting wrote:
> The "googlegle.com" case you describe seems to arise because, while we break
the
> user's input at the cursor position, we make no attempt to enforce that the
> input substrings appear in order, non-overlapping.  Should we?  Or does the
HQP
> scoring mechanism produce a higher score for such cases, so we already sort of
> have this condition, just as a relative scoring factor as opposed to an
absolute
> filter?

You're correct, the HQP scoring mechanism has this case.  We sort and eliminate
overlaps.  The part of the term that is subsumed by another match (in this
example the "gle" from "gle.com") will get no credit for a match, dropping the
score of the http://www.google.com/ URL.  But that URL will still match.

--mark

https://codereview.chromium.org/11757004/diff/20006/chrome/browser/autocomple...
File chrome/browser/autocomplete/autocomplete_field_trial.h (right):

https://codereview.chromium.org/11757004/diff/20006/chrome/browser/autocomple...
chrome/browser/autocomplete/autocomplete_field_trial.h:121: // Returns whether
HistoryQuick provider shoudl allow breaking the
On 2013/02/06 18:34:27, Peter Kasting wrote:
> Nit: shoudl

Done.

[Peter Kasting, 2013-02-06 18:49:44]

OK.  LGTM.

[commit-bot: I haz the power, 2013-02-06 19:41:19]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/mpearson@chromium.org/11757004/19009

[Mark P, 2013-02-06 19:51:30]

By the way, thanks Scott and Peter for the prompt review!

--mark

[commit-bot: I haz the power, 2013-02-06 22:22:08]

Change committed as 181065