RE: [External] : Improvement proposals for `completing-read'

[Drew Adams <drew.adams@oracle.com>]

> I see `completing-read' as a comparatively complicated API, which is
> hard use and hard to implement in its full extent.

You see that.  OK.  Specifics?  Complicated, sure,
maybe.  Like Emacs.  But hard to use and hard to
implement?  How so?

> For the end-user it helps to wrap the function in a more friendly API.

How does it help?  What's more friendly about it?
What's the problem you it tries to solve?

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

More "comfortable" in what way?

What usability issues?  (This sounds like the
classic, "When did you stop beating your wife?")

> For now I want to be a bit more concrete

Thank goodness.

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

Please specify the issues - "a bit more concrete",
please.

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

How about specifying whatever's relevant that you
feel came out of those discussions?  Or should we
just accept that the Summit Meeting has decided?

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

I'd like to hear about the problems the proposals
are meant to solve.

> Improvement proposals for `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.

What's the problem?  How does it hurt for users to
have the default history, `minibuffer-history',
available?  They don't have to use it, right?

Is your complaint about the time to sort it (see next)?

I'm not saying I'm opposed to your proposed solution.
I'm saying I haven't seen the problem specified that
you're trying to solve.

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

I'm all for more sort orders and faster sort orders.
Who wouldn't be?

But I'd propose to not sort in any hard-coded way, and
to let _users_ control what sort orders are used where.

A given command (or category of completion candidates,
or...) can provide a given set of sort orders for
users to choose from.

In Icicles that's the case.  And users can change
the possible sort orders and groups of orders.  They
can even customize the sort orders used for choosing
among sort orders (that too is on the fly with
completion).

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

See above.  Like other kinds of candidates, there are
umpteen interesting/useful ways to sort file-name
candidates.

These are the sort orders Icicles provides by default
for file-name candidates.

 alphabetical
 by 2nd parts alphabetically
 by directories first 
 by directories last 
 by file type
 by flx score
 by last file
 access time 
 by last file modification time
 by last use
 by last use as input
 by last use, dirs first 
 by previous use alphabetically
 case insensitive
 extra candidates first
 special candidates first 
 turned OFF

[`by 2nd parts alphabetically' is generic for commands
 that let you input two or more patterns, to complete
 against two or more "parts" of completion candidates
 (each part is optional).

 In the case of files, the two parts are (1) file name
 and (2) file contents.  So sorting `by 2nd parts
 alphabetically' for file-name candidates sorts first
 by the matches against file content, alphabetically.]

And it's trivial to define new sort orders, using
macro `icicle-define-sort-command'.

To be clear: this is not an advertisement for Icicles.
It's an argument that there are many useful ways to
sort, and users should be able to choose, on the fly.

> Proposal 4: Add support for `group-function'
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 
>    Grouping can be added to the default completion system by modifying
>    `completion-all-sorted-completions' and `completion--insert-strings'.

So the overall problem you say you want to solve is
that `completing-read' is too complex, hard to use,
and hard to implement.  Yet you want to add something
like this, to make it even more complex and hard to
implement? ;-)

Don't get me wrong.  I'm actually inclined toward
some such grouping behavior, FWIW.

My main concern about further complicating the code
implementing `completing-read' is that things will
end up hard-coded - and hence difficult to use by
users and by implementers of 3rd-party code.

One person's brilliant once-and-for-all optimization
can be another person's hard-coded ball & chain.

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

When you say users, here, you mean people who write
code that uses `completing-read', not users of such
code, right?

Why is this a problem for these coders?  I've never
encountered a problem in this regard.  Can you specify
a problem here?

Empty completion returning a special value (namely "")
lets code know that the user provided empty completion.
That's a _feature_.

Code can do _anything_ it wants in that case.  Why
would we hard-code the behavior, by disallowing
`completing-read' callers from knowing that a user
provided empty input?

Again, maybe you have a good reason or two why this
is needed.  But so far you've mentioned only the
difficulty for coders - and you've shown no example
of even that difficulty.

You propose to take away knowledge by code of what
a user input action was.  Why?  What real problem
is this meant to solve?

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

Most of what you write here (90%) seems to be about
solutions so far, without the problems having been
presented yet.  I think I see more about what you
think are handicaps for implementers and less about
what might benefit users.  That seems backwards, as
an Emacs priority.

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

Much better!  But I still wonder what the use case
(problem) is.

> Proposal 6: Return text properties from `completing-read'
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

100% agreement.  I proposed this a zillion years ago
(and added it to Icicles).  Rejected for Emacs.  But
this feature should only be _possible_, not imposed.

I did finally get vanilla Emacs to not strip text
properties by default for `read-from-minibuffer' and
`read-string'.  But this was refused for "any of the
functions that do minibuffer input with completion;
they always discard text properties."  (`C-h v
minibuffer-allow-text-properties')

