Re: handling many matches

Re: handling many matches

[Eli Zaretskii]

> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 01:16:07 +0300
> Cc: Jonas Bernoulli <jonas@bernoul.li>, Emacs developers <emacs-devel@gnu.org>,
>  Philippe Vaucher <philippe.vaucher@gmail.com>,
>  Adam Porter <adam@alphapapa.net>, Kyle Meyer <kyle@kyleam.com>,
>  Eli Zaretskii <eliz@gnu.org>
> 
> Whereas "other editors" have already solved this better (perhaps not 
> ideally, but better) by doing fuzzy matching with smart enough sorting. 
> We should start by matching that functionality, and only then add extra 
> capabilities, maybe.

IMNSHO, we should first develop the infrastructure for such "smart"
presentation of completion candidates and make it our default
completion strategy, and only after that consider changes, like the
proposed "namespacing" of APIs, that will allow users to use
completion as a substitute for Help commands.  It is IMO a bad idea to
flood the completion lists with many dozens of candidates and force
users to wade through them.  I certainly wouldn't call that "progress"
for Emacs.

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 09:29, Eli Zaretskii wrote:
> IMNSHO, we should first develop the infrastructure for such "smart"
> presentation of completion candidates and make it our default
> completion strategy,

How would that look, in your opinion?

> and only after that consider changes, like the
> proposed "namespacing" of APIs, that will allow users to use
> completion as a substitute for Help commands.

Namespacing of APIs is a step that should help the users with the 
current default completion strategy.

> It is IMO a bad idea to
> flood the completion lists with many dozens of candidates and force
> users to wade through them.  I certainly wouldn't call that "progress"
> for Emacs.

Is that what fido-mode does? People seem to like it.

Re: handling many matches

[Eli Zaretskii]

> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>  emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>  kyle@kyleam.com
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 16:26:54 +0300
> 
> On 02.05.2020 09:29, Eli Zaretskii wrote:
> > IMNSHO, we should first develop the infrastructure for such "smart"
> > presentation of completion candidates and make it our default
> > completion strategy,
> 
> How would that look, in your opinion?

If by "look" you mean to the user, then I envision a list of
completion candidates that somehow "knows" what I'm after, and places
those likely guesses near the beginning of the list.

> > and only after that consider changes, like the
> > proposed "namespacing" of APIs, that will allow users to use
> > completion as a substitute for Help commands.
> 
> Namespacing of APIs is a step that should help the users with the 
> current default completion strategy.

Like I said, I think the hopes it will deliver a significant enough
improvement are overrated.  It will certainly bloat the lists of
candidates by factors, which is why I think it isn't a very good idea
as long as we don't have some smart scoring of candidates.

> > It is IMO a bad idea to
> > flood the completion lists with many dozens of candidates and force
> > users to wade through them.  I certainly wouldn't call that "progress"
> > for Emacs.
> 
> Is that what fido-mode does? People seem to like it.

I don't have a good idea of what fido-mode does, but the rather foggy
idea I do have says it just applies fuzzy search criteria, attempting
to find non-literal matches.  If this is so, then I don't think fido
cuts it.  We need scoring that "learns" from what I do/did recently,
and from my habits.  Otherwise the list of candidates will remain
hopelessly long, with no promise of having what I'm really looking for
anywhere near the beginning.

Compare with the Internet search: it almost always brings me hundreds
of hits, but I normally find what I was after among the first dozen.
Even more spectacularly, when I type a search phrase into the search
box, it guesses what my search phrase will be, and the guesses are
almost always very accurate, so much so that if I don't see a long
enough list of reasonable candidates, I usually go looking for some
typo in what I typed (and almost always find it).  Some of the
candidates are based on my previous search phrases, and the ones I
typed are always ready to be reused, with a special indication to let
me know I recently used them.

It is this kind of powerful scoring that I think we need to develop if
we are going to handle many dozens of completion candidates.  Because
who has patience and time to wade through 100 candidates, let alone
1000?

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 16:52, Eli Zaretskii wrote:

> If by "look" you mean to the user, then I envision a list of
> completion candidates that somehow "knows" what I'm after, and places
> those likely guesses near the beginning of the list.

All fuzzy completion systems do that. Generally by scoring how well each 
string resembles the input string. Whether there are gaps between the 
matched characters, and so on. Our 'flex' completion style has this 
feature as well.

