Re: new-flex-completion-style

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> 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 :-(