unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
From: Oleh Krehel <ohwoeowho@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: 20365@debbugs.gnu.org
Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1
Date: Mon, 20 Apr 2015 10:38:14 +0200	[thread overview]
Message-ID: <CAA01p3rfJgkq9DSbktgU9yfgugokGWXa6wrCRrQ13zrwdTeMhQ@mail.gmail.com> (raw)
In-Reply-To: <jwvzj63mtcp.fsf-monnier+emacsbugs@gnu.org>

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





  reply	other threads:[~2015-04-20  8:38 UTC|newest]

Thread overview: 18+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-04-18 16:11 bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Oleh Krehel
2015-04-18 17:41 ` Stefan Monnier
2015-04-18 17:49   ` Oleh Krehel
2015-04-19  2:04     ` Stefan Monnier
2015-04-19 11:53       ` Oleh Krehel
2015-04-19 14:43         ` Drew Adams
2015-04-19 16:44         ` Dmitry Gutov
2015-04-19 17:00           ` Oleh Krehel
2015-04-19 17:12             ` Dmitry Gutov
2015-04-20  2:29         ` Stefan Monnier
2015-04-20  8:38           ` Oleh Krehel [this message]
2015-04-20 12:30             ` Oleh Krehel
2022-04-17 10:51               ` Lars Ingebrigtsen
2015-04-20 14:38             ` Stefan Monnier
2015-04-20 14:52               ` Oleh Krehel
2015-04-20 19:14                 ` Stefan Monnier
2015-04-18 23:40   ` Drew Adams
2015-04-19  1:50     ` Stefan Monnier

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAA01p3rfJgkq9DSbktgU9yfgugokGWXa6wrCRrQ13zrwdTeMhQ@mail.gmail.com \
    --to=ohwoeowho@gmail.com \
    --cc=20365@debbugs.gnu.org \
    --cc=monnier@iro.umontreal.ca \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).