unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Improvement proposals for `completing-read'
@ 2021-04-07 11:16 Daniel Mendler
  2021-04-07 17:11 ` Stefan Monnier
                   ` (3 more replies)
  0 siblings, 4 replies; 89+ messages in thread
From: Daniel Mendler @ 2021-04-07 11:16 UTC (permalink / raw)
  To: emacs-devel

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.



^ permalink raw reply	[flat|nested] 89+ messages in thread

end of thread, other threads:[~2021-04-15 17:10 UTC | newest]

Thread overview: 89+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-07 11:16 Improvement proposals for `completing-read' Daniel Mendler
2021-04-07 17:11 ` Stefan Monnier
2021-04-07 17:20   ` Stefan Monnier
2021-04-07 19:46     ` Daniel Mendler
2021-04-07 21:26       ` Stefan Monnier
2021-04-08  9:01         ` Daniel Mendler
2021-04-08 14:44           ` Stefan Monnier
2021-04-08 15:26             ` Stefan Kangas
2021-04-08 15:47               ` Daniel Mendler
2021-04-08 17:31               ` Stefan Monnier
2021-04-08 15:37             ` Daniel Mendler
2021-04-08 17:22               ` [External] : " Drew Adams
2021-04-08 18:22                 ` Dmitry Gutov
2021-04-08 18:48                   ` Drew Adams
2021-04-08 19:03                     ` Dmitry Gutov
2021-04-08 19:32                       ` Drew Adams
2021-04-08 17:30               ` Stefan Monnier
2021-04-08 17:57                 ` Daniel Mendler
2021-04-08 18:13                   ` Stefan Monnier
2021-04-08 19:15                     ` Daniel Mendler
2021-04-08 19:20               ` Dmitry Gutov
2021-04-08 19:46                 ` [External] : " Drew Adams
2021-04-08 20:12                   ` Dmitry Gutov
2021-04-08 21:12                     ` Drew Adams
2021-04-08 22:37                     ` Stefan Kangas
2021-04-09  0:03                       ` Dmitry Gutov
2021-04-09  2:09                         ` Using more and/or better icons in Emacs Stefan Kangas
2021-04-09  3:09                           ` Lars Ingebrigtsen
2021-04-09  3:35                           ` chad
2021-04-09 12:06                             ` Stefan Kangas
2021-04-09  7:41                           ` Yuri Khan
2021-04-09  9:59                             ` tomas
2021-04-09 11:15                               ` Dmitry Gutov
2021-04-09 11:19                           ` Dmitry Gutov
2021-04-09 12:22                             ` Stefan Kangas
2021-04-09 12:29                               ` Dmitry Gutov
2021-04-09 17:46                                 ` Stefan Kangas
2021-04-09 18:45                                   ` Eli Zaretskii
2021-04-09 19:30                                   ` Alan Third
2021-04-09 19:40                                     ` Alan Third
2021-04-09 22:38                                       ` Dmitry Gutov
2021-04-10  0:56                                       ` Stefan Kangas
2021-04-10  1:43                                         ` Stefan Kangas
2021-04-10  9:12                                           ` Alan Third
2021-04-10 10:56                                             ` Stefan Kangas
2021-04-10 13:48                                               ` Alan Third
2021-04-12 19:39                                                 ` Alan Third
2021-04-13  1:25                                                   ` Stefan Kangas
2021-04-13  7:35                                                     ` Alan Third
2021-04-13 10:39                                                       ` Stefan Kangas
2021-04-13 19:50                                                         ` Alan Third
2021-04-13 22:44                                                           ` Stefan Kangas
2021-04-14  6:46                                                           ` Eli Zaretskii
2021-04-15 15:37                                                             ` Alan Third
2021-04-15 15:50                                                               ` Eli Zaretskii
2021-04-15 17:10                                                                 ` Alan Third
2021-04-11 21:57                                       ` Dmitry Gutov
2021-04-09 23:16                                   ` Alan Third
2021-04-10  0:55                                     ` Stefan Kangas
2021-04-10  7:23                                       ` Eli Zaretskii
2021-04-10  9:17                                         ` Alan Third
2021-04-10  9:25                                           ` Eli Zaretskii
2021-04-08 17:22             ` [External] : Re: Improvement proposals for `completing-read' Drew Adams
2021-04-08 18:33               ` Drew Adams
2021-04-07 23:11       ` Drew Adams
2021-04-08  7:56       ` Eli Zaretskii
2021-04-07 18:39 ` Jean Louis
2021-04-07 19:49   ` Daniel Mendler
2021-04-07 22:16 ` Dmitry Gutov
2021-04-08  8:37   ` Daniel Mendler
2021-04-08 20:44     ` Dmitry Gutov
2021-04-08 21:30       ` Daniel Mendler
2021-04-10  2:21         ` Dmitry Gutov
2021-04-10  9:18           ` Daniel Mendler
2021-04-11  0:51             ` Dmitry Gutov
2021-04-11 13:08               ` Daniel Mendler
2021-04-12  0:32                 ` Dmitry Gutov
2021-04-12  0:40                   ` Daniel Mendler
2021-04-12 10:47                     ` Dmitry Gutov
2021-04-12 11:04                       ` Daniel Mendler
2021-04-14  0:00                         ` Dmitry Gutov
2021-04-14 10:44                           ` Daniel Mendler
2021-04-07 23:49 ` [External] : " Drew Adams
2021-04-08  9:29   ` Daniel Mendler
2021-04-08 17:19     ` Drew Adams
2021-04-09 11:19       ` Jean Louis
2021-04-09 11:47         ` Daniel Mendler
2021-04-09 17:22         ` Drew Adams
2021-04-09 17:41           ` Daniel Mendler

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).