handling of completion table duplicates

handling of completion table duplicates

[Ingo Lohmar]

Hi Everybody,

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, but I could not find that behavior documented in the elisp
info manual or the docstrings.

Is removing duplicates from the collection *expected* from completion
functions, or is the caller of the function responsible for providing a
collection without duplicates?

If I did not just miss the documentation (in which case I apologize),
should this be documented, and where?

Ingo

Re: handling of completion table duplicates

[Stefan Monnier]

> Is removing duplicates from the collection *expected* from completion
> functions, or is the caller of the function responsible for providing a
> collection without duplicates?

It's the generic completion code that's responsible for that, yes.


        Stefan

Re: handling of completion table duplicates

[Andreas Schwab]

Ingo Lohmar <i.lohmar@gmail.com> writes:

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

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

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

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

RE: handling of completion table duplicates

[Ingo Lohmar]

Thank you, Drew, for that extensive answer.

So I take it that the absence of any documentation on duplicate removal
is intentional (or at least it's no oversight) --- the question would
rather be "why should (or how even could) the handler remove them?"

RE: handling of completion table duplicates

[Drew Adams]

> Thank you, Drew, for that extensive answer.
> 
> So I take it that the absence of any documentation on duplicate removal
> is intentional (or at least it's no oversight) --- the question would
> rather be "why should (or how even could) the handler remove them?"

Not sure whom you're asking or quite what you are asking.
What do you mean by "the handler"?  And are you talking about
vanilla Emacs?  If so, it already removes duplicates.

[Wrt the doc, I think that as long as Emacs keeps the behavior
of deleting duplicates it should document the fact that it does
that.  And if it's not clear enough otherwise, it should say
just what comparison is done to determine sameness.]

RE: handling of completion table duplicates

[Ingo Lohmar]

On Tue, Apr 05 2016 14:42 (-0700), Drew Adams wrote:

>> So I take it that the absence of any documentation on duplicate removal
>> is intentional (or at least it's no oversight) --- the question would
>> rather be "why should (or how even could) the handler remove them?"
>
> Not sure whom you're asking or quite what you are asking.
> What do you mean by "the handler"?  And are you talking about
> vanilla Emacs?  If so, it already removes duplicates.

I just summarized what I gather from this short thread.  By "the
handler" I was referring to completing-read-default et al, who have to
handle a collection for completion.