Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 03.02.2019 02:28, Jo�o T�vora wrote:
> +          ;; Sort again in case the completion style has propertized
> +          ;; completions with a 'completion-style-sort-order.
> +          (setq completions
> +                (sort completions
> +                      (lambda (a b)
> +                        (let ((va (get-text-property 0 'completion-style-sort-order a))
> +                              (vb (get-text-property 0 'completion-style-sort-order b)))

Shouldn't we be concerned that this overrides display-sort-function 
returned by the completion table?

Maybe some sort of customizable mechanism is in order, similar to 
completion-styles.

Or more simply, we just leave it to the completion table's author to set 
display-sort-function to a special value that makes use of these 
properties. It's not like setting it to a different value is going to 
make sense in this case.

> +          ;; Annotate completions with <...>
> +          ;; the completion style annotation.

Is this for debugging?

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 03.02.2019 02:28, Jo�o T�vora wrote:
>> +          ;; Sort again in case the completion style has propertized
>> +          ;; completions with a 'completion-style-sort-order.
>> +          (setq completions
>> +                (sort completions
>> +                      (lambda (a b)
>> +                        (let ((va (get-text-property 0 'completion-style-sort-order a))
>> +                              (vb (get-text-property 0 'completion-style-sort-order b)))
>
> Shouldn't we be concerned that this overrides display-sort-function
> returned by the completion table?

Perhaps.  But it only does so when the completion style explicitly
wanted it.  And even so, the sort order should be stable, i.e. if the
completion style puts numerically equal values in two completions, they
should retain the backend's order.  And, obviously, it it doesn't put
any values in that property, then the backend's order is also retained.

In my experience, at least for the "flex" (also called "scatter", by the
way) completion style, the frontend's sorting takes precedence

> Maybe some sort of customizable mechanism is in order, similar to
> completion-styles.

It is already customizable: you don't have to use "flex" completion
style.  Let's first try it out and then see if we need _more_
customization.

> Or more simply, we just leave it to the completion table's author to
> set display-sort-function to a special value that makes use of these
> properties. It's not like setting it to a different value is going to
> make sense in this case.
>
>> +          ;; Annotate completions with <...>
>> +          ;; the completion style annotation.
>
> Is this for debugging?

At the moment, yes mostly.  But it could not be.  In SLY, I give users
an indication of how the scoring algorithm is working.  See it in
action:

https://raw.githubusercontent.com/joaotavora/sly/master/doc/animations/company-flex-completion.gif

João

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 06.02.2019 13:09, João Távora wrote:

> Perhaps.  But it only does so when the completion style explicitly
> wanted it.  And even so, the sort order should be stable, i.e. if the
> completion style puts numerically equal values in two completions, they
> should retain the backend's order.  And, obviously, it it doesn't put
> any values in that property, then the backend's order is also retained.

To put it simply, we already have a way to indicate the completions 
sorting: provide a particular property, or metadata. I'd prefer not to 
couple completion style with sorting, because someone somewhere might 
prefer to go without it (and use some other sorting options, e.g. by 
frequency of use or mentions in the buffer).

> In my experience, at least for the "flex" (also called "scatter", by the
> way) completion style, the frontend's sorting takes precedence

Not sure what you mean by frontend here.

> It is already customizable: you don't have to use "flex" completion
> style.  Let's first try it out and then see if we need _more_
> customization.

I'd rather we start with the "more simply" alternative I've mentioned. 
But others are welcome to add their opinions.

>> Is this for debugging?
> 
> At the moment, yes mostly.  But it could not be.  In SLY, I give users
> an indication of how the scoring algorithm is working.  See it in
> action:
> 
> https://raw.githubusercontent.com/joaotavora/sly/master/doc/animations/company-flex-completion.gif

It's kind of neat, but to be honest I don't see how these percentages 
help a random user.

Even if they do, there's no need to couple this annotation addition to 
the completion style. Just use a new annotation function that looks up 
the text properties that the style adds, and adds them on.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 06.02.2019 13:09, João Távora wrote:
>
>> Perhaps.  But it only does so when the completion style explicitly
>> wanted it.  And even so, the sort order should be stable, i.e. if the
>> completion style puts numerically equal values in two completions, they
>> should retain the backend's order.  And, obviously, it it doesn't put
>> any values in that property, then the backend's order is also retained.
>
> To put it simply, we already have a way to indicate the completions
> sorting: provide a particular property, or metadata.

Perhaps I'm missing something, and that is taiting all the remaining
discussion.  Aren't these properties/metadata thingies specific to the
completion table (files, buffers, code completions, etc)?

> I'd prefer not to couple completion style with sorting, because
> someone somewhere might prefer to go without it (and use some other
> sorting options, e.g. by frequency of use or mentions in the buffer).




>
>> In my experience, at least for the "flex" (also called "scatter", by the
>> way) completion style, the frontend's sorting takes precedence
>
> Not sure what you mean by frontend here.

I meant the completion style.  Though technically the completion style
is a degree short of a frontend, because it is a way to select the
completions collected by the backend (the completion table in Emacs
parlance) and pass them to the graphical frontend, be it icomplete's,
the *Completions* buffer or company.

In otherwords I should be able to mix and match

- frontends
- completion styles
- backends

Right?  Well all I'm saying is that, when using the flex/scatter
completion style, it's almost always, if not always always, a better
idea to stable-sort by flex-match score.

One good way to see this is to try my code with your company.el package,
which doesn't (hopefully _doesn't yet_) use the completion style's
sorting hints.  You can try it in Emacs Lisp. First do:

   (setq completion-styles '(flex))

Now go into the *scratch* buffer and type "undo". You'll see it's not
very useful: the first match you get is ":argument-precedence-order", a
legitimate match, for sure, but you probably meant something related to
the undo facilities.  And you have to scroll quite a bit before you to
"buffer-undo-list", which is buried deep in the many many b's that
match.

>> It is already customizable: you don't have to use "flex" completion
>> style.  Let's first try it out and then see if we need _more_
>> customization.
>
> I'd rather we start with the "more simply" alternative I've
> mentioned. But others are welcome to add their opinions.

Eventually, we can add a keybinding to resort exclusively according to
the table or exclusively according to the completion style.

>>> Is this for debugging?
>>
>> At the moment, yes mostly.  But it could not be.  In SLY, I give users
>> an indication of how the scoring algorithm is working.  See it in
>> action:
>>
>> https://raw.githubusercontent.com/joaotavora/sly/master/doc/animations/company-flex-completion.gif
>
> It's kind of neat, but to be honest I don't see how these percentages
> help a random user.

I can agree they should be improved.  It would be good to integrate some
prior art regarding flex string matching that has a good measure
of the match quality.  The one in the prototype is a empirical thing
that works quite OK for Common Lisp and myself.  `string-distance', for
instance, gives the the Levenshtein distance.  It's got a fancy name,
but it's not very useful for flex completion before

  (string-distance "foo" "barfoo") = (string-distance "foo" "frodos")

And we want "barfoo" to come first.  string-distance talks about
"deletions, insertions and substitutions required to transform a string
into another".  Perhaps if it measured also "move operations" it would
be a better measure.

Then instead of the percentage, we could show just the number of 1-char
editing operations, including moves, to turn the pattern into the
candidate.  That's a measure with actual meaning.

> Even if they do, there's no need to couple this annotation addition to
> the completion style. Just use a new annotation function that looks up
> the text properties that the style adds, and adds them on.

Again, this would only affect the specific completion table that I'm
writing this function for, right?  Or can I write metadata functions for
completion styles?

João

new-flex-completion-style (was: [Emacs-diffs] scratch/ 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness)

[Stefan Monnier]

>     Score, sort and annotate flex-style completions according to match
>     tightness

Sorting is a complicated matter here: we have completion tables,
completion styles, and completion front-ends, and all three seem to want
to be able to sort.

Obviously, the front-end has ultimate control, so we can't stop it from
sorting the way it likes, but we'd like it to be able to make an
informed choice.

As for sorting by the completion table or sorting by the completion
style, it's hard to figure out what should be done in general.
FWIW, it seems that all the completion tables that care about sorting do
it by sorting directly in `all-completions` and then setting the
*-sort-function to `identity`.  Presumably this can only DTRT for "flat"
completion tables.

W.r.t the UI sorting minibuffer.el has 2 different UIs with 2 different
sorting behaviors: there's the *Completions* buffer where results are
sorted alphabetically, and there's the force-complete cycling which
sorts by most-recently seen (using the minibuffer history variable) and
by length.

All this was designed in the context of completion tables and styles
where all returned candidates are basically equally likely.

Flex is going in the direction of completion systems where instead of
splitting the candidates between "possible matches" and "impossible
matches", the matches are all considered as possible, with some more
likely than others.

So in such a context, it's of utmost importance for the completion
table-or-style to provide its own sorting.  And in that case, I guess
most UIs should simply follow that sorting (instead of the current
situation where each UI uses its own sorting).

Still, in a case such as lisp/ecomplete.el where the completion table
provides its own sorting based on recent-usage-frequency, how should
this sorting be combined with that of flex?  I can see arguments in
favor of saying that the flex-weight should be ignored in favor of the
usage-frequency.

>     Up until now, there was no way for completion styles to control
>     sorting.  This change add such a facility and activated it for the new
>     "flex" completion style.

I'd like to move towards a completion-style API that uses cl-generic.
E.g. introduce generic functions like `completion-style-try-completion`
which would be like `completion-try-completion` but takes an additional
`style` argument and dispatches based on it (replacing the dispatch
based on completion-style-alist).

Maybe the sorting code (currently in minibuffer-completion-help) should
be moved to such a generic function, so the completion style would have
the choice of how it uses the `display-sort-function`.  But then should
we do the same with the sorting done in
`completion-all-sorted-completions` or should we come up with a single
generic function that covers both needs?

>     * lisp/minibuffer.el (minibuffer-completion-help): Use
>     completion-style-sort-order and compeltion-style-annotation
                                      ^^^^^^^^^^
                                      completion
>     properties.
>     (completion-pcm--hilit-commonality): Propertize completion with
>     'completion-pcm-commonality-score.
>     (completion-flx-all-completions): Porpertize completion with
                                        ^^^^^^^^^^
                                        Propertize

>     completion-style-sort-order and completion-style-annotation.

Regarding annotations, I think being able to `concat` at the end is
too limited.  If you take your example from sly, we'd like the "15%"
annotations to be right-aligned and I don't see an easy way to do that
with the facility you introduce.

The current annotation facility is also too limited in another way: in
read-char-by-name we annotate each char name with the actual char it
names, but we'd really like to prepend this annotation rather than
append it (it would make the chars much easier to see and to compare),
but the current annotation system doesn't offer this flexibility.

So I'd encourage you to come up with a more flexible annotation system
that allows prepending annotations as well as right-alignment (and
ideally combinations of those, with several columns, ...).


        Stefan

Re: new-flex-completion-style

[João Távora]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> W.r.t the UI sorting minibuffer.el has 2 different UIs with 2 different
> sorting behaviors: there's the *Completions* buffer where results are
> sorted alphabetically, and there's the force-complete cycling which
> sorts by most-recently seen (using the minibuffer history variable) and
> by length.

Tangent: When using icomplete (who else here uses icomplete?), this is
(the length) not good at all for switching buffers.  I want it to behave
like ido, where the natural order of buffer-list is preserved when the
buffer can't be found in the minibuffer-history-variable.  IOW for the
icomplete UI, sorting by length makes little sense.  It may make sense
for completion-at-point cycling.  I'm working on a patch for this.

> All this was designed in the context of completion tables and styles
> where all returned candidates are basically equally likely.
>
> Flex is going in the direction of completion systems where instead of
> splitting the candidates between "possible matches" and "impossible
> matches", the matches are all considered as possible, with some more
> likely than others.
> So in such a context, it's of utmost importance for the completion
> table-or-style to provide its own sorting.  And in that case, I guess
> most UIs should simply follow that sorting (instead of the current
> situation where each UI uses its own sorting).

The only problem is that completion-style doesn't have a point to
plug-in sorting yet.  So I thought good place to start is to place hints
in the completion-candidates.

> Still, in a case such as lisp/ecomplete.el where the completion table
> provides its own sorting based on recent-usage-frequency, how should
> this sorting be combined with that of flex?  I can see arguments in
> favor of saying that the flex-weight should be ignored in favor of the
> usage-frequency.

ecomplete has its own UI in ecomplete-display-matches? It's a question
of using or discarding the completion-style sorting hints stored in each
candidate.

My view of the matter is: completion table provides its sorting which
_can_ be overriden by completion style's sorting which _can_ be
overriden by completion UI's sorting.  AFAIU this can be done by writing
comparison functions that return nil if the current sorting should be
agnostic to both elements.

>>     Up until now, there was no way for completion styles to control
>>     sorting.  This change add such a facility and activated it for the new
>>     "flex" completion style.
>
> I'd like to move towards a completion-style API that uses cl-generic.
> E.g. introduce generic functions like `completion-style-try-completion`
> which would be like `completion-try-completion` but takes an additional
> `style` argument and dispatches based on it (replacing the dispatch
> based on completion-style-alist).

This is a good change, but it's not absolutely necessary to what I am
proposing right now.

>>     * lisp/minibuffer.el (minibuffer-completion-help): Use
>>     completion-style-sort-order and compeltion-style-annotation
>                                       ^^^^^^^^^^
>                                       completion
>>     properties.
>>     (completion-pcm--hilit-commonality): Propertize completion with
>>     'completion-pcm-commonality-score.
>>     (completion-flx-all-completions): Porpertize completion with
>                                         ^^^^^^^^^^
>                                         Propertize

Thanks.

>>     completion-style-sort-order and completion-style-annotation.
> Regarding annotations, I think being able to `concat` at the end is
> too limited.  If you take your example from sly, we'd like the "15%"
> annotations to be right-aligned and I don't see an easy way to do that
> with the facility you introduce.

I don't see the problem fully, but probably I'd rather remove the
annotation completely for now, until we have a better of how where we
want to place it.  As Dmitry suggested, the flex score annotation is
mostly a gimmick, we shouldn't add it until we have a good idea of how
it should work.
>
> The current annotation facility is also too limited in another way: in
> read-char-by-name we annotate each char name with the actual char it
> names, but we'd really like to prepend this annotation rather than
> append it (it would make the chars much easier to see and to compare),
> but the current annotation system doesn't offer this flexibility.
>
> So I'd encourage you to come up with a more flexible annotation system
> that allows prepending annotations as well as right-alignment (and
> ideally combinations of those, with several columns, ...).

What do you suggest?  I'd prefer small things that can be added
incrementally.  IOW, I don't have time for grand designs right now, I'm
mostly scratching the personal itch that is making icomplete.el not make
me miss ido.el so much.

So to summarize, I propose to add (1) the fafa9ec commit introducing
flex completion and (2) a new commit extracted from 2c7577558 which adds
the flex scoring calculation to each match, but doesn't do anything with
it yet.  Deal?

The first commit by itself can already greatly improve icomplete Ui.
And the second commit should encourage UI devs to start taking the
completion-style-sort-order hint into account.  If Dmitry does that in
company-capf, we get decent flex completion for little cost.

João

RE: new-flex-completion-style (was: [Emacs-diffs] scratch/ 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness)

[Drew Adams]

FWIW -

I guess you're arguing for an ability to sort completion candidates at multiple places/levels, including far upstream from interactive use.

My concern/interest is more about interactive use, where sorting can usefully interact with progressive filtering.  I like late binding. ;-)

In my context (Icicles) users can filter completion candidates incrementally in various ways, and sorting can act either on "raw" completion candidates (e.g. alist entries, including their cdrs) or on displayed candidates (e.g. text in *Completions*).

Unlike vanilla Emacs, the same sort order applies (intentionally) for displaying matching completions and for cycling among those candidates.

Users can switch among any number of sort orders (predicates) interactively.

The default set of sort orders available for this switching is defined by a user option.  But the code context (e.g. code that calls `completing-read') can change this set.  So different commands can make different sets of sort orders available.

Users can define new sort orders with a macro, which adds them to those made available by the user option.

Maybe some such capabilities would be relevant to your context; dunno.

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

Re: new-flex-completion-style

[Dmitry Gutov]

On 12.02.2019 01:16, João Távora wrote:
> And the second commit should encourage UI devs to start taking the
> completion-style-sort-order hint into account.  If Dmitry does that in
> company-capf, we get decent flex completion for little cost.

Note that if you adopt the approach I suggested (leave sorting to the 
display-sort-function), it will work with company-capf automatically.

And this can work in two ways: either the completion style adds text 
properties and the sort function looks it up, or the completion style 
(?) or the completion table does the sorting right away, and the 
display-sort-function is #'identity.

Re: new-flex-completion-style

[João Távora]

On Mon, Feb 11, 2019 at 11:02 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
>
> On 12.02.2019 01:16, João Távora wrote:
> > And the second commit should encourage UI devs to start taking the
> > completion-style-sort-order hint into account.  If Dmitry does that in
> > company-capf, we get decent flex completion for little cost.
>
> Note that if you adopt the approach I suggested (leave sorting to the
> display-sort-function), it will work with company-capf automatically.
>
> And this can work in two ways: either the completion style adds text
> properties and the sort function looks it up, or the completion style
> (?) or the completion table does the sorting right away, and the
> display-sort-function is #'identity.

Apparently there is something I am still missing about
display-sort-function. I admit to not have looked very hard at it. This
is probably why I didn't understand your suggestion.

Why don't we do this:  I add the two (presumably) unproblematic commits
(the new flex style + propertize completions with a numeric property), you
show me a patch where display-sort-function is plugged into the style,
supposing it is not very hard to do.  Deal?

João


-- 
João Távora

Re: new-flex-completion-style

[Dmitry Gutov]

On 12.02.2019 02:11, João Távora wrote:
> Why don't we do this:  I add the two (presumably) unproblematic commits
> (the new flex style + propertize completions with a numeric property), you
> show me a patch where display-sort-function is plugged into the style,
> supposing it is not very hard to do.  Deal?

Not plugged, but is integrated with. But sure.

Re: new-flex-completion-style

[Óscar Fuentes]

João Távora <joaotavora@gmail.com> writes:

> I don't see the problem fully, but probably I'd rather remove the
> annotation completely for now, until we have a better of how where we
> want to place it.  As Dmitry suggested, the flex score annotation is
> mostly a gimmick, we shouldn't add it until we have a good idea of how
> it should work.

Do you know flx [1] ? Would it be possible to implement it on top of
your work by providing a score function and/or a sort function?

1. https://github.com/lewang/flx

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 06.02.2019 22:47, João Távora wrote:

> Perhaps I'm missing something, and that is taiting all the remaining
> discussion.  Aren't these properties/metadata thingies specific to the
> completion table (files, buffers, code completions, etc)?

metadata - yes, properties - no (those are extra elements at the end of 
the list returned by completion-at-point-functions).

See completion--metadata and completion-extra-properties.

display-sort-function, for now, can only be a metadata element (though 
that shouldn't be hard to change). annotation-function, however, can be 
either.

So as things stand, the use of this completion style that'd see in mind, 
is when a particular completion function returns a table that indicates 
a particular category (for which the use of flex completion style is 
enabled), and a particular display-sort-function in its metadata.

Consequently, a preexisting completion tables wouldn't be supported. But 
like I said, it shouldn't be hard to change either.

> In otherwords I should be able to mix and match
> 
> - frontends
> - completion styles
> - backends
> 
> Right?  Well all I'm saying is that, when using the flex/scatter
> completion style, it's almost always, if not always always, a better
> idea to stable-sort by flex-match score.

I dunno, sorting takes CPU time anyways. Not sure a combination of 
several sorting functions will frequently give a better result than just 
one of them.

> One good way to see this is to try my code with your company.el package,
> which doesn't (hopefully _doesn't yet_) use the completion style's
> sorting hints.  You can try it in Emacs Lisp. First do:
> 
>     (setq completion-styles '(flex))
> 
> Now go into the *scratch* buffer and type "undo". You'll see it's not
> very useful: the first match you get is ":argument-precedence-order", a
> legitimate match, for sure, but you probably meant something related to
> the undo facilities.  And you have to scroll quite a bit before you to
> "buffer-undo-list", which is buried deep in the many many b's that
> match.

But then, if you enable company-sort-by-occurrence via 
company-transformers, the completion style's sorting won't be visible 
anymore anyway.

It's a question whether any other sorting approaches end up being 
helpful, but maybe some hybrid functions will work, where both 
occurrences and flex score are taken into account.

> Eventually, we can add a keybinding to resort exclusively according to
> the table or exclusively according to the completion style.

In the approach I'm thinking of, both options are the same sorting function.

> And we want "barfoo" to come first.  string-distance talks about
> "deletions, insertions and substitutions required to transform a string
> into another".  Perhaps if it measured also "move operations" it would
> be a better measure.

That's helpful to consider for the actual scores, and sorting.

> Then instead of the percentage, we could show just the number of 1-char
> editing operations, including moves, to turn the pattern into the
> candidate.  That's a measure with actual meaning.

And still, seeing it wouldn't help me if I'm just writing code. Sorry 
for being blunt.

Sort by them, sure. But show the values to the user? Why?

>> Even if they do, there's no need to couple this annotation addition to
>> the completion style. Just use a new annotation function that looks up
>> the text properties that the style adds, and adds them on.
> 
> Again, this would only affect the specific completion table that I'm
> writing this function for, right?  Or can I write metadata functions for
> completion styles?

The former, more or less. This creates a certain limitation, sure, but 
it shouldn't be a problem for Eglot.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Stefan Monnier]

> See completion--metadata and completion-extra-properties.

But a completion style like `flex` can't affect either of those.
And I expect some people will want to put in their `completion-styles`,
so `flex` should work well for all/most completion tables and all/most
completion-at-point-functions (and calls to completing-read).

> I dunno, sorting takes CPU time anyways. Not sure a combination of several
> sorting functions will frequently give a better result than just one
> of them.

I think I agree here: the stability of the `flex` sort is likely to make
little difference in practice (more specifically, the sets of matches
which share the same flex-score will be sufficiently numerous and small
that the sorting within them is not significant).

> But then, if you enable company-sort-by-occurrence via company-transformers,
> the completion style's sorting won't be visible anymore anyway.

I think this is OK: the front-end can indeed override the
sorting chosen by the completion-style and the completion-table.
If the result is poor, it's the front-end's problem and it is in
a position to fix it.

> It's a question whether any other sorting approaches end up being helpful,
> but maybe some hybrid functions will work, where both occurrences and flex
> score are taken into account.

Not sure how that can be done in a modular way: how can we specify an
API where `flex` can provide its scores, `sort-by-occurrence` can
specify its scores, they don't know about each other, and yet the two
sets of scores get mixed in a useful way?


        Stefan

Re: new-flex-completion-style

[Stefan Monnier]

>> W.r.t the UI sorting minibuffer.el has 2 different UIs with 2 different
>> sorting behaviors: there's the *Completions* buffer where results are
>> sorted alphabetically, and there's the force-complete cycling which
>> sorts by most-recently seen (using the minibuffer history variable) and
>> by length.
> Tangent: When using icomplete (who else here uses icomplete?), this is
> (the length) not good at all for switching buffers.

Not sure if it's related to icomplete.  Maybe the length-heuristic is
just not good for buffer names.  It was mostly motivated by experience
with M-x where I do believe that there is a correlation between command
name length and frequency of use of that command.

I think this length heuristic also works reasonably well in several
other circumstances (e.g. file names).

[ I'm clearly talking about the TAB-cycling use case, but I can't think
  of a good reason why the icomplete-mode should be very different.  ]

> I want it to behave like ido, where the natural order of buffer-list
> is preserved when the buffer can't be found in the
> minibuffer-history-variable.

How 'bout we change the buffer name completion table so it specifies its
own cycle-sort-function which uses buffer-list, then.  It seems like it
would be a clear win (the buffer-list order is a much better heuristic
than the length).

> The only problem is that completion-style doesn't have a point to
> plug-in sorting yet.

That's right.

> So I thought good place to start is to place hints
> in the completion-candidates.

It's probably a good idea, yes.

>> Still, in a case such as lisp/ecomplete.el where the completion table
>> provides its own sorting based on recent-usage-frequency, how should
>> this sorting be combined with that of flex?  I can see arguments in
>> favor of saying that the flex-weight should be ignored in favor of the
>> usage-frequency.
> ecomplete has its own UI in ecomplete-display-matches?

It also offers a completion-table (which I use via
a completion-at-point-function).

> My view of the matter is: completion table provides its sorting which
> _can_ be overriden by completion style's sorting which _can_ be
> overriden by completion UI's sorting.  AFAIU this can be done by writing
> comparison functions that return nil if the current sorting should be
> agnostic to both elements.

Writing the function is of course the easy part. 
The problem is where/how to insert this function.

>> I'd like to move towards a completion-style API that uses cl-generic.
>> E.g. introduce generic functions like `completion-style-try-completion`
>> which would be like `completion-try-completion` but takes an additional
>> `style` argument and dispatches based on it (replacing the dispatch
>> based on completion-style-alist).
>
> This is a good change, but it's not absolutely necessary to what I am
> proposing right now.

Definitely.  I just wanted to explain that the design to the current
solution can be done with this other change in mind.

>>>     * lisp/minibuffer.el (minibuffer-completion-help): Use
>>>     completion-style-sort-order and compeltion-style-annotation
>>                                       ^^^^^^^^^^
>>                                       completion
>>>     properties.
>>>     (completion-pcm--hilit-commonality): Propertize completion with
>>>     'completion-pcm-commonality-score.
>>>     (completion-flx-all-completions): Porpertize completion with
>>                                         ^^^^^^^^^^
>>                                         Propertize
> Thanks.

Duh!  I meant to add some idiotic scolding about those typos but got
side tracked by the annotations issue.  Sorry.  I promise to be more
firm next time.

>>>     completion-style-sort-order and completion-style-annotation.
>> Regarding annotations, I think being able to `concat` at the end is
>> too limited.  If you take your example from sly, we'd like the "15%"
>> annotations to be right-aligned and I don't see an easy way to do that
>> with the facility you introduce.
> I don't see the problem fully,

Hmm... I guess in the completion-style case, you could indeed look at
all the returned completions to compute the max-length and do some
right-alignment based on that.  For some reason, I feel like it'd be
better done elsewhere, tho (e.g. maybe company would rather right-align
based on the max-length of the *displayed* completions rather than
based on the max-length of all the completions).

> but probably I'd rather remove the annotation completely for now,
> until we have a better of how where we want to place it.  As Dmitry
> suggested, the flex score annotation is mostly a gimmick, we shouldn't
> add it until we have a good idea of how it should work.

Indeed, this annotation issue is orthogonal, so it can be kept for later.

>> So I'd encourage you to come up with a more flexible annotation system
>> that allows prepending annotations as well as right-alignment (and
>> ideally combinations of those, with several columns, ...).
>
> I'd prefer small things that can be added
> incrementally.

So do I.

> What do you suggest?

Nothing so far.

> So to summarize, I propose to add (1) the fafa9ec commit introducing
> flex completion and (2) a new commit extracted from 2c7577558 which adds
> the flex scoring calculation to each match, but doesn't do anything with
> it yet.  Deal?

Fine by me.  I'd call the score property `completion-score` because
I don't see any reason why it should be specific to the completion-style
(you could even have `flex` combine its score with a `completion-score`
property previously set by the completion-table, and then have the
front end combine that with its own scoring).

I think you can also make minibuffer-completion-help sort according to
that `completion-score`.

Regarding the code, see comments below.


        Stefan


> +          (setq completions
> +                (sort completions
> +                      (lambda (a b)
> +                        (let ((va (get-text-property 0 'completion-style-sort-order a))
> +                              (vb (get-text-property 0 'completion-style-sort-order b)))
> +                          (if (and va vb) (< va vb) va)))))

This will signal an error when one of the completions is the empty string :-(

> @@ -3056,22 +3067,41 @@ PATTERN is as returned by `completion-pcm--string->pattern'."
>           (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
>                  (md (match-data))
>                  (start (pop md))
> -                (end (pop md)))
> +                (end (pop md))
> +                (len (length str))
> +                (score-numerator 0)
> +                (score-denominator 0)
> +                (aux 0)
> +                (update-score
> +                 (lambda (a b)
> +                   "Update score variables given match range (A B)."
> +                   (setq
> +                    score-numerator   (+ score-numerator (- b a))
> +                    score-denominator (+ score-denominator (expt (- a aux) 1.5))
> +                    aux              b))))

I don't understand this scoring algorithm: please add a comment
explaining it (and give a meaningful name to `aux`).

> +           (funcall update-score 0 start)
>             (while md
> -             (put-text-property start (pop md)
> +             (funcall update-score start (car md))
> +             (put-text-property start
> +                                (pop md)

The extra line-break after `start` seems spurious.

> +           (put-text-property
> +            0 1 'completion-pcm-commonality-score
> +            (/ score-numerator (* len (1+ score-denominator)) 1.0) str))

This will signal an error when `str` is the empty string :-(

BTW, maybe PCM could also use this scoring for sorting (i.e. we could
set `completion-score` directly here)

> +           (let ((score (get-text-property 0 'completion-pcm-commonality-score comp)))
> +             (put-text-property 0 1 'completion-style-sort-order (- score) comp)

This will signal an error when `comp` is the empty string :-(

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> Consequently, a preexisting completion tables wouldn't be
> supported. But like I said, it shouldn't be hard to change either.

Oh.  That's what I feared (I think) It would be nice to add something
seemingly orthogonal like a "completion style" to all completion UI's
and all tables, without needing to change the completion tables
(granted, it would be good to *also* not change the UI's, but I'm not
sure there a solution for that).

> I dunno, sorting takes CPU time anyways. Not sure a combination of
> several sorting functions will frequently give a better result than
> just one of them.

I dunno what you dunno.  When using flex/scatter it's *really* important
to sort by flex-match.  I suggested "stable sorting" because it's a
slightly more decent thing to completion tables.  And by sorting twice
it's not like we're changing the Big-O complexity or anything.

But I also don't mind a scheme where the style's sorting completely
takes over (and we save those CPU cycles).

> But then, if you enable company-sort-by-occurrence via
> company-transformers, the completion style's sorting won't be visible
> anymore anyway.

I don't know what company-transformers are.  On the one hand I suppose
when you want to sort by occurance, you ... want to sort by occurrence.
So if you use the symbol "foofooubarbarnbazbazdquuxquuxo" very often
you'll see it sort to the top for your "undo" example.  So maybe company
should take the style's sorting last here, dunno.

> It's a question whether any other sorting approaches end up being
> helpful, but maybe some hybrid functions will work, where both
> occurrences and flex score are taken into account.

In this case I would first sort by occurance and then style-score.
There's no easy way to make a hybrid function, so we must pick a
default.  For all the examples I've been given, it seems that
flex-sorting should always come last. Since flex is the first and only
style that carries some sorting idea with it, perhaps it's not a very
bad idea to give it _some_ priority by default.

>> Eventually, we can add a keybinding to resort exclusively according to
>> the table or exclusively according to the completion style.
>
> In the approach I'm thinking of, both options are the same sorting
> function.

How would you synthetize it? 

> And still, seeing it wouldn't help me if I'm just writing code. Sorry
> for being blunt.

I'm a big boy, I can take blunt... :-)

> Sort by them, sure. But show the values to the user? Why?

In the general case, so the user has an idea _why_ something is being
automatically.  Humans generally gain confidence in algorithms if
they're shown human-comprehensible hints as to why it is is doing
something (humans generally also like this from other humans, which
explains why you ask me so many questions :-).

In this particular case, it's a very common idiom when displaying
tables/lists of something.  Perhaps in the "occurance sorting" field,
he/she will choose another word used less frequently for stylistic
purposes.

But, all that said, I'm not going to kill myself over the annotation,
nor do I think it even merits a customization option, though it's
probably not hard to do it anyway.

> The former, more or less. This creates a certain limitation, sure, but
> it shouldn't be a problem for Eglot.

Hmm? By far, Eglot isn't the only one thing I'm interested in enhancing
(actually, I've had few opportunities to actualy _use_ Eglot lately).

João

Re: new-flex-completion-style

[João Távora]

Óscar Fuentes <ofv@wanadoo.es> writes:

> João Távora <joaotavora@gmail.com> writes:

> Do you know flx [1] ? Would it be possible to implement it on top of
> your work by providing a score function and/or a sort function?
>
> 1. https://github.com/lewang/flx

I remember looking at this a long time ago.  It looked interesting, but
is almost certainly more complex/featureful than my implementation,
which is reasonably simple and tries to play along with the Emacs's
completion style/table/UI framework, something which is still relatively
fluid (as you can read in this thread).  So I'd rather take it slowly
before adding new features.

But I don't know what features you are looking for exactly, can you be
specific?

João

Re: new-flex-completion-style

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Not sure if it's related to icomplete.  Maybe the length-heuristic is
> just not good for buffer names.

Agreed. 

> I think this length heuristic also works reasonably well in several
> other circumstances (e.g. file names).

OK. Makes sense.  Just to be sure we're talking about
completion-all-sorted-completions, right?

> It seems like it would be a clear win (the buffer-list order is a much
> better heuristic than the length).

I'm so glad you're volunteering to do this ;-)

>>> Still, in a case such as lisp/ecomplete.el where the completion table
>>> provides its own sorting based on recent-usage-frequency, how should
>>> this sorting be combined with that of flex?  I can see arguments in
>>> favor of saying that the flex-weight should be ignored in favor of the
>>> usage-frequency.
>> ecomplete has its own UI in ecomplete-display-matches?
>
> It also offers a completion-table (which I use via
> a completion-at-point-function).

But I can use that table with another UI right?  Is that
completion-at-point-function in Emacs or in your config?

>> My view of the matter is: completion table provides its sorting which
>> _can_ be overriden by completion style's sorting which _can_ be
>> overriden by completion UI's sorting.  AFAIU this can be done by writing
>> comparison functions that return nil if the current sorting should be
>> agnostic to both elements.
>
> Writing the function is of course the easy part. 
> The problem is where/how to insert this function.

We have to decide on a good standard order/combination of sorting
functions.  If we decide that's not good enough for some cases we can go
for more indirections à la CL method combinations.  (wonder if
cl-generic has method combinations).

But this could very possibly be overdesigning at this point.

> Duh!  I meant to add some idiotic scolding about those typos but got
> side tracked by the annotations issue.  Sorry.  I promise to be more
> firm next time.

Since this makes fixing my dumb mistakes more fun, I hereby scold you
for your lack of scolding.

>> I don't see the problem fully,
> Hmm... I guess in the completion-style case, you could indeed look at
> all the returned completions to compute the max-length and do some
> right-alignment based on that.  For some reason, I feel like it'd be
> better done elsewhere, tho (e.g. maybe company would rather right-align
> based on the max-length of the *displayed* completions rather than
> based on the max-length of all the completions).

I'll think better about this once we sort out the sorting, which has
priority.

>> So to summarize, I propose to add (1) the fafa9ec commit introducing
>> flex completion and (2) a new commit extracted from 2c7577558 which adds
>> the flex scoring calculation to each match, but doesn't do anything with
>> it yet.  Deal?
>
> Fine by me.  I'd call the score property `completion-score` because
> I don't see any reason why it should be specific to the completion-style
> (you could even have `flex` combine its score with a `completion-score`
> property previously set by the completion-table, and then have the
> front end combine that with its own scoring).
>
> I think you can also make minibuffer-completion-help sort according to
> that `completion-score`.
>
> Regarding the code, see comments below.

I've pushed a new version fixing the problems you reported off-list.  I
did that _before_ reading this message.

I'll take a look at this new batch, do the obvious fixes.  But before
submitting anything sorting-related, I'd like Dmitry to show a patch for
his sorting idea on top of scratch/new-flex-completion-style, try it out
a bit and then report back here.

João

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 12.02.2019 16:19, Stefan Monnier wrote:
>> See completion--metadata and completion-extra-properties.
> 
> But a completion style like `flex` can't affect either of those.
> And I expect some people will want to put in their `completion-styles`,
> so `flex` should work well for all/most completion tables and all/most
> completion-at-point-functions (and calls to completing-read).

On the one hand, yes, but it's the abstraction we already have, and it 
will allow flex to work properly at least with certain completion 
tables. Which is a win.

On the other hand, a search for display-sort-function through Emacs's 
sources seems to indicate that the design is kind of a failure: there 
are only a couple places that set it to something, and in both cases 
it's #'identity, meaning "do not re-sort".

So minibuffer.el might want to take a cue from Company and 
company-transformers, to make this universal, we could add sorting as a 
feature of completion styles, or as a separate user option, for maximum 
flexibility. I'd simply like to avoid hardcoding extra sorting behavior, 
like the patch proposes.

> I think I agree here: the stability of the `flex` sort is likely to make
> little difference in practice (more specifically, the sets of matches
> which share the same flex-score will be sufficiently numerous and small
> that the sorting within them is not significant).

Yep.

> Not sure how that can be done in a modular way: how can we specify an
> API where `flex` can provide its scores, `sort-by-occurrence` can
> specify its scores, they don't know about each other, and yet the two
> sets of scores get mixed in a useful way?

Conveying information via text properties seems like a viable approach. 
We already use them to indicate matching characters, for instance.

Now, I wouldn't say it's terrible that sort-by-occurrence-and-score 
would know specifically about flex (I don't think there's going to be a 
lot of different styles in this flavor), but sure, like you proposed in 
another email, the property can have a neutral name like completion-score.

To emphasize: there won't be a sort-by-occurrence whatever, but a 
function called, say, sort-by-occurrence-and-score could take both 
occurrences and flex scores into account.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 12.02.2019 20:21, João Távora wrote:

> Oh.  That's what I feared (I think) It would be nice to add something
> seemingly orthogonal like a "completion style" to all completion UI's
> and all tables, without needing to change the completion tables
> (granted, it would be good to *also* not change the UI's, but I'm not
> sure there a solution for that).

You have a point, sure. But I'd rather reuse the abstraction we already 
have as the first step, and then maybe extend it (or add a new one), 
rather add sorting code that uses these text properties to an existing 
function.

> I dunno what you dunno.  When using flex/scatter it's *really* important
> to sort by flex-match.  I suggested "stable sorting" because it's a
> slightly more decent thing to completion tables.  And by sorting twice
> it's not like we're changing the Big-O complexity or anything.

Constants matter sometimes, too. Not necessarily in this case, but...

> But I also don't mind a scheme where the style's sorting completely
> takes over (and we save those CPU cycles).

That would be ideal, I think.

> I don't know what company-transformers are.

Not too hard to find out, I think.

> On the one hand I suppose
> when you want to sort by occurance, you ... want to sort by occurrence.
> So if you use the symbol "foofooubarbarnbazbazdquuxquuxo" very often
> you'll see it sort to the top for your "undo" example.  So maybe company
> should take the style's sorting last here, dunno.

OK, I was probably wrong here. Like, if only some of the completions 
have occurences, the rest would be sorted by flex scores, and that... 
sounds pretty good.

> In this case I would first sort by occurance and then style-score.
> There's no easy way to make a hybrid function, so we must pick a
> default.  For all the examples I've been given, it seems that
> flex-sorting should always come last. Since flex is the first and only
> style that carries some sorting idea with it, perhaps it's not a very
> bad idea to give it _some_ priority by default.

You probably mean assign the least priority to flex's scores. The flex 
score sort would happen first with this approach, though.

Almost all completions will have different scores, so sorting by them 
last would make all the previous sorting disappear.

>>> Eventually, we can add a keybinding to resort exclusively according to
>>> the table or exclusively according to the completion style.
>>
>> In the approach I'm thinking of, both options are the same sorting
>> function.
> 
> How would you synthetize it?

Err, not the way you'd want. The table would just be designed to be used 
with the completion style. And so its sorting function.

> In the general case, so the user has an idea _why_ something is being
> automatically.  Humans generally gain confidence in algorithms if
> they're shown human-comprehensible hints as to why it is is doing
> something (humans generally also like this from other humans, which
> explains why you ask me so many questions :-).

For a little while, maybe. To obtain the said confidence. And then, I'd 
opt to turn it off, because I prefer to avoid too much visual clutter 
(one of the reasons to use Emacs).

> In this particular case, it's a very common idiom when displaying
> tables/lists of something.  Perhaps in the "occurance sorting" field,
> he/she will choose another word used less frequently for stylistic
> purposes.
> 
> But, all that said, I'm not going to kill myself over the annotation,
> nor do I think it even merits a customization option, though it's
> probably not hard to do it anyway.

You see, regarding the annotations as well, it makes more sense to reuse 
the existing mechanism, or make it more flexible as well, somehow.

>> The former, more or less. This creates a certain limitation, sure, but
>> it shouldn't be a problem for Eglot.
> 
> Hmm? By far, Eglot isn't the only one thing I'm interested in enhancing
> (actually, I've had few opportunities to actualy _use_ Eglot lately).

Sly's completion table could take the same approach. As long as the 
completion table is under your control, it's all good.

By the way, we could also add an indirection for display-sort-function 
(and maybe the -cycle- one as well) similar to the styles. So we not 
only assign a style (or several of them) based on the category, but also 
the sorting function. This way, sorting of buffers the right way would 
still work and make sense. And at the same time, the user could change 
certain categories to use both flex matching and flex score sorting.

That's more work for the user, but still. Seems kinda elegant.

Re: new-flex-completion-style

[Óscar Fuentes]

João Távora <joaotavora@gmail.com> writes:

> Óscar Fuentes <ofv@wanadoo.es> writes:
>
>> João Távora <joaotavora@gmail.com> writes:
>
>> Do you know flx [1] ? Would it be possible to implement it on top of
>> your work by providing a score function and/or a sort function?
>>
>> 1. https://github.com/lewang/flx
>
> I remember looking at this a long time ago.  It looked interesting, but
> is almost certainly more complex/featureful than my implementation,
> which is reasonably simple and tries to play along with the Emacs's
> completion style/table/UI framework, something which is still relatively
> fluid (as you can read in this thread).  So I'd rather take it slowly
> before adding new features.
>
> But I don't know what features you are looking for exactly, can you be
> specific?

Basically, flx takes an input string and a list of candidates, assigns
an score to each candidate and returns a filtered list of candidates
sorted by the score.

This seems the same you described on your commit message.

Re: new-flex-completion-style

[João Távora]

On Wed, Feb 13, 2019 at 12:29 AM Óscar Fuentes <ofv@wanadoo.es> wrote:
>
> João Távora <joaotavora@gmail.com> writes:
>
> > Óscar Fuentes <ofv@wanadoo.es> writes:
> >
> >> João Távora <joaotavora@gmail.com> writes:
> >
> >> Do you know flx [1] ? Would it be possible to implement it on top of
> >> your work by providing a score function and/or a sort function?
> >>
> >> 1. https://github.com/lewang/flx
> >
> > I remember looking at this a long time ago.  It looked interesting, but
> > is almost certainly more complex/featureful than my implementation,
> > which is reasonably simple and tries to play along with the Emacs's
> > completion style/table/UI framework, something which is still relatively
> > fluid (as you can read in this thread).  So I'd rather take it slowly
> > before adding new features.
> >
> > But I don't know what features you are looking for exactly, can you be
> > specific?
>
> Basically, flx takes an input string and a list of candidates, assigns
> an score to each candidate and returns a filtered list of candidates
> sorted by the score.
>
> This seems the same you described on your commit message.

Indeed. I just had a look again.  The engine itself it around 360 loc
which should be 5-10x times longer than what I'm proposing.  The
scoring itself seems quite more intricate, with special cases and
customization for word separators, a "heatmap", camel-case
exceptions, and probably some I haven't understood.

My implementation, on the other hand, takes advantage of the
existing emacs PCM mechanism to generate a
".*<letter>.*<anotherletter>.*" regex to do the matching.
Importantly, it's agnostic to the type of thing represented by
the string being matched. Scoring is hooked onto the existing
logic for char highlighting.  The formula is a simple ad-hoc
thing that I invented and has been working OK.  It's quotient of
a running sum of a function of distances that are known when
highlighting chars.  Basically, it values "tighter" matches in
short strings, so matching "bar" to "obarb" scores higher than
matching it to "foobarbaz" which scores higher than
matching it to "booazzraa".

"Working OK" here means that the thing I meant is almost always
in the first three or four candidates. Perhaps you should try it
and confirm this, or show me cases where it isn't.

But you didn't answer my question: what specific features of flx
are you looking for?  I'd be happy to implement them if I have
the time, but I have to understand what they are.


João

Re: new-flex-completion-style

[Óscar Fuentes]

João Távora <joaotavora@gmail.com> writes:

> But you didn't answer my question: what specific features of flx
> are you looking for?  I'd be happy to implement them if I have
> the time, but I have to understand what they are.

My question was related to the modifications you are making to the
generic Emacs completion system to allow this type of score+sort
methods. Since flx works on the same principles, if your changes makes
the scoring and sorting user-configurable, alternative methods such as
flx would become usable as well.

I wasn't asking for changes on your "flex" completion method which, BTW,
looks to me as an evolution of ivy's and ido's flex method.

Thanks.

RE: new-flex-completion-style

[Drew Adams]

> your "flex" completion method which, BTW, looks to
> me as an evolution of ivy's and ido's flex method.

And Icicles's before those, FWIW.

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

Re: new-flex-completion-style

[Stefan Monnier]

> But you didn't answer my question: what specific features of flx
> are you looking for?

IIUC Le Wang's `flx` has two main features:
- Its scoring is supposed to be particularly good.
- It's supposed to be particularly fast.

> I'd be happy to implement them if I have
> the time, but I have to understand what they are.

Other than using flx.el I don't see any good way to "implement" those
features (especially the one about speed).

Of course, I have no idea if flx.el's scoring is indeed significantly
better in practice, nor if it's significantly faster in practice either.

BTW, the issue of scoring quality is not nearly as obvious as one might
think because the score one should give to a particular match depends on
the user's expectation and the user's expectation often depend on the
past behavior of the tool, i.e. on the scoring.


        Stefan

RE: new-flex-completion-style

[Drew Adams]

> BTW, the issue of scoring quality is not nearly as obvious as one might
> think because the score one should give to a particular match depends
> on the user's expectation and the user's expectation often depend on
> the past behavior of the tool, i.e. on the scoring.

+1 - good point. There's room for the tool to learn too.

And it can depend on the context - intended use of
the chosen completion(s).  The completing function
(completion table etc.) typically does not have a
good view of the user's context, including intent.

Put differently, if scoring only has the matches
and the input pattern to go on, the most it can do
is offer some measure of comparison based on just
those two inputs.  A score that's really useful to
a user might depend on more.

Re: new-flex-completion-style

[Óscar Fuentes]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> But you didn't answer my question: what specific features of flx
>> are you looking for?
>
> IIUC Le Wang's `flx` has two main features:
> - Its scoring is supposed to be particularly good.

This is all about personal taste. For me it is great, others don't think
so. Also, it takes a while to get used to and adjust your input
according to the scoring method.

> - It's supposed to be particularly fast.

Not quite. The initial implementation was terribly slow. Then it became
usable at the expense of memory usage (caching), which is way higher
than it should be for a feature like this.

It is in my to-do list to implement the algorithm in C, either into
Emacs core or as an extension, and see if the speed improvement is good
enough to dispense with all the caching.

>> I'd be happy to implement them if I have
>> the time, but I have to understand what they are.
>
> Other than using flx.el I don't see any good way to "implement" those
> features (especially the one about speed).
>
> Of course, I have no idea if flx.el's scoring is indeed significantly
> better in practice, nor if it's significantly faster in practice either.
>
> BTW, the issue of scoring quality is not nearly as obvious as one might
> think because the score one should give to a particular match depends on
> the user's expectation and the user's expectation often depend on the
> past behavior of the tool, i.e. on the scoring.

Indeed.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Stefan Monnier]

> On the one hand, yes, but it's the abstraction we already have, and it will
> allow flex to work properly at least with certain completion tables. Which
> is a win.

The problem I see with it is that performing the style-sorting via
completion-metadata or via completion-extra-properties is a hack that
works by breaking abstractions.

So, not only it will only work with some completion tables, but for that
you'll need to introduce "wrong" code in those completion tables.

I'd rather we extend the infrastructure so that completion styles can do
their own sorting.

> On the other hand, a search for display-sort-function through Emacs's
> sources seems to indicate that the design is kind of a failure: there are
> only a couple places that set it to something, and in both cases it's
> #'identity, meaning "do not re-sort".

Indeed.  Those cases *do* perform sorting, but they sort directly inside
their `all-completions` function rather than in their display-sort-function.

So yes, the design is kind of a failure, tho the alternative of having
a boolean in the metadata to say "don't sort" is no simpler.

> So minibuffer.el might want to take a cue from Company and
> company-transformers, to make this universal, we could add sorting as
> a feature of completion styles, or as a separate user option, for maximum
> flexibility.

The question is really: how/where would a completion style specify which
sorting it wants to do (based on the above-mentioned past experience,
we can assume that they'll want to do their sorting directly in
completion-all-completions and then specify "don't sort any further"),
and then how to change minibuffer.el to do that.

Currently, completion-all-completions does not return any information
about which style was used, so either we change this API so that it also
returns which style was used, or some info about the style gets added as
text-properties to influence subsequent sorting, or
completion-all-completions is changed to perform the sorting (which may
require extending its calling convention so the caller can tell it which
kind of sorting it wants).

> Now, I wouldn't say it's terrible that sort-by-occurrence-and-score would
> know specifically about flex (I don't think there's going to be a lot of
> different styles in this flavor), but sure, like you proposed in another
> email, the property can have a neutral name like completion-score.

Using scores would make it possible to combine different scoring systems
by weighting the different parts.  I'm not completely happy with the use
of text-properties, tho (e.g. ideally completion-all-completion could
return a list of pairs of the form (CANDIDATE . SCORE)).  But it has the
very significant advantage of requiring much fewer changes.


        Stefan

Re: new-flex-completion-style

[João Távora]

João Távora <joaotavora@gmail.com> writes:

> I'll take a look at this new batch, do the obvious fixes.  But before
> submitting anything sorting-related, I'd like Dmitry to show a patch for
> his sorting idea on top of scratch/new-flex-completion-style, try it out
> a bit and then report back here.

>> +          (setq completions
>> +                (sort completions
>> +                      (lambda (a b)
>> +                        (let ((va (get-text-property 0 'completion-style-sort-order a))
>> +                              (vb (get-text-property 0 'completion-style-sort-order b)))
>> +                          (if (and va vb) (< va vb) va)))))
>
> This will signal an error when one of the completions is the empty
> string :-(

I've removed this for now, I.e. there's absolutely no sorting yet before
we agree on who should be doing it and where.  But why would the empty
string be there anyway?

>> @@ -3056,22 +3067,41 @@ PATTERN is as returned by `completion-pcm--string->pattern'."
>>           (let* ((pos (if point-idx (match-beginning point-idx) (match-end 0)))
>>                  (md (match-data))
>>                  (start (pop md))
>> -                (end (pop md)))
>> +                (end (pop md))
>> +                (len (length str))
>> +                (score-numerator 0)
>> +                (score-denominator 0)
>> +                (aux 0)
>> +                (update-score
>> +                 (lambda (a b)
>> +                   "Update score variables given match range (A B)."
>> +                   (setq
>> +                    score-numerator   (+ score-numerator (- b a))
>> +                    score-denominator (+ score-denominator (expt (- a aux) 1.5))
>> +                    aux              b))))
>
> I don't understand this scoring algorithm: please add a comment
> explaining it

I don't "understand" it either :-) i.e. it was developed empirically,
more or less.  But let's try to:

Consider these bad ascii(tm) schematics matching the pattern "foo" to
the strings "barfobazoquux" and "barfoobazquux":

          bar         fo             baz         o             quux
          ---         ++             ---         +             ---- 
   <start>   <match_1>  <match_1_end>   <match_n> <match_n_end>    <end>
    
    
          bar         foo             bazquux
          ---         +++             ------- 
   <start>   <match_1>   <match_1_end>       <end>
   
+++ indicates parts where the pattern matched
--- indicates parts where the pattern didn't match

The formula assigns higher scores to "better" matches. It's bound by
[0..1] and in the form of a quotient.  For the numerator, it counts the
+++.  For the denominator, it takes counts the number of --- in each
such group, exponentiates that number to a "falloff constant", adds it
to the total, adds one to the final sum, and then multiples by the
length of the string.

If no --- you get

   (length/(length * (1 + 0)) == 1

If no +++, you get 0 (but this never happens cause we pre-filtered the
matches with pcm).

The falloff constant (FC) used in the denominator is important.  A
negative falloff will value tighter matches, a positive value will value
more evenly spread out matches.  I set the constant to 1.5 some time
ago, and I haven't gone back, but perhaps it could be -1.5.

Anyway with FC=1.5 the examples above would be:

   first string  1.507%
   second string 1.197%

with FC=-1.5 it would be

   first string  15.849%
   second string 19,834%

If haven't mangled the numbers, this seems to point that -1.5 is a
better default for the constant, which shouldn't be hardcoded anyway.
On the other hand, I've been working with -1.5 for a long time now and
never had any obvious problems.  It's probably what you said elsewhere,
"good" scoring is a question of getting used to whatever the system is
doing, IOW humans learn, too.

Also note that it doesn't make any sense to compare scores between
different match lengths, only between same match lenghts at different
positions on different strings.

Anyway, what do you think?  Is this acceptable or so you have anything
better?

> (and give a meaningful name to `aux`).

Oh happy days when hackers could code "aux" and feel very smug about it.

OK, I'll call it "last-b".

>> +           (funcall update-score 0 start)
>>             (while md
>> -             (put-text-property start (pop md)
>> +             (funcall update-score start (car md))
>> +             (put-text-property start
>> +                                (pop md)
>
> The extra line-break after `start` seems spurious.

Were you expecting it to have very deep, hidden meaning?  But OK.

>
>> +           (put-text-property
>> +            0 1 'completion-pcm-commonality-score
>> +            (/ score-numerator (* len (1+ score-denominator)) 1.0) str))
>
> This will signal an error when `str` is the empty string :-(

Ooops, but that that happen?  Can an empty string be pcm-matched
by some pattern?  There's 

> BTW, maybe PCM could also use this scoring for sorting (i.e. we could
> set `completion-score` directly here)
>
>> +           (let ((score (get-text-property 0 'completion-pcm-commonality-score comp)))
>> +             (put-text-property 0 1 'completion-style-sort-order (- score) comp)
>
> This will signal an error when `comp` is the empty string :-(

Same here.

Re: new-flex-completion-style

[Daniel Pittman]

[-- Attachment #1: Type: text/plain, Size: 1336 bytes --]

On Wed, Feb 13, 2019 at 10:42 AM Óscar Fuentes <ofv@wanadoo.es> wrote:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
> >> But you didn't answer my question: what specific features of flx
> >> are you looking for?
> > - It's supposed to be particularly fast.
>
> Not quite. The initial implementation was terribly slow. Then it became
> usable at the expense of memory usage (caching), which is way higher
> than it should be for a feature like this.
>
> It is in my to-do list to implement the algorithm in C, either into
> Emacs core or as an extension, and see if the speed improvement is good
> enough to dispense with all the caching.
>

FWIW, I have a general intention with no concrete action as yet to work out
how easiest to wire up fzf for matching, since it is extremely fast,
reasonably memory efficient, and at least for me does a good heuristic job
of matching things the way I expect them to match.  The MIT license makes
it possible to use as a module, though I also considered if a "pipe" mode
akin to {i,a,hun}spell might be a smarter strategy.

https://github.com/junegunn/fzf

This was motivated by my experience with flx, which was ... not positive,
in terms of matching in the way I expected.  It was better than the ".*
between every letter" model that it replaced, however.

[-- Attachment #2: Type: text/html, Size: 1852 bytes --]

Re: new-flex-completion-style

[Stefan Monnier]

> I've removed this for now, I.e. there's absolutely no sorting yet before
> we agree on who should be doing it and where.  But why would the empty
> string be there anyway?

Don't know: you'd have to ask it.

> I don't "understand" it either :-)

My question wasn't to justify the idea behind the algorithm but just to
describe in words what the code is supposedly computing.  I.e. something
like what you wrote here:

> The formula assigns higher scores to "better" matches. It's bound by
> [0..1] and in the form of a quotient.  For the numerator, it counts the
> +++.  For the denominator, it takes counts the number of --- in each
> such group, exponentiates that number to a "falloff constant", adds it
> to the total, adds one to the final sum, and then multiples by the
> length of the string.

Making sure I understand:
- "counts the +++" will always return the length of the pattern, right?
  So this is used just to normalize the result to ]0..1].
- if the falloff constant is 0, the denominator is the number of places
  where a "star" had to be added (plus one).  And if the falloff
  constant is positive it prefers more insertions of shorter text
  chunks over fewer insertions of longer text chunks, and if it's
  negative it oddly prefers longer insertions over shorter ones.

> Anyway, what do you think?  Is this acceptable or so you have anything
> better?

Fine by me (tho maybe I wouldn't count the final "---", to more
closely match [no pun intended] the usual prefix completion).

FWIW, in my "forgive" completion style I used the equivalent of
a falloff constant of 0 (i.e. I didn't care about the length of the
"---" but only about their number).

> OK, I'll call it "last-b".

It'll be eternally indebted to you.

>>> +           (funcall update-score 0 start)
>>>             (while md
>>> -             (put-text-property start (pop md)
>>> +             (funcall update-score start (car md))
>>> +             (put-text-property start
>>> +                                (pop md)
>>
>> The extra line-break after `start` seems spurious.
> Were you expecting it to have very deep, hidden meaning?  But OK.

I was actually bothered by the fact that the `diff` indicates a change
on an expression that's actually not modified (other than by insertion
of a line-break).  Anal retentiveness for ever!

>>> +           (put-text-property
>>> +            0 1 'completion-pcm-commonality-score
>>> +            (/ score-numerator (* len (1+ score-denominator)) 1.0) str))
>>
>> This will signal an error when `str` is the empty string :-(
>
> Ooops, but that that happen?  Can an empty string be pcm-matched
> by some pattern?  There's 

I think it can if the pattern is empty.  So maybe all those
put/get-text-property are fine if you make sure this code is never even
called when the pattern is empty.

BTW, the patch below seems to improve the behavior (e.g. it lets
`.../emacs/cfi TAB` complete to `.../emacs/config` as it should since
all remaining matches also match "config").


        Stefan


diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 8ea70b14f1..f5171bb2d0 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -3434,22 +3434,7 @@ completion-flex-try-completion
                 #'completion-flex--make-flex-pattern)))
     (if minibuffer-completing-file-name
         (setq all (completion-pcm--filename-try-filter all)))
-    (cond ((not (consp all))
-           all)
-          ((not (consp (cdr all))) ; single completion
-           (if (equal string (car all))
-               t
-             (cons (car all) (length (car all)))))
-          (t
-           ;; If more than one completion, try some "merging".
-           ;; Meaning add as much as possible to the user's
-           ;; pattern without losing any possible matches in
-           ;; `all'.  If that fails, leave user input
-           ;; untouched.
-           (let ((probe (completion-pcm--merge-try pattern all prefix suffix)))
-             (if (stringp probe)
-                 (cons probe (length probe))
-               (cons string point)))))))
+    (completion-pcm--merge-try pattern all prefix suffix)))
 
 (defun completion-flex-all-completions (string table pred point)
   "Get flex-completions of STRING in TABLE, given PRED and POINT."

Re: new-flex-completion-style

[João Távora]

On Wed, Feb 13, 2019 at 6:54 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> Making sure I understand:
> - "counts the +++" will always return the length of the pattern, right?
>   So this is used just to normalize the result to ]0..1].
> - if the falloff constant is 0, the denominator is the number of places
>   where a "star" had to be added (plus one).  And if the falloff
>   constant is positive it prefers more insertions of shorter text
>   chunks over fewer insertions of longer text chunks, and if it's
>   negative it oddly prefers longer insertions over shorter ones.

Yes and Yes.  The length of the pattern but probably not as
calculated by (length pattern).

I don't think it's odd.  I call the former "scattered match"
and the latter a "tighter match".  For the particular way I
remember symbol names, files names, etc, it's probably a good
idea, since I can almost always remember a full word in the name.

But sure enough I've had it configured for "scattered match"
all along and I didn't know!

> > Anyway, what do you think?  Is this acceptable or so you have anything
> > better?
>
> Fine by me (tho maybe I wouldn't count the final "---", to more
> closely match [no pun intended] the usual prefix completion).

Maybe this should be configurable, but in general I don't
think staying close to prefix completion should be a
goal, since this is a completely different game.  IOW, valuing
a string ends/beginning differently makes little sense in flex.

> >>> +           (put-text-property
> >>> +            0 1 'completion-pcm-commonality-score
> >>> +            (/ score-numerator (* len (1+ score-denominator)) 1.0) str))
> >>
> >> This will signal an error when `str` is the empty string :-(
> >
> > Ooops, but that that happen?  Can an empty string be pcm-matched
> > by some pattern?  There's
>
> I think it can if the pattern is empty.  So maybe all those
> put/get-text-property are fine if you make sure this code is never even
> called when the pattern is empty.

OK, I'll figure something out.

> BTW, the patch below seems to improve the behavior (e.g. it lets
> `.../emacs/cfi TAB` complete to `.../emacs/config` as it should since
> all remaining matches also match "config").

cool!

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 13.02.2019 19:00, Stefan Monnier wrote:
> So, not only it will only work with some completion tables, but for that
> you'll need to introduce "wrong" code in those completion tables.

Since we seem to want to redo completion tables in a major way anyway, I 
wouldn't worry about that too much, as long as the result is functional.

> I'd rather we extend the infrastructure so that completion styles can do
> their own sorting.

That's one option. Another option, which I've mentioned before, is to 
create an indirection for sorting functions via the completion table's 
category. Similar to the one that completions styles have.

> So yes, the design is kind of a failure, tho the alternative of having
> a boolean in the metadata to say "don't sort" is no simpler.

It's simpler but more ad-hoc, to be sure.

> The question is really: how/where would a completion style specify which
> sorting it wants to do (based on the above-mentioned past experience,
> we can assume that they'll want to do their sorting directly in
> completion-all-completions and then specify "don't sort any further"),
> and then how to change minibuffer.el to do that.

As we can see from the patch, using text properties (and actually sort 
later) also seems like a viable approach.

> Currently, completion-all-completions does not return any information
> about which style was used, so either we change this API so that it also
> returns which style was used, or some info about the style gets added as
> text-properties to influence subsequent sorting, or
> completion-all-completions is changed to perform the sorting (which may
> require extending its calling convention so the caller can tell it which
> kind of sorting it wants).

The category-based approach should circumvent that problem.

With this approach, completion styles don't indicate sorting, and 
whatever entity did set up the completion style to be used (the user, a 
configuration package, etc) would need to set up both completion styles 
and sorting functions to match.

> Using scores would make it possible to combine different scoring systems
> by weighting the different parts.  I'm not completely happy with the use
> of text-properties, tho (e.g. ideally completion-all-completion could
> return a list of pairs of the form (CANDIDATE . SCORE)).  But it has the
> very significant advantage of requiring much fewer changes.

I think text properties are fine here. In Company, we use them for 
various bits of information.

Further, if your goal is to combine different scoring systems, it'll 
probably be required to assign different scores (from different systems) 
to each completion. The form (CANDIDATE . SCORE) won't cut it, but text 
properties should.

Re: new-flex-completion-style

[Stefan Monnier]

> I don't think it's odd.  I call the former "scattered match"
> and the latter a "tighter match".

Don't you find it odd that "foo" gives a better score to
"fotttttttttttttttto" than to "foto" ?

[ Given them the same score sounds acceptable, tho.  ]


        Stefan

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 1:36 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
> > I don't think it's odd.  I call the former "scattered match"
> > and the latter a "tighter match".
>
> Don't you find it odd that "foo" gives a better score to
> "fotttttttttttttttto" than to "foto" ?

Perhaps.  But as it stands it doesn't make sense to
compare scores across different length strings.

It does make sense to compare the score between
foo's matches of foot and foto.

> [ Given them the same score sounds acceptable, tho.  ]

Feel free to add some kind of normalization to the function
if you can come up with it.  Or come up with another function
entirely.  As I said, a function that measures the distance
in "boring editing operations" between the pattern and the target
would be a nicer measure.

-- 
João Távora

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 1:55 PM João Távora <joaotavora@gmail.com> wrote:
>
> On Thu, Feb 14, 2019 at 1:36 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> >
> > > I don't think it's odd.  I call the former "scattered match"
> > > and the latter a "tighter match".
> >
> > Don't you find it odd that "foo" gives a better score to
> > "fotttttttttttttttto" than to "foto" ?
>
> Perhaps.  But as it stands it doesn't make sense to
> compare scores across different length strings.
>
> It does make sense to compare the score between
> foo's matches of foot and foto.
>
> > [ Given them the same score sounds acceptable, tho.  ]
>
> Feel free to add some kind of normalization to the function
> if you can come up with it.  Or come up with another function
> entirely.  As I said, a function that measures the distance
> in "boring editing operations" between the pattern and the target
> would be a nicer measure.

I've been experimenting with a simpler function that just counts the
number of "holes" and the length of those holes separately
in the denominator. The numerator is the same and a perfect
match is still a 1. It seems to fare better for your cases. For foo

Eventually we could weight the number and length
of holes differently so we can get this:

score(foo,barfoobaz) > score(foo,fabrobazo) >
score(foo,fotttttttttttttttttttttto)

Which would be nicer, I think.

João

Re: new-flex-completion-style

[Óscar Fuentes]

João Távora <joaotavora@gmail.com> writes:

> Eventually we could weight the number and length
> of holes differently so we can get this:
>
> score(foo,barfoobaz) > score(foo,fabrobazo) >
> score(foo,fotttttttttttttttttttttto)
>
> Which would be nicer, I think.

My experience on this type of discussions about flx says that you should
design a scoring algorithm based on some generic, human-related
heuristic that makes sense to you and stick to it. You will hear lots of
complaints by those that dislike the system, showing specific examples
that demonstrate "obvious" deficiencies on your approach. But it is
impossible to create something that makes everybody happy.

As long as Emacs can't read our minds, there will be no good-enough
completion mechanism. And even then... we are dealing with the Emacs
user base, you know :-)

Re: new-flex-completion-style

[Daniel Pittman]

[-- Attachment #1: Type: text/plain, Size: 3699 bytes --]

On Thu, Feb 14, 2019 at 10:16 AM João Távora <joaotavora@gmail.com> wrote:

> On Thu, Feb 14, 2019 at 1:55 PM João Távora <joaotavora@gmail.com> wrote:
> > On Thu, Feb 14, 2019 at 1:36 PM Stefan Monnier <monnier@iro.umontreal.ca>
> wrote:
> > >
> > > > I don't think it's odd.  I call the former "scattered match"
> > > > and the latter a "tighter match".
> > >
> > > Don't you find it odd that "foo" gives a better score to
> > > "fotttttttttttttttto" than to "foto" ?
> >
> > Perhaps.  But as it stands it doesn't make sense to
> > compare scores across different length strings.
> >
> > It does make sense to compare the score between
> > foo's matches of foot and foto.
> >
> > > [ Given them the same score sounds acceptable, tho.  ]
> >
> > Feel free to add some kind of normalization to the function
> > if you can come up with it.  Or come up with another function
> > entirely.  As I said, a function that measures the distance
> > in "boring editing operations" between the pattern and the target
> > would be a nicer measure.
>

The Levenshtein distance and close variants generally do a reasonable job
of approximating human expectations, yes.  Close variants (eg: only
delete/insert, no mutate) also work well.

The cost of building the Levenshtein edit distance matrix for picking or
ordering candidates is quite high, though;
https://en.wikipedia.org/wiki/Approximate_string_matching gives a good
summary, and you really don't want to use the most naive option if you can
avoid it.  Computation costs go through the roof very fast; the cost is
roughly proportional to the length of the candidate cubed, using the brute
force approach.

The other shortfall of using only edit distance is that most of the time
people expect to front-weight the search: you may have a closer edit
distance match later in the string, but people usually want a less exact
match, closer to the start, intuitively.


> I've been experimenting with a simpler function that just counts the
> number of "holes" and the length of those holes separately
> in the denominator. The numerator is the same and a perfect
> match is still a 1. It seems to fare better for your cases. For foo
>

I'd very, very strongly encourage y'all to take a look at the existing work
on the problem, not least because of the algorithmic complexity costs when
you apply this to a large corpus of candidates.  Consider, for example,
completion over the set of all defined symbols in Emacs, which is ~ 55,000
candidates, and IIRC I calculated the average length to 9 characters, so
brute force matching would be be on the order of 40 **million** comparisons
for the first pattern character, though thankfully dropping fast as you
eliminate non-matching candidates entirely.  (Raw comparisons, accounting
for all possible matches in all possible candidate, of that pattern, so
each candidate gets $length / $pattern_length comparisons performed.)

Anyway, the point is: this is an area where serious study has been
invested, and I strongly urge you to take advantage of that, rather than
trying to reinvent this surprisingly complex wheel.  This isn't simple to
do, and it definitely isn't simple to do in a high performance way.

PS: whatever else you do, make it trivial to configure what function is
used for ordering the candidate results.  That matters far more that the
details of the default match / order choice, because it allows easy
innovation over time.

PPS: the best modern tools seem to be derived from the problem of genome
sequence matching, but heuristics are definitely helpful too.  Again, fzf
is the best version of that I have found.

[-- Attachment #2: Type: text/html, Size: 4750 bytes --]

RE: new-flex-completion-style

[Drew Adams]

> As long as Emacs can't read our minds, there will be no good-enough
> completion mechanism. And even then... we are dealing with the Emacs
> user base, you know :-)

Yes.  Not only are users different but they use different
contexts, and the same user has different preferences in
different contexts.

And even when user A's preference for a particular context
is Preference-AA, s?he can sometimes want to change things
dynamically - in this case, change sort ordering.

A default, context-specific user preference-driven sort
order is fine, but a user can still want to change orders
on the fly.  That can happen, among other reasons, due to
what s?he is currently typing as an input pattern.

Re: new-flex-completion-style

[João Távora]

Daniel Pittman <slippycheeze@google.com> writes:

>  > Feel free to add some kind of normalization to the function
>  > if you can come up with it.  Or come up with another function
>  > entirely.  As I said, a function that measures the distance
>  > in "boring editing operations" between the pattern and the target
>  > would be a nicer measure.
>
> The Levenshtein distance and close variants generally do a reasonable
> job of approximating human expectations, yes.  Close variants (eg:
> only delete/insert, no mutate) also work well.

`string-distance' in Emacs is the Levenshtein distance and it does a
terrible job.  it says "foo" is as close to "foobar" as it is to
"fboror", which is not acceptable.  And neither is a variant like
Damerau–Levenshtein.  I could possibly use a variant that computes
things in "elementary boring editing operations", which includes moves.

There is a fundamental misunderstanding on your side I think.  The
distance formulae exist to solve another class of problems, which
include comparing strings of characters where one is _not_ a subsequence
of the other (a subsequence being a not-necessarily-contiguous in-order
subset of elements).  Often these problems want to compute not only the
distance _and_ but also the set of insertion, deletions, transposition
that bring a string to another.  This is why they are slow.  But they do
enable fancy things like auto-correct.

Those occur in the super well-studied high-tech fields that you suggest
I'm ignorant of.  And while I'm certainly no expert on the matter, I do
think none of that matters here.  Emacs uses things like "string-match"
to tell if a string matches another.  If it doesn't it doesn't, and
that's OK for "flex".

If, for some reason, the regexp starts being slow for flex-matching,
since it writes a regexp like ".*f.*o.*o.*", then it's very easy to
optimize these flex patterns in C directly.  A greedy implementation
(which is fine) will be just O(n).

So I don't know what speed problems you are referring to.  Neither is it
clear to me what fields your "fzf" suggestion would be "blazingly fast"
(as it self-describes itself) and/or how plugging it into Emacs would
solve anything.

In short for "flex", at least for the "flex" I'm interested in, Emacs
can separate the matching and scoring problem, so your worries do not
make sense.  This "flex" style even already exists in Emacs, but only in
ido.el.  That's what I'm trying to being to other areas of Emacs.

On the other hand, if you're writing an "autocorrection" completion
style then yes, these things could start making sense.  But I'm not
writing that.

> PPS: the best modern tools seem to be derived from the problem of
> genome sequence matching, but heuristics are definitely helpful too.
> Again, fzf is the best version of that I have found.

Does it autocorrect?  If yes, it might be a good choice for that other
completion style you may be describing.  It's hardly a good choice for
"flex".

João

Re: new-flex-completion-style

[João Távora]

João Távora <joaotavora@gmail.com> writes:

> subset of elements).  Often these problems want to compute not only the
> distance _and_ but also the set of insertion, deletions, transposition
           ^^^^^
Doh. Messed up the grammar there.  To be clear I meant these
problems want the distance _and_ the operations that transform one
string into another.

João

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 3:33 PM Óscar Fuentes <ofv@wanadoo.es> wrote:
>
> João Távora <joaotavora@gmail.com> writes:
>
> > Eventually we could weight the number and length
> > of holes differently so we can get this:
> >
> > score(foo,barfoobaz) > score(foo,fabrobazo) >
> > score(foo,fotttttttttttttttttttttto)
> >
> > Which would be nicer, I think.
>
> My experience on this type of discussions about flx says that you should
> design a scoring algorithm based on some generic, human-related
> heuristic that makes sense to you and stick to it. You will hear lots of
> complaints by those that dislike the system, showing specific examples
> that demonstrate "obvious" deficiencies on your approach. But it is
> impossible to create something that makes everybody happy.

I agree with all your arguments, but I do think Stefan has a pretty
good point in that example.  There's no reason not to heed it.

> As long as Emacs can't read our minds, there will be no good-enough
> completion mechanism. And even then... we are dealing with the Emacs
> user base, you know :-)

Indeed...

RE: new-flex-completion-style

[Drew Adams]

> The Levenshtein distance and close variants generally do
> a reasonable job of approximating human expectations, yes.
> Close variants (eg: only delete/insert, no mutate) also
> work well.
>
> The cost of building the Levenshtein edit distance matrix
> for picking or ordering candidates is quite high, though; ...
> gives a good summary, and you really don't want to use the
> most naive option if you can avoid it.  Computation costs
> go through the roof very fast; the cost is roughly
> proportional to the length of the candidate cubed, using the
> brute force approach.
>
> The other shortfall of using only edit distance is that most
> of the time people expect to front-weight the search: you
> may have a closer edit distance match later in the string,
> but people usually want a less exact match, closer to the
> start, intuitively.
>
> > I've been experimenting with a simpler function that just
> > counts the number of "holes" and the length of those holes
> > separately in the denominator. The numerator is the same
> > and a perfect match is still a 1. It seems to fare better
> > for your cases. For foo
>
> I'd very, very strongly encourage y'all to take a look at
> the existing work on the problem, not least because of the
> algorithmic complexity costs when you apply this to a large
> corpus of candidates.  Consider, for example, completion
> over the set of all defined symbols in Emacs, which is
> ~ 55,000 candidates, and IIRC I calculated the average
> length to 9 characters, so brute force matching would be
> be on the order of 40 **million** comparisons for the first
> pattern character, though thankfully dropping fast as you
> eliminate non-matching candidates entirely.  (Raw comparisons,
> accounting for all possible matches in all possible candidate,
> of that pattern, so each candidate gets
> $length / $pattern_length comparisons performed.)
>
> Anyway, the point is: this is an area where serious study
> has been invested, and I strongly urge you to take advantage
> of that, rather than trying to reinvent this surprisingly
> complex wheel.  This isn't simple to do, and it definitely
> isn't simple to do in a high performance way.
>
> PS: whatever else you do, make it trivial to configure what
> function is used for ordering the candidate results.  That
> matters far more that the details of the default match /
> order choice, because it allows easy innovation over time.
>
> PPS: the best modern tools seem to be derived from the
> problem of genome sequence matching, but heuristics are
> definitely helpful too.  Again, fzf is the best version of
> that I have found.

All good info; thanks.  +1 for (1) emphasizing the cost
in general/naive cases and for (2) saying "make it trivial
to configure" the sort order (function).

João's (first) reply to you, saying that an interactive
Emacs context (e.g. completion) has needs that can be a
bit different, is also relevant.

FWIW, here is how Icicles uses (2 kinds of) Levenshtein
matching:

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

And here is how it uses a Jaro-Winkler matching:

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

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 4:34 PM Drew Adams <drew.adams@oracle.com> wrote:
> João's (first) reply to you, saying that an interactive
> Emacs context (e.g. completion) has needs that can be a
> bit different, is also relevant.
>
> FWIW, here is how Icicles uses (2 kinds of) Levenshtein
> matching:
>
> https://www.emacswiki.org/emacs/Icicles_-_Completion_Methods_and_Styles#LevenshteinCompletion
>
> And here is how it uses a Jaro-Winkler matching:
>
> https://www.emacswiki.org/emacs/Icicles_-_Completion_Methods_and_Styles#JaroWinklerMatchCompletion

Earlier, I forgot to tell you that I had visited your page (this is
where I learned the "scatter" alias) and for the record I'm
(re)implementing your "Scatter-Match (Flex) Completion" thing:

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

Tho the equivalent regexp I'm using here is ".*a.*b.*c.*" not "a.*b.*c"
as your page states.  Anyway, what kind of scoring, if any, do you
use for sorting the matches to that particular completion style?

João









-- 
João Távora

RE: new-flex-completion-style

[Drew Adams]

> Earlier, I forgot to tell you that I had visited your page (this is
> where I learned the "scatter" alias) and for the record I'm
> (re)implementing your "Scatter-Match (Flex) Completion" thing:
> 
>   https://urldefense.proofpoint.com/v2/url?u=https-
> 3A__www.emacswiki.org_emacs_Icicles-5F-2D-5FCompletion-5FMethods-5Fand-
> 5FStyles-
> 23toc8&d=DwIFaQ&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=kI3P6lj
> Gv6CTHIKju0jqInF6AOwMCYRDQUmqX22rJ98&m=27ypntXsw7g-l7Nfe2JaeDgtsetIas-
> Qq30T2GdC_58&s=C4LaFFUPksrZ2l6B04Ovt4T-kt8Tz4xwZN2EO-z8iuk&e=
> 
> Tho the equivalent regexp I'm using here is ".*a.*b.*c.*" not "a.*b.*c"
> as your page states.

With Icicles regexp matching for completion you don't need the
initial `.*'.

> Anyway, what kind of scoring, if any, do you use for sorting
> the matches to that particular completion style?

I don't use any scoring for scatter matching.

Icicle users usually have a bunch of sort orders they can use
(which set can depend on the particular command and on user
preferences).  One of them is "by flx score", which uses a
score provided by `flx.el'.  With scatter matching users can
use any sort order allowed for the given command.

This page has a list of most of the sort orders available
by default:

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

When completing, in the mode-line of `*Completions*' you see
the number of matching candidates (e.g. 925), the match
method (e.g. `scatter completion'), and the sort order (e.g.
`by flx score').

---

[The two Icicles matchings using (1) `fuzzy-match.el' and
(2) Swank fuzzy matching each impose a sort order - users
can't switch sort orders when they use these two kinds of
matching.

These two are the kinds of fuzzy matching available for
"prefix" Icicles completion, i.e., using `TAB'.  The others,
such as scatter and levenshtein, are available for "apropos"
completion, i.e., using `S-TAB'.]

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 5:49 PM Drew Adams <drew.adams@oracle.com> wrote:
> > Tho the equivalent regexp I'm using here is ".*a.*b.*c.*" not "a.*b.*c"
> > as your page states.
> With Icicles regexp matching for completion you don't need the
> initial `.*'.

Let me state it another way.  Does your system match "foo"
to "barfoobaz" or does it fail?  If so, then I think your
_equivalent_ regexp is probably .*f.*o.*o.*

> I don't use any scoring for scatter matching.
> Icicle users usually have a bunch of sort orders they can use

Right. Which one do you use, when you use scatter-matching?

João

RE: new-flex-completion-style

[Drew Adams]

> > > Tho the equivalent regexp I'm using here is ".*a.*b.*c.*" not
> > > "a.*b.*c" as your page states.
> >
> > With Icicles regexp matching for completion you don't need the
> > initial `.*'.

And you don't need the final `.*', I should have added
(didn't notice it in your pattern).

It sounds like you're always trying to match all chars
in a line.  I'm not.  I'm not dealing with lines, in
general.  I'm matching a pattern against a string, in
general.
 
> Let me state it another way.  Does your system match "foo"
> to "barfoobaz" or does it fail?

It matches.

> If so, then I think your _equivalent_ regexp is probably .*f.*o.*o.*

(string-match-p "f.*o.*o" "barfoobaz") => 3

Scatter-matching is used with "apropos" completion.
It's just regexp completion, using the substituted
regexp.  Substituting regexp `f.*o.*o' for input
`foo' just does the above `string-match-p'.

> > I don't use any scoring for scatter matching.
> > Icicle users usually have a bunch of sort orders they can use
> 
> Right. Which one do you use, when you use scatter-matching?

Any of them.  Depends on what I'm doing and what I want.
Scatter-matching is typically not specific to particular
contexts, and thus to any context-specific sort orders.

Can you see that some of the following predefined orders
might be advantageous in particular contexts/use cases?
Can you see that whether matching is scatter, regexp,
basic prefix, or others, any of the following can be
useful?

(As I said, there are a couple of fuzzy-match methods
that impose their own sort order, but most do not.
Similarly, a few commands impose their own sort order -
they don't allow re-sorting.)

some of the Icicles sort orders that exist by default:

General:

 alphabetical
 case-insensitive
 by last use as input
 by previous use alphabetically

Color completion:

 by color name (colors)
 by hue (colors)
 by purity/saturation (colors)
 by brightness/value/luminance (colors)
 by all HSV components, in order (colors)
 by HSV distance from a base color (colors)
 by amount of red (colors)
 by amount of green (colors)
 by amount of blue (colors)
 by all RGB components, in order (colors)
 by RGB distance from a base color (colors)

Key completion:

 by key name, prefix keys first (keys)
 by key name, local bindings first (keys)

Command completion:

 by command name (commands)
 by abbrev frequency (commands)

Buffer-name completion:

 by buffer size (buffer names)
 *…* buffers last (buffer names)
 by major mode name (buffer names)
 by mode-line mode name (buffer names)
 by file/process name (buffer names)

File-name completion:

 by last file modification time (file names)
 by file type (extension) (file names)
 by directories first or last (file names)

Other:

 in book order (Info)
 special candidates first
 proxy candidates first
 extra candidates first
 by second multi-completion part (multi-completions)

 turned OFF (does not sort at all) 

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 7:20 PM Drew Adams <drew.adams@oracle.com> wrote:

> > If so, then I think your _equivalent_ regexp is probably .*f.*o.*o.*
> (string-match-p "f.*o.*o" "barfoobaz") => 3

Right, sorry for the confusion.

> Can you see that some of the following predefined orders
> might be advantageous in particular contexts/use cases?
> Can you see that whether matching is scatter, regexp,
> basic prefix, or others, any of the following can be
> useful?

No, I can't. That's probably input for the style vs category vs table
vs UI debate, where I'd rather, like Stefan, go for the path of
least redesign which seems to plug sorting to a style.

Perhaps I'll change my opinion with specific use cases where
using my proposed sorting function with flex isn't a good
solution.

Thanks anyway,
João

João Távora

RE: new-flex-completion-style

[Drew Adams]

> > Can you see that some of the following predefined orders
> > might be advantageous in particular contexts/use cases?
> > Can you see that whether matching is scatter, regexp,
> > basic prefix, or others, any of the following can be
> > useful?
> 
> No, I can't.

Seriously?  You can't imagine that someone completing
buffer names might want to (sometimes) put more
recently used buffer names before others for better
visibility or for quicker cycling access?

You can't imagine anyone ever wanting a different
order of candidates than what you would define based
on match scores?

Match scores are tightly linked to sort order only
for certain kinds of matching.  And even then such
an ordering is typically "all other things being
equal", i.e., for lack of any more meaningful sort.

What you say sounds bizarre to me.  Different contexts
can call for different sort orders.  And different
commands provide different contexts, as do different
user preferences.

Take Info nodes for `g', for instance.  Can't you
imagine that sometimes you might want to see completion
matches in book order, and other times in order of the
dates of your past visits, and other times in order of
the number of your visits, and other times in
alphabetical order?

And even for, say, number of visits, can you imagine
that sometimes you want to visit nodes that you've
visited a lot, and other times you might want to visit
nodes that you've never visited?

Do you really feel that one size (one order) fits all?

> That's probably input for the style vs category vs table
> vs UI debate, where I'd rather, like Stefan, go for the path of
> least redesign which seems to plug sorting to a style.

My own opinion on that is that what's important is that
a user be able to control such things on the fly.  Sort
order, for example: be able to immediately change it by
hitting a key while completing.

AFAIK (I could be wrong; I don't bother following this
evolution), vanilla Emacs doesn't even give users a way
to change completion styles on the fly.  Adding a sort
order or a category or whatever else to a style definition
doesn't help if a user can't turn on a dime, switching
to a different style.

What's more: As long as accommodation is attempted by
_combining_ such (pretty independent) things: sort order,
match method, categories, users will lose.

Why?  Because even if you give them a way to quickly
switch styles they can't switch parts of a style.  With
3 axes (order, matching, category) and with, say, 4
choices per axis, that's a lot of possible combinations.

To allow a user to pick any of those combinations s?he'd
need a style for each combination!  And then s?he'd have
to be able to remember them all and keep track of them.

No, the right approach, I think, is to let users move
at will, fluidly, along any such axis, to get any
combination anytime.  All a user needs to remember in
that case is a key to choose something on a given axis.

But no, I'm not trying to design or redesign vanilla
Emacs completion.  I tried to communicate all of this
long ago, and several times.  No takers.  So be it.
Been there; done that.  (I have, however, seen several
of the ideas picked up by other completion systems:
Helm, Ivy, even Ido and Icomplete in some cases.)

> Perhaps I'll change my opinion with specific use cases where
> using my proposed sorting function with flex isn't a good
> solution.

You should be able to change from, or to, it on the fly,
when you find that useful.  Then, being a believer in
your thing, you would set it as your preferred default
behavior.  But you'd still be able to pop out of the
box when you felt like it, and _without_ customizing
some preference and then starting over.

Re: new-flex-completion-style

[João Távora]

On Thu, Feb 14, 2019 at 10:04 PM Drew Adams <drew.adams@oracle.com> wrote:
> > > Can you see that some of the following predefined orders
> > No, I can't.
> Seriously?

Yes.


João Távora

Re: new-flex-completion-style

[Stefan Monnier]

>> > Can you see that some of the following predefined orders
>> > might be advantageous in particular contexts/use cases?
>> > Can you see that whether matching is scatter, regexp,
>> > basic prefix, or others, any of the following can be
>> > useful?
>> No, I can't.
> Seriously?

All the examples you give are non-specific to the completion-style used,
whereas the `flx` scoring seems more directly related to the
completion style.

I guess one could consider `flx` scoring as just another kind of
sorting, but I'm pretty sure that it can give odd results when used
with (say) regexp-style completion.

So maybe, another way to look at it is that there are several sorting
choices, one of them being provided by the completion-style.


        Stefan

RE: new-flex-completion-style

[Drew Adams]

> >> > Can you see that some of the following predefined orders
> >> > might be advantageous in particular contexts/use cases?
> >> > Can you see that whether matching is scatter, regexp,
> >> > basic prefix, or others, any of the following can be
> >> > useful?
> >> No, I can't.
> > Seriously?
> 
> All the examples you give are non-specific to the completion-style used,
> whereas the `flx` scoring seems more directly related to the
> completion style.

The sort order that a user might want in any
given context can depend on any number of things.

Some completion styles might be context-related
(i.e., more suited to some kinds of completion,
e.g. file names, than to other kinds).  But for
the most part they are not.  Categories bring us
closer to use contexts/cases than styles, I guess.

But actually, I did mention two fuzzy-matching
methods that impose the sort order used - they
give you no other sort choice.  In particular,
they can't give you a sort order that is
especially useful for a certain context.

I don't see scatter-matching as limiting in
that way.  You can use it with the sort orders
I listed.  That's not the case for
`fuzzy-match.el' matching or Swank fuzzy symbol
matching.

> I guess one could consider `flx` scoring as just another kind of
> sorting, but I'm pretty sure that it can give odd results when used
> with (say) regexp-style completion.

Depends on the regexp.  But sure, you wouldn't
want to sort based on scoring that privileges
substring match length for input that is a wild
regexp.

FWIW, Icicles uses `flx' _only_ for sorting (by
`flx-score'), not for matching.  And yes, it's
just another sorting method.  I could have
included it in the list I showed.  And yes, it's
not context-specific (though it's likely more
useful with some contexts than with others).

> So maybe, another way to look at it is that there are several sorting
> choices, one of them being provided by the completion-style.

That goes back to my point about coupling such
things together (matching and sorting) versus
decoupling and so letting a user mix & match
(modulo the rare exception).

If a user specifies a particular sort order
in a completion style then s?he can't also
use the rest of that style without that sort
order, or vice versa - not without defining
additional completion styles that provide
those other possibilities.

Sure, allowing a style to include a sort can
be handy if you want to use that combination
a lot.  It can also be limiting.

Why didn't you just include categories, not
as separately specifiable, but only as part
of styles?

Surely you saw an advantage in being able to
mix & match.  Same thing applies to sorting,
in general (i.e. modulo some exceptions, as
mentioned).

Being able to include a sort order in a style
is one thing.  Having to do that, to be able
to choose a sort order, is another thing.

Re: new-flex-completion-style

[Stefan Monnier]

>> I guess one could consider `flx` scoring as just another kind of
>> sorting, but I'm pretty sure that it can give odd results when used
>> with (say) regexp-style completion.
> Depends on the regexp.  But sure, you wouldn't
> want to sort based on scoring that privileges
> substring match length for input that is a wild
> regexp.

My point is that flx scoring is usually based on the idea that the
candidate does match using flx matching, whereas that might not be the
case is the matching was done some other way.  So the scoring result can
be completely meaningless (or it could even signal an error).

IOW matching and scoring can be intimately linked because the scoring is
based on *how* the candidate matched the input.


        Stefan

Re: new-flex-completion-style

[Dmitry Gutov]

On 15.02.2019 07:50, Stefan Monnier wrote:
> My point is that flx scoring is usually based on the idea that the
> candidate does match using flx matching, whereas that might not be the
> case is the matching was done some other way.  So the scoring result can
> be completely meaningless (or it could even signal an error).

Scoring is already performed by the style. That doesn't necessarily mean 
that sorting must be, too. Especially if the score is stored in a 
neutrally-named text property.

RE: new-flex-completion-style

[Drew Adams]

> >> I guess one could consider `flx` scoring as just another kind of
> >> sorting, but I'm pretty sure that it can give odd results when used
> >> with (say) regexp-style completion.
> > Depends on the regexp.  But sure, you wouldn't
> > want to sort based on scoring that privileges
> > substring match length for input that is a wild regexp.
> 
> My point is that flx scoring is usually based on the idea that the
> candidate does match using flx matching, whereas that might not be the
> case i[f] the matching was done some other way.  So the scoring result can
> be completely meaningless (or it could even signal an error).
> 
> IOW matching and scoring can be intimately linked because the scoring is
> based on *how* the candidate matched the input.

Yes.  And regexp matching is an outlier.  My point
about regexp matching was that for completion many
actual uses of regexp matching are substring matches
or close to it.  (`foobar' is a regexp.)

And besides this being the case for perhaps most
regexp-input matches (for completion), most other
match methods involve input chars that are also in
the candidates, so flx scoring even with non-flx
matching is generally not outlandish.

I think flx-score sorting is probably more useful
when you've typed relatively little and there are
many matches.  In a way it privileges, by sorting
(and hence for access by, e.g., cycling), candidates
that might match in two different ways, the optional
one being flx.

And yes, again, flx scoring is no doubt more useful
with some match methods than with others.  Finally,
I can't tell you how useful it might really be.
YMMV.  I can say that it's another sort order. ;-)

FWIW, the predicate I actually use for sorting by
`flx-score' just does alphabetical comparison if
the input doesn't return a `flx-score' for each of
the two candidates (i.e., if at least one does not
flx-match your input).

(defun icicle-flx-score-greater-p (s1 s2)
  "Non-nil means the `flx-score' of S1 is greater than that of S2.
That is, the cars of the `flx-score' values are compared.

If `flx-score' returns nil for either argument, then they are compared
using `icicle-case-string-less-p'.

This function requires library `flx.el'."
  (let* ((input   (if (and (icicle-file-name-input-p)
                           insert-default-directory)
                      (file-name-nondirectory
                        icicle-current-input)
                    icicle-current-input))
         (score1  (flx-score s1 input))
         (score2  (flx-score s2 input)))
    (if (and score1  score2)
        (> (car score1) (car score2))
      (icicle-case-string-less-p s1 s2))))

Re: new-flex-completion-style

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 504 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> How 'bout we change the buffer name completion table so it specifies its
> own cycle-sort-function which uses buffer-list, then.  It seems like it
> would be a clear win (the buffer-list order is a much better heuristic
> than the length).

Hi again,

Here are two patches: the first does exactly what you propose above, the
second goes a little bit further, but I still think it's the right
thing...

Lightly tested stuff...

João


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-switch-to-buffer-s-completion-table-uses-its-own-sor.patch --]
[-- Type: text/x-diff, Size: 1387 bytes --]

From f170e728c1c1ac426bb73c63cc54ba2ae30afd1a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Jo=C3=A3o=20T=C3=A1vora?= <joaotavora@gmail.com>
Date: Mon, 18 Feb 2019 20:32:38 +0000
Subject: [PATCH 1/2] switch-to-buffer's completion table uses its own sorting

* src/minibuf.c (Finternal_complete_buffer): Add
Qcycle_sort_function to completion table's metadata.
(syms_of_minibuf): New symbol Qcycle_sort_function.
---
 src/minibuf.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/src/minibuf.c b/src/minibuf.c
index 321fda1ba8..b23e24c4bd 100644
--- a/src/minibuf.c
+++ b/src/minibuf.c
@@ -1801,7 +1801,9 @@ If FLAG is nil, invoke `try-completion'; if it is t, invoke
   else if (EQ (flag, Qlambda))
     return Ftest_completion (string, Vbuffer_alist, predicate);
   else if (EQ (flag, Qmetadata))
-    return list2 (Qmetadata, Fcons (Qcategory, Qbuffer));
+    return list3 (Qmetadata,
+                  Fcons (Qcategory, Qbuffer),
+                  Fcons (Qcycle_sort_function, Qidentity));
   else
     return Qnil;
 }
@@ -1922,6 +1924,8 @@ syms_of_minibuf (void)
   DEFSYM (Qactivate_input_method, "activate-input-method");
   DEFSYM (Qcase_fold_search, "case-fold-search");
   DEFSYM (Qmetadata, "metadata");
+  DEFSYM (Qcycle_sort_function, "cycle-sort-function");
+
   /* A frame parameter.  */
   DEFSYM (Qminibuffer_exit, "minibuffer-exit");
 
-- 
2.20.0


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-cycle-sort-function-prevails-in-completion-all-sorte.patch --]
[-- Type: text/x-diff, Size: 2328 bytes --]

From f8ce65482d86a136f1320dac89e71662256c2168 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Jo=C3=A3o=20T=C3=A1vora?= <joaotavora@gmail.com>
Date: Mon, 18 Feb 2019 20:41:09 +0000
Subject: [PATCH 2/2] cycle-sort-function prevails in
 completion-all-sorted-completions

* lisp/minibuffer.el (completion-all-sorted-completions): Don't
re-sort if completion table has cycle-sort-function.
---
 lisp/minibuffer.el | 22 +++++++++++++---------
 1 file changed, 13 insertions(+), 9 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 7413be42eb..cc87ffaced 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1246,20 +1246,23 @@ completion-all-sorted-completions
           (setq all (delete-dups all))
           (setq last (last all))
 
-          (setq all (if sort-fun (funcall sort-fun all)
-                      ;; Prefer shorter completions, by default.
-                      (sort all (lambda (c1 c2) (< (length c1) (length c2))))))
-          ;; Prefer recently used completions and put the default, if
-          ;; it exists, on top.
-          (when (minibufferp)
-            (let ((hist (symbol-value minibuffer-history-variable)))
-              (setq all (sort all
+          (cond
+           (sort-fun
+            (setq all (funcall sort-fun all)))
+           (t
+            ;; Prefer shorter completions, by default.
+            (setq all (sort all (lambda (c1 c2) (< (length c1) (length c2)))))
+            (when (minibufferp)
+              ;; Prefer recently used completions and put the default, if
+              ;; it exists, on top.
+              (let ((hist (symbol-value minibuffer-history-variable)))
+                (setq all
+                      (sort all
                             (lambda (c1 c2)
                               (cond ((equal c1 minibuffer-default) t)
                                     ((equal c2 minibuffer-default) nil)
                                     (t (> (length (member c1 hist))
-                                          (length (member c2 hist))))))))))
+                                          (length (member c2 hist))))))))))))
           ;; Cache the result.  This is not just for speed, but also so that
           ;; repeated calls to minibuffer-force-complete can cycle through
           ;; all possibilities.
-- 
2.20.0

Re: new-flex-completion-style

[Stefan Monnier]

> @@ -1801,7 +1801,9 @@ If FLAG is nil, invoke `try-completion'; if it is t, invoke
>    else if (EQ (flag, Qlambda))
>      return Ftest_completion (string, Vbuffer_alist, predicate);
>    else if (EQ (flag, Qmetadata))
> -    return list2 (Qmetadata, Fcons (Qcategory, Qbuffer));
> +    return list3 (Qmetadata,
> +                  Fcons (Qcategory, Qbuffer),
> +                  Fcons (Qcycle_sort_function, Qidentity));
>    else
>      return Qnil;
>  }

That easy, huh?

> * lisp/minibuffer.el (completion-all-sorted-completions): Don't
> re-sort if completion table has cycle-sort-function.

I think a more precise description would be that cycle-sort-function now
also overrides the use of minibuffer-history-variable.
[ "Don't re-sort" sounds like a mere optimization rather than a change
  of semantics.  ]

Other than that, LGTM,


        Stefan

Re: new-flex-completion-style

[João Távora]

On Mon, Feb 18, 2019 at 11:35 PM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> > +                  Fcons (Qcategory, Qbuffer),
> > +                  Fcons (Qcycle_sort_function, Qidentity));
> >    else
> >      return Qnil;
> >  }
> That easy, huh?

Yep, and does the right thing default-wise, too.  If I'm not mistaken,
I'd say it behaves exactly like ido-switch-to-buffer now, which doesn't
use score-based sorting, when icomplete-mode is used with the
new flex completion style.

BTW, has the council of completion elders reached any sort of
white-smoke decision vis-à-vis where to score-sort?

> I think a more precise description would be that cycle-sort-function now
> also overrides the use of minibuffer-history-variable.

That's in the commit message's subject line, but OK I've changed it.

Re: new-flex-completion-style

[Stefan Monnier]

> Yep, and does the right thing default-wise, too.  If I'm not mistaken,
> I'd say it behaves exactly like ido-switch-to-buffer now, which doesn't
> use score-based sorting, when icomplete-mode is used with the
> new flex completion style.

;-)

> BTW, has the council of completion elders reached any sort of
> white-smoke decision vis-à-vis where to score-sort?

It's been too foggy around here lately to see much smoke, sorry.

>> I think a more precise description would be that cycle-sort-function now
>> also overrides the use of minibuffer-history-variable.
> That's in the commit message's subject line, but OK I've changed it.

Who reads the first line anyway?
[ After reading that first line: ] but that didn't make it clear that
the change is about the use of minibuffer-history-variable (the only
part which used to prevail over cycle-sort-function, AFAICT).


        Stefan

Re: new-flex-completion-style

[João Távora]

On Tue, Feb 19, 2019 at 12:54 PM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> >> I think a more precise description would be that cycle-sort-function now
> >> also overrides the use of minibuffer-history-variable.
> > That's in the commit message's subject line, but OK I've changed it.
>
> Who reads the first line anyway?
> [ After reading that first line: ] but that didn't make it clear that
> the change is about the use of minibuffer-history-variable (the only
> part which used to prevail over cycle-sort-function, AFAICT).

Because of my other change to that function, it now also
prevails over minibuffer-default. This is why I didn't specifically
mention minibuffer-history-variable. That and writing commit
messages is hard.

Take care,
João

Re: new-flex-completion-style

[Stefan Monnier]

> Because of my other change to that function, it now also
> prevails over minibuffer-default.  This is why I didn't specifically
> mention minibuffer-history-variable.  That and writing commit
> messages is hard.

The upside is that nitpicking is easy,


        Stefan

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Stefan Monnier]

>> So, not only it will only work with some completion tables, but for that
>> you'll need to introduce "wrong" code in those completion tables.
> Since we seem to want to redo completion tables in a major way anyway,

That's no guarantee that it will happen soon or at all, and it will have
to provide some backward compatibility.  And the more hacks we see using
the current system, the more difficult backward compatibility may become.

> I wouldn't worry about that too much, as long as the result is functional.

It'd be OK if it's indispensable, but I think there are better
alternatives that are easy to install right away.

>> I'd rather we extend the infrastructure so that completion styles can do
>> their own sorting.
> That's one option. Another option, which I've mentioned before, is to create
> an indirection for sorting functions via the completion table's
> category.  Similar to the one that completions styles have.

But those are orthogonal: the completion style can offer one kind of
sorting and that should work for all completion tables.
Completion tables can also offer their own kind of sorting (and it
should work with all completion styles).

How 'bout:

- Add global sorting config var(s?), to choose which kind of sorting to
  use, which would default to sorting based on "scores first and
  alphabetical after that".
- Let completion-category-overrides specify other choices.

This leaves some questions unanswered, tho:

- What about the distinction between cycle-sort and display-sort?
- Should the new var and new entries in completion-category-overrides
  contain directly sorting functions, or should they contain just the
  name of "sorting styles" with a separate table mapping those styles to
  actual functions (e.g. because a given style like `date` might be
  implemented differently for different completion tables?).
- Should we allow completion tables to offer several sorting choices?

In any case, in the mean time we can probably just introduce the new
sorting based on "scores first and alphabetical after that" and use it
by default.

> The category-based approach should circumvent that problem.
> With this approach, completion styles don't indicate sorting, and whatever
> entity did set up the completion style to be used (the user, a configuration
> package, etc) would need to set up both completion styles and sorting
> functions to match.

I think it'd be annoying for users to have to not only add `flex` to
their completion-styles but also change some sorting option at the same
time before that completion style becomes usable (in most cases, the
current alphabetical sorting works really poorly for `flex`).

> I think text properties are fine here.

It has its downsides, but I agree it seems like the better choice.


        Stefan

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 19.02.2019 19:10, Stefan Monnier wrote:
>>> So, not only it will only work with some completion tables, but for that
>>> you'll need to introduce "wrong" code in those completion tables.
>> Since we seem to want to redo completion tables in a major way anyway,
> 
> That's no guarantee that it will happen soon or at all, and it will have
> to provide some backward compatibility.  And the more hacks we see using
> the current system, the more difficult backward compatibility may become.

Very well.

This may be off topic now, but to the best of my recollection this 
discussion started from the question of the ability to add flex matching 
to particular completion tables. So that's where I was coming from, FWIW.

> But those are orthogonal: the completion style can offer one kind of
> sorting and that should work for all completion tables.

Orthogonal indeed, but it should be easier, implementation-wise, to only 
have one way that defines sorting logic. And also easier to port to the 
"new system", whenever that comes.

Also also, combining the flex sorting with most other kinds will most 
likely make the flex sorting hard to notice.

But please don't take this as a strong disagreement. Just an opinion.

> Completion tables can also offer their own kind of sorting (and it
> should work with all completion styles).
> 
> How 'bout:
> 
> - Add global sorting config var(s?), to choose which kind of sorting to
>    use, which would default to sorting based on "scores first and
>    alphabetical after that".

Put those defaults into completion-category-defaults, and you basically 
have my proposal, isn't that right?

> - Let completion-category-overrides specify other choices.
> 
> This leaves some questions unanswered, tho:
> 
> - What about the distinction between cycle-sort and display-sort?

TBH, I still don't know what's the difference between these. Meanwhile, 
company-capf has not support for the former, company has different kinds 
of paging through the popup, and it's working okay.

> - Should the new var and new entries in completion-category-overrides
>    contain directly sorting functions, or should they contain just the
>    name of "sorting styles" with a separate table mapping those styles to
>    actual functions (e.g. because a given style like `date` might be
>    implemented differently for different completion tables?).

Erm, I'd try the simpler approach first.

If the tables A and B are supposed to be sorted differently, couldn't 
they return different (but similarly sounding) category names?

Or if that's not generally feasible, what else would the sorting styles 
dispatch on? The tables themselves?

> - Should we allow completion tables to offer several sorting choices?

You mean different completion scores?

If you just mean other kinds of orderings, I think the user will choose 
via completion-category-overrides.

> In any case, in the mean time we can probably just introduce the new
> sorting based on "scores first and alphabetical after that" and use it
> by default.

*thumbsup*

> I think it'd be annoying for users to have to not only add `flex` to
> their completion-styles but also change some sorting option at the same
> time before that completion style becomes usable (in most cases, the
> current alphabetical sorting works really poorly for `flex`).

Apparently you're proposing to fix that by making the default sorting 
function to be flex-compatible. That sounds okay.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Stefan Monnier]

> This may be off topic now, but to the best of my recollection this
> discussion started from the question of the ability to add flex matching to
> particular completion tables. So that's where I was coming from, FWIW.

I see.  I was taking the point of view of a generic `flex` method for
use anywhere you like (I think the original motivation was to use it in
conjunction with `icomplete-mode` to more closely match to `ido`
behavior).

> Also also, combining the flex sorting with most other kinds will most likely
> make the flex sorting hard to notice.

Depends on the ordering (see below).

>> - Add global sorting config var(s?), to choose which kind of sorting to
>>    use, which would default to sorting based on "scores first and
>>    alphabetical after that".
>
> Put those defaults into completion-category-defaults, and you basically have
> my proposal, isn't that right?

completion-category-defaults is an alist providing extra settings for
specific categories, so it's not "global" in the sense I meant above
because can't be used to choose the sorting used for categories not
mentioned in completion-category-defaults.

>> - What about the distinction between cycle-sort and display-sort?
> TBH, I still don't know what's the difference between these.

display-sort is the sorting used when displaying the candidates in
a list like *Completions* whereas cycle-sort is the sorting used when
your TAB cycles through possible candidates (and it's also used in
icomplete-mode).

In display-sort we currently sort alphabetically whereas in cycle-sort
we want to use a heuristic that puts more likely choices first.

Maybe we should drop this distinction and just use the same sorting
everywhere (which would have to be the cycle-sort by default I think,
because the alphabetical sort is really a poor choice when cycling in
my experience).

The downside of the heuristic sort of cycle-sort is that sometimes/often
the heuristic is poor (by default it's just based on string
length ;-( ), so the *Completions* buffer would look "unsorted".

>> In any case, in the mean time we can probably just introduce the new
>> sorting based on "scores first and alphabetical after that" and use it
>> by default.
> *thumbsup*

OK, let's go with that for now.


        Stefan

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 27.02.2019 19:12, Stefan Monnier wrote:

> I see.  I was taking the point of view of a generic `flex` method for
> use anywhere you like (I think the original motivation was to use it in
> conjunction with `icomplete-mode` to more closely match to `ido`
> behavior).

That's a worthy goal as well, of course. Not sure it will be ideal for 
e.g. eglot's completion table, but that's a separate discussion, I guess.

>> Also also, combining the flex sorting with most other kinds will most likely
>> make the flex sorting hard to notice.
> 
> Depends on the ordering (see below).

With most helpful/meaningful kinds, then?

>>> - Add global sorting config var(s?), to choose which kind of sorting to
>>>     use, which would default to sorting based on "scores first and
>>>     alphabetical after that".
>>
>> Put those defaults into completion-category-defaults, and you basically have
>> my proposal, isn't that right?
> 
> completion-category-defaults is an alist providing extra settings for
> specific categories, so it's not "global" in the sense I meant above
> because can't be used to choose the sorting used for categories not
> mentioned in completion-category-defaults.

You mean it can't be used to change settings for the "other" categories, 
the defaults, right? Why don't we use the key 't' for this (with the 
corresponding tiny code change somewhere else)?

I think this will fit the name of the variable, as well as the way it is 
used. The function completion--category-override could use a rename in 
this case, though.

This will also let us set the completion style defaults for the "other" 
categories (and the user too, if completion-category-overrides supports 
the same).

> display-sort is the sorting used when displaying the candidates in
> a list like *Completions* whereas cycle-sort is the sorting used when
> your TAB cycles through possible candidates (and it's also used in
> icomplete-mode).

I see, thanks.

> In display-sort we currently sort alphabetically whereas in cycle-sort
> we want to use a heuristic that puts more likely choices first.
> 
> Maybe we should drop this distinction and just use the same sorting
> everywhere (which would have to be the cycle-sort by default I think,
> because the alphabetical sort is really a poor choice when cycling in
> my experience).

Yeah, I do believe we'd prefer the most likely choices at the top in the 
display-sort case as well (or for company-capf, at least).

> The downside of the heuristic sort of cycle-sort is that sometimes/often
> the heuristic is poor (by default it's just based on string
> length ;-( ), so the *Completions* buffer would look "unsorted".

Improving the heuristics should also help, of course. But it can be left 
for later.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Stefan Monnier]

>>> Also also, combining the flex sorting with most other kinds will most likely
>>> make the flex sorting hard to notice.
>> Depends on the ordering (see below).
> With most helpful/meaningful kinds, then?

With such sorting where most candidates get a different score, it's
difficult to combine the sorting indeed: depending on the precedence we
give to each type of score either the flex sorting will be unnoticeable
or the other one will be unnoticeable.

Of course, if we're careful we can try and tune the weighting of the
types of scores so that both scoring have a visible impact, but I have
the impression that it's going to require too careful tuning to be
usable in practice.

> You mean it can't be used to change settings for the "other" categories, the
> defaults, right? Why don't we use the key 't' for this (with the
> corresponding tiny code change somewhere else)?

Ah, we could yes.  That's equivalent to using another global var, indeed.
Currently we use global vars (completion-styles and
completion-cycle-threshold) for that purpose, mostly by accident.

>> The downside of the heuristic sort of cycle-sort is that sometimes/often
>> the heuristic is poor (by default it's just based on string
>> length ;-( ), so the *Completions* buffer would look "unsorted".
> Improving the heuristics should also help, of course. But it can be left
> for later.

I'm afraid that if we drop the display-sort and use cycle-sort
everywhere, there's going to be a very strong reaction from users not
appreciating the change.  Even more so if the heuristic is poor.


        Stefan

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 1668 bytes --]

On Mon, Mar 11, 2019, 00:18 Dmitry Gutov <dgutov@yandex.ru> wrote:

> On 27.02.2019 19:12, Stefan Monnier wrote:
>
> > I see.  I was taking the point of view of a generic `flex` method for
> > use anywhere you like (I think the original motivation was to use it in
> > conjunction with `icomplete-mode` to more closely match to `ido`
> > behavior).
>
> That's a worthy goal as well, of course. Not sure it will be ideal for
> e.g. eglot's completion table, but that's a separate discussion, I guess.
>

I've been very busy and just caught up with this discussion. I can't
contribute much more right now other than confirming Stefan's intuition for
the original motivation. I wanted, and want, icomplete to be as usable as
ido.el (with the added advantage of being well behaved). But I also want
eglot.el and elisp's completion-at-point to be able to flex-match like,
i.e. Sly does. So basically I want to be able to flex match everywhere.

Regarding sorting, after using it  in icomplete, C-x b, C-x f, M-x for a
while now, I can say this: There seems to be no case where I wouldn't like
flex's scoring to be the dominant, but I haven't turned it on right now
(mostly because there's no easy way yet due to this analysis-paralysis),
and the table's scoring for those three seems sufficient in a reasonable
number of the situations. When completing larger sets, such as
company-completing all elisp symbols for writing code, flex scoring becomes
indispensable, because the secondary sorting there is lexicographic.

Not sure what you can make of this, but if you can, make something :), and
thanks very much for working on this.

João

[-- Attachment #2: Type: text/html, Size: 2404 bytes --]

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 11.03.2019 03:15, Stefan Monnier wrote:
> Of course, if we're careful we can try and tune the weighting of the
> types of scores so that both scoring have a visible impact, but I have
> the impression that it's going to require too careful tuning to be
> usable in practice.

While possible, I think in practice it will require using just one 
combined sorting function, instead of passing the list of completions 
though several independent sorting functions. Although please feel free 
to prove me wrong, because I like the list-of-functions approach.

> Ah, we could yes.  That's equivalent to using another global var, indeed.
> Currently we use global vars (completion-styles and
> completion-cycle-threshold) for that purpose, mostly by accident.

Fair enough.

completion-sort-functions, then?

> I'm afraid that if we drop the display-sort and use cycle-sort
> everywhere, there's going to be a very strong reaction from users not
> appreciating the change.  Even more so if the heuristic is poor.

In that case I'd suggest dropping cycle-sort and, for now, keeping 
display-sort behavior as is. But make additional sorting configurable 
like we've been discussing, via completion-sort-functions, as well as 
package/user overrides in completion-category-*.

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 11.03.2019 10:47, João Távora wrote:
> But I also want eglot.el and elisp's completion-at-point to be able to 
> flex-match like, i.e. Sly does. So basically I want to be able to flex 
> match everywhere.

I'm referring to the distinction that eglot uses LSP which supposedly 
has the option of fuzzy matching in the external process. Which we 
probably want to use.

And to take advantage of that possibility, the completion styles would 
have to be somewhat different.

RE: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Drew Adams]

> While possible, I think in practice it will require using just one
> combined sorting function, instead of passing the list of completions
> though several independent sorting functions. Although please feel free
> to prove me wrong, because I like the list-of-functions approach.

(Caveat: I haven't been following this thread.)

Just thought I'd mention how I like to handle a
suite of sorting predicates for dealing with things,
including completion candidates, that may or may not
be comparable to varying degrees or in different ways.

When two such cannot be compared using the preferred
sorting predicate then the next-preferred predicate
is tried, and so on.

This page explains the approach:

https://www.emacswiki.org/emacs/ApplesAndOranges

The basic idea is to allow the use of both ordinary
two-valued (true/false) predicates and three-valued
(true/false/dunno) predicates, combining the latter
in a chain.

I use this in Bookmark+, for example, to sort
candidates that are bookmarks of different kinds.

Different kinds of bookmarks have different things
in common - fields that can be compared, for example.
They can also have fields that might not be comparable.

Depending on the purpose of a given sort, users can
want to use different comparison-predicate suites,
that is, apply different sets of predicates in
different orders of priority.

Variable `bmkp-sort-comparer' holds the current
comparison suite, which is used for sorting.

The variable value is one of the following:

* `nil', meaning no sorting;
* an ordinary 2-valued predicate; or
* a list of 3-valued predicates, optionally followed
  by a single 2-valued "fallback" predicate.

If the first 3-valued predicate in the list can
compare the two given bookmarks then it decides.  If
not then the second 3-valued predicate is tried, and
so on.  If none of the 3-valued predicates can decide
then the fallback, 2-valued predicate decides.

It's easy to combine 3-valued predicates  They
decide, themselves, whether they are applicable
to their two given arguments.  If not, they just
opt out of the deciding.

Variable `bkmp-sort-comparer' is described here:

https://www.emacswiki.org/emacs/ApplesAndOranges#BmkpSortComparer

Re: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Dmitry Gutov]

On 12.03.2019 03:10, Drew Adams wrote:
> The basic idea is to allow the use of both ordinary
> two-valued (true/false) predicates and three-valued
> (true/false/dunno) predicates, combining the latter
> in a chain.
> 
> I use this in Bookmark+, for example, to sort
> candidates that are bookmarks of different kinds.

That's a pretty cute idea.

I don't know if having a heterogeneous set of candidates is going to be 
a significant use case, though.

RE: [Emacs-diffs] scratch/new-flex-completion-style 2c75775 2/2: Score, sort and annotate flex-style completions according to match tightness

[Drew Adams]

> > The basic idea is to allow the use of both ordinary
> > two-valued (true/false) predicates and three-valued
> > (true/false/dunno) predicates, combining the latter
> > in a chain.
> >
> > I use this in Bookmark+, for example, to sort
> > candidates that are bookmarks of different kinds.
> 
> That's a pretty cute idea.
> 
> I don't know if having a heterogeneous set of candidates is going to be
> a significant use case, though.

If different kinds of scores can be more meaningful
for some candidates than for others, or not available
for some candidates, then you have heterogeneous data
to compare, and multiple comparators can be relevant.

I got the impression that such was the case, but as
I said, I haven't really followed this thread.