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

Previous Next

Full log

View this message in rfc822 format

From: Oleh Krehel <ohwoeowho <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 20365 <at> debbugs.gnu.org
Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1
Date: Sun, 19 Apr 2015 13:53:14 +0200

> We could change the Info-mode completion table so as to include the
> closing paren in the output of `all-completions' (and probably include
> the opening paren as well, in that case).  Note also that on my system
> "g (ema TAB" includes things like "emacs23/" where "(emacs23/)" is not
> a valid element (since emacs-23 is a directorym which is complete in
> steps, just as in C-x C-f).

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

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.

Oleh

Previous Next

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