Improvement proposals for `completing-read'

[Daniel Mendler]

While working on a set of packages around completion ([Selectrum],
[Consult], [Marginalia], [Embark], [Orderless], [Vertico], ...) it
became clear that there are a few spots where improvements to the
`completing-read' API can be made. After submitting my Vertico package
to GNU ELPA two days ago there has been the follow-up discussion in the
thread "Stepping Back: A Wealth Of Completion systems", where the
potential introduction of a `selecting-read' function has been proposed
by Philip Kaludercic. I want to respond to that and echo the opinion
stated by Stefan Monnier:

      I kind of agree, yet at the same time, the difference
      between the two is very small in most cases. So I think it
      might be worthwhile to look at it instead as making it
      possible for the caller to give a *hint* about what kind of
      UI would be best.

      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
the effort for the implementors of completion UIs. If a replacement can
be made which supersedes `completing-read' fully, this cost is reduced,
but such a change is still very impactful given that many packages use
`completing-read'.

I see `completing-read' as a comparatively complicated API, which is
hard use and hard to implement in its full extent. For the end-user it
helps to wrap the function in a more friendly API. Eric Abrahamsen has
used such an approach in his Gnorb package, see
`gnorb-select-from-list'. I have done the same in my Consult package,
see `consult--read'. Maybe moving to a more comfortable (but mostly
`completing-read' compatible) API would mitigate the usability issues
people are observing?

For now I want to be a bit more concrete and look at `completing-read'
and `minibuffer.el' directly and propose a few moderate improvements.
The improvements can help package authors in the short term, since they
address issues with the current state of the API. I am willing to
follow-up with patches, which implement the proposals.

The proposals have been inspired by the work on the aforementioned
packages and came to light in discussions with the respective authors of
the packages: Clemens Radermacher of Selectrum, Omar Antolín Camarena of
Embark and Orderless, and also Dmitry Gutov and Protesilaos Stavrou.

I am very much interested in your opinion regarding the following
proposals.

Daniel Mendler


[Selectrum] <https://github.com/raxod502/selectrum>

[Consult] <https://github.com/minad/consult>

[Marginalia] <https://github.com/minad/marginalia>

[Embark] <https://github.com/oantolin/embark>

[Orderless] <https://github.com/oantolin/orderless>

[Vertico] <https://github.com/minad/vertico>


Improvement proposals for `completing-read'
===========================================

  .. Proposal 1: Disabling the history
  .. Proposal 2: More efficient sorting
  .. Proposal 3: Sort file names by history
  .. Proposal 4: Add support for `group-function'
  .. Proposal 5: Forbid the null completions for `REQUIRE-MATCH=t'
  .. Proposal 6: Return text properties from `completing-read'
  .. Proposal 7: Allow duplicates and retain object identity
  .. Proposal 8: Completion style optimization of filtering and 
highlighting


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


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


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. The Vertico package contains the
  function `vertico--sort' which special cases file names. This approach
  could be adopted by `completion-all-sorted-completions'.

  Unfortunately `vertico--sort' does not sort file names by history if
  the file names are completed using `partial-completion' and I have not
  found an efficient way to do that. More generally, one may want to
  sort completion candidates if `completion-boundaries' are used by the
  `minibuffer-completion-table'. However since sorting files already
  requires special casing and files are most important, I did not
  implement this in `vertico--sort'.


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.

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

  For now, I implemented `group-function' support under the name
  `x-group-function' in the Vertico package. My Consult package uses
  this functionality for candidates originating from [multiple sources].

  Grouping can be added to the default completion system by modifying
  `completion-all-sorted-completions' and `completion--insert-strings'.
  A proof of concept can be found on the [Consult wiki].

  Furthermore support for `x-group-function' has been added to
  [Selectrum] and the external [Icomplete-vertical] package, which is to
  be distinguished from the Icomplete-vertical patches proposed on
  emacs-devel.


[helm-m-x] <https://tuhdo.github.io/static/part3/helm-m-x.gif>

[multiple sources] <https://github.com/minad/consult#multiple-sources>

[Consult wiki] <https://github.com/minad/consult/wiki/Grouping-support>

[Selectrum] <https://github.com/raxod502/selectrum>

[Icomplete-vertical] <https://github.com/oantolin/icomplete-vertical>


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.

  Note that null completion cannot occur if a default value is passed to
  `completing-read'. Therefore null completion can be avoided by a
  wrapper, which passes a special default argument. Unfortunately this
  leads to flicker.

  ,----
  | (defun completing-read-non-null (prompt table)
  |   (let ((ret))
  |     (while (eq (setq ret (completing-read prompt table nil t nil nil
  |                                           'null-completion))
  |                'null-completion))
  |     ret))
  | (completing-read-non-null "Prompt: " '(first second third))
  `----

  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.


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. When storing the selected candidate
  in the history, the text properties should still be stripped to avoid
  serialization problems. There is still null completion, see Proposal
  5. As of now the user has to look up the associated data in an an
  association list, but there is the more serious issue of duplicate
  candidates as addressed in the next section.

  Example:
  ,----
  | (completing-read "Text properties: "
  |                  (list (propertize "first" 'id 0)
  |                        (propertize "second" 'id 1)
  |                        (propertize "third" 'id 2))
  |                  nil t)
  `----


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.

  It is reasonable to handle the deduplication on a case by case basis
  in each completion table. Furthermore empty strings are removed by
  default completion for some reason. I rather consider this a bug in a
  completion table if it returns undesired empty candidates.

  Allowing duplicates is slightly more efficient and allows to retain
  the object identity of the candidates. If a candidate is selected
  which is part of the collection, this exact candidate should be
  returned. This subsumes Proposal 6 and allows to use text properties
  for disambiguation of candidates.

  Note that this proposal is useful mainly for completion tables which
  disable sorting by setting `display/cycle-sort-function' to the
  identity function. Currently if identical candidate strings are used
  for completion, these strings must be manually disambiguated by adding
  some unique prefixes or suffixes. I had this issue when implementing
  the `consult-line' command, which is a Swiper-like command based on
  `completing-read'. Furthermore the disambiguation issue occurs when
  mixing candidates from different candidate sources.

  Example:
  ,----
  | (completing-read "Duplicates: "
  |                  (list (propertize "dup" 'id 0)
  |                        (propertize "dup" 'id 1)
  |                        (propertize "dup" 'id 2))
  |                  nil t)
  `----


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

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

  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.