>>> and only after that consider changes, like the
>>> proposed "namespacing" of APIs, that will allow users to use
>>> completion as a substitute for Help commands.
>>
>> Namespacing of APIs is a step that should help the users with the
>> current default completion strategy.
> 
> Like I said, I think the hopes it will deliver a significant enough
> improvement are overrated.  It will certainly bloat the lists of
> candidates by factors, which is why I think it isn't a very good idea
> as long as we don't have some smart scoring of candidates.

The amount of "bloat" will be strictly limited by the number of aliases 
we add. I think there's a general agreement that we shouldn't go overboard.

>>> It is IMO a bad idea to
>>> flood the completion lists with many dozens of candidates and force
>>> users to wade through them.  I certainly wouldn't call that "progress"
>>> for Emacs.
>>
>> Is that what fido-mode does? People seem to like it.
> 
> I don't have a good idea of what fido-mode does, but the rather foggy
> idea I do have says it just applies fuzzy search criteria, attempting
> to find non-literal matches.  If this is so, then I don't think fido
> cuts it.

You can try it. It uses 'flex', and thus it sorts the matches based on 
scores.

> We need scoring that "learns" from what I do/did recently,
> and from my habits.  Otherwise the list of candidates will remain
> hopelessly long, with no promise of having what I'm really looking for
> anywhere near the beginning.

There are systems like that, including in third-party Emacs packages. 
Personally, I'm not fond of the idea (the unpredictability, first of 
all), and I'd rather we polish the current scoring algo first.

But it's good to have it customizable.

> Compare with the Internet search: it almost always brings me hundreds
> of hits, but I normally find what I was after among the first dozen.
> Even more spectacularly, when I type a search phrase into the search
> box, it guesses what my search phrase will be, and the guesses are
> almost always very accurate, so much so that if I don't see a long
> enough list of reasonable candidates, I usually go looking for some
> typo in what I typed (and almost always find it).  Some of the
> candidates are based on my previous search phrases, and the ones I
> typed are always ready to be reused, with a special indication to let
> me know I recently used them.

Right. There's some benefit in that. But also note that Internet 
searches can't really use fuzzy matching, at all. I'd venture to say 
that it will be difficult to combine fuzzy searches and historical 
scoring, too.

Re: handling many matches

[Eli Zaretskii]

> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>  emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>  kyle@kyleam.com
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 19:13:18 +0300
> 
> On 02.05.2020 16:52, Eli Zaretskii wrote:
> 
> > If by "look" you mean to the user, then I envision a list of
> > completion candidates that somehow "knows" what I'm after, and places
> > those likely guesses near the beginning of the list.
> 
> All fuzzy completion systems do that. Generally by scoring how well each 
> string resembles the input string.

That criterion alone is not enough, IME.  It is also important
(sometimes much more important) what I'm doing, in what major mode,
my previous completion attempts, etc.

> > Like I said, I think the hopes it will deliver a significant enough
> > improvement are overrated.  It will certainly bloat the lists of
> > candidates by factors, which is why I think it isn't a very good idea
> > as long as we don't have some smart scoring of candidates.
> 
> The amount of "bloat" will be strictly limited by the number of aliases 
> we add.

Yes, and I tend to think we will add a lot.

> I think there's a general agreement that we shouldn't go overboard.

Even if there is such an agreement, I'm not sure we will be able to
keep ourselves from going overboard.

> > We need scoring that "learns" from what I do/did recently,
> > and from my habits.  Otherwise the list of candidates will remain
> > hopelessly long, with no promise of having what I'm really looking for
> > anywhere near the beginning.
> 
> There are systems like that, including in third-party Emacs packages. 
> Personally, I'm not fond of the idea (the unpredictability, first of 
> all), and I'd rather we polish the current scoring algo first.

When the first few candidates are what I want, predictability goes out
the window.  I'm a happy user when I find what I'm looking for fast.

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 19:31, Eli Zaretskii wrote:

>> All fuzzy completion systems do that. Generally by scoring how well each
>> string resembles the input string.
> 
> That criterion alone is not enough, IME.  It is also important
> (sometimes much more important) what I'm doing, in what major mode,
> my previous completion attempts, etc.

Your argument here has merit. The difficulty is in writing an 
appropriate scoring algorithm.

The "what I'm doing" and "what major mode" conditions could be solved by 
pre-filtering in a lot of cases, though.

>>> Like I said, I think the hopes it will deliver a significant enough
>>> improvement are overrated.  It will certainly bloat the lists of
>>> candidates by factors, which is why I think it isn't a very good idea
>>> as long as we don't have some smart scoring of candidates.
>>
>> The amount of "bloat" will be strictly limited by the number of aliases
>> we add.
> 
> Yes, and I tend to think we will add a lot.