In Icicles this is governed by option
`icicle-unpropertize-completion-result-flag':

  Non-nil means strip text properties from the completion result.
  Set or bind this option to non-nil only if you need to ensure,
  for some other library, that the string returned by
  `completing-read' and `read-file-name' has no text properties.

  Typically, you will not use a non-nil value.  Internal text
  properties added by Icicles are always removed anyway.  A
  non-nil value lets you also remove properties such as `face'.

  Remember that you can use multi-command `icicle-toggle-option'
  anytime (`M-i M-i' during completion) to toggle an option
  value.

> Proposal 7: Allow duplicates and retain object identity
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 
>    If a completion table contains duplicates, these
>    duplicates should not be removed.

Absolutely.  This mania was perhaps a side effect of
those enamoured by the introduction of hash tables to
Emacs.  Such no-duplicate-keys maps are great; they
have their place.  But it doesn't follow that there
are no use cases for completion where the candidates
you choose among are duplicates.

It's a great thing (though admittedly sometimes a bit
of a bother) that for Emacs a completion candidate
that you choose is a string but the "full candidate"
for the underlying program can be an alist entry, a
hash-table key+value pair, etc.

(Even cases where both the key and value are equal -
in whatever sense - are possible.  But typically only
the keys are duplicates.)

This feature is used often in my code.  And in many
cases I put the "full candidate" thingy on the string
that gets displayed to users as a text property, for
unambiguous retrieval of the full value from the
returned chosen string.

(Of course, if the returned string doesn't result
from choosing a candidate but from user text input,
that changes possibilities - it won't carry the full
candidate on its shoulder.)

>    There are not many completion tables which generate
>    duplicate candidates

Do you mean not many _kinds_ of completion tables,
or not many completion tables (in practice)?  If
you mean the latter, I'd like to know why you think
that, as I doubt it's the case.  (No, I don't have
numbers either.)

>    and there exist multiple completion systems
>    which do not perform deduplication at all.

Icicles among them.

Or, rather, this is under program control.  And
even under user control.  [You may be sensing a
pattern, here...  More user control, less
deciding at design time (aka hard-coding).]

Variable `icicle-transform-function':

  Function used to transform the list of completion candidates.
  This is applied to the list of initial candidates.
  If this is nil, then no transformation takes place.

  You can toggle this at any time from the minibuffer using `C-$,'.

  The value is changed by program locally, for use in particular
  contexts.  E.g., when you use `C-c C-`' (`icicle-search-generic')
  in a `*shell*' buffer, Icicles uses this variable with a value of
  `icicle-remove-duplicates', to remove duplicate shell commands
  from your input history list.

  You can use this variable in your Lisp code to transform the list
  of candidates any way you like.  A typical use is to remove
  duplicates, by binding it to `icicle-remove-duplicates' or
  `icicle-remove-dups-if-extras'.

Interactively, `C-$' can behave differently,
depending on the current command (actually, the
current use of `completing-read').

>    It is reasonable to handle the deduplication on a
>    case by case basis in each completion table. 

Amen.

>    Allowing duplicates is slightly more efficient and
>    allows to retain the object identity of the candidates.

The latter is the reason to retain this feature.
It's important.  The former isn't important, IMO.

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

Why?  (I'm pretty sure I disagree.)

But maybe you just mean that if you sort the
candidates by taking their "object identity" into
account then that can help determine just which
duplicate a user chose.

If so, that's just implementation.  And it can
mean jumping through additional hoops.

>    Currently if identical candidate strings are used for
>    completion, these strings must be manually disambiguated

Yes.  And relying on a sort order to disambiguate
them is yet another roundabout hack.  Même combat.

>    Furthermore the disambiguation issue occurs when
>    mixing candidates from different candidate sources.

Indeed.

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

Again, please explain just what's been found,
instead of reporting what you've decided.  Details
matter.  What kind of highlighting?  When and how
was highlighting done, and to what?  What was tried?
In what contexts?  Just what problems were found?

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

If you're critiquing the highlighting done by
vanilla `completing-read', then I agree that such
highlighting isn't great.  Too eager (too early),
and too blanket (hard-coded).

As Stefan said recently, that old highlighting
was OK for simple prefix matching.  It just gets
in the way for other kinds of matching.

Icicles just tosses that highlighting
(both `completions-common-part' and
`completions-first-difference') out the window
and uses its own.

(defun icicle-undo-std-completion-faces ()
  "Get rid of standard completion-root highlighting in `*Completions*'."
  (when (fboundp 'face-spec-reset-face)
    (when (facep 'completions-common-part)
      (face-spec-reset-face 'completions-common-part)
      (set-face-attribute 'completions-common-part nil :inherit nil))
    (when (facep 'completions-first-difference)
      (face-spec-reset-face 'completions-first-difference)
      (set-face-attribute 'completions-first-difference nil :inherit nil))))

Icicles does the following kind of common-match
expansion (by default), and yes, highlighting can
be hard/problematic for some kinds of matching.

https://www.emacswiki.org/emacs/Icicles_-_Expanded-Common-Match_Completion

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

I do it in (I think) a simpler way in Icicles.
`completion-all-completions' shouldn't be involved
at all, IMO.  Icicles does it only in the function
that displays the _current_ set of candidates,
`icicle-display-candidates-in-Completions'.

And users can in rare cases control whether such
highlighting is done.  For Info commands where
completion candidates are node names, you can
optionally have candidates for already-visited nodes
be highlighted differently in *Completions*.  But
that's costly.  You can have this off by default and
just highlight them on demand with `C-x C-M-l'.
_____


General critique: Please present _one_ proposal per
thread, for consideration.  This thing about a Yalta
meeting having taken place and someone descending
from the summit with stone tables presenting the
IX Proposals isn't so helpful, IMO.

Admittedly, there are some relations among some of
them.  But still.

I propose that each proposal be submitted as a
separate enhancement request: `M-x report-emacs-bug'.
It could still be discussed more widely here, though.

And I'm glad people are thinking about, discussing,
and implementing such things.  Hooray!  So please
don't take my comments here too negatively.
Contradiction ~> progress.