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: Sun, 19 Apr 2015 22:29:00 -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 1429497030 4470 80.91.229.3 (20 Apr 2015 02:30:30 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 20 Apr 2015 02:30:30 +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 04:30:16 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 1Yk1TT-0001lM-FM for geb-bug-gnu-emacs@m.gmane.org; Mon, 20 Apr 2015 04:30:15 +0200 Original-Received: from localhost ([::1]:51608 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk1TS-0003oP-DP for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 22:30:14 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56394) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk1TO-0003nz-R1 for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 22:30:11 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yk1TJ-0003pk-Nx for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 22:30:10 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:43054) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk1TJ-0003ow-K4 for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 22:30:05 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Yk1TI-0007uE-Iw for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 22:30: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 02:30:04 +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.142949694430296 (code B ref 20365); Mon, 20 Apr 2015 02:30:04 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 20 Apr 2015 02:29:04 +0000 Original-Received: from localhost ([127.0.0.1]:32830 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yk1SJ-0007sZ-UU for submit@debbugs.gnu.org; Sun, 19 Apr 2015 22:29:04 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:46366) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yk1SH-0007sA-Lg for 20365@debbugs.gnu.org; Sun, 19 Apr 2015 22:29:02 -0400 Original-Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id t3K2T0Cn021100; Sun, 19 Apr 2015 22:29:00 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 2872C282C; Sun, 19 Apr 2015 22:29:00 -0400 (EDT) In-Reply-To: (Oleh Krehel's message of "Sun, 19 Apr 2015 13:53:14 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV5281=0 X-NAI-Spam-Version: 2.3.0.9393 : core <5281> : inlines <2753> : streams <1425373> : uri <1910934> 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:101742 Archived-At: > 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? 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. 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. 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. > 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. > 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). Stefan