From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.bugs Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Date: Mon, 20 Apr 2015 10:38:26 -0400 Message-ID: References: <87egnhfmcd.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1429540827 6535 80.91.229.3 (20 Apr 2015 14:40:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 20 Apr 2015 14:40:27 +0000 (UTC) Cc: 20365@debbugs.gnu.org To: Oleh Krehel Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Apr 20 16:40:13 2015 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1YkCrs-0000HK-Qh for geb-bug-gnu-emacs@m.gmane.org; Mon, 20 Apr 2015 16:40:12 +0200 Original-Received: from localhost ([::1]:53956 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YkCrs-0003gZ-1o for geb-bug-gnu-emacs@m.gmane.org; Mon, 20 Apr 2015 10:40:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35245) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YkCro-0003ey-Ey for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 10:40:09 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YkCrl-0001Li-4D for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 10:40:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:43914) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YkCrl-0001Ks-1s for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 10:40:05 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1YkCrj-0006Pz-Vt for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 10:40:04 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 20 Apr 2015 14:40:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 20365 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 20365-submit@debbugs.gnu.org id=B20365.142954075824608 (code B ref 20365); Mon, 20 Apr 2015 14:40:03 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 20 Apr 2015 14:39:18 +0000 Original-Received: from localhost ([127.0.0.1]:33690 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YkCqz-0006Op-N8 for submit@debbugs.gnu.org; Mon, 20 Apr 2015 10:39:18 -0400 Original-Received: from mercure.iro.umontreal.ca ([132.204.24.67]:37232) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YkCqx-0006Oh-In for 20365@debbugs.gnu.org; Mon, 20 Apr 2015 10:39:16 -0400 Original-Received: from hidalgo.iro.umontreal.ca (hidalgo.iro.umontreal.ca [132.204.27.50]) by mercure.iro.umontreal.ca (Postfix) with ESMTP id 560EC85FBF; Mon, 20 Apr 2015 10:38:55 -0400 (EDT) Original-Received: from lechon.iro.umontreal.ca (lechon.iro.umontreal.ca [132.204.27.242]) by hidalgo.iro.umontreal.ca (Postfix) with ESMTP id 1009E1E5B8B; Mon, 20 Apr 2015 10:38:27 -0400 (EDT) Original-Received: by lechon.iro.umontreal.ca (Postfix, from userid 20848) id E02FCB40DC; Mon, 20 Apr 2015 10:38:26 -0400 (EDT) In-Reply-To: (Oleh Krehel's message of "Mon, 20 Apr 2015 10:38:14 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) X-DIRO-MailScanner-Information: Please contact the ISP for more information X-DIRO-MailScanner: Found to be clean X-DIRO-MailScanner-SpamCheck: n'est pas un polluriel, SpamAssassin (score=-2.82, requis 5, autolearn=not spam, ALL_TRUSTED -2.82, MC_TSTLAST 0.00) X-DIRO-MailScanner-From: monnier@iro.umontreal.ca X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:101755 Archived-At: > 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