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

[Stefan Monnier]

> nodes. This concept can be adapted to all compltetion types with
> "infinite" candidates. And there would be zero confusion:
> `all-completions' would immediately return a list of strings, some of
> them terminal nodes, some of them "directories".  Then it only remains
> to provide a generic `file-directory-p' and we're done.

Yes, that's also what I was thinking.  Basically, if all-completions
returns something which requires further input, then this something
should include the "terminating char" which makes completion-boundaries
change (which is how to detect that your candidate list is out-of-date
because the input has "moved to another directory").

>> That's the case currently.  The completion-table is called and the
>> caller is the UI, and currently it's the UI's responsibility to remove
>> the duplicates.
> So Info returning duplicates is a bug that should be fixed?

Our UI already does remove duplicates (not in info.el, of course, since
our UI is in minibuffer.el).

>>> 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.
>> Actually, with a hash-table it's pretty much down to O(N).
> Yeah, but we're not using that.

Not sure who's "we", here.  But the point is that if the performance of
delete-dups becomes a problem, it can be improved.

> And having no assumptions on the data, the hashing function would be
> the most basic one.

I don't think that should make much difference: (make-hash-table :test #'equal)
should work just fine.


        Stefan