GNU bug report logs - #20365
24.5; all-completions returns duplicates for Info-read-node-name-1

Previous Next

Full log

Message #26 received at 20365 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Oleh Krehel <ohwoeowho <at> gmail.com>, Stefan Monnier
 <monnier <at> iro.umontreal.ca>
Cc: 20365 <at> debbugs.gnu.org
Subject: RE: bug#20365: 24.5; all-completions returns duplicates for
 Info-read-node-name-1
Date: Sun, 19 Apr 2015 07:43:43 -0700 (PDT)

> It just makes sense for any element of what
> `all-completions' returns to be a valid answer.

Interesting point of view.  Sounds familiar... ;-)

http://debbugs.gnu.org/cgi/bugreport.cgi?bug=1085

> About the duplicate entries, I think it should be the responsibility
> of the caller to remove the duplicates.  Here's my line of thought:
> a completion function is expected to have an O(N) complexity, where N
> is the amount of candidates. Removing duplicates is O(N^2) at worst,
> and O(NlogN) at best.  So the completion function should not attempt to
> remove the duplicates. It's doesn't affect the performance when I do
> it for 1000 candidates, but when it's 20k (`describe-function') it
> can have an impact.
> 
> The point is that the collection passed to the completion function
> can be very large, and all but O(N) algorithms should be avoided.  On
> the other hand, the caller knows exactly the type of data that it's
> passing and may be able to remove the duplicates in an efficient
> way.

FWIW -

I agree that the calling code should control duplicate removal.
(Definitely, `all-completions' should not do that.)

But it can make sense to allow the calling program to optionally
"reach inside `completing-read'" to do its duplicate removal.

In Icicles, the caller can cause `completing-read' itself to remove
duplicates by binding global variable `icicle-transform-function'.

Because `completing-read' does some processing (e.g. sorting)
after computation of the candidates, this filter promotion into
`completing-read' can save some time.  It can also give users
dynamic control over the candidates to be matched (the completion
domain).

The value of variable `icicle-transform-function' is a function
used to transform the list of completion candidates.  Users can
toggle such transforming on/off using `C-$' during completion.

The most common use, by far, of `icicle-transform-function' is
to bind it to a remove-duplicates function.  Other uses include
switching to a particular subset of candidates, against which
user input is then matched.

For example, using `C-$' with `icicle-apropos-value' toggles
filtering the domain of initial candidates according to the
prefix argument, as follows:

 * no prefix arg: only user options (+ values)
 *           < 0: only commands (+ definitions)
 *           > 0: only faces (+ plists)
 *           = 0: only options (+ values), commands (+ defs),
                  faces (+ plists)

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.