Re: Improvement proposals for `completing-read'

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

BTW, rereading the below, I see I'm sounding a bit too authoritative.
I'm the original author of the minibuffer.el completion code, but
remember that what I wrote is just my opinion: you'll want to
convince the actual maintainers for some of those changes ;-)


        Stefan


Stefan Monnier [2021-04-07 13:11:39] wrote:

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