Re: Improvement proposals for `completing-read'

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

>       It might deserve a completely new function to replace
>       `completing-read', but I think it would be good to make this
>       new function such that it makes `completing-read' obsolete.
>
> The cost of introduction of a new function is not to be underestimated
> in particular if it sits at a central place. Introducing another
> function which only differs slightly from the existing `completing-read'
> function could do more harm than good if it increases inconsistency and

All I meant is that the design could start from a clean slate, and
afterwards look at the result and see whether/how it can be retrofitted
into `completing-read`.

> Proposal 1: Disabling the history
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   I propose to allow the symbol `t' as `HIST' argument to
>   `completing-read' in order to disable the history. This aligns
>   `completing-read' with `read-from-minibuffer'. This change requires a
>   modification of the function `completion-all-sorted-completions',
>   which sorts the candidates by history position and currently assumes
>   that the `minibuffer-history-variable' is a variable symbol.
>
>   Example:
>   ,----
>   | (completing-read "No History: " '(first second third) nil nil nil t)
>   `----

[ I'm not sure there's a great benefit here, since in the situation
  where simplicity is what matters, using nil seems like a much better
  choice, but: ]
Good idea.

> Proposal 2: More efficient sorting
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   Currently candidate sorting is `O(m*n*log(n))' with history length m
>   and candidate list length n. This leads to a noticeable slowdown for
>   large values of `history-length'. I propose to improve the speed of
>   `completion-all-sorted-completions' by using a hash table. The Vertico
>   package provides an optimized sorting function, see `vertico--sort'.

You're asking whether we should fix a performance bug, the answer is: yes.

> Proposal 3: Sort file names by history
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   Currently `completion-all-sorted-completions' does not sort file
>   candidates based on history, when the candidates are file names and
>   the history elements are paths.

I think this is just a bug in that we don't pay attention to boundaries
when sorting.  It's probably just a matter of prepending the prefix
removed from the all-completions output when looking for an element in
the list (the end of this prefix is returned in the last `cdr` of
`completion-all-completions`).  Similarly, we may want to compare with
`string-prefix-p` rather than `equal`.

> Proposal 4: Add support for `group-function'
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   Completion tables can provide the functions `display-sort-function',
>   `cycle-sort-function', `annotation-function' and `affixation-function'
>   as completion metadata. I am proposing the addition of a
>   `group-function', which receives a list of candidates and returns a
>   list of groups `((group-title . group-candidates) ...)'. The group
>   function should retain the present order of the candidates within the
>   groups.

Sounds fine to me, yes.

[ This touches a delicate issue, of course: since some completion styles
  have their idea of sorting (e.g. `flex`), some UIs have other ideas,
  and then some completion tables have yet more ideas.

  I'm not super-happy with all those functions, to be honest, but it's
  not clear what an API should look like to better decouple the UIs,
  styles, and backends in this respect, so for now the best is probably
  to keep piling on stuff until a clearer picture emerges.  ]

>   This function is used in two ways. After sorting the candidates, the
>   group function is called with the candidate list in order to produce a
>   grouped list. Then the completion UI can call the group function a
>   second time when displaying the candidate groups in order to determine
>   the group titles.

I'd have expected the "list of lists" result to already include the
group titles.

>   This is useful for example if candidates originate from different
>   sources. Grouping is popular in Helm, for example as seen in
>   [helm-m-x].

Of course, it may be difficult for your function to recover the origin
of a candidate if the same candidate can come from two or more sources.

> Proposal 5: Forbid the null completions for `REQUIRE-MATCH=t'
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   If `completing-read' is passed `t' as argument to `REQUIRE-MATCH', the
>   completion must match a candidate from the completion table. However
>   there is also the possibility to exit the minibuffer with a null
>   completion. I propose to disallow this possibility. This change makes
>   it easier for users of `completing-read' since they can rely on
>   setting `REQUIRE-MATCH' to `t' and do not have to handle the null
>   completion specially.
[...]
>   If it is desired to avoid a backward incompatible change one could
>   consider adding a new special value for `REQUIRE-MATCH', for example
>   `'require-candidate', which explicitly forbids null completion.

I generally like the idea (I've also been bothered by this possibility
to return an empty string), but I haven't looked into fixing the
problem.  There's already an obvious way to tell `completing-read`
whether the null string is acceptable (by making the completion-table's
`test-completion` return non-nil for it), so maybe we don't need
a special new value.  But I don't have a good sense of the scale of the
potential compatibility breakage [I suspect that such a change might
also fix some code which doesn't bother to check for an empty output. ]
IOW, this deserves a bit for `grep`ping through all the ELisp code you
can get your hands on and try to see how/if it would be affected by such
a change.

As you say, in the worst case we can introduce a new value for
REQUIRE-MATCH, so as to be backward-compatibility-safe.  But I'd be
interested to see if there are cases where the current empty-string
"(mis)feature" is actually beneficial.

> Proposal 6: Return text properties from `completing-read'
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   As of now, `completing-read' strips text properties from the result
>   string. This behavior is reasonable for strings, which are not present
>   in the collection if `REQUIRE-MATCH/=t'. However if a candidate string
>   is selected, which is a member of the collection, the text properties
>   can be retained. If this is implemented and `REQUIRE-MATCH=t', the
>   user of `completing-read' can always rely on text properties to attach
>   arbitrary data to the candidates.

I think what you mean is that the text properties should be stripped
from the text taken from the minibuffer, but should be preserved from
the text taken from the completion tables's candidates (and then
together with that, you'd want to guarantee that when require-match is
non-nil the string object returned is actually one of those candidates
returned by the completion table)?

This is one of the important differences between "completion" and
"selection" in that completion is about using a completion-table as
a helper to write a chunk of text (but the resulting text in the end
should not be affected by how the user used the completion table to
come up with the final text), whereas selection is about choosing among
a set of candidates and the result is expected to be `eq` to one of
the candidates.

I agree that it would be good to move towards making `completing-read`
better support the "selection" use case.

> Proposal 7: Allow duplicates and retain object identity
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   If a completion table contains duplicates, these duplicates should not
>   be removed. There are not many completion tables which generate
>   duplicate candidates and there exist multiple completion systems which
>   do not perform deduplication at all.

[ I've been resisting this for quite some years, as Drew can testify.  ]

While I agree with preserving object identity, the issue of duplicates
is more problematic, because it means the user can't choose between them
using self-insert-command + RET.  IOW such completion-tables are
fundamentally making assumptions about the kind of UI with which they
can be used.

> Proposal 8: Completion style optimization of filtering and highlighting
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>   While working on Selectrum and Vertico it has been found that
>   highlighting has a significant cost. This matters if the number of
>   displayed candidates differs greatly from the number of filtered
>   candidates. Therefore it would be good to have a possibility to
>   separate highlighting and filtering.

Agreed.  It doesn't seem easy to retro fit this into the current API, tho.
[ The redesign of the completion API which I had started back in 2019
  (see scratch/completion-api for a very rough sketch of the general
  direction) also aimed to fix this.  ]

>   In the Orderless completion-style, there is a variable
>   `orderless-skip-highlighting' which can be set to `t' or to
>   a predicate function. Depending on the value of this variable
>   highlighting is applied or not applied by
>   `completion-all-completions'.

That's not a great solution, but as a temporary patch until we have
a better API it's OK.

>   In the first step, all the candidates can be computed and filtered
>   with `orderless-skip-highlighting=t', see
>   `vertico--recompute-candidates'. Afterwards, when displaying the
>   candidates, the completion UI has to pass the small subset of
>   candidates once again through `completion-all-completions', this time
>   with `orderless-skip-highlighting=nil', see `vertico--highlight'.

I suspect "pass the small subset of candidates once again through
`completion-all-completions'" can be tricky to do (e.g. for things like
file-name completion with `partial-completion`).

>   I propose to generalize this Orderless feature by introducing a
>   variable `completion-skip-highlighting', which behaves the same as
>   `orderless-skip-highlighting' and is implemented for all built-in
>   completion styles. In Orderless, the filtering and highlighting is
>   already separate internally, therefore skipping the highlighting
>   turned out to be a natural decision in Orderless. The situation could
>   be different for the built-in styles.

I think in all styles I can think of highlighting is done as a separate step.

>   As an alternative, one can introduce a third function
>   `completion-highlight-completions', which is specified in
>   `completion-styles-alist'. But I suspect that the introduction of an
>   extra function requires more effort.

I'd rather not go there, indeed.


        Stefan