From: Stefan Monnier <monnier@iro.umontreal.ca>
To: Oleh Krehel <ohwoeowho@gmail.com>
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:26 -0400 [thread overview]
Message-ID: <jwviocqg9mt.fsf-monnier+emacsbugs@gnu.org> (raw)
In-Reply-To: <CAA01p3rfJgkq9DSbktgU9yfgugokGWXa6wrCRrQ13zrwdTeMhQ@mail.gmail.com> (Oleh Krehel's message of "Mon, 20 Apr 2015 10:38:14 +0200")
> 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
next prev parent reply other threads:[~2015-04-20 14: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
2015-04-20 12:30 ` Oleh Krehel
2022-04-17 10:51 ` Lars Ingebrigtsen
2015-04-20 14:38 ` Stefan Monnier [this message]
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=jwviocqg9mt.fsf-monnier+emacsbugs@gnu.org \
--to=monnier@iro.umontreal.ca \
--cc=20365@debbugs.gnu.org \
--cc=ohwoeowho@gmail.com \
/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 external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.