That's a self-defeating argument.

By the amount of resistance from your side, my impression so far is that 
we'll end up adding none (again).

>>> We need scoring that "learns" from what I do/did recently,
>>> and from my habits.  Otherwise the list of candidates will remain
>>> hopelessly long, with no promise of having what I'm really looking for
>>> anywhere near the beginning.
>>
>> There are systems like that, including in third-party Emacs packages.
>> Personally, I'm not fond of the idea (the unpredictability, first of
>> all), and I'd rather we polish the current scoring algo first.
> 
> When the first few candidates are what I want, predictability goes out
> the window.  I'm a happy user when I find what I'm looking for fast.

That rules out the "browsing an API" use case, when we need the "first 
20" or "first 40" candidates to be good.

IOW, the algorithms should be everything to everyone. Which is 
difficult, but we should try to approach it.

Re: handling many matches

[Eli Zaretskii]

> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>  emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>  kyle@kyleam.com
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 19:58:08 +0300
> 
> >>> Like I said, I think the hopes it will deliver a significant enough
> >>> improvement are overrated.  It will certainly bloat the lists of
> >>> candidates by factors, which is why I think it isn't a very good idea
> >>> as long as we don't have some smart scoring of candidates.
> >>
> >> The amount of "bloat" will be strictly limited by the number of aliases
> >> we add.
> > 
> > Yes, and I tend to think we will add a lot.
> 
> That's a self-defeating argument.
> 
> By the amount of resistance from your side, my impression so far is that 
> we'll end up adding none (again).

Read my lips: I do NOT resist.  I'm warning the enthusiasts that they
might end up with a situation that is not better and potentially worse
than what we have today, and that the existing C-h commands will still
need to be used a lot to make any sense out of the results.

Other than that, feel free to propose any number of aliases that you
think might make sense.  I promise not to object, just make comments
and speak my opinions about the proposed aliases.

> > When the first few candidates are what I want, predictability goes out
> > the window.  I'm a happy user when I find what I'm looking for fast.
> 
> That rules out the "browsing an API" use case, when we need the "first 
> 20" or "first 40" candidates to be good.

Yes, because that use case shouldn't be served by completion, IMO.  If
someone wants a complete list of APIs, we should present the list of
APIs.  Completion is for _using_ one of the candidates, not about
looking through the entire list.

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 20:25, Eli Zaretskii wrote:
> Other than that, feel free to propose any number of aliases that you
> think might make sense.  I promise not to object, just make comments
> and speak my opinions about the proposed aliases.

Very good. We should indeed pick and choose. And we've already done a 
lot of that in another thread.

> Yes, because that use case shouldn't be served by completion, IMO.  If
> someone wants a complete list of APIs, we should present the list of
> APIs.  Completion is for_using_  one of the candidates, not about
> looking through the entire list.

It's about finding it, though. The best one for one's purpose.

We don't have ideal options anyway: the manual is verbose, you have to 
skip a lot of text, and it doesn't cover *all* the functions available, 
just the basics defined in the core library.

Apropos is exhaustive, but unsorted.

RE: handling many matches

[Drew Adams]

> We need scoring that "learns" from what I do/did recently,
> and from my habits....
> 
> Compare with the Internet search: it almost always brings me hundreds
> of hits, but I normally find what I was after among the first dozen.

Relatively little of that power/accuracy comes
from it learning from your habits (your previous
searches etc.).  It mostly comes from back links,
i.e., how many links a URL has from other URLs.

Of course, links among web pages in turn reflect
user use patterns (including searches).  But not
just your own use patterns.

But yes, your and my search of the same words
will return different hits.  There is some input
from our individual past uses of the internet
and the search engine.

> Even more spectacularly, when I type a search phrase into the search
> box, it guesses what my search phrase will be, and the guesses are
> almost always very accurate,...  Some of the candidates are based
> on my previous search phrases, and the ones I typed are always ready 
> to be reused, with a special indication to let me know I recently
> used them.

