handling many matches [was: [ELPA] New package: transient]

handling many matches [was: [ELPA] New package: transient]

[Drew Adams]

> > But then you have the reverse problem: after typing `file-name` in
> > fido-mode you get too many false-positive for functions which aren't
> > "manipulating file names" but merely return a file-name.
> 
> That's a fair point, but still the discoverability is not too bad.
> Given weighted sorting, the relevant functions are mostly at the top,
> see the screenshot.
> 
> Although we might want to look into why backup-file-name-p is sorted
> before file-name-quoted-p.

A comment on the general situation here, hoping it helps -

The problem of getting many matches is a general
one, and one that's more prevalent when matching
methods get extended or combined.

Just extending from prefix to substring matching
can increase the number of matches greatly.  Fuzzy
and regexp matching can both add to the problem and
sometimes help reduce it.

(The "problem" is also a helpful feature, and an
opportunity, of course.)

Icicles has had to deal with this inherent problem
and opportunity longer than other completion
frameworks, and a few of its features can really
help to tame it.  I mention them here because,
regardless of how they might be implemented or
presented to users (the UI), I think similar
features could help Emacs.

1. Progressive matching, i.e., narrowing the set
   of candidates by matching another pattern.
   (Rinse and repeat.)

   Matching multiple simple patterns is both much
   easier and more flexible/powerful than trying
   to come up with a single complex pattern (or
   fewer but more complex patterns).

2. Pruning, by excluding matches.

   This builds on #1.  You add another pattern to
   match (#1), then hit a key to subtract the
   resulting set of matches from the previous set.

   In your screenshot, for example, if you know
   you're not interested in the `tramp' matches,
   you just use #1 to add matching `tramp' as an
   additional requirement, then hit a key (`C-~'
   in Icicles) to prune those matches.  Similarly
   for other, easy to recognize blocks of matches.

   It's very quick to filter matches this way, and
   it would be impossible, in the general case, to
   get the same result by any particular completion
   style/method.  Only you know what it makes sense
   to prune, in any given context.

   At each step of additional matching (i.e. #1)
   you can hit a key (Icicles uses `C-g') to annul
   that match requirement.  For example, after you
   match `tramp', if you hit `C-g' then the matches
   return to including `tramp'.  (If you see that
   you want to keep some but not all of the `tramp'
   matches then you can just use #1 again to narrow
   further.

3. On-demand help on individual candidates.

   Be able to hit a help key to get a short or
   long description for a given candidate.  This
   of course requires some way to indicate/pick
   a single candidate just for help.

   In Icicles there are several ways to do this,
   including (a) cycling among them and (b) #1
   above, followed by a help key, followed by
   `C-g' - i.e., narrow to a single candidate,
   show its description, then widen back.

   This feature is not a way to add/subtract
   multiple matches all at once.  It's more of a
   tell-me-more, to help you decide about further
   matching.

In Icicles there are many more ways to manipulate
a set of matches, to tame the plethora problem.
But I wanted to mention those 3 - particularly the
first 2.

___

Now a word about sorting in this context, since
you mention it.

Sorting is important for many reasons, especially,
but not only, in a context where you can (or must)
access candidates in order, e.g., cycle among them.

You mention orders based on candidate scoring:

  "Given weighted sorting, the relevant functions
   are mostly at the top"

That can be helpful, but I think it's often
overrated.  The view that it's important or very
helpful can just be the result of making a
virtue out of necessity: In contexts where the
main or only candidate access is by cycling, it
follows that order is very important - just for
ease/speed of access.

But when other powerful ways of accessing are
available (e.g. easy narrowing - #1, #2), the
sort order can serve various other, otherwise
useful and interesting purposes than just
accessing a candidate.

Beyond just contrasting ease of access: Scoring
tries to measure relevancy, but real candidate
relevancy in many contexts can go beyond any
what any name-matching regime can offer.  Real
relevancy can often be about matching things
about candidates that aren't contained in their
names.

The PREDICATE arg for `completing-read', etc.
makes it possible to match based on more than
just candidate names.  But unless some hoops
are jumped through, candidate sorting is based
only on names.  PREDICATE constrains matches,
but the result is a set of names, and those are
what get scored.

Which brings up a related point: the purpose of
completion - showing matching candidates.  If
the only purpose is to choose a candidate, that
colors what one thinks is important/helpful.
Other purposes come from the value of seeing
and manipulating a _set_ of things.

And sort order fits in here: It can be useful
to present a set of candidates in different
ways, including different orders, for different
purposes.  It's not just about sequential order
for accessing a candidate.

Consequently, it can be helpful to be able to
change the sort order on the fly (during
completion/matching), in order to present the
same set of matches in different ways.

These 2 Icicles pages give an idea of other
uses of sort orders.  They describe or show
orders that help you see relations among
candidates in a given set of matches.  (And
yes, such sorts do often involve candidate
info that goes beyond names.)

https://www.emacswiki.org/emacs/Icicles_-_Sorting_Candidates#DifferentSortsForDifferentUses

https://www.emacswiki.org/emacs/Icicles_-_Key_Completion#Sorting

Re: handling many matches [was: [ELPA] New package: transient]

[Dmitry Gutov]

On 01.05.2020 20:20, Drew Adams wrote:
> 1. Progressive matching, i.e., narrowing the set
>     of candidates by matching another pattern.
>     (Rinse and repeat.)
> 
> 2. Pruning, by excluding matches.
> 
> 3. On-demand help on individual candidates.

This is all high-maintenance. It requires the user to master the 
matching interface first, with extra keys and new behaviors.

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.

RE: handling many matches [was: [ELPA] New package: transient]

[Drew Adams]

> > 1. Progressive matching, i.e., narrowing the set
> >    of candidates by matching another pattern.
> > 2. Pruning, by excluding matches.
> 
> This is all high-maintenance. It requires the user to master the
> matching interface first, with extra keys and new behaviors.

No, it doesn't require anything special from users.
It's pretty natural.  One key to separate match
patterns.  Another to remove the last set of matches.
Any keys will do.  And no requirement to use either.

Some completion frameworks offer #1, using SPC or
comma as the key.  Icicles uses S-SPC, by default,
so SPC can self-insert as part of a candidate.

(I don't know of other frameworks that offer #2,
but perhaps there are some.)

> 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.

I disagree (as I said) that any fuzzy matching,
with or without scoring, "solves this", at all.
___


And for the record, Icicles also offers fuzzy
matching - 7 kinds, including some that use
scoring.

https://www.emacswiki.org/emacs/Icicles_-_Completion_Methods_and_Styles#FuzzyCompletion

This is not about touting Icicles.  But for some
perspective, the relative worth of fuzzy matching
compared to progressive matching (#1) and pruning
(#2) is maybe 1 to 100.  Icicles provides a space
to compare them.

Of course, it depends on the domain of candidates;
for some domains fuzzy matching can be quite
helpful.  But even then it's better to be able to
use more than one matching (fuzzy or not) and be
able to prune matches (fuzzy or not).  Being able
to do such things doesn't mean you're required to.

In sum, fuzzy matching is a red herring, here -
completely orthogonal to the point made.

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

[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

[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

[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.