RE: handling of completion table duplicates

[Drew Adams]

> > I recently noticed that ivy-mode (at its very core a completing-read
> > alternative, just like ido-completing-read is another one) does *not*
> > eliminate duplicates from the collection it is passed, eg, in form of a
> > plain list.  (completing-read "Prompt: " '("a" "b" "c" "a" "d"))
> > Both completing-read as well as ido-completing-read remove such
> > duplicates,
> 
> all-completions doesn't.  The removal is probably just a side effect
> of the implementation.

Yes.

> > Is removing duplicates from the collection *expected* from completion
> > functions, or is the caller of the function responsible for providing a
> > collection without duplicates?
> 
> IMHO it's the resposibility of the caller to make sure the completion
> table is useful.

Yes.

This question of duplicates has been discussed here before.
http://lists.gnu.org/archive/html/emacs-devel/2013-05/msg00161.html

IMO, `completing-read' too should not remove duplicates, by
default.

It should be possible to bind a variable around its call, to
control whether it does.  (No, the calling sequence should not
be changed at this point.)

One reason for not having it force duplicate removal is the
question of what it means to be a "duplicate".  That judgment
should come only from the caller, not from `completing-read'.

`completing-read' treats its completions only as plain strings
for comparison purposes, including matching, sorting, and
duplicate removal.  (Symbol-name strings are compared, for
symbol candidates.)

But in fact, the raw completion candidates from argument
COLLECTION can be arbitrarily rich, containing much more
information - information that is ignored by the simple
comparisons made now.

A raw candidate can be any of the following (at least):

* A cons (for an alist COLLECTION), and its cdr can be an
  arbitrary Lisp value.

* A symbol, and its plist can be an arbitrary plist, with
  arbitrary Lisp values for the entries.

* A string, and it can have arbitrary text properties, with
  arbitrary Lisp values.  (And this applies also to the car
  of a cons raw candidate.)

* A hash-table key, and it can have an arbitrary Lisp
  value as its associated value.

IOW, `completing-read' can be passed candidates of arbitrary
richness, but it starts by ignoring that richness, in effect
reducing these raw candidates to simple strings.

But there is sufficient generality here for callers of
`completing-read' to retrieve a Lisp value associated with
the plain-string candidate currently used by it.

Candidate removal should be the privilege of the caller,
not `completing-read'.  The caller knows whether it might
want to distinguish two strings that have the same text but
different text properties; or two conses that have the same
string car but different cdrs; etc.

`completing-read' was designed long before there was any
notion or use of cycling among candidates, and thus before
any notion of a "current" candidate.

Its design assumes that the only way to distinguish (choose)
a candidate is to match an input string against a set of
string candidates.  Input is assumed to be by typing (versus
yanking), so text properties are not considered for the input
string.  Simple string-vs-string comparison is the design.

The fact that `completing-read' accepts a COLLECTION arg
that might associate additional information with a string
is a result only of providing for the convenient use of
existing structures (alists, to start with).  It does not
try to make any use of that additional info.

As soon as candidate cycling, for example, is introduced,
there is another way for a user to distinguish a candidate
besides the input string: the current cycling candidate.
(Actually, even before cycling, mouse selection of a
candidate also lets a user pick among "duplicates".)

Of course, a user also needs some way to distinguish
duplicates visually, in order to choose one (e.g., by
cycling or mouse).  This can come in various forms:
annotation, display of additional info during cycling, etc.

---

As one example, Icicles makes extensive use of the ability
to distinguish "duplicate" candidates.  I'm sure that other
applications do too.  In Icicle minor mode, `completing-read'
is redefined to allow for, but not impose, duplicate removal.

An Icicle user can use `C-$' (`icicle-toggle-transforming)
to toggle whether and how the set of candidate completions
is transformed initially.  Typically, this transformation
just removes duplicate candidates.  Programmatically, a
`completing-read' caller can remove duplicates by binding
`icicle-transform-function' to `icicle-remove-duplicates'.

"Sorting Candidates and Removing Duplicates":
https://www.emacswiki.org/emacs/Icicles_-_Sorting_Candidates