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

[Oleh Krehel]

On Mon, Apr 20, 2015 at 4:29 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> That would be fine. It just makes sense for any element of what
>> `all-completions' returns to be a valid answer.
>
> What's a valid answer?

A valid answer is the one that doesn't lead to an error if
`completing-read-function' returns it.
Also, in my experience, having less callbacks leads to easier debugging.
I've looked at the callbacks in `incomplete-mode': the completion
function gets called like 3 times for a single input.

> all-completions will happily return "share/" when completing on
> "/usr/s", even if you're looking for a .tex file rather than a directory
> and even if there's no "share/" in the current directory either.

This would be good if there was a "share/" in the current directory.
I'm fine with the concept of `all-completions' being able to return
"infinite" candidates, but it would be nice if it obeyed some rules.
For instance, ivy-mode can handle the file names being "infinte",
because of the concept of directories being non-terminal completion
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.

> Yet, we don't want all-completions to return elements of the form
> "/home/monnier/private/package/emacs/trunk/lisp/" since that would
> result in a lot of redundancy that then needs to be found&removed.

With a concept of "active directory" and "non-terminal" node this can be done.
"active directory" would be a generic `default-directory', and
"non-terminal" would
be a generic predicate `file-directory-p'.

> So, no, all-completions just doesn't always return "valid answers".
> Instead, it returns chunks of text that can added to some prefix (which
> you can find via `completion-boundaries'), the result of which should be
> a prefix of a valid answer.

We could have the cake and eat it too with my approach described above.

>> About the duplicate entries, I think it should be the responsibility
>> of the caller to remove the duplicates.
>
> 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?

>> 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. And having no assumptions on the data,
the hashing function would be the most basic one.

Oleh