Yes.  All of that can be food for thought for Emacs.
We already incorporate something similar with things
like dabbrev and library `completion.el'.  And even
minibuffer completion incorporates it in some cases,
promoting recent input history.

> It is this kind of powerful scoring that I think we need to develop if
> we are going to handle many dozens of completion candidates.

Yes and no.  Frequency of use and recency of use
are two (different) scoring criteria.  There are
_lots_ of different ways to score and sort.

So then you have the problem of how to tell
Emacs, in any given completion context, just
what to favor.

All of this is good to have.  And we need good
ways to choose among such possibilities,
including on the fly.

Re: handling many matches

[Eli Zaretskii]

> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>  emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>  kyle@kyleam.com
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 21:17:57 +0300
> 
> Apropos is exhaustive, but unsorted.

Then let's sort it.  The question is only: what is the key?

Re: handling many matches

[Eli Zaretskii]

> Date: Sat, 2 May 2020 11:21:36 -0700 (PDT)
> From: Drew Adams <drew.adams@oracle.com>
> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>         emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>         kyle@kyleam.com
> 
> > Compare with the Internet search: it almost always brings me hundreds
> > of hits, but I normally find what I was after among the first dozen.
> 
> Relatively little of that power/accuracy comes
> from it learning from your habits (your previous
> searches etc.).  It mostly comes from back links,
> i.e., how many links a URL has from other URLs.

AFAIK, this is outdated.  It's how search engines worked several years
ago.  They are much smarter nowadays.

> Of course, links among web pages in turn reflect
> user use patterns (including searches).  But not
> just your own use patterns.

I have evidence that my personal details and previous searches do
affect the results.

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 21:31, Eli Zaretskii wrote:
> Then let's sort it.  The question is only: what is the key?

Relevance to input, for example.

But how will we determine it, you will ask? For instance, by seeing 
where the search words are in the each listed name. If they are close to 
the beginning, assign higher scores.

As you can see, this will fit namespace-based naming quite well.

Re: handling many matches

[Eli Zaretskii]

> Cc: drew.adams@oracle.com, monnier@iro.umontreal.ca, jonas@bernoul.li,
>  emacs-devel@gnu.org, philippe.vaucher@gmail.com, adam@alphapapa.net,
>  kyle@kyleam.com
> From: Dmitry Gutov <dgutov@yandex.ru>
> Date: Sat, 2 May 2020 21:39:06 +0300
> 
> On 02.05.2020 21:31, Eli Zaretskii wrote:
> > Then let's sort it.  The question is only: what is the key?
> 
> Relevance to input, for example.
> 
> But how will we determine it, you will ask? For instance, by seeing 
> where the search words are in the each listed name. If they are close to 
> the beginning, assign higher scores.

You are still thinking about what our fuzzy completion does.  That's
not how you get scores that are relevant for the user, because how
close the hit is to what the user typed is mostly irrelevant.

RE: handling many matches

[Drew Adams]

> > Relatively little of that power/accuracy comes
> > from it learning from your habits (your previous
> > searches etc.).  It mostly comes from back links,
> > i.e., how many links a URL has from other URLs.
> 
> AFAIK, this is outdated.  It's how search engines
> worked several years ago.  They are much smarter nowadays.

"Relatively" is the key word there.  And "mostly".

> > Of course, links among web pages in turn reflect
> > user use patterns (including searches).  But not
> > just your own use patterns.
> 
> I have evidence that my personal details and previous searches do
> affect the results.

Did you read where I acknowledged that?  Clearly
the search engine's knowledge of you, your location,
your search history, your browser history, etc.
have a large influence on what hits you get and the
order you see them presented.

Regardless, your and my searches, in general, will
have a lot of hits in common, and so will the order.

RE: handling many matches

[Drew Adams]

> You are still thinking about what our fuzzy completion does.  That's
> not how you get scores that are relevant for the user, because how
> close the hit is to what the user typed is mostly irrelevant.

Hear, hear!  Maybe not "mostly" - depends on the use case.
But certainly _in general_.

Yes, relevance (score) varies, depending on the use
case.  In general, what's relevant is scoring the thing
that is represented by its name, not the name itself.

And how is that relevance determined?  Typically, you
need to use the PREDICATE arg to `completing-read', to
match not only the name but also the accompanying data
in an alist entry - data that can be super rich.

Of course, that works only for an alist arg, not for
an obarray, hash table, etc.  But there are hacks for
those other arg types (property on a symbol or string
candidate, for example).

Re: handling many matches

[Dmitry Gutov]

On 02.05.2020 21:46, Eli Zaretskii wrote:
>> Relevance to input, for example.
>>
>> But how will we determine it, you will ask? For instance, by seeing
>> where the search words are in the each listed name. If they are close to
>> the beginning, assign higher scores.
> You are still thinking about what our fuzzy completion does.  That's
> not how you get scores that are relevant for the user, because how
> close the hit is to what the user typed is mostly irrelevant.

It's rarely 100% irrelevant. Or else that would mean we have some 
nonsensical names.

But apparently you have some other algorithm in mind. Though I don't 
know what it is.