From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Oleh Krehel Newsgroups: gmane.emacs.bugs Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Date: Sun, 19 Apr 2015 13:53:14 +0200 Message-ID: References: <87egnhfmcd.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1429444463 16769 80.91.229.3 (19 Apr 2015 11:54:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Apr 2015 11:54:23 +0000 (UTC) Cc: 20365@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Apr 19 13:54:14 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 1Yjnnh-0002xI-C4 for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 13:54:13 +0200 Original-Received: from localhost ([::1]:48171 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yjnng-0006YF-N2 for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 07:54:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:40555) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yjnnc-0006Y7-Aq for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 07:54:09 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YjnnX-0000Bt-7S for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 07:54:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42456) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjnnX-0000Bp-3i for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 07:54:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1YjnnW-0002Zf-Dm for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 07:54:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Oleh Krehel Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 19 Apr 2015 11:54:02 +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.14294444039846 (code B ref 20365); Sun, 19 Apr 2015 11:54:02 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 19 Apr 2015 11:53:23 +0000 Original-Received: from localhost ([127.0.0.1]:60465 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yjnmt-0002Yk-2P for submit@debbugs.gnu.org; Sun, 19 Apr 2015 07:53:23 -0400 Original-Received: from mail-wi0-f179.google.com ([209.85.212.179]:38614) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yjnmq-0002YV-HO for 20365@debbugs.gnu.org; Sun, 19 Apr 2015 07:53:21 -0400 Original-Received: by wiun10 with SMTP id n10so63109298wiu.1 for <20365@debbugs.gnu.org>; Sun, 19 Apr 2015 04:53:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Dbjzf8Ps0vt+SxHWI5h37nnBHm8V1fdJ7yAmlakFBcI=; b=UUtbvg7FBd+xND4tP1fsRZR2T1Hr/6mbqOfY+5ZRn6t9rmuL6OfW7Yggd8CoEFuUMO 57VF7YUK2Vk8uUm7fcBCMJNsJqElHGxpb+Xjk6nzlzN38FVb/NiboC/habFKXNS/jcy5 WCvUBJhTYoDzuPNBZNs/RbI7WJeeNmVveKptx+tgDXxWD38oUHcj4Kd62jU5iW0TzBV7 JRUjeXjgaQo5hHvbq7NVXCuIEJrzqUfZw7LVdbidPAfqCYYFwdtdxpljSbiPLfP2v/mF k2yHddASrvSw8QWFXHXWbsIBuxhvJr6xB2gh9ZqYUXivZ4j7PEIPztzFRntBoRvPVHXu 1S7w== X-Received: by 10.194.161.193 with SMTP id xu1mr9490371wjb.48.1429444394807; Sun, 19 Apr 2015 04:53:14 -0700 (PDT) Original-Received: by 10.27.215.21 with HTTP; Sun, 19 Apr 2015 04:53:14 -0700 (PDT) In-Reply-To: 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:101711 Archived-At: > We could change the Info-mode completion table so as to include the > closing paren in the output of `all-completions' (and probably include > the opening paren as well, in that case). Note also that on my system > "g (ema TAB" includes things like "emacs23/" where "(emacs23/)" is not > a valid element (since emacs-23 is a directorym which is complete in > steps, just as in C-x C-f). That would be fine. It just makes sense for any element of what `all-completions' returns to be a valid answer. About the duplicate entries, I think it should be the responsibility of the caller 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. So the completion function should not attempt to remove the duplicates. It's doesn't affect the performance when I do it for 1000 candidates, but when it's 20k (`describe-function') it can have an impact. The point is that the collection passed to the completion function can be very large, and all but O(N) algorithms should be avoided. On the other hand, the caller knows exactly the type of data that it's passing and may be able to remove the duplicates in an efficient way. Oleh