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: Mon, 20 Apr 2015 10:38: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 1429519166 32337 80.91.229.3 (20 Apr 2015 08:39:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 20 Apr 2015 08:39:26 +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 Mon Apr 20 10:39:18 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 1Yk7Ea-0004iH-3b for geb-bug-gnu-emacs@m.gmane.org; Mon, 20 Apr 2015 10:39:16 +0200 Original-Received: from localhost ([::1]:52324 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk7EZ-0004yk-GQ for geb-bug-gnu-emacs@m.gmane.org; Mon, 20 Apr 2015 04:39:15 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38215) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk7EQ-0004sG-5O for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 04:39:12 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yk7EM-0002KQ-U1 for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 04:39:06 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:43219) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yk7EM-0002KL-Ql for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 04:39:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Yk7EM-0008Uw-JX for bug-gnu-emacs@gnu.org; Mon, 20 Apr 2015 04:39: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: Mon, 20 Apr 2015 08:39: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.142951910332614 (code B ref 20365); Mon, 20 Apr 2015 08:39:02 +0000 Original-Received: (at 20365) by debbugs.gnu.org; 20 Apr 2015 08:38:23 +0000 Original-Received: from localhost ([127.0.0.1]:32995 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yk7Di-0008Tx-L7 for submit@debbugs.gnu.org; Mon, 20 Apr 2015 04:38:23 -0400 Original-Received: from mail-wi0-f169.google.com ([209.85.212.169]:37314) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Yk7Dg-0008Tb-HO for 20365@debbugs.gnu.org; Mon, 20 Apr 2015 04:38:21 -0400 Original-Received: by widdi4 with SMTP id di4so82446932wid.0 for <20365@debbugs.gnu.org>; Mon, 20 Apr 2015 01:38: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=z1H7buDyfc322rTjGFebUb5wdOLnxwt2zYw+4azy98I=; b=nspW+7pd2w0bDz/MsWKWfMr8MQwAETo48LMc0/2Ev0alNIcDwxvsEMX+25JuImfCkq ybcMO4qPOSNW8ZHmGl/20LkiurMiayoRpWZAuK9gUC4B4JVSPXCykqnHU62nsNA+tyad 7ZTL7nnn5eiCd+SPXW96Njk7wd0Hw7ERKa+bRri5vXf5nvMU5FMS8T+hkrNZlrDVKr2e 20oeOo55UTnszaKZTRL7R8llfmdc8oNPaYclDwtXbn9JlCzb8+/bvyO0703FpsNknNsS q3BoEtGUmDEBLVwMkWRGARWm0sWjxpINJML+Qz+R3FvLEdHRdSEgXcqOuuZSZP5tE6gt oR6A== X-Received: by 10.180.95.36 with SMTP id dh4mr23552819wib.82.1429519094773; Mon, 20 Apr 2015 01:38:14 -0700 (PDT) Original-Received: by 10.27.215.21 with HTTP; Mon, 20 Apr 2015 01:38: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:101749 Archived-At: On Mon, Apr 20, 2015 at 4:29 AM, Stefan Monnier wrote: >> 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? A valid answer is the one that doesn't lead to an error if `completing-read-function' returns it. Also, in my experience, having less callbacks leads to easier debugging. I've looked at the callbacks in `incomplete-mode': the completion function gets called like 3 times for a single input. > 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. This would be good if there was a "share/" in the current directory. I'm fine with the concept of `all-completions' being able to return "infinite" candidates, but it would be nice if it obeyed some rules. For instance, ivy-mode can handle the file names being "infinte", because of the concept of directories being non-terminal completion 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. > 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. With a concept of "active directory" and "non-terminal" node this can be done. "active directory" would be a generic `default-directory', and "non-terminal" would be a generic predicate `file-directory-p'. > 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. We could have the cake and eat it too with my approach described above. >> 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. So Info returning duplicates is a bug that should be fixed? >> 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. And having no assumptions on the data, the hashing function would be the most basic one. Oleh