From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Drew Adams Newsgroups: gmane.emacs.bugs Subject: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1 Date: Sun, 19 Apr 2015 07:43:43 -0700 (PDT) Message-ID: <132790ef-aecc-4c38-912b-facfc988abcb@default> References: <87egnhfmcd.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1429454725 4344 80.91.229.3 (19 Apr 2015 14:45:25 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 19 Apr 2015 14:45:25 +0000 (UTC) Cc: 20365@debbugs.gnu.org To: Oleh Krehel , Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Apr 19 16:45:12 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 1YjqT9-00051f-FH for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 16:45:11 +0200 Original-Received: from localhost ([::1]:48751 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjqT8-0005y3-Ow for geb-bug-gnu-emacs@m.gmane.org; Sun, 19 Apr 2015 10:45:10 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:42906) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjqT5-0005vs-1j for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 10:45:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YjqT1-0007uM-S0 for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 10:45:07 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:42793) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YjqT1-0007sg-Ob for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 10:45:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1YjqT1-0006fz-69 for bug-gnu-emacs@gnu.org; Sun, 19 Apr 2015 10:45:03 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Drew Adams Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 19 Apr 2015 14:45: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.142945464225573 (code B ref 20365); Sun, 19 Apr 2015 14:45:02 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 19 Apr 2015 14:44:02 +0000 Original-Received: from localhost ([127.0.0.1]:60802 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjqS1-0006eD-TF for submit@debbugs.gnu.org; Sun, 19 Apr 2015 10:44:02 -0400 Original-Received: from aserp1040.oracle.com ([141.146.126.69]:20975) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1YjqRz-0006dm-BT for 20365@debbugs.gnu.org; Sun, 19 Apr 2015 10:44:00 -0400 Original-Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by aserp1040.oracle.com (Sentrion-MTA-4.3.2/Sentrion-MTA-4.3.2) with ESMTP id t3JEhpMk020727 (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Sun, 19 Apr 2015 14:43:52 GMT Original-Received: from aserv0121.oracle.com (aserv0121.oracle.com [141.146.126.235]) by userv0021.oracle.com (8.13.8/8.13.8) with ESMTP id t3JEhp43002945 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL); Sun, 19 Apr 2015 14:43:51 GMT Original-Received: from abhmp0004.oracle.com (abhmp0004.oracle.com [141.146.116.10]) by aserv0121.oracle.com (8.13.8/8.13.8) with ESMTP id t3JEhoii010882; Sun, 19 Apr 2015 14:43:50 GMT In-Reply-To: X-Priority: 3 X-Mailer: Oracle Beehive Extensions for Outlook 2.0.1.9 (901082) [OL 12.0.6691.5000 (x86)] X-Source-IP: userv0021.oracle.com [156.151.31.71] 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:101718 Archived-At: > It just makes sense for any element of what > `all-completions' returns to be a valid answer. Interesting point of view. Sounds familiar... ;-) http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D1085 > 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. >=20 > 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. FWIW - I agree that the calling code should control duplicate removal. (Definitely, `all-completions' should not do that.) But it can make sense to allow the calling program to optionally "reach inside `completing-read'" to do its duplicate removal. In Icicles, the caller can cause `completing-read' itself to remove duplicates by binding global variable `icicle-transform-function'. Because `completing-read' does some processing (e.g. sorting) after computation of the candidates, this filter promotion into `completing-read' can save some time. It can also give users dynamic control over the candidates to be matched (the completion domain). The value of variable `icicle-transform-function' is a function used to transform the list of completion candidates. Users can toggle such transforming on/off using `C-$' during completion. The most common use, by far, of `icicle-transform-function' is to bind it to a remove-duplicates function. Other uses include switching to a particular subset of candidates, against which user input is then matched. For example, using `C-$' with `icicle-apropos-value' toggles filtering the domain of initial candidates according to the prefix argument, as follows: * no prefix arg: only user options (+ values) * < 0: only commands (+ definitions) * > 0: only faces (+ plists) * =3D 0: only options (+ values), commands (+ defs), faces (+ plists)